BTree v4.0.0 Release Notes

Release Date: 2016-11-07 // about 6 years ago
  • ๐Ÿš€ This is a major release incorporating API-breaking changes. It also includes fixes for several high-severity bugs uncovered while working on new features, so this is a highly recommended upgrade.

    ๐Ÿ’ฅ Breaking changes

    • โšก๏ธ To support multiset operations, some of BTree's methods have grown a new required parameter specifying the key matching strategy. To get the original behavior, specify .groupingMatches as the matching strategy, except for union, as noted below. The compiler will provide fixits, but you'll still need to update the code by hand. This affects the following methods:

      • BTree.isSubset(of:)
      • BTree.isStrictSubset(of:)
      • BTree.isSuperset(of:)
      • BTree.isStrictSuperset(of:)
      • BTree.union(:) -- use the .countingMatches strategy to get the original, multiset-appropriate, behavior.
      • BTree.distinctUnion(:) -- removed; use union with the .groupingMatches strategy instead.
      • BTree.subtracting(:) (both overloads)
      • BTree.intersection(:) (both overloads)
      • BTree.symmetricDifference(:)

    ๐Ÿ†• New Features

    • SortedBag is a new generic collection implementing an ordered multiset.
    • BTreeMatchingStrategy is a new public enum for selecting one of two matching strategies when comparing elements from two trees with duplicate keys.
    • BTree.index(forInserting:at:) is a new method that returns the index at which a new element with the given key would be inserted into the tree.
    • SortedSet.indexOfFirstElement(after:) is a new method that finds the lowest index whose key is greater than the specified key.
    • SortedSet.indexOfFirstElement(notBefore:) is a new method that finds the lowest index whose key is greater than or equal to the specified key.
    • โœ… SortedSet.indexOfLastElement(before:) is a new method that finds the greatest index whose key is less than the specified key.
    • โœ… SortedSet.indexOfLastElement(notAfter:) is a new method that finds the greatest index whose key is less than or equal to the specified key.

    ๐Ÿ› Bug Fixes

    • Issue #19: BTree concatenation, set operations sometimes corrupt their input trees
    • ๐Ÿ”€ Issue #20: Corrupt BTree merge results when duplicate keys leak across common subtree boundaries
    • Issue #21: BTree comparisons (subset/superset) may assert on certain shared subtrees
    • โšก๏ธ SortedSet.update(with:) now has a discardable result.