list.h

Go to the documentation of this file.

/* $Id: list.h,v 1.9.2.22 2019/05/28 11:13:02 garloff Exp $
 * 
 * Copyright 1996--98 Kurt Garloff <kurt@garloff.de>
 * This software is protected by the GNU LGPL
 */
 
/*
 * TODO: 
 * - Implementation of treedel();
 */
 
 
#ifndef TBCI_LIST_H
#define TBCI_LIST_H  
 
#include "tbci/basics.h"
#ifndef LIST_LANG_C
# include <iostream>
#else
# include <stdio.h>
#endif
 
#ifdef PRAGMA_I
# pragma interface "list.h"
#endif
 
#define NULTP (T*)0
 
#ifndef STD__
# define STD__ std::
#endif
        
#ifdef NAMESPACE_TBCI
NAMESPACE_TBCI
#endif

template <typename T>
class ListItem {
    private:
    public:
        T* data;
        ListItem* next;
        ListItem* prev;
    public:
        ListItem() { data = new T; }
        ~ListItem() { /* STD__ cerr << "\ndelete ListItem!\n";*/ delete data; }
} ;
 
 
// Declare some (or all?) members static (?)
// We can only handle one list of each type then, cant we (?)
 
template <typename T> class List;
/* Iterators */
template <typename T>
class ListIterator
{
    protected:
        ListItem<T> *curr;
        long currnr;
        unsigned long vers;
        const List<T> *lst;
        int dir;
    public:
        // ctors
        ListIterator (const List<T>& _list, T* dataptr = 0);
        ListIterator (const List<T>& _list, ListItem<T>* li = 0);
        ListIterator (const List<T>& _list, ListItem<T>* li, 
                      const long nr);
        ListIterator (const ListIterator<T>& li) :
                curr (li.curr), currnr (li.currnr), 
                vers (li.vers), lst (li.lst), dir(li.dir)  {}
        // assignment
        ListIterator<T>& operator = (const ListIterator<T>&);
        // get no
        long getnr ();
        // dereference
        T* operator * () const;
        operator bool () const;
        // (pre)increment/decrement
        ListIterator<T>& operator ++ ();
        ListIterator<T>& operator -- ();
        // comparison
        bool operator == (const ListIterator<T>& li) const;
        bool operator != (const ListIterator<T>& li) const;
        bool operator <  (const ListIterator<T>& li) const;
        bool operator >  (const ListIterator<T>& li) const;
        bool operator <= (const ListIterator<T>& li) const;
        bool operator >= (const ListIterator<T>& li) const;
        
} ;
 
template <typename T> 
ListIterator<T>::ListIterator (const List<T>& _list, T* dataptr/* = 0*/)
        : vers (_list.vers), lst (&_list), dir (1)
{
        if (dataptr)
                _list.setcurr (dataptr);
        curr = _list.getcurr ();
        currnr = _list.getcurrnr ();
}
 
template <typename T> 
ListIterator<T>::ListIterator (const List<T>& _list, ListItem<T>* li /*= 0*/)
        : vers (_list.vers), lst (&_list), dir (1)
{
        if (li)
                _list.setcurr (li->data);
        curr = _list.getcurr ();
        currnr = (long)_list.getcurrnr ();
}
 
template <typename T> 
inline ListIterator<T>::ListIterator (const List<T>& _list, ListItem<T>* li, 
                                      const long nr)
        : curr (li), currnr (nr), vers (_list.vers), lst (&_list), dir (1)
{}
 
template <typename T>
inline ListIterator<T>& ListIterator<T>::operator = (const ListIterator<T>& li)
{
        curr = li.curr; currnr = li.currnr;
        vers = li.vers; lst = li.lst;
        dir = 1;
        return *this;
}
 
template <typename T> 
inline long ListIterator<T>::getnr ()
{
        if (vers != lst->vers) {
                currnr = lst->getnr (curr->data);
                vers = lst->vers;
        }
        return currnr;
}
 
template <typename T>
inline T* ListIterator<T>::operator * () const
{
        return curr->data;
}
 
template <typename T>
inline ListIterator<T>::operator bool () const
{
        if (curr)
                return true;
        else
                return false;
}
 
 
template <typename T>
inline ListIterator<T>& ListIterator<T>::operator ++ ()
{
        if (curr)
                if (dir > 0) {
                        curr = curr->next; currnr++;
                } else {
                        curr = curr->prev; currnr--;
                }
        else
                if (dir > 0) {
                        if (currnr <= 0) {
                                curr = lst->root;
                                currnr = 1;
                        }
                } else {
                        if (currnr > 0 /*lst->count*/) {
                                curr = lst->last;
                                currnr = lst->count;
                        }
                }
        return (*this);
}
 
template <typename T>
inline ListIterator<T>& ListIterator<T>::operator -- ()
{
        if (curr)
                if (dir > 0) {
                        curr = curr->prev; currnr--;
                } else {
                        curr = curr->next; currnr++;
                }
        else
                if (dir > 0) {
                        if (currnr > 0 /*lst->count*/) {
                                curr = lst->last;
                                currnr = lst->count;
                        }
                } else {
                        if (currnr <= 0) {
                                curr = lst->root;
                                currnr = 1;
                        }
                }
        return (*this);
}
 
template <typename T>
inline bool ListIterator<T>::operator == (const ListIterator<T>& li) const
{ 
        if (lst == li.lst /*&& dir == li.dir*/ && currnr == li.currnr)
                return true;
        else 
                return false;
}
 
template <typename T>
inline bool ListIterator<T>::operator != (const ListIterator<T>& li) const
{ 
        return !(*this == li);
}
 
template <typename T>
inline bool ListIterator<T>::operator <  (const ListIterator<T>& li) const
{
        if (lst != li.lst /*|| dir != li.dir*/)
                abort ();
        return (dir * currnr < li.dir * li.currnr);
}
 
template <typename T>
inline bool ListIterator<T>::operator <= (const ListIterator<T>& li) const
{
        if (lst != li.lst /*|| dir != li.dir*/)
                abort ();
        return (dir * currnr <= li.dir * li.currnr);
}
        
template <typename T>
inline bool ListIterator<T>::operator >  (const ListIterator<T>& li) const
{
        return !(*this <= li);
}
 
template <typename T>
inline bool ListIterator<T>::operator >= (const ListIterator<T>& li) const
{
        return !(*this <  li);
}
 
 
template <typename T>
class ListRIterator : public ListIterator<T>
{
 protected:
        using ListIterator<T>::dir;
        using ListIterator<T>::curr;
        using ListIterator<T>::currnr;
        using ListIterator<T>::vers;
        using ListIterator<T>::lst;
    public:
        ListRIterator (const List<T>& _list, T* dataptr)
                : ListIterator<T> (_list, dataptr)  { dir = -1; }
        ListRIterator (const List<T>& _list, ListItem<T>* li)
                : ListIterator<T> (_list, li)  { dir = -1; }
        ListRIterator (const List<T>& _list, ListItem<T>* li, 
                       const unsigned long nr)
                : ListIterator<T> (_list, li, nr)  { dir = -1; }
        /* ListRIterator (const ListIterator<T>& li) 
                : ListIterator<T> (li)  { dir = -1; } */
        ListRIterator<T>& operator = (const ListIterator<T>&);
} ;
 
template <typename T>
inline ListRIterator<T>& ListRIterator<T>::operator = (const ListIterator<T>& li)
{
        curr = li.curr; currnr = li.currnr;
        vers = li.vers; lst = li.lst;
        dir = 1;
        return *this;
}

template <typename T>
class List {
    protected:
        mutable ListItem<T> *curr;
        unsigned long count; 
        mutable unsigned long currnr;
        unsigned long vers;
        
        void checklast ();
        ListItem<T> *app ();
        
    protected:
        ListItem<T> *root;
        ListItem<T> *last;
        ListItem<T> *detached;
        
    public:
        friend class ListIterator<T>;
        typedef ListIterator<T> iterator;
        friend class ListRIterator<T>;
        typedef ListRIterator<T> riterator;
 
        List () : curr(NULL), count(0), currnr(0), 
                vers(0), root(NULL), last(NULL), detached(NULL) {}
        List (const List<T>&); 
        List<T>& operator = (const List<T>&);
        List<T>& alias (const List<T>&);
        
        iterator begin () const;
        iterator end () const;
        riterator rbegin () const;
        riterator rend () const;
 
        T* append ();
        T* append (T*);
        void erase (T*);
        void deltree (T*); //Deletes List from item to end
        void deltree ();
        //void treedel (T*)
        //void treedel ();
        /* Never do call by value with List<xy> argument, ~List () would be called ! */
        ~List () { deltree (); }
        
        T* getfirst () const;
        T* getlast () const;
        T* getcurr () const;
        T* getnext () const;
        T* getprev () const;
        T* setfirst () const;
        T* setlast () const;
        T* setnext () const;
        T* setprev () const;
        T* inscurr ();
        T* inscurr (T*);
        T* delcurr ();
        T* detachcurr ();
        
        unsigned long getlength () const;
        unsigned long size () const;
        unsigned long getcurrnr () const;
        unsigned long getnr (const T*) const;
        unsigned long getnr () const;   
        T* getbynr (long) const;
        
        T* setcurrnr (const unsigned long) const;
        T* setcurr (const T* rec) const { setcurrnr (getnr (rec)); return getcurr (); }
        
        void dumpList () const;
} ;
 
// Implementation
 
template <typename T>
inline void List<T>::checklast () 
{
        while (last -> next != NULL) { 
                last = last -> next; count++; 
        }
} //paranoia
 
// copy the List of pointers and the data itsself
template <typename T>
List<T>::List (const List<T>& l)
{ 
        ListItem<T>* tmp = l.root; vers = l.vers;
        root = NULL; last = NULL; curr = NULL; detached = NULL; count = 0;
        while (tmp)  {
                curr = app();
                //curr->data = tmp->data;
                *(curr->data) = *(tmp->data);
                tmp = tmp->next;
        }
}
 
// assignment
template <typename T>
List<T>& List<T>::operator = (const List<T>& l) 
{
        deltree ();
        ListItem<T>* tmp = l.root;
        root = NULL; last = NULL; curr = NULL; detached = NULL;
        count = 0; vers++;
        while (tmp)  {
                curr = app();
                //curr->data = tmp->data;
                *(curr->data) = *(tmp->data);
                tmp = tmp->next;
        }
        return *this;
}
 
// aliasing
template <typename T>
List<T>& List<T>::alias (const List<T>& l)
{
        deltree ();
        ListItem<T>* tmp = l.root; vers = l.vers;
        root = NULL; last = NULL; curr = NULL; detached = NULL; count = 0;
        while (tmp)  {
                curr = app();
                curr->data = tmp->data;
                tmp = tmp->next;
        }
        return *this;
}
 
        
template <typename T>
ListItem<T>* List<T>::app ()
{  
        count++; currnr = count; vers++;
        if (!root) {
                curr = new ListItem<T>; 
                curr->prev = NULL; curr->next = NULL;
                root = curr; last = curr;
                return curr;
        } else {
                //checklast(); 
                curr = new ListItem<T>;
                curr->prev = last; curr->next = NULL;
                last->next = curr; last = curr; 
                return curr;
        }
}
 
 
template <typename T>
inline T* List<T>::append ()
{ 
        return app()->data; 
}
 
template <typename T>
inline T* List<T>::append (T* data)
{
        T *tmp = this->append ();
        *tmp = *data; return tmp;
}
 
 
template <typename T>
T* List<T>::inscurr ()
{
        if (!curr) return append(); //append and insert is equal for void Lists
        count++; vers++;
        if (!(curr->prev)) { //Insert at the beginning of the List
                curr = new ListItem<T>; curr->prev = NULL; curr->next = root;
                root->prev = curr; root = curr;
        } else {
                ListItem<T> *ins = new ListItem<T>;
                ins->next = curr; ins->prev = curr->prev;
                ins->prev->next = ins; curr->prev = ins;
                curr = ins;
        }
        return curr->data;
}       
 
template <typename T>
inline T* List<T>::inscurr (T* elem)
{
        T* ptr = inscurr ();
        *ptr = *elem;
        return ptr;
}
 
template <typename T>
T* List<T>::delcurr ()
{
        if (curr == NULL) return NULTP;
        count--; vers++;
        if (curr->next == NULL) { // curr == last
                currnr = count;
                if (curr->prev == NULL) { // curr == root
                        delete curr;
                        root=NULL; curr=NULL; last=NULL; /*count=0;*/
                        return NULTP;
                } else {
                        last = curr->prev;
                        curr->prev->next = NULL;
                        delete curr;
                        curr = NULL;
                        return NULTP;
                }
        } else {
                if (curr->prev == NULL) { // curr == root
                        curr = curr->next;
                        delete curr->prev;
                        curr->prev = NULL;
                        root = curr;
                } else {
                        curr->prev->next = curr->next;
                        curr->next->prev = curr->prev;
                        ListItem<T> *del = curr;
                        curr = curr->next;
                        delete del;
                }
        }
        return curr->data;
}
 
template <typename T>
T* List<T>::detachcurr ()
{
        if (curr == NULL) return NULTP;
        count--; vers++;
        if (curr->next == NULL) { // curr == last
                currnr = count;
                if (curr->prev == NULL) { // curr == root
                        //if (detached)
                        //      detached->prev = curr;
                        curr->next = detached;
                        detached = curr; //detached->prev = NULL;
                        root=NULL; curr=NULL; last=NULL; /*count=0;*/
                        return NULTP;
                } else {
                        last = curr->prev;
                        curr->prev->next = NULL;
                        //if (detached)
                        //      detached->prev = curr;
                        curr->next = detached;
                        detached = curr; //detached->prev = NULL;
                        curr = NULL;
                        return NULTP;
                }
        } else {
                if (curr->prev == NULL) { // curr == root
                        curr = curr->next;
                        //if (detached)
                        //      detached->prev = curr->prev;
                        curr->prev->next = detached;
                        detached = curr->prev; //detached->prev = NULL;
                        curr->prev = NULL;
                        root = curr;
                } else {
                        curr->prev->next = curr->next;
                        curr->next->prev = curr->prev;
                        ListItem<T> *del = curr;
                        curr = curr->next;
                        //if (detached)
                        //      detached->prev = del;
                        del->next = detached; 
                        detached = del; //detached->prev = NULL;
                }
        }
        return curr->data;
}

template <typename T>
void List<T>::deltree (T* delroot) 
{  
        if (last == NULL) return;
        //checklast(); 
        vers++;
        //STD__ cerr << "\ndeltree  called!\n";
        while (!(last->data == delroot)) {
                count--; currnr = count;
                curr = last->prev; delete last; last = curr;
                if (curr == NULL) {  //check should not be necessary ...
#ifdef LIST_LANG_C
                        fprintf(stderr,"List::deltree: error: wrong pointer provided !\n");
#else
                        STD__ cerr << "List::deltree: error: wrong pointer provided !" << '\n';
#endif       
                        root = NULL; return;
                }
                else curr->next = NULL;
        }
        //delete last one, curr->data == delroot
        count --; currnr = count;
        curr = last->prev; delete last; last = curr;
        if (curr == NULL) root = NULL;
        else curr->next = NULL;
}
 
//template <typename T>
//void List<T>::treedel(T* rootdel)
 
template <typename T>
inline void List<T>::deltree () 
{ 
        if (root != NULL)
                deltree (root -> data);
        while (detached) {
                ListItem<T>* del = detached->next;
                delete detached;
                detached = del;
        }
}
 
//template <typename T>
//void List<T>::treedel()
 
template <typename T>
inline typename List<T>::iterator List<T>::begin () const
{ return ListIterator<T> (*this, root, (long)1); }
template <typename T>
inline typename List<T>::iterator List<T>::end () const
{ return ListIterator<T> (*this, 0, (long)count+1); }
template <typename T>
inline typename List<T>::riterator List<T>::rbegin () const
{ return ListRIterator<T> (*this, last, (long)count); }
template <typename T>
inline typename List<T>::riterator List<T>::rend () const
{ return ListRIterator<T> (*this, 0, (long)0); }
 
 
template <typename T>
inline T* List<T>::getfirst () const 
{ return (root?root->data:NULTP); }
 
template <typename T>
inline T* List<T>::getlast () const 
{ /*checklast();*/ return (last?last->data:NULTP); }
 
template <typename T>
inline T* List<T>::getcurr () const
{ return (curr?curr->data:NULTP); }
 
template <typename T>
inline T* List<T>::getnext () const 
{ if (!curr || !curr->next) return NULTP;
   else return curr->next->data; }
 
template <typename T>
inline T* List<T>::getprev () const 
{ if (!curr || !curr->prev) return NULTP;
   else return curr->prev->data; }
 
template <typename T>
inline T* List<T>::setfirst () const
{ curr = root; currnr = 1; return (curr?curr->data:NULTP); }
 
template <typename T>
inline T* List<T>::setlast () const
{ /*checklast();*/ curr = last; currnr = count; return (curr?curr->data:NULTP); }
 
template <typename T> 
inline T* List<T>::setnext () const 
{ if (!curr || !curr->next) return NULTP;
  else curr = curr->next; 
  currnr++; return curr->data; }
 
template <typename T>
inline T* List<T>::setprev () const 
{ if (!curr || !curr->prev) return NULTP;
  else curr = curr->prev;
  currnr--; return curr->data; }
 
template <typename T>
inline unsigned long List<T>::getlength () const 
{ return count; }
 
template <typename T>
inline unsigned long List<T>::size () const 
{ return count; }
 
template <typename T>
inline unsigned long List<T>::getcurrnr () const 
{ return currnr; }
 
template <typename T> 
void List<T>::erase (T* rec) //SLOW!
{
        if (root==NULL) 
                return;
        ListItem<T> *ptr = root;
        unsigned int ctr = 0;
        while (ptr) {
                ctr++;
                if (rec == ptr->data) break;
                ptr = ptr->next;
        }
        if (!ptr) 
                return;
        if (ptr->prev)
                ptr->prev = ptr->next;
        else
                root = ptr->next;
        if (last == ptr)
                last = ptr->prev;
        count--;
        if (currnr > ctr)
                currnr--;
        else if (currnr == ctr) {
                if (ptr->prev) {
                        curr = ptr->prev;
                        currnr--;
                } else 
                        curr = root;
        }
        delete ptr;
}
 
template <typename T> 
unsigned long List<T>::getnr (const T* rec) const //SLOW !
{  
        if (root==NULL) return 0;
        ListItem<T> *ptr = root;
        long cntr = 0;
        while (ptr) {
                cntr++;
                if (rec == ptr->data) return cntr;
                ptr = ptr->next;
        }
        return 0;
}
 
template <typename T>
inline unsigned long List<T>::getnr () const 
{ if (curr != NULL) return getnr(curr->data); else return 0; }
 
template <typename T>
T* List<T>::getbynr (long ctr) const
{
        if ((unsigned)ctr >= count || root == NULL)
                return NULTP;
        ListItem<T> *ptr = root;
        while (ptr && ctr--)
                ptr = ptr->next;
        if (ctr == -1)
                return ptr->data;
        else 
                return NULTP;
}
 
template <typename T>
T* List<T>::setcurrnr (const unsigned long nr) const
{
        curr = root; currnr = 0;
        while (curr && ++currnr < nr)
                curr = curr->next;
        if (curr) return curr->data;
        else return NULTP;
}
 
template <typename T>
void List<T>::dumpList () const
{
        ListItem<T>* tmp = root;
        printf ("Length:%li Curr:%li ", count, currnr);
        printf ("ROOT=%p CURR=%p LAST=%p\n", root, curr, last);
        while (tmp) {
                printf ("Elem:%p Prev:%p Next:%p Data:%p\n", tmp, tmp->prev, tmp->next, tmp->data);
                tmp = tmp->next;
        }
}
 
#ifdef __WATCOMC__
# define EQDOUBLE
#else
# define EQDOUBLE = double
#endif

 
template <typename T, typename S EQDOUBLE>
class nsList: public List<T>
{
    protected:
        using List<T>::root;
        using List<T>::last;
        using List<T>::curr;
        using List<T>::currnr;
        using List<T>::setlast;
        bool dir; //sort direction (true = descending)
        void quick (ListItem<T>*, ListItem<T>*);
    public:
        nsList () : List<T> () { dir = false; }
        void qsort (bool = false);
        T* sortin_r (T&, bool = false);
        long move_window (const S & val) const;
} ;
 
template <typename T, typename S>
void nsList<T,S>::quick (ListItem<T>* left, ListItem<T>* right)
{
        //if (left == right) return;
        ListItem<T>* le = left; ListItem<T>* ri = right;
        // Prevent overflow -> double !
        S test = (S)(((double)le->data->getval()+(double)ri->data->getval())/2); 
        T* tmp; 
        /* Avoid overhead of getnr()
         ListItem<T>* ptr = le;
         int zlr = getnr(ptr->data);
         zlr = (int)(zlr+getnr(ri->data))/2-zlr;
         for (int i=0; i<zlr; i++) ptr = ptr->next;
         double test = ptr->data->getval();
         */
        /* Debug
         STD__ cout << "left: " << getnr(le->data) << " " << le->data->getval() 
         << ", right: " << getnr(ri->data) << " " << ri->data->getval()
         << ", test: " << test << "\n";
         */
        int lesri = 1; // 1: le<ri, 0: le=ri; -1: le>ri
        while (lesri >= 0) {
                while ((dir?le->data->getval()>test:le->data->getval()<test)) {
                        le = le->next;
                        if (lesri == 0) 
                                lesri = -1;
                        else if (le == ri) 
                                lesri = 0;
                }
                //STD__ cout << "le: " << getnr(le->data) << '\n';
                while ((dir? ri->data->getval() < test: ri->data->getval() > test)) {
                        ri = ri->prev;
                        if (lesri == 0) 
                                lesri = -1;
                        else if (le == ri) 
                                lesri = 0;
                }
                //STD__ cout << "ri: " << getnr(ri->data) << ", " << lesri << '\n';     
                if (lesri == 1) {
                        tmp = le->data; le->data = ri->data; ri->data = tmp;
                        le = le->next; if (le == ri) lesri = 0;
                        ri = ri->prev; 
                        if (lesri == 0) lesri = -1;
                        else if (le == ri) lesri = 0;
                }
                else if (lesri == 0) {
                        if (le != right) 
                                le = le->next;
                        // FIXME
                        lesri = -1;
                        if (ri != left) 
                                ri = ri->prev;
                }
                //STD__ cout << "le: " << getnr(le->data) << ", ri: " << getnr(ri->data) << ", " << lesri << '\n';
        }
        //STD__ cout << "left " << left << " right " << right << " le " << le << " ri " << ri << '\n';
        if (left != ri) 
                quick(left,ri);
        if (le != right) 
                quick(le,right);
}
           
template <typename T, typename S>
void nsList<T,S>::qsort (bool desc)
{
        dir = desc;
        if (root == NULL || root == last) 
                return;
        quick(root,last);
}
 
template <class T,class S>
T* nsList<T,S>::sortin_r (T& dat, bool frst)
{
        bool sortedin = false;
        ListItem<T> *ptr, *ptr2;
        ptr2 = (frst? root: last);
        bool comp = (dat.getval() < ptr2->data->getval()) ^ dir;
        
        if (frst) { 
                ptr2 = root; 
#ifdef LIST_LANG_C
                fprintf (stderr, "Not yet implemented !\n");
#else
                STD__ cerr << "Not yet implemented !\n";
#endif
        }
        
        else
        {
                // ptr2 points to current ListItem, ptr to inserted  
                ptr2 = last; 
                if (!comp) return ptr2->data;
                //CSTD__ memcpy (ptr2->data, &dat, sizeof(T));
                *(ptr2->data) = dat;
                ptr2 = ptr2->prev; // pre-last
                if (!ptr2) return last->data;
                ptr2->next = NULL; // make new last
                ptr = last; last = ptr2; 
                while (ptr2 && !sortedin) {
                        comp = (dat.getval() < ptr2->data->getval()) ^ dir;
                        //sort in
                        if (!comp) {
                                ptr->prev = ptr2; ptr->next = ptr2->next;
                                if (ptr2->next) { 
                                        ptr2->next->prev = ptr; ptr2->next = ptr; 
                                }
                                else 
                                        last = ptr;
                                sortedin = true;
                        }
                        ptr2 = ptr2->prev;
                }
                // sort in at beginning
                if (!sortedin) {
                        ptr->prev = NULL; ptr->next = root;
                        root->prev = ptr; root = ptr;
                }
                //ptr2 = ptr; ptr2nr = getnr(ptr);
                return (setlast ());
        }
}
 
 
/* Find where we are in between, rel. to curr. pos. afterwards: 
 * curr->data->getval() <= val <= curr->next->data->getval() 
 * (for an ascending list)
 * border cases: curr will always be valid, curr->next may not
 */
 
template <typename T, typename S>
long nsList<T, S>::move_window (const S & val) const
{
        long oldnr = currnr;
        if (!curr) {
                curr = root; currnr = 1;
                if (!curr)
                        abort ();
        }
        ListItem<T>* next = curr->next;
        if (!dir) {
                // ascending
                /* best case: we're already positioned */
                if ( (curr == root || curr->data->getval() <= val) 
                     && (!next || next->data->getval() >= val))
                        return (currnr - oldnr);
                /* no: we have to walk :-( */
                /* go forward */
                if (next)
                        while (next->next && next->data->getval() < val) {
                                next = next->next; currnr++;
                        }
                if (curr->next != next) {
                        curr = next->prev;
                        return (currnr - oldnr);
                }
                /* go back ... */
                while (curr->prev && curr->data->getval() > val) {
                        curr = curr->prev; currnr--;
                }
                //next = curr->next;
                return (currnr - oldnr);
        } else {
                // descending
                /* best case: we're already positioned */
                if ( (curr == root || curr->data->getval() >= val) 
                     && (!next || next->data->getval() <= val))
                        return (currnr - oldnr);
                /* no: we have to walk :-( */
                /* go forward */
                if (next)
                        while (next->next && next->data->getval() > val) {
                                next = next->next; currnr++;
                        }
                if (curr->next != next) {
                        curr = next->prev;
                        return (currnr - oldnr);
                }
                /* go back ... */
                while (curr->prev && curr->data->getval() < val) {
                        curr = curr->prev; currnr--;
                }
                //next = curr->next;
                return (currnr - oldnr);
        }
}
 
#ifdef NAMESPACE_TBCI
NAMESPACE_END
#endif
 
#endif /* TBCI_LIST_H */