messif.utility
Class SortedArrayData<K,T>

java.lang.Object
  messif.utility.SortedArrayData<K,T>

Type Parameters:

K - the type of keys this array is ordered by

T - the type of objects stored in this array

Direct Known Subclasses:

AbstractArrayIndex, LongStorageMemoryIndex, SortedCollection

public abstract class SortedArrayData<K,T>
extends java.lang.Object

Abstract implementation of a basic sorted array data. The order is maintained by the compare(K, T) method. Methods for binary search with O(log n) complexity as well as some basic collection operations are provided.

Constructor Summary

SortedArrayData()

Method Summary

protected int	binarySearch(K key, int low, int high, boolean indicateFailure) Searches a range in this collection of objects for the specified value using the binary search algorithm.
protected abstract int	compare(K key, T object) Compares its two arguments for order.
T	first() Returns the last element of this collection according to the order specified by the comparator.
protected <C> int	fullSearch(IndexComparator<C,T> comparator, C key, int low, int high) Searches a range in this collection for objects that are equal to the specified key.
protected abstract T	get(int index) Returns the element at the specified position in this collection.
protected int	indexOf(java.lang.Object o) Returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element.
T	last() Returns the last element of this collection according to the order specified by the comparator.
static <T> void	mergeSort(T[] items1, int from1, int to1, T[] items2, int from2, int to2, java.util.Comparator<T> comparator, T[] destination, int fromDest, int toDest) Merges two sorted arrays into the destination array using the specified comparator.
abstract int	size() Returns the number of elements in this collection.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

SortedArrayData

public SortedArrayData()

Method Detail

size

public abstract int size()

Returns the number of elements in this collection.

Returns:

the number of elements in this collection

get

protected abstract T get(int index)
                  throws java.lang.IndexOutOfBoundsException,
                         java.lang.IllegalStateException

Returns the element at the specified position in this collection.

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

java.lang.IllegalStateException - if the object at position index cannot be accessed

compare

protected abstract int compare(K key,
                               T object)
                        throws java.lang.ClassCastException

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.

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.

binarySearch

protected int binarySearch(K key,
                           int low,
                           int high,
                           boolean indicateFailure)
                    throws java.lang.IndexOutOfBoundsException,
                           java.lang.IllegalStateException

Searches a range in this collection of objects for the specified value using the binary search algorithm.

If the range contains multiple elements with the specified value, there is no guarantee which one will be found.

Parameters:

low - the index of the first element (inclusive) to be searched

high - the index of the last element (inclusive) to be searched

key - the key value to be searched for

indicateFailure - flag that controls the return value when the key is not found; if indicateFailure == true, a negative number -(insertionPoint + 1) is returned, otherwise, the index of the nearest bigger key is returned

Returns:

index of the search key, if it is contained in this collection within the specified range; otherwise, the nearest (higher) index is returned or -1 according to the value of indicateFailure

Throws:

java.lang.IndexOutOfBoundsException - if the specified boundaries are outside range

java.lang.IllegalStateException - if there was an error accessing object via get(int)

fullSearch

protected <C> int fullSearch(IndexComparator<C,T> comparator,
                             C key,
                             int low,
                             int high)
                  throws java.lang.IndexOutOfBoundsException,
                         java.lang.IllegalStateException

Searches a range in this collection for objects that are equal to the specified key. If the comparator is not null it is used to check for equality. Otherwise, the Object.equals(java.lang.Object) is used.

Type Parameters:

C - type of keys for the comparator

Parameters:

comparator - the comparator used to check for equality of objects (can be null)

low - the index of the first element (inclusive) to be searched

high - the index of the last element (inclusive) to be searched

key - the key value to be searched for

Returns:

index of the first object that is equal to key or -1

Throws:

java.lang.IndexOutOfBoundsException - if the specified boundaries are outside range

java.lang.IllegalStateException - if there was an error accessing object via get(int)

indexOf

protected int indexOf(java.lang.Object o)

Returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element. More formally, returns the lowest index i such that (o==null ? get(i)==null : o.equals(get(i))), or -1 if there is no such index.

Parameters:

o - element to search for

Returns:

the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element

first

public T first()
        throws java.util.NoSuchElementException,
               java.lang.IllegalStateException

Returns the last element of this collection according to the order specified by the comparator.

Returns:

the element at the specified position in this collection

Throws:

java.util.NoSuchElementException - if the collection is empty

java.lang.IllegalStateException - if there was an error accessing object via get(int)

last

public T last()
       throws java.util.NoSuchElementException,
              java.lang.IllegalStateException

Returns the last element of this collection according to the order specified by the comparator.

Returns:

the element at the specified position in this collection

Throws:

java.util.NoSuchElementException - if the collection is empty

java.lang.IllegalStateException - if there was an error accessing object via get(int)

mergeSort

public static <T> void mergeSort(T[] items1,
                                 int from1,
                                 int to1,
                                 T[] items2,
                                 int from2,
                                 int to2,
                                 java.util.Comparator<T> comparator,
                                 T[] destination,
                                 int fromDest,
                                 int toDest)

Merges two sorted arrays into the destination array using the specified comparator.

Type Parameters:

T - type of array elements

Parameters:

items1 - the first array to merge

from1 - the starting index in the first array

to1 - the last index (exclusive) in the first array

items2 - the second array to merge

from2 - the starting index in the second array

to2 - the last index (exclusive) in the second array

comparator - the comparator used to compare objects from the collections; its type check is supressed, the array items are expected to be compatible

destination - the destination array

fromDest - the starting index in the destination array

toDest - the last index (exclusive) in the destination array