FrontQueue.h

Go to the documentation of this file.

#ifndef FrontQueue_HEADER
#define FrontQueue_HEADER

#ifdef HAVE_CONFIG_H
# include <config.h>
#endif

/***************************************************************************
 * Benoit Hudson (C) 2007.
 ***************************************************************************/
#include "SmallList.h"

namespace hudson {
/***************************************************************************
  * A container adaptor much like the STL's queue, except that we only require
  * the container to be a Front Insertion Sequence, not both front and back.
  * We also require the 'reverse' and 'swap' operations to be defined.
  * This works, e.q., for a hudson::SmallList or a std::list or std::deque.
  *
  * Unlike in the STL queue, we do not implement back() or size().
  * All operations are amortized constant so long as Sequence::push_front(),
  * pop_front(), and front() are amortized constant.
  *
  * This adaptor is faster than QueueFromStack because it assumes the existence
  * of reverse and swap.
 ***************************************************************************/
  template <class Item, class Sequence = SmallList<Item> > struct FrontQueue {
    typedef Sequence container_type;
    typedef typename container_type::value_type value_type;
    typedef typename container_type::reference reference;
    typedef typename container_type::const_reference const_reference;

    FrontQueue() { }
    FrontQueue(const FrontQueue& q): in_(q.in_), out_(q.out_) { }
    FrontQueue& operator=(const FrontQueue& q) { in_ = q.in_; out_ = q.out_; }

    bool empty() const { return out_.empty(); }

    reference top() {
      assert(!out_.empty());
      return out_.front();
    }
    const_reference top() const {
      assert(!out_.empty());
      return out_.front();
    }
    reference front() { return top(); }
    const_reference front() const { return top(); }

    void push(const_reference v) {
      if (out_.empty()) {
        assert(in_.empty());
        out_.push_front(v);
      } else {
        in_.push_front(v);
      }
    }

    void pop() {
      assert(!out_.empty());
      out_.pop_front();

      /* If out_ is empty, copy in the elements from in_, in reverse order.
       * Knowing that this is a SmallList means we can do it without any
       * allocation. */
      if (out_.empty() && !in_.empty()) {
        out_.swap(in_);
        out_.reverse();
      }
    }

    private:
    container_type in_;
    container_type out_;
  };

} // namespace hudson

#endif

---