<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=ISO-8859-1">
</head>
<body text="#000000" bgcolor="#FFFFFF">
Hello, <br>
<br>
Playing with the cl-containers and the heap implementation I come
across what looks like two bugs in heaps.lisp:<br>
<br>
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.<br>
<br>
2/ it looks like node-parent-index is incorrect as you use 0 based
indexes:<br>
<br>
It says:<br>
<br>
(defmethod node-parent-index ((node heap-node))<br>
(ash (index node) -1))<br>
<br>
But it should be<br>
<br>
(defmethod node-parent-index ((node heap-node))<br>
(ash (1- (index node)) -1))<br>
<br>
<br>
This is easy to test if you look at the result of <br>
<br>
(node-parent-index (r-child-index 0))<br>
<br>
It should be 0 but returns 1.<br>
<br>
The formula for parent node index using 0 based indexes is
documented in wikipedia:
<a class="moz-txt-link-freetext" href="http://en.wikipedia.org/wiki/Binary_heap#Heap_implementation">http://en.wikipedia.org/wiki/Binary_heap#Heap_implementation</a>. It is
<span style="color: rgb(0, 0, 0); font-family: sans-serif;
font-size: 13px; font-style: normal; font-variant: normal;
font-weight: normal; letter-spacing: normal; line-height:
19.200000762939453px; orphans: 2; text-align: left; text-indent:
0px; text-transform: none; white-space: normal; widows: 2;
word-spacing: 0px; -webkit-text-size-adjust: auto;
-webkit-text-stroke-width: 0px; background-color: rgb(255, 255,
255); display: inline !important; float: none;">parent<span
class="Apple-converted-space"> </span></span><i style="color:
rgb(0, 0, 0); font-family: sans-serif; font-size: 13px;
font-variant: normal; font-weight: normal; letter-spacing: normal;
line-height: 19.200000762939453px; orphans: 2; text-align: left;
text-indent: 0px; text-transform: none; white-space: normal;
widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto;
-webkit-text-stroke-width: 0px; background-color: rgb(255, 255,
255);">= a</i><span style="color: rgb(0, 0, 0); font-family:
sans-serif; font-size: 13px; font-style: normal; font-variant:
normal; font-weight: normal; letter-spacing: normal; line-height:
19.200000762939453px; orphans: 2; text-align: left; text-indent:
0px; text-transform: none; white-space: normal; widows: 2;
word-spacing: 0px; -webkit-text-size-adjust: auto;
-webkit-text-stroke-width: 0px; background-color: rgb(255, 255,
255); display: inline !important; float: none;">[</span>floor<span
style="color: rgb(0, 0, 0); font-family: sans-serif; font-size:
13px; font-style: normal; font-variant: normal; font-weight:
normal; letter-spacing: normal; line-height: 19.200000762939453px;
orphans: 2; text-align: left; text-indent: 0px; text-transform:
none; white-space: normal; widows: 2; word-spacing: 0px;
-webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px;
background-color: rgb(255, 255, 255); display: inline !important;
float: none;">((</span><i style="color: rgb(0, 0, 0); font-family:
sans-serif; font-size: 13px; font-variant: normal; font-weight:
normal; letter-spacing: normal; line-height: 19.200000762939453px;
orphans: 2; text-align: left; text-indent: 0px; text-transform:
none; white-space: normal; widows: 2; word-spacing: 0px;
-webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px;
background-color: rgb(255, 255, 255);">i</i><span style="color:
rgb(0, 0, 0); font-family: sans-serif; font-size: 13px;
font-style: normal; font-variant: normal; font-weight: normal;
letter-spacing: normal; line-height: 19.200000762939453px;
orphans: 2; text-align: left; text-indent: 0px; text-transform:
none; white-space: normal; widows: 2; word-spacing: 0px;
-webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px;
background-color: rgb(255, 255, 255); display: inline !important;
float: none;">−1)/2)]</span><br>
<br>
This causes some subtle bugs, harder to catch.<br>
<br>
I attach two tests in a file.<br>
<br>
Regards,<br>
Cosmin<br>
</body>
</html>