Maintenance release

What's Changed

• fix(iterator): ensure HasNext does not advance state by @plar in #47. See Issue #46 reported by @MadsRC
• docs: add migration section by @plar in #48

Full Changelog: v2.0.2...v2.0.3

v1 Maintenance Release

v1 Maintenance Release – backported fixes from v2

📢 Deprecation Notice

• v1 is now deprecated.
• All active development continues in v2.x.x.

In order to migrate, see the Migration from v1 to v2 section.

Doc maintenance release

What's Changed

• Update README.md by @plar in #43
• Fix docs by @plar in #44
• Update ref to pkg.go.dev by @plar in #45

Full Changelog: v2.0.1...v2.0.2

Maintenance release

What's Changed

• Create codeql.yml by @plar in #36
• Fix debug messages by @plar in #37
• docs: clarify lexicographical ordering in key sorting behavior by @plar in #39
• fix: module path should reflect v2 release by @MadsRC in #40
• docs(readme): fix syntax errors in code sample by @job79 in #42

Full Changelog: v2.0.0...v2.0.1

Reverse Iteration with Backward-Incompatible Changes

New Feature

• Reverse Iteration Support #33: Added reverse iteration capabilities for both whole-tree and prefix-based traversals, enabling descending order iterations.

API Breaking Changes in Tree interface

This will only affect you if you have implemented your own Tree interface.

Modified Tree.ForEachPrefix method signature:

// v1
ForEachPrefix(keyPrefix Key, callback Callback)
// v2
ForEachPrefix(keyPrefix Key, callback Callback, options ...int)

The ForEachPrefix method's signature has been modified to include optional traversal options, such as TraverseReverse.
According to Semantic Versioning rules, we must increase the major version number when the public API changes, even if it doesn't affect everyone.

Enhancements

• Usage improvements: updated example usage to showcase new reverse iteration functionality.
• Refactored traversal logic: simplified traversal handling by creating a more generic traversal function infrastructure and eliminated unnecessary functions.
• Improved function and type docs.

Bug Fixes

• Child index handling correction: fixed an error in clearing the presence map for node4 children during node deletions.

Testing

• Expanded test suite: moved substantial test cases into dedicated test files to improve organization and clarity.
• Bidirectional traversal tests: introduced tests to ensure correctness of both ascending and descending order tree traversals.
• Prefix traversal tests: added tests verifying both prefix-specific and arbitrary node traversals with early termination conditions.

Other changes

• Update dependabot.yml by @plar in #34

Full Changelog: v1.0.6...v2.0.0

Bugfix and Refactoring

Bugfix

• Fix miscounting childrenNum in node16's shrink #28. Kudos to @udzura!

Build and Continuous Integration

• Replaced the Makefile with a bash make script. The previous targets were all PHONY, and the Makefile syntax wasn't ideal for this project.
• Added GitHub Actions for continuous integration and automation.

Go Environment and Tools

• Integrated Go ecosystem tools for quality assurance, including mod, fmt, vet, lint, staticcheck, vulncheck, and gogec.
• Updated go.mod to Go version 1.18.
• Updated Go dependencies.

Code Refactoring

• Simplified node structures and merged the zeroChild field into the children field.
• Simplified code by eliminating bit operations for certain nodes.
• Merged similar functionality between the ForEach method and the Iterator.
• Split node.go and tree.go into separate files for improved modularity.
• Refactored and simplified tree iteration and traversal functionality.
• Refactored and simplified the String method for the tree.

Testing and Quality Assurance

• Introduced golden files for tests.
• Added t.Parallel for running tests in parallel.
• Refactored some tests for better coverage and readability.

Code Quality

• Fixed numerous Go lint warnings.
• Added comments to internal code for clarity.
• Renamed variables and method names to improve readability. (After all, cache invalidation and naming things are the two hard things in computer science. :)

This refactoring effort enhances code structure and quality without altering the external interface/public API.

Bugfix: support nil keys

Fix #26: insert multiple nil keys should not panic

Memory and performance optimization release

• Optimize node16/48 space usage
• Optimize node16 performance using bits package instead of sort
• Minor changes and code refactoring

Fix infra code

• Update travis to support go v1.13, v1.14 and v1.15
• Fix go v1.15 vet errors
• Restore test coverage to 100%

Bugfix: tree traversal with conditional callback

Fix #14: The tree traversal did not stop in some cases, even when the callback returned false.