public class Comparable 
{
  int val;

  Comparable(int _val) {
    val=_val;
  }

  int compareTo(Comparable other) {
    if (this.val<other.val) {
      return -1;
    } 
    else if (this.val>other.val) {
      return 1;
    } 
    else {
      return 0;
    }
  }
}

public class KdTree
{



  private class KdNode
  {
    Comparable data[ ];
    KdNode     left;
    KdNode     right;

    KdNode( Comparable item[ ] )
    {
      data = new Comparable[ 2 ];
      data[ 0 ] = item[ 0 ];
      data[ 1 ] = item[ 1 ];
      left = right = null;
    }
  }

  private KdNode root;

  public KdTree( )
  {
    root = null;
  }

  public void insert( Comparable [ ] x )
  {
    root = insert( x, root, 0 );
  }

  private KdNode insert( Comparable [ ] x, KdNode t, int level )
  {
    if ( t == null )
      t = new KdNode( x );
    else if ( x[ level ].compareTo( t.data[ level ] ) < 0 )
      t.left = insert( x, t.left, 1 - level );
    else
      t.right = insert( x, t.right, 1 - level );
    return t;
  }

  /**
   * Print items satisfying
   * low[ 0 ] <= x[ 0 ] <= high[ 0 ] and
   * low[ 1 ] <= x[ 1 ] <= high[ 1 ].
   */
  public void printRange( Comparable [ ] low, Comparable [ ] high )
  {
    printRange( low, high, root, 0, 0 );
  }

  private void printRange( Comparable [ ] low, Comparable [ ] high, 
  KdNode t, int level, int depth )
  {
    if ( t != null )
    {
      if ( low[ 0 ].compareTo( t.data[ 0 ] ) <= 0 &&
        low[ 1 ].compareTo( t.data[ 1 ] ) <= 0 &&
        high[ 0 ].compareTo( t.data[ 0 ] ) >= 0 &&
        high[ 1 ].compareTo( t.data[ 1 ] ) >= 0 )
        System.out.println( "(" + t.data[ 0 ].val + ","
          + t.data[ 1 ].val + ") " + depth);

      if ( low[ level ].compareTo( t.data[ level ] ) <= 0 )
        printRange( low, high, t.left, 1 - level, depth+1 );
      if ( high[ level ].compareTo( t.data[ level ] ) >= 0 )
        printRange( low, high, t.right, 1 - level, depth+1);
    }
  }


  public void drawRange( Comparable [ ] low, Comparable [ ] high )
  {
    drawRange( low, high, root, 0 );
  }

  private void drawRange( Comparable [ ] low, Comparable [ ] high, 
  KdNode t, int level )
  {
    if ( t != null )
    {
      if ( low[ 0 ].compareTo( t.data[ 0 ] ) <= 0 &&
        low[ 1 ].compareTo( t.data[ 1 ] ) <= 0 &&
        high[ 0 ].compareTo( t.data[ 0 ] ) >= 0 &&
        high[ 1 ].compareTo( t.data[ 1 ] ) >= 0 ) {

        // System.out.println( "(" + t.data[ 0 ].val + ","
        //   + t.data[ 1 ].val + ")" );
        stroke(255, 0, 0);
        ellipse(t.data[0].val, t.data[1].val, 3, 3);
      } 
      else { 
        stroke(0);
        ellipse(t.data[0].val, t.data[1].val, 3, 3);
      }
      if ( low[ level ].compareTo( t.data[ level ] ) <= 0 )
        drawRange( low, high, t.left, 1 - level );
      if ( high[ level ].compareTo( t.data[ level ] ) >= 0 )
        drawRange( low, high, t.right, 1 - level );
    }
  }


  public void draw()
  {
    draw(root, 0);
  }

  private void draw(KdNode t, int level) {
    if (t != null)
    {
      stroke(0);
      ellipse(t.data[0].val, t.data[1].val, 10, 10);

      draw(t.left, 1-level);
      draw(t.right, 1-level);
    }
  }

  public void drawLeftTraverse() 
  {
    drawLeftTraverse(root, 0);
  }

  private void drawLeftTraverse(KdNode t, int level) {
    if (t != null)
    {
      stroke(0);
      ellipse(t.data[0].val, t.data[1].val, 10, 10);

      draw(t.left, 1-level);
      draw(t.right, 1-level);
    }
  }
}