///////////////////Software Control Header///////////////////////////////////
// TSingLst.h - Library to support singly list
//
// $LogThisFile$ \Projects\UtilCode\Include\TSingLst.h
// 
// V01.01 15/10/2000 2337
//  CSinglyList - Remove accept pointer to element(default = m_head).
//                Return true on success.
//                Accept pointer insertion.
// 
// V01.00 10/10/2000 2159
//  Initial revision.
// 
// This code is freely distributed to help the development of complex
// software in any field using C++. The author is not held responsible
// for any damage caused by the usage of the code.
// The author should be acknowledged for the use of this piece of code in
// commercial software.
//
// Bug reports and suggestions are welcomed to report to
//
//          tzzstan@hotmail.com
/////////////////////////////////////////////////////////////////////////////

#ifndef __TS_SList__
#define __TS_SList__

#include <iostream.h>

/////////////////////////////////////////////////////////////////////////////
// CSinglyNode - Node representation of an object type.
//
// Desctiption: Manipulate object in node type.
//
// TSTan   12 Aug 2000
/////////////////////////////////////////////////////////////////////////////
template<class T> class CSinglyNode
{
   T *m_data;
   CSinglyNode<T> *m_next;

public:
   CSinglyNode(CSinglyNode<T> &, CSinglyNode<T> *Next = NULL); // copy const
   CSinglyNode(T &, CSinglyNode<T> *Next = NULL);
   CSinglyNode(T *, CSinglyNode<T> *Next = NULL);
   ~CSinglyNode();

///////////////////
// Modifiers
///////////////////

   // Set to next pointer
   void SetNext(CSinglyNode<T> *next) {m_next = next;}
   CSinglyNode<T> &operator=(CSinglyNode<T> &);

///////////////////
// Data retrieval
///////////////////

   // Return data pointer
   T *Data() const {return m_data;}
   // Return next pointer
   CSinglyNode<T> *Next() const {return m_next;}
};

/////////////////////////////////////////////////////////////////////////////
// CSinglyNode(CSinglyNode<T> &original, CSinglyNode<T> *Next)
//
// Desctiption: Copy constructor that creates a copy from original.
//
// original - Original node.
// Next - Optional pointer to next element(Defaulted to NULL).
//
// TSTan   12 Aug 2000
/////////////////////////////////////////////////////////////////////////////
template<class T> CSinglyNode<T>::CSinglyNode(CSinglyNode<T> &original,
   CSinglyNode<T> *Next)
{
   m_data = new T(*(original.m_data));
   m_next = Next;
}

/////////////////////////////////////////////////////////////////////////////
// operator=(CSinglyNode<T> &original
//
// Desctiption: Assignment with copy of T in node.
//
// Original - Original node.
//
// TSTan   12 Aug 2000
/////////////////////////////////////////////////////////////////////////////
template<class T> CSinglyNode<T> &CSinglyNode<T>::
   operator=(CSinglyNode<T> &original)
{
   delete m_data;
   m_data = new T(*(original.m_data));
   m_next = NULL;

   return *this;
}

/////////////////////////////////////////////////////////////////////////////
// CSinglyNode(T &Element, CSinglyNode<T> *Next)
//
// Desctiption: Constructor to create copy of T in node.
//
// Element - Reference to the element to be inserted.
// Next - Optional pointer to next element(Defaulted to NULL).
//
// TSTan   12 Aug 2000
/////////////////////////////////////////////////////////////////////////////
template<class T> CSinglyNode<T>::CSinglyNode(T &Element,
   CSinglyNode<T> *Next)
{
   m_data = new T(Element);
   m_next = Next;
}

/////////////////////////////////////////////////////////////////////////////
// CSinglyNode(T *Element, CSinglyNode<T> *Next)
//
// Desctiption: Constructor to create copy of T in node.
//
// Element - Reference to the element to be inserted.
// Next - Optional pointer to next element(Defaulted to NULL).
//
// TSTan   14 Oct 2000
/////////////////////////////////////////////////////////////////////////////
template<class T> CSinglyNode<T>::CSinglyNode(T *Element,
   CSinglyNode<T> *Next)
{
   m_data = Element;
   m_next = Next;
}

/////////////////////////////////////////////////////////////////////////////
// ~CSinglyNode()
//
// Desctiption: Destructor to clean up memory.
//
// TSTan   12 Aug 2000
/////////////////////////////////////////////////////////////////////////////
template<class T> CSinglyNode<T>::~CSinglyNode()
{
   delete m_data;
}

/////////////////////////////////////////////////////////////////////////////
// CSinglyList - class declaration of CSinglyList.
//
// Desctiption: Maintain objects in singly list.
//
// TSTan   12 Aug 2000
/////////////////////////////////////////////////////////////////////////////
template<class T> class CSinglyList
{
   int m_size;
   CSinglyNode<T> *m_head, *m_current;

   CSinglyNode<T> *CopyNodes(CSinglyNode<T> *);
   T *InsertTail(T &, CSinglyNode<T> *);
   T *InsertTail(T *, CSinglyNode<T> *);

public:
   // HEAD/TAIL to insert element.
   enum Location{
      HEAD,
      TAIL
   };

   CSinglyList(CSinglyList<T> &); // Copy constructor
   CSinglyList();
   ~CSinglyList();

///////////////////
// Modifiers
///////////////////
   T *Insert(T &, enum Location = HEAD);
   T *Insert(T *, enum Location = HEAD);
   bool Remove(T *Element = NULL);
   void RemoveAll();
   void ResetPtr();
   CSinglyNode<T> *Next();

   CSinglyList<T> &operator=(CSinglyList<T> &); // Assignment operator

///////////////////
// Data retrieval
///////////////////

   // Return data pointer to current node.
   T *Current() const {return m_current->Data();}
   // Return current pointer.
   CSinglyNode<T> *CurrentPtr() const {return m_current;};
   // Return true if the list is empty.
   bool IsEmpty() const {return !m_head;}
   // Return true if current point to valid element.
   bool IsValid() const {return !(m_current == NULL);}
   // Return the size of list.
   int Size() const {return m_size;}
   bool Exist(T &source);
};

/////////////////////////////////////////////////////////////////////////////
// Exist(T &source)
//
// Desctiption: Check whether 'source' exist in list.
//
// TSTan   29 Aug 2000
/////////////////////////////////////////////////////////////////////////////
template<class T> bool CSinglyList<T>::Exist(T &source)
{
   for(ResetPtr(); IsValid(); Next())
      if(*Current() == source)
         return true;

   return false;
}

/////////////////////////////////////////////////////////////////////////////
// ResetPtr()
//
// Desctiption: Set current pointer to the head of list.
//
// TSTan   13 Aug 2000
/////////////////////////////////////////////////////////////////////////////
template<class T> void CSinglyList<T>::ResetPtr()
{
   m_current = m_head;
}

/////////////////////////////////////////////////////////////////////////////
// Next()
//
// Desctiption: Set current pointer to the next of current node.
//
// TSTan   13 Aug 2000
/////////////////////////////////////////////////////////////////////////////
template<class T> CSinglyNode<T> *CSinglyList<T>::Next()
{
   if(m_current)
      m_current = m_current->Next();

   return m_current;
}

/////////////////////////////////////////////////////////////////////////////
// CSinglyList(CSinglyList<T> &original)
//
// Desctiption: Copy constructor that creates list from original.
//
// original - Original list.
//
// TSTan   12 Aug 2000
/////////////////////////////////////////////////////////////////////////////
template<class T> CSinglyList<T>::CSinglyList(CSinglyList<T> &original)
{
   m_head = NULL;
   m_current = NULL;
   m_size = 0;
   m_head = CopyNodes(original.m_head);
   ResetPtr();
}

/////////////////////////////////////////////////////////////////////////////
// operator=(CSinglyList<T> &original)
//
// Desctiption: Create list from original.
//
// original - Original list.
//
// TSTan   12 Aug 2000
/////////////////////////////////////////////////////////////////////////////
template<class T> CSinglyList<T> &CSinglyList<T>::
   operator=(CSinglyList<T> &original)
{
   RemoveAll();
   m_head = CopyNodes(original.m_head);
   ResetPtr();

   return *this;
}

/////////////////////////////////////////////////////////////////////////////
// CopyNodes(CSinglyNode<T> *thisNode)
//
// Desctiption: Function to recursively generates all nodes.
//
// thisNode - Pointer to node to generate
//
// TSTan   12 Aug 2000
/////////////////////////////////////////////////////////////////////////////
template<class T> CSinglyNode<T> *CSinglyList<T>::
   CopyNodes(CSinglyNode<T> *thisNode)
{
   if(thisNode)
   {
      m_head = CopyNodes(thisNode->Next());
      m_size++;
      return new CSinglyNode<T>(*thisNode, m_head);
   }

   return NULL;
}

/////////////////////////////////////////////////////////////////////////////
// CSinglyList()
//
// Desctiption: Constructor to initialize list members.
//
// TSTan   12 Aug 2000
/////////////////////////////////////////////////////////////////////////////
template<class T> CSinglyList<T>::CSinglyList()
{
   m_head = NULL;
   m_size = 0;
}

/////////////////////////////////////////////////////////////////////////////
// ~CSinglyList()
//
// Desctiption: Destructor to clean up memory.
//
// TSTan   12 Aug 2000
/////////////////////////////////////////////////////////////////////////////
template<class T> CSinglyList<T>::~CSinglyList()
{
   RemoveAll();
}

/////////////////////////////////////////////////////////////////////////////
// RemoveAll()
//
// Desctiption: Empty the list.
//
// TSTan   12 Aug 2000
/////////////////////////////////////////////////////////////////////////////
template<class T> void CSinglyList<T>::RemoveAll()
{
   while(m_head)
      Remove();

   m_head = NULL;
   m_current = NULL;
   m_size = 0;
}

/////////////////////////////////////////////////////////////////////////////
// Insert(T &Element)
//
// Desctiption: Insert one element into list.
//
// TSTan   12 Aug 2000
/////////////////////////////////////////////////////////////////////////////
template<class T> T *CSinglyList<T>::Insert(T &Element, enum Location where)
{
   if(where == HEAD)
   {
      CSinglyNode<T> *NewNode = new CSinglyNode<T>(Element, m_head);
      m_head = NewNode;
      m_size++;
      return NewNode->Data();
   }
   else
      return InsertTail(Element, m_head);
}

/////////////////////////////////////////////////////////////////////////////
// Insert(T *Element)
//
// Desctiption: Insert one element into list.
//
// TSTan   14 Oct 2000
/////////////////////////////////////////////////////////////////////////////
template<class T> T *CSinglyList<T>::Insert(T *Element, enum Location where)
{
   if(where == HEAD)
   {
      CSinglyNode<T> *NewNode = new CSinglyNode<T>(Element, m_head);
      m_head = NewNode;
      m_size++;
      return NewNode->Data();
   }
   else
      return InsertTail(Element, m_head);
}

/////////////////////////////////////////////////////////////////////////////
// InsertTail(T &Element, CSiglyNode<T> *thisNode)
//
// Desctiption: Insert one element into the end of list.
//
// TSTan   13 Aug 2000
/////////////////////////////////////////////////////////////////////////////
template<class T> T *CSinglyList<T>::InsertTail(T &Element,
   CSinglyNode<T> *thisNode)
{
   if(thisNode)
   {
      if(thisNode->Next())
         return InsertTail(Element, thisNode->Next());
      else
      {
         m_size++;
         thisNode->SetNext(new CSinglyNode<T>(Element));
         return thisNode->Next()->Data();
      }
   }
   else
   {
      m_size++;
      m_head = new CSinglyNode<T>(Element);
      return m_head->Data();
   }
}

/////////////////////////////////////////////////////////////////////////////
// InsertTail(T *Element, CSiglyNode<T> *thisNode)
//
// Desctiption: Insert one element into the end of list.
//
// TSTan   14 Oct 2000
/////////////////////////////////////////////////////////////////////////////
template<class T> T *CSinglyList<T>::InsertTail(T *Element,
   CSinglyNode<T> *thisNode)
{
   if(thisNode)
   {
      if(thisNode->Next())
         return InsertTail(Element, thisNode->Next());
      else
      {
         m_size++;
         thisNode->SetNext(new CSinglyNode<T>(Element));
         return thisNode->Next()->Data();
      }
   }
   else
   {
      m_size++;
      m_head = new CSinglyNode<T>(Element);
      return m_head->Data();
   }
}

/////////////////////////////////////////////////////////////////////////////
// Remove()
//
// Desctiption: Remove the first element from head.
//
// TSTan   12 Aug 2000
//
/////////////////////////////////////////////////////////////////////////////
template<class T> bool CSinglyList<T>::Remove(T *Element)
{
   if(!m_head)
      return false;

   if(Element == NULL)
      Element = m_head->Data();

   CSinglyNode<T> *PrevNode = NULL;
   for(CSinglyNode<T> *CurrentNode = m_head;
      CurrentNode; CurrentNode = CurrentNode->Next())
   {
      if(CurrentNode->Data() != Element)
      {
         PrevNode = CurrentNode;
         continue;
      }

      if(PrevNode)
         PrevNode->SetNext(CurrentNode->Next());
      else
         m_head = CurrentNode->Next();

      delete CurrentNode;
      m_size--;
      return true;
   }

   return false;
}

#endif