|
From: Nicholas N. <nj...@cs...> - 2005-06-02 21:31:07
|
On Thu, 2 Jun 2005, Jeremy Fitzhardinge wrote: >> I have a patch that lets you use the regular skip-list as an interval >> skip-list, with just minor changes to the API. It's from a while ago, >> though. > > A skiplist can represent non-overlapping intervals, but an interval > skiplist is a related but significantly more complex datastructure which > stores overlapping intervals and allows efficient stab queries (ie, all > intervals which overlap a point). Oh, yep, you're right. > I'm just being pedantic. A skiplist containing intervals (like the > Segment list in 2.4) will do the job. The 2.4 skiplist doesn't do intervals nicely, because you have to do the skiplist lookup and then another check "is this in the interval?" afterwards. My patch made this case nicer. N |