Rolling min max

[qchateau]

Rolling min and max with insertion complexity O(logN), where N is the window size, and extraction complexity O(1).

Is this fit for a merge into the main library ?

To be fair, I don't even know if this is the right place to submit a patch, but I could not find any information on how to contribute to accumulators. I hope someone can help.

[yuvalif]

@Tytan what if someone just wants min/max but without sorted rolling window? in this case insertion complexity should be O(1). only dependency should be of rolling window, not the sorted one.

[qchateau]

I will fix the documentation. What would you say is the quickest way of generating a human readable version of the doc ?

I sure can implement a lazy and immediate version of the rolling min and max if you deem the complexity acceptable. Anyway, you are right, people should be allowed to have the choice.

In this case what would you say should be the default implementation ? The lazy one would not mess with insertion cost, but I think people expect extraction to be fast.

[yuvalif]

I will fix the documentation. What would you say is the quickest way of generating a human readable version of the doc ?

I have no idea... maybe ask on the mailing list?

I sure can implement a lazy and immediate version of the rolling min and max if you deem the complexity acceptable. Anyway, you are right, people should be allowed to have the choice. In this case what would you say should be the default implementation ? The lazy one would not mess with insertion cost, but I think people expect extraction to be fast.

In general insertion cost is more important than extraction (assuming there are more insertions than extractions), but probably best to look at other accumulators where both options exist. Would be even nicer (though I'm not sure how to do that...) if you can collapse the lazy implementation to the regular one if you need the ordered window anyway (e.g. combining lazy min with regular max)

[qchateau]

I had to split the declaration of rolling_window and rolling_window_plus1 in rolling_window.hpp because GCC was complaining that the extractor of rolling_window used the extractor of rolling_window_plus1 before it was declared.

I added a lazy/immediate implementation for rolling min and max. The default being the lazy one.

I think addition of a mecanism to chose the immediate implementation instead of the lazy one if the sorted_rolling_window is used as a dependency by another feature in the set can be the subject of a further PR. I may work on this later on.