edu.ucla.sspace.util

Class BoundedSortedMultiMap<K,V>

java.lang.Object

edu.ucla.sspace.util.TreeMultiMap<K,V>

edu.ucla.sspace.util.BoundedSortedMultiMap<K,V>

All Implemented Interfaces:

MultiMap<K,V>, SortedMultiMap<K,V>, Serializable

public class BoundedSortedMultiMap<K,V>
extends TreeMultiMap<K,V>

A MultiMap implementation that grows to a fixed size and then retains only a fixed number of either keys or mappings. All keys used in this class must implements Comparable.

If an instance is bound by the total number of mappings, a user may configure whether the map arbitrarily removes tied mapping (those with the same key), or whether the tied mappings are removed fairly. While both result in the same size, an arbitrary mapping have a bias in the order of removal based on the element hash distribution. However, a fair removal policy incurs a slightly higher cost based on the number of elements sharing the same key.

See Also:

BoundedSortedMap, Serialized Form

Constructor Summary

Constructors

Constructor and Description
BoundedSortedMultiMap(int bound) Creates an instance that will retain the specified number of mappings that are associated with the highest keys, using an arbitrary removal policy.
BoundedSortedMultiMap(int bound, boolean keyBound) Creates an instance with the specified bound that will retain either the specified number of highest keys if keyBound is true, or the total number of mappings with the highest keys if keyBound is false.
BoundedSortedMultiMap(int bound, boolean keyBound, boolean retainHighest, boolean isFair) Creates an instance with the specified bound that will retain either the specified number of keys if keyBound is true, or the total number of mappings if keyBound is false.

Method Summary

Methods

Modifier and Type	Method and Description
boolean	put(K key, V value) Adds the key-value mapping to this map, and if the total number of mappings exceeds the bounds, removes either the currently lowest element, or if reversed, the currently highest element.
void	putAll(Map<? extends K,? extends V> m) Adds all of the key-value mapping to this map, and if the total number of mappings exceeds the bounds, removes either the currently lowest element, or if reversed, the currently highest element.
boolean	putMulti(K key, Collection<V> values) Adds all of the key-value mapping to this map, and if the total number of mappings exceeds the bounds, removes either the currently lowest element, or if reversed, the currently highest element.

Methods inherited from class edu.ucla.sspace.util.TreeMultiMap

asMap, clear, comparator, containsKey, containsMapping, containsValue, entrySet, firstKey, get, headMap, isEmpty, keySet, lastKey, putAll, putMany, range, remove, remove, size, subMap, tailMap, toString, values, valueSets

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

BoundedSortedMultiMap

public BoundedSortedMultiMap(int bound)

Creates an instance that will retain the specified number of mappings that are associated with the highest keys, using an arbitrary removal policy.

Parameters:

bound - the maximum number of key-value mappings to retain

BoundedSortedMultiMap

public BoundedSortedMultiMap(int bound,
                     boolean keyBound)

Creates an instance with the specified bound that will retain either the specified number of highest keys if keyBound is true, or the total number of mappings with the highest keys if keyBound is false. If keyBound is false, an arbitrary mapping for the lowest key will be removed.

Parameters:

bound - the number to retain

keyBound - true if the bound should apply to the number of keys, regardless of the number of values to which those keys map, or false if the bound should apply to the total number of key-value mappings in this map

BoundedSortedMultiMap

public BoundedSortedMultiMap(int bound,
                     boolean keyBound,
                     boolean retainHighest,
                     boolean isFair)

Creates an instance with the specified bound that will retain either the specified number of keys if keyBound is true, or the total number of mappings if keyBound is false. If retainHighest is true, the higest keys will be retained; else the lowest keys will be be retained. If keyBound is false, an the that will be removed will depend on the whether this map fairly removes tied mappings or arbitrarily removes mappings.

Parameters:

bound - the number to retain

keyBound - true if the bound should apply to the number of keys, regardless of the number of values to which those keys map, or false if the bound should apply to the total number of key-value mappings in this map

retainHighest - true if the higest keys should be kept, false if the lowest keys should be kept

isFair - if the map is value bound, true if the map should pick a random mapping to remove, which ensures fairness, rather than an arbitrary mapping.

Method Detail

put

public boolean put(K key,
          V value)

Adds the key-value mapping to this map, and if the total number of mappings exceeds the bounds, removes either the currently lowest element, or if reversed, the currently highest element. If this map is bound by the number of keys, a put operation may result in the range decreasing, even though the number of keys stays constant.

Specified by:

put in interface MultiMap<K,V>

Overrides:

put in class TreeMultiMap<K,V>

Parameters:

key - key with which the specified value is to be associated

value - a value to be associated with the specified key

Returns:

true if the provided value was not already in the set of value mapped to the specified key

putMulti

public boolean putMulti(K key,
               Collection<V> values)

Adds all of the key-value mapping to this map, and if the total number of mappings exceeds the bounds, removes either the currently lowest element, or if reversed, the currently highest element. If this map is bound by the number of keys, a put operation may result in the range decreasing, even though the number of keys stays constant.

Parameters:

key -

values -

putAll

public void putAll(Map<? extends K,? extends V> m)

Adds all of the key-value mapping to this map, and if the total number of mappings exceeds the bounds, removes either the currently lowest element, or if reversed, the currently highest element. If this map is bound by the number of keys, a put operation may result in the range decreasing, even though the number of keys stays constant.

Specified by:

putAll in interface MultiMap<K,V>

Overrides:

putAll in class TreeMultiMap<K,V>

Parameters:

m -