Skip to content

v2.0.0
Compare
Choose a tag to compare
@lorentey lorentey released this 06 Mar 19:04
· 144 commits to master since this release
v2.0.0
fee6873

This is a major release that includes breaking API changes, plus major new features and bug fixes.

The package now implements all major features that were on my initial roadmap; further development will likely concentrate on refining the API, improving performance and adapting the package to new Swift versions. (Although it is never too late to propose new features!)

This release supports Swift 2.1.1.

Swift 2.2 is conditionally supported; add -DSwift22 to the Swift compiler flags to enable it. Note that this version of the module will compile with a number of warnings on 2.2; these will be fixed when Swift 2.2 is released.

Swift 3 is not yet supported. In particular, API names mostly follow Swift 2 conventions, although certain internal APIs are following the new design conventions.

New Features

General

  • The README has been rewritten and greatly expanded in scope. It now includes a short intro and a detailed rationale section.
  • The term "position" has been systematically replaced with "offset" throughout the entire API and documentation.

BTree

  • The second component of BTree's elements has been renamed from "payload" to "value" throughout the entire API and documentation. This is for consistency with other Swift key-value collections.
  • BTree now includes efficient set operations: union, distinctUnion, subtract, exclusiveOr, and intersect. These are based on keys, and exploit the order of elements to detect when they can skip elementwise processing for specific subtrees. subtract and intersect also have overloads for selecting for keys contained in a sorted sequence.
  • BTree now supports efficient tree comparison operations: elementsEqual, isDisjointWith, isSubsetOf, isStrictSubsetOf, isSupersetOf, and isStrictSupersetOf. All of these except the first work like set comparisons on the keys of the tree. They exploit the element order and detect shared nodes to skip over subtrees whenever possible. When Value is Equatable, you can now compare B-trees for equality using the == operator.
  • BTreeKeySelector now includes an After case, which selects first the element that has a key that is larger than the specified key. This is occasionally useful.
  • BTree now defines explicit overrides for the following methods on SequenceType: prefix, suffix, prefixUpTo, prefixThrough, suffixFrom, dropLast, dropFirst, first, last, popFirst, popLast, removeFirst and removeLast.
    The new implementations perform better than the default, index-based implementations provided by CollectionType. There are also new overloads for key-based slicing.
  • BTree gained methods for starting a generator at any specific key, index or offset.
  • The withCursor family of methods now allow their closure to return a value.
  • BTree.remove(:) now returns the full element that was removed, not just the value component.
  • Bulk loading initializers of BTree now respect the original order of elements, and optionally allow filtering out elements with duplicate keys. When initializing a Map from a sequence that contains duplicates, only the last element is kept for any key.
  • New methods: BTree.removeAtIndex(:), and BTree.removeAll()
  • BTreeIndex now contains efficient O(log(n)) implementations for advancedBy and distanceTo, replacing their default O(n) variants.
  • BTreeIndex is now Comparable. However, comparing indices only makes sense if the indices belong to the same tree.
  • BTreeCursor now has an element property that allows you to get or update the entire (key, value) pair at the current position.

OrderedSet

  • OrderedSet is a new general-use wrapper around BTree, implementing a sorted analogue of Set.

List

  • The generator type of List has been renamed from ListGenerator to BTreeValueGenerator.
  • List explicitly implements RangeReplaceableCollectionType.
  • You can now use + to concatenate two List values, just like you can with Arrays.

Map

  • Map now supports elementsEqual, complete with an == operator when its Value is Equatable.
  • Map gained two methods for offset-based removal of elements: removeAtOffset and removeAtOffsets
  • You can now merge two Map values into a single map using merge.
  • You can extract a submap from a Map that includes or excludes a specific set or sequence of keys.

Improvements

  • Navigation inside the B-tree is now unified under a single protocol, BTreePath, for all three flavors of tree paths: BTreeStrongPath, BTreeWeakPath and BTreeCursorPath.
  • The complexity of BTree.endIndex has been reduced from O(log(n)) to O(1). This also improves the endIndex properties of Map and OrderedSet.
  • Iterating over B-trees is now a bit faster, as getting to the successor of an item does not normally involve array lookups.
  • BTree.shiftSlots is a new internal method for shifting elements between nodes at the same level. This operation is often useful while reorganizing/rebalancing the tree.
  • The bulk loading algorithm has been extracted into a separate internal struct and generalized to allow appending full trees, not just elements.
  • The generated docs now include nice method group headers splitting the method lists into organized chunks.

Bug fixes

  • Fixed issue #3, "Crash when inserting Element in List".
  • The copy-on-write semantics of BTree.withCursor(at: Index) have been fixed.
  • BTree now never allows its arrays to get larger than their specified order. (Previously, BTree.join could allow arrays to grow twice the maximum size, leading to wasted capacity.)
Assets 2
Loading