clojure.lang

Class PersistentTreeMap

java.lang.Object

clojure.lang.AFn

clojure.lang.APersistentMap

clojure.lang.PersistentTreeMap

All Implemented Interfaces:

Associative, Counted, IFn, IHashEq, ILookup, IMeta, IObj, IPersistentCollection, IPersistentMap, MapEquivalence, Reversible, Seqable, Sorted, java.io.Serializable, java.lang.Iterable, java.lang.Runnable, java.util.concurrent.Callable, java.util.Map

public class PersistentTreeMap
extends APersistentMap
implements IObj, Reversible, Sorted

Persistent Red Black Tree Note that instances of this class are constant values i.e. add/remove etc return new values

See Okasaki, Kahrs, Larsen et al

See Also:

Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
(package private) static class	PersistentTreeMap.Black
(package private) static class	PersistentTreeMap.BlackBranch
(package private) static class	PersistentTreeMap.BlackBranchVal
(package private) static class	PersistentTreeMap.BlackVal
(package private) static class	PersistentTreeMap.KeyIterator
(package private) static class	PersistentTreeMap.Node
static class	PersistentTreeMap.NodeIterator
(package private) static class	PersistentTreeMap.Red
(package private) static class	PersistentTreeMap.RedBranch
(package private) static class	PersistentTreeMap.RedBranchVal
(package private) static class	PersistentTreeMap.RedVal
static class	PersistentTreeMap.Seq
(package private) static class	PersistentTreeMap.ValIterator

Nested classes/interfaces inherited from class clojure.lang.APersistentMap

APersistentMap.KeySeq, APersistentMap.ValSeq

Nested classes/interfaces inherited from interface java.util.Map

java.util.Map.Entry<K,V>

Nested classes/interfaces inherited from interface clojure.lang.IFn

IFn.D, IFn.DD, IFn.DDD, IFn.DDDD, IFn.DDDDD, IFn.DDDDL, IFn.DDDDO, IFn.DDDL, IFn.DDDLD, IFn.DDDLL, IFn.DDDLO, IFn.DDDO, IFn.DDDOD, IFn.DDDOL, IFn.DDDOO, IFn.DDL, IFn.DDLD, IFn.DDLDD, IFn.DDLDL, IFn.DDLDO, IFn.DDLL, IFn.DDLLD, IFn.DDLLL, IFn.DDLLO, IFn.DDLO, IFn.DDLOD, IFn.DDLOL, IFn.DDLOO, IFn.DDO, IFn.DDOD, IFn.DDODD, IFn.DDODL, IFn.DDODO, IFn.DDOL, IFn.DDOLD, IFn.DDOLL, IFn.DDOLO, IFn.DDOO, IFn.DDOOD, IFn.DDOOL, IFn.DDOOO, IFn.DL, IFn.DLD, IFn.DLDD, IFn.DLDDD, IFn.DLDDL, IFn.DLDDO, IFn.DLDL, IFn.DLDLD, IFn.DLDLL, IFn.DLDLO, IFn.DLDO, IFn.DLDOD, IFn.DLDOL, IFn.DLDOO, IFn.DLL, IFn.DLLD, IFn.DLLDD, IFn.DLLDL, IFn.DLLDO, IFn.DLLL, IFn.DLLLD, IFn.DLLLL, IFn.DLLLO, IFn.DLLO, IFn.DLLOD, IFn.DLLOL, IFn.DLLOO, IFn.DLO, IFn.DLOD, IFn.DLODD, IFn.DLODL, IFn.DLODO, IFn.DLOL, IFn.DLOLD, IFn.DLOLL, IFn.DLOLO, IFn.DLOO, IFn.DLOOD, IFn.DLOOL, IFn.DLOOO, IFn.DO, IFn.DOD, IFn.DODD, IFn.DODDD, IFn.DODDL, IFn.DODDO, IFn.DODL, IFn.DODLD, IFn.DODLL, IFn.DODLO, IFn.DODO, IFn.DODOD, IFn.DODOL, IFn.DODOO, IFn.DOL, IFn.DOLD, IFn.DOLDD, IFn.DOLDL, IFn.DOLDO, IFn.DOLL, IFn.DOLLD, IFn.DOLLL, IFn.DOLLO, IFn.DOLO, IFn.DOLOD, IFn.DOLOL, IFn.DOLOO, IFn.DOO, IFn.DOOD, IFn.DOODD, IFn.DOODL, IFn.DOODO, IFn.DOOL, IFn.DOOLD, IFn.DOOLL, IFn.DOOLO, IFn.DOOO, IFn.DOOOD, IFn.DOOOL, IFn.DOOOO, IFn.L, IFn.LD, IFn.LDD, IFn.LDDD, IFn.LDDDD, IFn.LDDDL, IFn.LDDDO, IFn.LDDL, IFn.LDDLD, IFn.LDDLL, IFn.LDDLO, IFn.LDDO, IFn.LDDOD, IFn.LDDOL, IFn.LDDOO, IFn.LDL, IFn.LDLD, IFn.LDLDD, IFn.LDLDL, IFn.LDLDO, IFn.LDLL, IFn.LDLLD, IFn.LDLLL, IFn.LDLLO, IFn.LDLO, IFn.LDLOD, IFn.LDLOL, IFn.LDLOO, IFn.LDO, IFn.LDOD, IFn.LDODD, IFn.LDODL, IFn.LDODO, IFn.LDOL, IFn.LDOLD, IFn.LDOLL, IFn.LDOLO, IFn.LDOO, IFn.LDOOD, IFn.LDOOL, IFn.LDOOO, IFn.LL, IFn.LLD, IFn.LLDD, IFn.LLDDD, IFn.LLDDL, IFn.LLDDO, IFn.LLDL, IFn.LLDLD, IFn.LLDLL, IFn.LLDLO, IFn.LLDO, IFn.LLDOD, IFn.LLDOL, IFn.LLDOO, IFn.LLL, IFn.LLLD, IFn.LLLDD, IFn.LLLDL, IFn.LLLDO, IFn.LLLL, IFn.LLLLD, IFn.LLLLL, IFn.LLLLO, IFn.LLLO, IFn.LLLOD, IFn.LLLOL, IFn.LLLOO, IFn.LLO, IFn.LLOD, IFn.LLODD, IFn.LLODL, IFn.LLODO, IFn.LLOL, IFn.LLOLD, IFn.LLOLL, IFn.LLOLO, IFn.LLOO, IFn.LLOOD, IFn.LLOOL, IFn.LLOOO, IFn.LO, IFn.LOD, IFn.LODD, IFn.LODDD, IFn.LODDL, IFn.LODDO, IFn.LODL, IFn.LODLD, IFn.LODLL, IFn.LODLO, IFn.LODO, IFn.LODOD, IFn.LODOL, IFn.LODOO, IFn.LOL, IFn.LOLD, IFn.LOLDD, IFn.LOLDL, IFn.LOLDO, IFn.LOLL, IFn.LOLLD, IFn.LOLLL, IFn.LOLLO, IFn.LOLO, IFn.LOLOD, IFn.LOLOL, IFn.LOLOO, IFn.LOO, IFn.LOOD, IFn.LOODD, IFn.LOODL, IFn.LOODO, IFn.LOOL, IFn.LOOLD, IFn.LOOLL, IFn.LOOLO, IFn.LOOO, IFn.LOOOD, IFn.LOOOL, IFn.LOOOO, IFn.OD, IFn.ODD, IFn.ODDD, IFn.ODDDD, IFn.ODDDL, IFn.ODDDO, IFn.ODDL, IFn.ODDLD, IFn.ODDLL, IFn.ODDLO, IFn.ODDO, IFn.ODDOD, IFn.ODDOL, IFn.ODDOO, IFn.ODL, IFn.ODLD, IFn.ODLDD, IFn.ODLDL, IFn.ODLDO, IFn.ODLL, IFn.ODLLD, IFn.ODLLL, IFn.ODLLO, IFn.ODLO, IFn.ODLOD, IFn.ODLOL, IFn.ODLOO, IFn.ODO, IFn.ODOD, IFn.ODODD, IFn.ODODL, IFn.ODODO, IFn.ODOL, IFn.ODOLD, IFn.ODOLL, IFn.ODOLO, IFn.ODOO, IFn.ODOOD, IFn.ODOOL, IFn.ODOOO, IFn.OL, IFn.OLD, IFn.OLDD, IFn.OLDDD, IFn.OLDDL, IFn.OLDDO, IFn.OLDL, IFn.OLDLD, IFn.OLDLL, IFn.OLDLO, IFn.OLDO, IFn.OLDOD, IFn.OLDOL, IFn.OLDOO, IFn.OLL, IFn.OLLD, IFn.OLLDD, IFn.OLLDL, IFn.OLLDO, IFn.OLLL, IFn.OLLLD, IFn.OLLLL, IFn.OLLLO, IFn.OLLO, IFn.OLLOD, IFn.OLLOL, IFn.OLLOO, IFn.OLO, IFn.OLOD, IFn.OLODD, IFn.OLODL, IFn.OLODO, IFn.OLOL, IFn.OLOLD, IFn.OLOLL, IFn.OLOLO, IFn.OLOO, IFn.OLOOD, IFn.OLOOL, IFn.OLOOO, IFn.OOD, IFn.OODD, IFn.OODDD, IFn.OODDL, IFn.OODDO, IFn.OODL, IFn.OODLD, IFn.OODLL, IFn.OODLO, IFn.OODO, IFn.OODOD, IFn.OODOL, IFn.OODOO, IFn.OOL, IFn.OOLD, IFn.OOLDD, IFn.OOLDL, IFn.OOLDO, IFn.OOLL, IFn.OOLLD, IFn.OOLLL, IFn.OOLLO, IFn.OOLO, IFn.OOLOD, IFn.OOLOL, IFn.OOLOO, IFn.OOOD, IFn.OOODD, IFn.OOODL, IFn.OOODO, IFn.OOOL, IFn.OOOLD, IFn.OOOLL, IFn.OOOLO, IFn.OOOOD, IFn.OOOOL

Field Summary

Fields

Modifier and Type	Field and Description
int	_count
(package private) IPersistentMap	_meta
java.util.Comparator	comp
static PersistentTreeMap	EMPTY
PersistentTreeMap.Node	tree

Fields inherited from class clojure.lang.APersistentMap

_hash, _hasheq

Constructor Summary

Constructors

Modifier	Constructor and Description
	PersistentTreeMap()
private	PersistentTreeMap(java.util.Comparator comp)
(package private)	PersistentTreeMap(java.util.Comparator comp, PersistentTreeMap.Node tree, int count, IPersistentMap meta)
	PersistentTreeMap(IPersistentMap meta, java.util.Comparator comp)
(package private)	PersistentTreeMap(IPersistentMap meta, java.util.Comparator comp, PersistentTreeMap.Node tree, int _count)

Method Summary

Methods

Modifier and Type	Method and Description
(package private) PersistentTreeMap.Node	add(PersistentTreeMap.Node t, java.lang.Object key, java.lang.Object val, Box found)
(package private) static PersistentTreeMap.Node	append(PersistentTreeMap.Node left, PersistentTreeMap.Node right)
PersistentTreeMap	assoc(java.lang.Object key, java.lang.Object val)
PersistentTreeMap	assocEx(java.lang.Object key, java.lang.Object val)
(package private) static PersistentTreeMap.Node	balanceLeftDel(java.lang.Object key, java.lang.Object val, PersistentTreeMap.Node del, PersistentTreeMap.Node right)
(package private) static PersistentTreeMap.Node	balanceRightDel(java.lang.Object key, java.lang.Object val, PersistentTreeMap.Node left, PersistentTreeMap.Node del)
(package private) static PersistentTreeMap.Black	black(java.lang.Object key, java.lang.Object val, PersistentTreeMap.Node left, PersistentTreeMap.Node right)
int	capacity()
java.util.Comparator	comparator()
boolean	containsKey(java.lang.Object key)
int	count()
static PersistentTreeMap	create(java.util.Comparator comp, ISeq items)
static PersistentTreeMap	create(ISeq items)
static IPersistentMap	create(java.util.Map other)
int	depth()
(package private) int	depth(PersistentTreeMap.Node t)
int	doCompare(java.lang.Object k1, java.lang.Object k2)
IPersistentCollection	empty()
PersistentTreeMap.Node	entryAt(java.lang.Object key)
java.lang.Object	entryKey(java.lang.Object entry)
PersistentTreeMap.NodeIterator	iterator()
java.util.Iterator	keys()
java.util.Iterator	keys(PersistentTreeMap.NodeIterator it)
java.lang.Object	kvreduce(IFn f, java.lang.Object init)
(package private) static PersistentTreeMap.Node	leftBalance(java.lang.Object key, java.lang.Object val, PersistentTreeMap.Node ins, PersistentTreeMap.Node right)
PersistentTreeMap.Node	max()
java.lang.Object	maxKey()
IPersistentMap	meta()
PersistentTreeMap.Node	min()
java.lang.Object	minKey()
(package private) static PersistentTreeMap.Red	red(java.lang.Object key, java.lang.Object val, PersistentTreeMap.Node left, PersistentTreeMap.Node right)
(package private) PersistentTreeMap.Node	remove(PersistentTreeMap.Node t, java.lang.Object key, Box found)
(package private) PersistentTreeMap.Node	replace(PersistentTreeMap.Node t, java.lang.Object key, java.lang.Object val)
PersistentTreeMap.NodeIterator	reverseIterator()
(package private) static PersistentTreeMap.Node	rightBalance(java.lang.Object key, java.lang.Object val, PersistentTreeMap.Node left, PersistentTreeMap.Node ins)
ISeq	rseq()
ISeq	seq()
ISeq	seq(boolean ascending)
ISeq	seqFrom(java.lang.Object key, boolean ascending)
java.lang.Object	valAt(java.lang.Object key)
java.lang.Object	valAt(java.lang.Object key, java.lang.Object notFound)
java.util.Iterator	vals()
java.util.Iterator	vals(PersistentTreeMap.NodeIterator it)
PersistentTreeMap	withMeta(IPersistentMap meta)
PersistentTreeMap	without(java.lang.Object key)

Methods inherited from class clojure.lang.APersistentMap

clear, cons, containsValue, entrySet, equals, equiv, get, hashCode, hasheq, invoke, invoke, isEmpty, keySet, mapEquals, mapHash, mapHasheq, put, putAll, remove, size, toString, values

Methods inherited from class clojure.lang.AFn

applyTo, applyToHelper, call, invoke, invoke, invoke, invoke, invoke, invoke, invoke, invoke, invoke, invoke, invoke, invoke, invoke, invoke, invoke, invoke, invoke, invoke, invoke, invoke, run, throwArity

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Field Detail

comp

public final java.util.Comparator comp

tree

public final PersistentTreeMap.Node tree

_count

public final int _count

_meta

final IPersistentMap _meta

EMPTY

public static final PersistentTreeMap EMPTY

Constructor Detail

PersistentTreeMap

public PersistentTreeMap()

PersistentTreeMap

private PersistentTreeMap(java.util.Comparator comp)

PersistentTreeMap

public PersistentTreeMap(IPersistentMap meta,
                 java.util.Comparator comp)

PersistentTreeMap

PersistentTreeMap(IPersistentMap meta,
                 java.util.Comparator comp,
                 PersistentTreeMap.Node tree,
                 int _count)

PersistentTreeMap

PersistentTreeMap(java.util.Comparator comp,
                 PersistentTreeMap.Node tree,
                 int count,
                 IPersistentMap meta)

Method Detail

create

public static IPersistentMap create(java.util.Map other)

withMeta

public PersistentTreeMap withMeta(IPersistentMap meta)

Specified by:

withMeta in interface IObj

create

public static PersistentTreeMap create(ISeq items)

create

public static PersistentTreeMap create(java.util.Comparator comp,
                       ISeq items)

containsKey

public boolean containsKey(java.lang.Object key)

Specified by:

containsKey in interface Associative

Specified by:

containsKey in interface java.util.Map

assocEx

public PersistentTreeMap assocEx(java.lang.Object key,
                        java.lang.Object val)

Specified by:

assocEx in interface IPersistentMap

assoc

public PersistentTreeMap assoc(java.lang.Object key,
                      java.lang.Object val)

Specified by:

assoc in interface Associative

Specified by:

assoc in interface IPersistentMap

without

public PersistentTreeMap without(java.lang.Object key)

Specified by:

without in interface IPersistentMap

seq

public ISeq seq()

Specified by:

seq in interface Seqable

empty

public IPersistentCollection empty()

Specified by:

empty in interface IPersistentCollection

rseq

public ISeq rseq()

Specified by:

rseq in interface Reversible

comparator

public java.util.Comparator comparator()

Specified by:

comparator in interface Sorted

entryKey

public java.lang.Object entryKey(java.lang.Object entry)

Specified by:

entryKey in interface Sorted

seq

public ISeq seq(boolean ascending)

Specified by:

seq in interface Sorted

seqFrom

public ISeq seqFrom(java.lang.Object key,
           boolean ascending)

Specified by:

seqFrom in interface Sorted

iterator

public PersistentTreeMap.NodeIterator iterator()

Specified by:

iterator in interface java.lang.Iterable

kvreduce

public java.lang.Object kvreduce(IFn f,
                        java.lang.Object init)

reverseIterator

public PersistentTreeMap.NodeIterator reverseIterator()

keys

public java.util.Iterator keys()

vals

public java.util.Iterator vals()

keys

public java.util.Iterator keys(PersistentTreeMap.NodeIterator it)

vals

public java.util.Iterator vals(PersistentTreeMap.NodeIterator it)

minKey

public java.lang.Object minKey()

min

public PersistentTreeMap.Node min()

maxKey

public java.lang.Object maxKey()

max

public PersistentTreeMap.Node max()

depth

public int depth()

depth

int depth(PersistentTreeMap.Node t)

valAt

public java.lang.Object valAt(java.lang.Object key,
                     java.lang.Object notFound)

Specified by:

valAt in interface ILookup

valAt

public java.lang.Object valAt(java.lang.Object key)

Specified by:

valAt in interface ILookup

capacity

public int capacity()

count

public int count()

Specified by:

count in interface Counted

Specified by:

count in interface IPersistentCollection

entryAt

public PersistentTreeMap.Node entryAt(java.lang.Object key)

Specified by:

entryAt in interface Associative

doCompare

public int doCompare(java.lang.Object k1,
            java.lang.Object k2)

add

PersistentTreeMap.Node add(PersistentTreeMap.Node t,
                         java.lang.Object key,
                         java.lang.Object val,
                         Box found)

remove

PersistentTreeMap.Node remove(PersistentTreeMap.Node t,
                            java.lang.Object key,
                            Box found)

append

static PersistentTreeMap.Node append(PersistentTreeMap.Node left,
                            PersistentTreeMap.Node right)

balanceLeftDel

static PersistentTreeMap.Node balanceLeftDel(java.lang.Object key,
                                    java.lang.Object val,
                                    PersistentTreeMap.Node del,
                                    PersistentTreeMap.Node right)

balanceRightDel

static PersistentTreeMap.Node balanceRightDel(java.lang.Object key,
                                     java.lang.Object val,
                                     PersistentTreeMap.Node left,
                                     PersistentTreeMap.Node del)

leftBalance

static PersistentTreeMap.Node leftBalance(java.lang.Object key,
                                 java.lang.Object val,
                                 PersistentTreeMap.Node ins,
                                 PersistentTreeMap.Node right)

rightBalance

static PersistentTreeMap.Node rightBalance(java.lang.Object key,
                                  java.lang.Object val,
                                  PersistentTreeMap.Node left,
                                  PersistentTreeMap.Node ins)

replace

PersistentTreeMap.Node replace(PersistentTreeMap.Node t,
                             java.lang.Object key,
                             java.lang.Object val)

red

static PersistentTreeMap.Red red(java.lang.Object key,
                        java.lang.Object val,
                        PersistentTreeMap.Node left,
                        PersistentTreeMap.Node right)

black

static PersistentTreeMap.Black black(java.lang.Object key,
                            java.lang.Object val,
                            PersistentTreeMap.Node left,
                            PersistentTreeMap.Node right)

meta

public IPersistentMap meta()

Specified by:

meta in interface IMeta