#include <coherence/util/CircularArrayList.hpp>
Inherits AbstractList.
List
interface.
Implements all optional list operations, and permits all elements, including NULL
. This class is optimized operations on the front and back of the list to facilitate use as a queue or deque.
The size
, get
, set
, listIterator
operations run in constant time. The add
operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList
implementation.
Each CircularArrayList
instance has a capacity. The capacity is the size of the array used to store the elements in the list. It is always at least as large as the list size. As elements are added to an CircularArrayList, its capacity grows automatically. The details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost.
An application can increase the capacity of an CircularArrayList
instance before adding a large number of elements using the ensureCapacity
operation. This may reduce the amount of incremental reallocation.
Note that this implementation is not synchronized. If multiple threads access a CircularArrayList
concurrently, and at least one of the threads modifies the list structurally, it must be synchronized externally. (A structural modification is any operation that adds or deletes one or more elements, or explicitly resizes the backing array; merely setting the value of an element is not a structural modification.) This is typically accomplished by synchronizing on some object that naturally encapsulates the list.
The iterators returned by this class's listIterator
methods are fail-fast: if list is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove or add methods, the iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.
Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw ConcurrentModificationException
on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.
Public Types | ||||||||||
typedef spec::Handle | Handle | |||||||||
CircularArrayList Handle definition. | ||||||||||
typedef spec::View | View | |||||||||
CircularArrayList View definition. | ||||||||||
typedef spec::Holder | Holder | |||||||||
CircularArrayList Holder definition. | ||||||||||
Public Member Functions | ||||||||||
virtual void | trimToSize () | |||||||||
Trim the capacity of this list instance to be as small as possible. | ||||||||||
bool | ensureCapacity (size32_t cMin) | |||||||||
Increase the capacity of this list instance, if necessary, to ensure that it can hold at least the specified number of elements. | ||||||||||
virtual bool | add (size32_t i, Object::Holder oh) | |||||||||
Add the given element to this collection at the position specified. If an element is already at that position it will be shifted to the right by 1.
| ||||||||||
virtual bool | addAll (size32_t i, Collection::View vc) | |||||||||
Add all the elements from the supplied collection to this collection at the position specified.
| ||||||||||
virtual Object::Holder | get (size32_t i) const | |||||||||
Return the element from the specified position in the list.
| ||||||||||
virtual size32_t | indexOf (Object::View v) const | |||||||||
Return the position in the list of the first instance of the specified element.
| ||||||||||
virtual size32_t | lastIndexOf (Object::View v) const | |||||||||
Return the position in this list of the last instance of the specified element.
| ||||||||||
virtual ListIterator::Handle | listIterator (size32_t index=0) const | |||||||||
Return a ListIterator for this list starting at index.
| ||||||||||
virtual ListMuterator::Handle | listIterator (size32_t index=0) | |||||||||
Return a ListIterator for this list starting at index.
| ||||||||||
virtual Object::Holder | remove (size32_t index) | |||||||||
Remove the element at the specified position in the list.
| ||||||||||
virtual Object::Holder | set (size32_t index, Object::Holder oh) | |||||||||
Replace the element at the specified position in this list with the specified element.
| ||||||||||
virtual List::View | subList (size32_t fromIndex, size32_t toIndex) const | |||||||||
Return a new list containing the contents of the list between the specified fromIndex (inclusive) and toIndex (exclusive).
| ||||||||||
virtual List::Handle | subList (size32_t fromIndex, size32_t toIndex) | |||||||||
Return a new list containing the contents of the list between the specified fromIndex (inclusive) and toIndex (exclusive).
| ||||||||||
virtual size32_t | size () const | |||||||||
Return the number of elements in this collection.
| ||||||||||
virtual Iterator::Handle | iterator () const | |||||||||
Return an Iterator over this collection.
| ||||||||||
virtual Muterator::Handle | iterator () | |||||||||
Return an Iterator over this collection.
| ||||||||||
virtual ObjectArray::Handle | toArray (ObjectArray::Handle hao=NULL) const | |||||||||
Return the contents of this collection as an ObjectArray. If the collection fits in the specified array, it is returned, otherwise, a new array is allocated that is the size of this collection. If this collection fits in the array with aditional room then the element in the array immediately following the end of the collection is set to NULL. This can be useful in determining the length of this collection if the caller knows that the collection does not contain any NULL elements.
| ||||||||||
virtual bool | add (Object::Holder oh) | |||||||||
Add the given element to this collection.
This implementation will throw a coherence::lang::UnsupportedOperationException | ||||||||||
virtual bool | addAll (Collection::View vc) | |||||||||
Add all elements from the supplied collection to this collection.
This implementation will throw a coherence::lang::UnsupportedOperationException unless add() is overridden (assuming the specified collection is non-empty). | ||||||||||
virtual bool | remove (Object::View v) | |||||||||
Remove the supplied element from this collection.
This implementation will throw a coherence::lang::UnsupportedOperationException unless add() is overridden (assuming the specified collection is non-empty). | ||||||||||
virtual bool | removeAll (Collection::View vColl) | |||||||||
Remove all instances of the elements in the supplied collection from this collection. Upon completion, contains() on this collection will return false for all elements in the supplied collection.
This implementation will throw a coherence::lang::UnsupportedOperationException} unless remove() is overridden (assuming the specified collection is non-empty). | ||||||||||
virtual bool | retainAll (Collection::View vCol) | |||||||||
Remove all elements from this collection that are not present in the supplied collection.
This implementation will throw a coherence::lang::UnsupportedOperationException unless remove() is overridden (assuming there are items to be removed by the operation). | ||||||||||
virtual void | clear () | |||||||||
Remove all elements from this collection.
This implementation will throw a coherence::lang::UnsupportedOperationException. | ||||||||||
Protected Member Functions | ||||||||||
CircularArrayList (size32_t cInitialElements=16) | ||||||||||
Create a new CircularArrayList with the specified initial capacity. | ||||||||||
CircularArrayList (Collection::View vc) | ||||||||||
Create a new CircularArrayList that has a reference to every element in the supplied collection. | ||||||||||
virtual size32_t | effectiveIndex (size32_t index) const | |||||||||
Calculate the effective index taking into account offsets and the circular nature of CircularArrayList. | ||||||||||
virtual void | rangeCheck (size32_t index) const | |||||||||
Check if the given index is in range. | ||||||||||
virtual size32_t | ensureEffectiveIndex (size32_t index) const | |||||||||
After range checking Calculate the effective index while taking into account the offsets and the circular nature of the list. | ||||||||||
virtual bool | ensureCompactness () | |||||||||
Ensure the representation of this list is appropriatly compact by shrinking if necessary. | ||||||||||
virtual void | removeRange (size32_t fromIndex, size32_t toIndex) | |||||||||
Removes from this list all of the elements whose indexes are between fromIndex, inclusive and toIndex, exclusive. | ||||||||||
Protected Attributes | ||||||||||
MemberHandle < ObjectArray > | m_haoData | |||||||||
The array into which the elements of the list are stored. | ||||||||||
size32_t | m_iFirst | |||||||||
The offset to the first element. | ||||||||||
size32_t | m_iLast | |||||||||
The offset to one past the last element. | ||||||||||
size32_t | m_cElements | |||||||||
The size of the list (the number of elements it contains). | ||||||||||
size32_t | m_cMod | |||||||||
The current mod count which is used to detect concurrent modification. | ||||||||||
Classes | ||||||||||
class | SubCircularArrayList | |||||||||
Utility class to implement a SubList of a CircularArrayList. More... |
CircularArrayList | ( | size32_t | cInitialElements = 16 |
) | [protected] |
Create a new CircularArrayList with the specified initial capacity.
cInitialElements | the initial capacity of the list |
IllegalArgumentException | if the specified initial capacity is negative |
CircularArrayList | ( | Collection::View | vc | ) | [protected] |
Create a new CircularArrayList that has a reference to every element in the supplied collection.
vc | The collection to base the CircularArrayList on |
bool ensureCapacity | ( | size32_t | cMin | ) |
Increase the capacity of this list instance, if necessary, to ensure that it can hold at least the specified number of elements.
cMin | the minimum allowable capacity |
virtual size32_t effectiveIndex | ( | size32_t | index | ) | const [protected, virtual] |
Calculate the effective index taking into account offsets and the circular nature of CircularArrayList.
index | the index to transform |
virtual void rangeCheck | ( | size32_t | index | ) | const [protected, virtual] |
Check if the given index is in range.
If not, throw an appropriate runtime exception.
index | the index to be checked for being between size() and 0 inclusive |
IndexOutOfBoundsException |
virtual size32_t ensureEffectiveIndex | ( | size32_t | index | ) | const [protected, virtual] |
After range checking Calculate the effective index while taking into account the offsets and the circular nature of the list.
index | the index to transform |
IndexOutOfBoundsException |
virtual bool ensureCompactness | ( | ) | [protected, virtual] |
Ensure the representation of this list is appropriatly compact by shrinking if necessary.
virtual void removeRange | ( | size32_t | fromIndex, | |
size32_t | toIndex | |||
) | [protected, virtual] |
Removes from this list all of the elements whose indexes are between fromIndex, inclusive and toIndex, exclusive.
Shifts any succeeding elements to the left (reduces their index). This call shortens the list by (toIndex - fromIndex) elements. (If toIndex==fromIndex, this operation has no effect.)
fromIndex | the index of first element to be removed | |
toIndex | the index after last element to be removed. |
MemberHandle<ObjectArray> m_haoData [protected] |
The array into which the elements of the list are stored.
The capacity of the list is the length of this array buffer.