// Includes key range traversal and ranking for red-black tree, besides
// insertion as in Sedgewick.  Uses subtree sizes rather than root ranks
// for subtrees.

public class topdownRB
{
  private class Node
  {
    ITEM item;
    Node l, r;
    boolean cbit;
    int subtreeSize;  // Used for rank queries

    Node(ITEM x, boolean bit)
    {
      item = x;
      cbit=bit;
      subtreeSize=1;  // A new node is the only node in subtree
    }
  }

  private Node head;

  topdownRB(int maxN)
  {
    head = null;
  }

  private boolean less(KEY v, KEY w)
  {
    return v.less(w);
  }

  private boolean equals(KEY v, KEY w)
  {
    return v.equals(w);
  }

  private ITEM searchR(Node h, KEY v)
  { // Find node for v
    if (h == null)
      return null;
    if (equals(v, h.item.key()))
      return h.item;
    if (less(v, h.item.key())) 
      return searchR(h.l, v);                
    else
      return searchR(h.r, v);
  }

  public ITEM search(KEY key)
  {
    return searchR(head, key);
  }

  private ITEM searchFirstKeyNotLessThanR(Node h, KEY v)
  { // Find node with smallest key that is >= v
    if (h == null)
      return null;
    if (equals(v, h.item.key()))
      return h.item;
    if (less(v, h.item.key()))
    {
      ITEM x=searchFirstKeyNotLessThanR(h.l, v);
      if (x==null)
        return h.item;  // No node in h.l subtree has key >= v
      else
        return x;
    }       
    return searchFirstKeyNotLessThanR(h.r, v);
  }

  public ITEM searchFirstKeyNotLessThan(KEY key)
  { // Starts recursive search
    return searchFirstKeyNotLessThanR(head,key);
  }

  private ITEM searchLastKeyNotGreaterThanR(Node h, KEY v)
  { // Find node with largest key that is <= v
    if (h == null)
      return null;
    if (equals(v, h.item.key()))
      return h.item;
    if (less(v, h.item.key()))
      return searchLastKeyNotGreaterThanR(h.l, v);

    ITEM x=searchLastKeyNotGreaterThanR(h.r, v);
    if (x==null)
      return h.item;  // No node in h.r subtree has key <= v
    return x;
  }

  public ITEM searchLastKeyNotGreaterThan(KEY key)
  { // Starts recursive search
    return searchLastKeyNotGreaterThanR(head,key);
  }

  // Number of items processed during "in between" traversal
  static private int count;

  private void traverseBetweenNoCheck(Node h)
  { // Inorder processing of every node in subtree rooted by h.
    // Keys are already known to satisfy start<=key<=stop.
    if (h == null)
      return;
    traverseBetweenNoCheck(h.l);
//  System.out.format("NoCheck: Process %s\n",h.item.toString());
    count++;
    if (count%5==1)
      System.out.format("\n");
    System.out.format("%s ",h.item.key().toString());
    traverseBetweenNoCheck(h.r);
  }

  private void traverseBetweenStartCheck(Node h,KEY start)
  { // Inorder processing of nodes in subtree (rooted by h) with key>=start.
    // It is known from previous comparisons that keys in subtree are
    // not larger than some stop value.
    if (h == null)
      return;
    if (less(h.item.key(),start))
      traverseBetweenStartCheck(h.r,start);
    else
    {
      traverseBetweenStartCheck(h.l,start);
//    System.out.format("Start: Process %s\n",h.item.toString());
      count++;
      if (count%5==1)
        System.out.format("\n");
      System.out.format("%s ",h.item.key().toString());
      traverseBetweenNoCheck(h.r);
    }
  }

  private void traverseBetweenStopCheck(Node h,KEY stop)
  { // Inorder processing of nodes in subtree (rooted by h) with key<=stop.
    // It is known from previous comparisons that keys in subtree are
    // not smaller than some start value.
    if (h == null)
      return;
    if (less(stop,h.item.key()))
      traverseBetweenStopCheck(h.l,stop);
    else
    {
      traverseBetweenNoCheck(h.l);
//    System.out.format("Stop: Process %s\n",h.item.toString());
      count++;
      if (count%5==1)
        System.out.format("\n");
      System.out.format("%s ",h.item.key().toString());
      traverseBetweenStopCheck(h.r,stop);
    }
  }

  private void traverseBetweenR(Node h,KEY start,KEY stop)
  { // Inorder processing of nodes in subtree (rooted by h)
    // whose keys satisfy start<=key<=stop.
    if (h == null)
      return;
    if (less(stop,h.item.key()))
      traverseBetweenR(h.l,start,stop);
    else if (less(h.item.key(),start))
      traverseBetweenR(h.r,start,stop);
    else
    {
      traverseBetweenStartCheck(h.l,start);
//    System.out.format("Between: Process %s\n",h.item.toString());
      count++;
      if (count%5==1)
        System.out.format("\n");
      System.out.format("%s ",h.item.key().toString());
      traverseBetweenStopCheck(h.r,stop);
    }
  }

  public int traverseBetween(KEY start,KEY stop)
  {
    count=0;
    traverseBetweenR(head,start,stop);
    return count;
  }

  private int rank4keyR(Node h, KEY v)
  { // Computes rank (smallest key is ranked 1, largest key is ranked n)
    // within subtree rooted by h
    if (h == null)
      return 0;
    if (equals(v, h.item.key()))
      return 1 + (h.l!=null ? h.l.subtreeSize : 0);
    if (less(v, h.item.key())) 
      return rank4keyR(h.l, v);                
    return 1 + (h.l!=null ? h.l.subtreeSize : 0) + rank4keyR(h.r, v);
  }

  public int rank4key(KEY key)
  { // Computes rank (smallest key is ranked 1, largest key is ranked n)
    // within entire tree, i.e. number of keys <= given key
    return rank4keyR(head,key);
  }

  private KEY key4rankR(Node h,int rank)
  { // Inverse of rank4keyR()
    if (h == null)
      return null;
    if (rank==1 + (h.l!=null ? h.l.subtreeSize : 0))
      return h.item.key();
    if (rank<=(h.l!=null ? h.l.subtreeSize : 0))
      return key4rankR(h.l,rank);
    return key4rankR(h.r,rank-1-(h.l!=null ? h.l.subtreeSize : 0));
  }

  public KEY key4rank(int rank)
  { // Inverse of rank4key() - determines key for a rank
    return key4rankR(head,rank);
  }

  private Node rotR(Node h)
  { // Rotates edge between h and h.l adjusting subtree sizes
    Node x = h.l;
    h.l = x.r;
    x.r = h;

    x.r.subtreeSize=1 + (x.r.l!=null ? x.r.l.subtreeSize : 0)
                      + (x.r.r!=null ? x.r.r.subtreeSize : 0);
    x.subtreeSize=1 + (x.l!=null ? x.l.subtreeSize : 0)
                    + x.r.subtreeSize;
    return x;
  }

  private Node rotL(Node h)
  { // Rotates edge between h and h.r adjusting subtree sizes
    Node x = h.r;
    h.r = x.l;
    x.l = h;

    x.l.subtreeSize=1 + (x.l.r!=null ? x.l.r.subtreeSize : 0)
                      + (x.l.l!=null ? x.l.l.subtreeSize : 0);
    x.subtreeSize=1 + (x.r!=null ? x.r.subtreeSize : 0)
                    + x.l.subtreeSize;
    return x;
  }

  private static final boolean R = true;

  private static final boolean B = false;

  private boolean red(Node x)
  {
    if (x == null)
      return false;
    return x.cbit;
  }

  private Node insertRrs(Node h, ITEM x, boolean sw)
  // Sedgewick's code
  { 
    if (h == null)
      return new Node(x, R);

    if (red(h.l) && red(h.r))
    {
      h.cbit = R;
      h.l.cbit = B;
      h.r.cbit = B;
    }

    if (less(x.key(), h.item.key()))
    { 
      h.l = insertR(h.l, x, false); 
      if (red(h) && red(h.l) && sw)
        h = rotR(h);
      if (red(h.l) && red(h.l.l)) 
      {
        h = rotR(h);
        h.cbit = B;
        h.r.cbit = R;
      }
    }
    else
    { 
      h.r = insertR(h.r, x, true); 
      if (red(h) && red(h.r) && !sw)
        h = rotL(h);
      if (red(h.r) && red(h.r.r)) 
      {
        h = rotL(h);
        h.cbit = B;
        h.l.cbit = R;
      }
    }
    // Clean-up subtree size
    h.subtreeSize=1+(h.l!=null ? h.l.subtreeSize : 0)
                   +(h.r!=null ? h.r.subtreeSize : 0);
    return h;
  }

  private Node insertR(Node h, ITEM x, boolean sw)
  // Program 13.6 coded to be a bit clearer and make mutually exclusive
  // cases obvious.  See 2320 notes.  BPW
  // h is present node in search down tree.
  // Returns root of modified subtree.
  // x is the item to be inserted.
  // sw is TRUE <=> h is to the right of its parent.
  { 
    if (h == null)
      return new Node(x, R);       // Attach red leaf

    if (red(h.l) && red(h.r))      // Flip colors before searching down
    {
      h.cbit = R;
      h.l.cbit = B;
      h.r.cbit = B;
    }

    if (less(x.key(), h.item.key()))
    { 
      h.l = insertR(h.l, x, false);   // Insert in left subtree
      if (red(h.l))
        if (red(h))
          if (sw)
            // Case ~1
            h = rotR(h);              // Set up case ~2 after return
          else
            ;
        else if (red(h.l.l))
        {
          // Case 2
          h = rotR(h);
          h.cbit = B;
          h.r.cbit = R;
        }
    }
    else
    { 
      h.r = insertR(h.r, x, true);    // Insert in right subtree
      if (red(h.r))
        if (red(h))
          if (!sw)
            // Case 1
            h = rotL(h);              // Set up case 2 after return
          else
            ;
        else if (red(h.r.r))
        {
          // Case ~2
          h = rotL(h);
          h.cbit = B;
          h.l.cbit = R;
        }
    }
    // Clean-up subtree size
    h.subtreeSize=1+(h.l!=null ? h.l.subtreeSize : 0)
                   +(h.r!=null ? h.r.subtreeSize : 0);
    return h;
  }

  void insert(ITEM x)
  {
    head = insertR(head, x, B);
    head.cbit = B;
  }

  private boolean clean;

  private int audit(Node h)
  { // Checks subtree size values
    if (h==null)
      return 0;
    int computed=1+audit(h.l)+audit(h.r);
    if (computed!=h.subtreeSize)
    {
      System.out.format("Subtree size error at key %s computed %d stored %d\n",
        h.item.key(),computed,h.subtreeSize);
      clean=false;
    }
    return computed;
  }

  boolean auditSizes()
  {
    clean=true;
    audit(head);
    return clean;
  }
}