Courses/CS 460/Fall 2005/Notes for Sept 24

From CSWiki

Back to CS 460

We discussed the course website and the Mozart-Oz tutorial through SMerge.

SMerge and Insert are on this page of the tutorial.

[edit] SMerge

Here is the non-nested version of SMerge.

proc {SMerge Xs Ys Zs}
   case Xs#Ys of
      % If Xs is nil then Zs = Ys
      nil#Ys then Zs=Ys
      % If Ys is nil then Zs = Xs
   [] Xs#nil then Zs=Xs
      % Neither Xs nor Ys is nil. So Xs is X|Xr and Ys is Y|Yr.
      % This binds X, Xr, Y, and Yr to the heads and tails of Xs and Ys.
      % The parentheses are needed because # binds more tightly than |.
   [] (X|Xr) # (Y|Yr) then
      Zr in
      if X=<Y then
	 Zs = X|Zr
	 {SMerge Xr Ys Zr}
      else
	 Zs = Y|Zr
	 {SMerge Xs Yr Zr}
      end
   end
end

Here's a version that factors out the call to SMerge and that uses # to bind a number of variables all at once.

proc {SMerge Xs Ys Zs}
   case Xs#Ys of
      nil#Ys then Zs=Ys
   [] Xs#nil then Zs=Xs
   [] (X|Xr) # (Y|Yr) then
      Z Zr XArg YArg in
      Zs = Z | Zr
%     {SMerge XArg YArg Zr}
      if X =< Y then
	 Z#XArg#YArg = X#Xr#Ys
      else
	 Z#XArg#YArg = Y#Xs#Yr
      end
      {SMerge XArg YArg Zr}
   end
end

Note that the call to SMerge must follow the binding of its arguments even though the line that binds Zs may preceed everything. The commented out line that calls SMerge will generate a compiler error. I'm not sure why this is a compiler error rather than a run-time error.

[edit] Insert

In the program Insert, a new tree is created as TreeOut. The tree given as TreeIn is completely unchanged. Verify that by doing a Browse on it both before and after the Insert.

The new tree contains pointers to those parts of the original tree that had not changed. It is new only on the path that contains the node that changes. The new nodes are created with the lines

TreeOut = tree(Key Value T1 T2)

TreeOut = tree(K1 V1 T T2)

TreeOut = tree(K1 V1 T1 T)