Fast running maximum-minimum filters in C++.

A running maximum-minimum filter computes the maximum and minimum for each window in a sequence. For example, given these values:

1,2,3,2,1

Then the running maximum filter with a window of size 3 is:

3,3,3

whereas the minimum filter is

1, 2, 1

A running maximum-minimum filter computes simultaneously the maximum and the minimum filters.

This code implements the algorithms described in the following paper:

Daniel Lemire, Streaming Maximum-Minimum Filter Using No More than Three Comparisons per Element. Nordic Journal of Computing, 13 (4), pages 328-339, 2006.

A preprint is available there:

http://arxiv.org/abs/cs.DS/0610046

One of the result of this paper is that it is possible to compute the maximum-minimum filter faster than it is possible to compute both the maximum filter and the minimum filtering separately.