API for clojure.data.avl - AVL trees 0.0.12 (in development)

by MichaƂ Marczyk

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.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, java.io.Serializable


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.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.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 #{<, <=}.
Source


rank-of

function
Usage: (rank-of coll x)
Returns the rank of x in coll or -1 if not present.
Source


sorted-map

function
Usage: (sorted-map & keyvals)
keyval => key val
Returns a new AVL map with supplied mappings.
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.
Source


sorted-set

function
Usage: (sorted-set & keys)
Returns a new sorted set with supplied keys.
Source


sorted-set-by

function
Usage: (sorted-set-by comparator & keys)
Returns a new sorted set with supplied keys, using the supplied comparator.
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))].
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.
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 >= start <= end) is equivalent to, but more efficient
than, (into (empty coll) (subseq coll >= start <= end).
Source
Logo & site design by Tom Hickey.
Clojure auto-documentation system by Tom Faulhaber.