source: trunk/yat/utility/MergeIterator.h @ 3389

#ifndef theplu_yat_utility_merge_iterator
#define theplu_yat_utility_merge_iterator

// $Id: MergeIterator.h 3389 2015-03-16 07:48:21Z peter $

/*
  Copyright (C) 2013 Peter Johansson

  This file is part of the yat library, http://dev.thep.lu.se/yat

  The yat library 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; either version 3 of the
  License, or (at your option) any later version.

  The yat library 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 yat. If not, see <http://www.gnu.org/licenses/>.
*/

#include "stl_utility.h"
#include "yat/utility/yat_assert.h"

#include <boost/iterator/iterator_facade.hpp>
#include <boost/iterator/iterator_traits.hpp>

#include <iterator>
#include <set>
#include <vector>

namespace theplu {
namespace yat {
namespace utility {

  /**
     \brief Iterate over several ranges as if ranges have been merged

     MergeIterator is an \input_iterator that is created from several
     ranges and will iterate over the elements in the ranges as if
     ranges have been merged. Input ranges have to be sorted (as defined by
     the \c Compare object) or behaviour is undefined. When
     incremented, the iterator looks at next element in each range,
     identifies the smallest element, and points at that.

     Type Requirements:
     - \c Base is a \readable_iterator
     - \c Base is a \single_pass_iterator
     - \c Compare models
     <a href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html">
     StrictWeakOrdering</a>

     \since New in yat 0.11
   */
  template<
    typename Base,
    class Compare=std::less<typename std::iterator_traits<Base>::value_type>
    >
  class MergeIterator
    : public boost::iterator_facade<
    MergeIterator<Base, Compare>,
    typename boost::iterator_value<Base>::type,
    boost::single_pass_traversal_tag,
    typename boost::iterator_reference<Base>::type
    >
  {
  public:
    /**
       Creates an end-of-range iterator
     */
    MergeIterator(void) {};

    /**
       \brief Create MergeIterator

       Create a MergeIterator that will iterate over ranges
       [vec[0].first, vec[0].second), [vec[1].first, vec[1].second), ...

       \see make_merge_iterator(const std::vector<std::pair<Base, Base> >&)
     */
    MergeIterator(const std::vector<std::pair<Base, Base> >& vec)
    { init(vec); };

    /**
       \brief Creates MergeIterator using \a comp as compare object.

       Same as MergeIterator(2) but using \a comp rather than using a
       default constructed Compare object.

       \see
       make_merge_iterator(const std::vector<std::pair<Base, Base> >&, const Compare&)
     */
    MergeIterator(const std::vector<std::pair<Base, Base> >& vec,
                  const Compare& comp)
    : data_(PairCompare(comp))
    { init(vec); }

  private:
    friend class boost::iterator_core_access;

    typename MergeIterator<Base, Compare>::reference dereference(void) const;
    bool equal(const MergeIterator& other) const;
    void init(const std::vector<std::pair<Base,Base> >& v);
    void increment(void);

    class PairCompare
    {
    public:
      PairCompare(void) {}
      PairCompare(const Compare& c) : comp_(c) {}
      bool operator()(const std::pair<Base, Base>& x,
                      const std::pair<Base, Base>& y) const
      { return comp_(*x.first, *y.first); }
    private:
      Compare comp_;
    };

    std::multiset<std::pair<Base, Base>, PairCompare> data_;
  };

  /**
     Creates a MergeIterator that iterates over ranges defined in \a vec.

     \relates MergeIterator
   */
  template<typename Base>
  MergeIterator<Base>
  make_merge_iterator(const std::vector<std::pair<Base, Base> >& vec)
  {
    return MergeIterator<Base>(vec);
  }


  /**
     Creates a MergeIterator that iterates over ranges defined in \a
     vec, using \a comp to compare elements.

     \relates MergeIterator
  */
  template<typename Base, class Compare>
  MergeIterator<Base, Compare>
  make_merge_iterator(const std::vector<std::pair<Base, Base> >& vec,
                      const Compare& comp)
  {
    return MergeIterator<Base, Compare>(vec, comp);
  }



  // template implementations

  template<typename Base, class Compare>
  typename MergeIterator<Base, Compare>::reference
  MergeIterator<Base, Compare>::dereference(void) const
  {
    YAT_ASSERT(data_.size());
    YAT_ASSERT(data_.begin()->first != data_.begin()->second);
    return *data_.begin()->first;
  }


  template<typename Base, class Compare>
  bool MergeIterator<Base, Compare>::equal(const MergeIterator& other) const
  {
    if (data_.empty() || other.data_.empty())
      return data_.empty() == other.data_.empty();
    return data_.begin()->first == other.data_.begin()->first;
  }


  template<typename Base, class Compare>
  void
  MergeIterator<Base,Compare>::init(const std::vector<std::pair<Base,Base> >& v)
  {
    for (size_t i=0; i<v.size(); ++i)
      if (v[i].first != v[i].second)
        data_.insert(v[i]);
  }


  template<typename Base, class Compare>
  void MergeIterator<Base, Compare>::increment(void)
  {
    if (data_.empty())
      return;
    // store first range
    std::pair<Base, Base> tmp = *data_.begin();
    // remove first range from set of ranges
    data_.erase(data_.begin());
    // iterate the first range and if not end-of-range, insert the
    // range back into set of ranges
    if (++(tmp.first) != tmp.second)
      data_.insert(tmp);
  }

}}}
#endif