/ray/src/lib/tl/linkedlist.h

Go to the documentation of this file.

/*
 * lib/tl/linkedlist.h 
 * 
 * Complete implementation of a doubly linked list. 
 * List elements must be derived from LinkedListBase. 
 * 
 * Copyright (c) 2001--2004 by Wolfgang Wieser ] wwieser (a) gmx <*> de [ 
 * 
 * This file may be distributed and/or modified under the terms of the 
 * GNU General Public License version 2 as published by the Free Software 
 * Foundation. (See COPYING.GPL for details.)
 * 
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
 * 
 */

#ifndef _TemplateLibrary_LinkedList_H_
#define _TemplateLibrary_LinkedList_H_ 1

#include <lib/sconfig.h>    /* MUST be first */


template<typename T> struct LinkedListBase
{
    T *prev,*next;
    
    enum _LLB_NoInit { LLB_NoInit };
    
    inline LinkedListBase()  {  prev=next=NULL;  }
    inline LinkedListBase(_LLB_NoInit)  { }
    inline ~LinkedListBase()  { }
};


// Ugly macro used so that we can read things more easily.
#define _LLB LinkedListBase<T>

template<typename T> class LinkedList
{
    private:
        T *lfirst,*llast;
        
        inline LinkedList &operator=(const LinkedList &l)
            {  lfirst=l.lfirst;  llast=l.llast;  return(*this);  }
        inline LinkedList(const LinkedList &l)
            {  lfirst=l.lfirst;  llast=l.llast;  }
    public:
        inline LinkedList()  {  lfirst=llast=NULL;  }
        inline ~LinkedList()  {  }
        
        inline T *first()  const  {  return(lfirst);  }
        inline T *last()   const  {  return(llast);   }
        
        inline bool IsEmpty()  const  {  return(!lfirst);  }
        
        inline T *next(T *p)  const  {  return(p->_LLB::next);  }
        inline T *prev(T *p)  const  {  return(p->_LLB::prev);  }
        inline const T *next(const T *p)  const  {  return(p->_LLB::next);  }
        inline const T *prev(const T *p)  const  {  return(p->_LLB::prev);  }
        
        inline void AssignList(const LinkedList<T> *l)
            {  lfirst=l->lfirst;  llast=l->llast;  }
        
        inline void SwapList(LinkedList<T> *l)
            {  T *tmp=lfirst;  lfirst=l->lfirst;  l->lfirst=tmp;
                  tmp=llast;   llast= l->llast;   l->llast= tmp;  }
        
        inline void insert(T *p)
        {
            if(!p)  return;
            p->_LLB::next=lfirst;
            p->_LLB::prev=NULL;
            //if(lfirst)  lfirst->_LLB::prev=p;
            //else  llast=p;
            (lfirst ? lfirst->_LLB::prev : llast)=p;
            lfirst=p;
        }
        
        inline void append(T *p)
        {
            if(!p)  return;
            p->_LLB::prev=llast;
            p->_LLB::next=NULL;
            //if(llast)  llast->_LLB::next=p;
            //else  lfirst=p;
            (llast ? llast->_LLB::next : lfirst)=p;
            llast=p;
        }
        
        inline T *replace(T *newp,T *oldp)
        {
            newp->_LLB::next=oldp->_LLB::next;
            newp->_LLB::prev=oldp->_LLB::prev;
            if(lfirst==oldp)  lfirst=newp;
            if(llast==oldp)   llast=newp;
            oldp->_LLB::prev=oldp->_LLB::next=NULL;
            return(oldp);
        }
        
        inline void QueueBefore(T *p,T *where)
        {
            if(!p)  return;
            if(where==lfirst)
            {  insert(p);  return;  }
            p->_LLB::prev=where->_LLB::prev;
            where->_LLB::prev->_LLB::next=p;
            where->_LLB::prev=p;
            p->_LLB::next=where;
        }
        inline void QueueAfter(T *p,T *where)
        {
            if(!p)  return;
            if(where==llast)
            {  append(p);  return;  }
            p->_LLB::next=where->_LLB::next;
            where->_LLB::next->_LLB::prev=p;
            where->_LLB::next=p;
            p->_LLB::prev=where;
        }
        
        void queue(T *p,T *where,int loc)
        {
            if(loc<0)  QueueBefore(p,where);
            if(loc>0)  QueueAfter(p,where);
        }
        
        inline T *dequeue(T *p)
        {
            if(!p)  return(p);
            if(p==lfirst)  lfirst=lfirst->_LLB::next;
            else  p->_LLB::prev->_LLB::next=p->_LLB::next;
            if(p==llast)  llast=llast->_LLB::prev;
            else  p->_LLB::next->_LLB::prev=p->_LLB::prev;
            p->_LLB::next=p->_LLB::prev=NULL;
            return(p);
        }
        
        inline T *PopFirst()
        {
            if(!lfirst)  return(lfirst);
            T *p=lfirst;
            lfirst=lfirst->_LLB::next;
            if(lfirst)  lfirst->_LLB::prev=NULL;
            else  llast=NULL;
            p->_LLB::next=NULL;
            return(p);
        }
        inline T *PopLast()
        {
            if(!llast)  return(llast);
            T *p=llast;
            llast=llast->_LLB::prev;
            if(llast)  llast->_LLB::next=NULL;
            else  lfirst=NULL;
            p->_LLB::prev=NULL;
            return(p);
        }
        
        inline const T *search(const T *p)  const
        {
            for(T *i=lfirst; i; i=i->_LLB::next)
            {  if(i==p)  return(p);  }
            return(NULL);
        }
        inline const T *SearchRev(const T *p)  const
        {
            for(T *i=llast; i; i=i->_LLB::prev)
            {  if(i==p)  return(p);  }
            return(NULL);
        }
        
        inline int count()  const
        {
            int cnt=0;
            for(T *i=lfirst; i; i=i->_LLB::next,cnt++);
            return(cnt);
        }
        
        inline void clear()
            {  while(!IsEmpty()) delete PopFirst();  }
        
        inline void AppendList(LinkedList<T> &b)
        {
            if(b.IsEmpty()) return;
            
            b.lfirst->prev=llast;
            //if(llast)  llast->_LLB::next=b.first();
            //else  lfirst=b.first();
            (llast ? llast->_LLB::next : lfirst)=b.lfirst;
            llast=b.llast;
            
            b.lfirst=NULL;  b.llast=NULL;
        }
        
        inline T *MiddleNode()  const
        {
            //if(IsEmpty())  return(NULL);   <-- not needed!
            T *a=lfirst;
            for(T *b=llast; a!=b; b=b->_LLB::prev)  if((a=a->next)==b)  break;
            return(a);
        }
        
        template<typename OP>void MergeLists(
            LinkedList<T> &a,LinkedList<T> &b,const OP &_OP)
        {
            for(;;)
            {
                T *af=a.lfirst;  if(!af)  {  AppendList(b);  break;  }
                T *bf=b.lfirst;  if(!bf)  {  AppendList(a);  break;  }
                if(_OP.le(*af,*bf))  append(a.PopFirst());
                else                 append(b.PopFirst());
            }
        }
        
        template<typename OP>void MergeSort(const OP &_OP)  // recursive
        {
            if(IsEmpty())  return;
            // Divide: Split list. [O(n) due to MiddleNode()]
            T *m=MiddleNode();
            LinkedList<T> a,b;
            a.lfirst=lfirst;  a.llast=m;      m->_LLB::next=NULL;  lfirst=NULL;
            b.lfirst=m;       b.llast=llast;  m->_LLB::prev=NULL;  llast=NULL;
            // Conquer: Recursion depth O(log(n)). 
            a.MergeSort(_OP); b.MergeSort(_OP);
            // Merge: O(n). 
            MergeLists(a,b,_OP);
        }
};

#undef _LLB

#endif /* _TemplateLibrary_LinkedList_H_ */

---