bidirectional_vector.h

Go to the documentation of this file.

/*
 * Copyright 2021 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 <cstddef>
#include <deque>
#include <limits>
 
#include <fmt/format.h>  // IWYU pragma: keep
 
#include "num_collect/base/exception.h"
#include "num_collect/base/index_type.h"
#include "num_collect/logging/logging_macros.h"
#include "num_collect/util/assert.h"
 
namespace num_collect::util {
 
template <typename Value, typename Container = std::deque<Value>>
class bidirectional_vector {
public:
    using value_type = Value;
 
    using container_type = Container;
 
    bidirectional_vector() = default;
 
    bidirectional_vector(container_type container, index_type origin_index)
        : container_(std::move(container)), origin_index_(origin_index) {}
 
    [[nodiscard]] auto container() const noexcept -> const container_type& {
        return container_;
    }
 
    [[nodiscard]] auto empty() const noexcept -> bool {
        return container_.empty();
    }
 
    [[nodiscard]] auto min_index() const noexcept -> index_type {
        return origin_index_;
    }
 
    [[nodiscard]] auto max_index() const noexcept -> index_type {
        return origin_index_ + static_cast<index_type>(container_.size()) - 1;
    }
 
    [[nodiscard]] auto at(index_type index) const -> const value_type& {
        return container_[container_index(index)];
    }
 
    [[nodiscard]] auto at(index_type index) -> value_type& {
        return container_[container_index(index)];
    }
 
    [[nodiscard]] auto operator[](index_type index) const -> const value_type& {
        return container_[unsafe_container_index(index)];
    }
 
    [[nodiscard]] auto operator[](index_type index) -> value_type& {
        return container_[unsafe_container_index(index)];
    }
 
    [[nodiscard]] auto get_or_prepare(index_type index) -> value_type& {
        prepare_for(index);
        return container_[unsafe_container_index(index)];
    }
 
    void resize(index_type min_index, index_type max_index,
        const value_type& value = value_type()) {
        const index_type current_min_index = this->min_index();
        const index_type current_max_index = this->max_index();
 
        if (max_index < current_min_index || current_max_index < min_index) {
            origin_index_ = min_index;
            const auto next_size =
                static_cast<std::size_t>(max_index - min_index + 1);
            container_.resize(next_size);
            for (auto& elem : container_) {
                elem = value;
            }
            return;
        }
 
        if (min_index < current_min_index) {
            const auto num_added =
                static_cast<std::size_t>(current_min_index - min_index);
            container_.insert(container_.begin(), num_added, value);
        } else if (min_index > current_min_index) {
            const index_type num_erased = min_index - current_min_index;
            container_.erase(
                container_.begin(), container_.begin() + num_erased);
        }
        origin_index_ = min_index;
 
        if (max_index > current_max_index) {
            const auto num_added =
                static_cast<std::size_t>(max_index - current_max_index);
            container_.insert(container_.end(), num_added, value);
        } else if (max_index < current_max_index) {
            const index_type num_erased = current_max_index - max_index;
            container_.erase(container_.end() - num_erased, container_.end());
        }
    }
 
    void push_front(const value_type& value) {
        NUM_COLLECT_ASSERT(
            origin_index_ > std::numeric_limits<index_type>::min());
        container_.push_front(value);
        --origin_index_;
    }
 
    void push_back(const value_type& value) { container_.push_back(value); }
 
    void move_position(index_type offset) {
        NUM_COLLECT_ASSERT(is_safe_offset(offset));
        origin_index_ += offset;
    }
 
private:
    container_type container_{};
 
    index_type origin_index_{0};
 
    [[nodiscard]] auto container_index(index_type index) const -> std::size_t {
        if (index < origin_index_) {
            throw_out_of_range(index);
        }
        const auto result = static_cast<std::size_t>(index - origin_index_);
        if (result >= container_.size()) {
            throw_out_of_range(index);
        }
        return result;
    }
 
    [[nodiscard]] auto unsafe_container_index(index_type index) const noexcept
        -> std::size_t {
        return static_cast<std::size_t>(index - origin_index_);
    }
 
    [[noreturn]] void throw_out_of_range(index_type index) const {
        NUM_COLLECT_LOG_AND_THROW(invalid_argument,
            fmt::format("Index out of range (index: {}, range: [{}, {}])",
                index, min_index(), max_index()));
    }
 
    void prepare_for(index_type index) {
        if (container_.empty()) {
            origin_index_ = index;
            container_.push_back(value_type());
            return;
        }
 
        index_type next_min = min_index();
        index_type next_max = max_index();
        bool should_resize = false;
        if (next_min > index) {
            next_min = index;
            should_resize = true;
        }
        if (next_max < index) {
            next_max = index;
            should_resize = true;
        }
        if (should_resize) {
            resize(next_min, next_max);
        }
    }
 
    [[nodiscard]] auto is_safe_offset(index_type offset) const noexcept
        -> bool {
        if (offset < 0) {
            return origin_index_ >=
                std::numeric_limits<index_type>::min() - offset;
        }
        return max_index() <= std::numeric_limits<index_type>::max() - offset;
    }
};
 
}  // namespace num_collect::util