list.cpp

#ifndef __LIST_CPP
#define __LIST_CPP

#include "list.h"


///////////////////////////////////////////////////////////////////////////////
//
// class implementation to store data and links
//
///////////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////////
//
// default constructor; creates an empty node 
//
// param: 
//
// result: none
//
///////////////////////////////////////////////////////////////////////////////

Node::Node()
{
  // prev, next and data are null
  m_Prev = m_Next = NULL;
  m_Data = NULL;

  // don't do an auto delete
  m_AutoDel = FALSE;
}


///////////////////////////////////////////////////////////////////////////////
//
// creates an node with an data value and connects to prev and next
//
// param: 
//
// result: none
//
///////////////////////////////////////////////////////////////////////////////

Node::Node(PNode prev, PNode next, PVOID data, BOOL autoDel)
{
  // connect node
  Prev(prev);
  Next(next);
	
  // set data value
  m_Data = data;

  // set auto delete flag
  m_AutoDel = autoDel;
}


///////////////////////////////////////////////////////////////////////////////
//
// destructor
//
// param: 
//
// result: none
//
///////////////////////////////////////////////////////////////////////////////

Node::~Node()
{
  // disconnect from list
  if(m_Prev)
    m_Prev->m_Next = m_Next;

  if(m_Next)
    m_Next->m_Prev = m_Prev;

  // if auto delete ist set delete data pointer
  if(m_Data && m_AutoDel)
    delete m_Data;

  m_Prev = m_Next = NULL;
  m_Data = NULL;
  m_AutoDel = FALSE;
}


///////////////////////////////////////////////////////////////////////////////
//
// gets the previous node
//
// param: 
//
// result: m_Prev
//
///////////////////////////////////////////////////////////////////////////////

PNode Node::Prev() const
{
  return m_Prev;
}


///////////////////////////////////////////////////////////////////////////////
//
// sets the previous node and returns the node set
//
// param:  prev - previous node to set
//
// result: m_Prev
//
///////////////////////////////////////////////////////////////////////////////

PNode Node::Prev(PNode prev)
{
  if(prev)
    prev->m_Next = this;

  return m_Prev = prev;
}


///////////////////////////////////////////////////////////////////////////////
//
// gets the next node
//
// param: 
//
// result: m_Next
//
///////////////////////////////////////////////////////////////////////////////

PNode Node::Next() const
{
  return m_Next;
}


///////////////////////////////////////////////////////////////////////////////
//
// sets the next node and returns the node set
//
// param:  next - previous node to set
//
// result: m_Next
//
///////////////////////////////////////////////////////////////////////////////

PNode Node::Next(PNode next)
{
  if(next)
    next->m_Prev = this;

  return m_Next = next;
}


///////////////////////////////////////////////////////////////////////////////
//
// gets the data value
//
// param: 
//
// result: m_Data
//
///////////////////////////////////////////////////////////////////////////////

PVOID Node::Data() const
{
  return m_Data;
}


///////////////////////////////////////////////////////////////////////////////
//
// sets the data value and returns the data set
//
// param:  data - data value to set
//
// result: m_Data
//
///////////////////////////////////////////////////////////////////////////////

PVOID Node::Data(PVOID data)
{
  // if auto delete is set delete current data
  if(m_Data && m_AutoDel)
    delete m_Data;

  return m_Data = data;
}


///////////////////////////////////////////////////////////////////////////////
//
// gets the auto delete value
//
// param: 
//
// result: m_AutoDel
//
///////////////////////////////////////////////////////////////////////////////

BOOL Node::AutoDel() const
{
  return m_AutoDel;
}


///////////////////////////////////////////////////////////////////////////////
//
// sets the auto delete value and returns the value set
//
// param:  autoDel - auto delete value to set
//
// result: m_AutoDel
//
///////////////////////////////////////////////////////////////////////////////

BOOL Node::AutoDel(BOOL autoDel)
{
  return m_AutoDel = autoDel;
}


///////////////////////////////////////////////////////////////////////////////
//
// class implementation to store chained links
//
///////////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////////
//
// default constructor; creates an empty list
//
// param:  
//
// result: 
//
///////////////////////////////////////////////////////////////////////////////

List::List()
{
  // first an last node are null
  m_Head = m_Tail = NULL;
  m_Items = 0;
	
  // initialize a critical section object
  InitializeCriticalSection(&m_CritSect);
}


///////////////////////////////////////////////////////////////////////////////
//
// destructor; removes all nodes in the list
//
// param:  
//
// result: 
//
///////////////////////////////////////////////////////////////////////////////

List::~List()
{
  RemoveAll();

  // free the critical section object
  DeleteCriticalSection(&m_CritSect);
}


///////////////////////////////////////////////////////////////////////////////
//
// gets the first node in the list
//
// param: 
//
// result: m_Head
//
///////////////////////////////////////////////////////////////////////////////

PNode List::HeadPos() const
{
  PNode headNode;

  //EnterCriticalSection(m_CritSect);
  headNode = m_Head;
  //LeaveCriticalSection(m_CritSect);

  return headNode;
}


///////////////////////////////////////////////////////////////////////////////
//
// gets the last node in the list
//
// param: 
//
// result: m_Tail
//
///////////////////////////////////////////////////////////////////////////////

PNode List::TailPos() const
{
  PNode tailNode;

  //EnterCriticalSection(m_CritSect);
  tailNode = m_Tail;
  //LeaveCriticalSection(m_CritSect);

  return tailNode;
}


///////////////////////////////////////////////////////////////////////////////
//
// gets the node before a node
//
// param:  node
//
// result: previous node from node ( if there is one) or null
//
///////////////////////////////////////////////////////////////////////////////

PNode List::PrevPos(PNode node) const
{
  PNode prevNode;

  //EnterCriticalSection(m_CritSect);
  prevNode = node ? node->Prev() : NULL;
  //LeaveCriticalSection(m_CritSect);

  return prevNode;
}


///////////////////////////////////////////////////////////////////////////////
//
// gets the node after a node
//
// param:  node
//
// result: next node from node ( if there is one) or null
//
///////////////////////////////////////////////////////////////////////////////

PNode List::NextPos(PNode node) const
{
  PNode nextNode;

  //EnterCriticalSection(m_CritSect);
  nextNode = node ? node->Next() : NULL;
  //LeaveCriticalSection(m_CritSect);

  return nextNode;
}


///////////////////////////////////////////////////////////////////////////////
//
// gets the data pointer from the first node in the list
//
// param:  
//
// result: data pointer from head ( if there is one) or null
//
///////////////////////////////////////////////////////////////////////////////

PVOID List::Head() const
{
  PVOID head;

  //EnterCriticalSection(m_CritSect);
  head = m_Head ? m_Head->Data() : NULL;
  //LeaveCriticalSection(m_CritSect);

  return head;
}


///////////////////////////////////////////////////////////////////////////////
//
// sets the data pointer in the first node in the list
//
// param:  data    - data pointer to set
//         autoDel - turn autoDel on or off
//
// result: data pointer set
//
///////////////////////////////////////////////////////////////////////////////

PVOID List::Head(PVOID data, BOOL autoDel)
{
  if(m_Head) {
    // if auto delete is on we have to delete the old pointer
    if(m_Head->AutoDel() && m_Head->Data())
      delete m_Head->Data();

    m_Head->Data(data);
    m_Head->AutoDel(autoDel);
  }

  return m_Head ? m_Head->Data() : NULL;
}


///////////////////////////////////////////////////////////////////////////////
//
// gets the data pointer from the last node in the list
//
// param:  
//
// result: data pointer from tail ( if there is one) or null
//
///////////////////////////////////////////////////////////////////////////////

PVOID List::Tail() const
{
  return m_Tail ? m_Tail->Data() : NULL;
}


///////////////////////////////////////////////////////////////////////////////
//
// sets the data pointer in the last node in the list
//
// param:  data    - data pointer to set
//         autoDel - turn autoDel on or off
//
// result: data pointer set
//
///////////////////////////////////////////////////////////////////////////////

PVOID List::Tail(PVOID data, BOOL autoDel)
{
  if(m_Tail) {
    // if auto delete is on we have to delete the old pointer
    if(m_Tail->AutoDel() && m_Tail->Data())
      delete m_Tail->Data();

    m_Tail->Data(data);
    m_Tail->AutoDel(autoDel);
  }

  return m_Tail ? m_Tail->Data() : NULL;
}


///////////////////////////////////////////////////////////////////////////////
//
// gets the data pointer from the node before node
//
// param:  node - current node
//
// result: data pointer from node before node ( if there is one) or null
//
///////////////////////////////////////////////////////////////////////////////

PVOID List::Prev(PNode node) const
{
  return node && node->Prev() ? node->Prev()->Data() : NULL;
}


///////////////////////////////////////////////////////////////////////////////
//
// sets the data pointer in the node before node
//
// param:  node    - current node
//         data    - data pointer to set
//         autoDel - turn autoDel on or off
//
// result: data pointer set
//
///////////////////////////////////////////////////////////////////////////////

PVOID List::Prev(PNode node, PVOID data, BOOL autoDel)
{
  PNode prevNode = node ? node->Prev() : NULL;
	
  if(prevNode) {
    // if auto delete is set delete the old data pointer
    if(prevNode->AutoDel() && prevNode->Data())
      delete prevNode->Data();

    prevNode->Data(data);
    prevNode->AutoDel(autoDel);
  }

  return prevNode ? prevNode->Data() : NULL;
}


///////////////////////////////////////////////////////////////////////////////
//
// gets the data pointer from the node after node
//
// param:  node - current node
//
// result: data pointer from node after node ( if there is one) or null
//
///////////////////////////////////////////////////////////////////////////////

PVOID List::Next(PNode node) const
{
  return node && node->Next() ? node->Next()->Data() : NULL;
}


///////////////////////////////////////////////////////////////////////////////
//
// sets the data pointer in the after before node
//
// param:  node    - current node
//         data    - data pointer to set
//         autoDel - turn autoDel on or off
//
// result: data pointer set
//
///////////////////////////////////////////////////////////////////////////////

PVOID List::Next(PNode node, PVOID data, BOOL autoDel)
{
  PNode nextNode = node ? node->Next() : NULL;
	
  if(nextNode) {
    // if auto delete is set delete the old data pointer
    if(nextNode->AutoDel() && nextNode->Data())
      delete nextNode->Data();

    nextNode->Data(data);
    nextNode->AutoDel(autoDel);
  }

  return nextNode ? nextNode->Data() : NULL;
}


///////////////////////////////////////////////////////////////////////////////
//
// gets the data pointer from node
//
// param:  node - current node
//
// result: data pointer from node ( if there is one) or null
//
///////////////////////////////////////////////////////////////////////////////

PVOID List::This(PNode node) const
{
  return node ? node->Data() : NULL;
}


///////////////////////////////////////////////////////////////////////////////
//
// sets the data pointer in node
//
// param:  node    - current node
//         data    - data pointer to set
//         autoDel - turn autoDel on or off
//
// result: data pointer set
//
///////////////////////////////////////////////////////////////////////////////

PVOID List::This(PNode node, PVOID data, BOOL autoDel)
{
  if(node) {
    // if auto delete is set delete the old data pointer
    if(node->AutoDel() && node->Data())
      delete node->Data();

    node->Data(data);
    node->AutoDel(autoDel);
  }

  return node ? node->Data() : NULL;
}


///////////////////////////////////////////////////////////////////////////////
//
// creates a new node at head of list and stores the data pointer
//
// param:  data    - data pointer to set
//         autoDel - turn autoDel on or off
//
// result: pointer to created node
//
///////////////////////////////////////////////////////////////////////////////

PNode List::AddHead(PVOID data, BOOL autoDel)
{
  // alloc memory for the new node
  PNode node = new Node(NULL, m_Head, data, autoDel);
	
  if(node) {
    m_Head = node;

    // connect the node in the list
    if(!m_Tail)
      m_Tail = node;

    m_Items++;
  }

  return node;
}


///////////////////////////////////////////////////////////////////////////////
//
// creates a new node at head of list and stores the data pointer
//
// param:  data    - data pointer to set
//         autoDel - turn autoDel on or off
//
// result: pointer to created node
//
///////////////////////////////////////////////////////////////////////////////

PNode List::AddTail(PVOID data, BOOL autoDel)
{
  // alloc memory for the new node
  PNode node = new Node(m_Tail, NULL, data, autoDel);
	
  if(node) {
    // connect the node in the list
    if(!m_Head)
      m_Head = node;

    m_Tail = node;

    m_Items++;
  }

  return node;
}


///////////////////////////////////////////////////////////////////////////////
//
// removes a node from the list; there is no check, if the node belongs to the 
// list
//
// param:  node - node to remove
//
// result: true  - success
//         false - failure (node was null)
//
///////////////////////////////////////////////////////////////////////////////

BOOL List::Remove(PNode node)
{
  if(node) {
    // look on first and last postion of list
    if(node == m_Head)
      m_Head = node->Next();

    if(node == m_Tail)
      m_Tail = node->Prev();

    delete node;
    m_Items--;

    return TRUE;
  }

  return FALSE;
}


///////////////////////////////////////////////////////////////////////////////
//
// removes all nodes from the list
//
// param:  
//
// result: true  - success
//         false - failure
//
///////////////////////////////////////////////////////////////////////////////

BOOL List::RemoveAll()
{
  // clear all nodes
  for(PNode node = m_Head; node;) {
    PNode tmpNode = node->Next();

    delete node;

    node = tmpNode;
  }

  // reset list members
  m_Head = m_Tail = NULL;
  m_Items = 0;

  return TRUE;
}


///////////////////////////////////////////////////////////////////////////////
//
// removes all nodes from the list which data pointer are null 
//
// param:  
//
// result: true  - success
//         false - failure
//
///////////////////////////////////////////////////////////////////////////////

BOOL List::Compress()
{
  // clear all nodes if the data pointer is null
  for(PNode node = m_Head; node;) {
    PNode tmpNode = node->Next();

    if(!node->Data())
      Remove(node);

    node = tmpNode;
  }

  return TRUE;
}


///////////////////////////////////////////////////////////////////////////////
//
// checks the integrity of the list (first forward and then backward)
//
// param:  
//
// result: true  - success (integrity is ok)
//         false - failure (integrity has a failure)
//
///////////////////////////////////////////////////////////////////////////////

BOOL List::Check()
{
  {
    // first walk forward
    for(PNode node = m_Head; node; ) {
      if(node->Next() == m_Tail)
        break;

      if(!node->Next())
        return FALSE;
    }
  }
  // then walk backward
  for(PNode node = m_Tail; node; ) {
    if(node->Prev() == m_Head)
      break;

    if(!node->Prev())
      return FALSE;
  }

  return TRUE;
}


///////////////////////////////////////////////////////////////////////////////
//
// gets the number of nodes in the list
//
// param:  
//
// result: number of nodes
//
///////////////////////////////////////////////////////////////////////////////

DWORD List::Items() const
{
  return m_Items;
}


///////////////////////////////////////////////////////////////////////////////
//
// gets if the list is empty or not
//
// param:  
//
// result: true  - list is empty
//         false - list is not empty
//
///////////////////////////////////////////////////////////////////////////////

BOOL List::IsEmpty() const
{
  return m_Items ? TRUE : FALSE;
}


///////////////////////////////////////////////////////////////////////////////
//
// class implementation to iterate a list
//
///////////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////////
//
// constructor for a list iterator
//
// param:  list      - pointer to a list
//         setAtHead - iterator begins at head
//
// result: 
//
///////////////////////////////////////////////////////////////////////////////

ListItr::ListItr(PList listPtr, BOOL setAtHead)
{
  m_Node = 
    (m_List = listPtr) ? setAtHead ? listPtr->HeadPos() : listPtr->TailPos() : NULL;
}


///////////////////////////////////////////////////////////////////////////////
//
// destructor for a list iterator
//
// param:  
//
// result: 
//
///////////////////////////////////////////////////////////////////////////////

ListItr::~ListItr()
{
}


///////////////////////////////////////////////////////////////////////////////
//
// returns a pointer to the list attached with the list iterator
//
// param:  
//
// result: pointer to attached list
//
///////////////////////////////////////////////////////////////////////////////

PList ListItr::List() const
{
  return m_List;
}


///////////////////////////////////////////////////////////////////////////////
//
// attaches a list with the list iterator
//
// param:  list      - pointer to list to attach
//         setAtHead - position where the iterator begins
//
// result: pointer to attached list
//
///////////////////////////////////////////////////////////////////////////////

PList ListItr::List(PList listPtr, BOOL setAtHead)
{
  m_Node = 
    (m_List = listPtr) ? setAtHead ? listPtr->HeadPos() : listPtr->TailPos() : NULL;

  return m_List;
}


///////////////////////////////////////////////////////////////////////////////
//
// resets the iterator at begin or end of the list
//
// param:  setAtHead - position where the iterator begins
//
// result: pointer to attached list
//
///////////////////////////////////////////////////////////////////////////////

PNode ListItr::Reset(BOOL setAtHead)
{
  return m_Node = 
    m_List ? setAtHead ? m_List->HeadPos() : m_List->TailPos() : NULL;
}


///////////////////////////////////////////////////////////////////////////////
//
// iteration operator for the list (pre-inkrement)
//
// param:  
//
// result: pointer the data for current node
//
///////////////////////////////////////////////////////////////////////////////

PVOID ListItr::operator ++ ()
{
  return (m_Node = m_List && m_Node ? m_List->NextPos(m_Node) : NULL) ? 
    m_List->This(m_Node) : NULL;
}


///////////////////////////////////////////////////////////////////////////////
//
// iteration operator for the list (post-inkrement)
//
// param:  
//
// result: pointer the data for current node
//
///////////////////////////////////////////////////////////////////////////////

PVOID ListItr::operator ++ (int)
{
  PVOID data = m_List && m_Node ? m_List->This(m_Node) : NULL;

  m_Node = m_List && m_Node ? m_List->NextPos(m_Node) : NULL;
	
  return data;
}


///////////////////////////////////////////////////////////////////////////////
//
// iteration operator for the list (pre-inkrement)
//
// param:  
//
// result: pointer the data for current node
//
///////////////////////////////////////////////////////////////////////////////

PVOID ListItr::operator -- ()
{
  return (m_Node = m_List && m_Node ? m_List->PrevPos(m_Node) : NULL) ? 
    m_List->This(m_Node) : NULL;
}


///////////////////////////////////////////////////////////////////////////////
//
// iteration operator for the list (post-inkrement)
//
// param:  
//
// result: pointer the data for current node
//
///////////////////////////////////////////////////////////////////////////////
PVOID ListItr::operator -- (int)
{
  PVOID data = m_List && m_Node ? m_List->This(m_Node) : NULL;

  m_Node = m_List && m_Node ? m_List->PrevPos(m_Node) : NULL;
	
  return data;
}


///////////////////////////////////////////////////////////////////////////////
//
// conversation operator for the list; checks if begin or end of list is reached
//
// param:  
//
// result: true  - begin or end is not reached
//         false - begin or end is reached
//
///////////////////////////////////////////////////////////////////////////////

ListItr::operator int ()
{
  return m_List && m_Node ? TRUE : FALSE;
}


#endif