Chapter #10 Examples in Oz

% Utility functions
fun {RandomInt Min Max}
   X = {OS.rand}
   MinOS
   MaxOS
in
   {OS.randLimits ?MinOS ?MaxOS}
   Min + X*(Max - Min) div (MaxOS - MinOS)
end

{OS.srand 0}

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

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

% 10.1 Stacks
fun {MakeStack MaxStack}
   stack(data:{NewArray 0 MaxStack-1 _} top:{NewCell 0})
end

fun {StackEmpty S}
   if @(S.top) == 0 then
      true
   else
      false
   end
end

proc {Push S X}
   (S.top) := @(S.top) + 1
   (S.data).(@(S.top)) := X
end

fun {Pop S}
   if {StackEmpty S} then
      raise "underflow" end
   else
      (S.top) := @(S.top) - 1
      (S.data).(@(S.top)+1)
   end
end

local
   S = {MakeStack 100}
in
   {Push S 1234}
   {Push S 5678}
   {Browse 'Stack'#{Pop S}}
   {Browse 'Stack'#{Pop S}}
end

% 10.1 Queues
fun {MakeQueue MaxQueue}
   queue(data:{NewArray 0 MaxQueue-1 _} head:{NewCell 1} tail:{NewCell 1})
end

proc {Enqueue Q X}
   Q.data.(@(Q.tail)) := X
   if @(Q.tail) == {Array.high Q.data} then
      (Q.tail) := 1
   else
      (Q.tail) := @(Q.tail) + 1
   end
end

fun {Dequeue Q}
   X = Q.data.(@(Q.head))
   Q.data.(@(Q.head)) = _
in
   if @(Q.head) == {Array.high Q.data} then
      (Q.head) := 1
   else
      (Q.head) := @(Q.head) + 1
   end
   X
end

local
   Q = {MakeQueue 100}
in
   {Enqueue Q 1234}
   {Enqueue Q 5678}
   {Browse 'Queue'#{Dequeue Q}}
   {Browse 'Queue'#{Dequeue Q}}
end

% 10.2 Linked Lists
fun {MakeLinkedList}
   linkedlist(head:{NewCell nil})
end

fun {MakeLinkedListNode K X}
   linkedlistnode(key:K data:X next:{NewCell nil} prev:{NewCell nil})
end

fun {ListSearch L K}
   X = {NewCell @(L.head)}
in
   {While
      fun {$} @X \= nil andthen @X.key \= K end
      proc {$} X := @(@X.next) end}
   @X
end

proc {ListInsert L X}
   (X.next) := @(L.head)
   if @(L.head) \= nil then
      (@(L.head).prev) := X
   end
   (L.head) := X
   (X.prev) := nil
end

proc {ListDelete L X}
   if @(X.prev) \= nil then
      (@(X.prev).next) := @(X.next)
   else
      (L.head) := @(X.next)
   end
   if @(X.next) \= nil then
      (@(X.next).prev) := @(X.prev)
   end
end

local
   L = {MakeLinkedList}
in
   {ListInsert L {MakeLinkedListNode 1 1234}}
   {ListInsert L {MakeLinkedListNode 2 3456}}
   {ListInsert L {MakeLinkedListNode 3 5678}}
   {ListDelete L {ListSearch L 2}}
   {Browse 'LinkedList'#{ListSearch L 1}}
   {Browse 'LinkedList'#{ListSearch L 3}}
   {Browse 'LinkedList'#{ListSearch L 2}}
end

% 10.2 Linked List with sentinel
fun {MakeSentinelLinkedList}
   Sentinel = null(next:{NewCell _} prev:{NewCell _})
in
   (Sentinel.next) := Sentinel
   (Sentinel.prev) := Sentinel
   sentinallinkedlist(sentinel:Sentinel)
end

fun {SentinelListSearch L K}
  X = {NewCell @((L.sentinel).next)}
in
   {While
      fun {$} @X \= L.sentinel andthen @X.key \= K end
      proc {$} X := @(@X.next) end}
   @X
end

proc {SentinelListInsert L X}
   (X.next) := @((L.sentinel).next)
   (@((L.sentinel).next).prev) := X
   ((L.sentinel).next) := X
   (X.prev) := L.sentinel
end

proc {SentinelListDelete L X}
   (@(X.prev).next) := @(X.next)
   (@(X.next).prev) := @(X.prev)
end

local
   L = {MakeSentinelLinkedList}
in
   {SentinelListInsert L {MakeLinkedListNode 1 1234}}
   {SentinelListInsert L {MakeLinkedListNode 2 3456}}
   {SentinelListInsert L {MakeLinkedListNode 3 5678}}
   {SentinelListDelete L {SentinelListSearch L 2}}
   {Browse 'SentinelLinkedList'#{SentinelListSearch L 1}}
   {Browse 'SentinelLinkedList'#{SentinelListSearch L 3}}
   {Browse 'SentinelLinkedList'#{SentinelListSearch L 2}}
end

% 10.3 Pointers
Free = {NewCell 0}
Next = {NewArray 0 10 _}
Key = {NewArray 0 10 _}
Prev = {NewArray 0 10 _}

proc {InitObject}
   for I in {Array.low Next}..({Array.high Next}-1) do
      Next.I := I + 1
   end
end

{InitObject}

fun {AllocateObject}
   if @Free == nil then
      raise error('out of stack space') end
   else
      local
         X = @Free
      in
         Free := Next.X
         X
      end
   end
end

proc {FreeObject X}
   Next.X := @Free
   Free := X
end

L = {NewCell {AllocateObject}}
Next.@L := {AllocateObject}
Prev.@L := nil
Key.@L := 10
Next.(Next.@L) := {AllocateObject}
Prev.(Next.@L) := @L
Key.(Next.@L) := 20

Next.(Next.(Next.@L)) := nil
Prev.(Next.(Next.@L)) := @L
Key.(Next.(Next.@L)) := 30

{Browse 'Pointers'#Key.@L#Key.(Next.@L)#@Free}

% 10.4 Compact List Search
fun {CompactListSearch L N K}
   Return = {NewCell nil}
   I = {NewCell L}
in
   {While
      fun {$} @Return == nil andthen @I \= nil andthen Key.@I < K end
      proc {$}
         J = {NewCell {RandomInt 0 N}}
      in
         if Key.@I < Key.@J andthen Key.K =< K then
            I := @J
            if Key.@I == K then
               Return := @I
            else
               I := Next.@I
            end
         else
            I := Next.@I
         end
      end}
   if @Return \= nil then
      @Return
   elseif @I == nil orelse Key.@I > K then
      nil
   else
      @I
   end
end

{Browse 'CompactListSearch'#{CompactListSearch @L 2 20}}

% 10.4 Compact List Search'
fun {CompactListSearch_ L N K T}
   Return = {NewCell nil}
   I = {NewCell L}
in
   for Q in 1..T do
      local
         J = {RandomInt 0 N}
      in
         if @Return == nil andthen Key.@I < Key.J andthen Key.J =< K then
            I := J
            if Key.@I == K then
               Return := @I
            end
         end
      end
   end
   if @Return \= nil then
      @Return
   else
      {While
         fun {$} @I \= nil andthen Key.@I < K end
         proc {$}
            I := Next.@I
         end}
      if @I == nil orelse Key.@I > K then
         nil
      else
         @I
      end
   end
end

{Browse 'CompactListSearch_'#{CompactListSearch_ @L 2 20 5}}