bos/critbit — pull request #55 by isturdy (2013-05-29 15:33:27+00:00)
Title: Submap functions

Another place where the absence of an explicit key in the nodes hurts CritBit trees: all these are 50-100% slower than their Data.Map counterpart, primarily as a consequence of my having to traverse and rebuild the first tree to get a middle-ish key (an approach without `splitLookup`, using the entire right tree when it cannot be proved that the left tree is a subset of one of its branches, performs even worse). The benchmarking is also somewhat favorable to CritBit trees, as Maps keep size information in the nodes and can return immediately if the sizes are wrong.

I am in particular doubtful of my proper submap implementations; the method for tracking size seems somewhat kludgy (but performs somewhat better than checking sizes separately).

I based complexities on a worst-case complexity of `deleteFindMin` and `splitLookup` of *O(n)*; on a balanced tree they should be *O(log n)* and the submap functions should be *O(m log m + n log n)*.