<div dir="ltr"><div>Ah, I see that there's a semantic difference between FSet's interval-sets and these interval trees.  FSet merges intervals that overlap or abut while from what I see on Wikipedia, these interval trees don't do that.  It's the difference between a set represented as a collection of intervals, where we care only what numbers are in the set, versus a set of intervals that we want to remember as pairs.  Depending on your requirements, either of these might fit your needs better.</div><div><br></div><div>-- Scott<br></div></div><br><div class="gmail_quote"><div dir="ltr">On Sat, Oct 27, 2018 at 10:33 AM Scott L. Burson <<a href="mailto:Scott@sympoiesis.com">Scott@sympoiesis.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>Look closer, Ron.  FSet <i>does</i> do those operations in log time :-)</div><div><br></div><div>-- Scott</div><div><br></div></div><br><div class="gmail_quote"><div dir="ltr">On Sat, Oct 27, 2018 at 9:13 AM Ron Garret <<a href="mailto:ron@flownet.com" target="_blank">ron@flownet.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word">Yes, I know about FSet.  FSet is cool because it’s purely functional, but that is not what I need.  I need an interval tree that is efficient, i.e. that has O(log(n)) insertion, search, and deletion.<div><br><div><div>On Oct 27, 2018, at 3:52 AM, Camille Troillard <<a href="mailto:camille.troillard@icloud.com" target="_blank">camille.troillard@icloud.com</a>> wrote:</div><br class="m_-4800955195614910929m_-120636439366402978Apple-interchange-newline"><blockquote type="cite"><div dir="auto">Hi Ron,<div><br></div><div>Scott Burson’s FSet library [1] has an interval-set collection which pretty good. I’m not sure if that fits your requirement though. <br><br><div dir="ltr">Cam</div><div dir="ltr"><br></div><div dir="ltr">[1] <a href="https://github.com/slburson/fset/blob/master/Code/interval.lisp" target="_blank">https://github.com/slburson/fset/blob/master/Code/interval.lisp</a></div><div dir="ltr"><br></div><div dir="ltr"><br>On 26 Oct 2018, at 17:46, Ron Garret <<a href="mailto:ron@flownet.com" target="_blank">ron@flownet.com</a>> wrote:<br><br></div><blockquote type="cite"><div dir="ltr"><span>This is not a CCL bug, but all the cool kids seem to hang out here so...</span><br><span></span><br><span>I hereby offer a $500 bug bounty to the first person to publish a fix for this issue:</span><br><span></span><br><span><a href="https://github.com/rpav/cl-interval/issues/5" target="_blank">https://github.com/rpav/cl-interval/issues/5</a></span><br><span></span><br><span>This offer expires on Friday, Nov 9, 2018.  That’s not a hard deadline — if you need more time I can accommodate you.  I just don’t want someone trying to claim the bounty a year from now.  Also, I will need your SSN or TIN so I can send you a 1099.</span><br><span></span><br><span>If you want to take this on, contact me off-list for some additional info and test cases to help you get started.</span><br><span></span><br><span>rg</span><br><span></span><br><span>_______________________________________________</span><br><span>Openmcl-devel mailing list</span><br><span><a href="mailto:Openmcl-devel@clozure.com" target="_blank">Openmcl-devel@clozure.com</a></span><br><span><a href="https://lists.clozure.com/mailman/listinfo/openmcl-devel" target="_blank">https://lists.clozure.com/mailman/listinfo/openmcl-devel</a></span><br></div></blockquote></div></div></blockquote></div><br></div></div>_______________________________________________<br>
Openmcl-devel mailing list<br>
<a href="mailto:Openmcl-devel@clozure.com" target="_blank">Openmcl-devel@clozure.com</a><br>
<a href="https://lists.clozure.com/mailman/listinfo/openmcl-devel" rel="noreferrer" target="_blank">https://lists.clozure.com/mailman/listinfo/openmcl-devel</a><br>
</blockquote></div>
</blockquote></div>