[cl-containers-devel] darcs patch: When searching for an item in a bst, make sure that th...

[Nathan Bird]

On 3/6/2009 5:03 PM, Gary King wrote:
> Thanks Nathan,
>
> I'll look try at this over the weekend.
>
>
> On Mar 6, 2009, at 2:51 PM, Nathan Bird wrote:
>
>> On 3/6/2009 12:10 PM, Nathan Bird wrote:
>>> Fri Mar  6 11:52:50 EST 2009  Nathan Bird<nathan at acceleration.net>
>>>   * When searching for an item in a bst, make sure that the node 
>>> isn't a placeholder and actually has an element
>>>
>> The point of this is that because the red black tree has empty nodes as
>> placeholders we need to test for that. Without this searching a red
>> black tree for an element it doesn't contain doesn't return null, but
>> errors.
>>
>>> (containers:item-at (containers:make-container
>> 'containers:red-black-tree) 1)
>>
>> Alternatively to testing the element slot directly, there appears to be
>> a node-empty-p function that might be more appropriate.
I made a patch that uses the node-empty-p function instead, as well as a 
patch that adds a bunch of tests on the red-black and binary-search 
trees. Removed the tests/misc.lisp file in which all the code was 
commented out; what was in there is now one of the tests in trees.lisp 
(fixed up a bit).


-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: trees.dpatch
URL: <https://mailman.common-lisp.net/pipermail/cl-containers-devel/attachments/20090307/135aa69b/attachment.ksh>