An array-based list class. More...

#include <omArrayList.h>

Classes
class	ConstIterator
	An iterator class for an array list which can't modify it. More...

class	Iterator
	Iterator class for an array list. More...

Public Member Functions
	ArrayList ()
	Create a new empty array list with the default capacity of 8 elements. More...

	ArrayList (SizeType newCapacity)
	Create a new empty array list with the specified initial capacity. More...

	ArrayList (const T *elements, SizeType newNumElements)
	Create a new array list with its internal array initialized with element from an external array. More...

	ArrayList (const ArrayList< T, SizeType > &arrayList)
	Create a copy of an existing array list. This is a deep copy. More...

	~ArrayList ()

ArrayList &	operator= (const ArrayList &other)
	Assign the contents of one array list to another, performing a deep copy. More...

Bool	operator== (const ArrayList &other) const
	Return whether or not whether every entry in this list is equal to another list's entries. More...

Bool	operator!= (const ArrayList &other) const
	Return whether or not whether any entry in this list is not equal to another list's entries. More...

void	add (const T &newElement)
	Add an element to the end of the list. More...

void	addNew ()
	Construct a new element at the end of the list. More...

template<typename P1 >
void	addNew (const P1 &p1)
	Construct a new element at the end of the list. More...

template<typename P1 , typename P2 >
void	addNew (const P1 &p1, const P2 &p2)
	Construct a new element at the end of the list. More...

template<typename P1 , typename P2 , typename P3 >
void	addNew (const P1 &p1, const P2 &p2, const P3 &p3)
	Construct a new element at the end of the list. More...

template<typename P1 , typename P2 , typename P3 , typename P4 >
void	addNew (const P1 &p1, const P2 &p2, const P3 &p3, const P4 &p4)
	Construct a new element at the end of the list. More...

template<typename P1 , typename P2 , typename P3 , typename P4 , typename P5 >
void	addNew (const P1 &p1, const P2 &p2, const P3 &p3, const P4 &p4, const P5 &p5)
	Construct a new element at the end of the list. More...

void	addAll (const ArrayList &list)
	Add the contents of one ArrayList to another. More...

void	addAll (const T *otherArray, SizeType number)
	Add the contents of the specified array pointer to the end of the list. More...

Bool	insert (SizeType index, const T &newElement)
	Insert an element at the specified index of the list. More...

Bool	set (SizeType index, const T &newElement)
	Set an element at the specified index of the list to a new value. More...

Bool	removeAtIndex (SizeType index)
	Remove the element at the specified index, ordered version. More...

Bool	removeAtIndexUnordered (SizeType index)
	Remove the element at the specified index, unordered version. More...

Bool	remove (const T &object)
	Remove the first element equal to the parameter element, ordered version. More...

Bool	removeUnordered (const T &object)
	Remove the first element equal to the parameter element, unordered version. More...

Bool	removeLast ()
	Remove the last element in the array list. More...

SizeType	removeLast (SizeType number)
	Remove the last N elements from the array list. More...

void	clear ()
	Clear the contents of this array list. More...

void	reset ()
	Clear the contents of this array list and reclaim the allocated memory. More...

void	reset (SizeType newCapacity)
	Clear the contents of this array list and reclaim the allocated memory. More...

Bool	contains (const T &object) const
	Return whether or not the specified element is in this list. More...

Bool	getIndex (const T &object, SizeType &index) const
	Get the index of the list element equal to the parameter object. More...

T &	get (SizeType index)
	Return the element at the specified index. More...

const T &	get (SizeType index) const
	Return the element at the specified index. More...

T &	getFirst ()
	Return a reference to the first element in the array list. More...

const T &	getFirst () const
	Return a const reference to the first element in the array list. More...

T &	getLast ()
	Return a reference to the last element in the array list. More...

const T &	getLast () const
	Return a const reference to the last element in the array list. More...

T &	operator() (SizeType index)
	Return the element at the specified index. More...

const T &	operator() (SizeType index) const
	Return the element at the specified index. More...

T &	operator[] (SizeType index)
	Return the element at the specified index. More...

const T &	operator[] (SizeType index) const
	Return the element at the specified index. More...

const T *	getPointer () const
	Return a const pointer to the beginning of the internal array. More...

T *	getPointer ()
	Return a pointer to the beginning of the internal array. More...

Bool	isEmpty () const
	Return whether or not the array list has any elements. More...

SizeType	getSize () const
	Return the number of elements in the array list. More...

SizeType	getCapacity () const
	Return the current storage capacity of the array list. More...

void	setCapacity (SizeType newCapacity)
	Set the capacity of the array list. More...

Iterator	getIterator ()
	Return an iterator for the array list. More...

ConstIterator	getIterator () const
	Return a const iterator for the array list. More...

Detailed Description

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>
class om::util::ArrayList< T, SizeType, AllocatorType >

An array-based list class.

This class is an unordered collection of an arbitrary number of generic elements. It is array-based, making random access fast, but removing and inserting slow. It allocates a contiguous block of memory for the elements which it contains. The default initial capacity for the list is 8 elements, and the user can specify a custom initial capacity if desired. This array list implementation is not thread-safe. In threaded envirnments, use the ThreadSafeArrayList

Constructor & Destructor Documentation

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

om::util::ArrayList< T, SizeType, AllocatorType >::ArrayList ( )

inline

Create a new empty array list with the default capacity of 8 elements.

This is a lightweight operation and the array list doesn't allocate any memory until an element is added to the stack.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

om::util::ArrayList< T, SizeType, AllocatorType >::ArrayList ( SizeType newCapacity )

inline

Create a new empty array list with the specified initial capacity.

The initial capacity of the array list can be set by the parameter, which can be used to pad the array list to avoid having to resize the array list often.

Parameters

newCapacity - the initial capacity of the array list

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

om::util::ArrayList< T, SizeType, AllocatorType >::ArrayList	(	const T *	elements,
		SizeType	newNumElements
	)

inline

Create a new array list with its internal array initialized with element from an external array.

The initial capacity and size of the array list is set to the number of elements that are to be copied from the given array.

Parameters

elements	- an array of contiguous element objects from which to initialize this array list.
newNumElements	- the number of elements to copy from the element array.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

om::util::ArrayList< T, SizeType, AllocatorType >::ArrayList ( const ArrayList< T, SizeType > & arrayList )

inline

Create a copy of an existing array list. This is a deep copy.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

om::util::ArrayList< T, SizeType, AllocatorType >::~ArrayList ( )

inline

Member Function Documentation

template<typename T , typename SizeType , typename AllocatorType >

ArrayList< T, SizeType, AllocatorType > & om::util::ArrayList< T, SizeType, AllocatorType >::operator= ( const ArrayList< T, SizeType, AllocatorType > & other )

Assign the contents of one array list to another, performing a deep copy.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

Bool om::util::ArrayList< T, SizeType, AllocatorType >::operator== ( const ArrayList< T, SizeType, AllocatorType > & other ) const

inline

Return whether or not whether every entry in this list is equal to another list's entries.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

Bool om::util::ArrayList< T, SizeType, AllocatorType >::operator!= ( const ArrayList< T, SizeType, AllocatorType > & other ) const

inline

Return whether or not whether any entry in this list is not equal to another list's entries.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

void om::util::ArrayList< T, SizeType, AllocatorType >::add ( const T & newElement )

inline

Add an element to the end of the list.

If the capacity of the array list is not great enough to hold the new element, then the internal array is reallocated to be double the size and all elements are copied to the new array.

Parameters

newElement - the new element to add to the end of the list

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

void om::util::ArrayList< T, SizeType, AllocatorType >::addNew ( )

inline

Construct a new element at the end of the list.

If the capacity of the array list is not great enough to hold the new element, then the internal array is reallocated to be double the size and all elements are copied to the new array.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

template<typename P1 >

void om::util::ArrayList< T, SizeType, AllocatorType >::addNew ( const P1 & p1 )

inline

Construct a new element at the end of the list.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

template<typename P1 , typename P2 >

void om::util::ArrayList< T, SizeType, AllocatorType >::addNew	(	const P1 &	p1,
		const P2 &	p2
	)

inline

Construct a new element at the end of the list.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

template<typename P1 , typename P2 , typename P3 >

void om::util::ArrayList< T, SizeType, AllocatorType >::addNew	(	const P1 &	p1,
		const P2 &	p2,
		const P3 &	p3
	)

inline

Construct a new element at the end of the list.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

template<typename P1 , typename P2 , typename P3 , typename P4 >

void om::util::ArrayList< T, SizeType, AllocatorType >::addNew	(	const P1 &	p1,
		const P2 &	p2,
		const P3 &	p3,
		const P4 &	p4
	)

inline

Construct a new element at the end of the list.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

template<typename P1 , typename P2 , typename P3 , typename P4 , typename P5 >

void om::util::ArrayList< T, SizeType, AllocatorType >::addNew	(	const P1 &	p1,
		const P2 &	p2,
		const P3 &	p3,
		const P4 &	p4,
		const P5 &	p5
	)

inline

Construct a new element at the end of the list.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

void om::util::ArrayList< T, SizeType, AllocatorType >::addAll ( const ArrayList< T, SizeType, AllocatorType > & list )

inline

Add the contents of one ArrayList to another.

This method has the effect of adding each element of the given list to the end of this array list in order.

Parameters

list	- the list to be added to the end of this list

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

void om::util::ArrayList< T, SizeType, AllocatorType >::addAll	(	const T *	otherArray,
		SizeType	number
	)

inline

Add the contents of the specified array pointer to the end of the list.

This method has the effect of adding each element of the given array to the end of this array list in order.

template<typename T, typename SizeType, typename AllocatorType >

Bool om::util::ArrayList< T, SizeType, AllocatorType >::insert	(	SizeType	index,
		const T &	newElement
	)

Insert an element at the specified index of the list.

The method returns TRUE if the element was successfully inserted into the array list. If the index is outside of the bounds of the array list, then FALSE is returned, indicating that the element was not inserted. If needed, the array list is resized to double its current size in order to hold the new element. This method has time complexity of O(n/2) because all subsequent elements in the array list have to be moved towards the end of the list by one index.

Parameters

newElement	- the new element to insert into the array list.
index	- the index at which to insert the new element.

Returns: whether or not the element was successfully inserted into the array list.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

Bool om::util::ArrayList< T, SizeType, AllocatorType >::set	(	SizeType	index,
		const T &	newElement
	)

inline

Set an element at the specified index of the list to a new value.

This method returns TRUE if the specified index is within the bounds of the array list, indicating that the element was successfully set at that position in the array list. Otherwise, FALSE is returned, indicating that the index was out of bounds of the array list. This method has worst-case time complexity of O(1).

Parameters

newElement	- the new element to set in the list.
index	- the index at which to set the new element.

Returns: whether or not the element was successfully set to the new value.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

Bool om::util::ArrayList< T, SizeType, AllocatorType >::removeAtIndex ( SizeType index )

inline

Remove the element at the specified index, ordered version.

If the index is within the bounds of the list ( >= 0 && < getType() ), then the list element at that index is removed and TRUE is returned, indicating that the remove operation was successful. Otherwise, FALSE is returned and the list is unaffected. The order of the list is unaffected, meaning that all of the elements after the removed element must be copied one index towards the beginning of the list. This gives the method an average case performance of O(n/2) where n is the number of elements in the array list.

Parameters

index - the index of the list element to remove.

Returns: whether or not the element was successfully removed.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

Bool om::util::ArrayList< T, SizeType, AllocatorType >::removeAtIndexUnordered ( SizeType index )

inline

Remove the element at the specified index, unordered version.

If the index is within the bounds of the list ( >= 0 && < getSizeType() ), then the list element at that index is removed and TRUE is returned, indicating that the remove operation was successful. Otherwise, FALSE is returned and the list is unaffected. The order of the list is affected when this method successfully removes the element. It works by replacing the element at the index to be removed with the last element in the list. This gives the method a worst case time complexity of O(1), that is much faster than the ordered remove methods.

Parameters

index - the index of the list element to remove.

Returns: whether or not the element was successfully removed.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

Bool om::util::ArrayList< T, SizeType, AllocatorType >::remove ( const T & object )

inline

Remove the first element equal to the parameter element, ordered version.

If this element is found, then it is removed and TRUE is returned. Otherwise, FALSE is returned and the list is unaffected. The order of the list is unaffected, meaning that all of the elements after the removed element must be copied one index towards the beginning of the list. This gives the method an average case performance of O(n) where n is the number of elements in the array list. This method's complexity is worse than the ordered index remove method because it must search through the list for the element and then copy all subsequent elements one position nearer to the start of the list.

Parameters

object - the list element to remove the first instance of.

Returns: whether or not the element was successfully removed.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

Bool om::util::ArrayList< T, SizeType, AllocatorType >::removeUnordered ( const T & object )

inline

Remove the first element equal to the parameter element, unordered version.

If this element is found, then it is removed and TRUE is returned. Otherwise, FALSE is returned and the list is unaffected. The order of the list is affected when this method successfully removes the element. It works by replacing the element at the index to be removed with the last element in the list. This gives the method a worst case time complexity of O(n), that is much faster than the ordered remove methods (O(n^2)).

Parameters

object - the list element to remove the first instance of.

Returns: whether or not the element was successfully removed.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

Bool om::util::ArrayList< T, SizeType, AllocatorType >::removeLast ( )

inline

Remove the last element in the array list.

If the array list has elements remaining in it, then the last element in the array list is removed and TRUE is returned. If the array list has no remaining elements, then FALSE is returned, indicating that the list was unchanged. This method has worst case O(1) time complexity.

Returns: whether or not the last element was successfully removed.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

SizeType om::util::ArrayList< T, SizeType, AllocatorType >::removeLast ( SizeType number )

inline

Remove the last N elements from the array list.

If the array list has at least N elements remaining in it, then the last N elements in the array list are removed and N is returned. If the array list has less than N elements, then the list will be completely cleared, resulting in an empty list. The method returns the number of elements successfully removed.

Returns: the number of elements removed from the end of the list.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

void om::util::ArrayList< T, SizeType, AllocatorType >::clear ( )

inline

Clear the contents of this array list.

This method calls the destructors of all elements in the array list and sets the number of elements to zero while maintaining the array's capacity.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

void om::util::ArrayList< T, SizeType, AllocatorType >::reset ( )

inline

Clear the contents of this array list and reclaim the allocated memory.

This method performs the same function as the clear() method, but also deallocates the previously allocated internal array and reallocates it to an small initial starting size. Calling this method is equivalent to assigning a brand new array list instance to this one.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

void om::util::ArrayList< T, SizeType, AllocatorType >::reset ( SizeType newCapacity )

inline

Clear the contents of this array list and reclaim the allocated memory.

This method performs the same function as the clear() method, but also deallocates the previously allocated internal array and reallocates it to a small initial starting size. Calling this method is equivalent to assigning a brand new array list instance to this one. This version of the reset() method allows the caller to specify the new starting capacity of the array list.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

Bool om::util::ArrayList< T, SizeType, AllocatorType >::contains ( const T & object ) const

inline

Return whether or not the specified element is in this list.

The method has average case O(n/2) time complexity, where n is the number of elements in the array list. This method is here for convenience. It just calls the array list's getSizeType() method, and tests to see if the return value is not equal to -1. It is recommended that if one wants the index of the element as well as whether or not it is contained in the list, they should use the getSizeType() method exclusively, and check the return value to make sure that the element is in the list. This avoids the double O(n/2) lookup that would be performed one naively called this method and then that method.

Parameters

object - the element to check to see if it is contained in the list.

Returns: whether or not the specified element is in the list.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

Bool om::util::ArrayList< T, SizeType, AllocatorType >::getIndex	(	const T &	object,
		SizeType &	index
	)		const

inline

Get the index of the list element equal to the parameter object.

If the specified element is not found within the list, then FALSE is returned. Otherwise, FALSE is returned and the index of the element in the list is placed in the output index parameter.

Parameters

object	- the object to find in the array list.
index	- a reference to the variable in which to place the index.

Returns: TRUE if the object was found, FALSE otherwise.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

T& om::util::ArrayList< T, SizeType, AllocatorType >::get ( SizeType index )

inline

Return the element at the specified index.

If the specified index is not within the valid bounds of the array list, then an exception is thrown indicating an index out of bounds error occurred. This is the non-const version of the get() method, allowing modification of the element.

Parameters

index - the index of the desired element.

Returns: a const reference to the element at the index specified by the parameter.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

const T& om::util::ArrayList< T, SizeType, AllocatorType >::get ( SizeType index ) const

inline

Return the element at the specified index.

If the specified index is not within the valid bounds of the array list, then an exception is thrown indicating an index out of bounds error occurred. This is the const version of the get() method, disallowing modification of the element.

Parameters

index - the index of the desired element.

Returns: a const reference to the element at the index specified by the parameter.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

T& om::util::ArrayList< T, SizeType, AllocatorType >::getFirst ( )

inline

Return a reference to the first element in the array list.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

const T& om::util::ArrayList< T, SizeType, AllocatorType >::getFirst ( ) const

inline

Return a const reference to the first element in the array list.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

T& om::util::ArrayList< T, SizeType, AllocatorType >::getLast ( )

inline

Return a reference to the last element in the array list.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

const T& om::util::ArrayList< T, SizeType, AllocatorType >::getLast ( ) const

inline

Return a const reference to the last element in the array list.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

T& om::util::ArrayList< T, SizeType, AllocatorType >::operator() ( SizeType index )

inline

Return the element at the specified index.

If the specified index is not within the valid bounds of the array list, then an exception is thrown indicating an index out of bounds error occurred. This is the const version of the operator (), disallowing modification of the element.

Parameters

index - the index of the desired element.

Returns: a const reference to the element at the index specified by the parameter.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

const T& om::util::ArrayList< T, SizeType, AllocatorType >::operator() ( SizeType index ) const

inline

Return the element at the specified index.

If the specified index is not within the valid bounds of the array list, then an exception is thrown indicating an index out of bounds error occurred. This is the const version of the operator (), disallowing modification of the element.

Parameters

index - the index of the desired element.

Returns: a const reference to the element at the index specified by the parameter.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

T& om::util::ArrayList< T, SizeType, AllocatorType >::operator[] ( SizeType index )

inline

Return the element at the specified index.

If the specified index is not within the valid bounds of the array list, then an exception is thrown indicating an index out of bounds error occurred.

Parameters

index - the index of the desired element.

Returns: a const reference to the element at the index specified by the parameter.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

const T& om::util::ArrayList< T, SizeType, AllocatorType >::operator[] ( SizeType index ) const

inline

Return the element at the specified index.

If the specified index is not within the valid bounds of the array list, then an exception is thrown indicating an index out of bounds error occurred. This is the const version of the operator [], disallowing modification of the element.

Parameters

index - the index of the desired element.

Returns: a const reference to the element at the index specified by the parameter.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

const T* om::util::ArrayList< T, SizeType, AllocatorType >::getPointer ( ) const

inline

Return a const pointer to the beginning of the internal array.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

T* om::util::ArrayList< T, SizeType, AllocatorType >::getPointer ( )

inline

Return a pointer to the beginning of the internal array.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

Bool om::util::ArrayList< T, SizeType, AllocatorType >::isEmpty ( ) const

inline

Return whether or not the array list has any elements.

This method returns TRUE if the size of the array list is greater than zero, and FALSE otherwise. This method is here for convenience.

Returns: whether or not the array list has any elements.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

SizeType om::util::ArrayList< T, SizeType, AllocatorType >::getSize ( ) const

inline

Return the number of elements in the array list.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

SizeType om::util::ArrayList< T, SizeType, AllocatorType >::getCapacity ( ) const

inline

Return the current storage capacity of the array list.

The capacity is the maximum number of elements that the array list can hold before it will have to resize its internal array.

Returns: the current capacity of the array list.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

void om::util::ArrayList< T, SizeType, AllocatorType >::setCapacity ( SizeType newCapacity )

inline

Set the capacity of the array list.

The capacity is the maximum number of elements that the array list can hold before it will have to resize its internal array. The capacity of the array list is set to the specified value unless this value is smaller than the number of elements in the array list. If so, the capacity remains unchanged.

Parameters

newCapacity the desired capacity of the array list.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

Iterator om::util::ArrayList< T, SizeType, AllocatorType >::getIterator ( )

inline

Return an iterator for the array list.

The iterator serves to provide a way to efficiently iterate over the elements of the array list. It is more useful for a linked list type of data structure, but it is provided for uniformity among data structures.

Returns: an iterator for the array list.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

ConstIterator om::util::ArrayList< T, SizeType, AllocatorType >::getIterator ( ) const

inline

Return a const iterator for the array list.

The iterator serves to provide a way to efficiently iterate over the elements of the array list. It is more useful for a linked list type of data structure, but it is provided for uniformity among data structures.

Returns: an iterator for the array list.

The documentation for this class was generated from the following file:

omArrayList.h

Classes

Public Member Functions

Detailed Description

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator> class om::util::ArrayList< T, SizeType, AllocatorType >

Constructor & Destructor Documentation

Member Function Documentation

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>
class om::util::ArrayList< T, SizeType, AllocatorType >