ternary_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 <algorithm>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <limits>
#include <utility>
 
#include <Eigen/Core>
 
#include "num_collect/base/index_type.h"
#include "num_collect/util/assert.h"
 
namespace num_collect::opt::impl {
 
class ternary_vector {
public:
    using digit_type = std::int8_t;
 
    static constexpr index_type max_digits =
        static_cast<index_type>(std::numeric_limits<digit_type>::max());
 
    ternary_vector() = default;
 
    explicit ternary_vector(index_type dim)
        : data_(data_type::Zero(dim, init_digits_per_dimensions + 1)) {}
 
    [[nodiscard]] auto dim() const -> index_type { return data_.rows(); }
 
    void change_dim(index_type dim) {
        data_ = data_type::Zero(dim, init_digits_per_dimensions + 1);
    }
 
    [[nodiscard]] auto digits(index_type dim) const -> index_type {
        NUM_COLLECT_DEBUG_ASSERT(dim < data_.rows());
        return static_cast<index_type>(data_(dim, 0));
    }
 
    [[nodiscard]] auto operator()(index_type dim, index_type digit)
        -> digit_type& {
        NUM_COLLECT_DEBUG_ASSERT(dim < data_.rows());
        NUM_COLLECT_DEBUG_ASSERT(digit < data_(dim, 0));
        return data_(dim, digit + 1);
    }
 
    [[nodiscard]] auto operator()(index_type dim, index_type digit) const
        -> digit_type {
        NUM_COLLECT_DEBUG_ASSERT(dim < data_.rows());
        NUM_COLLECT_DEBUG_ASSERT(digit < data_(dim, 0));
        return data_(dim, digit + 1);
    }
 
    void push_back(index_type dim, digit_type digit) {
        const auto next_digits = digits(dim) + 1;
        if (next_digits >= data_.cols()) {
            NUM_COLLECT_ASSERT(next_digits <= max_digits);
            auto new_data = data_type(data_.rows(), next_digits + 1);
            new_data.leftCols(data_.cols()) = data_;
            data_ = std::move(new_data);
        }
        data_(dim, next_digits) = digit;
        data_(dim, 0) = static_cast<digit_type>(next_digits);
    }
 
    [[nodiscard]] auto operator==(const ternary_vector& right) const -> bool {
        NUM_COLLECT_ASSERT(data_.rows() == right.data_.rows());
        for (index_type i = 0; i < data_.rows(); ++i) {
            // NOLINTNEXTLINE: false positive
            const auto left_digits = static_cast<index_type>(data_(i, 0));
            const auto right_digits =  // NOLINTNEXTLINE: false positive
                static_cast<index_type>(right.data_(i, 0));
            const auto min_digits = std::min(left_digits, right_digits);
            for (index_type j = 0; j < min_digits; ++j) {
                if (data_(i, j + 1) != right.data_(i, j + 1)) {
                    return false;
                }
            }
            for (index_type j = min_digits; j < left_digits; ++j) {
                if (data_(i, j + 1) != static_cast<digit_type>(0)) {
                    return false;
                }
            }
            for (index_type j = min_digits; j < right_digits; ++j) {
                if (right.data_(i, j + 1) != static_cast<digit_type>(0)) {
                    return false;
                }
            }
        }
        return true;
    }
 
    [[nodiscard]] auto operator!=(const ternary_vector& right) const -> bool {
        return !operator==(right);
    }
 
    template <typename Scalar>
    [[nodiscard]] auto elem_as(index_type dim) const -> Scalar {
        NUM_COLLECT_DEBUG_ASSERT(dim < data_.rows());
        const auto ndigits = digits(dim);
        auto num = static_cast<Scalar>(0);
        auto coeff = static_cast<Scalar>(1);
        static const Scalar inv_base =
            static_cast<Scalar>(1) / static_cast<Scalar>(3);
        for (index_type i = 0; i < ndigits; ++i) {
            num += coeff * static_cast<Scalar>(data_(dim, i + 1));
            coeff *= inv_base;
        }
        return num;
    }
 
private:
    using data_type = Eigen::Matrix<digit_type, Eigen::Dynamic, Eigen::Dynamic,
        Eigen::RowMajor>;
 
    static constexpr index_type init_digits_per_dimensions = 4;
 
    data_type data_{};
};
 
}  // namespace num_collect::opt::impl
 
namespace std {
 
template <>
class hash<num_collect::opt::impl::ternary_vector> {
public:
    using argument_type = num_collect::opt::impl::ternary_vector;
 
    using result_type = std::size_t;
 
    [[nodiscard]] auto operator()(const argument_type& vec) const
        -> result_type {
        std::size_t res = 0;
        for (num_collect::index_type i = 0; i < vec.dim(); ++i) {
            std::size_t temp = 0;
            num_collect::index_type non_zero_digits = 0;
            for (num_collect::index_type j = 0; j < vec.digits(i); ++j) {
                if (vec(i, j) != 0) {
                    non_zero_digits = j + 1;
                }
            }
            for (num_collect::index_type j = 0; j < non_zero_digits; ++j) {
                constexpr std::size_t coeff = 3;
                temp *= coeff;
                temp += static_cast<std::size_t>(
                    static_cast<std::uint8_t>(vec(i, j)));
            }
            constexpr std::size_t coeff = 79865413;  // a prime number
            res *= coeff;
            res += temp;
        }
        return res;
    }
};
 
}  // namespace std