iglu.util
Class ValueSortedMap

java.lang.Object
  |
  +--java.util.AbstractMap
        |
        +--iglu.util.ValueSortedMap

All Implemented Interfaces:

java.lang.Cloneable, java.util.Map, java.io.Serializable

Direct Known Subclasses:

ActiveValueSortedMap

public class ValueSortedMap

extends java.util.AbstractMap

implements java.io.Serializable, java.lang.Cloneable

Holds an mapping between objects and their values, ordered by value. This class is similar to SortedMap except the objects are sorted by their values, rather than by the keys themselves.

This class is intended for use with objects that receive a value from a complex computation, such as document/query similarity.

If you need to sort objects by some method other than an external value, use TreeSet or TreeMap and create a custom Comparator. This class does not implement SortedMap because it does not have an explicit Comparator.

Note that this implementation is not synchronized. If multiple threads access a map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally. (A structural modification is any operation that adds or deletes one or more mappings; merely changing the value associated with an existing key is not a structural modification.) This is typically accomplished by synchronizing on some object that naturally encapsulates the map. If no such object exists, the map should be "wrapped" using the Collections.synchronizedMap method. This is best done at creation time, to prevent accidental unsynchronized access to the map:

 Map m = Collections.synchronizedMap(new ValueSortedMap(...));
 

This map keeps cached, sorted vectors of the elements in both forward and backward order. This is to speed up multiple accesses to the iterator functions.

Version:

1.0

Author:

Ryan Scherle, Travis Bauer

See Also:

TermVector, SortedMap, TreeSet, TreeMap, Serialized Form

Field Summary

static ValueSortedMap	EMPTY An empty map, for use when you don't want to do anthing to the vector.
protected java.util.Vector	forwardSortedVector
protected java.util.Vector	reverseSortedVector
protected java.util.HashMap	storedItems

Fields inherited from class java.util.AbstractMap

Constructor Summary

ValueSortedMap()
Constructs an empty map.

ValueSortedMap(java.util.Map map)
Constructs a new map from an existing mapping.

Method Summary

void	clear() Removes all mappings from this map.
private void	clearSorts() Removes the cached sort vectors in preparation for a change.
java.lang.Object	clone() Creates a shallow clone of the object.
boolean	containsKey(java.lang.Object key) Returns true if the specified key is in the mapping.
java.util.Set	entrySet() Returns an unordered set of all items in the map.
java.lang.Object	get(java.lang.Object key) Returns the value to which this map maps the specified key.
double	getDouble(java.lang.Object key) Returns the value to which this map maps the specified key.
boolean	isEmpty() Returns true if this map contains no key-value mappings.
java.util.Iterator	iterator() Returns an unordered iterator over the set.
java.util.Iterator	keyIterator() Returns an iterator for the keys contained in this map.
java.util.Set	keySet() Returns a set view of the keys contained in this map.
void	linearlyScale() Linearly scales the values in the map.
static void	main(java.lang.String[] args) Runs some tests on this class.
void	normalize() Normalizes the values in the map, so that its length (as a vector) is 1.
java.lang.Object	put(java.lang.Object key, double value) Adds an item and its value to the map.
java.lang.Object	put(java.lang.Object key, java.lang.Object value) Adds an item and its value to the map.
void	putAll(java.util.Map map) Copies all of the mappings from the specified map to this one.
int	rankOrder(java.lang.Object key) Returns the ordered position of this key in the map.
java.lang.Object	remove(java.lang.Object key) Removes the mapping for this key from this map if present.
java.util.Iterator	reverseKeyIterator() Returns an iterator over the objects in reverse key order.
void	scaleBy(double n) Scales all terms of the map by the given value.
int	size() Returns the number of elements in this map.
void	subtract(java.util.Set subItems) Performs a set difference on the list of items.
static void	test() Runs some tests on this class.
java.lang.String	toString() Returns a string representation of this map.
void	truncateTo(int numItems) Truncates this map to the given length.

Methods inherited from class java.util.AbstractMap

containsValue, equals, hashCode, values

Methods inherited from class java.lang.Object

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

Field Detail

storedItems

protected java.util.HashMap storedItems

forwardSortedVector

protected java.util.Vector forwardSortedVector

reverseSortedVector

protected java.util.Vector reverseSortedVector

EMPTY

public static final ValueSortedMap EMPTY

An empty map, for use when you don't want to do anthing to the vector.

Constructor Detail

ValueSortedMap

public ValueSortedMap()

Constructs an empty map.

ValueSortedMap

public ValueSortedMap(java.util.Map map)

Constructs a new map from an existing mapping.

Method Detail

size

public int size()

Returns the number of elements in this map.

Specified by:

size in interface java.util.Map

Overrides:

size in class java.util.AbstractMap

isEmpty

public boolean isEmpty()

Returns true if this map contains no key-value mappings.

Specified by:

isEmpty in interface java.util.Map

Overrides:

isEmpty in class java.util.AbstractMap

entrySet

public java.util.Set entrySet()

Returns an unordered set of all items in the map. These are Map.entry objects.

Specified by:

entrySet in interface java.util.Map

Specified by:

entrySet in class java.util.AbstractMap

containsKey

public boolean containsKey(java.lang.Object key)

Returns true if the specified key is in the mapping.

Specified by:

containsKey in interface java.util.Map

Overrides:

containsKey in class java.util.AbstractMap

get

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

Returns the value to which this map maps the specified key. If the key isn't in the map, returns null.

Specified by:

get in interface java.util.Map

Overrides:

get in class java.util.AbstractMap

getDouble

public double getDouble(java.lang.Object key)

Returns the value to which this map maps the specified key. If the key isn't in the map, or the value isn't a Number, returns 0.

put

public java.lang.Object put(java.lang.Object key,
                            java.lang.Object value)

Adds an item and its value to the map. If the item already exists in the map, the new value replaces the old value.

Specified by:

put in interface java.util.Map

Overrides:

put in class java.util.AbstractMap

put

public java.lang.Object put(java.lang.Object key,
                            double value)

Adds an item and its value to the map. If the item already exists in the map, the new value replaces the old value.

remove

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

Removes the mapping for this key from this map if present. Returns the value previously given to the key.

Specified by:

remove in interface java.util.Map

Overrides:

remove in class java.util.AbstractMap

putAll

public void putAll(java.util.Map map)

Copies all of the mappings from the specified map to this one. If an item already exists in the map, the new value replaces the old value.

Specified by:

putAll in interface java.util.Map

Overrides:

putAll in class java.util.AbstractMap

truncateTo

public void truncateTo(int numItems)

Truncates this map to the given length. The top numItems items, ordered by value, are kept.

subtract

public void subtract(java.util.Set subItems)

Performs a set difference on the list of items.

clear

public void clear()

Removes all mappings from this map.

Specified by:

clear in interface java.util.Map

Overrides:

clear in class java.util.AbstractMap

clearSorts

private void clearSorts()

Removes the cached sort vectors in preparation for a change.

keySet

public java.util.Set keySet()

Returns a set view of the keys contained in this map. These keys aren't ordered, because we've gotten rid of the values that were used to order them.

Specified by:

keySet in interface java.util.Map

Overrides:

keySet in class java.util.AbstractMap

iterator

public java.util.Iterator iterator()

Returns an unordered iterator over the set. Each object returned by the iterator is a Map.entry item. This function gives you a relatively inexpensive way to iterate over the set when you don't care about the order. keyIterator() returns items in order, but is relatively computationally expensive.

keyIterator

public java.util.Iterator keyIterator()

Returns an iterator for the keys contained in this map. Only the keys are included in the iterator, but they are ordered by their value. If the value is needed, it can be recalled with the get() or getDouble() methods. This iterator does not support the remove operation, even though it might appear to support it.

reverseKeyIterator

public java.util.Iterator reverseKeyIterator()

Returns an iterator over the objects in reverse key order. The objects will be returned in an other the opposite of keyIterator() This iterator does not support the remove operation, even though it might appear to support it.

toString

public java.lang.String toString()

Returns a string representation of this map.

Overrides:

toString in class java.util.AbstractMap

normalize

public void normalize()

Normalizes the values in the map, so that its length (as a vector) is 1. It is assumed that every item is mapped to a Number. If this is not true, only the items that map to a Number will be nomalized. Everything else will have its value set to zero.

scaleBy

public void scaleBy(double n)

Scales all terms of the map by the given value. It is assumed that every item is mapped to a Number. If this is not true, only the items that map to a Number will be scaled. Everything else will have its value set to zero.

linearlyScale

public void linearlyScale()

Linearly scales the values in the map. After scaling, the lowest value will be 1, the second-lowest will be 2, etc.

rankOrder

public int rankOrder(java.lang.Object key)

Returns the ordered position of this key in the map. Returns -1 if the key is not in the map.

clone

public java.lang.Object clone()

Creates a shallow clone of the object. The objects contained in the Map are not themselves cloned.

Overrides:

clone in class java.util.AbstractMap

test

public static void test()

Runs some tests on this class.

main

public static void main(java.lang.String[] args)

Runs some tests on this class.