container::ArrayList Class Reference

A mostly complete array-list implementation of List. More...

#include <arraylist.h>

Inheritance diagram for container::ArrayList:

[legend]

Collaboration diagram for container::ArrayList:

[legend]

List of all members.

Public Member Functions
virtual	~ArrayList ()
	Free all memory associated with this list.
virtual bool	isFirst () const
	Return true if the cursor is pointing to first real node, false otherwise.
virtual bool	isLast () const
	Determine whether the list cursor is pointing to the last Entity.
virtual bool	isTail () const
	Return true if the cursor is pointing to the list tail, false otherwise.
virtual bool	toFirst ()
	Point the cursor to the first Entity in the list.
virtual bool	toLast ()
	Point the cursor to the last Entity in the list.
virtual void	toTail ()
	Point the cursor to the tail of the list.
virtual bool	toNext ()
	Point the cursor to the next Entity in the list.
virtual bool	toPrev ()
	Point the cursor to the previous Entity in the list.
virtual Entity *	currentEntity ()
	Return a pointer to the current Entity.
virtual void	locateEntity (const Entity &key, int &index, Entity *&entity)
	Locate the first Entity that matches the specified key.
virtual Entity *	entityAt (int index)
	Return a pointer to the Entity found at the specified, zero-based index.
virtual ostream &	renderState (ostream &os) const
	Write the state of an Object for debugging and demonstration.
virtual const Info *	typeInfo () const
	Return the instance of Object::Info that describes the class of this object.
virtual Object *	clone (bool deepCopy=false) const =0
	A polymorphic copy constructor.
Static Public Attributes
static const Info *const	TYPE_INFO = Object::typeInfoFactory("ArrayList")
Protected Member Functions
	ArrayList ()
	Creates an empty list with the default DEFAULT_INITIAL_CAPACITY.
	ArrayList (int initialCapacity, int additionalCapacity)
	Creates an empty list with the specified initialCapacity.
	ArrayList (const ArrayList &pattern)
	Create a shallow copy of the pattern list.
	ArrayList (const ArrayList &pattern, bool deepCopy)
	Create a shallow or deep copy of the pattern list.
void	allocateArray ()
void	closeGap ()
	Close the gap at the list cursor by shifting Enity objects up in the List.
void	closeGap (int index)
	Close the gap at index by shifting Enity objects up in the List.
void	openGap (int index)
	Open a new gap at index by shifting Enity objects down in the List.
bool	isAtCapacity () const
virtual bool	deleteCurrent_impl ()
	Called by a template method.
virtual Entity *	extractCurrentEntity_impl ()
	Called by a template method.
Protected Attributes
int	capacity
	The current capacity of this ArrayList. Reflects the current number of elements allocated for array.
int	additionalCapacity
	The number of elements that will be added to capacity when array needs to grow.
Entity **	array
	An array of pointers to Entity objects.
int	current
	An index that serves as the List cursor.
Static Protected Attributes
static const int	DEFAULT_INITIAL_CAPACITY = 4
	Initial capacity of the underlying array.
static const int	DEFAULT_ADDITIONAL_CAPACITY = 2
	The increment that will be added to capacity when the array needs to grow.
static const int	BASE_INDEX = 0
Private Member Functions
void	copyConstructor (const ArrayList &pattern, bool deepCopy=false)
	Helper method; does actual work of the copy constructors.

---

Detailed Description

A mostly complete array-list implementation of List.

Derived directly from List, ArrayList is an abstract class that implements most of List using an array of Entity objects. The array grows as needed. Currently it does not contract. It never leaves gaps, i.e., all array elements less than Container::getCount() are populated.

---

Constructor & Destructor Documentation

container::ArrayList::ArrayList

(

)

[protected]

Creates an empty list with the default DEFAULT_INITIAL_CAPACITY.

When the current capacity is exceeded the underlying array will grow by the DEFAULT_ADDITIONAL_CAPACITY.

                    : capacity(DEFAULT_INITIAL_CAPACITY),
additionalCapacity(DEFAULT_ADDITIONAL_CAPACITY), array(NULL) {
   current = getCount();
   allocateArray();
}

Here is the call graph for this function:

container::ArrayList::ArrayList	(	int	initialCapacity,
		int	additionalCapacity
	)			[protected]

Creates an empty list with the specified initialCapacity.

When the current capacity is exceeded the underlying array will grow by the specified additionalCapacity.

                                                     : capacity(initCapacity),
additionalCapacity(addCapacity), array(NULL) {
   current = getCount();
   allocateArray();
}

Here is the call graph for this function:

container::ArrayList::ArrayList

(

const ArrayList &

pattern

)

[protected]

Create a shallow copy of the pattern list.

A new underlying array of pointers will be allocated. The new array will point to the existing Entity objects from pattern.

Precondition:

pattern is a valid ArrayList

Postcondition:

this ArrayList is logically equivelent to pattern

this ArrayList and pattern will share the same Entity instances.

                                             {
   copyConstructor(pattern);
}

Here is the call graph for this function:

container::ArrayList::ArrayList	(	const ArrayList &	pattern,
		bool	deepCopy
	)			[protected]

Create a shallow or deep copy of the pattern list.

A new underlying array of pointers will be allocated. If deepCopy is false the new array will point to the existing Entity objects from pattern. If deepCopy is true then independent copies of Entity will be created.

Precondition:

pattern is a valid ArrayList

Postcondition:

this ArrayList is logically equivelent to pattern

If deepCopy was true then ArrayList is completely independent from the pattern list

                                                            {
   copyConstructor(pattern, deepCopy);
}

Here is the call graph for this function:

container::ArrayList::~ArrayList

(

)

[virtual]

Free all memory associated with this list.

Calls purgeContents(), so all Entity objects in the list will be deleted.

                      {
   purgeContents();
   delete array;
}

Here is the call graph for this function:

---

Member Function Documentation

void container::ArrayList::allocateArray

(

)

[protected]

                              {
   Entity ** oldArray = array;

   if (oldArray != NULL) {
      capacity += additionalCapacity;
   }

   array = new Entity*[capacity];

   // Copying old values
   for (int i = 0; i < getCount(); i++) {
      array[i] = oldArray[i];
   }

   // Initialize the rest to NULL
   for (int i = getCount(); i < capacity; i++) {
      array[i] = NULL;
   }

   if (oldArray != NULL) {
      delete [] oldArray;
   }
}

Here is the call graph for this function:

Here is the caller graph for this function:

virtual Object* container::ArrayList::clone

(

bool

deepCopy = false

)

const [pure virtual]

A polymorphic copy constructor.

Implements container::List.

Implemented in container::OrderedArrayList, and container::SortedArrayList.

void container::ArrayList::closeGap

(

int

index

)

[protected]

Close the gap at index by shifting Enity objects up in the List.

                                  {
   if (isTail()) {
      return;
   }

   if (current > index) {
      current--;
   }

   const int lastElementIndex = getCount() - 1;

   for (int i = index; i < lastElementIndex; i++) {
      array[i] = array[i + 1];
   }

   array[lastElementIndex] = NULL;
}

Here is the call graph for this function:

void container::ArrayList::closeGap

(

)

[protected]

Close the gap at the list cursor by shifting Enity objects up in the List.

                         {
   closeGap(current);
}

Here is the caller graph for this function:

void container::ArrayList::copyConstructor	(	const ArrayList &	pattern,
		bool	deepCopy = false
	)			[private]

Helper method; does actual work of the copy constructors.

                                                                       {
   setCount(pattern.getCount());
   additionalCapacity = pattern.additionalCapacity;
   current = pattern.current;
   capacity = pattern.getCount();
   if (capacity == 0) {
      capacity = DEFAULT_INITIAL_CAPACITY;
   }
   array = new Entity*[capacity];

   for (int i = 0; i < pattern.getCount(); i++) {
      if (deepCopy) {
         // point to copies of existing Entities
         array[i] = dynamic_cast<Entity*>(pattern.array[i]->clone(deepCopy));
      } else {
         // point to existing Entities (shallow copy)
         array[i] = pattern.array[i];
      }
   }

   // Initialize the rest to NULL
   for (int i = getCount(); i < capacity; i++) {
      array[i] = NULL;
   }
}

Here is the call graph for this function:

Here is the caller graph for this function:

Entity * container::ArrayList::currentEntity

(

)

[virtual]

Return a pointer to the current Entity.

Returns:

A pointer to the current Entity object. Returns NULL if the list was empty or if the cursor was not pointing to an Entity.

Precondition:

The list cursor points to an Entity

Postcondition:

The current Entity remains in the list

The state of the List is unchanged

Implements container::List.

                                  {
   if (isTail()) return (NULL);
   return (array[current]);
}

Here is the call graph for this function:

bool container::ArrayList::deleteCurrent_impl

(

)

[protected, virtual]

Called by a template method.

See also:

Details documented in List::deleteCurrent

Implements container::List.

                                   {
   if (isTail()) return false;

   Entity * entity = array[current];
   closeGap();
   delete entity;
   return true;
}

Here is the call graph for this function:

Entity * container::ArrayList::entityAt

(

int

index

)

[virtual]

Return a pointer to the Entity found at the specified, zero-based index.

Returns:

A pointer to the Entity at the specified index

Precondition:

The List must contain at least one Entity object.

A valid index must be specified. For example, if count is 1 then the only valid index is 0.

Postcondition:

The state of the list is unchanged including the cursor position

Implements container::List.

                                     {
   if ((index >= getCount()) || (index < BASE_INDEX)) {
      return NULL;
   }

   return array[index];
}

Here is the call graph for this function:

Entity * container::ArrayList::extractCurrentEntity_impl

(

)

[protected, virtual]

Called by a template method.

See also:

Details documented in List::extractCurrentEntity

Implements container::List.

                                              {
   if (isTail()) return NULL;

   Entity * entity = array[current];
   closeGap();
   return entity;
}

Here is the call graph for this function:

bool container::ArrayList::isAtCapacity

(

)

const [inline, protected]

                                          {
   return capacity == getCount();
}

Here is the call graph for this function:

Here is the caller graph for this function:

bool container::ArrayList::isFirst

(

)

const [virtual]

Return true if the cursor is pointing to first real node, false otherwise.

TRUE is only possible if the list is not empty.

Implements container::List.

                              {
   if (isEmpty()) {
      return false;
   }

   return current == BASE_INDEX;
}

Here is the call graph for this function:

Here is the caller graph for this function:

bool container::ArrayList::isLast

(

)

const [virtual]

Determine whether the list cursor is pointing to the last Entity.

true is only possible if the list is not empty.

Returns:

true if the list cursor is pointing to the last Entity of the list, false otherwise

Implements container::List.

                             {
   if (isEmpty()) {
      return false;
   }

   return current == (getCount() - 1);
}

Here is the call graph for this function:

bool container::ArrayList::isTail

(

)

const [virtual]

Return true if the cursor is pointing to the list tail, false otherwise.

false is only possible if the list is not empty.

Implements container::List.

                             {
   return current == getCount();
}

Here is the call graph for this function:

Here is the caller graph for this function:

void container::ArrayList::locateEntity	(	const Entity &	key,
		int &	index,
		Entity *&	entity
	)			[virtual]

Locate the first Entity that matches the specified key.

The position is returned as a zero based index. The first Entity that matches is returned. No further checking of the list is performed.

Returns:

The zero based index of the matching Entity. If a matching Entity is not found List::NO_MATCHING_ENTITY_INDEX_FLAG is returned in index instead.

entity will point to the matching Entity. If a matching Entity is not found, NULL is returned in entity instead.

Precondition:

A matching Entity is in the list

Postcondition:

The state of the list is unchanged including the cursor position

Implements container::List.

Reimplemented in container::SortedArrayList.

                                                                           {
   for (int i = 0; i < getCount(); i++) {
      if (key.compareKeyTo(*array[i]) == 0) {
         index = i;
         entity = array[i];
         return;
      }
   }

   index = NO_MATCHING_ENTITY_INDEX_FLAG;
   entity = NULL;
}

Here is the call graph for this function:

void container::ArrayList::openGap

(

int

index

)

[protected]

Open a new gap at index by shifting Enity objects down in the List.

                                 {
   if (isAtCapacity()) {
      allocateArray();
   }

   for (int i = getCount(); i > index; i--) {
      array[i] = array[i - 1];
   }

   if (current >= index) {
      current++;
   }
}

Here is the call graph for this function:

Here is the caller graph for this function:

ostream & container::ArrayList::renderState

(

ostream &

os

)

const [virtual]

Write the state of an Object for debugging and demonstration.

This method must not change the state of an Object; adding or removing debug statements should not change the behavior of a class. The implementation must be robust, e.g., NULL safe, etc. and work without an unrecoverable error for any state, excluding an Object's time of construction and destruction. It is not required for the implementation to be thread safe.

Precondition:

The Object has been fully constructed and is not in the process of destruction

Postcondition:

The state of the Object is unchanged

Reimplemented from container::List.

Reimplemented in container::OrderedArrayList, and container::SortedArrayList.

                                                  {
   this->List::renderState(os);
   os << " capacity(" << capacity << ")";
   if (isTail()) {
      os << " TAIL<--CURSOR";
   }
   os << " contents{";

   int first = BASE_INDEX;
   for (int i = first; i < getCount(); i++) {
      if (i > first) {
         os << ", ";
      }
      os << std::endl << "      [" << i << ']' << array[i];
      if (i == current) {
         os << " <--CURSOR";
      }
   }

   return os << "}";
}

Here is the call graph for this function:

bool container::ArrayList::toFirst

(

)

[virtual]

Point the cursor to the first Entity in the list.

Returns:

false if the list is empty; otherwise, true. A value of true doesn't imply that the cursor was moved, i.e., it may have already been pointing to the first Entity.

Precondition:

The list is not empty

Postcondition:

The list cursor points to the first Entity in the list

Implements container::List.

                        {
   if (isEmpty()) {
      return false;
   }

   current = BASE_INDEX;
   return true;
}

Here is the call graph for this function:

bool container::ArrayList::toLast

(

)

[virtual]

Point the cursor to the last Entity in the list.

Returns:

false if the list is empty; otherwise, true. A value of true doesn't imply that the cursor was moved, i.e., it may have already been pointing to the last Entity.

Precondition:

The list is not empty

Postcondition:

The list cursor points to the last Entity in the list

Implements container::List.

                       {
   if (isEmpty()) {
      return false;
   }

   current = getCount() - 1;
   return true;
}

Here is the call graph for this function:

bool container::ArrayList::toNext

(

)

[virtual]

Point the cursor to the next Entity in the list.

Returns:

true if the list cursor was moved and points to an Entity

false if the cursor was moved to the tail of list

false if the cursor was already pointing to the tail

Precondition:

The List is not empty

The list cursor is not pointing to the tail

Postcondition:

The list cursor has moved to the next Entity or to the tail if it was pointing to the last Entity

Implements container::List.

                       {
   if (isTail()) {
      return false;
   }

   current++;
   return !isTail();
}

Here is the call graph for this function:

bool container::ArrayList::toPrev

(

)

[virtual]

Point the cursor to the previous Entity in the list.

Calling toPrev() never leaves the cursor pointing to the head of the list.

Returns:

true if the list cursor was moved

false if the cursor is already pointing the first Entity in the list

false if the list is empty

Precondition:

The list is not empty

The list cursor is not pointing to the first Entity in the list

Postcondition:

The list cursor has moved to the previous Entity

Implements container::List.

                       {
   if (isFirst() || isEmpty()) {
      return false;
   }

   current--;
   return true;
}

Here is the call graph for this function:

void container::ArrayList::toTail

(

)

[virtual]

Point the cursor to the tail of the list.

This method should always succeed. A List should always have the concept a tail, i.e., the node or element just beyond the end of the list. No Entity is available at the tail cursor position.

Precondition:

A List has been constructed

Postcondition:

The list cursor points to the tail

Implements container::List.

                       {
   current = getCount();
}

Here is the call graph for this function:

const Object::Info * container::ArrayList::typeInfo

(

)

const [virtual]

Return the instance of Object::Info that describes the class of this object.

Instantiation of Object::Info is controlled by the protected method Object::typeInfoFactory(const string&). Each sub-class of Object should create one and only one instance of Object::Info.

Reimplemented from container::List.

Reimplemented in container::OrderedArrayList, and container::SortedArrayList.

                                            {
   return TYPE_INFO;
}

---

Member Data Documentation

int container::ArrayList::additionalCapacity [protected]

The number of elements that will be added to capacity when array needs to grow.

Entity** container::ArrayList::array [protected]

An array of pointers to Entity objects.

const int container::ArrayList::BASE_INDEX = 0 [static, protected]

int container::ArrayList::capacity [protected]

The current capacity of this ArrayList. Reflects the current number of elements allocated for array.

int container::ArrayList::current [protected]

An index that serves as the List cursor.

Points to the current Entity

const int container::ArrayList::DEFAULT_ADDITIONAL_CAPACITY = 2 [static, protected]

The increment that will be added to capacity when the array needs to grow.

It's set to a small value for testing the dynamic growth behavior.

const int container::ArrayList::DEFAULT_INITIAL_CAPACITY = 4 [static, protected]

Initial capacity of the underlying array.

It's set to a small value for testing the dynamic growth behavior.

const Object::Info *const container::ArrayList::TYPE_INFO = Object::typeInfoFactory("ArrayList") [static]

Reimplemented from container::List.

Reimplemented in container::OrderedArrayList, and container::SortedArrayList.

---

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

• arraylist.h
• arraylist.cpp