API for clojure.data.avl - AVL trees 0.0.13 (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, 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.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



merge

function
Usage: (merge)
       (merge m)
       (merge m1 m2)
       (merge m1 m2 m3 & more)
(alpha)

Merges the given AVL maps which should all use the same comparator.
nil is accepted and converted into an empty AVL map. The value
returned is itself an AVL map, except in the nullary case in which
nil is returned.

In case of key collisions, mappings from maps further to the right
in the argument list take precedence.
Source


merge-with

function
Usage: (merge-with f)
       (merge-with f m)
       (merge-with f m1 m2)
       (merge-with f m1 m2 m3 & more)
(alpha)

Merges the given AVL maps which should all use the same comparator.
nil is accepted and converted into an empty AVL map. The value
returned is itself an AVL map, except in the nullary case in which
nil is returned.

Use f to combine values in case of key collisions.
Source


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


union

function
Usage: (union)
       (union s)
       (union s1 s2)
       (union s1 s2 s3 & more)
(alpha)

Computes the union of the given AVL sets which should all use the
same comparator. nil is accepted and converted into an empty AVL
set. The value returned is itself an AVL set, except in the nullary
case in which nil is returned.
Source


unsafe-join

function
Usage: (unsafe-join)
       (unsafe-join coll)
       (unsafe-join coll1 coll2)
       (unsafe-join coll1 coll2 coll3 & more)
(alpha)

ATTN: This function DOES NOT validate its inputs and WILL return
malformed results if the inputs do not satisfy the contract.

Merges or computes the union of colls. All colls must be AVL
collections of the same type using the same comparator. If collx
occurs earlier than colly among the arguments to unsafe-join,
collx's greatest element must be strictly smaller than the smallest
element of colly (in the sense determined by the comparator).
Source
Logo & site design by Tom Hickey.
Clojure auto-documentation system by Tom Faulhaber.