// Htree.java
// Robert Sedgewick and Kevin Wayne
// Slightly reformatted by Andrew Davison, Nov. 2022

// https://introcs.cs.princeton.edu/java/23recursion/Htree.java.html

/* Plot an order n H-tree.

   Usage:
     > compile Htree.java
     > run Htree n
   e.g.
     > run Htree 6
*/


public class Htree
{

  public static void main(String[] args)
  {
    if (args.length != 1) {
      System.out.println("Usage: java Htree <depth>");
      System.exit(1);
    }
    int n = Integer.parseInt(args[0]);

    double x = 0.5, y = 0.5;       // center of H-tree
    double size = 0.5;             // side length of H-tree
    draw(n, x, y, size);
  } /* main */


  private static void drawH(double x, double y, double size)
  // plot an H, centered on (x, y) of the given side length
  {
    // compute the coordinates of the 4 tips of the H
    double x0 = x - size/2;
    double x1 = x + size/2;
    double y0 = y - size/2;
    double y1 = y + size/2;

    // draw the 3 line segments of the H
    StdDraw.line(x0, y0, x0, y1);     // left  vertical segment of the H
    StdDraw.line(x1, y0, x1, y1);     // right vertical segment of the H
    StdDraw.line(x0,  y, x1,  y);     // connect two vertical segments
  } /* drawH */


  private static void draw(int n, double x, double y, double size)
  // plot an order n H-tree, centered on (x, y) of the given side length
  {
    if (n == 0)
      return;

    drawH(x, y, size);

    // compute x- and y-coordinates of the 4 half-size H-trees
    double x0 = x - size/2;
    double x1 = x + size/2;
    double y0 = y - size/2;
    double y1 = y + size/2;

    // recursively draw 4 half-size H-trees of order n-1
    draw(n-1, x0, y0, size/2);        // lower left  H-tree
    draw(n-1, x0, y1, size/2);        // upper left  H-tree
    draw(n-1, x1, y0, size/2);        // lower right H-tree
    draw(n-1, x1, y1, size/2);        // upper right H-tree
  } /* draw */


}  // end of Htree class