#ifndef _List_h
#define _List_h

#include <stdlib.h>
#include <iostream.h>

#include "containr.h"


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


// prototyping

template<class T>
class Node;

template <class T>
class ZeigerListe;

// class definitions

template <class T>
class ZeigerListe : public Container<T>
{
  public:
    ZeigerListe( void );
    ZeigerListe( ZeigerListe<T>& );  // Copykonstruktor

    ZeigerListe<T>& operator=( ZeigerListe<T>& );

    virtual ~ZeigerListe( void );

    void empty();         // Leert die Liste.

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

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

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

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

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

    inline int isFirst(); // Ist der Anfang der Liste erreicht?
    inline int isLast();  // Ist das Ende der Liste erreicht?
    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 die Liste an.
                                       // aktPos ist jetzt das neue Element 


    T* remove( void );   // Loescht den Akt. Knoten aus der Liste
                         // und liefert den Zeiger auf das Element.
    T* remove( T* p );   // Loescht den Knoten mit Zeiger p und gibt p zurueck
                         // wenn p nicht vorhanden wird NULL zurueckgegeben

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

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

    int find( T* );          // gibt die Position des gefunden Elementes
                             // -1 sonst

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


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( ZeigerListe<T>& list )
{
  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;
  for( list.first(); !list.isLast(); list.next() )
    append( list.retrieve() );
}

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

template <class T>
ZeigerListe<T>& ZeigerListe<T>::operator=( ZeigerListe<T>& list )
{
  empty();
  for( list.first(); !list.isLast(); list.next() )
    append( list.retrieve() );
  return *this;
}

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;
 // Es wird immer NULL zurueckgegeben!!!!!!!!
 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)
{
  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
  {
    cerr << "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>
int ZeigerListe<T>::find( T* p )
{
  for( first(); !isLast(); next() )
  {
    if( retrieve() == p )
      return getPos();
  }
 return -1;
}

template <class T>
T* ZeigerListe<T>::remove()
{
  Node<T> *N=NULL;
  T* R=NULL;
  if (isEmpty());  // nichts tun
  // cerr << "\nListe doch schon leer!";
  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>
T* ZeigerListe<T>::remove( T* p )
{
  int pos = find( p );
  
  if( pos == -1 )
    return NULL;
 
  setPos( pos );
  return remove();
}

template <class T>
void ZeigerListe<T>::removeWithElementDelete()
{
  Node<T> *N;
  if (isEmpty());  // nichts tun
  // cerr << "\nListe doch schon leer!";
  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>
int ZeigerListe<T>::getSize( void )
{
  int ret;
  int p = getPos();
  last();
  ret = getPos();
  setPos( p );
  return ret; 
}


#endif // _LIST_H

