
 { trp.p
Tue Sep  7 12:58:06 PDT 2004
 }

 program trp(input,output);

#include"strngs"

 { strngs
Sun Sep  5 06:38:08 PDT 2004
 }

  const
   idLen = 3;
   msLen = 10;
   firstLetter = 'A';
   lastLetter = 'Z';

  type
   idType = string[idLen];
   msType = string[msLen];


  var
   idNext:idType;

  function idGetNew:idType;
   var
    result:idType;
    i:integer;
    carry:boolean;
   begin
    result := idNext;
    carry := true;
    for i := idLen downto 1 do if carry then
     begin
      if idNext[i] < lastLetter then
       idNext[i] := succ(idNext[i])
      else
       idNext[i] := firstLetter;
      carry := idNext[i] = firstLetter;
     end;
    idGetNew := result;
   end;

#include"types"

 { types
Tue Sep  7 07:44:44 PDT 2004
 }

  type
   bst = ^bstNode;
   bstNode =
    record
     item:idType;
     left,right:bst;
    end;

   treap = ^treapNode;
   treapNode =
    record
     item:idtype;
     priority:double;
     left,right:treap;
    end;
   
#include"bsts"

 { bsts
Tue Sep  7 07:44:44 PDT 2004
 }

  function bstFind(root:bst; var key:idType):bst;
   begin
    if root = nil then bstFind := nil
    else if root^.item = key then bstFind := root
    else if key < root^.item then bstFind := bstFind(root^.left,key)
    else bstFind := bstFind(root^.right,key);
   end;

  procedure bstInsert(var root:bst; key:idType);
   begin
    if root = nil then
     begin
      new(root);
      root^.item := key;
      root^.left := nil;
      root^.right := nil;
     end
    else if root^.item = key then writeln('Duplicate item not inserted.')
    else if key < root^.item then bstInsert(root^.left,key)
    else bstInsert(root^.right,key);
   end;

  procedure bstRotateLeft(var root:bst);
    {input conditions: root <> nil, root^.right <> nil}
   var
    r,s:bst;
   begin
    if root = nil then writeln('Cannot left rotate')
    else if root^.right = nil then writeln('Cannot left rotate')
    else
     begin
      r := root;
      s := root^.right;
      r^.right := s^.left;
      s^.left := r; 
      root := s;
     end
   end;

  {procedure bstRotate(var root:bst);}

  procedure bstWrite(root:bst;level:integer);
   var
    i:integer;
   begin
    if root <> nil then
     begin
      bstWrite(root^.right,level+1);
      write('':level);writeln(root^.item);
      bstWrite(root^.left,level+1);
     end;
   end;

  procedure itemLoadBst(var root:bst);
   var
    x:idType;
   begin
    root := nil;
    while not eof do
     begin
      readln(x);
      bstInsert(root, x);
     end;
   end;

  function bstCount(root:bst):integer;
   begin
    if root = nil then bstCount := 0
    else bstCount := 1 + bstCount(root^.left)+bstCount(root^.right);
   end;

  function bstTotalPathLength(root:bst; level:integer):integer;
   begin
    if root = nil then bstTotalPathLength := 0
    else bstTotalPathLength := level
                         + bstTotalPathLength(root^.left,level+1)  
                         + bstTotalPathLength(root^.right,level+1);
   end;

  function bstAveragePathLength(root:bst):double;
   begin
    if root = nil then
     bstAveragePathLength := 0
    else
     bstAveragePathLength := bstTotalPathLength(root,0)/bstCount(root);
   end;

  procedure bstDelete(var root:bst; x:idType);
   begin
{writeln('Deleting ',x);}
    if root <> nil then
     if root^.item = x then
      if root^.right = nil then
{begin}
{writeln('root^.right = nil');}
       root := root^.left
{;end}
      else if root^.left = nil then
{begin}
{writeln('root^.left = nil');}
       root := root^.right
{;end}
      else
       begin
{writeln('Start bstRotateLeft');}
        bstRotateLeft(root);
{writeln('Finish bstRotateLeft');}
        bstDelete(root^.left,x);
       end
    else if x < root^.item then bstDelete(root^.left,x)
    else bstDelete(root^.right,x);
{writeln('Deleted ',x);}
   end;
       
#include"treaps"

 { treaps
Tue Sep  7 12:46:27 PDT 2004
Mon Apr  4 04:40:58 PDT 2005
 }

  function treapFind(root:treap; var key:idType):treap; {X}
   begin
    if root = nil then treapFind := nil
    else if root^.item = key then treapFind := root
    else if key < root^.item then treapFind := treapFind(root^.left,key)
    else treapFind := treapFind(root^.right,key);
   end;

  procedure treapRotateLeft(var root:treap); {X}
    {input conditions: root <> nil, root^.right <> nil}
   var
    r,s:treap;
   begin
    if root = nil then writeln('Cannot left rotate')
    else if root^.right = nil then writeln('Cannot left rotate')
    else
     begin
      r := root;
      s := root^.right;
      r^.right := s^.left;
      s^.left := r; 
      root := s;
     end
   end;

  procedure treapRotateRight(var root:treap); {X}
    {input conditions: root <> nil, root^.left <> nil}
   var
    r,s:treap;
   begin
    if root = nil then writeln('Cannot right rotate')
    else if root^.left = nil then writeln('Cannot right rotate')
    else
     begin
      r := root;
      s := root^.left;
      r^.left := s^.right;
      s^.right := r; 
      root := s;
     end
   end;

  procedure treapWrite(root:treap;level:integer);
   var
    i:integer;
   begin
    if root <> nil then
     begin
      treapWrite(root^.right,level+1);
      write('':level);writeln(root^.item,'':27-level,root^.priority:17:14);
      treapWrite(root^.left,level+1);
     end;
   end;

  function treapCount(root:treap):integer;
   begin
    if root = nil then treapCount := 0
    else treapCount := 1 + treapCount(root^.left)+treapCount(root^.right);
   end;

  function treapTotalPathLength(root:treap; level:integer):integer;
   begin
    if root = nil then treapTotalPathLength := 0
    else treapTotalPathLength := level
                         + treapTotalPathLength(root^.left,level+1)  
                         + treapTotalPathLength(root^.right,level+1);
   end;

  function treapAveragePathLength(root:treap):double;
   begin
    if root = nil then
     treapAveragePathLength := 0
    else
     treapAveragePathLength := treapTotalPathLength(root,0)/treapCount(root);
   end;

  procedure treapDelete(var root:treap; x:idType); {X}
   begin
    if root <> nil then
     if root^.item = x then
      if root^.right = nil then
       root := root^.left
      else if root^.left = nil then
       root := root^.right
      else if root^.left^.priority > root^.right^.priority then
       begin
        treapRotateLeft(root);
        treapDelete(root^.left,x);
       end
      else
       begin
        treapRotateRight(root);
        treapDelete(root^.right,x);
       end
    else if x < root^.item then treapDelete(root^.left,x)
    else treapDelete(root^.right,x);
   end;
       
  procedure treapInsert(var root:treap; key:idType); {X}
   begin
    if root = nil then
     begin
      new(root);
      root^.item := key;
      root^.priority := random;
      root^.left := nil;
      root^.right := nil;
     end
    else if root^.item = key then writeln('Duplicate item not inserted.')
    else if key < root^.item then
     begin
      treapInsert(root^.left,key);
      if root^.priority > root^.left^.priority then treapRotateRight(root);
     end
    else
     begin
      treapInsert(root^.right,key);
      if root^.priority > root^.right^.priority then treapRotateLeft(root);
     end
   end;

  procedure itemLoadTreap(var root:treap); {X}
   var
    x:idType;
   begin
    root := nil;
    while not eof do
     begin
      readln(x);
      treapInsert(root, x);
     end;
   end;


  var
   root:treap;
  begin
   writeln('Loading initial data');
   itemLoadTreap(root);   
   treapWrite(root,0);
   writeln('Average path length = ',treapAveragePathLength(root):0:4);
   writeln('Deleting Abe');
   treapDelete(root,'Abe');
   treapWrite(root,0);
   writeln('Average path length = ',treapAveragePathLength(root):0:4);
   writeln('Inserting Tad');
   treapInsert(root,'Tad');
   treapWrite(root,0);
   writeln('Average path length = ',treapAveragePathLength(root):0:4);
  end.

