inf.util
Class DoubleKeyTreeMap<E>

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

Type Parameters:

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

All Implemented Interfaces:

DoubleKeyMap<E>, java.lang.Cloneable, java.lang.Iterable<DoubleKeyTreeMap.DoubleKeyTreeEntry<E>>, java.util.Map<java.lang.Double,E>, java.util.SortedMap<java.lang.Double,E>

public class DoubleKeyTreeMap<E>
extends java.lang.Object
implements java.lang.Cloneable, DoubleKeyMap<E>, java.util.SortedMap<java.lang.Double,E>, java.lang.Iterable<DoubleKeyTreeMap.DoubleKeyTreeEntry<E>>

This is a Red-Black-Tree-based implementation of a SortedMap, mapping doubles (keys) to Objects (values). If the key is given as a Double rather than a double, 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 DoubleKeyEntrys 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 doubles here which are not Objects. The use of doubles rather than Doubles 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	DoubleKeyTreeMap.DoubleKeyTreeEntry<E>
(package private) class	DoubleKeyTreeMap.DoubleKeyTreeMapIterator<T>

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

DoubleKeyMap.DoubleKeyEntry<E>

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

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

Field Summary

protected DoubleKeyTreeMap.DoubleKeyTreeEntry<E>

root the root of the tree

Constructor Summary

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

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

Method Summary

void	clear() This function removes all mappings from this Map.
DoubleKeyTreeMap<E>	clone() This function returns a shallow copy of this DoubleKeyTreeMap.
java.util.Comparator<? super java.lang.Double>	comparator() This function throws an UnsupportedOperationException.
boolean	containsKey(double key) This function returns true if this DoubleKeyMap contains a mapping for the specified key, which is a double 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.Double,E>>	entrySet() This function returns a set of all the DoubleKeyEntrys contained in this Map.
boolean	equals(DoubleKeyMap<E> imap) This function tests whether the this and the given DoubleKeyMap 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.
double	firstDoubleKey() This function returns the first (lowest) key currently in this SortedMap.
java.lang.Double	firstKey() This function returns the first (lowest) key currently in this SortedMap.
E	get(double key) This function returns the value to which this DoubleKeyMap maps the specified key, which is a double 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 DoubleKeyTreeMap.
java.util.SortedMap<java.lang.Double,E>	headMap(java.lang.Double toKey) This function throws an UnsupportedOperationException.
boolean	isEmpty() This function tests whether this Map contains no entries.
java.util.Iterator<DoubleKeyTreeMap.DoubleKeyTreeEntry<E>>	iterator() This function returns an Iterator for the Entries in this Map.
java.util.Set<java.lang.Double>	keySet() This function returns a Set containing all the keys contained in this Map.
double	lastDoubleKey() This function returns the last (highest) key currently in this SortedMap.
java.lang.Double	lastKey() This function returns the last (highest) key currently in this SortedMap.
E	put(double key, E value) This function associates the specified key, a double, with the specified value in this DoubleKeyMap.
E	put(java.lang.Double key, E value) This function associates the specified key with the specified value in this Map.
void	putAll(java.util.Map<? extends java.lang.Double,? extends E> map) This function adds all the associations from the given Map to this Map.
E	remove(double key) This function removes the mapping for this key, a double, from this DoubleKeyMap 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.Double,E>	subMap(java.lang.Double fromKey, java.lang.Double toKey) This function throws an UnsupportedOperationException.
java.util.SortedMap<java.lang.Double,E>	tailMap(java.lang.Double fromKey) This function throws an UnsupportedOperationException.
java.lang.String	toString() This function returns a printable representation of this DoubleKeyMap.
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 DoubleKeyTreeMap.DoubleKeyTreeEntry<E> root

the root of the tree

Constructor Detail

DoubleKeyTreeMap

public DoubleKeyTreeMap()

This constructor creates a new, empty DoubleKeyTreeMap.

DoubleKeyTreeMap

public DoubleKeyTreeMap(java.util.Map<? extends java.lang.Double,? extends E> map)

This constructor creates a new DoubleKeyTreeMap 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 DoubleKeyTreeMap<E> clone()

This function returns a shallow copy of this DoubleKeyTreeMap. The values themselves are not cloned. Cloning a DoubleKeyTreeMap 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 DoubleKeyTreeMap.

put

public E put(java.lang.Double 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.Double,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.Double,? 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.Double,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.Double,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.Double,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 Double, 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.Double,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.Double,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 Double, 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.Double,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.Double> 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.Double,E>

Specified by:

keySet in interface java.util.SortedMap<java.lang.Double,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.Double,E>

Specified by:

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

Returns:

a Set of all keys in this Map

entrySet

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

This function returns a set of all the DoubleKeyEntrys 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.Double,E>

Specified by:

entrySet in interface java.util.SortedMap<java.lang.Double,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.Double,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 Double, 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.Double,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(double key,
             E value)

This function associates the specified key, a double, with the specified value in this DoubleKeyMap. If the DoubleKeyMap 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 DoubleKeyMap 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 DoubleKeyMap.

Specified by:

put in interface DoubleKeyMap<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(double key)

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

Specified by:

containsKey in interface DoubleKeyMap<E>

Parameters:

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

Returns:

true if this DoubleKeyMap contains a mapping for the specified key

get

public E get(double key)

This function returns the value to which this DoubleKeyMap maps the specified key, which is a double here. It returns null if the DoubleKeyMap contains no mapping for this key. A return value of null does not necessarily indicate that the DoubleKeyMap contains no mapping for the key; it's also possible that the DoubleKeyMap explicitly maps the key to null. The containsKey(double) 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 DoubleKeyMap.

Specified by:

get in interface DoubleKeyMap<E>

Parameters:

key - key whose associated value is to be returned

Returns:

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

remove

public E remove(double key)

This function removes the mapping for this key, a double, from this DoubleKeyMap if it was present. The value the key was mapped to is returned. A null return may indicate that the DoubleKeyMap 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 DoubleKeyMap.

Specified by:

remove in interface DoubleKeyMap<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.Double 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.Double,E>

Returns:

the first (lowest) key currently in this SortedMap

Throws:

java.util.NoSuchElementException - if this SortedMap is empty

lastKey

public java.lang.Double 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.Double,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.Double> comparator()
                                                          throws java.lang.UnsupportedOperationException

This function throws an UnsupportedOperationException. Since keys are doubles (Doubles) 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.Double,E>

Returns:

nothing

Throws:

java.lang.UnsupportedOperationException - always

headMap

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

This function throws an UnsupportedOperationException.

Specified by:

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

Parameters:

toKey - highest key in the requested sub-Map

Returns:

nothing

Throws:

java.lang.UnsupportedOperationException - always

tailMap

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

This function throws an UnsupportedOperationException.

Specified by:

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

Parameters:

fromKey - lowest key in the requested sub-Map

Returns:

nothing

Throws:

java.lang.UnsupportedOperationException - always

subMap

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

This function throws an UnsupportedOperationException.

Specified by:

subMap in interface java.util.SortedMap<java.lang.Double,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<DoubleKeyTreeMap.DoubleKeyTreeEntry<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<DoubleKeyTreeMap.DoubleKeyTreeEntry<E>>

Returns:

an ordered Iterator of the DoubleKeyEntrys in this Map

firstDoubleKey

public double firstDoubleKey()
                      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

lastDoubleKey

public double lastDoubleKey()
                     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 DoubleKeyMap the local equality test is used, otherwise entries are compared one by one.

Specified by:

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

Overrides:

equals in class java.lang.Object

Parameters:

o - the Object this DoubleKeyTreeMap is compared to

Returns:

boolean whether they represent equal mappings

equals

public boolean equals(DoubleKeyMap<E> imap)

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

Parameters:

imap - the DoubleKeyMap this is compared to

Returns:

boolean whether they contain equal entries

hashCode

public int hashCode()

This function computes a hash value for this DoubleKeyTreeMap. 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.Double,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 DoubleKeyMap. 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 DoubleKeyMap.