jpaul.DataStructs
Class NoCompTreeMap<K,V>

java.lang.Object
  jpaul.DataStructs.NoCompTreeMap<K,V>

All Implemented Interfaces:

java.io.Serializable, java.lang.Cloneable, java.util.Map<K,V>

public class NoCompTreeMap<K,V>
extends java.lang.Object
implements java.util.Map<K,V>, java.lang.Cloneable, java.io.Serializable

NoCompTreeMap is tree map that does not require any used-defined Comparator. Instead, the tree is ordered by the relative ordering between the haashcodes of the keys. The implementation is able to cope with the situation when two non-equal keys have the same hashcode: intuitively, the key that is put first in the map is considered lower than the other one.

For the curious programmer, when we add a new mapping, if the key to add has the same hashcode as the key from a tree node, we decend into the right subtree (unless the keys are equal). This means that if two many keys have the same hashcode, the tree can degenerate into a list. Still, we think this is unlikely to happen frequently in practice; in practice, we expect the complexity of operations to be more or less logarithmic in the size of the tree.

This map is useful to use in programs with many small maps or when coming out with a total ordering between elements is difficult (or the programmer is too lazy to think about such an order).

Version:

$Id: NoCompTreeMap.java,v 1.10 2006/03/14 02:29:31 salcianu Exp $

Author:

Alexandru Salcianu - salcianu@alum.mit.edu

See Also:

Serialized Form

Nested Class Summary

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

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

Constructor Summary

NoCompTreeMap()
Creates a NoCompTreeMap.

NoCompTreeMap(java.util.Map<? extends K,? extends V> map)
Creates a NoCompTreeMap with the same mappings as the given map.

Method Summary

void	clear()
NoCompTreeMap<K,V>	clone()
boolean	containsKey(java.lang.Object key)
boolean	containsValue(java.lang.Object value) Unsupported yet.
java.util.Set<java.util.Map.Entry<K,V>>	entrySet() Returns an unmodifiable set view of the map entries.
boolean	equals(java.lang.Object o)
V	get(java.lang.Object key)
int	hashCode()
boolean	isEmpty()
java.util.Set<K>	keySet() Returns an unmodifiable set view of the keys contained in this map.
V	put(K key, V value) Associates the specified value with the specified key in this map.
void	putAll(java.util.Map<? extends K,? extends V> map) Copies all of the mappings from the specified map to this map.
V	remove(java.lang.Object key) Removes the mapping previously attached to key.
int	size()
java.lang.String	toString()
java.util.Collection<V>	values() Returns an unmodifiable collection view of the values from this map.

Methods inherited from class java.lang.Object

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

Constructor Detail

NoCompTreeMap

public NoCompTreeMap()

Creates a NoCompTreeMap.

NoCompTreeMap

public NoCompTreeMap(java.util.Map<? extends K,? extends V> map)

Creates a NoCompTreeMap with the same mappings as the given map.

Method Detail

size

public final int size()

Specified by:

size in interface java.util.Map<K,V>

isEmpty

public final boolean isEmpty()

Specified by:

isEmpty in interface java.util.Map<K,V>

containsKey

public final boolean containsKey(java.lang.Object key)

Specified by:

containsKey in interface java.util.Map<K,V>

containsValue

public final boolean containsValue(java.lang.Object value)

Unsupported yet.

Specified by:

containsValue in interface java.util.Map<K,V>

get

public V get(java.lang.Object key)

Specified by:

get in interface java.util.Map<K,V>

put

public final V put(K key,
                   V value)

Associates the specified value with the specified key in this map.

Specified by:

put in interface java.util.Map<K,V>

remove

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

Removes the mapping previously attached to key. Returns the old mapping if any, or null otherwise.

Specified by:

remove in interface java.util.Map<K,V>

putAll

public final void putAll(java.util.Map<? extends K,? extends V> map)

Copies all of the mappings from the specified map to this map.

Specified by:

putAll in interface java.util.Map<K,V>

clear

public final void clear()

Specified by:

clear in interface java.util.Map<K,V>

values

public final java.util.Collection<V> values()

Returns an unmodifiable collection view of the values from this map.

Specified by:

values in interface java.util.Map<K,V>

entrySet

public final java.util.Set<java.util.Map.Entry<K,V>> entrySet()

Returns an unmodifiable set view of the map entries.

Specified by:

entrySet in interface java.util.Map<K,V>

keySet

public final java.util.Set<K> keySet()

Returns an unmodifiable set view of the keys contained in this map.

Specified by:

keySet in interface java.util.Map<K,V>

clone

public NoCompTreeMap<K,V> clone()

Overrides:

clone in class java.lang.Object

equals

public boolean equals(java.lang.Object o)

Specified by:

equals in interface java.util.Map<K,V>

Overrides:

equals in class java.lang.Object

hashCode

public int hashCode()

Specified by:

hashCode in interface java.util.Map<K,V>

Overrides:

hashCode in class java.lang.Object

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object