PriorityQueueCellArray.h

Go to the documentation of this file.

// -*- C++ -*-

// CONTINUE: add more documentation.

#if !defined(__ads_PriorityQueueCellArray_h__)
#define __ads_PriorityQueueCellArray_h__

#include "PriorityQueue.h"

#include "../array/Array.h"

#include <vector>

BEGIN_NAMESPACE_ADS


template<typename T, 
         typename Key = typename std::iterator_traits<T>::value_type,
         class GetKey = Dereference<T>,
         class Container = std::vector<T> >
class PriorityQueueCellArray :
  public PriorityQueue<T, Key> {
 private:

  //
  // private typedefs.
  //

  typedef PriorityQueue<T, Key> base_type;
  typedef GetKey get_key_functor;

 public:

  //
  // public typedefs.
  //

  typedef typename base_type::element_type element_type;
  typedef typename base_type::key_type key_type;
  typedef typename base_type::size_type size_type;

  typedef Container container_type;
  typedef const container_type& container_const_reference;
  typedef typename container_type::value_type value_type;
  typedef typename container_type::reference reference;
  typedef typename container_type::const_reference const_reference;
  typedef typename container_type::iterator iterator;
  typedef typename container_type::const_iterator const_iterator;

 private:

  // 
  // private typedefs
  //

  // The cell array.
  typedef Array< 1, container_type > cell_array_type;
  // An iterator over cells.
  typedef typename cell_array_type::iterator cell_iterator;

 private:

  //
  // Member data.
  //

  // The cell array.
  cell_array_type _array;
  // The top cell in the priority queue.
  cell_iterator _top;
  // The number of elements in the priority queue.
  size_type _size;
  // The minimum key that will be stored in the queue.
  key_type _min_key;
  // The span of a single cell.
  key_type _delta;
  // A lower bound on the keys stored in the top cell.
  key_type _lower_bound;
  // The number of cells.
  int _num_cells;

  // The functor to get the key from an element.
  get_key_functor _get_key;

#ifdef DEBUG_PriorityQueueCellArray
  // The index of the top cell (non-cyclic).
  int _top_index;
#endif

 public:

  //
  // Constructor and destructor.
  //


  PriorityQueueCellArray(key_type min_key, key_type delta, key_type span) :
    _array(int(span / delta) + 3),
    _top(_array.begin()),
    _size(0),
    // Adjust it down by delta, because we are not allowed to push into
    // the top cell.
    _min_key(min_key - delta),
    _delta(delta),
    _lower_bound(_min_key),
    _num_cells(_array.size()),
    _get_key()
#ifdef DEBUG_PriorityQueueCellArray
                                                                            ,_top_index(0)
#endif
  {}

  virtual
  ~PriorityQueueCellArray()
  {}

  //
  // Accessors
  //

  container_const_reference 
  top() const {
    return *_top;
  }

  size_type
  size() const {
    return _size;
  }

  bool
  empty() const {
    return _size == 0;
  }

  key_type
  lower_bound() const {
    return _lower_bound;
  }

  //
  // Manipulators
  //

  void 
  push(element_type x) {
    ++_size;
    _array[ index(_get_key(x)) ].push_back(x);
  }

  void 
  push(element_type x, key_type k) {
    ++_size;
    _array[ index(k) ].push_back(x);
  }

  void
  pop() {
    // Adjust the number of elements in the priority queue.
    _size -= _top->size();
    // Clear the container.
    _top->clear();
    // Increment the top iterator.
    ++_top;
    if (_top == _array.end()) {
      _top = _array.begin();
    }
    // Increment the lower bound on keys.
    _lower_bound += _delta;
#ifdef DEBUG_PriorityQueueCellArray
    ++_top_index;
#endif
  }

 private:

  //
  // Private member functions.
  //

  // Return the index of the appropriate cell.
  int
  index(key_type k) const {
#ifdef DEBUG_PriorityQueueCellArray
    int index = int((k - _min_key) / _delta);
    assert(k >= _min_key + _delta && _top_index < index &&
            index < _top_index + _num_cells);
#endif
    return int((k - _min_key) / _delta) % _num_cells;
  }

};

END_NAMESPACE_ADS

#endif

---