Skip to content

Latest commit

 

History

History
196 lines (168 loc) · 10.4 KB

CHANGELOG.md

File metadata and controls

196 lines (168 loc) · 10.4 KB

Changelog

All notable changes to this project will be documented in this file.

The format is based on Keep a Changelog and this project adheres to Semantic Versioning.

Unreleased

Added

  • Added B+tree multimap for internal (future) use. #93

Changed

  • Rewrote relocate(). This should be much cleaner now and slightly faster. #98, #99, #101
  • 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

1.4.0 - 2022-09-09

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

Removed

  • Nothing.

Fixed

  • Nothing.

1.3.0 - 2022-08-28

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

1.2.0 - 2022-04-14

Changed

  • 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

1.1.1 - 2022-01-30

Changed

  • Replaced size() in filters with DIM #26

1.1.0 - 2022-01-25

Added

  • FilterSphere for filtering by sphere constraint (by ctbur) #16
  • IEEE converter for 32bit float, see distance.h (by ctbur) #18

Changed

  • Performance improvement for updates and queries: removed use of std::variant. #23
  • Fixed imports <climits> -> <limits> (by ctbur) #15
  • Cleaned up build scripts #21
  • Fixed warnings: #20
    • "unused function argument" warnings
    • gcc/clang warnings
    • MSVC warnings
    • reserved identifier warnings (identifiers starting with _)
  • typos in README.md #22

1.0.1 - 2021-05-06

Changed

  • replaced compilation flag -fpermissive with -Werror, and fixed all warnings/errors, see issue #10

1.0.0 - 2021-03-23

Added

  • API: MultiMap: A wrapper that makes PH-Tree behave as a multi-map.
  • API: erase(iterator)
  • API: emplace_hint(iterator, ...)
  • API for PhTreeF and PhTreeBoxF: 32bit floating point options
  • Support for custom key classes

Changed

  • BREAKING CHANGE: The query functions now require a query box as input (instead of a min/max point pair)
  • BREAKING CHANGE: phtree_box_d.h has been removed, please use `phtree.h instead.
  • BREAKING CHANGE: phtree_d.h has been removed, please use phtree.h instead.
  • BREAKING CHANGE: Data converters (IEEE, Multiply, etc) are now structs i.o. functions/functors
  • BREAKING CHANGE: PhFilterNoOp has been renamed to FilterNoOp
  • BREAKING CHANGE: kNN queries now always require the distance function to be specified.
  • BREAKING CHANGE: Preprocessors have been refactored and renamed to Converter/ScalarConverter
  • Moved CI builds from Travis to GitHub actions

Removed

  • Nothing.

Fixed

  • GCC warnings from -Wsign-compare and -Wsequence-point.

0.1.0 - 2020-07-02

Added

  • Initial version.

Changed

  • Nothing.

Removed

  • Nothing.

Fixed

  • Nothing.