Chapter #2 Examples in Oz

% Utility functions
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

% 2.1 Insertion Sort
proc {InsertionSort A}
   for J in 2..{Array.high A} do
      local
         Key = A.J
         I = {NewCell J-1}
      in
         {While
            fun {$} @I > 0 andthen A.@I > Key end
            proc {$}
               A.(@I+1) := A.@I
               I := @I - 1
            end}
         A.(@I+1) := Key
      end
   end
end

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

% 2.2 Selection Sort
proc {SelectionSort A}
   N = {Array.high A}
in
   for J in 1..(N-1) do
      local
         Smallest = {NewCell J}
      in
         for I in (J+1)..N do
            if A.I < A.@Smallest then
               Smallest := I
            end
         end
         {ArrayExchange A J @Smallest}
      end
   end
end

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

% 2.3 Merge Sort
proc {Merge A P Q R}
   N1 = Q - P + 1
   N2 = R - Q
   Left = {NewArray 1 N1+1 _}
   Right = {NewArray 1 N2+1 _}
in
   for I in 1..N1 do
      Left.I := A.(P+I-1)
   end
   for J in 1..N2 do
      Right.J := A.(Q+J)
   end
   Left.(N1+1) := undefined
   Right.(N2+1) := undefined
   local
      I = {NewCell 1}
      J = {NewCell 1}
   in
      for K in P..R do
         if Right.@J == undefined orelse
            (Left.@I \= undefined andthen Left.@I =< Right.@J) then
            A.K := Left.@I
            I := @I + 1
         else
            A.K := Right.@J
            J := @J + 1
         end
      end
   end
end

proc {MergeSort A P R}
   if P < R then
      local
         Q = (P + R) div 2
      in
         {MergeSort A P Q}
         {MergeSort A Q+1 R}
         {Merge A P Q R}
      end
   end
end

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

% 2.3 Bubble Sort
proc {BubbleSort A}
   for I in 1..{Array.high A} do
      {For {Array.high A} I+1 ~1
         proc {$ J}
            if A.J < A.(J-1) then
               {ArrayExchange A J J-1}
            end
         end}
   end
end

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

% 2.3 Iterative Binary Search
fun {IterativeBinarySearch A V Low High}
   Return = {NewCell nil}
in
   {While
      fun {$} @Return == nil andthen @Low =< @High end
      proc {$}
         Mid = (@Low + @High) div 2
      in
         if V == A.Mid then
            Return := Mid
         elseif V > A.Mid then
            Low := Mid + 1
         else
            High := Mid - 1
         end
      end}
   @Return
end

local
   A  = {Tuple.toArray 10#20#30#40#50#60}
   Low = {NewCell {Array.low A}}
   High = {NewCell {Array.high A}}
in
   {Browse 'IterativeBinarySearch'#{IterativeBinarySearch A 40 Low High}}
end

% 2.3 Recursive Binary Search
fun {RecursiveBinarySearch A V Low High}
   if Low > High then
      nil
   else
      local
         Mid = (Low + High) div 2
      in
         if V == A.Mid then
            Mid
         elseif V > A.Mid then
            {RecursiveBinarySearch A V Mid+1 High}
         else
            {RecursiveBinarySearch A V Low Mid-1}
         end
      end
   end
end

local
   A  = {Tuple.toArray 10#20#30#40#50#60}
   Low = {Array.low A}
   High = {Array.high A}
in
   {Browse 'RecursiveBinarySearch'#{RecursiveBinarySearch A 40 Low High}}
end