container::SortedArrayList Class Reference

An array implementation of SortedList. More...

#include <sortedarraylist.h>

Inheritance diagram for container::SortedArrayList:

[legend]

Collaboration diagram for container::SortedArrayList:

[legend]

List of all members.

Public Member Functions
	SortedArrayList ()
	SortedArrayList (const SortedArrayList &pattern)
virtual	~SortedArrayList ()
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
	A polymorphic copy constructor.
Static Public Attributes
static const Info *const	TYPE_INFO
Protected Member Functions
virtual bool	insertSorted_impl (Entity *entity)
	Called by a template method.
virtual void	locateEntity (const Entity &key, int &index, Entity *&entity)
	Uses a binary search to locate the Entity object with the given key.
virtual bool	add_impl (Entity *entity)
	Called by a template method.
Private Member Functions
bool	binarySearch (const Entity &key, int &index) const
	Locate the Entity with the matching key using a binary search algorithm.

---

Detailed Description

An array implementation of SortedList.

---

Constructor & Destructor Documentation

container::SortedArrayList::SortedArrayList

(

)

{ }

container::SortedArrayList::SortedArrayList

(

const SortedArrayList &

pattern

)

{ }

container::SortedArrayList::~SortedArrayList

(

)

[virtual]

{ }

---

Member Function Documentation

bool container::SortedArrayList::add_impl

(

Entity *

entity

)

[protected, virtual]

Called by a template method.

See also:

Details documented in List::add

Implements container::List.

                                             {
   return insertSorted_impl(entity);
}

Here is the call graph for this function:

bool container::SortedArrayList::binarySearch	(	const Entity &	key,
		int &	index
	)			const [private]

Locate the Entity with the matching key using a binary search algorithm.

Returns:

true if found, false other wise

index will point to the Entity if found, otherwise index will point to where the key belongs if the corresponding Entity object were to be inserted

                                                                      {
   int tIndex = BASE_INDEX;
   int bIndex = getCount() - 1;
   index = BASE_INDEX; // default to first element for empty list

   for (int range = bIndex - tIndex; range >= 0; range = bIndex - tIndex) {
      index = (range / 2) + tIndex;

      int delta = key.compareKeyTo(*array[index]);
      if (delta > 0) {
         tIndex = ++index;
      } else if (delta < 0) {
         bIndex = index - 1;
      } else {
         return true;
      }
   }

   return false;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Object * container::SortedArrayList::clone

(

bool

deepCopy = false

)

const [virtual]

A polymorphic copy constructor.

Implements container::ArrayList.

{ }

bool container::SortedArrayList::insertSorted_impl

(

Entity *

entity

)

[protected, virtual]

Called by a template method.

See also:

Details documented in SortedList::insertSorted

Implements container::SortedList.

                                                      {
   int targetIndex = 0;
   if (binarySearch(*entity, targetIndex)) {
      return false;
   }
   openGap(targetIndex);
   array[targetIndex] = entity;
   return true;
}

Here is the call graph for this function:

Here is the caller graph for this function:

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

Uses a binary search to locate the Entity object with the given key.

Overrides the implementation in ArrayList. Uses a binary search for optimization.

See also:

List::locateEntity for method contract

Reimplemented from container::ArrayList.

                                                                                 {
   int i = 0;
   if (binarySearch(key, i)) {
      index = i;
      entity = array[i];
   } else {
      index = NO_MATCHING_ENTITY_INDEX_FLAG;
      entity = NULL;
   }
}

Here is the call graph for this function:

ostream & container::SortedArrayList::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::ArrayList.

                                                        {
   return this->ArrayList::renderState(os);
}

const Object::Info * container::SortedArrayList::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::ArrayList.

                                                  {
   return TYPE_INFO;
}

---

Member Data Documentation

const Object::Info *const container::SortedArrayList::TYPE_INFO [static]

Initial value:

      Object::typeInfoFactory("SortedArrayList")

Reimplemented from container::ArrayList.

---

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

• sortedarraylist.h
• sortedarraylist.cpp