ostore.util
Class QSTreeSet

java.lang.Object
  |
  +--ostore.util.QSTreeSet

All Implemented Interfaces:

QuickSerializable

public class QSTreeSet

extends Object

implements QuickSerializable

A QSTreeSet is a wrapper class of TreeSet that implements QuickSerializable. All elements of the QSTreeSet must also be QuickSerializable. Most of the functionality from the TreeSet has not been ported. If you require the use of a missing method, implement it.

Version:

$Id: QSTreeSet.java,v 1.4 2003/03/18 01:01:19 jeffpang Exp $

Author:

Hakim Weatherspoon

Constructor Summary

QSTreeSet()
Constructs a QSTreeSet.

QSTreeSet(Collection c)
Constructs a new set containing the elements in the specified collection, sorted according to the elements' natural order.

QSTreeSet(InputBuffer buffer)
Constructs a QSTreeSet from its serialized form.

QSTreeSet(QSComparator c)

QSTreeSet(SortedSet s)
Constructs a new set containing the same elements as the given sorted set, sorted according to the same ordering.

Method Summary

boolean	add(QuickSerializable o) Adds the specified element to this set if it is not already present.
boolean	addAll(Collection c) Adds all of the elements in the specified collection to this set.
boolean	addAll(QSTreeSet c)
void	clear() Removes all of the elements from this set.
Object	clone() Create an exact copy of this QSTreeSet
Comparator	comparator() Returns the comparator used to order this sorted set, or null if this tree set uses its elements natural ordering.
boolean	contains(QuickSerializable o) Returns true if this set contains the specified element.
boolean	containsAll(Collection c) Returns true if this collection contains all of the elements in the specified collection.
boolean	containsAll(QSTreeSet c)
boolean	equals(Object o) Compare this QSTreeSet to another Object.
Object	first() Returns the first (lowest) element currently in this sorted set.
TreeSet	getTreeSet()
int	hashCode() Return a hashcode, specified and generated as in TreeSet.
SortedSet	headSet(QuickSerializable toElement) Returns a view of the portion of this set whose elements are strictly less than toElement.
boolean	isEmpty() Returns true if this set contains no elements.
Iterator	iterator() Returns an iterator over the elements in this set.
QuickSerializable	last() Returns the last (highest) element currently in this sorted set.
boolean	remove(QuickSerializable o) Removes the given element from this set if it is present.
boolean	removeAll(Collection c) Removes from this set all of its elements that are contained in the specified collection (optional operation).
boolean	removeAll(QSTreeSet c)
void	serialize(OutputBuffer buffer) Add the object to the buffer.
int	size() Returns the number of elements in this set (its cardinality).
SortedSet	subSet(QuickSerializable fromElement, QuickSerializable toElement) Returns a view of the portion of this set whose elements range from fromElement, inclusive, to toElement, exclusive.
SortedSet	tailSet(QuickSerializable fromElement) Returns a view of the portion of this set whose elements are greater than or equal to fromElement.
QuickSerializable[]	toArray() Returns an array containing all of the elements in this collection.
QuickSerializable[]	toArray(QuickSerializable[] a) Returns an array with a runtime type is that of the specified array and that contains all of the elements in this collection.
String	toString() Produce a human-readable version of this QSVector, which includes all the elements.

Methods inherited from class java.lang.Object

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

Constructor Detail

QSTreeSet

public QSTreeSet()

Constructs a QSTreeSet.

QSTreeSet

public QSTreeSet(QSComparator c)

QSTreeSet

public QSTreeSet(InputBuffer buffer)
          throws QSException

Constructs a QSTreeSet from its serialized form.

Parameters:

buffer - serialized form of object.

QSTreeSet

public QSTreeSet(SortedSet s)
          throws QSException

Constructs a new set containing the same elements as the given sorted set, sorted according to the same ordering.

Parameters:

s - sorted set whose elements will comprise the new set.

Throws:

QSException - if any of the elements are not instanceof QuickSerializable.

QSTreeSet

public QSTreeSet(Collection c)
          throws QSException

Constructs a new set containing the elements in the specified collection, sorted according to the elements' natural order. All keys inserted into the set must implement the Comparable interface. Furthermore, all such keys must be mutually comparable: k1.compareTo(k2) must not throw a ClassCastException for any elements k1 and k2 in the set.

Parameters:

c - The elements that will comprise the new set.

Throws:

ClassCastException - if the keys in the given collection are not comparable, or are not mutually comparable.

QSException - if any of the elements are not instanceof QuickSerializable.

Method Detail

serialize

public void serialize(OutputBuffer buffer)

Description copied from interface: QuickSerializable

Add the object to the buffer.

Specified by:

serialize in interface QuickSerializable

Parameters:

buffer - the output buffer to add the object to

getTreeSet

public TreeSet getTreeSet()

hashCode

public int hashCode()

Return a hashcode, specified and generated as in TreeSet.

Overrides:

hashCode in class Object

Returns:

a hashcode which incorporates the hashcodes of all the elements in the QSTreeSet

equals

public boolean equals(Object o)

Compare this QSTreeSet to another Object.

Overrides:

equals in class Object

Returns:

true iff the other Object is also a QSTreeSet and contains equal elements.

clone

public Object clone()
             throws CloneNotSupportedException

Create an exact copy of this QSTreeSet

Overrides:

clone in class Object

Returns:

new QSTreeSet identical to this one. this is a shallow-copy

CloneNotSupportedException

toString

public String toString()

Produce a human-readable version of this QSVector, which includes all the elements.

Overrides:

toString in class Object

Returns:

a String representation of this QSTreeSet.

iterator

public Iterator iterator()

Returns an iterator over the elements in this set. The elements are returned in ascending order.

Returns:

an iterator over the elements in this set.

size

public int size()

Returns the number of elements in this set (its cardinality).

Returns:

the number of elements in this set (its cardinality).

isEmpty

public boolean isEmpty()

Returns true if this set contains no elements.

Returns:

true if this set contains no elements.

contains

public boolean contains(QuickSerializable o)

Returns true if this set contains the specified element.

Parameters:

o - the object to be checked for containment in this set.

Returns:

true if this set contains the specified element.

Throws:

ClassCastException - if the specified object cannot be compared with the elements currently in the set.

add

public boolean add(QuickSerializable o)

Adds the specified element to this set if it is not already present.

Parameters:

o - element to be added to this set.

Returns:

true if the set did not already contain the specified element.

Throws:

ClassCastException - if the specified object cannot be compared with the elements currently in the set.

remove

public boolean remove(QuickSerializable o)

Removes the given element from this set if it is present.

Parameters:

o - object to be removed from this set, if present.

Returns:

true if the set contained the specified element.

Throws:

ClassCastException - if the specified object cannot be compared with the elements currently in the set.

clear

public void clear()

Removes all of the elements from this set.

addAll

public boolean addAll(Collection c)
               throws QSException

Adds all of the elements in the specified collection to this set.

Parameters:

c - elements to be added

Returns:

true if this set changed as a result of the call.

Throws:

ClassCastException - if the elements provided cannot be compared with the elements currently in the set.

QSException - if any of the elements are not instanceof QuickSerializable.

addAll

public boolean addAll(QSTreeSet c)
               throws QSException

QSException

subSet

public SortedSet subSet(QuickSerializable fromElement,
                        QuickSerializable toElement)

Returns a view of the portion of this set whose elements range from fromElement, inclusive, to toElement, exclusive. (If fromElement and toElement are equal, the returned sorted set is empty.) The returned sorted set is backed by this set, so changes in the returned sorted set are reflected in this set, and vice-versa. The returned sorted set supports all optional Set operations.

The sorted set returned by this method will throw an IllegalArgumentException if the user attempts to insert an element outside the specified range.

Note: this method always returns a half-open range (which includes its low endpoint but not its high endpoint). If you need a closed range (which includes both endpoints), and the element type allows for calculation of the successor a given value, merely request the subrange from lowEndpoint to successor(highEndpoint). For example, suppose that s is a sorted set of strings. The following idiom obtains a view containing all of the strings in s from low to high, inclusive:

     SortedSet sub = s.subSet(low, high+"\0");
 

A similar technique can be used to generate an open range (which contains neither endpoint). The following idiom obtains a view containing all of the strings in s from low to high, exclusive:

     SortedSet sub = s.subSet(low+"\0", high);
 

Parameters:

fromElement - low endpoint (inclusive) of the subSet.

toElement - high endpoint (exclusive) of the subSet.

Returns:

a view of the portion of this set whose elements range from fromElement, inclusive, to toElement, exclusive.

Throws:

ClassCastException - if fromElement and toElement cannot be compared to one another using this set's comparator (or, if the set has no comparator, using natural ordering).

IllegalArgumentException - if fromElement is greater than toElement.

NullPointerException - if fromElement or toElement is null and this set uses natural order, or its comparator does not tolerate null elements.

headSet

public SortedSet headSet(QuickSerializable toElement)

Returns a view of the portion of this set whose elements are strictly less than toElement. The returned sorted set is backed by this set, so changes in the returned sorted set are reflected in this set, and vice-versa. The returned sorted set supports all optional set operations.

The sorted set returned by this method will throw an IllegalArgumentException if the user attempts to insert an element greater than or equal to toElement.

Note: this method always returns a view that does not contain its (high) endpoint. If you need a view that does contain this endpoint, and the element type allows for calculation of the successor a given value, merely request a headSet bounded by successor(highEndpoint). For example, suppose that s is a sorted set of strings. The following idiom obtains a view containing all of the strings in s that are less than or equal to high:

 SortedSet head = s.headSet(high+"\0");

Parameters:

toElement - high endpoint (exclusive) of the headSet.

Returns:

a view of the portion of this set whose elements are strictly less than toElement.

Throws:

ClassCastException - if toElement is not compatible with this set's comparator (or, if the set has no comparator, if toElement does not implement Comparable).

IllegalArgumentException - if this set is itself a subSet, headSet, or tailSet, and toElement is not within the specified range of the subSet, headSet, or tailSet.

NullPointerException - if toElement is null and this set uses natural ordering, or its comparator does not tolerate null elements.

tailSet

public SortedSet tailSet(QuickSerializable fromElement)

Returns a view of the portion of this set whose elements are greater than or equal to fromElement. The returned sorted set is backed by this set, so changes in the returned sorted set are reflected in this set, and vice-versa. The returned sorted set supports all optional set operations.

The sorted set returned by this method will throw an IllegalArgumentException if the user attempts to insert an element less than fromElement. Note: this method always returns a view that contains its (low) endpoint. If you need a view that does not contain this endpoint, and the element type allows for calculation of the successor a given value, merely request a tailSet bounded by successor(lowEndpoint). For example, suppose that s is a sorted set of strings. The following idiom obtains a view containing all of the strings in s that are strictly greater than low:

     SortedSet tail = s.tailSet(low+"\0");
 

Parameters:

fromElement - low endpoint (inclusive) of the tailSet.

Returns:

a view of the portion of this set whose elements are greater than or equal to fromElement.

Throws:

ClassCastException - if fromElement is not compatible with this set's comparator (or, if the set has no comparator, if fromElement does not implement Comparable).

IllegalArgumentException - if this set is itself a subSet, headSet, or tailSet, and fromElement is not within the specified range of the subSet, headSet, or tailSet.

NullPointerException - if fromElement is null and this set uses natural ordering, or its comparator does not tolerate null elements.

containsAll

public boolean containsAll(Collection c)
                    throws QSException

Returns true if this collection contains all of the elements in the specified collection.

This implementation iterates over the specified collection, checking each element returned by the iterator in turn to see if it's contained in this collection. If all elements are so contained true is returned, otherwise false.

Parameters:

c - collection to be checked for containment in this collection.

Returns:

true if this collection contains all of the elements in the specified collection.

QSException

See Also:

contains(QuickSerializable)

containsAll

public boolean containsAll(QSTreeSet c)
                    throws QSException

QSException

removeAll

public boolean removeAll(Collection c)
                  throws QSException

Removes from this set all of its elements that are contained in the specified collection (optional operation).

This implementation determines which is the smaller of this set and the specified collection, by invoking the size method on each. If this set has fewer elements, then the implementation iterates over this set, checking each element returned by the iterator in turn to see if it is contained in the specified collection. If it is so contained, it is removed from this set with the iterator's remove method. If the specified collection has fewer elements, then the implementation iterates over the specified collection, removing from this set each element returned by the iterator, using this set's remove method.

Note that this implementation will throw an UnsupportedOperationException if the iterator returned by the iterator method does not implement the remove method.

Parameters:

c - elements to be removed from this set.

Returns:

true if this set changed as a result of the call.

Throws:

UnsupportedOperationException - removeAll is not supported by this set.

QSException - if any of the elements are not instanceof QuickSerializable.

See Also:

remove(QuickSerializable), contains(QuickSerializable)

removeAll

public boolean removeAll(QSTreeSet c)
                  throws QSException

QSException

comparator

public Comparator comparator()

Returns the comparator used to order this sorted set, or null if this tree set uses its elements natural ordering.

Returns:

the comparator used to order this sorted set, or null if this tree set uses its elements natural ordering.

first

public Object first()

Returns the first (lowest) element currently in this sorted set.

Returns:

the first (lowest) element currently in this sorted set.

Throws:

NoSuchElementException - sorted set is empty.

last

public QuickSerializable last()

Returns the last (highest) element currently in this sorted set.

Returns:

the last (highest) element currently in this sorted set.

Throws:

NoSuchElementException - sorted set is empty.

toArray

public QuickSerializable[] toArray()

Returns an array containing all of the elements in this collection. If the collection makes any guarantees as to what order its elements are returned by its iterator, this method must return the elements in the same order. The returned array will be "safe" in that no references to it are maintained by the collection. (In other words, this method must allocate a new array even if the collection is backed by an Array). The caller is thus free to modify the returned array.

This implementation allocates the array to be returned, and iterates over the elements in the collection, storing each object reference in the next consecutive element of the array, starting with element 0.

Returns:

an array containing all of the elements in this collection.

toArray

public QuickSerializable[] toArray(QuickSerializable[] a)

Returns an array with a runtime type is that of the specified array and that contains all of the elements in this collection. If the collection fits in the specified array, it is returned therein. Otherwise, a new array is allocated with the runtime type of the specified array and the size of this collection.

If the collection fits in the specified array with room to spare (i.e., the array has more elements than the collection), the element in the array immediately following the end of the collection is set to null. This is useful in determining the length of the collection only if the caller knows that the collection does not contain any null elements.)

If this collection makes any guarantees as to what order its elements are returned by its iterator, this method must return the elements in the same order.

This implementation checks if the array is large enough to contain the collection; if not, it allocates a new array of the correct size and type (using reflection). Then, it iterates over the collection, storing each object reference in the next consecutive element of the array, starting with element 0. If the array is larger than the collection, a null is stored in the first location after the end of the collection.

Parameters:

a - the array into which the elements of the collection are to be stored, if it is big enough; otherwise, a new array of the same runtime type is allocated for this purpose.

Returns:

an array containing the elements of the collection.

Throws:

NullPointerException - if the specified array is null.

ArrayStoreException - if the runtime type of the specified array is not a supertype of the runtime type of every element in this collection.