Oracle Coherence for C++ API
Release 3.7.1.0

E22845-01

CircularArrayList Class Reference

#include <coherence/util/CircularArrayList.hpp>

Inherits AbstractList.

List of all members.


Detailed Description

Resizable-array implementation of the 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.

Author:
djl 2009.01.14
Since:
Coherence 3.5
 

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.

Parameters:
 i the position to insert the element at
 oh the element to add
Returns:
true iff this list was modified as a result of this operation
Exceptions:
 coherence::lang::IndexOutOfBoundsException if the index is out of range
virtual bool addAll (size32_t i, Collection::View vc)
 Add all the elements from the supplied collection to this collection at the position specified.

Parameters:
 i the index of the list to add the elements to
 vc the collection to add to this list
Returns:
true iff this list was modified as a result of this operation
Exceptions:
 coherence::lang::IndexOutOfBoundsException if the inedex is out of range
virtual Object::Holder get (size32_t i) const
 Return the element from the specified position in the list.

Parameters:
 i the position of the item to return
Returns:
the element from the specified position in the list
Exceptions:
 coherence::lang::IndexOutOfBoundsException if the index is out of range
virtual size32_t indexOf (Object::View v) const
 Return the position in the list of the first instance of the specified element.

Parameters:
 v The object in the list to return the index of
Returns:
the position of the object if found, or List::npos
virtual size32_t lastIndexOf (Object::View v) const
 Return the position in this list of the last instance of the specified element.

Parameters:
 v The element to search for in the list
Returns:
the position of the element if found, or List::npos
virtual
ListIterator::Handle 
listIterator (size32_t index=0) const
 Return a ListIterator for this list starting at index.

Parameters:
 i the index to start the ListIterator at
Returns:
a ListIterator for this list start at index
virtual
ListMuterator::Handle 
listIterator (size32_t index=0)
 Return a ListIterator for this list starting at index.

Parameters:
 i the index to start the ListIterator at
Returns:
a ListIterator for this list start at index
virtual Object::Holder remove (size32_t index)
 Remove the element at the specified position in the list.

Parameters:
 i the index from which to remove an element
Returns:
the element at the specified position prior to this operation
Exceptions:
 coherence::lang::IndexOutOfBoundsException if the index is out of range
virtual Object::Holder set (size32_t index, Object::Holder oh)
 Replace the element at the specified position in this list with the specified element.

Parameters:
 i the position in the list to replace
 oh the object to replace at the specified position
Returns:
the element at the specified position prior to this operation
Exceptions:
 coherence::lang::IndexOutOfBoundsException if the index is out of range
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).

Parameters:
 iFrom the start position in this list to create the sublist from (inclusive).
 iTo the end position in this list to end the sublist at (exclusive).
Returns:
the new sublist of this list
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).

Parameters:
 iFrom the start position in this list to create the sublist from (inclusive).
 iTo the end position in this list to end the sublist at (exclusive).
Returns:
the new sublist of this list
virtual size32_t size () const
 Return the number of elements in this collection.

Returns:
the number of elements in this collection
virtual Iterator::Handle iterator () const
 Return an Iterator over this collection.

Returns:
an Iterator over this collection
virtual Muterator::Handle iterator ()
 Return an Iterator over this collection.

Returns:
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.

Parameters:
 hao an array in which to store the collection's contents
Returns:
a ObjectArray containing all the elements of the collection in the same order as returned by the collection's Iterator
See also:
Iterator
virtual bool add (Object::Holder oh)
 Add the given element to this collection.

Parameters:
 oh the element to add
Returns:
true iff this collection was modified as a result of this operation

This implementation will throw a coherence::lang::UnsupportedOperationException

virtual bool addAll (Collection::View vc)
 Add all elements from the supplied collection to this collection.

Parameters:
 vCol the collection of elements to add
Returns:
true iff this collection was modified as a result of this operation
Exceptions:
 coherence::lang::NullPointerException if the specified collection is NULL
See also:
add()

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.

Parameters:
 v the element to remove
Returns:
true iff this collection was modified as a result of this operation

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.

Parameters:
 vCol the collection of elements to remove
Returns:
true iff this collection was modified as a result of this operation
Exceptions:
 coherence::lang::NullPointerException if the specified collection is NULL
See also:
remove()

contains()

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.

Parameters:
 vCol the collection of elements to retain
Returns:
true iff this collection was modified as a result of this operation.
Exceptions:
 coherence::lang::NullPointerException if the specified collection is NULL
See also:
remove()

contains()

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...

Constructor & Destructor Documentation

CircularArrayList ( size32_t  cInitialElements = 16  )  [protected]

Create a new CircularArrayList with the specified initial capacity.

Parameters:
 cInitialElements the initial capacity of the list
Exceptions:
 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.

Parameters:
 vc The collection to base the CircularArrayList on
Returns:
a new CircularArrayList


Member Function Documentation

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.

Parameters:
 cMin the minimum allowable capacity
Returns:
true if the capacity was increased

virtual size32_t effectiveIndex ( size32_t  index  )  const [protected, virtual]

Calculate the effective index taking into account offsets and the circular nature of CircularArrayList.

Parameters:
 index the index to transform
Returns:
the effective index in the physical storage array

virtual void rangeCheck ( size32_t  index  )  const [protected, virtual]

Check if the given index is in range.

If not, throw an appropriate runtime exception.

Parameters:
 index the index to be checked for being between size() and 0 inclusive
Exceptions:
 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.

Parameters:
 index the index to transform
Returns:
the effective index in the physical storage array
Exceptions:
 IndexOutOfBoundsException  

virtual bool ensureCompactness (  )  [protected, virtual]

Ensure the representation of this list is appropriatly compact by shrinking if necessary.

Returns:
true if an actual compaction happened; false otherwise

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

Parameters:
 fromIndex the index of first element to be removed
 toIndex the index after last element to be removed.


Member Data Documentation

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.


The documentation for this class was generated from the following file:
Copyright © 2000, 2011, Oracle and/or its affiliates. All rights reserved.