--- title: dankogai/swift-critbittree framework: Swift Package Catalog role: article path: packages/dankogai/swift-critbittree --- # dankogai/swift-critbittree [Crit-bit tree] in Swift — `CBTSet` and `CBTDictionary`, drop-in analogues of `Set` and `Dictionary` that keep their elements in sorted order. ## Synopsis ```swift import CritBitTree var set: CBTSet = ["swift", "critbit", "tree"] set.insert("banana") set.contains("swift") // true Array(set) // ["banana", "critbit", "swift", "tree"] — always sorted set.prefix("cr") // ["critbit"] — prefix search in O(len(prefix)) var freq = CBTDictionary() for word in "to be or not to be".split(separator: " ") { freq[word, default: 0] += 1 } print(freq) // ["be": 2, "not": 1, "or": 1, "to": 2] ``` ## Description A crit-bit tree is a binary trie in which every internal node records only the position of the *critical bit* — the first bit at which its two subtrees differ — and every key lives in a leaf. It was popularized by [D. J. Bernstein][Crit-bit tree]; see also [Adam Langley's annotated implementation][critbit.pdf] and [Nim's critbits module][nim-critbits]. [critbit.pdf]: https://www.imperialviolet.org/binary/critbit.pdf [nim-critbits]: https://nim-lang.org/docs/critbits.html Properties that fall out of the structure: - **Fast, comparison-free operations** — membership, insertion, and removal walk one node per critical bit, testing a single bit at each step: O(k) where k is the key length in bits, independent of the number of elements. - **Sorted iteration** — in-order traversal yields keys in ascending bit-lexicographic order, for free. - **Canonical shape** — the tree's structure depends only on the set of keys, never on insertion order, which makes equality a simple parallel traversal. - **Compact** — n keys need exactly n − 1 internal nodes. This package implements the tree as a persistent (path-copying) data structure, so `CBTSet` and `CBTDictionary` are value types with the same copy-on-assignment behavior as `Set` and `Dictionary`, sharing structure between copies. ### Types | Type | Analogue of | |------|-------------| | `CBTSet` / `CBASet` | `Set` | | `CBTDictionary` / `CBADictionary` | `Dictionary` | All four conform to **all protocols of their built-in analogues except** the Objective-C/Foundation bridging machinery (`CVarArg`, `_ObjectiveCBridgeable`, custom `AnyHashable` representations), which only applies to types bridged to `NSSet`/`NSDictionary`. That is: `Sequence`, `Collection`, `SetAlgebra` or `ExpressibleByDictionaryLiteral`, `Equatable`, `Hashable`*, `Encodable`*/`Decodable`*, `Sendable`*, `CustomReflectable`, `CustomStringConvertible`, and `CustomDebugStringConvertible` (* conditionally, like the built-ins). The method-level API matches too: `firstIndex(of:)` / `index(forKey:)` in O(k), `remove(at:)`, `popFirst()`, `Set`-style `filter` returning `Self`, `Keys`/`Values` dictionary views (`values` supports in-place mutation), `init(minimumCapacity:)`, `reserveCapacity(_:)`, and `Dictionary(grouping:by:)`. The `CBT` types store the tree as individually allocated nodes; mutations copy only the path from root to leaf, so copies share almost all structure — and `prefix(_:)` can return a view that shares its subtree outright. The `CBA` types store the same tree in two flat arrays (branches as `(critbit, left, right)` index triples, elements alongside), so an n-element container owns two array buffers instead of 2n − 1 heap nodes: substantially faster in practice (roughly 4× on insertion and iteration, more on removal), at the cost of whole-array copy-on-write when a shared copy mutates, and tombstones left behind by removals until the container empties. Same semantics, same API — pick `CBA` for speed, `CBT` for cheap structural sharing. The append-only storage gives the `CBA` types one extra ability: `insertionOrder()`, a lazy view of the elements in insertion order (updates keep an element's position; remove-then-insert moves it to the end). See [Benchmark.md](Benchmark.md) for measurements against the built-in `Set` and `Dictionary`. Set elements and dictionary keys must conform to `CritBitAvailable`: ```swift public protocol CritBitAvailable: Equatable { /// Position of the first differing bit, MSB-first, or nil if equal. static func critbitAt(_ lhs: Self, _ rhs: Self) -> Int? /// Whether the bit at `position` is set, in the same numbering. func critbit(at position: Int) -> Bool /// The number of bits in the value's representation. var critbitWidth: Int { get } } ``` Conformances are provided for `String`, `Substring`, all ten standard fixed-width integer types, and — conditionally and recursively — `Array` of any conforming element, so `CBTSet<[String]>` or `CBTDictionary<[UInt8], Value>` just work. Arrays are encoded with a leading element count, so they order *shortlex* (shorter arrays first) and `[1, 2]`, `[1, 2, 0]`, and `["1", "2"]` vs `["12"]` are all distinct keys. Default implementations cover any `StringProtocol` or `FixedWidthInteger` type, so conforming another such type is one line: ```swift extension UInt128: CritBitAvailable {} ``` ### Prefix search The signature capability of a crit-bit tree: all keys sharing a prefix occupy one contiguous subtree, so `prefix(_:)` — available on both containers when elements/keys are strings — locates it in O(k) in the length of the prefix, independent of the number of elements, and returns a set/dictionary that shares the subtree: ```swift let s: CBTSet = ["app", "apple", "applesauce", "banana"] s.prefix("app") // ["app", "apple", "applesauce"] let d: CBTDictionary = ["app": 1, "apple": 2, "banana": 3] d.prefix("app") // ["app": 1, "apple": 2] ``` ### Differences from Set and Dictionary Both are inherent to the data structure and can be a feature: - Iteration order is deterministic: ascending bit-lexicographic order. For strings this is UTF-8 byte order; for unsigned integers, numeric order; for signed integers, negative values follow non-negative ones (bit 0 is the sign bit). - Identity is bitwise: two `String` keys are the same key iff their UTF-8 bytes are equal, so canonically equivalent but differently composed strings (e.g. precomposed vs. decomposed `"é"`) are distinct. Relatedly, strings containing `U+0000` are not distinguishable from their truncations — the same limitation as the C original's NUL-terminated keys. ## Usage ### Swift Package Manager Add to your `Package.swift`: ```swift dependencies: [ .package(url: "https://github.com/dankogai/swift-critbittree.git", branch: "main"), ], ``` and `"CritBitTree"` to your target's dependencies. In Xcode: *File → Add Package Dependencies…* with the URL above. ### Build and test ```sh swift build ``` ```sh swift test ``` ### Playground Open `macOS.playground` in Xcode (with the package checked out) to try the API interactively. ## License [MIT](LICENSE). © 2026 Dan Kogai. ## Package Metadata Repository: dankogai/swift-critbittree Default branch: main README: README.md