messif.utility
Class SortedCollection<T>

java.lang.Object
  extended by messif.utility.SortedArrayData<T,T>
      extended by messif.utility.SortedCollection<T>
Type Parameters:
T - the type of objects stored in this collection
All Implemented Interfaces:
java.io.Serializable, java.lang.Cloneable, java.lang.Iterable<T>, java.util.Collection<T>
Direct Known Subclasses:
RankedSortedCollection

public class SortedCollection<T>
extends SortedArrayData<T,T>
implements java.util.Collection<T>, java.io.Serializable, java.lang.Cloneable

Implementation of a sorted collection. The order is maintained using the comparator specified in the constructor. Complexity of insertion is O(log n).

See Also:
Serialized Form

Constructor Summary
SortedCollection()
          Constructs an empty collection.
SortedCollection(java.util.Comparator<? super T> comparator)
          Constructs an empty collection.
SortedCollection(int initialCapacity)
          Constructs an empty collection with the specified initial capacity.
SortedCollection(int initialCapacity, java.util.Comparator<? super T> comparator)
          Constructs an empty collection with the specified initial capacity.
SortedCollection(int initialCapacity, int maximalCapacity, java.util.Comparator<? super T> comparator)
          Constructs an empty collection with the specified initial and maximal capacity.
 
Method Summary
 boolean add(T e)
          Adds the specified element to this list.
 boolean addAll(java.util.Collection<? extends T> c)
          Add all of the elements in the specified collection to this list.
 void clear()
          Removes all of the elements from this list.
 java.lang.Object clone()
          Returns a shallow copy of this SortedCollection instance.
protected  int compare(T key, T object)
          Compares its two arguments for order.
 boolean contains(java.lang.Object o)
          Returns true if this list contains the specified element.
 boolean containsAll(java.util.Collection<?> c)
          Returns true if this collection contains all of the elements in the specified collection.
protected  T get(int index)
          Returns the element at the specified position in this collection.
 int getMaximalCapacity()
          Returns the maximal capatity of this collection.
 boolean isEmpty()
          Returns true if this collection contains no elements.
 boolean isFull()
          Returns true if this collection contains the maximal number of elements.
 java.util.Iterator<T> iterator()
          Returns an iterator over the elements in this collection.
 java.util.Iterator<T> iterator(int skip, int count)
          Returns an iterator over the elements in this collection skipping the first skip items and returning only count elements.
 T popLast()
          Deprecated. Use removeLast() method instead
protected  boolean remove(int index)
          Removes the element at the specified position in this collection.
 boolean remove(java.lang.Object o)
          Removes the first occurrence of the specified element from this list, if it is present.
 boolean removeAll(java.util.Collection<?> c)
          Removes all of this collection's elements that are also contained in the specified collection.
 T removeFirst()
          Removes and returns the first element of this collection according to the order specified by the comparator.
 T removeLast()
          Removes and returns the last element of this collection according to the order specified by the comparator.
 boolean retainAll(java.util.Collection<?> c)
          Retains only the elements in this collection that are contained in the specified collection.
 int size()
          Returns the number of elements in this collection.
 java.lang.Object[] toArray()
          Returns an array containing all of the elements in this list in proper sequence (from first to last element).
<E> E[]
toArray(E[] array)
          Returns an array containing all of the elements in this list in proper sequence (from first to last element); the runtime type of the returned array is that of the specified array.
 java.lang.String toString()
          Returns a string representation of this collection.
 
Methods inherited from class messif.utility.SortedArrayData
binarySearch, first, fullSearch, indexOf, last, mergeSort
 
Methods inherited from class java.lang.Object
equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface java.util.Collection
equals, hashCode
 

Constructor Detail

SortedCollection

public SortedCollection(int initialCapacity,
                        int maximalCapacity,
                        java.util.Comparator<? super T> comparator)
                 throws java.lang.IllegalArgumentException
Constructs an empty collection with the specified initial and maximal capacity.

Parameters:
initialCapacity - the initial capacity of the collection
maximalCapacity - the maximal capatity of the collection
comparator - the comparator that defines ordering
Throws:
java.lang.IllegalArgumentException - if the specified initial or maximal capacity is invalid

SortedCollection

public SortedCollection(int initialCapacity,
                        java.util.Comparator<? super T> comparator)
                 throws java.lang.IllegalArgumentException
Constructs an empty collection with the specified initial capacity. The capacity of this collection is not limited.

Parameters:
initialCapacity - the initial capacity of the collection
comparator - the comparator that defines ordering
Throws:
java.lang.IllegalArgumentException - if the specified initial or maximal capacity is invalid

SortedCollection

public SortedCollection(java.util.Comparator<? super T> comparator)
                 throws java.lang.IllegalArgumentException
Constructs an empty collection. The initial capacity of the collection is set to 16 and maximal capacity is not limited.

Parameters:
comparator - the comparator that defines ordering
Throws:
java.lang.IllegalArgumentException - if the specified initial or maximal capacity is invalid

SortedCollection

public SortedCollection(int initialCapacity)
                 throws java.lang.IllegalArgumentException
Constructs an empty collection with the specified initial capacity. The order is defined using the natural order of items. The capacity of this collection is not limited.

Parameters:
initialCapacity - the initial capacity of the collection
Throws:
java.lang.IllegalArgumentException - if the specified initial or maximal capacity is invalid

SortedCollection

public SortedCollection()
                 throws java.lang.IllegalArgumentException
Constructs an empty collection. The order is defined using the natural order of items. The initial capacity of the collection is set to 16 and maximal capacity is not limited.

Throws:
java.lang.IllegalArgumentException - if the specified initial or maximal capacity is invalid
Method Detail

compare

protected int compare(T key,
                      T object)
               throws java.lang.ClassCastException
Description copied from class: SortedArrayData
Compares its two arguments for order. Returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.

Specified by:
compare in class SortedArrayData<T,T>
Parameters:
key - the key to indexCompare
object - the object to be compared
Returns:
a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.
Throws:
java.lang.ClassCastException - if the arguments' types prevent them from being compared by this comparator.

size

public int size()
Returns the number of elements in this collection.

Specified by:
size in interface java.util.Collection<T>
Specified by:
size in class SortedArrayData<T,T>
Returns:
the number of elements in this collection

isEmpty

public boolean isEmpty()
Returns true if this collection contains no elements.

Specified by:
isEmpty in interface java.util.Collection<T>
Returns:
true if this collection contains no elements

isFull

public boolean isFull()
Returns true if this collection contains the maximal number of elements.

Returns:
true if this collection contains the maximal number of elements

getMaximalCapacity

public int getMaximalCapacity()
Returns the maximal capatity of this collection.

Returns:
the maximal capatity of this collection

contains

public boolean contains(java.lang.Object o)
Returns true if this list contains the specified element. More formally, returns true if and only if this list contains at least one element e such that (o==null ? e==null : o.equals(e)).

Specified by:
contains in interface java.util.Collection<T>
Parameters:
o - element whose presence in this list is to be tested
Returns:
true if this list contains the specified element

containsAll

public boolean containsAll(java.util.Collection<?> c)
Returns true if this collection contains all of the elements in the specified collection.

Specified by:
containsAll in interface java.util.Collection<T>
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
Throws:
java.lang.NullPointerException - if the specified collection is null
See Also:
contains(Object)

get

protected final T get(int index)
Returns the element at the specified position in this collection.

Specified by:
get in class SortedArrayData<T,T>
Parameters:
index - index of the element to return
Returns:
the element at the specified position in this collection
Throws:
java.lang.IndexOutOfBoundsException - if the index is out of range (index < 0 || index >= size())

removeLast

public T removeLast()
             throws java.util.NoSuchElementException
Removes and returns the last element of this collection according to the order specified by the comparator.

Returns:
the last element in this collection
Throws:
java.util.NoSuchElementException - if the collection is empty

popLast

@Deprecated
public T popLast()
          throws java.util.NoSuchElementException
Deprecated. Use removeLast() method instead

Removes and returns the last element of this collection according to the order specified by the comparator.

Returns:
the last element in this collection
Throws:
java.util.NoSuchElementException - if the collection is empty

removeFirst

public T removeFirst()
              throws java.util.NoSuchElementException
Removes and returns the first element of this collection according to the order specified by the comparator.

Returns:
the first element in this collection
Throws:
java.util.NoSuchElementException - if the collection is empty

clone

public java.lang.Object clone()
                       throws java.lang.CloneNotSupportedException
Returns a shallow copy of this SortedCollection instance. The elements themselves are not copied and the comparator is shared.

Overrides:
clone in class java.lang.Object
Returns:
a clone of this SortedCollection instance
Throws:
java.lang.CloneNotSupportedException

toArray

public java.lang.Object[] toArray()
Returns an array containing all of the elements in this list in proper sequence (from first to last element).

The returned array will be "safe" in that no references to it are maintained by this list. (In other words, this method must allocate a new array). The caller is thus free to modify the returned array.

This method acts as bridge between array-based and collection-based APIs.

Specified by:
toArray in interface java.util.Collection<T>
Returns:
an array containing all of the elements in this list in proper sequence

toArray

public <E> E[] toArray(E[] array)
Returns an array containing all of the elements in this list in proper sequence (from first to last element); the runtime type of the returned array is that of the specified array. If the list 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 list.

If the list fits in the specified array with room to spare (i.e., the array has more elements than the list), 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 list only if the caller knows that the list does not contain any null elements.)

Specified by:
toArray in interface java.util.Collection<T>
Type Parameters:
E - the type of array components
Parameters:
array - the array into which the elements of the list 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 list
Throws:
java.lang.ArrayStoreException - if the runtime type of the specified array is not a supertype of the runtime type of every element in this list
java.lang.NullPointerException - if the specified array is null

add

public boolean add(T e)
Adds the specified element to this list. The element is added according the to order defined by the comparator.

Specified by:
add in interface java.util.Collection<T>
Parameters:
e - element to be appended to this list
Returns:
true (as specified by Collection.add(E))

remove

public boolean remove(java.lang.Object o)
Removes the first occurrence of the specified element from this list, if it is present. If the list does not contain the element, it is unchanged. More formally, removes the element with the lowest index i such that (o==null ? get(i)==null : o.equals(get(i))) (if such an element exists). Returns true if this list contained the specified element (or equivalently, if this list changed as a result of the call).

Specified by:
remove in interface java.util.Collection<T>
Parameters:
o - element to be removed from this list, if present
Returns:
true if this list contained the specified element

remove

protected boolean remove(int index)
Removes the element at the specified position in this collection.

Parameters:
index - index of the element to remove
Returns:
false if the object was not removed (e.g. because there is no object with this index)

addAll

public boolean addAll(java.util.Collection<? extends T> c)
Add all of the elements in the specified collection to this list. The elements are added according the to order defined by the comparator.

Specified by:
addAll in interface java.util.Collection<T>
Parameters:
c - collection containing elements to be added to this list
Returns:
true if this list changed as a result of the call
Throws:
java.lang.NullPointerException - if the specified collection is null

removeAll

public boolean removeAll(java.util.Collection<?> c)
Removes all of this collection's elements that are also contained in the specified collection. After this call returns, this collection will contain no elements in common with the specified collection.

Specified by:
removeAll in interface java.util.Collection<T>
Parameters:
c - collection containing elements to be removed from this collection
Returns:
true if this collection changed as a result of the call
Throws:
java.lang.NullPointerException - if the specified collection is null
See Also:
remove(Object), contains(Object)

retainAll

public boolean retainAll(java.util.Collection<?> c)
Retains only the elements in this collection that are contained in the specified collection. In other words, removes from this collection all of its elements that are not contained in the specified collection.

Specified by:
retainAll in interface java.util.Collection<T>
Parameters:
c - collection containing elements to be retained in this collection
Returns:
true if this collection changed as a result of the call
Throws:
java.lang.NullPointerException - if the specified collection is null
See Also:
remove(Object), contains(Object)

clear

public void clear()
Removes all of the elements from this list. The list will be empty after this call returns.

Specified by:
clear in interface java.util.Collection<T>

toString

public java.lang.String toString()
Returns a string representation of this collection. The string representation consists of a list of the collection's elements in the order defined by the comparator, enclosed in square brackets ("[]"). Adjacent elements are separated by the characters ", " (comma and space). Elements are converted to strings as by String.valueOf(Object).

Overrides:
toString in class java.lang.Object
Returns:
a string representation of this collection

iterator

public java.util.Iterator<T> iterator()
Returns an iterator over the elements in this collection. Their order is defined by the comparator.

Specified by:
iterator in interface java.lang.Iterable<T>
Specified by:
iterator in interface java.util.Collection<T>
Returns:
an iterator over the elements in this collection

iterator

public java.util.Iterator<T> iterator(int skip,
                                      int count)
Returns an iterator over the elements in this collection skipping the first skip items and returning only count elements. If count is less than or equal to zero, all objects from the collection (except for skip) are returned. Note that their order is defined by the comparator.

Parameters:
skip - number of items to skip
count - number of items to iterate (maximally, can be less)
Returns:
an iterator over the elements in this collection