CGAL users discussion list

[Matt Johnson <>]

Ping?

On 03/21/2012 03:31 PM, mrj10 wrote:
> I was looking at Interval_skip_list.h and noticed what I think might be a bug
> in adjustMarkersOnDelete().  Many places in the code need to do special-case
> check to see if the source or sink of an ISL edge is the ISL header or
> footer, but this check is not done in the if statement on line 860 (in CGAL
> 4.0).  The check is currently:
>
> if(x->forward[i]==0 ||
>    !m->getInterval()->contains_interval(update[i]->key, x->forward[i]->key))
> {
>      newDemoted.insert(m->getInterval());
> }
>
> If update[i] is the header, update[i]->key will be garbage (we don't
> initialize the header's key in the ISL constructor), so the
> contains_interval() call may do something unexpected.  It seems like the
> check should be:
>
> if(x->forward[i]==0 ||
>    isHeader(update[i]) ||
>    !m->getInterval()->contains_interval(update[i]->key, x->forward[i]->key))
> {
>      newDemoted.insert(m->getInterval());
> }
>
> The implementation is very clever in other places, so it's entirely possible
> I may have missed an invariant that makes this check unnecessary, but I've
> run into bugs where edges from the header have markers on them, and they
> appear to be caused by a bad result from this check.
>
> Best,
> Matt
>
> --
> View this message in context: 
> http://cgal-discuss.949826.n4.nabble.com/Interval-Skip-List-bug-tp4493660p4493660.html
> Sent from the cgal-discuss mailing list archive at Nabble.com.