org.openmdx.base.collection
Class AbstractSparseArray

java.lang.Object
  org.openmdx.base.collection.AbstractSparseArray

All Implemented Interfaces:

Iterable, Collection, SparseArray

Direct Known Subclasses:

MarshallingSparseArray, TreeSparseArray

public abstract class AbstractSparseArray
extends Object
implements SparseArray

This class provides a skeletal implementation of the SparseArray interface to minimize the effort required to implement this interface backed by a data store.

The programmer needs only to extend this class and provide an implementation for the populationMap() method.

The programmer should generally provide a void (no argument) and collection constructor, as per the recommendation in the Collection interface specification. The documentation for each non-abstract methods in this class describes its implementation in detail. Each of these methods may be overridden if the collection being implemented admits a more efficient implementation.

Constructor Summary

protected

AbstractSparseArray() Constructs an empty sparse array.

Method Summary

boolean	add(Object o) Appends the specified element to the end of this sparse array (optional operation).
boolean	addAll(Collection c) Adds all of the elements in the specified collection to this collection (optional operation).
List	asList() A list backed up by the sparse array.
void	clear() Removes all of the elements from this collection (optional operation).
boolean	contains(Object o) Returns true if this collection contains the specified element.
boolean	containsAll(Collection c) Returns true if this collection contains all of the elements in the specified collection.
int	end() Return the index where add() would insert an element.
Object	get(int index) Returns the element at the specified position in this sparse array.
int	indexOf(Object o) Returns the index in this sparse array of the first occurrence of the specified element, or -1 if this sparse array does not contain this element.
boolean	isEmpty() Returns true if this collection contains no elements.
Iterator	iterator() Returns an iterator over the elements in this sparse array (in proper sequence).
protected int	lowerBound() The lower bound is relevant for the end(), add(Object element) and asList() methods.
PopulationIterator	populationIterator() Returns an iterator for the populated elements in this sparse array (in proper sequence).
PopulationIterator	populationIterator(int fromIndex) Returns an iterator for the populated elements in this sparse array (in proper sequence).
abstract SortedMap	populationMap() Returns a map view of this sparse array's populated elements.
Object	remove(int index) Removes the element at the specified position in this sparse array (optional operation).
boolean	remove(Object o) Removes a single instance of the specified element from this collection, if it is present (optional operation).
boolean	removeAll(Collection c) Removes from this collection all of its elements that are contained in the specified collection (optional operation).
boolean	retainAll(Collection c) Retains only the elements in this collection that are contained in the specified collection (optional operation).
Object	set(int index, Object element) Replaces the element at the specified position in this sparse array with the specified element (optional operation).
void	setAll(SparseArray t) Copies all of the entries from the specified sparse array to this sparse array (optional operation).
int	size() Returns the number of (non-null) elements in this sparse array.
int	start() Return the index of the first populated element in the sparse array or -1 if the sparse array is empty.
SparseArray	subArray(int fromIndex, int toIndex) Returns a view of the portion of this sparse array between the specified fromIndex, inclusive, and toIndex, exclusive.
Object[]	toArray() Returns an array containing all of the elements in this collection.
Object[]	toArray(Object[] 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() Returns a string representation of this collection.

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.util.Collection

equals, hashCode

Constructor Detail

AbstractSparseArray

protected AbstractSparseArray()

Constructs an empty sparse array.

Method Detail

lowerBound

protected int lowerBound()

The lower bound is relevant for the end(), add(Object element) and asList() methods.

Returns:

this sparse array's lower bound

See Also:

end(), asList(), add(Object)

populationMap

public abstract SortedMap populationMap()

Returns a map view of this sparse array's populated elements. The map's iterator will return the entries in ascending order. The map is backed by the sparse array, so changes to the sparse array are reflected in the map, and vice-versa. If the sparse array is modified while an iteration over the map is in progress, the results of the iteration are undefined. The map supports element removal, which removes the corresponding entry from the sparse array, via the Iterator.remove, Map.remove, removeAll retainAll, and clear operations. It does not support the add or addAll operations.

Specified by:

populationMap in interface SparseArray

Returns:

a map view of this sparse array's populated elements

size

public int size()

Returns the number of (non-null) elements in this sparse array. If this sparse array contains more than Integer.MAX_VALUE elements or if its size can't be determined yet it returns Integer.MAX_VALUE.

This implementaion returns the population map's size.

Specified by:

size in interface Collection

Specified by:

size in interface SparseArray

Returns:

the number of elements in this sparse array.

iterator

public Iterator iterator()

Returns an iterator over the elements in this sparse array (in proper sequence).

This implementaion returns an iterator over the population map's values.

Specified by:

iterator in interface Iterable

Specified by:

iterator in interface Collection

Specified by:

iterator in interface SparseArray

Returns:

an iterator over the elements in this sparse array (in proper sequence).

asList

public List asList()

A list backed up by the sparse array. Its size() is the sparse array's lastIndex() + 1 and the sparse array's un-populated positions are represented as null values.

Specified by:

asList in interface SparseArray

Returns:

a list representing the sparse array

start

public int start()

Return the index of the first populated element in the sparse array or -1 if the sparse array is empty.

This implementation returns the population map's first key unless it is empty.

Specified by:

start in interface SparseArray

Returns:

the index of the first populated element in the sparse array.

end

public int end()

Return the index where add() would insert an element.

This implementation returns the population map's last key unless it is empty.

Specified by:

end in interface SparseArray

Returns:

the index of the last populated element in the sparse array incremented by one unless the sparse array is empty; if it is empty fromIndex is returned for subarrays, 0 otherwise.

get

public Object get(int index)

Returns the element at the specified position in this sparse array.

This implementation returns the corresponding element from the population map.

Specified by:

get in interface SparseArray

Parameters:

index - index of element to return.

Returns:

the element at the specified position in this sparse array.

Throws:

IndexOutOfBoundsException - if the index is out of range (index < 0).

set

public Object set(int index,
                  Object element)

Replaces the element at the specified position in this sparse array with the specified element (optional operation).

set(i,null) is equivalent to remove(i).

This implementation puts the corresponding element into the population map unless it is null.

Specified by:

set in interface SparseArray

Parameters:

index - index of element to replace.

element - element to be stored at the specified position.

Returns:

the element previously at the specified position.

Throws:

UnsupportedOperationException - if the set method is not supported by this sparse array.

ClassCastException - - if the class of the specified element prevents it from being added to this sparse array.

IllegalArgumentException - if some aspect of the specified element prevents it from being added to this sparse array.

IndexOutOfBoundsException - if the index is out of range (index < 0).

setAll

public void setAll(SparseArray t)

Copies all of the entries from the specified sparse array to this sparse array (optional operation). These settings will replace any setings that this sparse array had for any of the indices currently in the specified map.

This implementation calls the set(int index, Object element) method for each entry.

Specified by:

setAll in interface SparseArray

Parameters:

t - Entries to be stored in this map.

Throws:

UnsupportedOperationException - if the sttAll method is not supported by this sparse array.

ClassCastException - if the class of a value in the specified sparse array prevents it from being stored in this sparse array.

IllegalArgumentException - some aspect of a key or value in the specified map prevents it from being stored in this map.

NullPointerException - this map does not permit null keys or values, and the specified key or value is null.

add

public boolean add(Object o)

Appends the specified element to the end of this sparse array (optional operation).

Adding a null value to a sparse array does nothing.

Sparse arrays that support this operation may place limitations on what elements may be added to this sparse array. In particular, some sparse arrays will impose restrictions on the type of elements that may be added. Sparse array classes should clearly specify in their documentation any restrictions on what elements may be added.

This implementation puts the element at position end() into the sparse array unless it is null.

Specified by:

add in interface Collection

Specified by:

add in interface SparseArray

Parameters:

o - element to be appended to this sparse array.

Returns:

true if o != null; false otherwise.

Throws:

UnsupportedOperationException - if the add method is not supported by this sparse array.

ClassCastException - if the class of the specified element prevents it from being added to this sparse array.

IllegalArgumentException - if some aspect of this element prevents it from being added to this collection.

remove

public Object remove(int index)

Removes the element at the specified position in this sparse array (optional operation). Returns the element that was removed from the sparse array.

remove(i) is equivalent to set(i,null).

This implementation removes the element from the population.

Specified by:

remove in interface SparseArray

Parameters:

index - the index of the element to removed.

Returns:

the element previously at the specified position.

Throws:

UnsupportedOperationException - if the remove method is not supported by this sparse array.

IndexOutOfBoundsException - if the index is out of range (index < 0).

indexOf

public int indexOf(Object o)

Returns the index in this sparse array of the first occurrence of the specified element, or -1 if this sparse array does not contain this 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.

Specified by:

indexOf in interface SparseArray

Parameters:

o - element to search for.

Returns:

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

populationIterator

public PopulationIterator populationIterator()

Returns an iterator for the populated elements in this sparse array (in proper sequence). The first index is start() and the last end() - 1 respectively. The indices are not contiguous.

Specified by:

populationIterator in interface SparseArray

Returns:

an iterator over the populated elements in the sparse array

See Also:

populationIterator(int), start(), end()

populationIterator

public PopulationIterator populationIterator(int fromIndex)

Returns an iterator for the populated elements in this sparse array (in proper sequence). The first index is greater or equal fromIndex and the last end() - 1 respectively. The indices are not contiguous.

This implementation iterates over the tail array starting at fromIndex.

Specified by:

populationIterator in interface SparseArray

Returns:

an iterator over the populated elements in the sparse array

See Also:

populationIterator(), end()

subArray

public SparseArray subArray(int fromIndex,
                            int toIndex)

Returns a view of the portion of this sparse array between the specified fromIndex, inclusive, and toIndex, exclusive. (If fromIndex and toIndex are equal, the returned sparse array is empty.) The returned sparse array is backed by this sparse array, so changes in the returned sparse array are reflected in this sparse array, and vice-versa. The returned sparse array supports all of the optional sparse array operations supported by this sparse array.

This method eliminates the need for explicit range operations (of the sort that commonly exist for arrays). Any operation that expects a sparse array can be used as a range operation by passing a subArray view instead of a whole sparse array. For example, the following idiom removes a range of elements from a sparse array:

list.subArray(from, to).clear();

Similar idioms may be constructed for indexOf and lastIndexOf, and all of the algorithms in the Collections class can be applied to a subArray.

The semantics of this list returned by this method become undefined if the backing list (i.e., this list) is structurally modified in any way other than via the returned list. (Structural modifications are those that change the size of this list, or otherwise perturb it in such a fashion that iterations in progress may yield incorrect results.)

Specified by:

subArray in interface SparseArray

Parameters:

fromIndex - low endpoint (inclusive) of the subArray.

toIndex - high endpoint (exclusive) of the subArray.

Returns:

a view of the specified range within this sparse array.

Throws:

IndexOutOfBoundsException - for an illegal endpoint index value (fromIndex < 0 || fromIndex > toIndex).

isEmpty

public boolean isEmpty()

Returns true if this collection contains no elements.

This implementation checks whether the population map is empty.

Specified by:

isEmpty in interface Collection

Returns:

true if this collection contains no elements.

contains

public boolean contains(Object o)

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

This implementation checks whether the object is among the population map's values.

Specified by:

contains in interface Collection

Parameters:

o - object to be checked for containment in this collection.

Returns:

true if this collection contains the specified element.

toArray

public Object[] 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.

Specified by:

toArray in interface Collection

Returns:

an array containing all of the elements in this collection.

toArray

public Object[] toArray(Object[] 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.

Specified by:

toArray in interface 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.

remove

public boolean remove(Object o)

Removes a single instance of the specified element from this collection, if it is present (optional operation). More formally, removes an element e such that (o==null ? e==null : o.equals(e)), if the collection contains one or more such elements. Returns true if the collection contained the specified element (or equivalently, if the collection changed as a result of the call).

This implementation removes the object from the population map's values.

Specified by:

remove in interface Collection

Parameters:

o - element to be removed from this collection, if present.

Returns:

true if the collection contained the specified element.

Throws:

UnsupportedOperationException - if the remove method is not supported by this collection.

containsAll

public boolean containsAll(Collection c)

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

This implementation checks whether all the collection's elements are among population map's values.

Specified by:

containsAll in interface Collection

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.

See Also:

contains(Object)

addAll

public boolean addAll(Collection c)

Adds all of the elements in the specified collection to this collection (optional operation). The behavior of this operation is undefined if the specified collection is modified while the operation is in progress. (This implies that the behavior of this call is undefined if the specified collection is this collection, and this collection is nonempty.)

This implementation iterates over the specified collection, and adds each object returned by the iterator to this collection, in turn.

Note that this implementation will throw an UnsupportedOperationException unless add is overridden.

Specified by:

addAll in interface Collection

Parameters:

c - collection whose elements are to be added to this collection.

Returns:

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

Throws:

UnsupportedOperationException - if the addAll method is not supported by this collection.

See Also:

add(Object)

removeAll

public boolean removeAll(Collection c)

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

This implementation removes all elements in the specified collection from the population map's values.

Specified by:

removeAll in interface Collection

Parameters:

c - elements to be removed from this collection.

Returns:

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

Throws:

UnsupportedOperationException - removeAll is not supported by this collection.

See Also:

remove(Object), contains(Object)

retainAll

public boolean retainAll(Collection c)

Retains only the elements in this collection that are contained in the specified collection (optional operation). In other words, removes from this collection all of its elements that are not contained in the specified collection.

This implementation removes all elements not contained in the specified collection from the population map's values.

Specified by:

retainAll in interface Collection

Parameters:

c - elements to be retained in this collection.

Returns:

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

Throws:

UnsupportedOperationException - if the retainAll method is not supported by this collection.

See Also:

remove(Object), contains(Object)

clear

public void clear()

Removes all of the elements from this collection (optional operation). The collection will be empty after this call returns (unless it throws an exception).

This implementation clears the population map.

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

Specified by:

clear in interface Collection

Throws:

UnsupportedOperationException - if the remove method is not supported by this collection.

toString

public String toString()

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

This implementation creates an empty string buffer, appends a left square bracket, and iterates over the collection appending the string representation of each element in turn. After appending each element except the last, the string ", " is appended. Finally a right bracket is appended. A string is obtained from the string buffer, and returned.

Overrides:

toString in class Object

Returns:

a string representation of this collection.