haskell/containers — pull request #8 by mkscrg (2012-01-30 23:54:53+00:00)
Title: Implementation of `successor` function for IntMap

PATRICIA trees support the "successor" operation with O(min(n,W)) runtime complexity. That is, given some input key `k'`, find the `(k, v)` pair with the smallest `k` greater than or equal to `k'`. This is useful for efficiently implementing certain hashing schemes such as (consistent hashing)[http://en.wikipedia.org/wiki/Consistent_hashing].

This pull request is an implementation of an O(min(n,W)) `successor` function:

successor :: Key -> IntMap a -> Maybe (Key, a)

Note that you can implement `successor` in terms of `splitLookup` and `findMin`, but the use of `splitLookup` slows things down unnecessarily.

Cheers,
Mike