Home Original page

clojure.data.avl - data.avl 0.2.0-SNAPSHOT API documentation

API for clojure.data.avl -


Full namespace name: clojure.data.avl

Overview

An implementation of persistent sorted maps and sets based on AVL
trees which can be used as drop-in replacements for Clojure's
built-in sorted maps and sets based on red-black trees. Apart from
the standard sorted collection API, the provided map and set types
support the transients API and several additional logarithmic time
operations: rank queries via clojure.core/nth (select element by
rank) and clojure.data.avl/rank-of (discover rank of element),
"nearest key" lookups via clojure.data.avl/nearest, splits by key
and index via clojure.data.avl/split-key and
clojure.data.avl/split-at, respectively, and subsets/submaps using
clojure.data.avl/subrange.

Types


AVLMap

type


    Fields: [comp tree cnt _meta _hash _hasheq]

    Protocols: clojure.core.protocols/IKVReduce

    Interfaces: clojure.data.avl.IAVLTree, clojure.data.avl.INavigableTree, clojure.lang.Associative, clojure.lang.Counted, clojure.lang.IEditableCollection, clojure.lang.IFn, clojure.lang.IHashEq, clojure.lang.ILookup, clojure.lang.IMeta, clojure.lang.IObj, clojure.lang.IPersistentCollection, clojure.lang.IPersistentMap, clojure.lang.IReduce, clojure.lang.Indexed, clojure.lang.MapEquivalence, clojure.lang.Reversible, clojure.lang.Seqable, clojure.lang.Sorted, java.io.Serializable, java.lang.Iterable, java.util.Map

  

    

    

    
AVLMapSeq

    
type

    Fields: [_meta stack ascending? cnt _hash _hasheq]

    Protocols: 

    Interfaces: clojure.lang.Counted, clojure.lang.IHashEq, clojure.lang.IMeta, clojure.lang.IObj, clojure.lang.IPersistentCollection, clojure.lang.ISeq, clojure.lang.Seqable, clojure.lang.Sequential, java.io.Serializable, java.util.List

  

    

    

    
AVLNode

    
type

    Fields: [edit key val left right height rank]

    Protocols: 

    Interfaces: clojure.data.avl.IAVLNode, clojure.lang.Associative, clojure.lang.Counted, clojure.lang.IEditableCollection, clojure.lang.IFn, clojure.lang.IHashEq, clojure.lang.ILookup, clojure.lang.IMapEntry, clojure.lang.IMeta, clojure.lang.IObj, clojure.lang.IPersistentCollection, clojure.lang.IPersistentStack, clojure.lang.IPersistentVector, clojure.lang.Indexed, clojure.lang.Reversible, clojure.lang.Seqable, clojure.lang.Sequential, java.io.Serializable, java.lang.Comparable, java.lang.Iterable, java.util.Collection, java.util.List, java.util.Map$Entry, java.util.RandomAccess

  

    

    

    
AVLSet

    
type

    Fields: [_meta avl-map _hash _hasheq]

    Protocols: 

    Interfaces: clojure.data.avl.IAVLTree, clojure.data.avl.INavigableTree, clojure.lang.Counted, clojure.lang.IEditableCollection, clojure.lang.IFn, clojure.lang.IHashEq, clojure.lang.ILookup, clojure.lang.IMeta, clojure.lang.IObj, clojure.lang.IPersistentCollection, clojure.lang.IPersistentSet, clojure.lang.IReduce, clojure.lang.Indexed, clojure.lang.Reversible, clojure.lang.Seqable, clojure.lang.Sorted, java.io.Serializable, java.util.Set

  

    

    

    
AVLTransientMap

    
type

    Fields: [edit comp tree cnt]

    Protocols: 

    Interfaces: clojure.data.avl.ITransientAssociative2Impl, clojure.lang.Counted, clojure.lang.IFn, clojure.lang.ILookup, clojure.lang.ITransientAssociative, clojure.lang.ITransientCollection, clojure.lang.ITransientMap

  

    

    

    
AVLTransientSet

    
type

    Fields: [transient-avl-map]

    Protocols: 

    Interfaces: clojure.lang.Counted, clojure.lang.IFn, clojure.lang.ITransientCollection, clojure.lang.ITransientSet

  





  
  
Public Variables and Functions

  

    

    

    
nearest

    
function
Usage: (nearest coll test x)


    
(alpha)

Equivalent to, but more efficient than, (first (subseq* coll test x)),
where subseq* is clojure.core/subseq for test in #{>, >=} and
clojure.core/rsubseq for test in #{<, <=}.

    

    
Added in data.avl version 0.0.12

    
    Source
  

    

    

    
rank-of

    
function
Usage: (rank-of coll x)


    
Returns the rank of x in coll or -1 if not present.

    

    
Added in data.avl version 0.0.6

    
    Source
  

    

    

    
sorted-map

    
function
Usage: (sorted-map & keyvals)


    
keyval => key val
Returns a new AVL map with supplied mappings.

    

    
Added in data.avl version 0.0.1

    
    Source
  

    

    

    
sorted-map-by

    
function
Usage: (sorted-map-by comparator & keyvals)


    
keyval => key val
Returns a new sorted map with supplied mappings, using the supplied
comparator.

    

    
Added in data.avl version 0.0.1

    
    Source
  

    

    

    
sorted-set

    
function
Usage: (sorted-set & keys)


    
Returns a new sorted set with supplied keys.

    

    
Added in data.avl version 0.0.1

    
    Source
  

    

    

    
sorted-set-by

    
function
Usage: (sorted-set-by comparator & keys)


    
Returns a new sorted set with supplied keys, using the supplied comparator.

    

    
Added in data.avl version 0.0.1

    
    Source
  

    

    

    
split-at

    
function
Usage: (split-at n coll)


    
(alpha)

Equivalent to, but more efficient than,
[(into (empty coll) (take n coll))
 (into (empty coll) (drop n coll))].

    

    
Added in data.avl version 0.0.12

    
    Source
  

    

    

    
split-key

    
function
Usage: (split-key k coll)


    
(alpha)

Returns [left e? right], where left and right are collections of
the same type as coll and containing, respectively, the keys below
and above k in the ordering determined by coll's comparator, while
e? is the entry at key k for maps, the stored copy of the key k for
sets, nil if coll does not contain k.

    

    
Added in data.avl version 0.0.12

    
    Source
  

    

    

    
subrange

    
function
Usage: (subrange coll test limit)
       (subrange coll start-test start end-test end)


    
(alpha)

Returns an AVL collection comprising the entries of coll between
start and end (in the sense determined by coll's comparator) in
logarithmic time. Whether the endpoints are themselves included in
the returned collection depends on the provided tests; start-test
must be either > or >=, end-test must be either < or <=.

When passed a single test and limit, subrange infers the other end
of the range from the test: > / >= mean to include items up to the
end of coll, < / <= mean to include items taken from the beginning
of coll.

(subrange coll >= start <= end) is equivalent to, but more efficient
than, (into (empty coll) (subseq coll >= start <= end)).

    

    
Added in data.avl version 0.0.12

    
    Source