All Packages  Class Hierarchy  This Package  Previous  Next  Index

Class com.objectspace.jgl.OrderedSet

java.lang.Object
   |
   +----com.objectspace.jgl.OrderedSet

public class OrderedSet

extends Object

implements Set

OrderedSets 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 one) 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 uses 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:

Set, BinaryPredicate, SetOperations, OrderedSet examples

OrderedSet()

Construct myself to be an empty OrderedSet that orders elements based on their hash value and does not allow duplicates.

OrderedSet(BinaryPredicate)

Construct myself to be an empty OrderedSet that orders elements using a specified binary predicate and does not allow duplicates.

OrderedSet(BinaryPredicate, boolean)

Construct myself to be an empty OrderedSet that orders elements using a specified binary predicate and conditionally allows duplicates.

OrderedSet(boolean)

Construct myself to be an empty OrderedSet that orders elements based on their hash value and conditionally allows duplicates.

OrderedSet(OrderedSet)

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

add(Object)

If the object doesn't exist or duplicates are allowed, add the object and return null, otherwise don't modify the set and return the matching object.

allowsDuplicates()

Return true if duplicates are allowed.

begin()

Return an iterator positioned at my first item.

clear()

Remove all of my elements.

clone()

Return a shallow copy of myself.

copy(OrderedSet)

Become a shallow copy of an existing OrderedSet.

count(Object)

Return the number of items that match a particular object.

difference(OrderedSet)

Return a new OrderedSet that contains the elements that are in me but not in a specified set.

elements()

Return an Enumeration of my components.

end()

Return an iterator positioned immediately after my last item.

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

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

find(Object)

Find an object and return its position.

finish()

Return an iterator positioned immediately afer my last item.

get(Object)

Return the first object that matches the given object, or null if no match exists.

getComparator()

Return my comparator.

hashCode()

Return my hash code for support of hashing containers

intersection(OrderedSet)

Return a new OrderedSet that contains the elements that are both in me and in a specified set.

isEmpty()

Return true if I contain no entries.

lowerBound(Object)

Return an iterator positioned at the first location that a particular object could be inserted without violating the ordering criteria.

maxSize()

Return the maximum number of entries that I can contain.

properSubsetOf(OrderedSet)

Return true if every element in me is also in a specified OrderedSet and I'm smaller than the specified OrderedSet.

put(Object)

If the object doesn't exist, add the object and return null, otherwise replace the first object that matches and return the old object.

remove(Enumeration)

Remove the element at a particular position.

remove(Enumeration, Enumeration)

Remove the elements within a specified range.

remove(Object)

Remove all objects that match the given object.

remove(Object, int)

Remove at most a given number of objects that match the given object.

size()

Return the number of entries that I contain.

start()

Return an iterator positioned at my first item.

subsetOf(OrderedSet)

Return true if every element in me is also in a specified OrderedSet.

swap(OrderedSet)

Swap my contents with another OrderedSet.

symmetricDifference(OrderedSet)

Return a new OrderedSet that contains the elements that are either in me or in a specified OrderedSet, but not both.

toString()

Return a string that describes me.

union(OrderedSet)

Return a new OrderedSet that contains all of my elements and all of the elements in a specified OrderedSet.

upperBound(Object)

Return an iterator positioned at the last location that a particular object could be inserted without violating the ordering criteria.

 public OrderedSet()

Construct myself to be an empty OrderedSet that orders elements based on their hash value and does not allow duplicates.

 public OrderedSet(boolean allowDuplicates)

Construct myself to be an empty OrderedSet that orders elements based on their hash value and conditionally allows duplicates.

Parameters:

allowDuplicates - true if duplicates are allowed.

 public OrderedSet(BinaryPredicate comparator)

Construct myself to be an empty OrderedSet that orders elements using a specified binary predicate and does not allow duplicates.

Parameters:

comparator - The predicate for ordering objects.

 public OrderedSet(BinaryPredicate comparator,
                   boolean allowDuplicates)

Construct myself to be an empty OrderedSet that orders elements using a specified binary predicate and conditionally allows duplicates.

Parameters:

comparator - The predicate for ordering objects.

allowDuplicates - true if duplicates are allowed.

 public OrderedSet(OrderedSet set)

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

Parameters:

set - The OrderedSet 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(OrderedSet set)

Become a shallow copy of an existing OrderedSet.

Parameters:

set - The OrderedSet 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 components.

 public ForwardIterator start()

Return an iterator positioned at my first item.

 public ForwardIterator finish()

Return an iterator positioned immediately afer my last item.

 public synchronized OrderedSetIterator begin()

Return an iterator positioned at my first item.

 public synchronized OrderedSetIterator end()

Return an iterator positioned immediately after my last item.

 public boolean isEmpty()

Return true if I contain no entries.

 public int size()

Return the number of entries that I contain.

 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(OrderedSet set)

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

Parameters:

set - The OrderedSet to compare myself against.

 public synchronized int hashCode()

Return my hash code for support of hashing containers

Overrides:

hashCode in class Object

 public synchronized void swap(OrderedSet set)

Swap my contents with another OrderedSet.

Parameters:

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

 public synchronized void clear()

Remove all of my elements.

 public synchronized int remove(Object object)

Remove all objects that match the given object.

Parameters:

object - The object to match for removals

Returns:

Return The number of objects removed.

 public synchronized int remove(Object object,
                                int count)

Remove at most a given number of objects that match the given object.

Parameters:

object - The object to match for removals

count - The maximum number of objects to remove.

Returns:

Return The number of objects removed.

 public synchronized Object remove(Enumeration e)

Remove the element at a particular position.

Parameters:

e - An Enumeration positioned at the element to remove.

Returns:

The object that was removed or null if none

Throws: IllegalArgumentException

if the Enumeration isn't a OrderedSetIterator for this OrderedSet object.

 public synchronized int remove(Enumeration first,
                                Enumeration last)

Remove the elements within a specified range.

Parameters:

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

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

Returns:

Return the nubmer of values removed.

Throws: IllegalArgumentException

is the Enumeration isn't a OrderedSetIterator for this OrderedSet object.

 public synchronized OrderedSetIterator find(Object object)

Find an object and return its position. If the object is not found, return end().

Parameters:

object - The object to locate.

 public synchronized int count(Object object)

Return the number of items that match a particular object.

Parameters:

object - The object to match against.

 public synchronized OrderedSetIterator lowerBound(Object object)

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

Parameters:

object - The object in question.

 public synchronized OrderedSetIterator upperBound(Object object)

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

Parameters:

object - The object in question.

 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.

 public BinaryPredicate getComparator()

Return my comparator.

 public synchronized Object add(Object object)

If the object doesn't exist or duplicates are allowed, add the object and return null, otherwise don't modify the set and return the matching object.

Parameters:

object - The object to be added.

Throws: NullPointerException

If the value of the object is equal to null.

 public synchronized Object get(Object object)

Return the first object that matches the given object, or null if no match exists.

Parameters:

object - The object to match against.

 public synchronized Object put(Object object)

If the object doesn't exist, add the object and return null, otherwise replace the first object that matches and return the old object.

Parameters:

object - The object to add.

Throws: NullPointerException

If the value of the object is equal to null.

 public synchronized OrderedSet union(OrderedSet set)

Return a new OrderedSet that contains all of my elements and all of the elements in a specified OrderedSet.

Parameters:

set - The OrderedSet to union myself with.

Throws: InvalidOperationException

if set is in multi-mode.

See Also:

setUnion

 public synchronized OrderedSet intersection(OrderedSet set)

Return a new OrderedSet that contains the elements that are both in me and in a specified set.

Parameters:

set - The OrderedSet to intersect myself with.

See Also:

setIntersection

 public synchronized OrderedSet difference(OrderedSet set)

Return a new OrderedSet that contains the elements that are in me but not in a specified set.

Parameters:

set - The OrderedSet to difference myself with.

See Also:

setDifference

 public synchronized OrderedSet symmetricDifference(OrderedSet set)

Return a new OrderedSet that contains the elements that are either in me or in a specified OrderedSet, but not both.

Parameters:

set - The OrderedSet to symmetric difference myself with.

See Also:

setSymmetricDifference

 public synchronized boolean subsetOf(OrderedSet set)

Return true if every element in me is also in a specified OrderedSet.

Parameters:

set - The OrderedSet to test against.

See Also:

includes

 public synchronized boolean properSubsetOf(OrderedSet set)

Return true if every element in me is also in a specified OrderedSet and I'm smaller than the specified OrderedSet.

Parameters:

set - The OrderedSet to test against.

All Packages  Class Hierarchy  This Package  Previous  Next  Index