/*
 * Copyright (c) 2008, 2018, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */
package jit.graph;

import nsk.share.TestFailure;

//import Node;

// This class defines the tree object.

public class RBTree
{
   public final static int  maxNodes = 70;        // maximum nodes allowed.
   public final static int  INSERT   = 0;         // constants indicating
   public final static int  DELETE   = 1;         // the current operation
   public final static int  NOP      = 2;
   public final static Node treeNull = new Node(); // the tree NULL node.

   private Node    root;
   private int     num_of_nodes;
   private int     height;           // The tree heigth ,it is updated
                                     // in each operation.

   // since the algorithem is executed in stages I have to remember data
   // on the state.
   private Node    node;  // The current operation is being done on it.
   private int     action;// The operation being performed (insert / delete)
   private int     stage; // The current stage of execution

   // the constructor initialize the object fields.

   public RBTree()
   {
      root         = treeNull;
      node         = treeNull;
      num_of_nodes = 0;
      height       = 0;
      action       = NOP;
      stage        = 0;
   }

   // This method return the root of the tree.

   public Node getRoot()
   {
      return root;
   }

   // This method return the number of nodes in the tree.

   public int getNodes()
   {
      return num_of_nodes;
   }

   // This method return the heigth of the tree.

   public int getHeight()
   {
      return height;
   }



   // This method inserts k into the Red Black Tree

   public boolean RBInsert(int k)
   {

      Thread Pause = new Thread();   // this thread is used for delay
                                     // between the stages.
      if (action != NOP)  // checking similar to the RB_Insert method
      {
         System.out.println
         ("Only one operation can be done at a time.");
         return false;
      }
      if (num_of_nodes == maxNodes)
      {
         System.out.println
         ("The maximum nodes allowed is already reached.");
         return false;
      }
      if (Search(k) == treeNull) // Check if there is already node with key k.
      {
         action = INSERT;
         node = new Node(k);
         node.setNode(Node.Left_son,treeNull);
         node.setNode(Node.Right_son,treeNull);
         node.setNode(Node.Parent,treeNull);
         stage = 1;
         while (stage != 0)     // This is the loop that perform all the
         {                      // operation steps.
            InsertStep();       // perform one step
            updateHeight();     // update the tree height
         }
         action = NOP;           // set the action to NoOPretion.
         return true;
      }
      else
        System.out.println
        ("Insertion failed. This key already exist.");
      return false;
   }


   // This method deletes the element k from the Red Black tree

   public boolean RBDelete(int k)
   {
      Thread Pause = new Thread();   // this thread is used for delay
                                     // between the stages.
      if (action != NOP)
      {                              // checking like in RB_Delete method
         System.out.println
         ("Only one operation can be done at a time.");
         return false;
      }
      node = Search(k);
      if (node != treeNull)       // Check if there is a node with key k.
      {
         action = DELETE;
         stage = 1;
         while (stage != 0)    // this loop perform all the operation
         {                     // steps.
            DeleteStep();               // perform one step
            updateHeight();             // update the tree height

         }
         action = NOP;
         return true;
      }
      else
         System.out.println
         ("Deletion failed. This key doesn't exist.");
      return false;
   }

   // This method perform one step in the insertion operation.
   // If perform a step acording to the stage variable.
   // I will not explain exactly what each stage do, just that they
   // divided to 4 categories:
   // 1. inserting a node to the tree.
   // 2. marking nodes that will be recolored.
   // 3. recoloring nodes.
   // 4. rotating right or left.

   private void InsertStep()
   {
      Node Pr,GrPr,Un; // Pr is parent, GrPr is grandparent
                       // and Un is uncle.
      switch (stage)
      {
           case 1: // Inserting a node to the tree
               /*
                  System.out.println  // send a message to the screen
                  (new String("Inserting ")
                  .concat(Integer.toString(node.getKey())));
               */
                  Tree_Insert();        // inserting an element to the tree
                  break;
           case 2:       // mid stage that move to algorithem to the
                         // proper next stage, and send proper message
                         // to the screen
                  Pr = node.getNode(Node.Parent);
                  GrPr = Pr.getNode(Node.Parent);
                  if (Pr == GrPr.getNode(Node.Left_son))
                  {
                     Un = GrPr.getNode(Node.Right_son);
                     if (Un.getColor() == Node.Red)
                     {
                        stage = 3;
                     }
                     else
                        if (node == Pr.getNode(Node.Right_son))
                        {
                           node = Pr;
                           stage = 5;
                        }
                        else
                        {
                           stage = 6;
                        }
                  }
                  else
                  {
                     Un = GrPr.getNode(Node.Left_son);
                     if (Un.getColor() == Node.Red)
                     {
                        stage = 3;
                     }
                     else
                        if (node == Pr.getNode(Node.Left_son))
                        {
                           node = Pr;
                           stage = 5;
                        }
                        else
                        {
                           stage = 6;
                        }
                  }
                  break;
           case 3:       // This stage marks node that will be recolored
                  Pr = node.getNode(Node.Parent);
                  GrPr = Pr.getNode(Node.Parent);
                  if (Pr == GrPr.getNode(Node.Left_son))
                     Un = GrPr.getNode(Node.Right_son);
                  else
                      Un = GrPr.getNode(Node.Left_son);

                  node = GrPr;
                  stage = 4;
                  break;
           case 4:          // this stage recolor marked nodes.
                  node.setColor(Node.Red);
                  (node.getNode(Node.Left_son)).setColor(Node.Black);
                  (node.getNode(Node.Right_son)).setColor(Node.Black);

                  if ((node == root) ||
                     ((node.getNode(Node.Parent)).getColor() == Node.Black))
                     if (root.getColor() == Node.Red)
                     {
                        stage = 9;
                     }
                     else
                        stage = 0;
                  else
                  {
                     stage = 2;
                     InsertStep();
                  }
                  break;
           case 5:        // This stage perform rotation operation
                  Pr = node.getNode(Node.Parent);
                  if (node == Pr.getNode(Node.Left_son))
                     Left_Rotate(node);
                  else
                     Right_Rotate(node);

                  stage = 6;
                  break;
           case 6:        // This stage marks nodes that will be recolor.
                  Pr = node.getNode(Node.Parent);
                  GrPr = Pr.getNode(Node.Parent);

                  stage = 7;
                  break;
           case 7:        // This stage recolor marked nodes.
                  Pr = node.getNode(Node.Parent);
                  Pr.setColor(Node.Black);
                  GrPr = Pr.getNode(Node.Parent);
                  GrPr.setColor(Node.Red);

                  stage = 8;
                  break;
           case 8:        // This stage perform rotation operation
                  Pr = node.getNode(Node.Parent);
                  GrPr = Pr.getNode(Node.Parent);
                  if (Pr == GrPr.getNode(Node.Left_son))
                     Right_Rotate(GrPr);
                  else
                     Left_Rotate(GrPr);
                  if (root.getColor() == Node.Red)
                  {
                     stage = 9;
                  }
                  else
                     stage = 0;
                  break;
           case 9:        // this stage mark the root.
                   stage = 10;
                  break;
           case 10:       // This stage recolor the root.
                  root.setColor(Node.Black);
                  stage = 0;
                  break;
      }
   }

   // This method perform one step in the deletion operation.
   // If perform a step acording to the stage variable.
   // I will explain exactly what each stage do, just that they
   // divided to 4 categories:
   // 1. deleting a node from the tree.
   // 2. marking nodes that will be recolored.
   // 3. recoloring nodes.
   // 4. rotating right or left.

   public void DeleteStep()
   {
       Node Pr,Br;     // Pr is Parent ,Br is Brother
       switch (stage)
       {
             case 1:   // This stage delete a node from the tree.
                 /*
                    System.out.println
                    (new String("Deleting ")
                    .concat(Integer.toString(node.getKey())));
                 */
                    Tree_Delete();
                    break;
             case 2:   // This stage marks a nodes that will be recolored
                       // or perform other stage.
                    Pr = node.getNode(Node.Parent);
                    if (node == Pr.getNode(Node.Left_son))
                       Br = Pr.getNode(Node.Right_son);
                    else
                       Br = Pr.getNode(Node.Left_son);
                    if (Br.getColor() == Node.Red)
                    {
                        stage = 3;
                    }
                    else
                       if (((Br.getNode(Node.Right_son)).getColor() == Node.Black)
                          && ((Br.getNode(Node.Left_son)).getColor() == Node.Black))
                       {
                          stage = 5;
                          DeleteStep();
                       }
                       else
                       {
                          stage = 7;
                          DeleteStep();
                       }
                    break;
             case 3:    // this stage recolor marked nodes.
                    Pr = node.getNode(Node.Parent);
                    if (node == Pr.getNode(Node.Left_son))
                    {
                       Br = Pr.getNode(Node.Right_son);

                    }
                    else
                    {
                       Br = Pr.getNode(Node.Left_son);
                    }
                    Br.setColor(Node.Black);
                    Pr.setColor(Node.Red);

                    stage = 4;
                    break;
             case 4:     // this stage perform rotation operation
                    Pr = node.getNode(Node.Parent);
                    if (node == Pr.getNode(Node.Left_son))
                    {
                       Left_Rotate(Pr);
                       Br = Pr.getNode(Node.Right_son);
                    }
                    else
                    {
                       Right_Rotate(Pr);
                       Br = Pr.getNode(Node.Left_son);
                    }
                    if (((Br.getNode(Node.Right_son)).getColor() == Node.Black)
                       && ((Br.getNode(Node.Left_son)).getColor() == Node.Black))
                       stage = 5;
                    else
                       stage = 7;

                    break;
             case 5:     // this stage marks nodes that will be recolor.
                    Pr = node.getNode(Node.Parent);
                    if (node == Pr.getNode(Node.Left_son))
                       Br = Pr.getNode(Node.Right_son);
                    else
                       Br = Pr.getNode(Node.Left_son);

                    stage = 6;
                    break;
             case 6:     // This stage recolor marked nodes.
                    Pr = node.getNode(Node.Parent);
                    if (node == Pr.getNode(Node.Left_son))
                       Br = Pr.getNode(Node.Right_son);
                    else
                       Br = Pr.getNode(Node.Left_son);
                    Br.setColor(Node.Red);
                    node = Pr;

                    if ((node != root) && (node.getColor() == Node.Black))
                       stage = 2;
                    else
                       if (node.getColor() == Node.Red)
                       {
                          stage = 13;
                       }
                       else
                          stage = 0;
                    break;
             case 7:     // this stage marks nodes that will be recolor
                         // or perform other stage.
                    Pr = node.getNode(Node.Parent);
                    if (node == Pr.getNode(Node.Left_son))
                    {
                       Br = Pr.getNode(Node.Right_son);
                       if ((Br.getNode(Node.Right_son)).getColor() == Node.Black)
                       {
                          stage = 8;
                       }
                       else
                       {
                          stage = 10;
                          DeleteStep();
                       }
                    }
                    else
                    {
                       Br = Pr.getNode(Node.Left_son);
                       if ((Br.getNode(Node.Left_son)).getColor() == Node.Black)
                       {
                          stage = 8;
                       }
                       else
                       {
                          stage = 10;
                          DeleteStep();
                       }
                    }
                    break;
             case 8:     // this stage recolor marked nodes.
                    Pr = node.getNode(Node.Parent);
                    if (node == Pr.getNode(Node.Left_son))
                    {
                       Br = Pr.getNode(Node.Right_son);
                       (Br.getNode(Node.Left_son)).setColor(Node.Black);

                    }
                    else
                    {
                       Br = Pr.getNode(Node.Left_son);
                       (Br.getNode(Node.Right_son)).setColor(Node.Black);

                    }
                    Br.setColor(Node.Red);
                    stage = 9;
                    break;
             case 9:    // this stage perform rotation operation
                    Pr = node.getNode(Node.Parent);
                    if (node == Pr.getNode(Node.Left_son))
                    {
                       Br = Pr.getNode(Node.Right_son);
                       Right_Rotate(Br);
                    }
                    else
                    {
                       Br = Pr.getNode(Node.Left_son);
                       Left_Rotate(Br);
                    }

                    stage = 10;
                    break;
             case 10:   // This stage marks node that will be recolor.

                    Pr = node.getNode(Node.Parent);
                    if (node == Pr.getNode(Node.Left_son))
                    {
                       Br = Pr.getNode(Node.Right_son);
                    }
                    else
                    {
                       Br = Pr.getNode(Node.Left_son);
                    }

                    stage = 11;
                    break;
             case 11:    // this stage recolor marked nodes.
                    Pr = node.getNode(Node.Parent);
                    if (node == Pr.getNode(Node.Left_son))
                    {
                       Br = Pr.getNode(Node.Right_son);
                       (Br.getNode(Node.Right_son)).setColor(Node.Black);
                    }
                    else
                    {
                       Br = Pr.getNode(Node.Left_son);
                       (Br.getNode(Node.Left_son)).setColor(Node.Black);

                    }
                    if (Br.getColor() != Pr.getColor())
                       Br.setColor(Pr.getColor());
                    if (Pr.getColor() != Node.Black)
                       Pr.setColor(Node.Black);

                    stage = 12;
                    break;
             case 12:    // this stage perform rotation operation.
                    Pr = node.getNode(Node.Parent);
                    if (node == Pr.getNode(Node.Left_son))
                       Left_Rotate(Pr);
                    else
                       Right_Rotate(Pr);
                    node = root;
                    if (node.getColor() == Node.Red)
                    {
                       stage = 13;
                    }
                    else
                       stage = 0;
                    break;
             case 13:    // this stage marks a node that will be recolor
                    stage = 14;
                    break;
             case 14:    // this stage recolor marked node.
                    node.setColor(Node.Black);
                    stage = 0;
                    break;
       }
   }

   // This method insert the node 'node' to the tree.
   // it called from the first stage in the InsertStep method.
   // we 'dive' from the root to a leaf acording to the node key
   // and insert the node in the proper place.

   private void Tree_Insert()
   {
       Node n1,n2;
       n1 = root;
       n2 = treeNull;
       while (n1 != treeNull)
       {
          n2 = n1;
          if (node.getKey() < n1.getKey())
             n1 = n1.getNode(Node.Left_son);
          else
             n1 = n1.getNode(Node.Right_son);
       }
       node.setNode(Node.Parent,n2);
       if (n2 == treeNull)
          root = node;
       else
       {
          if (node.getKey() < n2.getKey())
             n2.setNode(Node.Left_son,node);
          else
             n2.setNode(Node.Right_son,node);
       }
       //Parent.display.drawTree();
       // updating the insertion stage.
       if ((node == root) ||
          ((node.getNode(Node.Parent)).getColor() == Node.Black))
          if (root.getColor() == Node.Red)
          {
             stage = 9;
          }
          else
             stage = 0;
       else
       {
          stage = 2;
          InsertStep();
       }
       num_of_nodes++;   // increasing the number of nodes
   }

   // This method delete the node 'node' from the tree.
   // it called from the first stage in the DeleteStep method.
   // if node has at most one son we just remove it and connect
   // his son and parent. If it has 2 sons we delete his successor
   // that has at most one son and replace him with the successor.

   private void Tree_Delete()
   {
      Node n1,n2,n3;
      if ((node.getNode(Node.Left_son) == treeNull) ||
          (node.getNode(Node.Right_son) == treeNull))
         n1 = node;
      else
         n1 = Tree_Successor(node);
      if (n1.getNode(node.Left_son) != treeNull)
         n2 = n1.getNode(Node.Left_son);
      else
         n2 = n1.getNode(Node.Right_son);

      n3 = n1.getNode(Node.Parent);
      n2.setNode(Node.Parent,n3);
      if (n3 == treeNull)
         root = n2;
      else
         if (n1 == n3.getNode(Node.Left_son))
            n3.setNode(Node.Left_son,n2);
         else
            n3.setNode(Node.Right_son,n2);

      if (n1 != node)
      {
         node.setKey(n1.getKey());
      }


      node = n2;
      if (n1.getColor() == Node.Black)
         if ((node != root) && (node.getColor() == Node.Black))
            stage = 2;
         else
            if (node.getColor() == Node.Red)
               stage = 13;
            else
               stage = 0;
      else
         stage = 0;
      num_of_nodes--;      // decrease the number of nodes.
   }

   // This method return the successor of the node n in the tree.

   private Node Tree_Successor(Node n)
   {
      Node n1;
      if (n.getNode(Node.Right_son) != treeNull)
      {
         n = n.getNode(Node.Right_son);
         while (n.getNode(Node.Left_son) != treeNull)
             n = n.getNode(Node.Left_son);
         return n;
      }
      n1 = n.getNode(Node.Parent);
      while ((n1 != treeNull) && (n == n1.getNode(Node.Right_son)))
      {
         n = n1;
         n1 = n1.getNode(Node.Parent);
      }
      return n1;
   }

   // This method perform Left Rotation with n1.

   private void Left_Rotate(Node n1)
   {
      Node n2;

      n2 = n1.getNode(Node.Right_son);
      n1.setNode(Node.Right_son,n2.getNode(Node.Left_son));
      if (n2.getNode(Node.Left_son) != treeNull)
         (n2.getNode(Node.Left_son)).setNode(Node.Parent,n1);
      n2.setNode(Node.Parent,n1.getNode(Node.Parent));
      if (n1.getNode(Node.Parent) == treeNull)
         root = n2;
      else
         if (n1 == (n1.getNode(Node.Parent)).getNode(Node.Left_son))
            (n1.getNode(Node.Parent)).setNode(Node.Left_son,n2);
         else
            (n1.getNode(Node.Parent)).setNode(Node.Right_son,n2);
      n2.setNode(Node.Left_son,n1);
      n1.setNode(Node.Parent,n2);
   }

   // This method perform Right Rotation with n1.

   private void Right_Rotate(Node n1)
   {
      Node n2;

      n2 = n1.getNode(Node.Left_son);
      n1.setNode(Node.Left_son,n2.getNode(Node.Right_son));
      if (n2.getNode(Node.Right_son) != treeNull)
         (n2.getNode(Node.Right_son)).setNode(Node.Parent,n1);
      n2.setNode(Node.Parent,n1.getNode(Node.Parent));
      if (n1.getNode(Node.Parent) == treeNull)
         root = n2;
      else
         if (n1 == (n1.getNode(Node.Parent)).getNode(Node.Left_son))
            (n1.getNode(Node.Parent)).setNode(Node.Left_son,n2);
         else
            (n1.getNode(Node.Parent)).setNode(Node.Right_son,n2);
      n2.setNode(Node.Right_son,n1);
      n1.setNode(Node.Parent,n2);
   }

   // This method search the tree for a node with key 'key', and
   // return the node on success otherwise treeNull.

   public Node Search(int key)
   {
      Node node;
      node = root;
      while ((node != treeNull) && (key != node.getKey()))
         if (key < node.getKey())
            node = node.getNode(Node.Left_son);
         else
            node = node.getNode(Node.Right_son);
      return node;
   }

   // This method update the tree height it uses a recursive method
   // findheight.

   private void updateHeight()
   {
      height = 0;
      if (root != treeNull)
         findHeight(root,1);
   }

   // This is a recursive method that find a node height.

   private void findHeight(Node n,int curr)
   {
      if (height < curr)
         height = curr;
      if (n.getNode(Node.Left_son) != treeNull)
         findHeight(n.getNode(Node.Left_son),curr+1);
      if (n.getNode(Node.Right_son) != treeNull)
         findHeight(n.getNode(Node.Right_son),curr+1);
   }

}
