v1.6.1

Highlights

• Fix compilation issue with Windows SDK

What's Changed

Changed

• Renamed CALLBACK to CALLBACK_FN to avoid conflicts with Windows SDK. #142
• Dead code cleanup. #144

Removed

• Removed copy constructor/assignment from bplus-maps. Added some fringe case tests. #145

Full Changelog: v1.6.0...v1.6.1 or CHANGELOG

v1.6.0

Highlights

• performance improvement for nearest neighbor queries (kNN).
• New lower_bound(key) API method to find a key or the next higher (using Morton order) key.
• New DistanceChebyshev for using Chebyshev distance with kNN
• API change: relocate() now returns size_t
• Several refactorings and minor changes

What's Changed

Added

• Added benchmark for bit operations in common. #128
• Added lower_bounds(key) to API. #126
• Added bpt_fixed_vector, a fixed size flat vector for future use. It can be dropped in for an std::vector. #124
• Added Chebyshev distance metric DistanceChebyshev. #129

Changed

• Changed bpt_vector to use std::destroy i.o. default dstr. #132
• Moved B+trees into own namespace. #131
• Moved some stuff in common into namespace detail. #129
• Improved kNN search implementation. This also deprecates the post-increment iterator. #118

Fixed

• Replaced deprecated <assert.h> imports with <cassert>. #134
• Fixes undefined behavior in debug method. #135
• API: Fixes relocate() return type to be size_t. #136
• Fix constness of B+tree check(). #137
• Minor fixes for next release. #140

Full Changelog: v1.5.0...v1.6.0 or CHANGELOG

v1.5.0

Overview

This release contains several performance improvement. relocate() was completely rewritten. The build now works with all newer bazel versions up to latest (6.0.0)

What's Changed

Added

• Added B+tree multimap for internal (future) use. #93
• Added some fuzz tests. Not that these require manual compilation, see fuzzer/README.md. #114
• Added float-32 variants to multimap: PhTreeMultiMapF, PhTreeMultiMapBoxF. #117

Changed

• Clean up array_map. #107,
• Fixed compatibility with bazel 6.0.0. #109,
• Added missing compiler flag for TZCNT/CTZ (count trailing zeros). This should be much faster on haswell or later CPUs. #103,
• Rewrote relocate(). This should be much cleaner now and slightly faster. #98, #99, #101, #104, #115
• Cleaned up HandleCollision() and key comparison functions. #97
• Improved performance by eliminating memory indirection for DIM > 3. This was enabled by referencing "Node" directly in "Entry" which was enabled by implanting an indirection in array_map. #96
• Improved performance of window queries by executing them partially as point queries. This works best for point datasets, and somewhat for box datasets with "include" queries. There is no benefit for "intersection" queries. #88
• Improved benchmarks for insert and query to use a more compact format. #91
• Improved performance of window queries by optimizing calculation of min/max masks.
  Improved performance of queries and updates by changing bit-width of min/max masks and hc_pos_t. #95

Removed

• bazel version requirement file .bazelversion. #89

Fixed

• Fixed copy cstr/assignment of B+trees, see also #102. These were not used at all. #119
• Fixed numerous warnings when compiling with MSVC. #120

Full Changelog: v1.4.0...v1.5.0 or CHANGELOG

v1.4.0

What's new

This release is a pure project structure release, no PH-tree features were added or fixed.
This is a breaking release:

• if you are using bazel, bazel dependency has now to be declared with

   deps = [
       "@phtree//:phtree",
   ],
  

• if you included the following files directly: converter.h, distance.h or filter.h. These have been moved from the common directory to the parent directory because they are part of the API.

This release focuses on project structure and build systems:

• Structure: The library has been moved into a subdirectory called include. Tests and benchmarks have been moved to separate folders.
• Bazel: Cleaned up bazel import (now requires deps = ["@phtree//:phtree"])
• Cmake: Added support for FetchContent, find_package() (after cmake install) and inclusion via add_subfolder()
• Doc: Added section to README.md on how to include the phtree when using bazel or cmake
• Code quality: Added code coverage and linting, and additional projects to verify build ability.
• A ton of script cleanup, build success badges

Personal note: I am aware that these are breaking changes in a minor release. I hope this is acceptable because the code should be easy to adapt (no API changes) and pretty much optional anyway (there are no functional changes to the PH-tree itself). Having only project and build system changes didn't seem to justify a major release. I'll try to adhere to semantic versioning from now on.

Changelog

Added

• Added build features: #53
  • linting for C++ and bazel files.
  • Added CI status badges.
  • Added test coverage
• Added support for cmake FetchContent. See README for details. #75
• Added support for cmake find_packet() and direct import via add_sub_directory(). See README for details. #83

Changed

• Cleaned up build scripts. #53
• Fixed code coverage + migrate to linux. #80
• BREAKING CHANGE The project has been restructured to have a more "standard" directory structure. This affects how bazel dependencies work (use deps = ["@phtree//:phtree",]) and enables cmake FetchContent_. See README for details. #75

See CHANGELOG

v1.3.0

This release contains a few bug fixes and numerous improvements mostly related to performance. Notably:

• New relocate() and relocate_if() functions for faster "moving" of entries from one coordinate to another
• New try_emplace() functions analogous to try_emplace() in std::map etc.
• Proper support for cmake with Visual Studio 2019 (except benchmarks).

See CHANGELOG

What's Changed

Added

• Added flag to relocate() allow short cutting in case of identical keys. #68
• Added tested support for move-only and copy-only value objects. #56
• Added custom bucket implementation (similar to std::unordered_set). This improves update performance by 5%-20%. #44
• Added PhTree.relocate(old_key, new_key) and PhTree.relocate_if(old_key, new_key, predicate). This is a lot faster than using other methods. #43
• Added try_emplace(key, value) and try_emplace(iter_hint, key, value) #40
• Added FilterBoxAABB and FilterSphereAABB as examples for filtering a PH-Tree with box keys #33

Changed

• Moved tests and benchmarks into separate folders. #67
• Cleaned up unit tests. #54
• Simplified internals of erase(). #47
• Removed internal use of std::optional() to slightly reduce memory overhead #38
• Removed restrictions on bazel version #35
• API BREAKING CHANGE: API of filters have been changed to be more correct, explicit and flexible. #21
  • Correctness: Converters and distance functions are not copied unnecessarily anymore.
  • Explicit: Filters must have a mandatory parameter for a converter reference. This ensures that the correct converter is used, probably tree.converter().
  • Flexible: Distance functions can be provided through a universal reference (forwarding reference). Also, filters are now movable and copyable.
• API BREAKING CHANGE: Allow filtering on buckets in multimaps. Multimap filters have different functions
  and function signatures than normal PhTree filters. #26

Fixed

• Fixed compiler warnings when compiling with Visual Studio 2019. #74
• Fixed cmake to work with Visual Studio 2019. Added tests and benchmarks to cmake. (benchmarks still do not work with VS at the moment). #62
• Fixed compilation problems and a memory leak when compiling with Visual Studio 2019. (also added msan support). #64

Full Changelog: v1.2.0...v1.3.0

v1.2.0

This release contains numerous improvements mostly related to performance:

• Bugfix: FilterSphere was not working correctly. #27
• Potentially BREAKING CHANGE: Refactored API of all methods that accept callbacks and filters to
  accept universal/forwarding references.
  Also changed filters and callback to not require const methods. #22
• Clean up iterator implementations. #19
• Make PhTree and PhTreeMultimap movable (move-assign/copy). #18
• Potentially BREAKING CHANGE when using IsNodeValid() in provided filters:
  Changed bit_width_t from uin16_t to uint32_t. This improves performance of 3D insert/emplace
  on small datasets by up to 15%. To avoid warnings that meant that the API of FilterAABB and FilterSphere
  had to be changed to accept uint32_t instead of int. This may break some implementations. #17
• DIM>8 now uses custom b_plus_tree_map instead of std::map. This improves performance for all operations, e.g.
  window queries on large datasets are up to 4x faster. Benchmarks results can be found in the issue. #14
• postfix/infix field moved from Node to Entry. This avoids indirections and improves performance of most by ~10%.
  operations by 5-15%. #11
• Entries now use 'union' to store children. #9
• Avoid unnecessary find() when removing a node. #5
• Avoid unnecessary key copy when inserting a node. #4
• for_each(callback, filter) was traversing too many nodes. #2
• Build improvements for bazel/cmake