tpl_arrayQueue.H

# ifndef TPL_ARRAYQUEUE_H
# define TPL_ARRAYQUEUE_H

# include <ahAssert.H>
# include <ahDefs.H>
# include <tpl_memArray.H>

using namespace Aleph;

namespace Aleph {

    template <typename T> 
class ArrayQueue : public MemArray<T>
{
private:

  size_t front_index; // items are extracted from this point
  size_t rear_index;  // new item are inserted by this point

  void increase_index(size_t & i, const size_t inc = 1) const
  {
    i += inc;
    i %= this->dim;
  }

  T & rear_item(const size_t i = 0) 
  {
    return this->access((size_t) (rear_index - i - 1) % this->dim);
  }

  const T & rear_item(const size_t i = 0) const
  {
    return this->access((size_t) (rear_index - i - 1) % this->dim);
  }

public:

  void swap(ArrayQueue & q)
  {
    this->MemArray<T>::swap(q);
    std::swap(front_index, q.front_index);
    std::swap(rear_index, q.rear_index);
  }

  ArrayQueue(const size_t sz = 8) 
    : MemArray<T>(sz), front_index(0), rear_index(0)
  {
    // empty
  }

  ArrayQueue(const ArrayQueue & q)
    : MemArray<T>(q), front_index(q.front_index), rear_index(q.rear_index)
  {

  }

  ArrayQueue(ArrayQueue && q)
    : MemArray<T>(std::move(q)), 
      front_index(q.front_index), rear_index(q.rear_index)
  {
    // empty
  }

  ArrayQueue & operator = (const ArrayQueue & q)
  {
    if (this == &q)
      return *this;

    static_cast<MemArray<T>&>(*this) = q;
    
    front_index = q.front_index;
    rear_index = q.rear_index;

    return *this;
  }

  ArrayQueue & operator = (ArrayQueue && q)
  {
    std::swap(front_index, q.front_index);
    std::swap(rear_index, q.rear_index);
    static_cast<MemArray<T>*>(this)->swap(q);
    return *this;
  }

private:

  T & complete_put()
  {
    T & ret_val = this->access(rear_index);
    increase_index(rear_index);
    ++this->n;
    return ret_val;
  }

public:

  T & put(const T & item) throw(std::exception, std::bad_alloc)
  {
    if (this->expand(front_index))
      {
        front_index = 0;
        rear_index = this->n; 
      }
    this->access(rear_index) = item;
    return complete_put();
  }

  T & put(T && item) throw(std::exception, std::bad_alloc)
  {
    if (this->expand(front_index))
      {
        front_index = 0;
        rear_index = this->n; 
      }
    this->access(rear_index) = std::move(item);
    return complete_put();
  }

  T & putn(size_t sz) throw(std::exception, std::bad_alloc)
  {
    const int avail_n = this->dim - this->n;
    if (avail_n > sz)
      {
        sz -= this->dim - this->n;
        this->n = this->dim;
        this->expand(front_index);
      }

    increase_index(rear_index, sz);
    this->n += sz;
    return rear_item();
  }

  T get() throw(std::exception, std::underflow_error, std::bad_alloc)
  {
    if (this->n == 0)
      throw std::underflow_error ("queue is empty");

    T ret_val = std::move(this->access(front_index)); 
    this->n--;
    increase_index(front_index);

    if (this->contract(front_index))
      {
        front_index = 0;
        rear_index = this->n;
      }

    return ret_val;
  }

  T & getn(const size_t i) throw(std::exception, std::underflow_error)
  {
    if (i >= this->n)
      throw std::underflow_error ("queue is empty");

    this->n -= i;
    increase_index(front_index, i);

    if (this->contract(front_index))
      {
        front_index = 0;
        rear_index = this->n;
      }

    return this->access(front_index);
  } 

  T & front(const size_t i = 0) throw(std::exception, std::range_error)
  {
    if (i >= this->n) 
      throw std::range_error ("index of front out of range");

    return this->access((front_index + i) % this->dim);
  }

  const T & front(const size_t i = 0) const
    throw(std::exception, std::range_error)
  {
    if (i >= this->n) 
      throw std::range_error ("index of front out of range");

    return this->access((front_index + i) % this->dim);
  }

  T & rear(const size_t i = 0) throw(std::exception, std::range_error)
  {
    if (i >= this->n) 
      throw std::range_error ("index of rear out of range");

    return rear_item(i);
  }

  const T & rear(const size_t i = 0) const
    throw(std::exception, std::range_error)
  {
    if (i >= this->n) 
      throw std::range_error ("index of rear out of range");

    return rear_item(i);
  }

  template <class Operation>
  bool traverse(Operation & operation)
  {
    if (this->n == 0)
      return true;

    for (size_t i = front_index; i != rear_index; ++i)
      if (not operation(this->access(i)))
        return false;
    return true;
  }

  template <class Operation>
  bool traverse(Operation & operation) const 
  {
    return const_cast<ArrayQueue*>(this)->traverse(operation);
  }

  template <class Operation>
  bool traverse(Operation && operation = Operation()) const
  {
    return traverse<Operation>(operation);
  }

  template <class Operation>
  bool traverse(Operation && operation = Operation())
  {
    return traverse<Operation>(operation);
  }

  Functional_Methods(T);

  Generic_Items(T);
};

    template <typename T> 
class FixedQueue
{
private:

  size_t two_pow;
  size_t dim;
  T *    array;
  size_t front_index; /* index of oldest inserted item */
  size_t rear_index;
  size_t mask;
  size_t num_items; 

  void increase_index(size_t & i, const size_t inc = 1) const
  {
    I( ((i + inc)%dim) == ((i+ inc)&mask) );

    i += inc;
    i &= mask;  
  }

  T & rear_item(const size_t i = 0) 
  {
    I(static_cast<size_t>((rear_index - i - 1) & mask) == 
      (rear_index - i - 1)%dim);

    return array[static_cast<size_t> ((rear_index - i - 1) & mask)];
  }

  const T & rear_item(const size_t i = 0) const
  {
    I(static_cast<size_t>((rear_index - i - 1) & mask) == 
      (rear_index - i - 1)%dim);

    return array[static_cast<size_t> ((rear_index - i - 1) & mask)];
  }

public:

  void swap(FixedQueue & q)
  {
    std::swap(two_pow, q.two_pow);
    std::swap(dim, q.dim);
    std::swap(array, q.array);
    std::swap(front_index, q.front_index);
    std::swap(rear_index, q.rear_index);
    std::swap(mask, q.mask);
    std::swap(num_items, q.num_items);
  }

  FixedQueue(const size_t & tp = 8)  
    : two_pow(tp), dim(1<<two_pow), array(NULL), front_index(0), 
      rear_index(0), mask(dim - 1), num_items(0)
  { 
    array = new T [dim];
  }

  ~FixedQueue()
  {
    if (array != NULL)
      delete [] array;
  }

  FixedQueue(const FixedQueue & q) 
    : two_pow(q.two_pow), dim(q.dim), array(new T [dim]),
      front_index(q.front_index), rear_index(q.rear_index), mask(q.mask), 
      num_items(q.num_items)
  {
    for (size_t i = front_index; i != rear_index; ++i)
      array[i] = q.array[i];
  }

  FixedQueue(FixedQueue && q) : FixedQueue()
  {
    swap(q);
  }

  FixedQueue & operator = (const FixedQueue & q)
  {
    if (this == &q)
      return *this;

    if (array != NULL)
      delete [] array;

    new (this) FixedQueue(q);
    return *this;
  }

  FixedQueue & operator = (FixedQueue && q)
  {
    swap(q);
    return *this;
  }

  T & put(const T& item) throw(std::exception, std::overflow_error)
  {
    I(num_items < dim);
    array[rear_index] = item;
    T & ret_val = array[rear_index];
    increase_index(rear_index);
    num_items++;
    return ret_val;
  }

  T & put(T && item) throw(std::exception, std::overflow_error)
  {
    I(num_items < dim);
    array[rear_index] = std::move(item);
    T & ret_val = array[rear_index];
    increase_index(rear_index);
    num_items++;
    return ret_val;
  }

  T & putn(const size_t n) throw(std::exception, std::overflow_error)
  {
    I(num_items + n < dim);
    increase_index(rear_index, n);
    num_items += n;
    return rear_item();
  }

  T get() throw(std::exception, std::underflow_error)
  {
    I(num_items > 0);
    num_items--;
    T ret_val = std::move(array[front_index]);
    increase_index(front_index);
    return ret_val;
  }

  T & getn(const size_t n) throw(std::exception, std::underflow_error)
  {
    I(num_items >= n);
    num_items -= n;
    increase_index(front_index, n);
    return array[front_index];
  } 

  T & front(const size_t i = 0) throw(std::exception, std::range_error)
  {
    I(i < num_items);
    return array[front_index + i];
  }

  const T & front(const size_t i = 0) const
    throw(std::exception, std::range_error)
  {
    I(i < num_items);
    return array[front_index + i];
  }

  T & rear(const size_t i = 0) throw(std::exception, std::range_error)
  {
    I(i < num_items);
    return rear_item(i);
  }

  const T & rear(const size_t i = 0) const 
    throw(std::exception, std::range_error)
  {
    I(i < num_items);
    return rear_item(i);
  }

  const size_t & size() const { return num_items; }

  bool is_empty() const { return num_items == 0; }

  const size_t & capacity() const { return dim; }

  template <class Operation>
  bool traverse(Operation & operation)
  {
    if (num_items == 0)
      return true;
    for (size_t i = front_index; i != rear_index; ++i)
      if (not operation(array[i]))
        return false;
    return true;
  }

  template <class Operation>
  bool traverse(Operation & operation) const 
  {
    return const_cast<FixedQueue*>(this)->traverse(operation);
  }

  template <class Operation>
  bool traverse(Operation && operation = Operation()) const
  {
    return traverse<Operation>(operation);
  }

  template <class Operation>
  bool traverse(Operation && operation = Operation())
  {
    return traverse<Operation>(operation);
  }

  Functional_Methods(T);

  Generic_Items(T);
};

} // end namespace Aleph

# endif /* TPL_ARRAYQUEUE_H */