/**
 * $Id: dllist.h,v 1.21 2002/10/22 14:01:08 plasmahh Exp $
 * $Revision: 1.21 $
 * $Author: plasmahh $
 * $Date: 2002/10/22 14:01:08 $
 */

#ifndef __DLLIST_H
#define __DLLIST_H

#ifndef __EXCEPTION_H
#include "exception.h"
#endif
/*
This file contains the classes dllist, dllnode and dlliterator to create a fully functional double linked list
*/ 
template <class T> class dllnode;
template <class T> class dlliterator;

/// self expfor now
enum sort_mode { none, up, down };

/**
 * @brief class for a double linked list
 *
 * This classes implements a basic data structure, often called
 * double linked list. It uses a dllnode for the single items, and 
 * a dlliterator should be used to access items. 
 * @todo Implement Iterator, and some different versions of dllist
 * which can add items in a sorted order...
 */
// **********
// ********** definition dllist class
// **********

template <class T>
class dllist/*{{{*/
{
    //friend class dllnode<T>;
    friend class dlliterator<T>;
private:
    /// pointer to the actual node in the list
    dllnode<T> * actual;
    /// Pointer to the first element in the list
    dllnode<T> * first;
    /// Pointer to the last element in the list
    dllnode<T> * last;
    /// Number of items that are currently in the list
    unsigned long items;
    /// sort mode the list is currently of...
    sort_mode	smode;
    // The following private functions are for adding in sorted list mode only...
    // they are very slow, so don't use sorted mode unless speed doesnt matter...
    void add_up ( dllnode< T >* nit);
    void add_down ( dllnode< T>* nit);
public:
    /// creates an emtpy dllist (sort mode is none per default)
    dllist( ):actual(NULL),first(NULL),last(NULL),items(0),smode(none){};
    /**
     * Creates a dllist with predefined sort mode
     * @param sort_mode sort mode that the list will be of
     */
    dllist( sort_mode sm ):actual(NULL),first(NULL),last(NULL),items(0),smode(sm){};

    /// creates a dllist of another dllist (copies data, same sort mode as the one to be copied !!!)
    dllist( const dllist & ol): actual(NULL),first(NULL),last(NULL),items(0),smode(ol.smode){ *this = ol; };
    /// virtual destructor, perhaps we are derived somehow...
    virtual ~dllist(){ clear(); };

    /**
     * @param None
     * @return actual number of elements in the list 
     */
    inline unsigned long 	size( void ) const { return items; }

    /**
     * @param None
     * @return if the list is empty or not
     */ 
    inline	 bool	empty( void ) const { return items == 0; }

    /**
     * The sort mode defines, how the values are added to the list
     * in descending, ascending oder no order. No order is the fastest
     * since the items will be added to the end 
     * @note when changing the sort mode on a list it will not be resorted
     * only new elements are sorted (therefore you can force a resort when
     * assigning lists
     */
    inline    void set_sort_mode ( sort_mode sm) { smode = sm; }

    /**
     * Adds an element to the list. If compiled with _SAFE_
     * defined, this will throw an exception if no memory can 
     * be allocated.
     * @param T nit is the element that should be added
     * @return None
     */
    void 	add ( const T & nit);

    /**
     * Deletes all Elements in the list
     * @param None
     * @return None
     */
    void 	clear( void );

    /**
     * Writes some basic info about the Data Structure
     * @param ostream o that the info will be written to
     * @return ostream that the info was written to
     */
    friend ostream & operator<< <T> ( ostream& o , const dllist<T> & v);

    /**
     * assignes one list to another. The target list will
     * be emptied and the new data will be copied
     * @note The Sort mode of the original list will be preserved, 
     * so you can resort a list when assigning
     * @param dllist<T> that will we copied
     * @return dllist<T> that the other list was copied to
     */
    dllist&	operator=(const dllist & ol);

    /**
     * This adds a list to another. Be carefull when using different sort
     * modes and/or assigning differentely !!
     */
    dllist&	operator+=(const dllist & ol);

    /**
     * One list is smaller, if the number of items is smaller
     */
    friend bool operator < <T> ( const dllist<T> & a, const dllist<T> & b) ;
    friend bool operator > <T> ( const dllist<T> & a, const dllist<T> & b) ;

    /**
     * accesses the actual element in the list
     * @param None
     * @return lists actual element
     */
    inline operator dllnode<T> & () const { return * actual; }
};/*}}}*/

//*********
//********* implementation dllist
//*********

template <class T>
bool operator < ( const dllist<T> & a, const dllist<T> & b)
{ 
    return (a.items < b.items ); 
}

template <class T>
bool operator > ( const dllist<T> & a, const dllist<T> & b) 
{ 
    return (a.items > b.items ); 
}

template <class T>
inline void dllist<T>::clear( void )
{
    dllnode<T> *ptr,*dptr;
    ptr = first;
    while(ptr)
    {
        dptr = ptr;
        ptr = ptr->next;
        delete dptr;
    }
    first=last=actual=NULL;
    items = 0;
}

template <class T>
inline dllist<T>& dllist<T>::operator+=( const dllist<T> & ol)
{
    if ( ol.first ) // list to be copied from is empty when first==NULL
    {
        dllnode <T> *ptr;
        for (ptr=ol.first; ptr != NULL; ptr = ptr->next)
        {  
            dllnode< T > *nn = new dllnode<T>(*ptr);
            #ifdef _SAFE_
            if ( !nn ) 
                throw new x_mem ("dllist::operator=", __LFF__);
            #endif
	    if ( smode == up )
	    {
	        add_up ( nn );
		continue;
	    }
	    if ( smode == down )
	    {
		add_down ( nn );
		continue;
	    }
            if ( last ) 
            {
                nn->next = NULL;
                nn->prev = last;
                nn->prev -> next = nn;
                last = nn;
            }
            else
            {
                last = first = actual = nn;
            }
            items++;
	}// of for
    }// of if
    return (*this);
}

template <class T>
inline dllist<T>& dllist<T>::operator=( const dllist<T> & ol)
{
    clear();  // actual list must be empty...
    if ( ol.first ) // list to be copied from is empty when first==NULL
    {
        dllnode <T> *ptr;
        for (ptr=ol.first; ptr != NULL; ptr = ptr->next)
        {  
            dllnode< T > *nn = new dllnode<T>(*ptr);
            #ifdef _SAFE_
            if ( !nn ) 
                throw new x_mem ("dllist::operator=", __LFF__);
            #endif
	    if ( smode == up )
	    {
	        add_up ( nn );
		continue;
	    }
	    if ( smode == down )
	    {
		add_down ( nn );
		continue;
	    }
            if ( last ) 
            {
                nn->next = NULL;
                nn->prev = last;
                nn->prev -> next = nn;
                last = nn;
            }
            else
            {
                last = first = actual = nn;
            }
            items++;
	}// of for
    }// of if
    return (*this);
}

template <class T>
ostream & operator << ( ostream &o, const dllist<T> &v )
{
    o << "dllist size :" << v.size() << endl;
    return o;
}


template <class T>
inline void dllist<T>::add_down ( dllnode<T> * nit )
{
    if ( last )
    {
	dllnode<T> * ptr;
	for ( ptr = first; ptr != NULL; ptr = ptr->next )
	{
	    if ( *nit > *ptr )
	    {
		nit->next = ptr;
		nit->prev = ptr->prev;
		if ( ptr->prev )
		{
		    ptr->prev->next = nit;
		}
		ptr->prev = nit;
		if ( ptr == first )
		{
		    first = nit;
		}
		break;
	    }
	}
	if ( ptr == NULL )
	{
	    nit->next = NULL;
	    nit->prev = last;
	    last->next  = nit;
	    last = nit;
	}
    }
    else
    {
        nit->prev = nit->next = NULL;
	last = first = actual = nit;
    }
    items++;
}

template <class T>
inline void dllist<T>::add_up ( dllnode<T> * nit )
{
    if ( last )
    {
	dllnode<T> * ptr;
	for ( ptr = first;ptr != NULL; ptr = ptr-> next )
        {
	    if ( *nit < *ptr )
	    {
                nit->next = ptr;
            	nit->prev = ptr->prev;
		if ( ptr-> prev)
	        {
            	    ptr -> prev -> next = nit;
	        }
		ptr -> prev = nit;
		if ( ptr == first )
	        {
		    first = nit;
	        }
		break;
	    }
    	}
	if ( ptr == NULL ) // if the last elemement has been reached, just append
	    {
	    nit->next = NULL;
	    nit->prev = last;
	    last-> next = nit;
	    last = nit;
	    }
    }
    else
    {
	nit->prev = nit->next = NULL;
        last = first = actual = nit;
    }
    items++;
}

template <class T>
inline void dllist<T>::add ( const T & nit)
{
    dllnode< T > *nn = new dllnode<T>(nit);
    #ifdef _SAFE_
    if ( !nn ) 
        throw new x_mem ("dllist::add", __LFF__);
    #endif
    if ( smode == up )
    {
	add_up ( nn );
	return;
    }
    if ( smode == down )
    {
	add_down( nn );
	return;
    }
    if ( last ) 
    {
	nn->next = NULL;
	nn->prev = last;
	nn->prev -> next = nn;
	last = nn;
    }
    else
    {
        last = first = actual = nn;
    }
    items++;
}

//***********
//*********** dllnode declaration
//***********

/**
 * @brief Node for double linked list
 *
 * These Nodes contain the actual elements fo the list
 * together with the control data
 */
template <class T>
class dllnode
{
    friend class dllist<T>;
    friend class dlliterator<T>;
private:
    /// Pointer to the next Node
    dllnode<T> * next;
    /// Pointer to the previous Node
    dllnode<T> * prev;
    /// The Item that is at this node
    T item;
    /// contructs a Node of the template element T
    dllnode (const T & _item ):next(NULL), prev(NULL), item(_item){}

public:
    /// accesses the current item
    inline operator       T&( )       { return item ; };
    /// accesses the current item via const reference
    inline operator const T&( ) const { return  item; };
    /// accesses the current item via point<F3>er reference
    inline operator const T*( ) const { return & item; };
    /// Returns the Next Element of this Node
    inline dllnode<T> *Next( void ) const { return next; }
    /// Returns Previous Element to this Node
    inline dllnode<T> *Prev( void ) const { return prev; }

friend ostream& operator<< <T> ( ostream & o, const dllnode<T> & v);
friend bool operator <  <T> ( const dllnode<T> & a, const dllnode<T> & b);
friend bool operator >  <T> ( const dllnode<T> & a, const dllnode<T> & b);
};

template <class T>
bool operator <  ( const dllnode<T> & a, const dllnode<T> & b)
{
return ( a.item < b.item );
}

template <class T>
bool operator >  ( const dllnode<T> & a, const dllnode<T> & b)
{
return ( a.item > b.item );
}

template <class T>
ostream& operator<< ( ostream & o, const dllnode<T> & v)
{
    o << v.item;
    return o;
}

//***********
//*********** dlliterator declaration
//***********

/**
 * @brief This is an iterator for the dllists. 
 *
 * You can iterate through the single elements of the list.
 * The best construct is a for loop :
 * @code
 * for (iterator.first(); iterator.valid(); iterator.next()) { }
 * @endcode
 * With this loop you can access every element in the list from 
 * first to last ( use last/prev for other direction )
 */
template <class T>
class dlliterator
{
private:
    /// reference to the list we iterate through
    dllist<T> &list;
public:
    /// constructs this iterator of the list
    dlliterator(dllist<T>& lis) : list(lis) { if (! list.empty() ) first();}

    /**
     * Sets the iterator to the first item
     * @param none
     * @return if the action was successfull and points to a valid item 
     */
    inline bool first ( void ) { return ( list.actual = list.first); }

    /**
     * Sets the iterator to the last element in the list
     * @param none
     * @return if the pointer was succesfully and is valid
     */
    inline bool last ( void ){ return ( list.actual = list.last); }

    /**
     * Sets the actual item to the next in the list
     * @param nonde
     * @return if succesfull and actual is valid
     * @note If _FAST_ is defined it will not be checked if actual is a valid element
     */
    inline bool next ( void ); 

    /**
     * Sets to the previous Node
     * @param Nonde
     * @return if it was successfull to set pointer and if it is valid
     * @note If _FAST_ is defined it will not be checked if actual is a valid element
     */
    inline bool prev ( void );

    /**
     * @param None
     * @return if the actual item pointer is on a valid position
     */
    inline bool valid ( void ){ return (list.actual); }

    /**
     * @param None
     * @return The actual Item 
     * @note If the actual pointer is not valid the behaviour may
     * be undefined or not as expected
     */
    inline T & item( void );
};

//*********
//********* dlliterator implementation
//*********

template <class T>
inline bool dlliterator<T>::prev ( void )
{
    #ifndef _FAST_
    if ( list.actual )
    #endif
        return ( list.actual = list.actual->prev );
    return false;
}

template <class T>
inline T & dlliterator<T>::item( void )
{
    #ifndef _FAST_
    if (list.actual)
    #endif
    return list.actual-> operator T& ();
    #ifdef _SAFE_
    else
//throw exception
#endif
/**
 * @bug BUG !!!!!
 * We can't return anything if the list is empty !!! throw an exception ???
 * or what ??
 */
cout << "WARNING AN EMPTY LIST WAS ACCESSED !! WARNING, BUG BUG BUG !!! " << endl;
return list.actual-> operator T& ();
}




template <class T>
inline bool dlliterator< T >::next ( void )
{ 
    #ifndef _FAST_
    if ( list.actual )
    #endif
        return ( list.actual = list.actual->next );
    return false;
}
#else
#warning Multiple inclusion of dllist.h, please check your headers
#endif 
/**
 *$Log: dllist.h,v $
 *Revision 1.21  2002/10/22 14:01:08  plasmahh
 *implementing binary tree
 *
 *Revision 1.20  2002/10/21 23:47:18  plasmahh
 *huch ?
 *
 *Revision 1.19  2002/10/16 23:07:21  plasmahh
 *fixed memory bugs in mstring
 *TODO : refine of exception structure
 *
 *Revision 1.18  2002/10/10 20:56:30  plasmahh
 *doc cleanuo
 *
 *Revision 1.16  2002/06/20 21:02:10  plasmahh
 *internal documentation changes
 *socket fixes !
 *
 *Revision 1.15  2002/06/11 14:17:05  plasmahh
 *Added operators.
 *Fixed sorting bug which destroyed origin list
 *
 *Revision 1.14  2002/06/11 09:36:03  plasmahh
 *dirty fixed converstion sequence warnings
 *
 *Revision 1.13  2002/06/10 22:55:04  plasmahh
 *partly fixed assignment operators, more to be done
 *
 *Revision 1.12  2002/06/10 22:10:54  plasmahh
 * added operators and fixed some sorting things
 *
 *Revision 1.11  2002/06/10 19:56:54  plasmahh
 *implemented missing operators
 *
 *Revision 1.10  2002/06/10 19:44:53  plasmahh
 *some slight compiler defined changes
 *
 *Revision 1.9  2002/06/10 10:30:33  plasmahh
 *Added += operator
 *
 *Revision 1.8  2002/06/09 21:23:21  plasmahh
 *changed a few things that might be bugs
 *
 *Revision 1.7  2002/05/23 22:28:57  plasmahh
 *Fixed operator= bug which was never copying the real list...
 *
 *Revision 1.6  2002/05/23 19:48:08  plasmahh
 *removed some compiler warnings.
 *fixed one or two bugs.
 *refined include structure, for faster compiling
 *hm, what else ? don't know, I hope this works all ;)
 *
 *Revision 1.5  2002/05/14 16:31:13  plasmahh
 *Removed some compiler warnings
 *Added more code,  hopefully fast ;)
 *
 *Revision 1.4  2002/05/05 20:24:36  plasmahh
 *added doygen configuration file
 *made dllist work
 *added dlliterator to dllist.h
 *made some test progams cooler ;)
 *added some exceptions...
 *anything else to do ?? *G*
 *
 *Revision 1.3  2002/04/29 18:20:23  plasmahh
 *some small changes in definitions
 *
 *Revision 1.2  2002/04/29 16:09:15  plasmahh
 *first version of double link list, that compiles. Needs to be tested
 *added #define _DEBUG_ to defines, for indicating debug compilation
 *
 *Revision 1.1  2002/04/22 19:04:48  plasmahh
 *Added some parts of a double linked list class
 *
 */