Liking cljdoc? Tell your friends :D

datahike.btset

B+ tree

Leaf: keys[] :: array of values

Node: pointers[] :: links to children nodes keys[] :: max value for whole subtree node.keys[i] == max(node.pointers[i].keys) All arrays are 64..128 elements, inclusive

BTSet: root :: Node or Leaf shift :: path bit-shift of root level, == (depth - 1) * level-shift cnt :: size of a set, integer, rolling comparator :: comparator used for ordering meta :: clojure meta map __hash :: hash code, same as for clojure collections, on-demand, cached

Path: conceptually a vector of indexes from root to leaf value, but encoded in a single int. E.g. we have path [7 53 11] representing root.pointers[7].pointers[3].keys[11]. In our case level-shift is 8, meaning each index will take 8 bits: (7 << 16) | (53 << 8) | 11 = 472331 0000 0111 0011 0101 0000 1011

Iter: set :: Set this iterator belongs to left :: Current path right :: Right bound path (exclusive) keys :: Cached ref for keys array for a leaf idx :: Cached idx in keys array Keys and idx are cached for fast iteration inside a leaf

 B+ tree
-------

Leaf: keys[]     :: array of values

Node:     pointers[] :: links to children nodes
          keys[]     :: max value for whole subtree
                        node.keys[i] == max(node.pointers[i].keys)
All arrays are 64..128 elements, inclusive

BTSet:    root       :: Node or Leaf
          shift      :: path bit-shift of root level, == (depth - 1) * level-shift
          cnt        :: size of a set, integer, rolling
          comparator :: comparator used for ordering
          meta       :: clojure meta map
          __hash     :: hash code, same as for clojure collections, on-demand, cached

Path: conceptually a vector of indexes from root to leaf value, but encoded in a single int.
      E.g. we have path [7 53 11] representing root.pointers[7].pointers[3].keys[11].
      In our case level-shift is 8, meaning each index will take 8 bits:
      (7 << 16) | (53 << 8) | 11 = 472331
      0000 0111   0011 0101   0000 1011

Iter:     set       :: Set this iterator belongs to
          left      :: Current path
          right     :: Right bound path (exclusive)
          keys      :: Cached ref for keys array for a leaf
          idx       :: Cached idx in keys array
Keys and idx are cached for fast iteration inside a leaf
raw docstring

-btset-from-seqclj/s

(-btset-from-seq seq cmp)
source

-btset-from-sorted-arrclj/s

(-btset-from-sorted-arr arr cmp)
source

-distanceclj/s

(-distance node left right level)
source

-next-pathclj/s

(-next-path node path level)
source

-prev-pathclj/s

(-prev-path node path level)
source

-rpathclj/s

(-rpath node level)

Returns rightmost path possible starting from node and going deeper

Returns rightmost path possible starting from node and going deeper
sourceraw docstring

-rseekclj/s

(-rseek set key)

Returns path to the first element that is > key. If all elements in a set are <= key, returns (-rpath set) + 1. It’s a virtual path that is bigger than any path in a tree

Returns path to the first element that is > key.
If all elements in a set are <= key, returns `(-rpath set) + 1`.
It’s a virtual path that is bigger than any path in a tree
sourceraw docstring

-seekclj/s

(-seek set key)

Returns path to first element >= key, or -1 if all elements in a set < key

Returns path to first element >= key,
or -1 if all elements in a set < key
sourceraw docstring

-sliceclj/s

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

alastclj/s

(alast arr)
source

alter-btsetclj/s

(alter-btset set root shift cnt)
source

arr-map-inplaceclj/s

(arr-map-inplace f arr)
source

avg-lenclj/s

source

binary-search-lclj/s

(binary-search-l cmp arr r k)
source

binary-search-rclj/s

(binary-search-r cmp arr r k)
source

btsetclj/s

(btset)
(btset & keys)
source

BTSetcljs

source

btset-byclj/s

(btset-by cmp)
(btset-by cmp & keys)
source

btset-conjclj/s

(btset-conj set key cmp)
source

btset-disjclj/s

(btset-disj set key cmp)
source

btset-iterclj/s

(btset-iter set)

Iterator that represents whole set

Iterator that represents whole set
sourceraw docstring

check-n-spliceclj/s

(check-n-splice cmp arr from to new-arr)
source

cutclj/s

(cut arr cut-from)
(cut arr cut-from cut-to)
source

cut-n-spliceclj/s

(cut-n-splice arr cut-from cut-to splice-from splice-to xs)
source

distanceclj/s

(distance set path-l path-r)
source

empty-pathclj/s

source

eq-arrclj/s

(eq-arr cmp a1 a1-from a1-to a2 a2-from a2-to)
source

est-countclj/s

(est-count iter)
source

halfclj/smacro

(half x)
source

INodeclj/s≠protocol

node-conjclj/s

(node-conj _ cmp key)

node-disjclj/s

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

node-lenclj/s

(node-len _)

node-lim-keyclj/s

(node-lim-key _)

node-lookupclj/s

(node-lookup _ cmp key)

node-mergeclj/s

(node-merge _ next)

node-merge-n-splitclj/s

(node-merge-n-split _ next)
source

insertclj/s

(insert arr idx xs)
source

Itercljs

source

iterclj/s

(iter set left right)
source

iter-chunkclj/s

(iter-chunk iter)
source

iter-chunked-nextclj/s

(iter-chunked-next iter)
source

iter-firstclj/s

(iter-first iter)
source

iter-nextclj/s

(iter-next iter)
source

iter-reduceclj/s

(iter-reduce iter f)
(iter-reduce iter f start)
source

iter-rseqclj/s

(iter-rseq iter)
source

keys-forclj/s

(keys-for set path)
source

Leafcljs

source

level-shiftclj/s

source

lookup-exactclj/s

(lookup-exact cmp arr key)
source

lookup-rangeclj/s

(lookup-range cmp arr key)
source

max-lenclj/s

source

merge-n-splitclj/s

(merge-n-split a1 a2)
source

min-lenclj/s

source

next-pathclj/s

(next-path set path)

Returns path representing next item after path in natural traversal order, or -1 if end of tree has been reached

Returns path representing next item after `path` in natural traversal order,
or -1 if end of tree has been reached
sourceraw docstring

Nodecljs

source

not==clj/smacro

(not== x y)
source

path-getclj/s

(path-get path level)
source

path-maskclj/s

source

path-setclj/s

(path-set path level idx)
source

prev-pathclj/s

(prev-path set path)

Returns path representing previous item before path in natural traversal order, or -1 if path was already beginning of a tree

Returns path representing previous item before `path` in natural traversal order,
or -1 if `path` was already beginning of a tree
sourceraw docstring

return-arrayclj/s

(return-array a1)
(return-array a1 a2)
(return-array a1 a2 a3)

Drop non-nil references and return array of arguments

Drop non-nil references and return array of arguments
sourceraw docstring

ReverseItercljs

source

riterclj/s

(riter set left right)
source

riter-firstclj/s

(riter-first riter)
source

riter-nextclj/s

(riter-next ri)
source

riter-rseqclj/s

(riter-rseq riter)
source

rotateclj/s

(rotate node root? left right)
source

sliceclj/s

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

When called with single key, returns iterator over set that contains all elements equal to the key. When called with two keys (range), returns iterator for all X where key-from <= X <= key-to

When called with single key, returns iterator over set that contains all elements equal to the key.
When called with two keys (range), returns iterator for all X where key-from <= X <= key-to
sourceraw docstring

spliceclj/s

(splice arr splice-from splice-to xs)
source

uninitialized-hashclj/s

source

cljdoc is a website building & hosting documentation for Clojure/Script libraries

× close