Chapter #6 Examples in Oz

% Utility functions
% Oz doesn't have a max int, so we'll just fake one for now
Infinity = {Pow 2 31}

proc {While Expr Stmt}
   if {Expr} then {Stmt} {While Expr Stmt} end
end

proc {ArrayExchange A I J}
   X = A.I
in
   A.I := A.J
   A.J := X
end

% 6.1 Heap helpers
fun {Parent I} I div 2 end
fun {Left I} 2*I end
fun {Right I} 2*I + 1 end

% 6.2 Max-Heapify
% Note: the book makes HeapSize an attribute.  For the examples here, it will be a parameter.
proc {MaxHeapify A I HeapSize}
   L = {Left I}
   R = {Right I}
   Largest = {NewCell _}
in
   if L =< @HeapSize andthen A.L > A.I then
      Largest := L
   else
      Largest := I
   end
   if R =< @HeapSize andthen A.R > A.@Largest then
      Largest := R
   end
   if @Largest \= I then
      {ArrayExchange A I @Largest}
      {MaxHeapify A @Largest HeapSize}
   end
end

% 6.3 Build-Max-Heap
proc {BuildMaxHeap A HeapSize}
   HeapSize := {Array.high A}
   {For {Array.high A} div 2 1 ~1
      proc {$ I}
         {MaxHeapify A I HeapSize}
      end}
end

% 6.4 Heap Sort
proc {HeapSort A}
   HeapSize = {NewCell _}
in
   {BuildMaxHeap A HeapSize}
   {For {Array.high A} 2 ~1
      proc {$ I}
         {ArrayExchange A 1 I}
         HeapSize := @HeapSize - 1
         {MaxHeapify A 1 HeapSize}
      end}
end

local
   A  = {Tuple.toArray 5#2#4#6#1#3}
in
   {HeapSort A}
   {Browse 'HeapSort'#{Array.toRecord '#' A}}
end

% 6.5 Priority Queues  (Note: Oz Arrays can not grow in size dynamically)
fun {HeapMaximum A}
   A.1
end

fun {HeapExtractMax A HeapSize}
   if @HeapSize < 1 then
      raise "heap underflow" end
   end
   local
      Max = A.1
   in
      A.1 := A.@HeapSize
      HeapSize := @HeapSize - 1
      {MaxHeapify A 1 HeapSize}
      Max
   end
end

proc {HeapIncreaseKey A I Key}
   I = {NewCell @I}
in
   if Key < A.@I then
      raise "new key is smaller than current key" end
   end
   A.@I := Key

   {While
      fun {$} @I > 1 andthen A.{Parent @I} < A.@I end
      proc {$}
         {ArrayExchange A @I {Parent @I}}
         I := {Parent @I}
      end}
end

proc {MaxHeapInsert A Key HeapSize}
   HeapSize := @HeapSize + 1
   A.@HeapSize := ~Infinity
   {HeapIncreaseKey A HeapSize Key}
end