I am looking for help identifying the most efficient data structure and algorithms to hold and manipulate a collection of disjoint fixed interval times series data segments as an in memory cache. The time series data segments are vectors of numeric values of generic type T along with a start time and period:

  struct Segment<T> {
    // The gps time in nanoseconds of the first data point in data.
    start: u64,

    // The number of nanoseconds between adjacent data points in data.
    period: u64,

    data: Vec<T>,
  }

The operations need to include:

• Given a start time and a stop time:

  • Return the smallest set of disjoint segments that combine to hold all of the data in the collection between the given start time and stop time, trimmed as necessary to hold only values between those two times.
  • Return the smallest set of disjoint start time, stop time pairs that combine to give all of the time intervals between the given start time and stop time where there are no data values in the collection.

• Given a segment:

  • Trim it as needed to avoid overlap with any of the existing segments in the collection and then add it to the collection, merging it with any immediately time adjacent segments in the collection.

• Given a start time and a stop time:

  • Remove all of the data in the collection between the given start time and stop time, trimming the segments in the collection as needed.