All Packages  Class Hierarchy  This Package  Previous  Next  Index

Class jgl.OrderedMap

java.lang.Object
   |
   +----java.util.Dictionary
           |
           +----jgl.OrderedMap

public class OrderedMap

extends Dictionary

implements Container

A OrderedMap is useful for implementing a collection of one-to-one or one-to-many mappings.

Strictly speaking, there is no reason why null is not a valid key. However, most comparators (including the default HashComparator) will fail and throw an exception if you attempt to add a null key because they cast the key to a class and then activate one of its methods. It is perfectly possible to hand-craft a comparator that will accept null as a valid key.

There are many different approaches that could be used to implementing an associative container. For example, most of the older libraries used a hashing scheme for positioning and retrieving items. This implementation use a data structure called a red-black tree. A red-black tree is a binary search tree that uses an extra field in every node to store the node's color. Red-black trees constrain the way that nodes may be colored in such a way that the tree remains reasonably balanced. This property is important for ensuring a good overall performance - red-black trees guarantee that the worst case performance for the most common dynamic set operations is O(log N). One conseqence of using a binary tree for storage of data is that the items remain in a sorted order. This allows JGL users to iterate through an associative container and access its elements in a sequenced manner. Each node of the red-black tree holds a Pair( key, value ). The comparator is used to order the Pairs based only on their keys.

Insertion does not affect iterators or references.

Removal only invalidates the iterators and references to the removed elements.

See Also:

OrderedMultimap, BinaryPredicate, OrderedMapExamples

OrderedMap()

Construct myself to be an empty OrderedMap that orders its keys based on their hash value and does not allow duplicates.

OrderedMap(BinaryPredicate)

Construct myself to be an empty OrderedMap that orders its keys using a specified binary predicate and does not allow duplicates.

OrderedMap(BinaryPredicate, boolean)

Construct myself to be an empty OrderedMap that orders its keys using a specified binary predicate and conditionally allows duplicates.

OrderedMap(boolean)

Construct myself to be an empty OrderedMap that orders its keys based on their hash value and conditionally allows duplicates.

OrderedMap(OrderedMap)

Construct myself to be a shallow copy of an existing OrderedMap.

add(Object)

Assume that the specified object is a Pair whose first field is a key and whose second field is a value.

add(Object, Object)

If the key doesn't exist or duplicates are allowed, associate the value with the key and return null, otherwise don't modify the map and return the current value associated with the key.

allowsDuplicates()

Return true if duplicates are allowed.

begin()

Return an iterator positioned at my first pair.

clear()

Remove all of my elements.

clone()

Return a shallow copy of myself.

copy(OrderedMap)

Become a shallow copy of an existing OrderedMap.

count(Object)

Return the number of key/value pairs that match a particular key.

countValues(Object)

Return the number of values that match a given object.

elements()

Return an Enumeration of my values

end()

Return an iterator positioned immediately after my last pair.

equalRange(Object)

Return a pair of iterators whose first element is equal to lowerBound() and whose second element is equal to upperBound().

equals(Object)

Return true if I'm equal to another object.

equals(OrderedMap)

Return true if I contain the same items in the same order as another OrderedMap.

find(Object)

Find a key/value pair based on its key and return its position.

finish()

Return an iterator positioned immediately afer my last pair.

get(Object)

Return the value associated with key, or null if the key does not exist.

getComparator()

Return my comparator.

hashCode()

Return my hash code for support of hashing containers

isEmpty()

Return true if I contain no entries.

keys()

Return an Enumeration of all my keys.

keys(Object)

Return an Enumeration of all my keys that are associated with a particular value.

lowerBound(Object)

Return an iterator positioned at the first location that a pair with a specified key could be inserted without violating the ordering criteria.

maxSize()

Return the maximum number of entries that I can contain.

put(Object, Object)

If the key doesn't exist, associate the value with the key and return null, otherwise replace the first value associated with the key and return the old value.

remove(Enumeration)

Remove the element at a particular position and return its value.

remove(Enumeration, Enumeration)

Remove the elements within a specified range, returning the first value of the key in that range.

remove(Object)

If I contain key/value pair(s) that matches a particular key, remove them and return the value of the first key removed, otherwise return null.

size()

Return the number of entries that I contain.

start()

Return an iterator positioned at my first pair.

swap(OrderedMap)

Swap my contents with another OrderedMap.

toString()

Return a string that describes me.

upperBound(Object)

Return an iterator positioned at the last location that a pair with a specified key could be inserted without violating the ordering criteria.

values(Object)

Return an Enumeration of all my values that are associated with a particular key.

  public OrderedMap()

Construct myself to be an empty OrderedMap that orders its keys based on their hash value and does not allow duplicates.

  public OrderedMap(boolean allowDuplicates)

Construct myself to be an empty OrderedMap that orders its keys based on their hash value and conditionally allows duplicates.

Parameters:

allowDuplicates - true if duplicates are allowed.

  public OrderedMap(BinaryPredicate comparator)

Construct myself to be an empty OrderedMap that orders its keys using a specified binary predicate and does not allow duplicates.

Parameters:

comparator - The predicate for ordering keys.

  public OrderedMap(BinaryPredicate comparator,
                    boolean allowDuplicates)

Construct myself to be an empty OrderedMap that orders its keys using a specified binary predicate and conditionally allows duplicates.

Parameters:

comparator - The predicate for ordering keys.

allowDuplicates - true if duplicates are allowed.

  public OrderedMap(OrderedMap map)

Construct myself to be a shallow copy of an existing OrderedMap.

Parameters:

map - The OrderedMap to copy.

  public boolean allowsDuplicates()

Return true if duplicates are allowed.

  public synchronized Object clone()

Return a shallow copy of myself.

Overrides:

clone in class Object

  public synchronized void copy(OrderedMap map)

Become a shallow copy of an existing OrderedMap.

Parameters:

map - The OrderedMap that I shall become a shallow copy of.

  public synchronized String toString()

Return a string that describes me.

Overrides:

toString in class Object

  public synchronized Enumeration elements()

Return an Enumeration of my values

Overrides:

elements in class Dictionary

  public synchronized ForwardIterator start()

Return an iterator positioned at my first pair.

  public synchronized ForwardIterator finish()

Return an iterator positioned immediately afer my last pair.

  public synchronized OrderedMapIterator begin()

Return an iterator positioned at my first pair.

  public synchronized OrderedMapIterator end()

Return an iterator positioned immediately after my last pair.

  public boolean isEmpty()

Return true if I contain no entries.

Overrides:

isEmpty in class Dictionary

  public int size()

Return the number of entries that I contain.

Overrides:

size in class Dictionary

  public int maxSize()

Return the maximum number of entries that I can contain.

  public boolean equals(Object object)

Return true if I'm equal to another object.

Parameters:

object - The object to compare myself against.

Overrides:

equals in class Object

  public synchronized boolean equals(OrderedMap map)

Return true if I contain the same items in the same order as another OrderedMap. Use equals() to compare the individual elements.

Parameters:

map - The OrderedMap to compare myself against.

  public int hashCode()

Return my hash code for support of hashing containers

Overrides:

hashCode in class Object

  public synchronized void swap(OrderedMap map)

Swap my contents with another OrderedMap.

Parameters:

map - The OrderedMap that I will swap my contents with.

  public synchronized void clear()

Remove all of my elements.

  public synchronized Object remove(Object key)

If I contain key/value pair(s) that matches a particular key, remove them and return the value of the first key removed, otherwise return null.

Parameters:

key - The key of the pair(s) to be removed.

Returns:

The value that was removed or null if none.

Overrides:

remove in class Dictionary

  public synchronized Object remove(Enumeration pos)

Remove the element at a particular position and return its value.

Parameters:

pos - An Enumeration positioned at the element to remove.

Returns:

The value that was removed or null if none.

Throws: IllegalArgumentException

is the Enumeration isn't an OrderedMapIterator for this OrderedMap object.

  public synchronized Object remove(Enumeration first,
                                    Enumeration last)

Remove the elements within a specified range, returning the first value of the key in that range.

Parameters:

first - An iterator positioned at the first element to remove.

last - An iterator positioned immediately after the last element to remove.

Throws: IllegalArgumentException

is the Enumeration isn't an OrderedMapIterator for this OrderedMap object.

  public synchronized OrderedMapIterator find(Object key)

Find a key/value pair based on its key and return its position. If the pair is not found, return end().

Parameters:

object - The object to locate.

  public synchronized int count(Object key)

Return the number of key/value pairs that match a particular key.

Parameters:

key - The key to match against.

  public synchronized int countValues(Object value)

Return the number of values that match a given object.

Parameters:

value - The value to match against.

  public synchronized OrderedMapIterator lowerBound(Object key)

Return an iterator positioned at the first location that a pair with a specified key could be inserted without violating the ordering criteria. If no such location is found, return an iterator positioned at end().

Parameters:

key - The key.

  public synchronized OrderedMapIterator upperBound(Object key)

Return an iterator positioned at the last location that a pair with a specified key could be inserted without violating the ordering criteria. If no such location is found, return an iterator positioned at end().

Parameters:

key - The key.

  public BinaryPredicate getComparator()

Return my comparator.

  public synchronized Object get(Object key)

Return the value associated with key, or null if the key does not exist.

Parameters:

key - The key to search against.

Overrides:

get in class Dictionary

  public synchronized Object put(Object key,
                                 Object value)

If the key doesn't exist, associate the value with the key and return null, otherwise replace the first value associated with the key and return the old value.

Parameters:

key - The key.

value - The value.

Throws: NullPointerException

If the key or value is null.

Overrides:

put in class Dictionary

  public Object add(Object object)

Assume that the specified object is a Pair whose first field is a key and whose second field is a value. If the key doesn't exist or duplicates are allowed, associate the value with the key and return null, otherwise don't modify the map and return the current value associated with the key.

Parameters:

object - The pair to add.

Throws: IllegalArgumentException

If the object is not a Pair

Throws: NullPointerException

If the object is null or if the first or second items in the pair are null.

  public Object add(Object key,
                    Object value)

If the key doesn't exist or duplicates are allowed, associate the value with the key and return null, otherwise don't modify the map and return the current value associated with the key.

Parameters:

key - The key.

value - The value.

Throws: NullPointerException

If the key or value is null.

  public synchronized Enumeration keys()

Return an Enumeration of all my keys.

Overrides:

keys in class Dictionary

  public synchronized Enumeration keys(Object value)

Return an Enumeration of all my keys that are associated with a particular value.

Parameters:

value - The value to match.

  public synchronized Enumeration values(Object key)

Return an Enumeration of all my values that are associated with a particular key.

Parameters:

key - The key to match.

  public synchronized Range equalRange(Object object)

Return a pair of iterators whose first element is equal to lowerBound() and whose second element is equal to upperBound().

Parameters:

object - The object whose bounds are to be found.

All Packages  Class Hierarchy  This Package  Previous  Next  Index