About CLRS The following Oz code is derived from the examples provided in the book:
"Introduction To Algorithms, Second Edition" by Thomas H. Corman, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein.
http://mitpress.mit.edu/algorithms/

 ```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}} ```

Chris Rathman / Chris.Rathman@tx.rr.com