prefuse.util.collections
Class AbstractTreeMap

java.lang.Object
  prefuse.util.collections.AbstractTreeMap

All Implemented Interfaces:

IntSortedMap

Direct Known Subclasses:

DoubleIntTreeMap, FloatIntTreeMap, IntIntTreeMap, LongIntTreeMap, ObjectIntTreeMap

public abstract class AbstractTreeMap
extends java.lang.Object
implements IntSortedMap

Abstract base class for red-black trees that map a key value to an int value.

Author:

jeffrey heer

Nested Class Summary

static class	AbstractTreeMap.Entry
protected class	AbstractTreeMap.EntryIterator
protected class	AbstractTreeMap.KeyIterator
protected class	AbstractTreeMap.ValueIterator

Field Summary

protected boolean	allowDuplicates
protected static boolean	BLACK
protected LiteralComparator	cmp
protected int	lastOrder
protected int	modCount
protected static AbstractTreeMap.Entry	NIL
protected static boolean	RED
protected AbstractTreeMap.Entry	root
protected int	size
protected int	unique

Constructor Summary

AbstractTreeMap(LiteralComparator comparator, boolean allowDuplicates)

Method Summary

void	clear()
java.util.Comparator	comparator()
protected abstract int	compare(AbstractTreeMap.Entry e1, AbstractTreeMap.Entry e2)
boolean	containsValue(int value)
protected void	decrementSize(boolean isUnique)
protected AbstractTreeMap.Entry	find(AbstractTreeMap.Entry x)
protected AbstractTreeMap.Entry	findCeiling(AbstractTreeMap.Entry x)
protected AbstractTreeMap.Entry	findPredecessor(AbstractTreeMap.Entry x)
protected void	fixUpInsert(AbstractTreeMap.Entry x)
protected void	fixUpRemove(AbstractTreeMap.Entry x)
int	getMaximum()
int	getMedian()
int	getMinimum()
int	getUniqueCount()
protected void	incrementSize(boolean isUnique)
boolean	isAllowDuplicates()
boolean	isEmpty()
protected AbstractTreeMap.Entry	maximum(AbstractTreeMap.Entry x)
protected AbstractTreeMap.Entry	minimum(AbstractTreeMap.Entry x)
protected AbstractTreeMap.Entry	predecessor(AbstractTreeMap.Entry x)
protected void	remove(AbstractTreeMap.Entry z)
protected void	rotateLeft(AbstractTreeMap.Entry x)
protected void	rotateRight(AbstractTreeMap.Entry x)
int	size()
protected AbstractTreeMap.Entry	successor(AbstractTreeMap.Entry x)
IntIterator	valueIterator(boolean ascend)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

RED

protected static final boolean RED

See Also:

Constant Field Values

BLACK

protected static final boolean BLACK

See Also:

Constant Field Values

NIL

protected static final AbstractTreeMap.Entry NIL

cmp

protected LiteralComparator cmp

root

protected AbstractTreeMap.Entry root

allowDuplicates

protected boolean allowDuplicates

size

protected int size

unique

protected int unique

modCount

protected int modCount

lastOrder

protected int lastOrder

Constructor Detail

AbstractTreeMap

public AbstractTreeMap(LiteralComparator comparator,
                       boolean allowDuplicates)

Method Detail

isAllowDuplicates

public boolean isAllowDuplicates()

Specified by:

isAllowDuplicates in interface IntSortedMap

size

public int size()

Specified by:

size in interface IntSortedMap

See Also:

Map.size()

isEmpty

public boolean isEmpty()

Specified by:

isEmpty in interface IntSortedMap

comparator

public java.util.Comparator comparator()

Specified by:

comparator in interface IntSortedMap

See Also:

SortedMap.comparator()

clear

public void clear()

Specified by:

clear in interface IntSortedMap

See Also:

Map.clear()

getMinimum

public int getMinimum()

Specified by:

getMinimum in interface IntSortedMap

getMaximum

public int getMaximum()

Specified by:

getMaximum in interface IntSortedMap

getMedian

public int getMedian()

Specified by:

getMedian in interface IntSortedMap

getUniqueCount

public int getUniqueCount()

Specified by:

getUniqueCount in interface IntSortedMap

containsValue

public boolean containsValue(int value)

Specified by:

containsValue in interface IntSortedMap

See Also:

Map.containsValue(java.lang.Object)

valueIterator

public IntIterator valueIterator(boolean ascend)

Specified by:

valueIterator in interface IntSortedMap

incrementSize

protected void incrementSize(boolean isUnique)

decrementSize

protected void decrementSize(boolean isUnique)

compare

protected abstract int compare(AbstractTreeMap.Entry e1,
                               AbstractTreeMap.Entry e2)

find

protected AbstractTreeMap.Entry find(AbstractTreeMap.Entry x)

findPredecessor

protected AbstractTreeMap.Entry findPredecessor(AbstractTreeMap.Entry x)

findCeiling

protected AbstractTreeMap.Entry findCeiling(AbstractTreeMap.Entry x)

minimum

protected AbstractTreeMap.Entry minimum(AbstractTreeMap.Entry x)

maximum

protected AbstractTreeMap.Entry maximum(AbstractTreeMap.Entry x)

successor

protected AbstractTreeMap.Entry successor(AbstractTreeMap.Entry x)

predecessor

protected AbstractTreeMap.Entry predecessor(AbstractTreeMap.Entry x)

rotateLeft

protected void rotateLeft(AbstractTreeMap.Entry x)

rotateRight

protected void rotateRight(AbstractTreeMap.Entry x)

fixUpInsert

protected void fixUpInsert(AbstractTreeMap.Entry x)

fixUpRemove

protected void fixUpRemove(AbstractTreeMap.Entry x)

remove

protected void remove(AbstractTreeMap.Entry z)