type pair = {id: int; mutable value: int}
let maxval = 9999
let empty = {id = (-1); value = 0}
exception Empty
    
class sizeheap size = object (self)
  val mutable last = 0
  val array = Array.create (size+1) empty
  val where = Array.create (size+1) 0
  method hprint = Array.map 
      (fun x -> Printf.printf "%d:%d, " x.id x.value)
      (Array.sub array 0 last)
  method move from towards = 
    if from != towards then 
      try 
	where.(array.(from).id) <- towards;
	array.(towards) <- array.(from)
      with x -> Printf.printf "failed moving from %d to %d\n" from towards; 
  method lookminid = if last == 0 then 0 else array.(1).id
  method lookminval = if last == 0 then 0 else array.(1).value
  method sizeof id = array.(where.(id)).value
  method percolate_down startpos =
    let lastval = array.(last).value in 
    let pos = ref startpos in
    while !pos != last do
      let lval = if !pos*2 > last then maxval else array.(!pos*2).value in
      let rval = if !pos*2+1 > last then maxval else array.(!pos*2+1).value in
      if lval >= rval then
	let from = if lval > lastval then last else !pos * 2 in
	self#move from !pos; pos := from
      else 
	let from = if lval > lastval then last else !pos * 2 in
	self#move from !pos; pos := from
    done;
    array.(last) <- empty;
    last <- last - 1
  method percolate_up startpos value =
    let pos = ref startpos in
    while array.(!pos/2).value > value && !pos > 0 do
      self#move (!pos/2) !pos; 
      pos := !pos/2
    done;
    !pos
  method inconsistent = 
    for i=1 to last do 
      let id = array.(i).id in
      assert (where.(id) = i);
    done
  method popmin = if last == 0 then raise Empty else
  let out = array.(1) in
  where.(out.id) <- 0;
  self#percolate_down 1;
  out
  method popmin_id = self#popmin.id
  method insert id value = 
    let record = {id=id; value = value} in
    last <- last + 1;
    let pos = self#percolate_up last value in
    try 
      where.(id) <- pos;
      array.(pos) <- record
    with x -> 
      Printf.printf "failed to insert %d at pos %d\n" id pos
  method decrease id value =
    let pos = where.(id) in
    let oldval = array.(pos).value in
    if oldval > value then begin
      array.(pos).value <- value;
      let elem = array.(pos) in
      let value = elem.value in
      if value > 0 then 
	let finalpos = self#percolate_up pos value in
	array.(finalpos) <- elem;
	where.(id) <- finalpos
      else begin
	where.(id) <- 0;
	self#percolate_down pos
      end;
    end;
  method decrement id =
    self#decrease id (array.(where.(id)).value - 1)
end (*of the sizeheap class*)