 | Fast, modern, ropes and ordered collections that do more than sort. Drop-in replacements for |
- Ropes — concat, split, splice, insert: 10–1300x faster than native baselines at scale, in three flavors: generic,
StringRope(CharSequence), andByteRope(unsigned bytes) - Sets and Maps work exactly as you're used to, but do more, up to 60x faster
- Interval maps for overlap queries ("what's scheduled at 3pm?")
- Range maps for non-overlapping regions ("which subnet owns this IP?")
- Segment trees for range aggregation ("total sales from day 10 to 50?")
- Fuzzy collections for nearest-neighbor lookup ("snap 9.3 to the closest valid size")
- Priority queues, multisets, and more
All built from a modular, extensible, weight-balanced tree platform with shared foundation for splitting, joining, and parallel operations.
- Zorp's Sneaker Emporium — Narrative guide with extended examples
- Cookbook — Practical patterns: leaderboards, time-series, scheduling, queues, multisets, and more
- Collections API — Collection-by-collection constructor and operation reference
- Ropes — Rope tutorial, use cases, and design
- Benchmark Report — Current performance numbers (auto-generated)
- Benchmark Methodology — Infrastructure, interpretation, and how to run
- Competitive Analysis — Comparison with other libraries
- vs clojure.data.avl — For data.avl users considering a switch
- Algorithms — Tree structure, rotations, split/join, interval augmentation
- Why Weight-Balanced Trees? — Comparison with red-black and AVL trees
- One Tree, Many Forests — Conceptual architecture and design rationale
Use ordered-set and ordered-map exactly like
clojure.core/sorted-set and clojure.core/sorted-map. All the functions you know work the same way. The difference is under the
hood — and in the new things you can do.
(require '[ordered-collections.core :as oc])
;; Ropes — O(log n) split, splice, concat
(defr (oc/rope [:a:b:c:d:e])) ;=> #vec/rope [:a :b :c :d:e]
(apply oc/rope-concat
(reverse (oc/rope-split r 2))) ;=> #vec/rope [:c :d :e :a :b]
(oc/rope-insert r 2 [:x:y]) ;=> #vec/rope [:a :b :x :y :c :d :e];; Sets
(defs (oc/ordered-set [31415926])) ;=> #ordered/set [1 2 3 4 5 6 9]
(s4) ;=> 4
(s7) ;=> nil
(conj s 0) ;=> #{0 1 2 3 4 5 6 9};; Maps
(defm (oc/ordered-map {:b2:a1:c3})) ;=> #ordered/map [[:a 1] [:b 2] [:c 3]]
(m:b) ;=> 2
(assoc m :d4) ;=> {:a 1, :b 2, :c 3, :d 4}Across the measured workloads, ordered-collections is faster than
both clojure.core/sorted-set and clojure.data.avl at every
cardinality. Set algebra is the standout, with 18-60x wins at 500K.
Even against unordered clojure.core/set the benchmarks still show
roughly 4-28x wins.
| Operation | N=10K | N=100K | N=500K |
|---|---|---|---|
| Union | 12.9x | 23.4x | 59.6x |
| Intersection | 9.3x | 15.5x | 34.6x |
| Difference | 10.8x | 24.3x | 54.7x |
| Operation | N=10K | N=100K | N=500K |
|---|---|---|---|
| Union | 9.7x | 20.0x | 51.3x |
| Intersection | 6.9x | 13.1x | 29.9x |
| Difference | 7.9x | 15.0x | 37.2x |
| Operation | N=10K | N=100K | N=500K |
|---|---|---|---|
| Union | 3.7x | 7.2x | 20.5x |
| Intersection | 3.5x | 6.6x | 17.8x |
| Difference | 4.6x | 9.8x | 28.4x |
| Operation | vs sorted-set | vs data.avl |
|---|---|---|
| Construction | 2.1x / 2.4x / 2.8x | 1.1x / 1.2x / 1.5x |
| Lookup | 1.1x / 1.0x / 0.9x | 1.0x / 0.9x / 0.9x |
| Split | — | 4.9x / 6.1x / 6.8x |
| Fold | 2.5x / 4.0x / 3.5x | 3.1x / 5.4x / 4.8x |
| Workload | N=1K | N=5K | N=10K | N=100K | N=500K |
|---|---|---|---|---|---|
| 200 random edits | 4.7x | 14x | 26x | 261x | 1237x |
| Single splice | 4.8x | 13x | 106x | 762x | 863x |
| Concat pieces | 169x | 22x | 29x | 39x | 36x |
| Reduce (sum) | 1.0x | 1.7x | 1.4x | 1.5x | 1.3x |
| Fold (sum) | 2.9x | 1.4x | 1.2x | 1.3x | 1.6x |
| Random nth (1000) | 0.5x | 0.2x | 0.2x | 0.2x | 0.2x |
| Workload | N=1K | N=5K | N=10K | N=100K | N=500K |
|---|---|---|---|---|---|
| 200 random edits | 0.6x | 2.6x | 5.7x | 38x | 130x |
| Single splice | 0.4x | 3.2x | 5.9x | 42x | 349x |
| Single insert | 0.4x | 2.7x | 6.2x | 40x | 154x |
| Single remove | 1.5x | 3.6x | 7.1x | 44x | 412x |
| Concat halves | 0.9x | 0.5x | 2.5x | 20x | 29x |
| Reduce (sum chars) | 0.4x | 0.5x | 0.5x | 0.5x | 0.5x |
re-find / re-seq | 0.6-1.3x | 0.1-0.2x | 0.1-0.2x | 0.1-0.2x | 0.1-0.2x |
The rope family wins decisively on structural editing at scale; the advantage grows with collection size. See Ropes for the full tutorial.
Benchmarked on Apple M2 (aarch64), OpenJDK 25.0.2, Clojure 1.12.4. See report.txt for full results and benchmarks.md for methodology.
The core is a weight-balanced binary tree. Each node knows its subtree size, enabling O(log n) positional access and efficient parallel decomposition.
Split and join are the fundamental primitives — splitting at a key produces two trees in O(log n); joining is also O(log n). Set operations, subrange extraction, and parallel fold all reduce to split/join. Set operations use Adams' divide-and-conquer algorithm (1992) extended with the parallel forkl-join based approach from Blelloch, Ferizovic & Sun (2016).
Collection constructors provide the comparator and node-construction hooks, so the same tree algorithms can back generic, primitive-specialized, and augmented variants.
Augmented trees extend the basic structure: interval trees store max-endpoint per subtree for O(log n + k) overlap queries; segment trees store aggregates for O(log n) range queries.
See Algorithms for implementation details and Why Weight-Balanced Trees? for comparison with red-black and AVL trees.
The fundamental collection types currently implemented are:
ordered-set, ordered-map, rope, interval-set, interval-map,
range-map, segment-tree, priority-queue, ordered-multiset, fuzzy-set,
and fuzzy-map.
| Constructor | Description |
|---|---|
| Ordered Set | |
(oc/ordered-set coll) | Sorted set (drop-in for sorted-set) |
(oc/ordered-set-by pred coll) | Sorted set with custom comparator |
(oc/long-ordered-set coll) | Sorted set optimized for Long keys |
(oc/string-ordered-set coll) | Sorted set optimized for String keys |
| Ordered Map | |
(oc/ordered-map coll) | Sorted map (drop-in for sorted-map) |
(oc/ordered-map-by pred coll) | Sorted map with custom comparator |
(oc/long-ordered-map coll) | Sorted map optimized for Long keys |
(oc/string-ordered-map coll) | Sorted map optimized for String keys |
| Interval Collections | |
(oc/interval-set coll) | Set supporting interval overlap queries |
(oc/interval-map coll) | Map supporting interval overlap queries |
| Range Map | |
(oc/range-map) | Non-overlapping ranges (Guava TreeRangeMap) |
| Segment Tree | |
(oc/segment-tree f identity coll) | O(log n) range aggregate queries |
(oc/segment-tree-by pred f identity coll) | Segment tree with custom ordering predicate |
(oc/segment-tree-with cmp f identity coll) | Segment tree with custom Comparator |
| Priority Queue | |
(oc/priority-queue pairs) | Priority queue from [priority value] pairs |
| Ordered Multiset | |
(oc/ordered-multiset coll) | Sorted multiset (allows duplicates) |
| Rope | |
(oc/rope coll) | Persistent sequence for structural editing |
(oc/rope-concat a b) | Concatenate two ropes — O(log n) |
(oc/rope-splice r start end items) | Replace a range — O(log n) |
| StringRope | |
(oc/string-rope s) | Persistent text sequence (implements CharSequence) |
(oc/string-rope-concat a b) | Concatenate two string ropes — O(log n) |
| ByteRope | |
(oc/byte-rope bs) | Persistent memory — structural editing, zero-cost snapshots, structure sharing |
(oc/byte-rope-concat a b) | Concatenate two byte ropes — O(log n) |
| Fuzzy Collections | |
(oc/fuzzy-set coll) | Returns closest element to query |
(oc/fuzzy-map coll) | Returns value for closest key to query |
A rope is a persistent sequence optimized for structural editing —
concatenation, splitting, splicing, and insertion in the middle of large
sequences. Where PersistentVector is O(n) for mid-sequence edits,
the rope is O(log n). Three variants share the same kernel:
rope— arbitrary Clojure values (vector-compatible)string-rope— UTF-16 text, implementsCharSequenceforre-find/clojure.stringbyte-rope— persistent memory with structural editing, zero-cost snapshots, and structure sharing. Think of it as a byte buffer with the safety properties of a persistent data structure: splice at any offset in O(log n), keep old versions for free, let the GC reclaim what's unreachable
(defr (oc/rope (range100000)))
;; Splice into the middle — O(log n), not O(n)
(defedited (oc/rope-splice r 5000050010 [:new:data]))
;; Split — O(log n)
(let [[left right] (oc/rope-split r 50000)]
[(count left) (count right)]) ;=> [50000 50000];; StringRope — drops into regex and clojure.string
(deftext (oc/string-rope"hello world"))
(re-find#"wor" text) ;=> "wor";; ByteRope — binary protocols, streaming digest
(defpacket (oc/byte-rope [0x480x450x4C0x4C0x4F]))
(oc/byte-rope-get-int packet 0) ;=> 1212501068See Ropes for the full tutorial.
Operations that sorted-set and sorted-map don't provide — at any collection size.
For the full collection-by-collection surface area, see Collections API.
(defs (oc/ordered-set [5030204010]))
(nth s 2) ;=> 30 O(log n)
(oc/rank s 30) ;=> 2 O(log n)
(oc/median s) ;=> 30 O(log n)
(oc/percentile s 90) ;=> 50 O(log n)
(oc/slice s 14) ;=> (20 30 40)(defs (oc/ordered-set [200200400300500]))
(oc/nearest s :<=350) ;=> 300 (floor)
(oc/nearest s :>=350) ;=> 400 (ceiling)
(oc/nearest s :<300) ;=> 200 (predecessor)
(oc/nearest s :>300) ;=> 400 (successor)(defs (oc/ordered-set [54312]))
(oc/split-key3 s) ;=> [#{1 2} 3 #{4 5}] O(log n)
(oc/split-at2 s) ;=> [#{1 2} #{3 4 5}] O(log n);; subrange returns a collection, not a seq
(oc/subrange s :>=2:<=4) ;=> #{2 3 4} meeting: +-------+
lunch: +-------+
review: +-------+
9==10==11==12==13==14==15==16==17
(defschedule
(oc/interval-map
{[912] "meeting" [1417] "review" [1115] "lunch"}))
(schedule11) ;=> ("meeting" "lunch") point query
(schedule [1014]) ;=> ("meeting" "lunch" "review") range query
(oc/span schedule) ;=> [9 17]Non-overlapping ranges — each point maps to exactly one value. Inserting a new range automatically carves out whatever it overlaps.
(deftiers
(-> (oc/range-map)
(assoc [0100] :bronze)
(assoc [100500] :silver)
(assoc [5005000] :gold)))
(tiers250) ;=> :silver
(oc/get-entry tiers 250) ;=> [[100 500] :silver]Insert a flash-sale range — bronze and silver are automatically split:
(oc/ranges (assoc tiers [50200] :flash))
;; => ([[0 50] :bronze] ← auto-trimmed;; [[50 200] :flash] ← inserted;; [[200 500] :silver] ← auto-trimmed;; [[500 5000] :gold])(defsales (oc/sum-tree {1100, 2200, 3150, 4300, 5250}))
(oc/query sales 24) ;=> 650 O(log n)
(oc/aggregate sales) ;=> 1000 O(1);; Update and re-query
(defsales' (assoc sales 3500))
(oc/query sales' 24) ;=> 1000;; Also: min-tree, max-tree, or any associative operation
(defpeaks (oc/segment-tree max 0 {1100, 2200, 3150}))
(oc/query peaks 13) ;=> 200(defsizes (oc/fuzzy-set [678910111213]))
(sizes9.3) ;=> 9
(oc/fuzzy-nearest sizes 9.3) ;=> [9 0.30]
(deftiers (oc/fuzzy-map {0:bronze500:silver1000:gold}))
(tiers480) ;=> :silver;; Priority queue (min-heap)
(defpq (oc/priority-queue [[3:medium] [1:urgent] [5:low]]))
(peek pq) ;=> [1 :urgent]
(peek (pop pq)) ;=> [3 :medium];; Multiset (sorted bag, allows duplicates)
(defms (oc/ordered-multiset [31415926535]))
(oc/multiplicity ms 5) ;=> 3All collection types implement CollFold for efficient r/fold:
(require '[clojure.core.reducers :as r])
(defcombinef (fn ([] {}) ([m1 m2] (merge-with + m1 m2))))
(defreducef (fn [m x] (update m (mod x 100) (fnil inc 0))))
(r/fold combinef reducef (oc/ordered-set (range1000000)))
;; 1M-element frequency-map workload from the benchmark suite:;; ~6.9x faster than hash-set reduce, ~4.5x faster than sorted-set fold,;; ~3.4x faster than data.avl fold$ lein test
Ran 690 tests containing 471,000+ assertions.
0 failures, 0 errors.
The test suite includes generative tests via test.check and equivalence
tests against sorted-set, sorted-map, and clojure.data.avl.
$ lein codox # Generate API docs in doc/api
$ lein stats # Print project statistics
$ lein bench # Criterium, N=100K (~5 min)
$ lein bench --full # Criterium, N=1K,5K,10K,100K,500K (~60 min)
$ lein bench --readme --full # README tables only (~10 min)
$ lein bench --sizes 50000 # Custom sizes
$ lein bench-simple # Quick iteration bench (100 to 100K)
$ lein bench-simple --full # Full suite (100 to 1M)
$ lein bench-range-map # Range-map vs Guava TreeRangeMap
$ lein bench-parallel # Parallel threshold crossover analysis
$ lein bench-report # Analyze latest benchmark results
Criterium results are written to
bench-results/<timestamp>.edn.
The implementation of this weight-balanced binary tree data structure library was inspired by the following:
Adams (1992) 'Implementing Sets Efficiently in a Functional Language' Technical Report CSTR 92-10, University of Southampton. http://groups.csail.mit.edu/mac/users/adams/BB/92-10.ps
Hirai and Yamamoto (2011) 'Balancing Weight-Balanced Trees' Journal of Functional Programming / 21 (3): Pages 287-307 https://yoichihirai.com/bst.pdf
Oleg Kiselyov 'Towards the best collection API, A design of the overall optimal collection traversal interface' https://okmij.org/ftp/papers/LL3-collections-enumerators.txt
Nievergelt and Reingold (1972) 'Binary Search Trees of Bounded Balance' STOC '72 Proceedings 4th Annual ACM symposium on Theory of Computing Pages 137-142 https://dl.acm.org/doi/abs/10.1145/800152.804906
Driscoll, Sarnak, Sleator, and Tarjan (1989) 'Making Data Structures Persistent' Journal of Computer and System Sciences Volume 38 Issue 1, February 1989 18th Annual ACM Symposium on Theory of Computing Pages 86-124 https://www.sciencedirect.com/science/article/pii/0022000089900342
MIT Scheme weight balanced tree as reimplemented by Yoichi Hirai and Kazuhiko Yamamoto using the revised non-variant algorithm recommended integer balance parameters from (Hirai/Yamamoto 2011). https://www.cambridge.org/core/journals/journal-of-functional-programming/article/balancing-weightbalanced-trees/7281C4DE7E56B74F2D13F06E31DCBC5B
Wikipedia 'Interval Tree' https://en.wikipedia.org/wiki/Interval_tree
Wikipedia 'Segment Tree' https://en.wikipedia.org/wiki/Segment_tree
Google Guava 'RangeMap' https://guava.dev/releases/snapshot/api/docs/com/google/common/collect/RangeMap.html
Wikipedia 'Weight Balanced Tree' https://en.wikipedia.org/wiki/Weight-balanced_tree
Andrew Baine (2007) 'Purely Functional Data Structures in Common Lisp' Google Summer of Code 2007, mentored by Rahul Jain https://funds.common-lisp.dev/funds.pdfhttps://developers.google.com/open-source/gsoc/2007/
Scott L. Burson 'Functional Set-Theoretic Collections for Common Lisp' https://fset.common-lisp.dev/
Adams (1993) 'Efficient sets—a balancing act' Journal of Functional Programming 3(4): 553-562 https://www.cambridge.org/core/journals/journal-of-functional-programming/article/functional-pearls-efficient-setsa-balancing-act/0CAA1C189B4F7C15CE9B8C02D0D4B54E
Blelloch, Ferizovic, and Sun (2016) 'Just Join for Parallel Ordered Sets' ACM SPAA 2016 https://dl.acm.org/doi/10.1145/2935764.2935768
Boehm, Atkinson, and Plass (1995) 'Ropes: an Alternative to Strings' Software: Practice and Experience 25(12) https://www.cs.rit.edu/usr/local/pub/jeh/courses/QUARTERS/FP/Labs/CesswordsII/boehm-ropes.pdf
Haskell containers library (Data.Set, Data.Map) https://hackage.haskell.org/package/containers
SLIB Weight-Balanced Trees (Aubrey Jaffer) https://people.csail.mit.edu/jaffer/slib/Weight_002dBalanced-Trees.html
PAM: Parallel Augmented Maps https://cmuparlay.github.io/PAMWeb/
The use and distribution terms for this software are covered by the Eclipse Public License 1.0, which can be found in the file LICENSE.txt at the root of this distribution. By using this software in any fashion, you are agreeing to be bound by the terms of this license. You must not remove this notice, or any other, from this software.
For extended examples featuring Zorp, Kevin the sentient flip-flop, and Big Toe Tony's 47 feet, see Zorp's Sneaker Emporium.