inf.util
Class IntKeyTreeMap<E>

java.lang.Object
  inf.util.IntKeyTreeMap<E>

Type Parameters:

E - the element type for the values to which the keys are mapped

All Implemented Interfaces:

IntKeyMap<E>, java.lang.Cloneable, java.lang.Iterable<IntKeyTreeMap.IntKeyTreeEntry<E>>, java.util.Map<java.lang.Integer,E>, java.util.SortedMap<java.lang.Integer,E>

public class IntKeyTreeMap<E>
extends java.lang.Object
implements java.lang.Cloneable, IntKeyMap<E>, java.util.SortedMap<java.lang.Integer,E>, java.lang.Iterable<IntKeyTreeMap.IntKeyTreeEntry<E>>

This is a Red-Black-Tree-based implementation of a SortedMap, mapping ints (keys) to Objects (values). If the key is given as an Integer rather than an int, it must not be null. Values are allowed to be null. This class guarantees that the Map will be in ascending key order and the Iterator returned by iterator() will list the IntKeyEntrys contained in this Map 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 ints here which are not Objects. The use of ints rather than Integers improves the efficiency of the implementation (very roughly by a factor of 2).

Important: The functions that should give a collection view of this Map as described in the documentation for Map do not do so in this implementation. Modifications to the returned Sets or Collection only affect the Map in a limited way, and vice versa.

Author:

Gerhard Wickler, based on the TreeMap implementation by Josh Bloch and Doug Lea

Nested Class Summary

(package private) static class	IntKeyTreeMap.IntKeyTreeEntry<E>
(package private) class	IntKeyTreeMap.IntKeyTreeMapIterator<T>

Nested classes/interfaces inherited from interface inf.util.IntKeyMap

IntKeyMap.IntKeyEntry<E>

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

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

Field Summary

protected IntKeyTreeMap.IntKeyTreeEntry<E>

root the root of the tree

Constructor Summary

IntKeyTreeMap()
This constructor creates a new, empty IntKeyTreeMap.

IntKeyTreeMap(java.util.Map<? extends java.lang.Integer,? extends E> map)
This constructor creates a new IntKeyTreeMap that contains all the associations from the given map.

Method Summary

void	clear() This function removes all mappings from this Map.
IntKeyTreeMap<E>	clone() This function returns a shallow copy of this IntKeyTreeMap.
java.util.Comparator<? super java.lang.Integer>	comparator() This function throws an UnsupportedOperationException.
boolean	containsKey(int key) This function returns true if this IntKeyMap contains a mapping for the specified key, which is an int here.
boolean	containsKey(java.lang.Object key) This function returns true if this Map contains a mapping for the specified key.
boolean	containsValue(java.lang.Object value) This function returns true if this Map contains an Entry containing the specified value.
java.util.Set<java.util.Map.Entry<java.lang.Integer,E>>	entrySet() This function returns a Set of all the IntKeyEntrys contained in this Map.
boolean	equals(IntKeyMap<E> imap) This function tests whether the this and the given IntKeyMap do map the same keys to equal values.
boolean	equals(java.lang.Object o) This function tests whether this and the given Object are equal.
int	firstIntKey() This function returns the first (lowest) key currently in this SortedMap.
java.lang.Integer	firstKey() This function returns the first (lowest) key currently in this SortedMap.
E	get(int key) This function returns the value to which this IntKeyMap maps the specified key, which is an int here.
E	get(java.lang.Object key) This function returns the value to which this Map maps the specified key.
int	hashCode() This function computes a hash value for this IntKeyTreeMap.
java.util.SortedMap<java.lang.Integer,E>	headMap(java.lang.Integer toKey) This function throws an UnsupportedOperationException.
boolean	isEmpty() This function tests whether this Map contains no entries.
java.util.Iterator<IntKeyTreeMap.IntKeyTreeEntry<E>>	iterator() This function returns an Iterator for the Entries in this Map.
java.util.Set<java.lang.Integer>	keySet() This function returns a Set containing all the keys contained in this Map.
int	lastIntKey() This function returns the last (highest) key currently in this SortedMap.
java.lang.Integer	lastKey() This function returns the last (highest) key currently in this SortedMap.
E	put(int key, E value) This function associates the specified key, an int, with the specified value in this IntKeyMap.
E	put(java.lang.Integer key, E value) This function associates the specified key with the specified value in this Map.
void	putAll(java.util.Map<? extends java.lang.Integer,? extends E> map) This function adds all the associations from the given Map to this Map.
E	remove(int key) This function removes the mapping for this key, an int, from this IntKeyMap if it was present.
E	remove(java.lang.Object 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.SortedMap<java.lang.Integer,E>	subMap(java.lang.Integer fromKey, java.lang.Integer toKey) This function throws an UnsupportedOperationException.
java.util.SortedMap<java.lang.Integer,E>	tailMap(java.lang.Integer fromKey) This function throws an UnsupportedOperationException.
java.lang.String	toString() This function returns a printable representation of this IntKeyMap.
java.util.Collection<E>	values() This function returns a Collection containing all the values contained in this Map.

Methods inherited from class java.lang.Object

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

Field Detail

root

protected IntKeyTreeMap.IntKeyTreeEntry<E> root

the root of the tree

Constructor Detail

IntKeyTreeMap

public IntKeyTreeMap()

This constructor creates a new, empty IntKeyTreeMap.

IntKeyTreeMap

public IntKeyTreeMap(java.util.Map<? extends java.lang.Integer,? extends E> map)

This constructor creates a new IntKeyTreeMap that contains all the associations from the given map.

Parameters:

map - the Map containing the associations to be added to this Map

Method Detail

clone

public IntKeyTreeMap<E> clone()

This function returns a shallow copy of this IntKeyTreeMap. The values themselves are not cloned. Cloning an IntKeyTreeMap is rather inefficient (time complexity in O(n), where n is the size of this Map) and is best avoided whenever possible.

Overrides:

clone in class java.lang.Object

Returns:

a shallow copy of this IntKeyTreeMap.

put

public E put(java.lang.Integer key,
             E value)

This function associates the specified key with the specified value in this Map. If the Map previously contained a mapping for this key, the old value is replaced. The old value is also used as the return value of this function. A null return may indicate that no previous association existed or that the Map previously associated null with the specified key. Note that the given key Object must not be null. The time complexity of this function is guaranteed to be in O(log(n)), where n is the size of this Map.

Specified by:

put in interface java.util.Map<java.lang.Integer,E>

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

putAll

public void putAll(java.util.Map<? extends java.lang.Integer,? extends E> map)

This function adds all the associations from the given Map to this Map. Any values for existing keys in this Map will be replaced. The time complexity of this function is in O(m log(n+m)), where m is the size of the given Map and n is the size of this Map.

Specified by:

putAll in interface java.util.Map<java.lang.Integer,E>

Parameters:

map - the Map containing the associations to be added to this Map

isEmpty

public boolean isEmpty()

This function tests whether this Map contains no entries. If this is true, the size of the Map is 0.

Specified by:

isEmpty in interface java.util.Map<java.lang.Integer,E>

Returns:

true iff this map contains no key-value mappings

size

public int size()

This function returns the number of key-value mappings in this Map. The result is a positive integer.

Specified by:

size in interface java.util.Map<java.lang.Integer,E>

Returns:

the number of key-value mappings in this Map

containsKey

public boolean containsKey(java.lang.Object key)

This function returns true if this Map contains a mapping for the specified key. Note that the given key Object must be an Integer, which must not be null. The time complexity of this function is guaranteed to be in O(log(n)), where n is the size of this Map.

Specified by:

containsKey in interface java.util.Map<java.lang.Integer,E>

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

containsValue

public boolean containsValue(java.lang.Object value)

This function returns true if this Map contains an Entry containing the specified value. The given value may be null. Note that searching for values is inefficient: the time complexity of this function is in O(n), where n is the size of this Map, i.e. it is linear in the size of the Map.

Specified by:

containsValue in interface java.util.Map<java.lang.Integer,E>

Parameters:

value - the value whose presence in this Map is to be tested

Returns:

true if this Map maps one or more keys to the given value

get

public E get(java.lang.Object 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(Object) operation may be used to distinguish these two cases. Note that the given key Object must be an Integer, but must not be null. The time complexity of this function is guaranteed to be in O(log(n)), where n is the size of this Map.

Specified by:

get in interface java.util.Map<java.lang.Integer,E>

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

keySet

public java.util.Set<java.lang.Integer> keySet()

This function returns a Set containing all the keys contained in this Map. The time and space complexity of this function is in O(n), where n is the size of this Map. In this implementation the returned Set is actually a TreeSet and the keys in it are in the same order as in this SortedMap.

Important: This function does not return a collection view of this Map as described in the documentation of the Map interface, and changes to the returned Set will not affect this Map, and vice versa. In other words, this Map and the returned Set are independent Objects.

Specified by:

keySet in interface java.util.Map<java.lang.Integer,E>

Specified by:

keySet in interface java.util.SortedMap<java.lang.Integer,E>

Returns:

a Set of all keys in this Map

values

public java.util.Collection<E> values()

This function returns a Collection containing all the values contained in this Map. Note that the Collection may contain duplicates. The time and space complexity of this function is in O(n), where n is the size of this Map. In this implementation the returned Collection is actually a LinkedList and the values in it are in the same order as in this SortedMap.

Important: This function does not return a collection view of this Map as described in the documentation of the Map interface, and changes to the returned Collection will not affect this Map, and vice versa. In other words, this Map and the returned Collection are independent Objects. However the contained value Objects are shared.

Specified by:

values in interface java.util.Map<java.lang.Integer,E>

Specified by:

values in interface java.util.SortedMap<java.lang.Integer,E>

Returns:

a Set of all keys in this Map

entrySet

public java.util.Set<java.util.Map.Entry<java.lang.Integer,E>> entrySet()

This function returns a Set of all the IntKeyEntrys contained in this Map. The time and space complexity of this function is in O(n), where n is the size of this Map. In this implementation the returned Set is actually a HashSet.

Important: This function does not quite return a collection view of this Map as described in the documentation of the Map interface, and changes to the returned Collection may not affect this Map, and vice versa. Essentially, the returned Entries are those contained in the Map, so changes to the Entries will be reflected in the Map. However, new Entries that are added to the Set, or Entries that are removed from it will not affect the Map.

Specified by:

entrySet in interface java.util.Map<java.lang.Integer,E>

Specified by:

entrySet in interface java.util.SortedMap<java.lang.Integer,E>

Returns:

Set of Entries in this Map

clear

public void clear()

This function removes all mappings from this Map. The resulting Map behaves exactly as if it had just been newly created.

Specified by:

clear in interface java.util.Map<java.lang.Integer,E>

remove

public E remove(java.lang.Object key)

This function removes the mapping for this key from this Map if it was present. The value the key was mapped to is returned. A null return may indicate that the Map previously associated null with the specified key. Note that the given key Object must be an Integer, but must not be null. The time complexity of this function is guaranteed to be in O(log(n)), where n is the size of this Map.

Specified by:

remove in interface java.util.Map<java.lang.Integer,E>

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

put

public E put(int key,
             E value)

This function associates the specified key, an int, with the specified value in this IntKeyMap. If the IntKeyMap previously contained a mapping for this key, the old value is replaced. The old value is also used as the return value of this function. A null return may indicate that no previous association existed or that the IntKeyMap previously associated null with the specified key. The time complexity of this function is guaranteed to be in O(log(n)), where n is the size of this IntKeyMap.

Specified by:

put in interface IntKeyMap<E>

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

containsKey

public boolean containsKey(int key)

This function returns true if this IntKeyMap contains a mapping for the specified key, which is an int here. The time complexity of this function is guaranteed to be in O(log(n)), where n is the size of this IntKeyMap.

Specified by:

containsKey in interface IntKeyMap<E>

Parameters:

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

Returns:

true if this IntKeyMap contains a mapping for the specified key

get

public E get(int key)

This function returns the value to which this IntKeyMap maps the specified key, which is an int here. It returns null if the IntKeyMap contains no mapping for this key. A return value of null does not necessarily indicate that the IntKeyMap contains no mapping for the key; it's also possible that the IntKeyMap explicitly maps the key to null. The containsKey(int) operation may be used to distinguish these two cases. The time complexity of this function is guaranteed to be in O(log(n)), where n is the size of this IntKeyMap.

Specified by:

get in interface IntKeyMap<E>

Parameters:

key - key whose associated value is to be returned

Returns:

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

remove

public E remove(int key)

This function removes the mapping for this key, an int, from this IntKeyMap if it was present. The value the key was mapped to is returned. A null return may indicate that the IntKeyMap previously associated null with the specified key. The time complexity of this function is guaranteed to be in O(log(n)), where n is the size of this IntKeyMap.

Specified by:

remove in interface IntKeyMap<E>

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

firstKey

public java.lang.Integer firstKey()
                           throws java.util.NoSuchElementException

This function returns the first (lowest) key currently in this SortedMap. The time complexity of this function is guaranteed to be in O(log(n)), where n is the size of this SortedMap.

Specified by:

firstKey in interface java.util.SortedMap<java.lang.Integer,E>

Returns:

the first (lowest) key currently in this SortedMap

Throws:

java.util.NoSuchElementException - if this SortedMap is empty

lastKey

public java.lang.Integer lastKey()
                          throws java.util.NoSuchElementException

This function returns the last (highest) key currently in this SortedMap. The time complexity of this function is guaranteed to be in O(log(n)), where n is the size of this SortedMap.

Specified by:

lastKey in interface java.util.SortedMap<java.lang.Integer,E>

Returns:

the last (highest) key currently in this SortedMap

Throws:

java.util.NoSuchElementException - if the SortedMap is empty

comparator

public java.util.Comparator<? super java.lang.Integer> comparator()
                                                           throws java.lang.UnsupportedOperationException

This function throws an UnsupportedOperationException. Since keys are ints (Integers) here the order is defined by their values and no Comparator is needed to determine their order.

Specified by:

comparator in interface java.util.SortedMap<java.lang.Integer,E>

Returns:

nothing

Throws:

java.lang.UnsupportedOperationException - always

headMap

public java.util.SortedMap<java.lang.Integer,E> headMap(java.lang.Integer toKey)
                                                 throws java.lang.UnsupportedOperationException

This function throws an UnsupportedOperationException.

Specified by:

headMap in interface java.util.SortedMap<java.lang.Integer,E>

Parameters:

toKey - highest key in the requested sub-Map

Returns:

nothing

Throws:

java.lang.UnsupportedOperationException - always

tailMap

public java.util.SortedMap<java.lang.Integer,E> tailMap(java.lang.Integer fromKey)
                                                 throws java.lang.UnsupportedOperationException

This function throws an UnsupportedOperationException.

Specified by:

tailMap in interface java.util.SortedMap<java.lang.Integer,E>

Parameters:

fromKey - lowest key in the requested sub-Map

Returns:

nothing

Throws:

java.lang.UnsupportedOperationException - always

subMap

public java.util.SortedMap<java.lang.Integer,E> subMap(java.lang.Integer fromKey,
                                                       java.lang.Integer toKey)
                                                throws java.lang.UnsupportedOperationException

This function throws an UnsupportedOperationException.

Specified by:

subMap in interface java.util.SortedMap<java.lang.Integer,E>

Parameters:

fromKey - lowest key in the requested sub-Map

toKey - highest key in the requested sub-Map

Returns:

nothing

Throws:

java.lang.UnsupportedOperationException - always

iterator

public java.util.Iterator<IntKeyTreeMap.IntKeyTreeEntry<E>> iterator()

This function returns an Iterator for the Entries in this Map. They will be returned in the (ascending) order of their keys.

Specified by:

iterator in interface java.lang.Iterable<IntKeyTreeMap.IntKeyTreeEntry<E>>

Returns:

an ordered Iterator of the IntKeyEntrys in this Map

firstIntKey

public int firstIntKey()
                throws java.util.NoSuchElementException

This function returns the first (lowest) key currently in this SortedMap. The time complexity of this function is guaranteed to be in O(log(n)), where n is the size of this SortedMap.

Returns:

the first (lowest) key currently in this SortedMap

Throws:

java.util.NoSuchElementException - if this SortedMap is empty

lastIntKey

public int lastIntKey()
               throws java.util.NoSuchElementException

This function returns the last (highest) key currently in this SortedMap. The time complexity of this function is guaranteed to be in O(log(n)), where n is the size of this SortedMap.

Returns:

the last (highest) key currently in this SortedMap

Throws:

java.util.NoSuchElementException - if the SortedMap is empty

equals

public boolean equals(java.lang.Object o)

This function tests whether this and the given Object are equal. If the given Object is an IntKeyMap the local equality test is used, otherwise entries are compared one by one.

Specified by:

equals in interface java.util.Map<java.lang.Integer,E>

Overrides:

equals in class java.lang.Object

Parameters:

o - the Object this IntKeyTreeMap is compared to

Returns:

boolean whether they represent equal mappings

equals

public boolean equals(IntKeyMap<E> imap)

This function tests whether the this and the given IntKeyMap do map the same keys to equal values.

Parameters:

imap - the IntKeyMap this is compared to

Returns:

boolean whether they contain equal entries

hashCode

public int hashCode()

This function computes a hash value for this IntKeyTreeMap. Note that this function is relatively expensive to compute (linear in the size of the Map) and thus, hashing may not be very efficient.

Specified by:

hashCode in interface java.util.Map<java.lang.Integer,E>

Overrides:

hashCode in class java.lang.Object

Returns:

a hash value for this Map

toString

public java.lang.String toString()

This function returns a printable representation of this IntKeyMap. It is printed as a comma-separated set of "key->value" pairs, e.g.:

 {1->One, 2->Two}
 

Overrides:

toString in class java.lang.Object

Returns:

a String representation of this IntKeyMap.