/*! 
  -----------------------------------------------------------------------------
 
  module: Tools_List.hpp
 
  -----------------------------------------------------------------------------
 
  responsible:  TiloH
 
  special area: universal list for tools
   
  description:  a list class, a little bit like STL list

  version:      7.4.4 and higher 
  -----------------------------------------------------------------------------
 
                          Copyright (c) 2002-2005 SAP AG
 
  -----------------------------------------------------------------------------



    ========== licence begin  GPL
    Copyright (c) 2002-2005 SAP AG

    This program is free software; you can redistribute it and/or
    modify it under the terms of the GNU General Public License
    as published by the Free Software Foundation; either version 2
    of the License, or (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
    ========== licence end




*/

#if !defined(Tools_List_HPP)
#define Tools_List_HPP

//
//-----------------------------------------------------------------------------
// includes
//-----------------------------------------------------------------------------
//

#include <new.h>


//-----------------------------------------------------------------------------
// macros
//-----------------------------------------------------------------------------

#if defined(WIN32)
#define Tools_List_NEW new
#else
#if defined (HPUX)
#define Tools_List_NEW new(nothrow)
#else
#define Tools_List_NEW new(std::nothrow)
#endif
#endif


//-----------------------------------------------------------------------------
// forward declarations
//-----------------------------------------------------------------------------

template<class T> class Tools_ListNode;
template<class T> class Tools_ListIterator;
template<class T> class Tools_ListConstIterator;
template<class T> class Tools_ListReverseIterator;
template<class T> class Tools_ListConstReverseIterator;


/*
  -----------------------------------------------------------------------------
  Class:        Tools_List
  -----------------------------------------------------------------------------

  description:  List

  -----------------------------------------------------------------------------
 */
template<class T> class Tools_List
{
  public:
    /*--------------------------------------------------------------------------
    public function: constructor

    description:  constructor, creates an empty list, containing a hidden and
                  empty list node used for end of list handling (thus forcing
                  class T to have a default constructor)   

    arguments:    none

    return value: none
    --------------------------------------------------------------------------*/
    Tools_List();

    /*--------------------------------------------------------------------------
    public function: destructor

    description:  destructs a list by freeing all memory used by list nodes,
                  note that if class T is pointing to memory itself, that memory
                  must either be freed in the destructor of class T or before
                  the destructor of the list is called

    arguments:    none

    return value: none
    --------------------------------------------------------------------------*/
    ~Tools_List();

    /*--------------------------------------------------------------------------
    public function: push_front()

    description:  adds a copy of AnElement at the front of the list, using the
                  global operator new and the copy constructor of class T or the
                  default constructor+assignment operator of class T

    arguments:    AnElement   [in] reference to instance of class T

    return value: true, if a copy could be created and added
                  false, otherwise (out of memory situation)
    --------------------------------------------------------------------------*/
    bool push_front(const T & AnElement);

    /*--------------------------------------------------------------------------
    public function: push_back()

    description:  adds a copy of AnElement at the end of the list, using the
                  global operator new and the copy constructor of class T or the
                  default constructor+assignment operator of class T

    arguments:    AnElement   [in] reference to instance of class T

    return value: true, if a copy could be created and added
                  false, otherwise (out of memory situation)
    --------------------------------------------------------------------------*/
    bool push_back(const T & AnElement);

    /*--------------------------------------------------------------------------
    public function: insert()

    description:  inserts a copy of AnElement "in front" of the element, the
                  iterator Position is pointing to. Hereby the meaning of
                  "in front" is determined by the used iterator type, so for a
                  reverse_iterator it means actually behind. insert() is using
                  the global operator new and the copy constructor of class T or
                  the default constructor+assignment operator of class T. 

    arguments:    Position    [in] iterator pointing to a member of the list 
                  AnElement   [in] reference to instance of class T

    return value: true, if a copy could be created and inserted
                  false, otherwise (out of memory situation)
    --------------------------------------------------------------------------*/
    bool insert(Tools_ListIterator<T> Position, const T & AnElement);
    bool insert(Tools_ListReverseIterator<T> Position, const T & AnElement);

    Tools_ListIterator<T>        erase(Tools_ListIterator<T> PosToErase);
    Tools_ListReverseIterator<T> erase(Tools_ListReverseIterator<T> PosToErase);
    Tools_ListIterator<T>        erase(Tools_ListIterator<T> StartPosToErase, Tools_ListIterator<T> AfterEndPosToErase);

    void pop_front();
    void pop_back();
    void clear();

    bool empty() const;

    typedef Tools_ListIterator<T>             iterator;
    typedef Tools_ListConstIterator<T>        const_iterator;
    typedef Tools_ListReverseIterator<T>      reverse_iterator;
    typedef Tools_ListConstReverseIterator<T> const_reverse_iterator;
    typedef unsigned long                     size_type;

    const T& front() const;
    const T& back() const;

    iterator               begin();
    const_iterator         begin() const;

    iterator               end();
    const_iterator         end() const;

    reverse_iterator       rbegin();
    const_reverse_iterator rbegin() const;

    reverse_iterator       rend();
    const_reverse_iterator rend() const;

    size_type size() const;

  private:
    Tools_ListNode<T> FixAnchor;
};

// -----------------------------------------------------------------------------
// implementation 
// -----------------------------------------------------------------------------

template<class T> class Tools_ListNode
{
  public:
    Tools_ListNode();
    Tools_ListNode(const T &c);
 
  private:
    Tools_ListNode<T> * prev;
    T                   info;
    Tools_ListNode<T> * next;

    friend class Tools_List<T>;
    friend class Tools_ListIterator<T>;
    friend class Tools_ListConstIterator<T>;
    friend class Tools_ListReverseIterator<T>;
    friend class Tools_ListConstReverseIterator<T>;
};

template<class T> class Tools_ListIterator
{
  public:
    Tools_ListIterator();
    Tools_ListIterator(Tools_ListNode<T> *o);

    Tools_ListIterator<T> & operator ++ ();
    Tools_ListIterator<T>   operator ++ (int);
    Tools_ListIterator<T> & operator -- ();
    Tools_ListIterator<T>   operator -- (int);
    int operator==(const Tools_ListIterator<T> &o) const;
    int operator!=(const Tools_ListIterator<T> &o) const;
    T & operator * ();

    Tools_ListIterator<T> & operator=(const Tools_ListReverseIterator<T> &);

    friend class Tools_List<T>;
    friend class Tools_ListConstIterator<T>;
    friend class Tools_ListReverseIterator<T>;

  private:
    Tools_ListNode<T> * NodePointer;
};

template<class T> class Tools_ListConstIterator
{
  public:
    Tools_ListConstIterator();
    Tools_ListConstIterator(const Tools_ListNode<T> *o);
    Tools_ListConstIterator(const Tools_ListIterator<T> &li);

    Tools_ListConstIterator<T> & operator ++ ();
    Tools_ListConstIterator<T>   operator ++ (int);
    Tools_ListConstIterator<T> & operator -- ();
    Tools_ListConstIterator<T>   operator -- (int);
    int operator==(const Tools_ListConstIterator<T> &o) const;
    int operator!=(const Tools_ListConstIterator<T> &o) const;
    const T & operator * () const;

    Tools_ListConstIterator<T> & operator=(const Tools_ListConstReverseIterator<T> &);

    friend class Tools_List<T>;
    //friend class Tools_ListReverseIterator<T>;

  private:
    const Tools_ListNode<T> * NodePointer;
};

template<class T> class Tools_ListReverseIterator
{
  public:
    Tools_ListReverseIterator();
    Tools_ListReverseIterator(Tools_ListNode<T> *);

    Tools_ListReverseIterator<T> & operator ++ ();
    Tools_ListReverseIterator<T>   operator ++ (int);
    Tools_ListReverseIterator<T> & operator -- ();
    Tools_ListReverseIterator<T>   operator -- (int);
    int operator==(const Tools_ListReverseIterator<T> &o) const;
    int operator!=(const Tools_ListReverseIterator<T> &o) const;
    T & operator * ();

    Tools_ListReverseIterator<T> & operator=(const Tools_ListIterator<T> &);

    friend class Tools_List<T>;
    friend class Tools_ListIterator<T>;

  private:
    Tools_ListNode<T> * NodePointer;
};

template<class T> class Tools_ListConstReverseIterator
{
  public:
    Tools_ListConstReverseIterator();
    Tools_ListConstReverseIterator(const Tools_ListNode<T> *);

    Tools_ListConstReverseIterator<T> & operator ++ ();
    Tools_ListConstReverseIterator<T>   operator ++ (int);
    Tools_ListConstReverseIterator<T> & operator -- ();
    Tools_ListConstReverseIterator<T>   operator -- (int);
    int operator==(const Tools_ListConstReverseIterator<T> &o) const;
    int operator!=(const Tools_ListConstReverseIterator<T> &o) const;
    const T & operator * () const;

    Tools_ListConstReverseIterator<T> & operator=(const Tools_ListIterator<T> &);

    friend class Tools_List<T>;

  private:
    const Tools_ListNode<T> * NodePointer;
};


// -----------------------------------------------------------------------------
// public constructor Tools_List<T>::Tools_List
// -----------------------------------------------------------------------------

template<class T> inline Tools_List<T>::Tools_List()
{
    FixAnchor.next=&FixAnchor;
    FixAnchor.prev=&FixAnchor;
}

// -----------------------------------------------------------------------------
// public destructor Tools_List<T>::~Tools_List
// -----------------------------------------------------------------------------
 
template<class T> inline Tools_List<T>::~Tools_List()
{
    Tools_ListNode<T> *h;

    while(FixAnchor.next!=(&FixAnchor)) //while there is another element as FixAnchor
    {
        h=FixAnchor.next;               //get a pointer to the first such element
        FixAnchor.next=h->next;         //take it out of the list

        delete h;                       //and free the memory used by it
    }
}

// -----------------------------------------------------------------------------
// public member function Tools_List<T>::push_front
// -----------------------------------------------------------------------------

template<class T> inline bool Tools_List<T>::push_front(const T & AnElement)
{
    Tools_ListNode<T> *h=Tools_List_NEW Tools_ListNode<T>(AnElement);

    if(0!=h)
    {
        h->next=FixAnchor.next;
        h->prev=&FixAnchor;
        FixAnchor.next->prev=h;
        FixAnchor.next=h;
    }

    return (0!=h);
}

// -----------------------------------------------------------------------------
// public member function Tools_List<T>::push_back
// -----------------------------------------------------------------------------

template<class T> inline bool Tools_List<T>::push_back(const T & AnElement)
{
    Tools_ListNode<T> *h=Tools_List_NEW Tools_ListNode<T>(AnElement);

    if(0!=h)
    {
        h->next=&FixAnchor;
        h->prev=FixAnchor.prev;
        FixAnchor.prev->next=h;
        FixAnchor.prev=h;
    }

    return (0!=h);
}

// -----------------------------------------------------------------------------
// public member function Tools_List<T>::insert
// -----------------------------------------------------------------------------

template<class T> inline bool Tools_List<T>::insert(Tools_ListIterator<T> Position, const T & AnElement)
{
    Tools_ListNode<T> *h=Tools_List_NEW Tools_ListNode<T>(AnElement);

    if(0!=h)
    {
        h->next=Position.NodePointer;
        h->prev=Position.NodePointer->prev;
        Position.NodePointer->prev->next=h;
        Position.NodePointer->prev=h;
    }

    return (0!=h);
}

template<class T> inline bool Tools_List<T>::insert(Tools_ListReverseIterator<T> Position, const T & AnElement)
{
    Tools_ListNode<T> *h=Tools_List_NEW Tools_ListNode<T>(AnElement);

    if(0!=h)
    {
        h->next=Position.NodePointer->next;
        h->prev=Position.NodePointer;
        Position.NodePointer->next->prev=h;
        Position.NodePointer->next=h;
    }

    return (0!=h);
}

// -----------------------------------------------------------------------------
// public member function Tools_List<T>::erase(Tools_ListIterator<T> PosToErase);
// -----------------------------------------------------------------------------

template<class T> inline Tools_ListIterator<T> Tools_List<T>::erase(Tools_ListIterator<T> PosToErase)
{
    PosToErase.NodePointer->prev->next=PosToErase.NodePointer->next;
    PosToErase.NodePointer->next->prev=PosToErase.NodePointer->prev;

    Tools_ListIterator<T> rc(PosToErase.NodePointer->next);

    delete PosToErase.NodePointer;

    return rc;
}

// -----------------------------------------------------------------------------
// public member function Tools_List<T>::erase(Tools_ListReverseIterator<T> PosToErase);
// -----------------------------------------------------------------------------

template<class T> inline Tools_ListReverseIterator<T> Tools_List<T>::erase(Tools_ListReverseIterator<T> PosToErase)
{
    PosToErase.NodePointer->prev->next=PosToErase.NodePointer->next;
    PosToErase.NodePointer->next->prev=PosToErase.NodePointer->prev;

    Tools_ListReverseIterator<T> rc(PosToErase.NodePointer->prev);

    delete PosToErase.NodePointer;

    return rc;
}

// -----------------------------------------------------------------------------
// public member function Tools_List<T>::erase(Tools_ListReverseIterator<T> PosToErase);
// -----------------------------------------------------------------------------

template<class T> inline Tools_ListIterator<T> Tools_List<T>::erase(Tools_ListIterator<T> StartPosToErase, Tools_ListIterator<T> AfterEndPosToErase)
{
    while(StartPosToErase!=AfterEndPosToErase)
        StartPosToErase=erase(StartPosToErase);

    return AfterEndPosToErase;
}

// -----------------------------------------------------------------------------
// public member function Tools_List<T>::pop_front();
// -----------------------------------------------------------------------------

template<class T> inline void Tools_List<T>::pop_front()
{
    if(!empty())
        erase(begin());
}

// -----------------------------------------------------------------------------
// public member function Tools_List<T>::pop_back();
// -----------------------------------------------------------------------------

template<class T> inline void Tools_List<T>::pop_back()
{
    if(!empty())
        erase(rbegin());
}

// -----------------------------------------------------------------------------
// public member function Tools_List<T>::clear();
// -----------------------------------------------------------------------------

template<class T> inline void Tools_List<T>::clear()
{
    Tools_ListNode<T> *h;

    while(FixAnchor.next!=(&FixAnchor)) //while there is another element as FixAnchor
    {
        h=FixAnchor.next;               //get a pointer to the first such element
        FixAnchor.next=h->next;         //take it out of the list

        delete h;                       //and free the memory used by it
    }

    FixAnchor.prev=(&FixAnchor);
}

template<class T> inline bool Tools_List<T>::empty() const
{
    return (FixAnchor.next==(&FixAnchor));
}

template<class T> inline const T& Tools_List<T>::front() const
{
    return (FixAnchor.next->info);
}

template<class T> inline const T& Tools_List<T>::back() const
{
    return (FixAnchor.prev->info);
}

template<class T> inline typename Tools_List<T>::iterator Tools_List<T>::begin()
{
    return Tools_ListIterator<T>(FixAnchor.next);
}

template<class T> inline typename Tools_List<T>::const_iterator Tools_List<T>::begin() const
{
    return Tools_ListConstIterator<T>(FixAnchor.next);
}

template<class T> inline typename Tools_List<T>::iterator Tools_List<T>::end()
{
    return Tools_ListIterator<T>(&FixAnchor);
}

template<class T> inline typename Tools_List<T>::const_iterator Tools_List<T>::end() const
{
    return Tools_ListConstIterator<T>(&FixAnchor);
}

template<class T> inline typename Tools_List<T>::reverse_iterator Tools_List<T>::rbegin()
{
    return Tools_ListReverseIterator<T>(FixAnchor.prev);
}

template<class T> inline typename Tools_List<T>::const_reverse_iterator Tools_List<T>::rbegin() const
{
    return Tools_ListConstReverseIterator<T>(FixAnchor.prev);
}

template<class T> inline typename Tools_List<T>::reverse_iterator Tools_List<T>::rend()
{
    return Tools_ListReverseIterator<T>(&FixAnchor);
}

template<class T> inline typename Tools_List<T>::const_reverse_iterator Tools_List<T>::rend() const
{
    return Tools_ListConstReverseIterator<T>(&FixAnchor);
}

template<class T> inline typename Tools_List<T>::size_type Tools_List<T>::size() const
{
    size_type                     rc=0;
    typename Tools_List<T>::const_iterator h=begin();

    for(; h!=end(); ++h)
        ++rc;

    return rc;
}


template<class T> inline Tools_ListNode<T>::Tools_ListNode()
{
}

#if defined (SUN)
template<class T> inline Tools_ListNode<T>::Tools_ListNode(const T &c)
{
    if(0!=this) //looks funny, but solves the problem that on solaris during a 'new(std::nothrow) X' 
        info=c; //the constructor X::X() is even called, if the new(std::nothrow) could not allocate
}               //the memory and returned a 0.
#else
template<class T> inline Tools_ListNode<T>::Tools_ListNode(const T &c)
:info(c)
{
}
#endif


template<class T> inline Tools_ListIterator<T>::Tools_ListIterator()
:NodePointer(0)
{
}

template<class T> inline Tools_ListIterator<T>::Tools_ListIterator(Tools_ListNode<T> *o)
:NodePointer(o)
{
}

template<class T> inline Tools_ListIterator<T> & Tools_ListIterator<T>::operator ++ ()
{
    NodePointer=NodePointer->next;

    return (*this);
}

template<class T> inline Tools_ListIterator<T> Tools_ListIterator<T>::operator ++ (int)
{
    Tools_ListIterator<T> TempIterator(NodePointer);
    NodePointer=NodePointer->next;

    return TempIterator;
}

template<class T> inline Tools_ListIterator<T> & Tools_ListIterator<T>::operator -- ()
{
    NodePointer=NodePointer->prev;

    return (*this);
}

template<class T> inline Tools_ListIterator<T> Tools_ListIterator<T>::operator -- (int)
{
    Tools_ListIterator<T> TempIterator(NodePointer);
    NodePointer=NodePointer->prev;

    return TempIterator;
}

template<class T> inline int Tools_ListIterator<T>::operator==(const Tools_ListIterator<T> &o) const
{
    return (NodePointer==o.NodePointer);
}

template<class T> inline int Tools_ListIterator<T>::operator!=(const Tools_ListIterator<T> &o) const
{
    return (NodePointer!=o.NodePointer);
}

template<class T> inline T & Tools_ListIterator<T>::operator * ()
{
    return NodePointer->info;
}

template<class T> inline Tools_ListIterator<T> & Tools_ListIterator<T>::operator=(const Tools_ListReverseIterator<T> &ri)
{
    NodePointer=ri.NodePointer;

    return (*this);
}


template<class T> inline Tools_ListConstIterator<T>::Tools_ListConstIterator()
:NodePointer(0)
{
}

template<class T> inline Tools_ListConstIterator<T>::Tools_ListConstIterator(const Tools_ListNode<T> *o)
:NodePointer(o)
{
}

template<class T> inline Tools_ListConstIterator<T>::Tools_ListConstIterator(const Tools_ListIterator<T>& li)
:NodePointer(li.NodePointer)
{
}

template<class T> inline Tools_ListConstIterator<T> & Tools_ListConstIterator<T>::operator ++ ()
{
    NodePointer=NodePointer->next;

    return (*this);
}

template<class T> inline Tools_ListConstIterator<T> Tools_ListConstIterator<T>::operator ++ (int)
{
    Tools_ListConstIterator<T> TempIterator(NodePointer);
    NodePointer=NodePointer->next;

    return TempIterator;
}

template<class T> inline Tools_ListConstIterator<T> & Tools_ListConstIterator<T>::operator -- ()
{
    NodePointer=NodePointer->prev;

    return (*this);
}

template<class T> inline Tools_ListConstIterator<T> Tools_ListConstIterator<T>::operator -- (int)
{
    Tools_ListConstIterator<T> TempIterator(NodePointer);
    NodePointer=NodePointer->prev;

    return TempIterator;
}

template<class T> inline int Tools_ListConstIterator<T>::operator==(const Tools_ListConstIterator<T> &o) const
{
    return (NodePointer==o.NodePointer);
}

template<class T> inline int Tools_ListConstIterator<T>::operator!=(const Tools_ListConstIterator<T> &o) const
{
    return (NodePointer!=o.NodePointer);
}

template<class T> inline const T & Tools_ListConstIterator<T>::operator * () const
{
    return NodePointer->info;
}

template<class T> inline Tools_ListConstIterator<T> & Tools_ListConstIterator<T>::operator=(const Tools_ListConstReverseIterator<T> &ri)
{
    NodePointer=ri.NodePointer;

    return (*this);
}


template<class T> inline Tools_ListReverseIterator<T>::Tools_ListReverseIterator()
:NodePointer(0)
{
}

template<class T> inline Tools_ListReverseIterator<T>::Tools_ListReverseIterator(Tools_ListNode<T> *o)
:NodePointer(o)
{
}

template<class T> inline Tools_ListReverseIterator<T> & Tools_ListReverseIterator<T>::operator ++ ()
{
    NodePointer=NodePointer->prev;

    return (*this);
}

template<class T> inline Tools_ListReverseIterator<T> Tools_ListReverseIterator<T>::operator ++ (int)
{
    Tools_ListReverseIterator<T> TempIterator(NodePointer);
    NodePointer=NodePointer->prev;

    return TempIterator;
}

template<class T> inline Tools_ListReverseIterator<T> & Tools_ListReverseIterator<T>::operator -- ()
{
    NodePointer=NodePointer->next;

    return (*this);
}

template<class T> inline Tools_ListReverseIterator<T> Tools_ListReverseIterator<T>::operator -- (int)
{
    Tools_ListReverseIterator<T> TempIterator(NodePointer);
    NodePointer=NodePointer->next;

    return TempIterator;
}

template<class T> inline int Tools_ListReverseIterator<T>::operator==(const Tools_ListReverseIterator<T> &o) const
{
    return (NodePointer==o.NodePointer);
}

template<class T> inline int Tools_ListReverseIterator<T>::operator!=(const Tools_ListReverseIterator<T> &o) const
{
    return (NodePointer!=o.NodePointer);
}

template<class T> inline T & Tools_ListReverseIterator<T>::operator * ()
{
    return NodePointer->info;
}

template<class T> inline Tools_ListReverseIterator<T> & Tools_ListReverseIterator<T>::operator=(const Tools_ListIterator<T> &i)
{
    NodePointer=i.NodePointer;

    return (*this);
}


template<class T> inline Tools_ListConstReverseIterator<T>::Tools_ListConstReverseIterator()
:NodePointer(0)
{
}

template<class T> inline Tools_ListConstReverseIterator<T>::Tools_ListConstReverseIterator(const Tools_ListNode<T> * Original)
:NodePointer(Original)
{
}

template<class T> inline Tools_ListConstReverseIterator<T> & Tools_ListConstReverseIterator<T>::operator ++ ()
{
    NodePointer=NodePointer->prev;

    return (*this);
}

template<class T> inline Tools_ListConstReverseIterator<T> Tools_ListConstReverseIterator<T>::operator ++ (int)
{
    Tools_ListConstReverseIterator<T> TempIterator(NodePointer);
    NodePointer=NodePointer->prev;

    return TempIterator;
}

template<class T> inline Tools_ListConstReverseIterator<T> & Tools_ListConstReverseIterator<T>::operator -- ()
{
    NodePointer=NodePointer->next;

    return (*this);
}

template<class T> inline Tools_ListConstReverseIterator<T> Tools_ListConstReverseIterator<T>::operator -- (int)
{
    Tools_ListConstReverseIterator<T> TempIterator(NodePointer);
    NodePointer=NodePointer->next;

    return TempIterator;
}

template<class T> inline int Tools_ListConstReverseIterator<T>::operator==(const Tools_ListConstReverseIterator<T> &o) const
{
    return (NodePointer==o.NodePointer);
}

template<class T> inline int Tools_ListConstReverseIterator<T>::operator!=(const Tools_ListConstReverseIterator<T> &o) const
{
    return (NodePointer!=o.NodePointer);
}

template<class T> inline const T & Tools_ListConstReverseIterator<T>::operator * () const
{
    return NodePointer->info;
}

#endif
