packed_rtree.hpp

Go to the documentation of this file.

#pragma once
 
#include <fcb/error.hpp>
#include <fcb/range_reader.hpp>
#include <fcb/span.hpp>
 
#include <cstdint>
#include <vector>
 
namespace fcb {
 
struct SearchResultItem;
 
struct BBox {
    double min_x;
    double min_y;
    double max_x;
    double max_y;
};
 
struct NodeItem {
    double min_x;
    double min_y;
    double max_x;
    double max_y;
    std::uint64_t offset;
 
    static constexpr std::size_t kSize = 40;
 
    static NodeItem decode(bytes_view b);
 
    static NodeItem empty(std::uint64_t offset);
 
    void expand(const NodeItem& r);
 
    void encode(std::uint8_t* out) const;
 
    bool intersects(const BBox& q) const;
};
 
std::uint64_t rtree_num_nodes(std::uint64_t num_items, std::uint16_t node_size);
 
struct LevelBound {
    std::uint64_t start;
    std::uint64_t end;
};
 
std::vector<LevelBound> rtree_level_bounds(std::uint64_t num_items, std::uint16_t node_size);
 
std::vector<SearchResultItem> rtree_search_bbox(RangeReader& reader, std::uint64_t index_begin,
                                                std::uint64_t num_items, std::uint16_t node_size,
                                                const BBox& query);
 
}  // namespace fcb