// Random Binary Trees
//
// Paul E. Dunne 28/11/07
//
import java.util.*;
public class RandomTrees
  {
  static Random S = new Random();
  //*****************************************************
  // Generate Random Binary Tree (n leaves) from Root Down
  // (as described in lecture notes)
  //******************************************************
  public static BinaryTree RootDown(int n)
    {
    BinaryTree T = new BinaryTree();
    int k;
    T.SetRootValue(n);
    if (n>1)
      {
      k = S.nextInt(n-1) + 1;  // Choose number of leaves in Left
      T.SetLeft(RootDown(k));
      T.SetRight(RootDown(n-k));
      };
    return BinaryTree.LabelTree(T);
    };
  //*****************************************************
  // From Leaf nodes upward
  // (as described in lecture notes)
  //*****************************************************
  public static BinaryTree LeafUp(int n)
    {
    BinaryTree[] T = new BinaryTree[n];
    BinaryTree Temp;
    int m = n;
    int i,j;
    for (int k=0; k<m; k++)
      {
      T[k] = new BinaryTree();
      T[k].SetRootValue(1);
      };
    while (m>1)
      {
      Temp = new BinaryTree();
      j = S.nextInt(m);
      Temp = T[m-1]; T[m-1] = T[j]; T[j] = Temp;
      i = S.nextInt(m-1);
      Temp = new BinaryTree();
      Temp.SetRootValue(m);
      Temp.SetLeft(T[m-1]);
      Temp.SetRight(T[i]);
      T[i] = Temp;
      m--;
      };
    return BinaryTree.LabelTree(T[0]);
    };
 //***************************************************************
 // Uniform Method (from algorithm given in,
 //
 // Generating Binary Trees at Random
 // M.D. Atkinson and J.-R. Sack, Inf. Proc. Lett., 41, pages 21-23, 1992;
 //
 // The variable and method names used in the suite of methods given below
 // are adopted from the notation used in this paper.)
 //
 // Basic approach: generate uniformly at random, a well-formed
 // sequence of 2(n-1) brackets - '(' and ')' - i.e. in which every
 // '(' has a matching ')'. Such sequences map 1-1 to the edges in
 // a binary tree - hence 2n-2 edges = 2n-1 nodes (n leaf nodes + n-1 internal).
 //****************************************************************
 //
 //***************************************************************************
 // Give w (assumed to be well-formed) construct its corresponding binary tree
 //***************************************************************************
 public static BinaryTree ConvertToTree(String w)
   {
   BinaryTree T = new BinaryTree();
   int k = 0;
   if (w.length()==0)
     { 
     T.SetRootValue(1);
     }
   else
     {
     k = BreakPoint(w);
     T.SetRootValue(w.length());
     T.SetLeft( ConvertToTree(w.substring(1,k-1)) );
     T.SetRight( ConvertToTree( w.substring(k,w.length()) ) );
     };
   return T;
   };
 //***********************************************************************
 // Test if the (even length) sequence of '(' and ')' in w is well-formed
 //***********************************************************************
 public static boolean WellFormed(String w)
   {
   int defect = 0;
   int k=0;
   int[] s = new int[w.length()+1];
   s[0]=0;
   for (k=0; k < w.length(); k++)
     {
     if (w.charAt(k)=='(')
       s[k+1] = s[k]+1;
     else
       s[k+1] = s[k]-1;
     };
   for (k=1; k<w.length()+1; k=k+2)
     if (s[k]<0) defect++;
   return (defect==0);
   };
 //*****************************************************************
 // The break point of a string of 2m brackets, w, is the length of a
 // string u, for which w=u.v (concatenation) and is the first point (>0)
 // at which u contains equal numbers of ( and ) brackets; u, of course,
 // is not necessarily well-formed.
 //*****************************************************************
 public static int BreakPoint(String w)
   {
   int x=1;
   int k=0;
   int[] s = new int[w.length()+1];
   s[0]=0;
   for (k=0; k < w.length(); k++)
    {
    if (w.charAt(k)=='(')
      s[k+1] = s[k]+1;
    else
      s[k+1] = s[k]-1;
    };
   while ((x<w.length()+1)&&(s[x]!=0))
     {
     x++;
     };
   return x;
   };
 //*****************************************************************
 // Given w, Split returns the partiton of w in u and v determined by
 // its breakpoint.
 //*****************************************************************
 public static String[] Split(String w)
   {
   String[] uv = new String[2];
   int bp;
   bp = BreakPoint(w);
   uv[0] = w.substring(0,bp);          // The string u.
   uv[1] = w.substring(bp,w.length()); // The string v (w = u.v)
   return uv;
   };
 //*****************************************************************
 // The * operation of Atkinson and Sack (p. 22, paragraph before Lemma 1):
 // given a bracket sequence t, t* replaces each ( in t by ) and vice-versa.
 //*****************************************************************
 public static String FlipBrackets(String t)
   {
   char[] tstar = new char[t.length()];
   for (int i=0; i<t.length(); i++)
    if (t.charAt(i)=='(')
      tstar[i]=')';
    else
      tstar[i]='(';
    return new String(tstar);
   };
 //**************************************************************** 
 // The key mapping defined in Atkinson and Sack (p. 22): any sequence
 // w in which there are the same number of '(' brackets as ')' can be
 // mapped to a unique well-formed sequence Phi(w) of the same length.
 //********************************************************************
 public static String PhiMap(String w)
   {
   String[] uv = new String[2];
   String t;
   String y,z;
   char[] temp;
   if (w.length()==0)
     z = "";
   else
     {
     uv = Split(w);
     if (WellFormed(uv[0]))
       {
       z = uv[0].concat(PhiMap(uv[1]));
       }
     else
       {
       t = FlipBrackets(uv[0].substring(1,uv[0].length()-1));
       y = "(".concat(PhiMap(uv[1]));
       z = y.concat(")".concat(t));
       };
     }
   return z;
   };
 //**************************************************************** 
 // The main Uniform binary tree generator
 //**************************************************************** 
 public static BinaryTree UniformTree(int n)
   {
   BinaryTree T = new BinaryTree();
   int[] Base = new int[2*n-2];
   int[] L = new int[n-1];
   boolean[] y = new boolean[2*n-1];
   char[] x = new char[2*n-2];
   String w,z;
   int m=0;
   int t=2*n-3;
   int k;
   //****************************************************************************
   // Step 1: Choose Random combinationi, L, of n-1 values from 2(n-1)
   // {1,2,3,....,2(n-1)} values
   // and
   // Step 2: Map this combination to Boolean sequence y(1),...y(2n-2)
   //         using, y(i)=true if i was chosen; y(i)=false otherwise
   //****************************************************************************
   for (int i=0; i<2*n-2; i++)
     {
     Base[i] = i+1;
     y[i+1] = false;
     };
   while (m<n-1)
     {
     k = S.nextInt(t+1);
     L[m] = Base[k]; Base[k] = Base[t];
     y[L[m]] = true; 
     m++; t--;
     };
   //****************************************************************************
   // Final part of Step 2: form a sequence of '(' and ')' from y(1),...,y(2n-2)
   //****************************************************************************
   for (int i=0; i<2*n-2; i++)
     if (y[i+1])
       x[i] = '(';
     else
       x[i]=')';
   w = new String(x);
   //************************************************************************
   // Step 3: Map w to its corresponding well-formed bracket sequence \Phi(w)
   //************************************************************************
   z = PhiMap(w);
   return(BinaryTree.LabelTree(ConvertToTree(z)));
   };
 }