//------------------------------------------------------------------------------
// 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