---

TPtrListT.hh

#ifndef _T_PTR_LIST_T_HH
#define _T_PTR_LIST_T_HH

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

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

typedef struct TListEntry TListEntry_t;


// Holder for an entry in the list.
struct TListEntry
{
  // Previous entry.
  TListEntry_t *prev;
  
  // Next entry.
  TListEntry_t *next;
  
  // Pointer to object in this entry.
  void *data;
};


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

  void UpdateCurrent (int i);
  
  void Copy (TPtrListT<T> &list);
  
  
  /* First entry. */
  TListEntry_t *myFirst;
  
  /* Last entry. */
  TListEntry_t *myLast;
  
  /* Pointer of last entry used.
     Used to speed up index operator etc. */
  TListEntry_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 TPtrListT<T>::Append (T *a)
{
  TListEntry_t *entry;
  
  if (! (entry = (TListEntry_t *) malloc (sizeof (TListEntry_t))))
    throw TMemoryException ();
  
  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 TPtrListT<T>::Apply (void (*fn)(T *, void *), void *d)
{
  TListEntry_t *entry = myFirst;
  
  for (int i = 0; i < myNumElements; i++)
    {
      fn ((T *)entry->data, d);
      entry = entry->next;
    }
}


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


template <class T>
void TPtrListT<T>::ClearAndDestroy ()
{
  TListEntry_t *entry = myFirst, *tmp_entry;
  
  for (int i = 0; i < myNumElements; i++)
    {
      delete (T*)entry->data;
      tmp_entry = entry;
      entry = entry->next;
      free (tmp_entry);
    }
  
  Reset ();
}


template <class T>
void TPtrListT<T>::Insert (T *a, int i)
{
  TListEntry_t *entry, *prev;
  
  /* 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
  
  if (! (entry = (TListEntry_t *) malloc (sizeof (TListEntry_t))))
    throw TMemoryException ();
  
  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* TPtrListT<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 ();
  
  TListEntry_t *entry;
  T *data;
  
  /* Remove first entry? */
  if (! i)
    {
      entry = myFirst;
      data = (T *)myFirst->data;
      myFirst = myFirst->next;
      myCurrentPtr = myFirst;
      myCurrentNum = 0;
    }
  else
    {
      UpdateCurrent (i);
      entry = myCurrentPtr;
      data = (T *)myCurrentPtr->data;
      myCurrentPtr->prev->next = myCurrentPtr->next;
      myCurrentPtr->next->prev = myCurrentPtr->prev;
      myCurrentPtr = myCurrentPtr->next;
      /* myCurrentNum stays the same! */
    }
  
  free (entry);
  myNumElements--;
  
  return data;
}


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


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


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


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


template <class T>
void TPtrListT<T>::Copy (TPtrListT<T> &list)
{
  TListEntry_t *entry = NULL, *prev = NULL;
  TListEntry_t *entry_orig = list.myFirst;
  
  myFirst       = NULL;
  myNumElements = list.myNumElements;
  
  for (int i = 0; i < myNumElements; i++)
    {
      if (! (entry = (TListEntry_t *) malloc (sizeof (TListEntry_t))))
        throw TMemoryException ();
      
      /* 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 TPtrListT<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_PTR_LIST_T_HH

---