//------------------------------------------------------------------------------
//    module: stdList.h                                                       //
//                                                                            //
//    Simple but time efficient single linked list template                   //
//                                                                            //
//    copyright 2000-2003 by Lars Haendel                                     //
//    home: www.newty.de                                                      //
//                                                                            //
//    This program is free software; you can redistribute it and/or modify    //
//    it under the terms of the GNU General Public License as published by    //
//    the Free Software Foundation as version 2 of the License.               //
//                                                                            //
//    This program is distributed in the hope that it will be useful,         //
//    but WITHOUT ANY WARRANTY; without even the implied warranty of          //
//    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the           //
//    GNU General Public License for more details.                            //
//                                                                            //
//    You should have received a copy of the GNU General Public License       //
//    along with this program; if not, write to the Free Software             //
//    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.               //
//                                                                            //
//------------------------------------------------------------------------------

#ifndef STDLIST_H
#define STDLIST_H

// note: do not(!) include <string> to prevent dozens of warnings "...not expanded inline"
#include <stdio>           //          sprintf()

#include "exception.h"     //          exception handling



//----------------------------------------------------------------------------------------------------------------------
// utility function: iterates list and calls 'delete' for each element; however this will only compile if <TEntry>
// is a pointer
template <class TList> void DeleteEntries(TList* list)
{
   if(list->Size() > 0)                   // if list is not empty ...
   {
      list->Reset();                      // ... position to top, ...
      for(int i=0;i<list->Size();i++)     // ... iterate the list and ...
      {
         list->Next();
         delete list->Get();              // ... call 'delete' for each element
      }
   }
};


//----------------------------------------------------------------------------------------------------------------------
// template definition of list element
template <class TEntry> class TListElement
{
public:
   TListElement*  next;       // pointer to next element
   TEntry         entry;      // element itself
};


//----------------------------------------------------------------------------------------------------------------------
// class template for simple but efficient single linked list
// Attention: If the list elements are pointers you(!) must release the memory the pointer point to. You may use the
// utility function DeleteEntries() to do this. If elements are inserted into the list they will be copied.
// Take care if the list element is a class which has pointers. You may have to implement a copy constructor!
// Attention: If you call Reset() you have to call Next() before you can access the first list element!
template <class TEntry> class TStdList
{
private:

   // pointers to list elements
   TListElement<TEntry>* start;           // first
   mutable TListElement<TEntry>* act;     // actual
   mutable TListElement<TEntry>* prev;    // previous

   int size;                              // # list elements
   mutable int _pos;                      // index of actual list position

   char szName[STS];                      // name of the list, useful in debug mode

public:

   // constructor/destructor
   TStdList();
   ~TStdList();

   void Clear();                                                                 // clear all list elements
   void SetName(const char* _szName) { strcpy(szName, _szName); };               // set the list's name

   // functions to position in list
   inline void Reset() const;                                   // position to first element
   inline void Next() const;                                    // position to next element
   void        Pos(const int& __pos) const;                     // position to element with specified index
   const int&  Pos() const { return _pos; };                    // return current position index


   // functions to get and set list elements
   inline TEntry& Get();                                                         // return element at actual position
   inline const TEntry& Get() const;                                             // const version
   inline TEntry& Get(const int& i) { Pos(i); return Get(); };                   // return i-th element in list
   inline const TEntry& Get(const int& i) const { Pos(i); return Get(); };       // const version
   inline TEntry& Ins();                                       //  insert new empty element after(!) actual position

   // overwrite(!) element at actual position with given element
   inline void Put(TEntry& entry)   { (*act).entry = entry; };
   inline void Ins(TEntry& entry)   { Ins() = entry;  };       // insert given element after(!) actual position
   inline void Del();                                          // delete element at actual position from list

   void Cat(TStdList<TEntry>* list);                           // concatenate/append given list at the end of this list

   inline const int& Size() const { return size; };            // return # elements in list
};


//----------------------------------------------------------------------------------------------------------------------
// constructor
template <class TEntry> TStdList<TEntry>::TStdList()
{
   strcpy(szName, "TStdList<TEntry>");

   // create dummy element at begin of list
   prev           = new TListElement<TEntry>;
   (*prev).next   = NULL;

   act   = prev;
   start = prev;

   size  = 0;
   _pos  = -1;
}


//----------------------------------------------------------------------------------------------------------------------
// destructor
template <class TEntry> TStdList<TEntry>::~TStdList()
{
   Clear();                            // clear all list elements
   delete start;                       // delete the dummy element at top of list
}


//----------------------------------------------------------------------------------------------------------------------
// clear all list elements
template <class TEntry> void TStdList<TEntry>::Clear()
{
   if(size > 0)                  // if list is not empty ...
   {
      Reset();                   // position to top of list
      Next();

      int t = size;              // remember # list elements ...

      for(int i=0;i<t;i++)
         Del();                  // and delete them
   }
}


//----------------------------------------------------------------------------------------------------------------------
// position to first list element
template <class TEntry> void TStdList<TEntry>::Reset() const
{
   // throw exception if list is empty
// IF_TRUE_THROW_NAMED_ERR( (*start).next == NULL, name, "::reset() called on empty list!")

   prev   = start;            // set previous and actual element
   act    = start;            //

   _pos   = -1;
}


//----------------------------------------------------------------------------------------------------------------------
// position forward to next element
template <class TEntry> inline void TStdList<TEntry>::Next() const
{
   // throw exception if actual element is NULL, i.e. not existing
   IfTrueThrowTypeB(!act, "Function Next() called after last element in list!", szName, "stdList.h");


   prev  = act;
   act   = (*act).next;    // position forward

   _pos++;                 // increment position index
}


//----------------------------------------------------------------------------------------------------------------------
// position to element at specified position
template <class TEntry> void TStdList<TEntry>::Pos(const int& __pos) const
{
   // throw exception if index is 'out of range'
   IfTrueThrowTypeB(__pos<-1 || __pos>=size, "Function Pos() called with illegal value!", szName, "stdList.h");

   // if specified position is before(!) actual position
   if(_pos > __pos)
   {
      Reset();          // reset to top
      Pos(__pos);       // ... and call again

      return;
   }

   int k=__pos-_pos;    // estimate # of elements from actual to desired position

   // ... and call Next() as many times
   for(int i=0;i<k;i++)
      Next();
}


//----------------------------------------------------------------------------------------------------------------------
// return element at actual list position
template <class TEntry> TEntry& TStdList<TEntry>::Get()
{
   // throw exception if actual element is NULL, i.e. not existing
   IfTrueThrowTypeB(!act, "Function Get() called on NULL-pointer!", szName, "stdList.h");
   IfTrueThrowTypeB(_pos==-1,"Function Get() called while list was positioned before first element! Call Next() before!"
                     , szName, "stdList.h");

   return (*act).entry;    // return element
}


template <class TEntry> const TEntry& TStdList<TEntry>::Get() const
{
   // throw exception if actual element is NULL, i.e. not existing
   IfTrueThrowTypeB(!act, "Function Get() called on NULL-pointer!", szName, "stdList.h");

   return (*act).entry;    // return element
}


//----------------------------------------------------------------------------------------------------------------------
// insert new (and un-initialized) element after(!) the actual position
template <class TEntry> TEntry& TStdList<TEntry>::Ins()
{
   // throw exception if actual element is NULL, i.e. not existing
   IfTrueThrowTypeB(!act, "Function Ins() called on NULL-pointer!", szName, "stdList.h");


   TListElement<TEntry>* old  = (*act).next;    // remember pointer to next element
   (*act).next    = new TListElement<TEntry>;   // insert element
   prev           = act;
   act            = (*act).next;                // position forward
   (*act).next    = old;                        // connect to next element (set stored pointer)

   size++;                                      // increment # element counter and ...
   _pos++;                                      // position index

   return (*act).entry;                         // return new element
}


//----------------------------------------------------------------------------------------------------------------------
// concatenate/append another list to the end of this one
template <class TEntry> void TStdList<TEntry>::Cat(TStdList<TEntry>* list)
{
   list->Reset();             // position on first entry of other list
   list->Next();

   Pos(Size()-1);             // position to end of this list
   act->next = list->act;     // append other list


   size+=list->size;          // manipulate sizes
   list->size=0;
}


//----------------------------------------------------------------------------------------------------------------------
// delete list element at actual list position
template <class TEntry> void TStdList<TEntry>::Del()
{
   // throw exception if element at actual position is NULL, i.e. not existing
   IfTrueThrowTypeB( !act || _pos == -1, "Function Del() called on NULL-pointer!", szName, "stdList.h");


   (*prev).next = (*act).next;      // connect previous element to next element
   delete act;                      // delete element at actual list position
   act = (*prev).next;              // position forward, note: there is no checking if element exists

   size--;                          // decrement element counter
}
#endif