v5.0.0

Breaking Updates

1. Remove MAX_ARGUMENTS_LENGTH as it is not always a constant. More details here.
2. Move utils in src/collection/ to src/utils/
3. Move MAX_ARRAY_LENGTH from ArrayUtils to env namespace

Updates

1. Add env namespace
2. Replace MAX_ARGUMENTS_LENGTH with env.getMaxArgumentsLength()

v4.1.3

Updates

1. Add u32.lzb().
2. Add u32.lzp().

Enhancements

1. Refactor u32.bitsSet().
2. Refactor u32.msp().
3. InOrderSegmentTree
   • Improve memory usage from 2n to 2n - 1 (where n is # of elements).
   • Remove unneeded code from update logic.

v4.1.2

Fixes

1. LevelOrderSegmentTree
   Instantiating a new tree with 1 element caused an error trying to set the internal array to length -1. Fixed and added tests.

v4.1.1

Fixes:

1. Fix size reduction in LevelOrderSegmentTree
   Removing an element in pop() was not triggering a size reduction as intended. Once resized, the pointers were also not being updated correctly in shrink().

v4.1.0

Features:

1. Add StringUtils namespace

Fixes:

1. Fix size reduction method for LevelOrderSegmentTree
   When the tree's size was a power of 2, the updated tree would have a
   complete bottom level, instead of being half-full as intended. The
   update fixes this and adds a check to see if sizing down is even
   possible.

v4.0.0

Breaking Updates

1. Remove math namespace
2. Remove u32.mlsp()

Features:

1. Add ArrayUtils namespace
2. Add IteratorUtils namespace
3. Add NumberUtils namespace
4. Add u32 namespace

Enhancements:

1. Improve performance of ArrayList's addAll() and splice() methods by adopting the new ArrayUtils.splice() method

v3.0.0

Breaking Updates

1. Change Tree.contains() to Tree.has()
2. Change Tree.add() to return the tree

Features:

1. Add Collection interface
2. Refactor all data structures to implement Collection interface
3. Add SegmentTree interface
4. Add InOrderSegmentTree implementation
5. Add LevelOrderSegmentTree implementation
6. Add math/num for manipulating numbers
7. Add math/u32 for manipulating unsigned 32-bit numbers

Enhancements

1. Add removeStack() to tree/binaryTreeUtils
   When removing a non-leaf node in a binary tree, it is common to first swap the node with its predecessor or successor (if any), so that it can be removed as a leaf node. As this works across a variety of binary tree implementations, it has been packaged into a function.

v2.1.0

Features:

1. Add AVLTree implementation
   This implementation uses and stores balance factors (height differences) instead of absolute heights in each node, simplifying the approach and reducing per-node extra memory to 2 bits.

Enhancement

1. Improve performance of AATree

v2.0.0

Breaking Updates

1. Remove dump() from the Heap
   The original idea was for the default iterator on Sorted objects
   to iterate the object in sorted order. When order did not matter, dump()
   could be used.

   In practice, there exists objects that are considered sorted in usage but
   not in implementation. Heaps are an example of this; to return elements in
   sorted order, extra work is required. If this is the behavior of the
   default iterator, then this work is done implicitly. This can become a penalty
   as an object is passed to contexts where this behavior is not known.

   This update removes this constraint on the default iterator. It no longer must return a
   elements in sorted order (though it is of course free to do so). Objects should instead
   provide a separate method for in-order traversal of their elements (such as Heap.sorted()).

Features:

1. Add Tree interface
2. Add SortedTree interface
3. Add AATree implementation

Enhancement

1. Improve performance of skewMerge() used by SkewHeap
   skewMerge() merges K leftist heaps into 1. The process involves potentially splitting each
   heap into multiple heaps, then combining all of them. The total number of heaps after splitting is N.

   The previous implementation did this in Nlog(N) time complexity. The new implementation uses a heapSort
   approach to do this in Nlog(K) time complexity (see mergeKSorted() in src/heap/utils).

v1.4.0

Features

Sortable

1. Add Sortable interface

Heap

1. Add Heap interface
2. Add BinaryHeap implementation
3. Add SkewHeap implementation

List

1. Update the List interface to extend Sortable
2. Implement sort()