All Packages  Class Hierarchy  This Package  Previous  Next  Index

Class COM.objectspace.jgl.OrderedMultiSet

java.lang.Object
   |
   +----COM.objectspace.jgl.OrderedSet
           |
           +----COM.objectspace.jgl.OrderedMultiSet

public class OrderedMultiSet

extends OrderedSet

An OrderedMultiSet is a container that is optimized for fast associative lookup. Items are matched using equals(). When an item is inserted into a OrderedMultiSet, it is stored in a data structure that allows the item to be found very quickly. Within the data structure, the items are ordered according to a comparator object. By default, the comparator is a HashComparator that orders objects based on their hash value. An OrderedMultiSet may contain matching items.

OrderedMultiSets are useful when fast associate lookup is important and when index-based lookup is unnecessary.

Strictly speaking, there is no reason why null is not a valid entry. However, most comparators (including the default HashComparator) will fail and throw an exception if you attempt to add a null entry because they cast the entry 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.

Insertion does not affect iterators or references.

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

See Also:

OrderedSet, BinaryPredicate, SetOperations, OrderedSetExamples, OrderedSet

OrderedMultiSet()

Construct myself to be an empty OrderedMultiSet that orders elements based on their hash value.

OrderedMultiSet(BinaryPredicate)

Construct myself to be an empty OrderedMultiSet that orders elements using a specified binary predicate.

OrderedMultiSet(OrderedMultiSet)

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

clone()

Return a shallow copy of myself.

copy(OrderedMultiSet)

Become a shallow copy of an existing OrderedMultiSet.

equals(Object)

Return true if I'm equal to another object.

equals(OrderedMultiSet)

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

swap(OrderedMultiSet)

Swap my contents with another OrderedMultiSet.

toString()

Return a string that describes me.

  public OrderedMultiSet()

Construct myself to be an empty OrderedMultiSet that orders elements based on their hash value.

  public OrderedMultiSet(BinaryPredicate comparator)

Construct myself to be an empty OrderedMultiSet that orders elements using a specified binary predicate.

Parameters:

comparator - The predicate for ordering objects.

  public OrderedMultiSet(OrderedMultiSet set)

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

Parameters:

set - The OrderedMultiSet to copy.

  public synchronized Object clone()

Return a shallow copy of myself.

Overrides:

clone in class OrderedSet

  public synchronized void copy(OrderedMultiSet set)

Become a shallow copy of an existing OrderedMultiSet.

Parameters:

set - The OrderedMultiSet that I shall become a shallow copy of.

  public synchronized String toString()

Return a string that describes me.

Overrides:

toString in class OrderedSet

  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 OrderedSet

  public synchronized boolean equals(OrderedMultiSet set)

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

Parameters:

set - The OrderedMultiSet to compare myself against.

  public synchronized void swap(OrderedMultiSet set)

Swap my contents with another OrderedMultiSet.

Parameters:

set - The OrderedMultiSet that I will swap my contents with.

All Packages  Class Hierarchy  This Package  Previous  Next  Index