de.bb.util
Class MultiMap

java.lang.Object
  java.util.AbstractMap
      de.bb.util.MultiMap

All Implemented Interfaces:

java.io.Serializable, java.util.Map, java.util.SortedMap

public class MultiMap
extends java.util.AbstractMap

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>

Constructor Summary

MultiMap()
Creates a MultiMap object without a Comparator.

MultiMap(java.util.Comparator comp_)
Creates a MultiMap object, using the specified Comparator.

Method Summary

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

Constructor Detail

MultiMap

public MultiMap(java.util.Comparator 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 java.lang.Object remove(java.lang.Object key,
                               java.lang.Object 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 java.lang.Object put(java.lang.Object key,
                            java.lang.Object value)

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

Specified by:

put in interface java.util.Map

Overrides:

put in class java.util.AbstractMap

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

Overrides:

clear in class java.util.AbstractMap

size

public int size()

Returns the number of components in this Map.

Specified by:

size in interface java.util.Map

Overrides:

size in class java.util.AbstractMap

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

Overrides:

isEmpty in class java.util.AbstractMap

Returns:

true if this Map has no components; false otherwise.

fixAdd

protected final void fixAdd(de.bb.util.MapBase.Leaf i)

Rebalance the tree on add.

Parameters:

i -

get

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

Get the element for the specified value

Specified by:

get in interface java.util.Map

Overrides:

get in class java.util.AbstractMap

Parameters:

key - the key for the element to search

Returns:

the value if found, either null

remove

public java.lang.Object 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

Overrides:

remove in class java.util.AbstractMap

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(java.lang.Object a,
                            java.lang.Object 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

Overrides:

containsKey in class java.util.AbstractMap

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 entrySet()

Return a Set for this Map's entries.

Specified by:

entrySet in interface java.util.Map

Specified by:

entrySet in interface java.util.SortedMap

Specified by:

entrySet in class java.util.AbstractMap

Returns:

a Set for this Map's entries.

comparator

public java.util.Comparator comparator()

Return the used Comparator object, if any.

Specified by:

comparator in interface java.util.SortedMap

Returns:

the used Comparator object, or null.

firstKey

public java.lang.Object firstKey()

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

Specified by:

firstKey in interface java.util.SortedMap

Returns:

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

lastKey

public java.lang.Object lastKey()

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

Specified by:

lastKey in interface java.util.SortedMap

Returns:

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

subMap

public java.util.SortedMap subMap(java.lang.Object from,
                                  java.lang.Object 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

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 tailMap(java.lang.Object 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

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 headMap(java.lang.Object 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

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

Returns:

a String with all members.