---

TValListT.hh

#ifndef _T_VAL_LIST_T_HH
#define _T_VAL_LIST_T_HH

#include <stdlib.h>
#include "TBoundsException.hh"
#include "TMemoryException.hh"

#define T_ABS(x) (x < 0 ? -x: x)


// Holder for an entry in the list.

template <class T>
class TValListEntryT
{
public:
  
  TValListEntryT<T> *prev;
  
  TValListEntryT<T> *next;
  
  T data;
};


template <class T>
class TValListT
{
public:
  
  TValListT () { Reset (); }
  
  TValListT (TValListT<T> &list) { Copy (list); }
  
  ~TValListT () { Clear (); }
  
  void Append (T a);
  
  void Apply (void (*fn)(T *, void *), void *d);
  
  void Clear ();
  
  inline int Entries () const { return myNumElements; }
  
  inline T First () { return myFirst->data; }
  
  void Insert (T a, int i = 0);
  
  inline T Last () { return myLast->data; }
  
  T Remove (int i = 0);
  
  T RemoveLast ();
  
  void Sort (bool reverse = false);
  
  T& operator[](int i);
  
  TValListT<T>& operator=(const TValListT<T> &list);
  
  
private:
  
  inline void Reset ()
  {
    myFirst = NULL;
    myLast  = NULL;
    myCurrentPtr  = NULL;
    myCurrentNum  = 0;
    myNumElements = 0;
  }

  void UpdateCurrent (int i);
  
  void Copy (const TValListT<T> &list);
  
  
  /* First entry. */
  TValListEntryT<T> *myFirst;
  
  /* Last entry. */
  TValListEntryT<T> *myLast;
  
  /* Pointer of last entry used.
     Used to speed up index operator etc. */
  TValListEntryT<T> *myCurrentPtr;
  
  /* Number of last entry used.
     Used to speed up index operator etc. */
  int myCurrentNum;
  
  /* Number of elements in list. */
  int myNumElements;
};


template <class T>
void TValListT<T>::Append (T a)
{
  TValListEntryT<T> *entry;
  
  entry = new TValListEntryT<T>;
  entry->data = a;
  
  if (myNumElements)
    {
      myLast->next = entry;
      entry->prev = myLast;
      myLast = entry;
    }
  else
    {
      myFirst = entry;
      myLast = entry;
      myCurrentPtr = myFirst;
      myCurrentNum = 0;
    }
  
  myNumElements++;
}


template <class T>
void TValListT<T>::Apply (void (*fn)(T *, void *), void *d)
{
  TValListEntryT<T> *entry = myFirst;
  
  for (int i = 0; i < myNumElements; i++)
    {
      fn (&entry->data, d);
      entry = entry->next;
    }
}


template <class T>
void TValListT<T>::Clear ()
{
  TValListEntryT<T> *entry = myFirst, *tmp_entry;
  
  for (int i = 0; i < myNumElements; i++)
    {
      tmp_entry = entry;
      entry = entry->next;
      delete tmp_entry;
    }
  
  Reset ();
}


template <class T>
void TValListT<T>::Insert (T a, int i)
{
  TValListEntryT<T> *entry;
  
  /* Takes care of inserting to empty list or after last entry. */
  if (i == myNumElements)
    {
      Append (a);
      return;
    }
  
#ifdef TOOLS_BOUND_CHECK
  if (i >= myNumElements || i < 0)
    throw TBoundsException ();
#endif
  
  entry = new TValListEntryT<T>;
  entry->data = a;
  
  /* Insert to first entry? */
  if (! i)
    {
      myFirst->prev = entry;
      entry->next = myFirst;
      myFirst = entry;
      myCurrentPtr = myFirst;
      myCurrentNum = 0;
    }
  else
    {
      UpdateCurrent (i);
      entry->prev = myCurrentPtr->prev;
      entry->next = myCurrentPtr;
      myCurrentPtr->prev->next = entry;
      myCurrentPtr->prev = entry;
      myCurrentPtr = entry;
      /* myCurrentNum stays the same! */
    }
  
  myNumElements++;
}


template <class T>
T TValListT<T>::Remove (int i)
{
#ifdef TOOLS_BOUND_CHECK
  if (i >= myNumElements || i < 0)
    throw TBoundsException ();
#endif
  
  /* Removing last entry? */
  if (i == (myNumElements - 1))
    return RemoveLast ();
  
  TValListEntryT<T> *entry;
  T data;
  
  /* Remove first entry? */
  if (! i)
    {
      entry = myFirst;
      data = myFirst->data;
      myFirst = myFirst->next;
      myCurrentPtr = myFirst;
      myCurrentNum = 0;
    }
  else
    {
      UpdateCurrent (i);
      entry = myCurrentPtr;
      data = myCurrentPtr->data;
      myCurrentPtr->prev->next = myCurrentPtr->next;
      myCurrentPtr->next->prev = myCurrentPtr->prev;
      myCurrentPtr = myCurrentPtr->next;
      /* myCurrentNum stays the same! */
    }
  
  delete entry;
  myNumElements--;
  
  return data;
}


template <class T>
T TValListT<T>::RemoveLast ()
{
#ifdef TOOLS_BOUND_CHECK
  if (! myNumElements)
    throw TBoundsException ();
#endif
  
  TValListEntryT<T> *entry = myLast;
  T data = myLast->data;
  
  if (myNumElements == 1)
    Reset ();
  else
    {
      myLast = myLast->prev;
      myNumElements--;
      if (myCurrentNum >= myNumElements)
        {
          myCurrentPtr = myFirst;
          myCurrentNum = 0;
        }
    }
  
  delete entry;
  return data;
}


/* FIXME */
template <class T>
void TValListT<T>::Sort (bool reverse)
{
}


template <class T>
T& TValListT<T>::operator[](int i)
{
#ifdef TOOLS_BOUND_CHECK
  if (i >= myNumElements || i < 0)
    throw TBoundsException ();
#endif
  
  UpdateCurrent (i);
  
  return myCurrentPtr->data;
}


template <class T>
TValListT<T>& TValListT<T>::operator=(const TValListT<T> &list)
{
  /* Only copy if different objects. */
  if (&list != this)
    {
      Clear ();
      Copy (list);
    }
  
  return *this;
}


template <class T>
void TValListT<T>::Copy (const TValListT<T> &list)
{
  TValListEntryT<T> *entry = NULL, *prev = NULL;
  TValListEntryT<T> *entry_orig = list.myFirst;
  
  myFirst = NULL;
  myNumElements = list.myNumElements;
  
  for (int i = 0; i < myNumElements; i++)
    {
      entry = new TValListEntryT<T>;
      
      /* Hook previous entry to this one. */
      if (prev)
        prev->next = entry;
      
      entry->prev = prev;
      entry->data = entry_orig->data;
      prev = entry;
      
      entry_orig = entry_orig->next;
      
      /* Store pointer to first entry. */
      if (! i)
        myFirst = entry;
    }
  
  myCurrentPtr  = myFirst;
  myCurrentNum  = 0;
  myLast = entry;
}


template <class T>
void TValListT<T>::UpdateCurrent (int i)
{
  int l_dist = (myNumElements - 1) - i;
  int c_dist = T_ABS (myCurrentNum - i);
  
  /* First better then last? */
  if (i <= l_dist)
    {
      /* First better than current? */
      if (i < c_dist)
        {
          myCurrentPtr = myFirst;
          myCurrentNum = 0;
        }
    }
  else
    {
      /* Last better than current? */
      if (l_dist < c_dist)
        {
          myCurrentPtr = myLast;
          myCurrentNum = (myNumElements - 1);
        }
    }
  
  /* Scan forward? */
  if (myCurrentNum < i)
    {
      for (; myCurrentNum < i; myCurrentNum++)
        myCurrentPtr = myCurrentPtr->next;
    }
  
  /* Scan backwards */
  if (myCurrentNum > i)
    {
      for (; myCurrentNum > i; myCurrentNum--)
        myCurrentPtr = myCurrentPtr->prev;
    }
}

#endif // _T_VAL_LIST_T_HH

---