#ifndef _List_h
#define _List_h

#include <stdlib.h>

#include "containr.h"
#include "wtrace\werror.h"


#ifndef false
        #define false 0
        #define true  1
#endif


// prototyping

template<class T>
class Node;



// class definitions

template <class T>
class ZeigerListe : public Container<T>
{
  public:
                ZeigerListe();
                virtual ~ZeigerListe();

                virtual void empty();    // Leert die Liste.

                virtual void emptyWithElementDelete(); // Leert die Liste und loesch die Elemente.

                virtual inline T* first();       // Setzt AktListenPosition auf das erste Element
                                                          // und liefert den Zeiger darauf.

                virtual inline T* last();        // Setzt AktListenPosition auf das letzte Element.
                                                          // und liefert den Zeiger darauf.
                                                                // das letzte Element ist immer leer

                virtual inline T* next();        // Erhoeht AktListenPosition um eins.
                                                          // und liefert den Zeiger darauf.

                virtual inline T* previous();    // Erniedrigt AktListenPostion um eins.
                                                                // und liefert den Zeiger darauf.

                virtual inline int isFirst();     // Ist der Anfang der Liste erreicht?
                virtual inline int isLast();     // Ist das Ende der Liste erreicht?
                virtual inline int isEmpty(); // Ist die Liste vielleicht leer?

                virtual T* insert(T* new_pointer); // Fuegt neues Element vor der AktPos ein.
                virtual T* append(T* new_pointer); // Haengt neues Element an di List an.


                virtual T* remove();         // Loescht den Akt. Knoten aus der Liste
                                                                         // und liefert den Zeiger auf das Element.

                virtual void removeWithElementDelete(); // Loescht den Akt. Knoten aus der Liste
                                                                          // und das Element des Knotens!

                virtual inline T* retrieve();      // Liefert einen Zeiger auf das aktuelle Element.

                virtual void exchange( int pos1, int pos2 ); // vertauscht die beiden Elemente der Positionen  pos1 und pos2

                virtual inline int setPos(int pos); // 0..ende-1
                virtual inline int getPos();        // 0..ende-1

protected:
                Node<T> *aktPtr;     // Die aktuelle Position in der Liste;
                Node<T> *anfPtr;     // Zeiger auf Anfang der Liste.
                Node<T> *endPtr;       // Zeiger auf Ende der Liste.
                int aktPos;
                int anfPos;
                int endPos;

};


template<class T>
class Node
{
 public:
  Node *Nachfolger;
  Node *Vorgaenger;
  T* Zeiger;
};




// Die Implementierung der Elementfunktionen von ZeigerListe !!

template <class T>
ZeigerListe<T>::ZeigerListe()

{
  Node<T> *N;
  N = new Node<T>;
  N->Zeiger = NULL;
  N->Nachfolger = NULL;
  N->Vorgaenger=NULL;

  endPtr = N;
  aktPtr = N;
  anfPtr = N;

  anfPos        = 0;
  aktPos        = 0;
  endPos        = 0;
}


template <class T>
ZeigerListe<T>::~ZeigerListe()
{
  while(anfPtr != NULL)
  {
                         Node<T> *N = anfPtr;
                         anfPtr = N->Nachfolger;
                         delete N;
  }
}


template <class T>
void ZeigerListe<T>::empty()
{
  while(anfPtr != endPtr)   // Alle Knoten loeschen.
  {
                Node<T> *N = anfPtr;
                anfPtr = N->Nachfolger;
                delete N;          // Knoten loeschen
  }

  anfPtr->Vorgaenger = NULL;

  aktPtr = endPtr;

  aktPos = 0;
  anfPos = 0;
  endPos = 0;

}

template <class T>
void ZeigerListe<T>::emptyWithElementDelete()
{
  while(anfPtr != endPtr)   // Alle Knoten loeschen.
  {
                Node<T> *N = anfPtr;
                anfPtr = N->Nachfolger;

                delete N->Zeiger;  // Element loeschen

                delete N;          // Knoten loeschen
  }

  anfPtr->Vorgaenger = NULL;

  aktPtr = endPtr;

  aktPos = 0;
  anfPos = 0;
  endPos = 0;
}


template <class T>
T* ZeigerListe<T>::first()
{
 if ( isEmpty() ) // is list empty?
  return NULL;
 aktPos = 0;
 aktPtr = anfPtr;
 return aktPtr->Zeiger; /* falls Liste leer wird NULL zurueckgegeben */
}


template <class T>
T* ZeigerListe<T>::last()
{
 aktPtr=endPtr;
 aktPos=endPos;
 // das letzte Element ist immer leer!!!!
 //return endPtr->Zeiger;
 return NULL;
}

template <class T>
T* ZeigerListe<T>::next()
{
        if (aktPtr!=endPtr)
        {
                aktPos++;
                return (aktPtr=aktPtr->Nachfolger)->Zeiger;
        }
        else;
                return NULL; // falls Liste am Ende ist wird NULL zurueckgegeben
}

template <class T>
T* ZeigerListe<T>::previous()
{
        if (aktPtr!=anfPtr)
        {
                aktPos--;
                return (aktPtr=aktPtr->Vorgaenger)->Zeiger;
        }
        else
                return NULL; // falls Liste am Anfang ist wird NULL zurueckgegeben
}

template <class T>
int ZeigerListe<T>::isLast()
{
  return int(aktPtr==endPtr);
}

template <class T>
int ZeigerListe<T>::isFirst()
{
  return int(aktPtr==anfPtr);
}

template <class T>
int ZeigerListe<T>::isEmpty()
{
  return int(anfPtr==endPtr);
}


template <class T>
T* ZeigerListe<T>::insert(T* NewPointer)
{
        char*   __fn = "ZeigerListe::insert";

        T* R;
        Node<T> *N;
        N = new Node<T>;

        if (N!=NULL) {
                N->Nachfolger=aktPtr;
                N->Vorgaenger=aktPtr->Vorgaenger;
                N->Zeiger=NewPointer;

                if (!isEmpty())
                        aktPtr->Vorgaenger->Nachfolger=N;
                aktPtr->Vorgaenger=N;


                R=NewPointer;

                if (isEmpty() || (aktPtr==anfPtr) )
                        anfPtr=N;
                aktPtr=N;

                endPos++;
        }
        else
        {
                ErrRecover( __fn, "", "mem allocation error" );
                exit(1);
        }
        return R;
}

template <class T>
T* ZeigerListe<T>::append(T* NewPointer)
{
                  last();
                  return insert(NewPointer);
}



template <class T>
T* ZeigerListe<T>::retrieve()
{
  return aktPtr->Zeiger; // wenn Liste leer, dann wird NULL zurueckgeben!
}


template <class T>
T* ZeigerListe<T>::remove()
{
  Node<T> *N=NULL;
  T* R=NULL;
  if (isEmpty());  // nichts tun
  else
  {
                        N=aktPtr;
                        R=aktPtr->Zeiger;
                        if ( isFirst() ) { // Anfang der Liste
                                         N->Nachfolger->Vorgaenger=NULL;
                                         anfPtr=N->Nachfolger;
                                         aktPtr=anfPtr;
                        }
                        else
                                         if ( isLast() ) { // Ende der Liste
                                                N->Vorgaenger->Nachfolger=NULL;
                                                endPtr = N->Vorgaenger;
                                                aktPtr = endPtr;
                                         }
                                         else { // mittendrin
                                                N->Nachfolger->Vorgaenger=N->Vorgaenger;
                                                N->Vorgaenger->Nachfolger=N->Nachfolger;
                                                aktPtr=aktPtr->Nachfolger;   // Loeschen wie ENTFERNEN nicht wie BACKSPACE!
                                         }
                        delete N;
  endPos--;

  }
  return R;
};

template <class T>
void ZeigerListe<T>::removeWithElementDelete()
{
  Node<T> *N;
  if (isEmpty());  // nichts tun
  else {
                        N=aktPtr;
                        if ( isFirst() ) { // Anfang der Liste
                                         N->Nachfolger->Vorgaenger=NULL;
                                         anfPtr=N->Nachfolger;
                                         aktPtr=anfPtr;
                        }
                        else
                                         if ( isLast() ) { // Ende der Liste
                                                N->Vorgaenger->Nachfolger=NULL;
                                                endPtr = N->Vorgaenger;
                                                aktPtr = endPtr;
                                         }
                                         else { // mittendrin
                                                N->Nachfolger->Vorgaenger=N->Vorgaenger;
                                                N->Vorgaenger->Nachfolger=N->Nachfolger;
                                                aktPtr=aktPtr->Nachfolger;   // Loeschen wie ENTFERNEN nicht wie BACKSPACE!
                                         }
                        delete N->Zeiger; // Element loeschen
                        delete N;         // Knoten loeschen
  endPos--;
  }
};


template <class T>
int ZeigerListe<T>::setPos(int pos)
{
 if ((pos<0) || (pos>endPos))
  return -1;     // -1   wenn pos nicht geht
 else
 {
  aktPtr=anfPtr;
  for (int i=0; i<pos; i++)
        aktPtr=aktPtr->Nachfolger;
  return (aktPos=pos);
 }
}

template <class T>
int ZeigerListe<T>::getPos()
{
 return aktPos;
}


template <class T>
void ZeigerListe<T>::exchange( int pos1, int pos2 )
{
        char*           __fn = "ZeigerListe<T>::switch";
        T*                      posData;
        Node<T>*        posPtr;

        int oldPos = aktPos;

        if( pos1 == pos2 )
                return;

        if ( pos1 < 0 )
        {
                pos1 = 0;
                ErrRecover( __fn, "", "pos1( %d ) < 0; setting pos1 = 0!", pos1 );
        }
        if ( pos1 > endPos )
        {
                pos1 = endPos;
                ErrRecover( __fn, "", "pos1( %d ) > endPos( %d ); setting pos1 = endPos!", pos1, endPos );
        }
        if ( pos2 < 0 )
        {
                pos2 = 0;
                ErrRecover( __fn, "", "pos2( %d ) < 0; setting pos2 = 0!", pos2 );
        }
        if ( pos2 > endPos )
        {
                pos2 = endPos;
                ErrRecover( __fn, "", "pos2( %d ) > endPos( %d ), setting pos2 = endPos!", pos2, endPos );
        }

        setPos( pos1 );
        posPtr = aktPtr;
        posData = aktPtr->Zeiger;

        setPos( pos2 );
        posPtr->Zeiger = aktPtr->Zeiger;
        aktPtr->Zeiger = posData;

        setPos( oldPos );
}



#endif // _LIST_H