com.dean.interval-tree.tree.tree — com.dean/interval-tree 0.1.2

*n-join* clj

*t-join* clj

+delta+ clj

The primary balancing rotation coefficient that is used for the determination whether two subtrees of a node are in balance or require adjustment by means of a rotation operation. The specific rotation to be performed is determined by +gamma+.

+gamma+ clj

The secondary balancing rotation coefficient that is used for the determination of whether a single or double rotation operation should occur, once it has been decided based on +delta+ that a rotation is indeed required.

kvlr clj macro

(kvlr [ksym vsym lsym rsym] n & body)

destructure node n: key value left right. This is the principal destructuring macro for operating on regions of trees

lr clj macro

(lr [lsym rsym] n & body)

maybe-z clj

(maybe-z n)

node-add clj

(node-add n k)

(node-add n k v)

Insert a new key/value into the tree rooted at n.

node-chunked-fold clj

(node-chunked-fold i n combinef reducef)

Parallel chunked fold mechansim to suport clojure.core.reducers/CollFold

node-compare clj

(node-compare accessor n1 n2)

return 3-way comparison of the trees n1 and n2 using an accessor to compare specific node consitituent values: :k, :v, :kv, or any user-specifed function. Default, when not specified, to the entire node structure. return-value semantics: -1 -> n1 is LESS-THAN n2 0 -> n1 is EQUAL-TO n2 +1 -> n1 is GREATER-THAN n2

node-concat2 clj

(node-concat2 l r)

Join two trees, the left rooted at l, and the right at r, performing a single balancing operation on the resulting tree, if needed. Assumes all keys in l are smaller than all keys in r, and the relative balance of l and r is such that no more than one rotation operation will be required to balance the resulting tree.

node-concat3 clj

(node-concat3 k v l r)

Join two trees, the left rooted at l, and the right at r, with a new key/value, performing rotation operations on the resulting trees and subtrees. Assumes all keys in l are smaller than all keys in r, and the relative balance of l and r is such that no more than one rotation operation will be required to balance the resulting tree.

node-create clj

(node-create k v l r)

Join left and right subtrees at root k/v. Assumes all keys in l < k < all keys in r.

node-create-weight-balanced clj

(node-create-weight-balanced k v l r)

Join left and right weight-balanced subtrees at root k/v. Assumes all keys in l < k < all keys in r.

node-create-weight-balanced-interval clj

(node-create-weight-balanced-interval i v l r)

Join left and right weight-balanced interval subtrees at root k/v. Assumes all keys in l < k < all keys in r.

node-enum-first clj

node-enum-prior clj

(node-enum-prior enum)

node-enum-rest clj

(node-enum-rest enum)

node-enumerator clj

(node-enumerator n)

(node-enumerator n enum)

Efficient mechanism to accomplish partial enumeration of tree-structure into a seq representation without incurring the overhead of operating over the entire tree. Used internally for implementation of higher-level collection api routines

node-enumerator-reverse clj

(node-enumerator-reverse n)

(node-enumerator-reverse n enum)

node-filter clj

(node-filter p n)

return a tree with all nodes of n satisfying predicate p.

node-find clj

(node-find n k)

find a node in n whose key = k

node-find-best-interval clj

(node-find-best-interval n i pred)

node-find-intervals clj

(node-find-intervals n i)

node-find-nearest clj

(node-find-nearest n k & [gt-or-lt])

Find the nearest k according to relation expressed by :< or :>

node-fold-left clj

(node-fold-left f n)

(node-fold-left f base n)

Fold-left (reduce) the collection from least to greatest.

node-fold-right clj

(node-fold-right f n)

(node-fold-right f base n)

Fold-right (reduce) the collection from greatest to least.

node-greatest clj

(node-greatest n)

Return the node containing the minimum key of the tree rooted at n

node-healthy? clj

(node-healthy? n)

verify node n and all descendants satisfy the node-invariants of a weight-balanced binary tree.

node-invert clj

(node-invert n)

return a tree in which the keys and values of n are reversed.

node-iter clj

(node-iter n f)

For the side-effect, apply f to each node of the tree rooted at n.

node-iter-reverse clj

(node-iter-reverse n f)

For the side-effect, apply f to each node of the tree rooted at n.

node-least clj

(node-least n)

Return the node containing the minimum key of the tree rooted at n

node-map-compare clj

node-map-merge clj

(node-map-merge n1 n2 merge-fn)

Merge two maps in worst case linear time.

node-nth clj

(node-nth n index)

Return nth node from the beginning of the ordered tree rooted at n. (Logarithmic Time)

node-rank clj

(node-rank n k)

Return the rank (sequential position) of a given KEY within the ordered tree rooted at n. (Logarithmic Time)

node-remove clj

(node-remove n k)

remove the node whose key is equal to k, if present.

node-remove-greatest clj

(node-remove-greatest n)

Return a tree the same as the one rooted at n, with the node containing the maximum key removed. See node-greatest.

node-remove-least clj

(node-remove-least n)

Return a tree the same as the one rooted at n, with the node containing the minimum key removed. See node-least.

node-seq clj

(node-seq n)

Return a (lazy) seq of nodes in tree rooted at n in the order they occur. (Logarithmic Time)

node-seq-reverse clj

(node-seq-reverse n)

Return a (lazy) seq of nodes in tree rooted at n in reverse order.

node-set-compare clj

node-set-difference clj

(node-set-difference n1 n2)

node-set-intersection clj

(node-set-intersection n1 n2)

set intersection

node-set-union clj

(node-set-union n1 n2)

set union

node-singleton clj

(node-singleton k v)

Create and return a newly allocated, balanced tree containing a single association, that of key K with value V.

node-size clj

(node-size n)

returns the balance metric of the tree rooted at n.

node-split clj

(node-split n k)

returns a triple (l present r) where: l is the set of elements of n that are < k, r is the set of elements of n that are > k, present is false if n contains no element equal to k, or (k v) if n contains an element with key equal to k.

node-split-greater clj

(node-split-greater n k)

return a tree of all nodes whose key is greater than k (Logarithmic time).

node-split-lesser clj

(node-split-lesser n k)

return a tree of all nodes whose key is less than k (Logarithmic time).

node-split-nth clj

(node-split-nth n i)

return a tree of all nodes whose position is >= i. (Logarithmic Time)

node-stitch clj

(node-stitch k v l r)

The stitch operation is the sole balancing constructor and interface to the specific balancing rotation algorithm of the tree. other balancing algorithms (AVL Tree, Red-Black Tree) can be implemented here without effect to other aspects of the tree. Sometimes referred to as n-join operation

node-stitch-weight-balanced clj

(node-stitch-weight-balanced k v l r)

Weight-Balancing Algorithm:

Join left and right subtrees at root k/v, performing a single or double rotation to balance the resulting tree, if needed. Assumes all keys in l < k < all keys in r, and the relative weight balance of the left and right subtrees is such that no more than one single/double rotation will result in each subtree being less than +delta+ times the weight of the other. This is the heart of tree construction.

node-subseq clj

(node-subseq n from)

(node-subseq n from to)

Return a (lazy) seq of nodes for the slice of the tree beginning at position from ending at to.

node-subset? clj

(node-subset? super sub)

return true if sub is a subset of super

node-vec clj

(node-vec n & {:keys [accessor reverse?]})

Eagerly return a vector of all nodes in tree rooted at n in the specified order, optionally using an accessor to extract specific node consitituent values: :k, :v, :kv, or any user-specifed function. Default, when not specified, to the entire node structure.

node-weight clj

(node-weight n)

returns node weight as appropriate for rotation calculations using the 'revised non-variant algorithm' for weight balanced binary tree.

rotate-double-left clj

(rotate-double-left ak av x c)

Perform a double left rotation, moving Y1, the left subtree of the left subtree of the right subtree of A, into the left subtree (shown below). This must occur in order to restore proper balance when the weight of the left subtree of node A is less then the weight of the right subtree of node A multiplied by rotation coefficient +delta+ and the weight of the left subtree of node B is greater than or equal to the weight of the right subtree of node B multiplied by rotation coefficient +gamma+.

          ,---,                                    ,---,
          | A |                                    | B |
       ___:---:___                             ____:---:____
  ,---:           :---,                   ,---:             :---,
  | X |           | C |                   | A |             | C |
  '---'           :---:         =>        :---:             :---:
             ,---:     :---,         ,---:     :---,   ,---:     :---,
             | B |     | Z |         | X |     | y1|   | y2|     | Z |
             :---:     '---'         '---'     '---'   '---'     '---'
        ,---:     :---,
        | y1|     | y2|
        '---'     '---'

rotate-double-right clj

(rotate-double-right ck cv a z)

Perform a double right rotation, moving Y2, the right subtree of the right subtree of the left subtree of C, into the right subtree (shown below). This must occur in order to restore proper balance when the weight of the right subtree of node C is less then the weight of the left subtree of node C multiplied by rotation coefficient +delta+ and the weight of the right subtree of node B is greater than or equal to the weight of the left subtree of node B multiplied by rotation coefficient +gamma+.

          ,---,                                    ,---,
          | C |                                    | B |
       ___:---:___                             ____:---:____
  ,---:           :---,                   ,---:             :---,
  | A |           | Z |                   | A |             | C |
  :---:           '---'        =>         :---:             :---:

,---: :---, ,---: :---, ,---: :---, | X | | B | | X | | y1| | y2| | Z | '---' :---: '---' '---' '---' '---' ,---: :---, | y1| | y2| '---' '---'

rotate-single-left clj

(rotate-single-left ak av x b)

Perform a single left rotation, moving Y, the left subtree of the right subtree of A, into the left subtree (shown below). This must occur in order to restore proper balance when the weight of the left subtree of node A is less then the weight of the right subtree of node A multiplied by rotation coefficient +delta+ and the weight of the left subtree of node B is less than the weight of the right subtree of node B multiplied by rotation coefficient +gamma+

          ,---,                                  ,---,
          | A |                                  | B |
          :---:                                  :---:
         :     :                                :     :
    ,---:       :---,                      ,---:       :---,
    | X |       | B |           =>         | A |       | Z |
    '---'       :---:                      :---:       '---'
           ,---:     :---,            ,---:     :---,
           | Y |     | Z |            | X |     | Y |
           '---'     '---'            '---'     '---'

rotate-single-right clj

(rotate-single-right bk bv a z)

Perform a single right rotation, moving Y, the right subtree of the left subtree of B, into the right subtree (shown below). This must occur in order to restore proper balance when the weight of the right subtree of node B is less then the weight of the left subtree of node B multiplied by rotation coefficient +delta+ and the weight of the right subtree of node A is less than the weight of the left subtree of node A multiplied by rotation coefficient +gamma+.

          ,---,                                  ,---,
          | B |                                  | A |
          :---:                                  :---:
         :     :                                :     :
    ,---:       :---,                      ,---:       :---,
    | A |       | Z |          =>          | X |       | B |
    :---:       '---'                      '---'       :---:

,---: :---, ,---: :---, | X | | Y | | Y | | Z | '---' '---' '---' '---'