org.bolson
Class SplayMap

java.lang.Object
  org.bolson.SplayMap

All Implemented Interfaces:

java.io.Serializable, java.util.Map, java.util.SortedMap

public class SplayMap
extends java.lang.Object
implements java.util.SortedMap, java.io.Serializable

See Also:

Serialized Form

Nested Class Summary

protected class	SplayMap.SMCollection
protected class	SplayMap.SMKeySet
protected static class	SplayMap.SMNode
protected class	SplayMap.SMNodeSet
protected class	SplayMap.SMSIterator

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

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

Field Summary

protected static int	RETURN_KEY
protected static int	RETURN_NODE
protected static int	RETURN_VALUE

Constructor Summary

SplayMap()

SplayMap(java.util.Comparator cmp)

Method Summary

void	clear()
java.util.Comparator	comparator()
boolean	containsKey(java.lang.Object key)
boolean	containsValue(java.lang.Object value)
static void	doubleRotateGreaterLess(SplayMap.SMNode a, SplayMap.SMNode b, SplayMap.SMNode c)
static void	doubleRotateLeft(SplayMap.SMNode a, SplayMap.SMNode b, SplayMap.SMNode c)
static void	doubleRotateLessGreater(SplayMap.SMNode a, SplayMap.SMNode b, SplayMap.SMNode c)
static void	doubleRotateRight(SplayMap.SMNode a, SplayMap.SMNode b, SplayMap.SMNode c)
java.util.Set	entrySet()
java.lang.Object	firstKey()
protected SplayMap.SMNode	firstNode()
java.lang.Object	get(java.lang.Object key)
protected SplayMap.SMNode	getNode(java.lang.Object key)
java.util.SortedMap	headMap(java.lang.Object toKey)
boolean	isEmpty()
java.util.Set	keySet()
java.lang.Object	lastKey()
protected SplayMap.SMNode	lastNode()
java.lang.Object	put(java.lang.Object key, java.lang.Object value)
void	putAll(java.util.Map m)
java.lang.Object	remove(java.lang.Object key)
protected java.lang.Object	removeNode(SplayMap.SMNode cur)
static void	rotateLeft(SplayMap.SMNode a, SplayMap.SMNode b) a is parent of greater b b to top
static void	rotateRight(SplayMap.SMNode a, SplayMap.SMNode b) a is lesser child of b a to top
int	size()
protected void	splayUp(SplayMap.SMNode it)
java.util.SortedMap	subMap(java.lang.Object fromKey, java.lang.Object toKey)
java.util.SortedMap	tailMap(java.lang.Object fromKey)
java.util.Collection	values()

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.util.Map

equals, hashCode

Field Detail

RETURN_NODE

protected static final int RETURN_NODE

See Also:

Constant Field Values

RETURN_KEY

protected static final int RETURN_KEY

See Also:

Constant Field Values

RETURN_VALUE

protected static final int RETURN_VALUE

See Also:

Constant Field Values

Constructor Detail

SplayMap

public SplayMap()

SplayMap

public SplayMap(java.util.Comparator cmp)

Method Detail

size

public int size()

Specified by:

size in interface java.util.Map

isEmpty

public boolean isEmpty()

Specified by:

isEmpty in interface java.util.Map

containsKey

public boolean containsKey(java.lang.Object key)

Specified by:

containsKey in interface java.util.Map

containsValue

public boolean containsValue(java.lang.Object value)

Specified by:

containsValue in interface java.util.Map

clear

public void clear()

Specified by:

clear in interface java.util.Map

get

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

Specified by:

get in interface java.util.Map

put

public java.lang.Object put(java.lang.Object key,
                            java.lang.Object value)
                     throws java.lang.IllegalArgumentException

Specified by:

put in interface java.util.Map

Throws:

java.lang.IllegalArgumentException

putAll

public void putAll(java.util.Map m)

Specified by:

putAll in interface java.util.Map

removeNode

protected java.lang.Object removeNode(SplayMap.SMNode cur)

remove

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

Specified by:

remove in interface java.util.Map

entrySet

public java.util.Set entrySet()

Specified by:

entrySet in interface java.util.Map

keySet

public java.util.Set keySet()

Specified by:

keySet in interface java.util.Map

values

public java.util.Collection values()

Specified by:

values in interface java.util.Map

comparator

public java.util.Comparator comparator()

Specified by:

comparator in interface java.util.SortedMap

firstNode

protected SplayMap.SMNode firstNode()

firstKey

public java.lang.Object firstKey()

Specified by:

firstKey in interface java.util.SortedMap

headMap

public java.util.SortedMap headMap(java.lang.Object toKey)

Specified by:

headMap in interface java.util.SortedMap

lastNode

protected SplayMap.SMNode lastNode()

lastKey

public java.lang.Object lastKey()

Specified by:

lastKey in interface java.util.SortedMap

subMap

public java.util.SortedMap subMap(java.lang.Object fromKey,
                                  java.lang.Object toKey)

Specified by:

subMap in interface java.util.SortedMap

tailMap

public java.util.SortedMap tailMap(java.lang.Object fromKey)

Specified by:

tailMap in interface java.util.SortedMap

splayUp

protected void splayUp(SplayMap.SMNode it)

rotateRight

public static void rotateRight(SplayMap.SMNode a,
                               SplayMap.SMNode b)

a is lesser child of b a to top

rotateLeft

public static void rotateLeft(SplayMap.SMNode a,
                              SplayMap.SMNode b)

a is parent of greater b b to top

doubleRotateRight

public static void doubleRotateRight(SplayMap.SMNode a,
                                     SplayMap.SMNode b,
                                     SplayMap.SMNode c)

doubleRotateLeft

public static void doubleRotateLeft(SplayMap.SMNode a,
                                    SplayMap.SMNode b,
                                    SplayMap.SMNode c)

doubleRotateLessGreater

public static void doubleRotateLessGreater(SplayMap.SMNode a,
                                           SplayMap.SMNode b,
                                           SplayMap.SMNode c)

doubleRotateGreaterLess

public static void doubleRotateGreaterLess(SplayMap.SMNode a,
                                           SplayMap.SMNode b,
                                           SplayMap.SMNode c)

getNode

protected SplayMap.SMNode getNode(java.lang.Object key)