p_queue_fast.hh

// Copyright (C) 2007, 2008, 2009 EPITA Research and Development Laboratory (LRDE)
//
// This file is part of Olena.
//
// Olena is free software: you can redistribute it and/or modify it under
// the terms of the GNU General Public License as published by the Free
// Software Foundation, version 2 of the License.
//
// Olena is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with Olena.  If not, see <http://www.gnu.org/licenses/>.
//
// As a special exception, you may use this file as part of a free
// software project without restriction.  Specifically, if other files
// instantiate templates or use macros or inline functions from this
// file, or you compile this file and link it with other files to produce
// an executable, this file does not by itself cause the resulting
// executable to be covered by the GNU General Public License.  This
// exception does not however invalidate any other reasons why the
// executable file might be covered by the GNU General Public License.

#ifndef MLN_CORE_SITE_SET_P_QUEUE_FAST_HH
# define MLN_CORE_SITE_SET_P_QUEUE_FAST_HH


# include <mln/core/site_set/p_array.hh>


namespace mln
{

  // Forward declaration.
  template <typename P> class p_queue_fast;



  namespace trait
  {

    template <typename P>
    struct site_set_< p_queue_fast<P> >
    {
      typedef trait::site_set::nsites::known     nsites;
      typedef trait::site_set::bbox::unknown     bbox;
      typedef trait::site_set::contents::growing contents;
      typedef trait::site_set::arity::multiple   arity;
    };

  } // end of namespace trait




  template <typename P>
  class p_queue_fast : public internal::site_set_base_< P, p_queue_fast<P> >
  {
    typedef p_queue_fast<P> self_;
  public:

    typedef P element;

    typedef p_indexed_psite<self_> psite;

    typedef p_indexed_fwd_piter<self_> fwd_piter;

    typedef p_indexed_bkd_piter<self_> bkd_piter;

    typedef fwd_piter piter;


    p_queue_fast();

    void reserve(typename p_array<P>::size_type n);

    bool has(const psite& p) const;

    bool has(const util::index& i) const;

    bool is_valid() const;

    bool compute_has(const P& p) const;

    unsigned nsites() const;

    bool empty() const;

    void push(const P& p);

    typedef P i_element;

    void insert(const P& p);


    void pop();

    const P& front() const;

    const P& pop_front();


    void purge();

    void clear();


    const P& operator[](unsigned i) const;

    const std::vector<P>& std_vector() const;

    std::size_t memory_size() const;

  protected:

    p_array<P> q_;
    unsigned begin_;
    unsigned end_;
  };



# ifndef MLN_INCLUDE_ONLY

  template <typename P>
  inline
  p_queue_fast<P>::p_queue_fast()
  {
    begin_ = 0;
    end_ = 0;
  }

  template <typename P>
  inline
  void
  p_queue_fast<P>::reserve(typename p_array<P>::size_type n)
  {
    q_.reserve(n);
  }

  template <typename P>
  inline
  void
  p_queue_fast<P>::purge()
  {
    std::vector<P>& v = q_.hook_std_vector_();
    std::copy(v.begin() + begin_,
              v.begin() + end_,
              v.begin());
    v.resize(end_ - begin_);
    end_ -= begin_;
    begin_ = 0;
  }

  template <typename P>
  inline
  bool
  p_queue_fast<P>::has(const psite& p) const
  {
    mln_precondition(p.target_() == this); // FIXME: Refine.
    if (p.index() < 0 || unsigned(p.index()) >= nsites())
      return false;
    // The type of rhs below is mln_site(p_array<P>).
//     mln_invariant(p.to_site() == (*this)[p.index()]);
    return true;
  }

  template <typename P>
  inline
  bool
  p_queue_fast<P>::has(const util::index& i) const
  {
    return i >= 0 && unsigned(i) < nsites();
  }

  template <typename P>
  inline
  bool
  p_queue_fast<P>::compute_has(const P& p) const
  {
    for (unsigned i = begin_; i < end_; ++i)
      if (q_[i] == p)
        return true;
    return false;
  }

  template <typename P>
  inline
  bool
  p_queue_fast<P>::is_valid() const
  {
    return true;
  }

  template <typename P>
  inline
  unsigned
  p_queue_fast<P>::nsites() const
  {
    mln_invariant(end_ >= begin_);
    return end_ - begin_;
  }

  template <typename P>
  inline
  bool
  p_queue_fast<P>::empty() const
  {
    mln_invariant(end_ >= begin_);
    return end_ == begin_;
  }

  template <typename P>
  inline
  void
  p_queue_fast<P>::push(const P& p)
  {
    q_.append(p);
    ++end_;
  }

  template <typename P>
  inline
  void
  p_queue_fast<P>::pop()
  {
    mln_precondition(! this->is_empty());
    ++begin_;
  }

  template <typename P>
  inline
  const P&
  p_queue_fast<P>::front() const
  {
    mln_precondition(! this->is_empty());
    return q_[begin_];
  }

  template <typename P>
  inline
  const P&
  p_queue_fast<P>::pop_front()
  {
    mln_precondition(! this->is_empty());
    const P& res = this->front();
    this->pop();
    return res;
  }

  template <typename P>
  inline
  void
  p_queue_fast<P>::clear()
  {
    end_ = begin_;
  }

  template <typename P>
  inline
  const P&
  p_queue_fast<P>::operator[](unsigned i) const
  {
    mln_precondition(i < nsites());
    return q_[begin_ + i];
  }

  template <typename P>
  inline
  void
  p_queue_fast<P>::insert(const P& p)
  {
    this->push(p);
  }

  template <typename P>
  inline
  const std::vector<P>&
  p_queue_fast<P>::std_vector() const
  {
    return q_.std_vector();
  }

  template <typename P>
  inline
  std::size_t
  p_queue_fast<P>::memory_size() const
  {
    return q_.memory_size() + 2 * sizeof(unsigned);
  }

# endif // ! MLN_INCLUDE_ONLY

} // end of namespace mln


#endif // ! MLN_CORE_SITE_SET_P_QUEUE_FAST_HH