This package is not currently in any snapshots. If you're interested in using it, we recommend adding it to Stackage Nightly. Doing so will make builds more reliable, and allow stackage.org to host generated Haddocks.
This repository contains an implementation of order statistic tree in Haskell programming language.
I could not find an order statistic tree at Hackage, so I have to develop one.
This implementation uses weight-balanced trees which are desribed in
Hirai, Yoichi, and Kazuhiko Yamamoto. "Balancing weight-balanced trees." Journal of Functional Programming 21.03 (2011): 287-307.
Also some code is based on containers package.
Implementation of order statistic tree is described in
Cormen, T.H., Leiserson, Rivest, Stein. Introduction to algorithms. The MIT Press. 3rd ed.
Benchmarks
I tried to make this tree as fast as possible. The results on my i7-4790 with 16Gb RAM are following:
OSTree was created from 1.000.000 random numbers in 1.987 ± 0.015 s (e.g. for Data.Map.Strict - 2.081 ± 0.008 s);
deletion from OSTree with 1.000.000 random numbers was made in 13.88 ± 0.14 ms;
lookup from OSTree with 1.000.000 random numbers was made in 164.8 ± 1.06 ns;
selection from OSTree with 1.000.000 random numbers was made in 56.54 ± 0.99 ns;
full testing protocol can be found in result-bench.txt.
