[cl-containers-devel] Two bugs in heaps.lisp

[Cosmin Marian]

Hello,

I don't really work with git so I don't know how to submit a patch via 
github.
But attached is the result of "git diff" command. Hope it helps. If not, 
let me know, I will try to look into github.

Kind regards,
Cosmin

On 20/12/2012 20:23, Gary King wrote:
> Would you be able to submit a patch via github?
>
>> Playing with the cl-containers and the heap implementation I come 
>> across what looks like two bugs in heaps.lisp:
>>
>> 1/ delete-item/sift does not use the key of the elements stored in 
>> the heap in order to compare them. This is easy to see in the source 
>> code.
>>
>> 2/ it looks like node-parent-index is incorrect as you use 0 based 
>> indexes:
> [...]

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.common-lisp.net/pipermail/cl-containers-devel/attachments/20121221/0f65af99/attachment.html>
-------------- next part --------------
diff --git a/dev/heaps.lisp b/dev/heaps.lisp
index 30fa301..c62e234 100644
--- a/dev/heaps.lisp
+++ b/dev/heaps.lisp
@@ -41,7 +41,7 @@
 
 
 (defmethod node-parent-index ((node heap-node))
-  (ash (index node) -1))
+  (ash (1- (index node)) -1))
 
 
 (defmethod exchange-heap-nodes ((n1 heap-node) (n2 heap-node) (heap heap-container))
@@ -103,9 +103,10 @@
 (defmethod delete-item ((heap heap-container) (node heap-node))
   (labels ((sift (node)
              (when (and (/= 0 (index node))
-                        (funcall (sorter heap) 
-                                 (element node) (element (heap-node-parent node heap))))
-               (exchange-heap-nodes node (heap-node-parent node heap) heap)
+			(funcall (sorter heap)
+				 (funcall (key heap) (element node))
+				 (funcall (key heap) (element (heap-node-parent node heap)))))
+	       (exchange-heap-nodes node (heap-node-parent node heap) heap)
                (sift node))))
     (let ((last (last-item heap))
           (key (key heap)))