Analyze time series data to get min max over past period of time The algorithm should analyze measured time series data in realtime and should check if all values of the specified last period lay inside a specified range. The range is calculated with max-min over the specified time period.

Input data

t        | 10:00 | 10:01 | 10:02 | 10:03 | ... | 19:00 |
Temp [°C]| 40    | 41.3  | 39    | 43    |     | 45    |


Algorithm parameters


Duration D: Past time to check for min/max
Max range R: (max-min) &lt; R


e.g: Check if the temperature was steady within 2 °C for the last hour. D=1hour, R=2°C

The algorithm should check periodically during data acquisition if the condition (all values of the last hour have been inside a range of 2°C) is true. 

Other requirements


The sampling time can be from 10Hz to 50kHz.
The time will always be increasing.
Since this algorithm should run in an realtime environment there should be no memory allocations during run time


Possible solutions

At the moment I have two possible solutions but do not like both of them:


Store all values within the duration in a bounded fifo-buffer and perform a min/max check from start to end periodically. I expect this to be the worst solution
Store the tuples in two B-Trees: 

There are two indexes


TimeIndex t->(t,v): Index from time to tuple, 
ValueIndex v->list(t,v): Index from the value to a list of tuples with this value. 


The algorithm will first get all tuples that are outside the time range and remove them in the value index. 

Then the value index is updated with the newly measured tuples. 

The range can then be determined by looking up the minimum and maximum key in the value index.


I think the second approach is faster but will allocate memory during runtime. Since it should run in a realtime environment I like to avoid allocations. 

Is there another possibility with O(log n) and no allocations?
The following paper provides a O(1) algorithm:

D. Lemire, Streaming Maximum-Minimum Filter Using No More than Three Comparisons per Element, Nordic Journal of Computing, 13 (4), 2006 (https://arxiv.org/abs/cs/0610046).

An implementation of this algorithm is provided in the GNU Scientific Library (see https://www.gnu.org/software/gsl/doc/html/movstat.html).