output.txt

we made 2001 samples in a noisy line from -1 to 1
we found 10 levels of overview
level	size
  0	1001
  1	501
  2	251
  3	126
  4	63
  5	32
  6	16
  7	8
  8	4
  9	2
  10	1
level:6 :: -0.872762,-1.000000 -0.744586,-0.871821 -0.616251,-0.743321 -0.488057,-0.615834 -0.360860,-0.487522 -0.232252,-0.359011 -0.104363,-0.231671 0.023846,-0.103364 0.151822,0.024362 0.279400,0.152869 0.407188,0.280731 0.535230,0.408374 0.663373,0.536270 0.791642,0.664731 0.919253,0.792076 1.000738,0.000000
level:7 :: -0.744586,-1.000000 -0.488057,-0.743321 -0.232252,-0.487522 0.023846,-0.231671 0.279400,0.024362 0.535230,0.280731 0.791642,0.536270 1.000738,0.000000
level:8 :: -0.488057,-1.000000 0.023846,-0.487522 0.535230,0.024362 1.000738,0.000000
level:9 :: 0.023846,-1.000000 1.000738,0.000000

waveform-overview.cpp

#include <iostream>
#include <limits>
#include <vector>

struct Max {
  float maximum{-std::numeric_limits<float>::infinity()};
  void consider(float f) {
    if (f > maximum) maximum = f;
  }
};

struct Min {
  float minimum{std::numeric_limits<float>::infinity()};
  void consider(float f) {
    if (f < minimum) minimum = f;
  }
};

struct MaxMin : Max, Min {
  void consider(float f) {
    Min::consider(f);
    Max::consider(f);
  }
};

typedef std::vector<MaxMin> Overview;
typedef std::vector<Overview> OverviewList;

struct Thing {
  OverviewList overviewList;

  unsigned build(float* waveform, unsigned size) {
    unsigned level = 0;

    // make a new level: 0
    overviewList.emplace_back();

    // fill in the 0th level of summary. 1 Maxmin for each pair of samples
    for (unsigned k = 0; k < size; k += 2) {
      MaxMin& mm = overviewList.back().emplace_back();
      mm.consider(waveform[k]);
      mm.consider(waveform[k + 1]);
    }

    level++;

    while (true) {
      // make a new level
      overviewList.emplace_back();

      Overview& previousLevel(overviewList[level - 1]);
      Overview& o(overviewList[level]);

      // for each MaxMin frame on the previous level...
      unsigned n = 0;
      for (auto& mm : previousLevel) {
        if (n % 2 == 0) {
          // add 1 MaxMin for every 2 MaxMin from the previous level
          o.emplace_back();
        }
        o.back().Max::consider(mm.maximum);
        o.back().Min::consider(mm.minimum);
        n++;
      }

      if (o.size() == 1) {
        // we found an overview level that only needs one MaxMin to summarize
        break;
      }

      level++;
    }

    return level;
  }
};

float r() { return rand() / float(RAND_MAX); }

int main() {
  std::vector<float> waveform;
  for (float f = -1.0f; f < 1.0f; f += 0.001f) {
    waveform.push_back(f + r() / 1000);
  }

  printf("we made %lu samples in a noisy line from -1 to 1\n", waveform.size());

  Thing thing;
  unsigned levels = thing.build(waveform.data(), waveform.size());
  printf("we found %u levels of overview\n", levels);
  printf("level\tsize\n");
  for (int i = 0; i < thing.overviewList.size(); i++) {
    printf("  %d\t%lu\n", i, thing.overviewList[i].size());
  }
  for (unsigned l = 6; l < levels; l++) {
    printf("level:%u :: ", l);
    for (auto& mm : thing.overviewList[l]) {
      printf("%f,%f ", mm.maximum, mm.minimum);
    }
    printf("\n");
  }
}