#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <tuple>
#include <iomanip>
using namespace std;

/** A point in the stream.
 * 
 * point where (at a specific time) the value changes.
 * */
template<typename T>
struct Point {
  using value_type = T;
  float time;
  T value;
};

/** Alias to break through a single iterator layer. */
template<typename Iterator>
using Behind1Iterator =
  typename iterator_traits<Iterator>::value_type;

/** Alias to break through 2 layers of iterators. */
template<typename Iterator>
using Behind2Iterators =
  Behind1Iterator<typename Behind1Iterator<Iterator>::iterator>;

/** Merge streams (sorted ranges of points) into a single, final stream, with
 * the values superimposed. */
template<
 typename Iterator,
 typename Out
 >
void merge_point_lists(
      Iterator from, Iterator to,
      Out out) {
  using namespace std;
  // Iterator type of the containers which are the values
  // of the given range [from,to)
  using StreamIterator = typename Behind1Iterator<Iterator>::iterator;
  // value_type of the Points
  using Value = typename Behind2Iterators<Iterator>::value_type;
  // Information about each of the streams:
  // 1. the current effect on the result stream
  // 2. iterator to the next time point in the stream
  // 3. end of the stream
  vector<tuple<Value, StreamIterator, StreamIterator>> streams;
  transform(from, to, inserter(streams, begin(streams)),
      [] (auto & stream) {
        return make_tuple(static_cast<Value>(0), begin(stream), end(stream));
      });
  // Comparator to generate a min heap (!), where the top element is
  // the information for the stream, whose next value is the earliest.
 auto heap_compare = [] (auto const & lhs, auto const & rhs) {
         bool less = (*get<1>(lhs)).time < (*get<1>(rhs)).time;
         return (not less);
       };
  // The current value of the result stream.
  Value current = 0;
  while (streams.size() > 0) {
  	// Reorder the stream information to get the one with the earliest next
  	// value into top ...
    make_heap(begin(streams), end(streams), heap_compare);
    // .. and select it.
    auto & earliest = streams[0];
    // New value is the current one, minus the previous effect of the selected
    // stream plus the new value from the selected stream
    current = current - get<0>(earliest) + (*get<1>(earliest)).value;
    // Store the new time point with the new value and the time of the used
    // time point from the selected stream
    *out++ = Point<Value>{(*get<1>(earliest)).time, current};
    // Update the effect of the selected stream
    get<0>(earliest) = (*get<1>(earliest)).value;
    // Advance selected stream to its next time point
    ++(get<1>(earliest));
    // Remove stream if empty
    if (get<1>(earliest) == get<2>(earliest)) {
      swap(streams[0], streams[streams.size() - 1u]);
      streams.pop_back();
    }
  }
}



int main(int, char **) {
  vector<Point<int>> input[] = {
      {{0.5,1}, {2,2}, {3.2,3}, {4,0}},
      {{1,10}, {2,20}, {3,30}, {4.5,0}},
      {{3.14,100}, {6.28,200}, {10,0}},
      {{1.5,1000},{2.5,0}}};
  vector<Point<int>> merged;
  merge_point_lists(begin(input), end(input), inserter(merged, begin(merged)));
  // returns points with the same time, but with different values. remove these
  // duplicates, by first making them REALLY equal, i.e. setting their values
  // to the last value ...
  for (auto write = begin(merged), read = begin(merged), stop = end(merged);
      write != stop;) {
    for (++read; (read != stop) and (read->time == write->time); ++read) {
      write->value = read->value;
    }
    for (auto const cached = (write++)->value; write != read; ++write) {
      write->value = cached;
    }
  }
  // ... and then removing them.
  merged.erase(
      unique(begin(merged), end(merged),
          [](auto const & lhs, auto const & rhs) {
            return (lhs.time == rhs.time);}),
      end(merged));
  // print the result
  for (auto const & point : merged) {
    cout << "@" << setw(4) << point.time << " change to " << setw(5) << point.value << endl;
  }
  return 0;
}