// Template for sorted list

// Author: U.Breymann / H.P.Weber

// Date: 05.05.05



#ifndef SORTEDLIST_H

#define SORTEDLIST_H



#include <list>

#include <algorithm>  // find



#include "compare.h"



template< class T >

class SortedList 

{

public:

   typedef std::list< T >::iterator Iterator;

   typedef std::list< T >::const_iterator ConstIterator;

   SortedList( const Compare< T >& cmp = Compare< T >() ) : comp( cmp ) { }

   virtual ~SortedList() { }

   

   bool empty() const { return myList.empty(); }

   int size()   const { return myList.size(); }

   

   // take first or last element

   void pop_front() { myList.pop_front(); }

   void pop_back()  { myList.pop_back(); }

   

   // read first or last element

   T& front()             { return myList.front(); }

   const T& front() const { return myList.front(); }

   T& back()              { return myList.back(); }

   const T& back() const  { return myList.back(); }

   

   Iterator begin()            { return myList.begin(); }

   ConstIterator begin() const { return myList.begin(); }

   Iterator end()              { return myList.end(); }

   ConstIterator end() const   { return myList.end(); }

   

   void erase( Iterator& pos ) { myList.erase( pos ); }

   

   // find element

   Iterator find( const T& value ) 

   {

      return std::find( myList.begin(), myList.end(), value );

   }

   

   // sorted insert

   Iterator insert( const T& value ) 

   {

      // find place to insert

      Iterator temp( begin() );

      while( temp != end() && comp( *temp, value ) ) ++temp;

      return myList.insert( temp, value );

   }

   

private:

   std::list< T > myList;

   Compare< T > comp;

};



#endif