Chapter #11 Examples in Oz

% Utility functions
proc {While Expr Stmt}
   if {Expr} then {Stmt} {While Expr Stmt} end
end

proc {RepeatUntil Stmt Expr}
   {Stmt}
   if {Not {Expr}} then {RepeatUntil Stmt Expr} end
end

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

% 11.1 DirectAddress Table
fun {DirectAddressSearch T Key}
   T.Key
end

proc {DirectAddressInsert T X=Value#Key}
   T.Key := Value
end

proc {DirectAddressDelete T X=_#Key}
   T.Key := nil
end

local
   T = {Tuple.toArray nil#nil#nil#nil#nil}
in
   {DirectAddressInsert T 10#1}
   {DirectAddressInsert T 20#2}
   {DirectAddressInsert T 30#3}
   {DirectAddressInsert T 40#4}
   {DirectAddressInsert T 50#5}
   {Browse 'DirectAddressSearch'#{DirectAddressSearch T 1}}
   {DirectAddressDelete T _#1}
   {Browse 'DirectAddressSearch'#{DirectAddressSearch T 1}}
end

% 11.2 ChainedHashInsert
fun {SillyHash X}
   case X
   of a then 1
   [] b then 1
   [] c then 1
   [] d then 2
   [] e then 2
   end
end

proc {ChainedHashInsert T X=Value#Key}
   I = {SillyHash Key}
in
   if T.I == nil then
      T.I := {MakeLinkedList}
   elseif {ListSearch T.I Key} \= nil then
      {ChainedHashDelete T X}
   end
   {ListInsert T.I {MakeLinkedListNode Key Value}}
end

fun {ChainedHashSearch T Key}
   I = {SillyHash Key}
in
   if T.I == nil then
      nil
   else
      case {ListSearch T.I Key}
      of linkedlistnode(data:Value key:_ next:_ prev:_) then Value
      else nil
      end
   end
end

proc {ChainedHashDelete T X=Value#Key}
   I = {SillyHash Key}
in
   {ListDelete T.I {ListSearch T.I Key}}
end

local
   T = {Tuple.toArray nil#nil#nil#nil#nil}
in
   {ChainedHashInsert T 10#a}
   {ChainedHashInsert T 20#b}
   {ChainedHashInsert T 30#c}
   {ChainedHashInsert T 40#d}
   {ChainedHashInsert T 50#e}
   {Browse 'ChainedHashSearch'#{ChainedHashSearch T a}}
   {ChainedHashDelete T _#a}
   {ChainedHashDelete T _#b}
   {ChainedHashInsert T 15#a}
   {Browse 'ChainedHashSearch'#{ChainedHashSearch T a}}
   {Browse 'ChainedHashSearch'#{ChainedHashSearch T b}}
   {Browse 'ChainedHashSearch'#{ChainedHashSearch T c}}
end

% 11.3 Division Hash
fun {DivisionHash K M}
   K mod M
end

% 11.3 Multiplication Hash
fun {IsPowerOf2 N}
   {BitAnd N N-1} == 0
end

fun {BitAnd X Y}
   case X#Y
   of 0#_ then 0
   [] _#0 then 0
   else
      2 * {BitAnd (X div 2) (Y div 2)} +
         if X mod 2 == Y mod 2 then X mod 2 else 0 end
   end
end

fun {ShiftRight X N}
   X div {Pow 2 N}
end

fun {MultiplicationHash K Size}
   if {IsPowerOf2 Size} then
      local
         R = 2654435769 * K
         ShiftAmount
         BitMask = Size - 1
      in
         {BitAnd {ShiftRight R ShiftAmount} BitMask}
      end
   else
      local
         Multiplier = 0.6180339887
         X
         %double x = o.hashCode() * MULTIPLIER;
      in
         %x -= Math.floor(x); // take the fractional part
         %x *= tableSize;  // multiply by the table size
         {FloatToInt X}
      end
   end
end

% 11.4 Hash
M = 100
fun {Hash K I}
   _
end
fun {HashInsert T K}
   Return = {NewCell nil}
   I = {NewCell 0}
in
   {RepeatUntil
      proc {$}
         J = {Hash K I}
      in
         if T.J == nil then
            T.J := K
            Return := J
         else
            I := @I + 1
         end
      end
      fun {$} @Return \= nil orelse @I == M end}
   if @Return \= nil then
      @Return
   else
      raise error('hash table overflow') end
   end
end

fun {HashSearch T K}
   Return = {NewCell nil}
   I = {NewCell 0}
   J = {NewCell _}
in
   {RepeatUntil
      proc {$}
         J := {Hash K I}
         if T.@J == K then
            Return := J
         else
            I := @I + 1
         end
      end
      fun {$} @Return \= nil orelse T.@J == nil orelse I == M end}
   @Return
end