include/AD/contain/fixqueue.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 fixed_sized_queue_h
  26 #define fixed_sized_queue_h
  27
  28 /////////////////////////////////////////////////////////////////////////
  29 // Class FixQueue<T,Capacity> is a very simple double ended
  30 // queue parameterized by the element type and its maximum capacity.
  31 // For simplicity, no bounds checking is performed.
  32 /////////////////////////////////////////////////////////////////////////
  33
  34 #include <AD/generic/generic.h>   // Generic definitions
  35
  36 template<class T, int Capacity>
  37    class FixQueue {
  38
  39       // Our queue is actually implemented as an array with
  40       // indices to the front and the back of the queue.
  41       // Indices are ``wrapped around'' when they reach the
  42       // prescribed boundaries.
  43
  44       T elements[Capacity];  // The queue itself.
  45       int front, back;             // indices to front and back of the queue
  46       int count;                   // number of elements
  47
  48    public:
  49
  50       FixQueue() : front(0), back(1), count(0) {}
  51
  52       inline int size() const      { return count; }
  53       inline int capacity() const  { return Capacity; }
  54       inline Bool is_empty() const { return count == 0; }
  55       inline Bool is_full() const  { return count == Capacity; }
  56
  57       inline const T& head() const { return elements[front]; }
  58       inline       T& head()       { return elements[front]; }
  59       inline const T& tail() const { return elements[back]; }
  60       inline       T& tail()       { return elements[back]; }
  61
  62       inline const T& operator [] (int i) const
  63          {  int index = front + i;
  64             if (index >= Capacity) index -= Capacity;
  65             return elements[index];
  66          }
  67
  68       inline T& operator [] (int i)
  69          {  int index = front + i;
  70             if (index >= Capacity) index -= Capacity;
  71             return elements[index];
  72          }
  73
  74       inline void clear() { front = 0; back = 1; }
  75       inline void insert_head (const T& e)
  76          {  if (++front >= Capacity) front = 0; elements[front] = e; count++; }
  77       inline T& remove_head ()
  78          {  int index = front--; count--;
  79             if (front < 0) front = Capacity-1;
  80             return elements[index];
  81          }
  82       inline void insert_tail (const T& e)
  83          {  if (--back < 0) back = Capacity-1; elements[back] = e; count++; }
  84       inline T& remove_tail ()
  85          {  int index = back++; count--;
  86             if (back >= Capacity) back = 0;
  87             return elements[index];
  88          }
  89
  90       /////////////////////////////////////////////////////////////////
  91       //  Iterators
  92       /////////////////////////////////////////////////////////////////
  93       inline Ix first()    const { return Ix(count); }
  94       inline Ix last()     const { return Ix(count > 0 ? 1 : 0); }
  95       inline Ix next(Ix i) const { return Ix((int)i - 1); }
  96       inline Ix prev(Ix i) const { return Ix((int)i < count ? (int)i+1 : 0); }
  97       inline const T& operator () (Ix i) const { return (*this)[(int)i-1]; }
  98       inline T& operator () (Ix i) { return (*this)[(int)i-1]; }
  99    };
 100
 101 #endif