MergeIterator.h

#ifndef theplu_yat_utility_merge_iterator
#define theplu_yat_utility_merge_iterator

// $Id: MergeIterator.h 3550 2017-01-03 05:41:02Z peter $

/*
  Copyright (C) 2013, 2015, 2016 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/concept_check.hpp>
#include <boost/iterator/iterator_concepts.hpp>
#include <boost/iterator/iterator_facade.hpp>
#include <boost/iterator/iterator_traits.hpp>

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

namespace theplu {
namespace yat {
namespace utility {

  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:
    MergeIterator(void) {};

    MergeIterator(const std::vector<std::pair<Base, Base> >& vec)
    { init(vec); };

    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_;
  };

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


  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)
  {
    BOOST_CONCEPT_ASSERT((boost_concepts::ReadableIterator<Base>));
    BOOST_CONCEPT_ASSERT((boost_concepts::SinglePassIterator<Base>));
    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