Module PathVisual.MutBinHeap


module MutBinHeap: sig .. end


Mutable binary heap of (int * int) * int * float using hash table for fast delete
type pos = int * int 
type elt = pos * int * float 
type arrayidx = int 

type t = {
   mutable last : arrayidx;
   mutable arr : elt array;
   hash : arrayidx PathVisual.IntPairHash.t;
   compare : elt -> elt -> int;
}
val get : t ->
arrayidx -> elt
val parent : arrayidx -> arrayidx
Get array index of parent
val left_child : arrayidx -> arrayidx
Get array index of left child
val right_child : arrayidx -> arrayidx
Get array index of right child
val getpos : t ->
PathVisual.IntPairHash.key -> elt
Get element with given pos
val swap : t ->
arrayidx -> arrayidx -> unit
Swaps 2 array indexes
val bubbleup : t -> arrayidx -> unit
val bubbledown : t -> arrayidx -> unit
val make : (elt -> elt -> int) ->
t
Make a new binary heap.
make (fun ((x,y),cost,dist)
         ((x',y'),cost',dist') -> compare ((float cost)
         +. dist) ((float cost') +. dist'))
makes a binary heap comparing cost + distance (A* )
val insert : t -> elt -> unit
Insert element into heap
val remove : t -> PathVisual.IntPairHash.key -> unit
Remove element
((x,y),cost,dist)
where
(x,y) = pos

val replace : t -> elt -> unit
Insert new element or replace existing element with matching first.
replace heap ((2,0),2,3.0)
would replace the existing element
((2,0),3,5.0)
.
val pop : t -> elt
Returns the minimum element and removes it from the heap.