{
# DEBUG a stats variable
my $_hheap_maxsize = -1;

# the hashed-heap.
# elements of the binary heap are three-elt arrays of:
#   d: the closest distance (the key of the heap),
#   q: the point (the key of the hash),
#   p: the other point it is close from.
# the hash has the points as its keys,
#   and the indices in the heap as their value.

# hheap_init is a private function that creates a hash-heap
sub hheap_init {
 [{}, []];
}

# hheap_dec is a private function that inserts or moves down an element in the heap.
# if the new distance is greater than the existing one, nothing happens.
sub hheap_dec {
 my($hheap, $d, $q, $p) = @_;
 my($hash, $heap) = @$hheap;
 #warn "[D120 hheap_dec $d, $q, $p]";
 my($k, $kk);
 if (!exists($$hash{$q})) { # new element, insert it
  $k = @$heap;
 } else {
  $k = $$hash{$q};
  ${$$heap[$k]}[0] <= $d and # no improvement, do nothing
   return;
  # improvement, change it
 }
 # gravitate it down
 while (0 < $k && $d < ${$$heap[$kk = ($k - 1) >> 1]}[0]) {
  $$heap[$k] = $$heap[$kk];
  $$hash{${$$heap[$k]}[1]} = $k;
  $k = $kk;
 }
 # do the actual change
 $$heap[$k] = [$d, $q, $p];
 $$hash{$q} = $k;
 #warn "[D130]";
}

# hheap_pop is a private function for popping the element 
# of the smallest distance (minimal d) from the heap.
# returns the empty list if the heap is empty.
sub hheap_pop {
 #warn "[D220 hheap_pop]";
 my($hheap) = @_;
 my($hash, $heap) = @$hheap;
 my(@r, $m, $k, $j, $t, $d);
 @$heap or
  return;
 $k = 0;
 @r = @{$$heap[$k]};
 delete($$hash{$r[1]});
 $t = pop @$heap;
 $d = $$t[0];
 $m = @$heap or
  return @r;
 {
  $j = ($k << 1) + 1;
  $j < $m or
   last;
  $j + 1 < $m &&
   ${$$heap[$j + 1]}[0] <= ${$$heap[$j]}[0] and
   $j = $j + 1;
  ${$$heap[$j]}[0] < $d and do {
   $$heap[$k] = $$heap[$j];
   $$hash{${$$heap[$k]}[1]} = $k;
   $k = $j;
   redo;
  };
 }
 $$heap[$k] = $t;
 $$hash{$$t[1]} = $k;
 #warn "[D230 @r, $k @$t]";
 @r;
}

# a private debugging function
sub hheap_verify {
 if (0) { # DEBUG
  my($e, $s);
  eval {
   $s = hheap_verify1(@_);
  };
  $e = $@ and do {
   require Dumpvalue;
   $|++;
   Dumpvalue->new->dumpValues([$e, @_, $_hheap_maxsize]);
   die $e;
  };
  $_hheap_maxsize < $s and
   $_hheap_maxsize = $s;
 }
}
sub hheap_verify1 {
 #warn "[D320 hheap_verify]";
 my($hheap) = @_;
 my($hash, $heap) = @$hheap;
 my($k);
 keys(%$hash) == @$heap or
  die "assertion failed: hheap size mismatch: hash " . keys(%$hash) . ", heap " . @$heap;
 for $k (0 .. @$heap - 1) {
  ref($$heap[$k]) eq "ARRAY" or
   die "assertion failed: non-array heap element index " . $k;
  exists($$hash{${$$heap[$k]}[1]}) or
   warn("assertion failed: hheap element missing from hash: "), die "index " . $k . ", element " . ${$$heap[$k]}[1] . ", distance " . ${$$heap[$k]}[0];
  $k == $$hash{${$$heap[$k]}[1]} or
   warn("assertion failed: hheap index mismatch: "), die "    real index " . $k . ", element " . ${$$heap[$k]}[1] . ", hash value " . $$hash{${$$heap[$k]}[1]};
 }
 for $k (1 .. @$heap - 1) {
  ${$$heap[($k - 1) >> 1]}[0] <= ${$$heap[$k]}[0] or
   warn("assertion failed: hheap heap mismatch: "), die "parent index " . $k . ", element " . ${$$heap[$k]}[1] . ", distance " . ${$$heap[$k]}[0] .
    ", child index " . (($k - 1) >> 1) . ", element " . ${$$heap[($k - 1) >> 1]}[1] . ", distance " . ${$$heap[($k - 1) >> 1]}[0];
 }
 #warn "[D330]";
 0 + @$heap;
}

}