generic finger-tree structure (http://staff.city.ac.uk/~ross/papers/FingerTree.html)
#4IntervalMap: split on left bound and search on right bound
Hi,
Thank you for writing fingertree, this is a neat data structure!
In a recent discussion about it on reddit, I came up with a few functions that unfortunately cannot be implemented with the current opaque API.
-- | Separate intervals that start before and after the key.
startAfter :: Ord v => v -> IntervalMap v a -> (IntervalMap v a, IntervalMap v a)
-- | Get the interval with the smallest left bound.
startsFirst :: Ord v => IntervalMap v a -> Maybe (Interval v, a)
-- | Get the interval with the greatest right bound.
endsLast :: Ord v => IntervalMap v a -> Maybe (Interval v, a)Do they seem like good candidates to be added to the library? I can work on a patch, if that is a good idea.
Would it also be possible to make the implementation details of IntervalMap available in an Internal module?
Hello
I am the original requester from the Reddit thread. For me personally, I don't mind abstraction in the interface. Basically, I already have some that can use a Data.Map and can be missing data, in which case I can use Map.lookupLE or Map.lookupGE to get the nearest match on either side. I would like to have some kind of functionality like this on IntervalMap (in fact, for my specific case I only need searchLE or "search less than or equal").
- status set to closed
I've added startAfter (called splitAfter), a generalization of startFirst (called leastView), and a bounds function, which, together with search, should give the functionality of endsLast.
I'd rather not make an Internal module, if only so that missing functionality will be reported as a bug.
