ix.isim.util
Class LongKeyTreeMap

java.lang.Object
  ix.isim.util.LongKeyTreeMap

public class LongKeyTreeMap
extends java.lang.Object

This is a Red-Black-Tree-based implementation of a sorted map, mapping longs to objects. This class guarantees that the map will be in ascending key order and the Iterator returned by values() will list the values (not the keys) in ascending key order.

This implementation provides guaranteed log(n) time cost for the containsKey(...), get(...), put(...) and remove(...) operations. Algorithms are adaptations of those in Cormen, Leiserson, and Rivest's Introduction to Algorithms.

This implementation should essentially behave like the one in the java.util package. The main difference is that keys are longs here which are not ojbects. The use of longs rather than Doubles greatly improves the efficiency of the implementation.

Nested Class Summary

(package private) static class	LongKeyTreeMap.Entry A node in the tree.
(package private) class	LongKeyTreeMap.LongKeyTreeMapIterator

Field Summary

protected LongKeyTreeMap.Entry

root the root of the tree

Constructor Summary

LongKeyTreeMap()
This constructor creates a new, empty map.

Method Summary

void	clear() This function removes all mappings from this map.
protected java.lang.Object	clone() This class does not support cloning and an exception will be thrown if this method is called.
boolean	containsKey(long key) This function returns true if this map contains a mapping for the specified key.
long	firstKey() This function returns the first (lowest) key currently in this sorted map.
java.lang.Object	get(long key) This function returns the value to which this map maps the specified key.
long	lastKey() This function returns the last (highest) key currently in this sorted map.
java.lang.Object	put(long key, java.lang.Object value) This function associates the specified value with the specified key in this map.
java.lang.Object	remove(long key) This function removes the mapping for this key from this map if it was present.
int	size() This function returns the number of key-value mappings in this map.
java.util.Iterator	values() This function returns an iterator for the objects in this map.

Methods inherited from class java.lang.Object

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

Field Detail

root

protected LongKeyTreeMap.Entry root

the root of the tree

Constructor Detail

LongKeyTreeMap

public LongKeyTreeMap()

This constructor creates a new, empty map.

Method Detail

clone

protected java.lang.Object clone()
                          throws java.lang.CloneNotSupportedException

This class does not support cloning and an exception will be thrown if this method is called.

Overrides:

clone in class java.lang.Object

Returns:

nothing

Throws:

java.lang.CloneNotSupportedException - will be thrown

size

public int size()

This function returns the number of key-value mappings in this map.

Returns:

the number of key-value mappings in this map

containsKey

public boolean containsKey(long key)

This function returns true if this map contains a mapping for the specified key.

Parameters:

key - the key whose presence in this map is to be tested

Returns:

true if this map contains a mapping for the specified key

get

public java.lang.Object get(long key)

This function returns the value to which this map maps the specified key. It returns null if the map contains no mapping for this key. A return value of null does not necessarily indicate that the map contains no mapping for the key; it's also possible that the map explicitly maps the key to null. The containsKey(...) operation may be used to distinguish these two cases.

Parameters:

key - key whose associated value is to be returned

Returns:

the value to which this map maps the specified key, or null if the map contains no mapping for the key

firstKey

public long firstKey()
              throws java.util.NoSuchElementException

This function returns the first (lowest) key currently in this sorted map.

Returns:

the first (lowest) key currently in this sorted map

Throws:

NoSuchElementException - if the map is empty

lastKey

public long lastKey()
             throws java.util.NoSuchElementException

This function returns the last (highest) key currently in this sorted map.

Returns:

the last (highest) key currently in this sorted map

Throws:

NoSuchElementException - if the map is empty

put

public java.lang.Object put(long key,
                            java.lang.Object value)

This function associates the specified value with the specified key in this map. If the map previously contained a mapping for this key, the old value is replaced. A null return may indicate that the map previously associated null with the specified key.

Parameters:

key - the key with which the specified value is to be associated

value - the value to be associated with the specified key

Returns:

previous value associated with specified key, or null if there was no mapping for the key

remove

public java.lang.Object remove(long key)

This function removes the mapping for this key from this map if it was present. A null return may indicate that the map previously associated null with the specified key.

Parameters:

key - the key to the mapping that is to be removed

Returns:

the previous value associated with specified key, or null if there was no mapping for the key

clear

public void clear()

This function removes all mappings from this map.

values

public java.util.Iterator values()

This function returns an iterator for the objects in this map. They will be returned in the (ascending) order of their keys.

Returns:

an ordered Iterator of the values (not keys) in this map