// Copyright 2008, Roland Bock

#include <queue>
#include <vector>

#include <boost/iterator/iterator_facade.hpp> 
#include <boost/iterator/iterator_concepts.hpp> 
#include <boost/range/iterator_range.hpp> 

/**
 *  A MergeIterator 
 *    takes a vector of IteratorRanges for sorted ranges 
 *    represents an iterator over the merged and sorted combination of the two
 */
template<typename IteratorType, 
         typename ItemType, 
         typename ItemComparatorType = std::greater<ItemType> >
class MergeIterator: public boost::iterator_facade<MergeIterator<IteratorType, ItemType>,
                                                    const ItemType,
                                                    boost::single_pass_traversal_tag>
{
public:
   // Constructor which takes a vector of Iterator Ranges
   MergeIterator(std::vector<boost::iterator_range<IteratorType> > iterators):
     iterators_(iterators.begin(), iterators.end())
   {
   }

   // Empty constructor can be used for comparison (== end of a MergeIterator)
   MergeIterator()
   {}

private:
   friend class boost::iterator_core_access;

   // Comparator for IteratorRanges.
   struct IteratorRangeComparator
   {
      bool operator()(const boost::iterator_range<IteratorType> lhs, const boost::iterator_range<IteratorType> rhs)
      {
         return ItemComparatorType()(lhs.front(), rhs.front());
      }
   };

private:
   void increment()
   {
      boost::iterator_range<IteratorType> top = iterators_.top();
      iterators_.pop();
      
      if (top.advance_begin(1).begin() != top.end())
      {
         iterators_.push(top);
      }
   }

   const ItemType& dereference() const
   {
      return iterators_.top().front();
   }

   const bool equal(const MergeIterator<IteratorType, ItemType>& rhs) const
   {
      return iterators_.size() == rhs.iterators_.size()
         && true; // How can two priority_queues be compared?
   }

   std::priority_queue<boost::iterator_range<IteratorType>, 
                       std::deque<boost::iterator_range<IteratorType> >,  
                       IteratorRangeComparator> iterators_;
};
//------------------------------------------------------------------------------------------




//------------------------------------------------------------------------------------------
// Sample program
//------------------------------------------------------------------------------------------
#include <iostream>
using namespace std;


int main()
{
   vector<int> a;
   vector<int> b; 

   for (int i = 0; i < 10; ++i)
      if (i%2)
         a.push_back(i);
      else
         b.push_back(i);

   boost::iterator_range<vector<int>::iterator> itA(a.begin(), a.end());
   boost::iterator_range<vector<int>::iterator> itB(b.begin(), b.end());


   vector<boost::iterator_range<vector<int>::iterator> > iterators;
   iterators.push_back(itA);
   iterators.push_back(itB);

   MergeIterator<vector<int>::iterator, int> mergedBegin(iterators);
   MergeIterator<vector<int>::iterator, int> mergedEnd;

   for (MergeIterator<vector<int>::iterator, int> it = mergedBegin; it != mergedEnd; ++it)
      cerr << *it << endl;
}