[cl-containers-devel] Bug in PREDECESSOR?

[Kai Kaminski]

Hi Gary,

first of all I'd like to thank you for your amazing work. I'm just
blown away by the scope and quality.

The potential bug I'm referring to manifests itself when calling
PREDECESSOR for an item that can't be found in the container (say a
binary search tree). In that case the method for

  (PREDECESSOR CONTAINER-USES-NODES-MIXIN T)

is called (that's ok), which in turn calls SEARCH-FOR-NODE. That call
returns NIL, since the item can't be found, which leads to another
call to (PREDECESSOR CONTAINER-USES-NODES-MIXIN T).

Calling PREDECESSOR for an item that's not in the container might not
make much sense, but I believe that it shouldn't hang. I would have
sent you a patch, but I'm not sure how to fix this, because I'm not
sure what PREDECESSOR should do: signal a condition or return NIL.

The same behaviour affects SUCCESSOR.

I tried to write a LIFT testcase, but my LIFT doesn't seem to
understand the :TIMEOUT clause.


Thanks again,

Kai