#ifndef _SortList_h
#define _SortList_h

#include <stdlib.h> // NULL

# include <stdio.h> // perror()


// own includes
#include "list.h"


#ifndef FALSE
	#define FALSE 0
	#define TRUE  1
#endif


// prototyping

template<class T>
class Node;


// definition of class Comparable

template <class T>
class Comparable
{
 public:
  virtual int compare(T*) {return FALSE;};
};


// definition of class SortedList

template <class T>
class SortedList : public ZeigerListe<T>
{
  public:

#ifdef _DEBUG
   SortedList();
   virtual ~SortedList();
#endif //_DEBUG

   virtual T* insert( T* ); // Fuegt neues Element ein.
   virtual T* append( T* );
   virtual T* find( T* );

#ifdef _DEBUG
	 FILE *fherr;
#endif // _DEBUG

};


// Die Implementierung der Elementfunktionen von SortedList !!

#ifdef _DEBUG
template <class T>
SortedList<T>::SortedList()
{
 fherr=fopen("c:\\t\\sortlist.err", "wb");
 if (fherr==NULL)
 {
  perror("SortList::SortList ");
 }
}

template <class T>
SortedList<T>::~SortedList()
{
  if (fherr!=NULL)
   fclose(fherr);
}
#endif // _DEBUG


template <class T>
T* SortedList<T>::insert(T* newPointer)
{
 T* R;
 Node<T> *N;

 if( newPointer == NULL ) // als erstes Parametercheck
 {
  return NULL;
 }

 N = new Node<T>;

 if (N!=NULL) {  // konnte Speicher reserviert werden?

  first();
  if (!isEmpty())
   while (aktPtr!=endPtr) // solange ich nicht am Ende bin
   {
      if ( newPointer->compare( aktPtr->Zeiger )<0 )
         break;
      next();
   }
   //
   // jetzt muss auf alle Faelle vor der aktPos eingefuegt werden
   //
   N->Nachfolger=aktPtr;
   N->Vorgaenger=aktPtr->Vorgaenger;
   N->Zeiger = newPointer;

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


   R = newPointer;

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

  endPos++;
 }
 else
 {
  perror ("SortedList::insert()");
  exit(1);
  //return NULL;
 }
 return R;
}


template <class T>
T* SortedList<T>::append(T* newPointer)
{
   return insert( newPointer );
}


template <class T>
T* SortedList<T>::find(T* item)
{
 int i=0;
 Node<T> *node;

 if( item == NULL ) // als erstes Parametercheck
 {
  return NULL;
 }


 node=anfPtr;

#ifdef _DEBUG
 fprintf(fherr, "%s", item->get());
 fflush(fherr);
#endif // _DEBUG

 while (node->Nachfolger!=NULL)
 {
  if (item->compare(node->Zeiger)==0)
  {
   aktPtr=node;
   aktPos=i;
   return node->Zeiger;
  }
  i++;
  node=node->Nachfolger;
 }
 return NULL;
}


#endif // _SORTEDLIST_H

