Method sparsify

include/process/timeseries.hpp:191–229

Performs "sparsification" to limit the size of the time series to be within the capacity. The sparsifying technique is to iteratively halve the granularity of the older half of the time series. Once sparsification reaches the midpoint of the time series, it begins again from the beginning. Sparsification results in the following granularity over time: Initial: | ------------------------ A ------

  // Each stage halves the size and granularity of time series prior
  // to sparsifying.
  void sparsify()
  {
    // We remove every other element up to the halfway point of the
    // time series, until we're within the capacity. If we reach the
    // half-way point of the time series, we'll start another
    // sparsification cycle from the beginning, for example:
    //
    // next             Time series with a capacity of 7.
    //   v              Initial state with 7 entries
    // 0 1 2 3 4 5 6
    //
    //   next           Insert '7'.
    //     v            Capacity is exceeded, we remove '1' and
    // 0 2 3 4 5 6 7    advance to remove '3' next.
    //
    //     next         Insert '8'.
    //       v          Capacity is exceeded, we remove '3' and
    // 0 2 4 5 6 7 8    advance to remove '5' next.
    //
    // next             Insert '9'.
    //   v              Capacity is exceeded, we remove '5' and now
    // 0 2 4 6 7 8 9    '7' is past the halfway mark, so we will reset
    //                  reset to the beginning and consider '2'.

    while (values.size() > capacity) {
      // If the index is uninitialized, or past the half-way point,
      // we set it back to the beginning.
      if (index.isNone() || index.get() > values.size() / 2) {
        // The second element is the initial deletion candidate.
        next = values.begin();
        ++next;
        index = 1;
      }

      next = values.erase(next);
      next++; // Skip one element.
      index = index.get() + 1;
    }
  }

  // Non-const for assignability.
  Duration window;