fork download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <iterator>
  5. #include <tuple>
  6. #include <iomanip>
  7. using namespace std;
  8.  
  9. /** A point in the stream.
  10.  * 
  11.  * point where (at a specific time) the value changes.
  12.  * */
  13. template<typename T>
  14. struct Point {
  15.   using value_type = T;
  16.   float time;
  17.   T value;
  18. };
  19.  
  20. /** Alias to break through a single iterator layer. */
  21. template<typename Iterator>
  22. using Behind1Iterator =
  23.   typename iterator_traits<Iterator>::value_type;
  24.  
  25. /** Alias to break through 2 layers of iterators. */
  26. template<typename Iterator>
  27. using Behind2Iterators =
  28.   Behind1Iterator<typename Behind1Iterator<Iterator>::iterator>;
  29.  
  30. /** Merge streams (sorted ranges of points) into a single, final stream, with
  31.  * the values superimposed. */
  32. template<
  33.  typename Iterator,
  34.  typename Out
  35.  >
  36. void merge_point_lists(
  37.       Iterator from, Iterator to,
  38.       Out out) {
  39.   using namespace std;
  40.   // Iterator type of the containers which are the values
  41.   // of the given range [from,to)
  42.   using StreamIterator = typename Behind1Iterator<Iterator>::iterator;
  43.   // value_type of the Points
  44.   using Value = typename Behind2Iterators<Iterator>::value_type;
  45.   // Information about each of the streams:
  46.   // 1. the current effect on the result stream
  47.   // 2. iterator to the next time point in the stream
  48.   // 3. end of the stream
  49.   vector<tuple<Value, StreamIterator, StreamIterator>> streams;
  50.   transform(from, to, inserter(streams, begin(streams)),
  51.       [] (auto & stream) {
  52.         return make_tuple(static_cast<Value>(0), begin(stream), end(stream));
  53.       });
  54.   // Comparator to generate a min heap (!), where the top element is
  55.   // the information for the stream, whose next value is the earliest.
  56.  auto heap_compare = [] (auto const & lhs, auto const & rhs) {
  57.          bool less = (*get<1>(lhs)).time < (*get<1>(rhs)).time;
  58.          return (not less);
  59.        };
  60.   // The current value of the result stream.
  61.   Value current = 0;
  62.   while (streams.size() > 0) {
  63.   	// Reorder the stream information to get the one with the earliest next
  64.   	// value into top ...
  65.     make_heap(begin(streams), end(streams), heap_compare);
  66.     // .. and select it.
  67.     auto & earliest = streams[0];
  68.     // New value is the current one, minus the previous effect of the selected
  69.     // stream plus the new value from the selected stream
  70.     current = current - get<0>(earliest) + (*get<1>(earliest)).value;
  71.     // Store the new time point with the new value and the time of the used
  72.     // time point from the selected stream
  73.     *out++ = Point<Value>{(*get<1>(earliest)).time, current};
  74.     // Update the effect of the selected stream
  75.     get<0>(earliest) = (*get<1>(earliest)).value;
  76.     // Advance selected stream to its next time point
  77.     ++(get<1>(earliest));
  78.     // Remove stream if empty
  79.     if (get<1>(earliest) == get<2>(earliest)) {
  80.       swap(streams[0], streams[streams.size() - 1u]);
  81.       streams.pop_back();
  82.     }
  83.   }
  84. }
  85.  
  86.  
  87.  
  88. int main(int, char **) {
  89.   vector<Point<int>> input[] = {
  90.       {{0.5,1}, {2,2}, {3.2,3}, {4,0}},
  91.       {{1,10}, {2,20}, {3,30}, {4.5,0}},
  92.       {{3.14,100}, {6.28,200}, {10,0}},
  93.       {{1.5,1000},{2.5,0}}};
  94.   vector<Point<int>> merged;
  95.   merge_point_lists(begin(input), end(input), inserter(merged, begin(merged)));
  96.   // returns points with the same time, but with different values. remove these
  97.   // duplicates, by first making them REALLY equal, i.e. setting their values
  98.   // to the last value ...
  99.   for (auto write = begin(merged), read = begin(merged), stop = end(merged);
  100.       write != stop;) {
  101.     for (++read; (read != stop) and (read->time == write->time); ++read) {
  102.       write->value = read->value;
  103.     }
  104.     for (auto const cached = (write++)->value; write != read; ++write) {
  105.       write->value = cached;
  106.     }
  107.   }
  108.   // ... and then removing them.
  109.   merged.erase(
  110.       unique(begin(merged), end(merged),
  111.           [](auto const & lhs, auto const & rhs) {
  112.             return (lhs.time == rhs.time);}),
  113.       end(merged));
  114.   // print the result
  115.   for (auto const & point : merged) {
  116.     cout << "@" << setw(4) << point.time << " change to " << setw(5) << point.value << endl;
  117.   }
  118.   return 0;
  119. }
  120.  
Success #stdin #stdout 0s 3460KB
comments (?)
stdin 
Standard input is empty
stdout 
@ 0.5 change to     1
@   1 change to    11
@ 1.5 change to  1011
@   2 change to  1022
@ 2.5 change to    22
@   3 change to    32
@3.14 change to   132
@ 3.2 change to   133
@   4 change to   130
@ 4.5 change to   100
@6.28 change to   200
@  10 change to     0
https://ideone.com/Dt1OU8
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!