me.tonsky.persistent-sorted-set — org.clojars.tiensonqin/persistent-sorted-set 0.1.0

A B-tree based persistent sorted set. Supports transients, custom comparators, fast iteration, efficient slices (iterator over a part of the set) and reverse slices. Almost a drop-in replacement for [[clojure.core/sorted-set]], the only difference being this one can’t store nil.

-slice cljs

(-slice set key-from key-to comparator)

alter-btset cljs

(alter-btset set root shift cnt)

arr-map-inplace cljs

(arr-map-inplace f arr)

arr-partition-approx cljs

(arr-partition-approx min-len max-len arr)

Splits arr into arrays of size between min-len and max-len, trying to stick to (min+max)/2

bit-mask cljs

bits-per-level cljs

tunable param

child cljs

(child node idx storage)

conj clj/s≠

(conj set key cmp)

clj

Analogue to [[clojure.core/conj]] but with comparator that overrides the one stored in set.

cljs

Analogue to [[clojure.core/conj]] with comparator that overrides the one stored in set.

disj clj/s

(disj set key cmp)

Analogue to [[clojure.core/disj]] with comparator that overrides the one stored in set.

empty-path cljs

est-count cljs

(est-count iter)

factors cljs

from-sequential clj/s≠

clj

(from-sequential cmp keys)

(from-sequential cmp keys opts)

cljs

(from-sequential cmp seq)

Create a set with custom comparator and a collection of keys. Useful when you don’t want to call [[clojure.core/apply]] on sorted-set-by.

from-sorted-array clj/s≠

clj

(from-sorted-array cmp keys)

(from-sorted-array cmp keys len)

(from-sorted-array cmp keys len opts)

cljs

(from-sorted-array cmp arr)

(from-sorted-array cmp arr _len)

(from-sorted-array cmp arr _len opts)

Fast path to create a set if you already have a sorted array of elements on your hands.

IIter cljs protocol

-copy cljs

(-copy this left right)

INode cljs protocol

node-child cljs

(node-child _ idx storage)

node-conj cljs

(node-conj _ cmp key storage)

node-disj cljs

(node-disj _ cmp key root? left right storage)

node-len cljs

(node-len _)

node-lim-key cljs

(node-lim-key _)

node-lookup cljs

(node-lookup _ cmp key storage)

node-merge cljs

(node-merge _ next storage)

node-merge-n-split cljs

(node-merge-n-split _ next)

IRoot cljs protocol

-ensure-root-node cljs

(-ensure-root-node _)

ISeek cljs protocol

-seek cljs

(-seek this key)

(-seek this key comparator)

IStore cljs protocol

store-aux cljs

(store-aux this storage)

iter cljs

(iter set left right)

max-len cljs

max-safe-level cljs

max-safe-path cljs

js limitation for bit ops

min-len cljs

new-leaf cljs

(new-leaf keys)

(new-leaf keys address)

(new-leaf keys address dirty)

new-node cljs

(new-node keys children addresses)

(new-node keys children addresses address)

(new-node keys children addresses address dirty?)

restore clj/s

(restore address storage)

(restore address storage opts)

Constructs lazily-loaded set from storage and root address. Supports all operations that normal in-memory impl would, will fetch missing nodes by calling IStorage::restore when needed

restore-by clj/s≠

clj

(restore-by cmp address storage)

(restore-by cmp address storage opts)

cljs

(restore-by cmp address storage)

(restore-by cmp address storage {:keys [set-metadata]})

Constructs lazily-loaded set from storage, root address and custom comparator. Supports all operations that normal in-memory impl would, will fetch missing nodes by calling IStorage::restore when needed

riter cljs

(riter set left right)

rslice clj/s≠

clj

(rslice set from to)

(rslice set from to cmp)

A reverse iterator for part of the set with provided boundaries. (rslice set from to) returns backwards iterator for all Xs where from <= X <= to. (rslice set from nil) returns backwards iterator for all Xs where X <= from. Optionally pass in comparator that will override the one that set uses. Supports efficient [[clojure.core/rseq]].

cljs

(rslice set key)

(rslice set key-from key-to)

(rslice set key-from key-to comparator)

A reverse iterator for part of the set with provided boundaries. (rslice set from to) returns backwards iterator for all Xs where from <= X <= to. Optionally pass in comparator that will override the one that set uses. Supports efficient [[clojure.core/rseq]].

seek clj/s

(seek seq to)

(seek seq to cmp)

An efficient way to seek to a specific key in a seq (either returned by [[clojure.core.seq]] or a slice.) (seek (seq set) to) returns iterator for all Xs where to <= X. Optionally pass in comparator that will override the one that set uses.

settings clj/s

(settings set)

slice clj/s≠

clj

(slice set from to)

(slice set from to cmp)

An iterator for part of the set with provided boundaries. (slice set from to) returns iterator for all Xs where from <= X <= to. (slice set from nil) returns iterator for all Xs where X >= from. Optionally pass in comparator that will override the one that set uses. Supports efficient [[clojure.core/rseq]].

cljs

(slice set key-from key-to)

(slice set key-from key-to comparator)

An iterator for part of the set with provided boundaries. (slice set from to) returns iterator for all Xs where from <= X <= to. Optionally pass in comparator that will override the one that set uses. Supports efficient [[clojure.core/rseq]].

sorted-arr-distinct cljs

(sorted-arr-distinct arr cmp)

Filter out repetitive values in a sorted array. Optimized for no-duplicates case

sorted-set clj/s≠

(sorted-set)

(sorted-set & keys)

clj

Create a set with default comparator.

sorted-set* clj/s

(sorted-set* opts)

Create a set with custom comparator, metadata and settings

sorted-set-by clj/s≠

(sorted-set-by cmp)

(sorted-set-by cmp & keys)

clj

Create a set with custom comparator.

store clj/s

(store set)

(store set storage)

Store each not-yet-stored node by calling IStorage::store and remembering returned address. Incremental, won’t store same node twice on subsequent calls. Returns root address. Remember it and use it for restore

uninitialized-address cljs

uninitialized-hash cljs

walk-addresses clj

(walk-addresses set consume-fn)

Visit each address used by this set. Usable for cleaning up garbage left in storage from previous versions of the set