container::LinkedList Class Reference

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

#include <linkedlist.h>

Inheritance diagram for container::LinkedList:

[legend]

Collaboration diagram for container::LinkedList:

[legend]

List of all members.

Classes
class	Node
	LinkedList uses Node objects to form a list of Entity objects. More...
Public Member Functions
virtual	~LinkedList ()
	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.
Static Public Attributes
static const Info *const	TYPE_INFO = Object::typeInfoFactory("LinkedList")
Protected Member Functions
	LinkedList ()
	Creates an empty list.
	LinkedList (const LinkedList &pattern)
	NOT IMPLEMENTED. Creates a deep copy of the pattern list.
virtual bool	toNext (Node *&cursor)
virtual bool	deleteCurrent_impl ()
	Called by a template method.
virtual Entity *	extractCurrentEntity_impl ()
	Called by a template method.
Protected Attributes
Node *	current
	List cursor.
Node *	head
	Dummy node that marks the beginning of the list.
Node *	tail
	Dummy node that marks the end of the list.

---

Detailed Description

A mostly complete linked-list implementation of List.

Derived directly from List, LinkedList is an abstract class that implements most of List using doubly-linked nodes.

---

Constructor & Destructor Documentation

container::LinkedList::LinkedList

(

)

[protected]

Creates an empty list.

head and tail are allocated and pointed to each other. current is pointed to the tail node.

                      : head(new Node()), tail(new Node()) {
   current = tail;

   // Point dummy nodes to each other
   head->next = tail;
   head->prev = NULL;
   tail->prev = head;
   tail->next = NULL;
}

container::LinkedList::LinkedList

(

const LinkedList &

pattern

)

[protected]

NOT IMPLEMENTED. Creates a deep copy of the pattern list.

Copies of all nodes and their Entities will are created for the new list.

Todo:

Implement copy constructor

{ }

container::LinkedList::~LinkedList

(

)

[virtual]

Free all memory associated with this list.

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

                        {
   purgeContents();
   delete head;
   delete tail;
}

Here is the call graph for this function:

---

Member Function Documentation

Entity * container::LinkedList::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 (current->entity);
}

Here is the call graph for this function:

Here is the caller graph for this function:

bool container::LinkedList::deleteCurrent_impl

(

)

[protected, virtual]

Called by a template method.

See also:

Details documented in List::deleteCurrent

Implements container::List.

                                    {
   if (isTail()) return false;

   Node *doomedNode = current;
   current = doomedNode->next;
   delete doomedNode;
   return true;
}

Here is the call graph for this function:

Entity * container::LinkedList::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 < 0)) {
      return NULL;
   }

   Node * node = head;
   for (int i = 0; toNext(node); i++) {
      if (i == index) {
         return node->entity;
      }
   }

   // should never get here
   return NULL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Entity * container::LinkedList::extractCurrentEntity_impl

(

)

[protected, virtual]

Called by a template method.

See also:

Details documented in List::extractCurrentEntity

Implements container::List.

                                               {
   if (isTail()) return NULL;

   Node *doomedNode = current;
   current = doomedNode->next;
   Entity * entity = doomedNode->extractEntity();
   delete doomedNode;
   return entity;
}

Here is the call graph for this function:

bool container::LinkedList::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 (current == tail) return (false);
   if (current != head->next) return (false);
   return (true);
}

bool container::LinkedList::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 (tail->prev == current) return (true);
   return (false);
}

bool container::LinkedList::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.

                              {
   if (current == tail) return (true);
   return (false);
}

Here is the caller graph for this function:

void container::LinkedList::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.

                                                                            {
   Node * node = head;
   int i = 0;
   while (toNext(node)) {
      if (key.compareKeyTo(*node->entity) == 0) {
         index = i;
         entity = node->entity;
         return;
      }
      i++;
   }
   index = NO_MATCHING_ENTITY_INDEX_FLAG;
   entity = NULL;
}

Here is the call graph for this function:

ostream & container::LinkedList::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::OrderedLinkedList, and container::SortedLinkedList.

                                                   {
   this->List::renderState(os);
   if (isTail()) {
      os << " TAIL<--CURSOR";
   }
   os << " contents{";
   const struct LinkedList::Node* node = head->next;

   for (int i = 0; node != tail; i++) {
      if (i > 0) {
         os << ", ";
      }
      const Entity* entity = node->entity;
      os << std::endl << "      [" << i << ']' << entity;
      if (node == current) {
         os << " <--CURSOR";
      }
      node = node->next;
   }

   return os << "}";
}

Here is the call graph for this function:

bool container::LinkedList::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.

                         {
   current = head->next;
   if (current == tail) return (false);

   return (true);
}

Here is the caller graph for this function:

bool container::LinkedList::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 = tail->prev;

   return (true);
}

Here is the call graph for this function:

bool container::LinkedList::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.

                        {
   return toNext(current);
}

Here is the caller graph for this function:

bool container::LinkedList::toNext

(

Node *&

cursor

)

[protected, virtual]

/brief Performs the toNext opperation on an arbitrary Node, as opposed to the public toNext() which opperates on the list cursor

                                     {
   if (cursor == tail) return (false);
   cursor = cursor->next;
   return (cursor != tail);
}

Here is the caller graph for this function:

bool container::LinkedList::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 (current == head->next) return (false);
   current = current->prev;
   return (true);
}

void container::LinkedList::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 = tail;
}

const Object::Info * container::LinkedList::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::OrderedLinkedList, and container::SortedLinkedList.

                                             {
   return TYPE_INFO;
}

---

Member Data Documentation

Node* container::LinkedList::current [protected]

List cursor.

Points to the current node

Node* container::LinkedList::head [protected]

Dummy node that marks the beginning of the list.

current never points to head.

Todo:

Considering allowing current to point to head.

Node* container::LinkedList::tail [protected]

Dummy node that marks the end of the list.

current is allowed to point to tail. It does so when the list is empty, when the list has been completely iterated, after toTail() is called, or possibly after toNext() is called.

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

Reimplemented from container::List.

Reimplemented in container::OrderedLinkedList, and container::SortedLinkedList.

---

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

• linkedlist.h
• linkedlist.cpp