Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Class Members | File Members

ArrayList Class Template Reference

#include <ArrayList.h>

List of all members.


Detailed Description

template<class ELEMENTTYPE>
class toolbox::ArrayList< ELEMENTTYPE >

The ArrayList class holds any type of object, storing them internally in an array.

So direct access is fast, but adding objects is not as fast as possible. If you add or remove objects, the array is automatically resized. To prevent the array from excessive reallocation, some extra cells are always held. They can be configured with the fill ratio attributes of the constructors. The class distinguished between the size, which is the number of reserved cells, and the count, which is the number of used cells.

See also:
See collections.txt for an overview of the available collection classes.
Author:
Thomas Jacob

Definition at line 45 of file ArrayList.h.

Public Member Functions

void Append (ELEMENTTYPE *Element)
 Appends an element to the array.

void AppendAll (const ArrayList< ELEMENTTYPE > *Elements)
 Appends all elements of another array list to this one.

 ArrayList (long initSize, int minimumFillRatio, int desiredFillRatio)
 Creates a new array list.

 ArrayList (long initSize)
 Creates a new array list.

 ArrayList ()
 Creates a new array list.

virtual int Compare (const ELEMENTTYPE *Element1, const ELEMENTTYPE *Element2) const
 Compares two elements and returns -1, if the first is less than the second, 0, if both elements are equal and 1, if the first is more than the second.

bool Contains (const ELEMENTTYPE *Element, int(*compare)(const ELEMENTTYPE *Element1, const ELEMENTTYPE *Element2)) const
 Returns whether a given element is contained in this array.

bool Contains (const ELEMENTTYPE *Element) const
 Returns whether a given element is contained in this array.

bool Delete (ELEMENTTYPE *Element)
 Deletes a given element from the array.

bool Delete (long from, long count)
 Deletes multiple elements at a given range.

bool Delete (long nr)
 Deletes an element at a given position.

void DeleteAll ()
 Deletes all elements from the array.

bool DeleteFirst ()
 Deletes the first element from the array.

bool DeleteLast ()
 Deletes the last element from the array.

int Find (const ELEMENTTYPE *Element, int(*compare)(const ELEMENTTYPE *Element1, const ELEMENTTYPE *Element2)) const
 Returns the 0-indexed position of a given element within the array list.

int Find (const ELEMENTTYPE *Element) const
 Returns the 0-indexed position of a given element within the array list.

ELEMENTTYPE * Get (long nr) const
 Returns the element at a given position.

long GetCount () const
 Returns the number of used array cells.

int GetDesiredFillRatio () const
 Returns the fill ratio after an array resize.

int GetFillRatio () const
 Returns the current fill ratio.

ELEMENTTYPE * GetFirst () const
 Returns the first element of the array.

ELEMENTTYPE * GetLast () const
 Returns the last element of the array.

int GetMinimumFillRatio () const
 Returns the minimum fill ratio for the array.

void Insert (ELEMENTTYPE *Element, long nr)
 Inserts an element before a given position.

void InsertAll (const ArrayList< ELEMENTTYPE > *Elements, long nr)
 Inserts all elements of another array list before a given position.

bool IsEmpty () const
 Returns, whether there are no elements in the array.

void Prepend (ELEMENTTYPE *Element)
 Prepends an element to the array.

void PrependAll (const ArrayList< ELEMENTTYPE > *Elements)
 Prepends all elements of another array list to this one.

ELEMENTTYPE * Replace (ELEMENTTYPE *NewElement, long nr)
 Replaces an element by another one.

void Shuffle ()
 Shuffles all entries randomly.

void Sort (int(*compare)(const ELEMENTTYPE *Element1, const ELEMENTTYPE *Element2))
 Sorts the elements in the array according to a given comparison function.

void Sort ()
 Sorts the elements in the array according to the Compare method.

bool Unlink (long from, long count)
 Removes multiple elements from the array.

ELEMENTTYPE * Unlink (ELEMENTTYPE *Element)
 Removes a given element from the array.

ELEMENTTYPE * Unlink (long nr)
 Removes an element at a given position.

void UnlinkAll ()
 Removes all elements from the array without freeing them or returning them.

ELEMENTTYPE * UnlinkFirst ()
 Removes the first element from the array.

ELEMENTTYPE * UnlinkLast ()
 Removes the last element from the array.

virtual ~ArrayList ()
 Destroys the array list.


Private Member Functions

void CheckSize (int newSize)
 Checks, if the array has to be resized, and resizes it if necessary.

void Init (long initSize, int minimumFillRatio, int desiredFillRatio)
 Initializes the array.

void Resize (long newSize)
 Resizes the array to a new size.


Private Attributes

long Count
 The number of used array cells.

int DesiredFillRatio
 The fill ratio after an array resize.

ELEMENTTYPE ** Elements
 The object array itself.

long InitSize
 The minimum and initial size of the array.

int MinimumFillRatio
 The minimum fill ratio for the array.

long Size
 The number of reserved array cells.


Constructor & Destructor Documentation

ArrayList  ) 
 

Creates a new array list.

ArrayList long  initSize  ) 
 

Creates a new array list.

Parameters:
initSize The minimum and initial size of the array list.

ArrayList long  initSize,
int  minimumFillRatio,
int  desiredFillRatio
 

Creates a new array list.

Parameters:
initSize The minimum and initial size of the array list.
minimumFillRatio The minimum fill ratio for the array list.
desiredFillRatio The fill ratio after an array resize.

virtual ~ArrayList  )  [virtual]
 

Destroys the array list.

When deleting the array list, all contained elements are also freed.


Member Function Documentation

void Append ELEMENTTYPE *  Element  ) 
 

Appends an element to the array.

Parameters:
Element The element to be appended.

void AppendAll const ArrayList< ELEMENTTYPE > *  Elements  ) 
 

Appends all elements of another array list to this one.

Warning:
The elements' memory is shared by both array lists, so one array should get its elements unlinked before destruction.
Parameters:
Elements The elements to be appended.

void CheckSize int  newSize  )  [private]
 

Checks, if the array has to be resized, and resizes it if necessary.

Parameters:
newSize The newly required minimum size.

virtual int Compare const ELEMENTTYPE *  Element1,
const ELEMENTTYPE *  Element2
const [virtual]
 

Compares two elements and returns -1, if the first is less than the second, 0, if both elements are equal and 1, if the first is more than the second.

This method is used for comparison in the sorting. Override this method to provide your own comparison.

Parameters:
Element1 The first element to be compared.
Element2 The second element to be compared.
Returns:
-1, 0 or 1, if Element1<Element2, Element1==Element2 or Element1>Element2.

bool Contains const ELEMENTTYPE *  Element,
int(*  compare)(const ELEMENTTYPE *Element1, const ELEMENTTYPE *Element2)
const
 

Returns whether a given element is contained in this array.

This method uses a given compare method to compare the elements.

Note:
This method performs a linear search.
Parameters:
Element The element to be searched.
compare A functions that compares two elements and returns -1, if the first is less than the second, 0, if both elements are equal and 1, if the first is more than the second.
Returns:
Whether the element is contained.

bool Contains const ELEMENTTYPE *  Element  )  const
 

Returns whether a given element is contained in this array.

This method uses the Compare method to compare the elements.

Note:
This method performs a linear search.
Parameters:
Element The element to be searched.
Returns:
Whether the element is contained.

bool Delete ELEMENTTYPE *  Element  ) 
 

Deletes a given element from the array.

The element is searched, removed from the array and freed. If the element is not contained, nothing happens. If the element is contained multiple times, only one instance is deleted.

Parameters:
Element The element to be deleted.
Returns:
Whether the element was found.

bool Delete long  from,
long  count
 

Deletes multiple elements at a given range.

The elements are removed from the array and freed.

Parameters:
from The starting position of the range. If from is invalid, nothing happens.
count The number of elements to be removed. If count is invalid, nothing happens.
Returns:
Whether the range was found.

bool Delete long  nr  ) 
 

Deletes an element at a given position.

The element is removed from the array and freed.

Parameters:
nr The position of the element. If nr is invalid, nothing happens.
Returns:
Whether the element was found.

void DeleteAll  ) 
 

Deletes all elements from the array.

All elements are removed from the array and freed.

bool DeleteFirst  )  [inline]
 

Deletes the first element from the array.

The element is removed from the array and freed. If the array is empty, nothing happens.

Returns:
Whether the element was found.

bool DeleteLast  ) 
 

Deletes the last element from the array.

The element is removed from the array and freed. If the array is empty, nothing happens.

Returns:
Whether the element was found.

int Find const ELEMENTTYPE *  Element,
int(*  compare)(const ELEMENTTYPE *Element1, const ELEMENTTYPE *Element2)
const
 

Returns the 0-indexed position of a given element within the array list.

This method uses a given compare method to compare the elements.

Note:
This method performs a linear search.
Parameters:
element The element to be looked up.
compare A functions that compares two elements and returns -1, if the first is less than the second, 0, if both elements are equal and 1, if the first is more than the second.
Returns:
The 0-indexed position of the element or -1, if the element is not found.

int Find const ELEMENTTYPE *  Element  )  const
 

Returns the 0-indexed position of a given element within the array list.

This method uses the Compare method to compare the elements.

Note:
This method performs a linear search.
Parameters:
element The element to be looked up.
Returns:
The 0-indexed position of the element or -1, if the element is not found.

ELEMENTTYPE* Get long  nr  )  const
 

Returns the element at a given position.

Parameters:
nr The position of the element. If nr is invalid, the method returns NULL.
Returns:
The element at the position or NULL.

long GetCount  )  const [inline]
 

Returns the number of used array cells.

This is the number of added objects.

Returns:
The number of used array cells.

int GetDesiredFillRatio  )  const [inline]
 

Returns the fill ratio after an array resize.

Returns:
The fill ratio after an array resize.
See also:
DesiredFillRatio

int GetFillRatio  )  const [inline]
 

Returns the current fill ratio.

Returns:
The current fill ratio.

ELEMENTTYPE* GetFirst  )  const
 

Returns the first element of the array.

If the array is empty, the method returns NULL.

Returns:
The first element or NULL.

ELEMENTTYPE* GetLast  )  const
 

Returns the last element of the array.

If the array is empty, the method returns NULL.

Returns:
The last element or NULL.

int GetMinimumFillRatio  )  const [inline]
 

Returns the minimum fill ratio for the array.

Returns:
The minimum fill ratio for the array.
See also:
MinimumFillRatio

void Init long  initSize,
int  minimumFillRatio,
int  desiredFillRatio
[private]
 

Initializes the array.

Parameters:
initSize The minimum and initial size of the array.
minimumFillRatio The minimum fill ratio for the array.
desiredFillRatio The fill ratio after an array resize.

void Insert ELEMENTTYPE *  Element,
long  nr
 

Inserts an element before a given position.

All elements at and after the position are moved by one.

Parameters:
Element The element to be inserted.
nr The position to insert before. If nr is invalid, nothing happens.

void InsertAll const ArrayList< ELEMENTTYPE > *  Elements,
long  nr
 

Inserts all elements of another array list before a given position.

All elements at and after the position are moved.

Warning:
The elements' memory is shared by both array lists, so one array should get its elements unlinked before destruction.
Parameters:
Elements The elements to be inserted.
nr The position to insert before. If nr is invalid, nothing happens.

bool IsEmpty  )  const [inline]
 

Returns, whether there are no elements in the array.

void Prepend ELEMENTTYPE *  Element  )  [inline]
 

Prepends an element to the array.

Parameters:
Element The element to be prepended.

void PrependAll const ArrayList< ELEMENTTYPE > *  Elements  )  [inline]
 

Prepends all elements of another array list to this one.

Warning:
The elements' memory is shared by both array lists, so one array should get its elements unlinked before destruction.
Parameters:
Elements The elements to be prepended.

ELEMENTTYPE* Replace ELEMENTTYPE *  NewElement,
long  nr
 

Replaces an element by another one.

The replaced element is not freed, but returned.

Parameters:
NewElement The element that replaces the old one.
nr The position of the element to be replaced. If nr is invalid, nothing happens and the method returns NULL.
Returns:
The old element.

void Resize long  newSize  )  [private]
 

Resizes the array to a new size.

The elements are preserved.

Parameters:
newSize The new size for the array.

void Shuffle  ) 
 

Shuffles all entries randomly.

void Sort int(*  compare)(const ELEMENTTYPE *Element1, const ELEMENTTYPE *Element2)  ) 
 

Sorts the elements in the array according to a given comparison function.

The whole array has a sorted order afterwards, but is not harmed at all in any other way. All elements remain the same.

Parameters:
compare A functions that compares two elements and returns -1, if the first is less than the second, 0, if both elements are equal and 1, if the first is more than the second.

void Sort  )  [inline]
 

Sorts the elements in the array according to the Compare method.

The whole array has a sorted order afterwards, but is not harmed at all in any other way. All elements remain the same.

bool Unlink long  from,
long  count
 

Removes multiple elements from the array.

The elements are not freed.

Parameters:
from The starting position of the range. If from is invalid, nothing happens.
count The number of elements to be removed. If count is invalid, nothing happens.
Returns:
Whether the range was found.

ELEMENTTYPE* Unlink ELEMENTTYPE *  Element  ) 
 

Removes a given element from the array.

The element is not freed, but returned. If the element is not contained, nothing happens and the method returns NULL. If the element is contained multiple times, only one instance is unlinked.

Parameters:
Element The element to be removed.
Returns:
The element or NULL.

ELEMENTTYPE* Unlink long  nr  ) 
 

Removes an element at a given position.

The element is not freed, but returned.

Parameters:
nr The position of the element. If nr is invalid, nothing happens and the method returns NULL.
Returns:
The element or NULL.

void UnlinkAll  ) 
 

Removes all elements from the array without freeing them or returning them.

Warning:
No element is freed, so you have to have a pointer to the objects, or the memory is lost.

ELEMENTTYPE* UnlinkFirst  )  [inline]
 

Removes the first element from the array.

The element is not freed, but returned. If the array is empty, nothing happens and the method returns NULL.

Returns:
The element or NULL.

ELEMENTTYPE* UnlinkLast  ) 
 

Removes the last element from the array.

The element is not freed, but returned. If the array is empty, nothing happens and the method returns NULL.

Returns:
The element or NULL.


Member Data Documentation

long Count [private]
 

The number of used array cells.

This is the number of added objects.

Definition at line 54 of file ArrayList.h.

int DesiredFillRatio [private]
 

The fill ratio after an array resize.

This happens, if all cells are used up, or if the fill ratio drops under the MinimumFillRatio value. The rest of the cell is reserved for further adding of objects.

Definition at line 64 of file ArrayList.h.

ELEMENTTYPE** Elements [private]
 

The object array itself.

Definition at line 69 of file ArrayList.h.

long InitSize [private]
 

The minimum and initial size of the array.

This is the number of minimum reserved cells.

Definition at line 75 of file ArrayList.h.

int MinimumFillRatio [private]
 

The minimum fill ratio for the array.

If the fill ratio drops under this value, it is resized to the DesiredFillRatio.

Definition at line 89 of file ArrayList.h.

long Size [private]
 

The number of reserved array cells.

This is not the number of used array cells.

See also:
Count

Definition at line 96 of file ArrayList.h.


The documentation for this class was generated from the following file:
Generated on Tue Oct 3 00:23:39 2006 for ToolBox by doxygen 1.3.6