All Packages  Class Hierarchy  This Package  Previous  Next  Index

Class collections.Dynarray 

java.lang.Object
   |
   +----collections.UpdatableImpl
           |
           +----collections.UpdatableSeqImpl
                   |
                   +----collections.Dynarray
public class Dynarray
extends UpdatableSeqImpl
implements UpdatableSeq, SortableCollection
Dynamically allocated and resized Arrays. Beyond implementing its interfaces, adds methods to adjust capacities. The default heuristics for resizing usually work fine, but you can adjust them manually when you need to. Dynarrays are generally like java.util.Vectors. But unlike them, Dynarrays do not actually allocate arrays when they are constructed. Among other consequences, you can adjust the capacity `for free' after construction but before adding elements. You can adjust it at other times as well, but this may lead to more expensive resizing. Also, unlike Vectors, they release their internal arrays whenever they are empty.

Variable Index

o array_
The elements, or null if no buffer yet allocated.
o minCapacity
The minimum capacity of any non-empty buffer

Constructor Index

o Dynarray()
Make a new empty Dynarray.
o Dynarray(Predicate)
Make an empty Dynarray with given element screener
o Dynarray(Predicate, Object[], int)
Special version of constructor needed by clone()

Method Index

o appendElements(Enumeration)
Implements collections.UpdatableSeq.appendElements.
o at(int)
Implements collections.Seq.at.
o capacity()
return the current internal buffer capacity (zero if no buffer allocated).
o capacity(int)
Set the internal buffer capacity to max(size(), newCap).
o checkImplementation()
Implements collections.ImplementationCheckable.checkImplementation.
o clear()
Implements collections.UpdatableCollection.clear.
o clone()
Make an independent copy.
o elements()
Implements collections.Collection.elements.
o exclude(Object)
Implements collections.UpdatableCollection.exclude.
o first()
Implements collections.Seq.first.
o firstIndexOf(Object)
Implements collections.Seq.firstIndexOf.
o firstIndexOf(Object, int)
Implements collections.Seq.firstIndexOf.
o includes(Object)
Implements collections.Collection.includes.
o insertAt(int, Object)
Implements collections.UpdatableSeq.insertAt.
o insertElementsAt(int, Enumeration)
Implements collections.UpdatableSeq.insertElementsAt.
o insertFirst(Object)
Implements collections.UpdatableSeq.insertFirst.
o insertLast(Object)
Implements collections.UpdatableSeq.insertLast.
o last()
Implements collections.Seq.last.
o lastIndexOf(Object)
Implements collections.Seq.lastIndexOf.
o lastIndexOf(Object, int)
Implements collections.Seq.lastIndexOf.
o occurrencesOf(Object)
Implements collections.Collection.occurrencesOf.
o prependElements(Enumeration)
Implements collections.UpdatableSeq.prependElements.
o quickSort(Object[], int, int, Comparator)
An implementation of Quicksort using medians of 3 for partitions.
o removeAt(int)
Implements collections.UpdatableSeq.removeAt.
o removeFirst()
Implements collections.UpdatableSeq.removeFirst.
o removeFromTo(int, int)
Implements collections.UpdatableSeq.removeFromTo.
o removeLast()
Implements collections.UpdatableSeq.removeLast.
o removeOneOf(Object)
Implements collections.UpdatableCollection.removeOneOf.
o replaceAllOf(Object, Object)
Implements collections.UpdatableCollection.replaceAllOf.
o replaceAt(int, Object)
Implements collections.UpdatableSeq.replaceAt.
o replaceFirst(Object)
Implements collections.UpdatableSeq.replaceFirst.
o replaceLast(Object)
Implements collections.UpdatableSeq.replaceLast.
o replaceOneOf(Object, Object)
Implements collections.UpdatableCollection.replaceOneOf Time complexity: O(n).
o sort(Comparator)
Implements collections.SortableCollection.sort.
o subseq(int, int)
Implements collections.Seq.subseq.
o take()
Implements collections.UpdatableCollection.take.

Variables

o minCapacity 
 public static final int minCapacity
The minimum capacity of any non-empty buffer

o array_ 
 protected Object array_[]
The elements, or null if no buffer yet allocated.

Constructors

o Dynarray 
 public Dynarray()
Make a new empty Dynarray.

o Dynarray 
 public Dynarray(Predicate screener)
Make an empty Dynarray with given element screener

o Dynarray 
 protected Dynarray(Predicate s,
                    Object b[],
                    int c)
Special version of constructor needed by clone()

Methods

o clone 
 protected Object clone() throws CloneNotSupportedException
Make an independent copy. The elements themselves are not cloned

Overrides:
clone in class Object
o capacity 
 public synchronized int capacity()
return the current internal buffer capacity (zero if no buffer allocated).

Returns:
capacity (always greater than or equal to size())
o capacity 
 public synchronized void capacity(int newCap)
Set the internal buffer capacity to max(size(), newCap). That is, if given an argument less than the current number of elements, the capacity is just set to the current number of elements. Thus, elements are never lost by setting the capacity.

Parameters:
newCap - the desired capacity.
Returns:
condition: 
 capacity() >= size() &&
 version() != PREV(this).version() == (capacity() != PREV(this).capacity())
o includes 
 public synchronized boolean includes(Object element)
Implements collections.Collection.includes. Time complexity: O(n).

Overrides:
includes in class UpdatableImpl
See Also:
includes
o occurrencesOf 
 public synchronized int occurrencesOf(Object element)
Implements collections.Collection.occurrencesOf. Time complexity: O(n).

Overrides:
occurrencesOf in class UpdatableImpl
See Also:
occurrencesOf
o elements 
 public synchronized CollectionEnumeration elements()
Implements collections.Collection.elements. Time complexity: O(1).

Overrides:
elements in class UpdatableImpl
See Also:
elements
o first 
 public synchronized Object first() throws NoSuchElementException
Implements collections.Seq.first. Time complexity: O(1).

Overrides:
first in class UpdatableSeqImpl
See Also:
first
o last 
 public synchronized Object last() throws NoSuchElementException
Implements collections.Seq.last. Time complexity: O(1).

Overrides:
last in class UpdatableSeqImpl
See Also:
last
o at 
 public synchronized Object at(int index) throws NoSuchElementException
Implements collections.Seq.at. Time complexity: O(1).

Overrides:
at in class UpdatableSeqImpl
See Also:
at
o firstIndexOf 
 public synchronized int firstIndexOf(Object element,
                                      int startingIndex)
Implements collections.Seq.firstIndexOf. Time complexity: O(n).

Overrides:
firstIndexOf in class UpdatableSeqImpl
See Also:
firstIndexOf
o lastIndexOf 
 public synchronized int lastIndexOf(Object element,
                                     int startingIndex)
Implements collections.Seq.lastIndexOf. Time complexity: O(n).

Overrides:
lastIndexOf in class UpdatableSeqImpl
See Also:
lastIndexOf
o firstIndexOf 
 public synchronized int firstIndexOf(Object element)
Implements collections.Seq.firstIndexOf. Time complexity: O(n).

Overrides:
firstIndexOf in class UpdatableSeqImpl
See Also:
firstIndexOf
o lastIndexOf 
 public synchronized int lastIndexOf(Object element)
Implements collections.Seq.lastIndexOf. Time complexity: O(n).

Overrides:
lastIndexOf in class UpdatableSeqImpl
See Also:
lastIndexOf
o subseq 
 public synchronized Seq subseq(int from,
                                int length) throws NoSuchElementException
Implements collections.Seq.subseq. Time complexity: O(length).

Overrides:
subseq in class UpdatableSeqImpl
See Also:
subseq
o clear 
 public synchronized void clear()
Implements collections.UpdatableCollection.clear. Time complexity: O(1).

Overrides:
clear in class UpdatableImpl
See Also:
clear
o removeOneOf 
 public synchronized void removeOneOf(Object element)
Implements collections.UpdatableCollection.removeOneOf. Time complexity: O(n).

Overrides:
removeOneOf in class UpdatableImpl
See Also:
removeOneOf
o replaceOneOf 
 public synchronized void replaceOneOf(Object oldElement,
                                       Object newElement) throws IllegalElementException
Implements collections.UpdatableCollection.replaceOneOf Time complexity: O(n).

Overrides:
replaceOneOf in class UpdatableImpl
See Also:
replaceOneOf
o replaceAllOf 
 public synchronized void replaceAllOf(Object oldElement,
                                       Object newElement) throws IllegalElementException
Implements collections.UpdatableCollection.replaceAllOf. Time complexity: O(n * number of replacements).

Overrides:
replaceAllOf in class UpdatableImpl
See Also:
replaceAllOf
o exclude 
 public synchronized void exclude(Object element)
Implements collections.UpdatableCollection.exclude. Time complexity: O(n * occurrencesOf(element)).

Overrides:
exclude in class UpdatableImpl
See Also:
exclude
o take 
 public synchronized Object take() throws NoSuchElementException
Implements collections.UpdatableCollection.take. Time complexity: O(1). Takes the rightmost element of the array.

Overrides:
take in class UpdatableImpl
See Also:
take
o sort 
 public void sort(Comparator cmp)
Implements collections.SortableCollection.sort. Time complexity: O(n log n). Uses a quicksort-based algorithm.

See Also:
sort
o insertFirst 
 public synchronized void insertFirst(Object element) throws IllegalElementException
Implements collections.UpdatableSeq.insertFirst. Time complexity: O(n)

Overrides:
insertFirst in class UpdatableSeqImpl
See Also:
insertFirst
o replaceFirst 
 public synchronized void replaceFirst(Object element) throws IllegalElementException
Implements collections.UpdatableSeq.replaceFirst. Time complexity: O(1).

Overrides:
replaceFirst in class UpdatableSeqImpl
See Also:
replaceFirst
o removeFirst 
 public synchronized void removeFirst() throws NoSuchElementException
Implements collections.UpdatableSeq.removeFirst. Time complexity: O(n).

Overrides:
removeFirst in class UpdatableSeqImpl
See Also:
removeFirst
o insertLast 
 public synchronized void insertLast(Object element) throws IllegalElementException
Implements collections.UpdatableSeq.insertLast. Time complexity: normally O(1), but O(n) if size() == capacity().

Overrides:
insertLast in class UpdatableSeqImpl
See Also:
insertLast
o replaceLast 
 public synchronized void replaceLast(Object element) throws IllegalElementException, NoSuchElementException
Implements collections.UpdatableSeq.replaceLast. Time complexity: O(1).

Overrides:
replaceLast in class UpdatableSeqImpl
See Also:
replaceLast
o removeLast 
 public synchronized void removeLast() throws NoSuchElementException
Implements collections.UpdatableSeq.removeLast. Time complexity: O(1).

Overrides:
removeLast in class UpdatableSeqImpl
See Also:
removeLast
o insertAt 
 public synchronized void insertAt(int index,
                                   Object element) throws IllegalElementException, NoSuchElementException
Implements collections.UpdatableSeq.insertAt. Time complexity: O(n).

Overrides:
insertAt in class UpdatableSeqImpl
See Also:
insertAt
o removeAt 
 public synchronized void removeAt(int index) throws NoSuchElementException
Implements collections.UpdatableSeq.removeAt. Time complexity: O(n).

Overrides:
removeAt in class UpdatableSeqImpl
See Also:
removeAt
o replaceAt 
 public synchronized void replaceAt(int index,
                                    Object element) throws IllegalElementException, NoSuchElementException
Implements collections.UpdatableSeq.replaceAt. Time complexity: O(1).

Overrides:
replaceAt in class UpdatableSeqImpl
See Also:
replaceAt
o prependElements 
 public synchronized void prependElements(Enumeration e) throws IllegalElementException, CorruptedEnumerationException
Implements collections.UpdatableSeq.prependElements. Time complexity: O(n + number of elements in e) if (e instanceof CollectionEnumeration) else O(n * number of elements in e)

Overrides:
prependElements in class UpdatableSeqImpl
See Also:
prependElements
o appendElements 
 public synchronized void appendElements(Enumeration e) throws IllegalElementException, CorruptedEnumerationException
Implements collections.UpdatableSeq.appendElements. Time complexity: O(number of elements in e)

Overrides:
appendElements in class UpdatableSeqImpl
See Also:
appendElements
o insertElementsAt 
 public synchronized void insertElementsAt(int index,
                                           Enumeration e) throws IllegalElementException, CorruptedEnumerationException, NoSuchElementException
Implements collections.UpdatableSeq.insertElementsAt. Time complexity: O(n + number of elements in e) if (e instanceof CollectionEnumeration) else O(n * number of elements in e)

Overrides:
insertElementsAt in class UpdatableSeqImpl
See Also:
insertElementsAt
o removeFromTo 
 public synchronized void removeFromTo(int fromIndex,
                                       int toIndex) throws NoSuchElementException
Implements collections.UpdatableSeq.removeFromTo. Time complexity: O(n).

Overrides:
removeFromTo in class UpdatableSeqImpl
See Also:
removeFromTo
o quickSort 
 public static void quickSort(Object s[],
                              int lo,
                              int hi,
                              Comparator cmp)
An implementation of Quicksort using medians of 3 for partitions. Used internally by sort. It is public and static so it can be used to sort plain arrays as well.

Parameters:
s, - the array to sort
lo, - the least index to sort from
hi, - the greatest index
cmp, - the comparator to use for comparing elements
o checkImplementation 
 public synchronized void checkImplementation() throws ImplementationError
Implements collections.ImplementationCheckable.checkImplementation.

Overrides:
checkImplementation in class UpdatableImpl
See Also:
checkImplementation 
All Packages  Class Hierarchy  This Package  Previous  Next  Index