node_connection_list.h

Go to the documentation of this file.

/*
 * Copyright 2023 MusicScience37 (Kenta Kabashima)
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
#pragma once
 
#include <span>
 
#include "num_collect/base/index_type.h"
#include "num_collect/util/assert.h"
#include "num_collect/util/vector.h"
 
namespace num_collect::linear::impl::amg {
 
template <typename StorageIndex = int>
class node_connection_list {
public:
    using storage_index_type = StorageIndex;
 
    node_connection_list() {
        begin_indices_.push_back(static_cast<storage_index_type>(0));
    }
 
 
    void initialize() {
        node_indices_.clear();
        begin_indices_.clear();
        begin_indices_.push_back(static_cast<storage_index_type>(0));
    }
 
    void push_back(storage_index_type node_index) {
        node_indices_.push_back(node_index);
    }
 
    void finish_current_node() {
        begin_indices_.push_back(
            static_cast<storage_index_type>(node_indices_.size()));
    }
 
 
 
    [[nodiscard]] auto num_nodes() const -> index_type {
        return static_cast<index_type>(begin_indices_.size()) -
            static_cast<index_type>(1);
    }
 
    [[nodiscard]] auto connected_nodes_to(index_type node_index) const
        -> std::span<const storage_index_type> {
        return std::span<const storage_index_type>(
            // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
            node_indices_.data() + begin_indices_[node_index],
            // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
            node_indices_.data() + begin_indices_[node_index + 1]);
    }
 
 
    [[nodiscard]] auto transpose() const
        -> node_connection_list<storage_index_type> {
        const auto num_nodes_cached =
            static_cast<storage_index_type>(num_nodes());
 
        util::vector<storage_index_type> begin_indices(
            begin_indices_.size(), static_cast<storage_index_type>(0));
        for (const storage_index_type index : node_indices_) {
            NUM_COLLECT_DEBUG_ASSERT(index < num_nodes_cached);
            ++begin_indices[index + 1];
        }
        for (index_type i = 1; i < begin_indices.size() - 1; ++i) {
            begin_indices[i + 1] += begin_indices[i];
        }
        NUM_COLLECT_DEBUG_ASSERT(begin_indices_.back() == node_indices_.size());
 
        util::vector<storage_index_type> node_indices(node_indices_.size());
        util::vector<storage_index_type> next_index = begin_indices;
        for (storage_index_type i = 0; i < num_nodes_cached; ++i) {
            for (const storage_index_type j : connected_nodes_to(i)) {
                auto& index = next_index[j];
                NUM_COLLECT_DEBUG_ASSERT(index < begin_indices[j + 1]);
                node_indices[index] = i;
                ++index;
            }
        }
 
        return node_connection_list<storage_index_type>(
            std::move(node_indices), std::move(begin_indices));
    }
 
private:
    node_connection_list(util::vector<storage_index_type> node_indices,
        util::vector<storage_index_type> begin_indices)
        : node_indices_(std::move(node_indices)),
          begin_indices_(std::move(begin_indices)) {}
 
    util::vector<storage_index_type> node_indices_{};
 
    util::vector<storage_index_type> begin_indices_{};
};
 
}  // namespace num_collect::linear::impl::amg