TODO.txt

Ideas that didn't work
======================
#39  Store nodes flat in Entries.
     Some improvement (5-10%), but it doesn work for flat_array_map, because that
     is already a "flat" std::array and would cause the whole tree to materialize during compilation time.
     Lesson: Try to mak flat_sparse_map "flat" -> see #86
#88  Using PQ for upper part of WQ. This had absolutely no effect (testing with query_mm_d_benchmark with 100K-10M).
     Counting showed that PQ would go 3-5 nodes deep (100K:3, 10M: 5) but that had no effect.
     Lesson: Look at WQ initialization, it may be too expensive. Why is WQ traversal so slow???
Non-flat keys: Use e.g. vector as keys
     Tested in: https://github.com/tzaeschke/phtree-cpp/tree/yolo/vector-keys
     The implementation actually uses a pointer-to-array instead of a vector (this allows constexpr SIZE for
     loop unrolling etc).
     Results:
     - There is no problem for PhPointLD using an inherited std::array -> No effect on performance
     - Using a delegated array (with unique_ptr) has an effect,
     - For insert, it starts paying of for 30D, being up to 20% faster for 60D
     - For query and kNN, it never pays off.
     -> See RESULTS.txt


Fix const-ness
==============
- operator[] should have a const overload
- find() should have a non-const overload
- test:

TEST(PhTreeTest, SmokeTestConstTree) {
    // Test edge case: only one entry in tree
    PhPoint<3> p{1, 2, 3};
    TestTree<3, Id> tree1;
    tree1.emplace(p, Id{1});
    tree1.emplace(p, Id{2});
    Id id3{3};
    tree1.insert(p, id3);
    Id id4{4};
    tree1.insert(p, id4);
    const auto& tree = tree1;
    ASSERT_EQ(tree.size(), 1);
    ASSERT_EQ(tree.find(p).second()._i, 1);
    ASSERT_EQ(tree[p]._i, 1);

    auto q_window = tree.begin_query({p, p});
    ASSERT_EQ(1, q_window->_i);
    ++q_window;
    ASSERT_EQ(q_window, tree.end());

    auto q_extent = tree.begin();
    ASSERT_EQ(1, q_extent->_i);
    ++q_extent;
    ASSERT_EQ(q_extent, tree.end());

    auto q_knn = tree.begin_knn_query(10, p, DistanceEuclidean<3>());
    ASSERT_EQ(1, q_knn->_i);
    ++q_knn;
    ASSERT_EQ(q_knn, tree.end());

    ASSERT_EQ(1, tree1.erase(p));
    ASSERT_EQ(0, tree.size());
    ASSERT_EQ(0, tree1.erase(p));
    ASSERT_EQ(0, tree.size());
    ASSERT_TRUE(tree.empty());
}


b_plus_tree_map - binary search
===============
Use custom binary search:

    // return BptEntry* ?!?!?
    template <typename E>
    [[nodiscard]] auto lower_bound(key_t key, std::vector<E>& data) noexcept {
        return std::lower_bound(data.begin(), data.end(), key, [](E& left, const key_t key) {
            return left.first < key;
        });
        //        auto pos = __lower_bound(&*data_leaf_.begin(), &*data_leaf_.end(), key);
        //        return data_leaf_.begin() + pos;
    }

    template <typename TT>
    inline auto __lower_bound(const TT* __first, const TT* __last, key_t __val) const noexcept {
        const TT* const_first = __first;
        auto __len = __last - __first;

        while (__len > 0) {
            auto __half = __len >> 1;
            const TT* __middle = __first + __half;
            if (__middle->first < __val) {
                __first = __middle;
                ++__first;
                __len = __len - __half - 1;
            } else
                __len = __half;
        }
        return __first - const_first;
    }