de.bb.util

Class MultiMap<K,V>

java.lang.Object

java.util.AbstractMap<K,V>

de.bb.util.MultiMap<K,V>

All Implemented Interfaces:

java.io.Serializable, java.util.Map<K,V>, java.util.SortedMap<K,V>

public class MultiMap<K,V>
extends java.util.AbstractMap<K,V>

This class is used to maintain key value pairs, sorted by key. All keys must be usable by the specified Comparator object, or if no Comparator is used, by the Objects compareTo function.
This implementation allows duplicate keys.

• If a key is inserted twice or more often, insert places the new entry behind (rightmost) the existing entries.
• If a key is removed, the first (leftmost) entry is removed.
• To delete an explicit key, value pair, a remove(k,p) function exists.

In other words:
If only one constant key is used, to insert, get and remove values, it acts like a FIFO.

See Also:

Serialized Form

Nested Class Summary

Nested classes/interfaces inherited from class java.util.AbstractMap

java.util.AbstractMap.SimpleEntry<K,V>, java.util.AbstractMap.SimpleImmutableEntry<K,V>

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

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

Field Summary

Fields

Modifier and Type	Field and Description
protected java.util.Comparator<K>	comp

Constructor Summary

Constructors

Constructor and Description
MultiMap() Creates a MultiMap object without a Comparator.
MultiMap(java.util.Comparator<K> comp_) Creates a MultiMap object, using the specified Comparator.

Method Summary

Methods

Modifier and Type	Method and Description
void	clear() Clears this Map so that it contains no objects.
java.util.Comparator<K>	comparator() Return the used Comparator object, if any.
protected int	compare(K a, K b)
boolean	containsKey(java.lang.Object key) Returns true if this map contains a mapping for the specified key.
java.util.Set<java.util.Map.Entry<K,V>>	entrySet() Return a Set for this Map's entries.
K	firstKey() Return the key of the sorted first entry in this Map.
protected void	fixAdd(de.bb.util.MapBase.Leaf<K,V> i) Rebalance the tree on add.
V	get(java.lang.Object key) Get the element for the specified value
java.util.SortedMap<K,V>	headMap(K to) Create a sub map view of this map.
boolean	isEmpty() Tests if this Map has no components.
K	lastKey() Return the key of the sorted last entry in this Map.
V	put(K key, V value) Insert a given object into the tree using the specified key.
V	remove(K key, V value) Removes the key holding the specified value from this Map.
V	remove(java.lang.Object key) Removes the key holding the specified value from this Map.
int	size() Returns the number of components in this Map.
java.util.SortedMap<K,V>	subMap(K from, K to) Create a sub map view of this map.
java.util.SortedMap<K,V>	tailMap(K from) Create a sub map view of this map.
java.lang.String	toString() displays the members with toString().

Methods inherited from class java.util.AbstractMap

clone, containsValue, equals, hashCode, keySet, putAll, values

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.util.SortedMap

keySet, values

Methods inherited from interface java.util.Map

containsValue, equals, hashCode, putAll

Field Detail

comp

protected java.util.Comparator<K> comp

Constructor Detail

MultiMap

public MultiMap(java.util.Comparator<K> comp_)

Creates a MultiMap object, using the specified Comparator.

Parameters:

comp_ - a Comparator object.

MultiMap

public MultiMap()

Creates a MultiMap object without a Comparator.

Method Detail

remove

public V remove(K key,
       V value)

Removes the key holding the specified value from this Map. Useful in MultiMap to remove a distinct key / value entry. This method does nothing if the key is not in the Map. If value is null, the first matching key is removed.

Parameters:

key - the key that needs to be removed.

value - the value at the key that needs to be removed.

Returns:

the value to which the key had been mapped in this MultiMap, or null if the key did not have a mapping.

put

public V put(K key,
    V value)

Insert a given object into the tree using the specified key.

Specified by:

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

Overrides:

put in class java.util.AbstractMap<K,V>

Parameters:

key - the key

value - the inserted value

Returns:

the old replaced value or null.

clear

public void clear()

Clears this Map so that it contains no objects.

Specified by:

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

Overrides:

clear in class java.util.AbstractMap<K,V>

size

public int size()

Returns the number of components in this Map.

Specified by:

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

Overrides:

size in class java.util.AbstractMap<K,V>

Returns:

the number of components in this Map.

isEmpty

public final boolean isEmpty()

Tests if this Map has no components.

Specified by:

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

Overrides:

isEmpty in class java.util.AbstractMap<K,V>

Returns:

true if this Map has no components; false otherwise.

fixAdd

protected final void fixAdd(de.bb.util.MapBase.Leaf<K,V> i)

Rebalance the tree on add.

Parameters:

i -

get

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

Get the element for the specified value

Specified by:

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

Overrides:

get in class java.util.AbstractMap<K,V>

Parameters:

key - the key for the element to search

Returns:

the value if found, either null

remove

public V remove(java.lang.Object key)

Removes the key holding the specified value from this Map. Useful in MultiMap to remove a distinct key / value entry. This method does nothing if the key is not in the Map. If value is null, the first matching key is removed.

Specified by:

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

Overrides:

remove in class java.util.AbstractMap<K,V>

Parameters:

key - the key that needs to be removed.

Returns:

the value to which the key had been mapped in this MultiMap, or null if the key did not have a mapping.

compare

protected final int compare(K a,
          K b)

containsKey

public boolean containsKey(java.lang.Object key)

Returns true if this map contains a mapping for the specified key.

Specified by:

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

Overrides:

containsKey in class java.util.AbstractMap<K,V>

Parameters:

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

Returns:

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

Throws:

java.lang.NullPointerException - if the key is null and this map does not not permit null keys.

entrySet

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

Return a Set for this Map's entries.

Specified by:

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

Specified by:

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

Specified by:

entrySet in class java.util.AbstractMap<K,V>

Returns:

a Set for this Map's entries.

comparator

public java.util.Comparator<K> comparator()

Return the used Comparator object, if any.

Specified by:

comparator in interface java.util.SortedMap<K,V>

Returns:

the used Comparator object, or null.

firstKey

public K firstKey()

Return the key of the sorted first entry in this Map.

Specified by:

firstKey in interface java.util.SortedMap<K,V>

Returns:

the key of the sorted first entry in this Map, or null on empty Map.

lastKey

public K lastKey()

Return the key of the sorted last entry in this Map.

Specified by:

lastKey in interface java.util.SortedMap<K,V>

Returns:

the key of the sorted last entry in this Map, or null on empty Map.

subMap

public java.util.SortedMap<K,V> subMap(K from,
                              K to)

Create a sub map view of this map. The parameters specify the start and the not included end point. It is also possible to create a SubMap from this SubMap.

Specified by:

subMap in interface java.util.SortedMap<K,V>

Parameters:

from - first key of the sub map

to - first key behind the last key.

Returns:

a new allocated object which is a view to the underlying map.

tailMap

public java.util.SortedMap<K,V> tailMap(K from)

Create a sub map view of this map. The parameter specifies the start point, and the sub map ends at the same point as this map. It is also possible to create a SubMap from this SubMap.

Specified by:

tailMap in interface java.util.SortedMap<K,V>

Parameters:

from - first key of the sub map

Returns:

a new allocated object which is a view to the underlying map.

headMap

public java.util.SortedMap<K,V> headMap(K to)

Create a sub map view of this map. The sub map starts at the same point as this map, and the parameter specifies the not included end point. It is also possible to create a SubMap from this SubMap.

Specified by:

headMap in interface java.util.SortedMap<K,V>

Parameters:

to - first key behind the last key.

Returns:

a new allocated object which is a view to the underlying map.

toString

public java.lang.String toString()

displays the members with toString().

Overrides:

toString in class java.util.AbstractMap<K,V>

Returns:

a String with all members.