index.hpp

 
#ifndef UFO_CONTAINER_TREE_INDEX_HPP
#define UFO_CONTAINER_TREE_INDEX_HPP
 
// STL
#include <algorithm>
#include <cstdint>
#include <functional>
#include <limits>
#include <ostream>
 
namespace ufo
{
struct TreeIndex {
    // 64 bits instead, either
    //  32 bits X high levels
    //  32 bits Y low levels
    // or
    //  32-Dim bits X high levels
    //  32 bits Y low levels
    //  Dim bits for offset
 
    using pos_type    = std::uint32_t;
    using offset_type = std::uint32_t;
 
    static constexpr pos_type const TYPE_BIT =
        pos_type(1) << (std::numeric_limits<pos_type>::digits - 1);
    static constexpr pos_type const NULL_POS       = std::numeric_limits<pos_type>::max();
    static constexpr pos_type const PROCESSING_POS = NULL_POS - 1;
    static constexpr pos_type const INVALID_POS    = NULL_POS - 2;
    static constexpr pos_type const MAX_VALID_POS  = INVALID_POS - 1;
 
    pos_type    pos{NULL_POS};
    offset_type offset{0};
 
    constexpr TreeIndex() noexcept = default;
 
    constexpr TreeIndex(pos_type pos, offset_type offset) noexcept
        : pos(pos), offset(offset)
    {
    }
 
    friend void swap(TreeIndex& lhs, TreeIndex& rhs) noexcept
    {
        std::swap(lhs.pos, rhs.pos);
        std::swap(lhs.offset, rhs.offset);
    }
 
    constexpr bool operator==(TreeIndex rhs) const
    {
        return pos == rhs.pos && offset == rhs.offset;
    }
 
    constexpr bool operator!=(TreeIndex rhs) const { return !(operator==(rhs)); }
 
    [[nodiscard]] constexpr TreeIndex sibling(offset_type offset) const
    {
        return {pos, offset};
    }
 
    [[nodiscard]] constexpr bool valid() const { return MAX_VALID_POS >= pos; }
};
 
inline std::ostream& operator<<(std::ostream& out, TreeIndex index)
{
    return out << "pos: " << +index.pos << " offset: " << +index.offset;
}
}  // namespace ufo
 
namespace std
{
template <>
struct hash<ufo::TreeIndex> {
    std::size_t operator()(ufo::TreeIndex index) const
    {
        return (static_cast<std::uint64_t>(index.pos) << 3) | index.offset;
    }
};
}  // namespace std
 
#endif  // UFO_CONTAINER_TREE_INDEX_HPP