include/AD/contain/varqueue.h

   1 //////////////////////////////////////////////////////////////////////////////
   2 // NOTICE:
   3 //
   4 // ADLib, Prop and their related set of tools and documentation are in the
   5 // public domain.   The author(s) of this software reserve no copyrights on
   6 // the source code and any code generated using the tools.  You are encouraged
   7 // to use ADLib and Prop to develop software, in both academic and commercial
   8 // settings, and are free to incorporate any part of ADLib and Prop into
   9 // your programs.
  10 //
  11 // Although you are under no obligation to do so, we strongly recommend that
  12 // you give away all software developed using our tools.
  13 //
  14 // We also ask that credit be given to us when ADLib and/or Prop are used in
  15 // your programs, and that this notice be preserved intact in all the source
  16 // code.
  17 //
  18 // This software is still under development and we welcome any suggestions
  19 // and help from the users.
  20 //
  21 // Allen Leung
  22 // 1994
  23 //////////////////////////////////////////////////////////////////////////////
  24
  25 #ifndef variable_sized_queue_h
  26 #define variable_sized_queue_h
  27
  28 #include <AD/generic/generic.h>
  29
  30 template <class T>
  31    class VarQueue {
  32       T * elements;  // array of elements
  33       int limit;     // current limit
  34       int count;     // number of elements
  35       int front;     // index to the front of the queue
  36       int back;      // index to the back of the queue
  37       int growth;    // number of elements to expand each time
  38
  39       void grow();
  40
  41    public:
  42
  43       ////////////////////////////////////////////////////////////////////////
  44       //  Constructor and destructor
  45       ////////////////////////////////////////////////////////////////////////
  46       VarQueue(int size = 8, int growthRate = 32);
  47      ~VarQueue();
  48
  49       ////////////////////////////////////////////////////////////////////////
  50       //  Selectors
  51       ////////////////////////////////////////////////////////////////////////
  52       inline int      size    () const { return count; }
  53       inline int      capacity() const { return limit; }
  54       inline Bool     is_empty () const { return count == 0; }
  55       inline Bool     is_full  () const { return count == limit; }
  56       inline const T& head    () const { return elements[front]; }
  57       inline const T& tail    () const { return elements[back]; }
  58       inline       T& head    ()       { return elements[front]; }
  59       inline       T& tail    ()       { return elements[back]; }
  60
  61       ////////////////////////////////////////////////////////////////////////
  62       //  Mutators
  63       ////////////////////////////////////////////////////////////////////////
  64
  65       ////////////////////////////////////////////////////////////////////////
  66       //  Returns the i'th element from the queue.
  67       ////////////////////////////////////////////////////////////////////////
  68       inline T& operator [] (int i) const
  69          {  int index = front - i;
  70             if (index < 0) index += limit;
  71             return elements[index];
  72          }
  73
  74       ////////////////////////////////////////////////////////////////////////
  75       //  Empties the queue
  76       ////////////////////////////////////////////////////////////////////////
  77       inline void clear() { front = 0; back = 1; count = 0; }
  78
  79       ////////////////////////////////////////////////////////////////////////
  80       //  Insert an element to the head of the queue.
  81       ////////////////////////////////////////////////////////////////////////
  82       inline void insert_head (const T& e)
  83          {  if (is_full()) grow();
  84             if (++front >= limit) front = 0; elements[front] = e; count++;
  85          }
  86
  87       ////////////////////////////////////////////////////////////////////////
  88       //  Removes an element from the head of the queue
  89       ////////////////////////////////////////////////////////////////////////
  90       inline T& remove_head ()
  91          {  int index = front--; count--;
  92             if (front < 0) front = limit-1;
  93             return elements[index];
  94          }
  95
  96       ////////////////////////////////////////////////////////////////////////
  97       //  Insert an element to the tail of the queue
  98       ////////////////////////////////////////////////////////////////////////
  99       inline void insert_tail (const T& e)
 100          {  if (is_full()) grow();
 101             if (--back < 0) back = limit-1; elements[back] = e; count++;
 102          }
 103
 104       ////////////////////////////////////////////////////////////////////////
 105       //  Removes an element from the tail of the queue
 106       ////////////////////////////////////////////////////////////////////////
 107       inline T& remove_tail ()
 108          {  int index = back++; count--;
 109             if (back >= limit) back = 0;
 110             return elements[index];
 111          }
 112
 113       /////////////////////////////////////////////////////////////////
 114       //  Iterators
 115       /////////////////////////////////////////////////////////////////
 116       inline Ix last()     const { return Ix(count); }
 117       inline Ix first()    const { return Ix(count > 0 ? 1 : 0); }
 118       inline Ix prev(Ix i) const { return Ix((int)i - 1); }
 119       inline Ix next(Ix i) const { return Ix((int)i < count ? (int)i+1 : 0); }
 120       inline const T& operator () (Ix i) const { return (*this)[(int)i-1]; }
 121       inline       T& operator () (Ix i)       { return (*this)[(int)i-1]; }
 122    };
 123
 124 //////////////////////////////////////////////////////////////////////////////
 125 //  Constructor
 126 //////////////////////////////////////////////////////////////////////////////
 127 template <class T>
 128    VarQueue<T>::VarQueue(int size, int growthRate)
 129       : elements(new T [size]),
 130         limit(size), count(0), front(0), back(1), growth(growthRate) {}
 131
 132 //////////////////////////////////////////////////////////////////////////////
 133 //  Destructor
 134 //////////////////////////////////////////////////////////////////////////////
 135 template <class T>
 136    VarQueue<T>::~VarQueue() { delete [] elements; }
 137
 138 //////////////////////////////////////////////////////////////////////////////
 139 //  Expand a queue
 140 //////////////////////////////////////////////////////////////////////////////
 141 template <class T>
 142    void VarQueue<T>::grow()
 143    {  int new_limit = limit + growth + limit / 4;
 144       T * new_elements = new T [new_limit];
 145       for (int i = back, j = 0, n = count; n > 0; n--) {
 146          new_elements[j++] = elements[i];
 147          if (++i == limit) i = 0;
 148       }
 149       delete [] elements;
 150       elements = new_elements;
 151       front = count-1; back = 0; limit = new_limit;
 152    }
 153
 154 #endif