/*
 * 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 java.util.*;
import java.lang.reflect.*;
import nsk.share.TestFailure;

public class test6
{
    private static final int[] MethodID = {Globals.MethodID_Array[11]};

    private static Random localNumGen = new Random(Globals.RANDOM_SEED);
    private static final int maxEntries = 25;

    //flattens the binary tree into an array
    private void getSortedArray(Node root, int [] dataArray, int[] index)
    {
        if ((root != null) && (root!=RBTree.treeNull))
            {
                getSortedArray(root.getNode(Node.Left_son), dataArray, index);
                dataArray[index[0]++] = root.getKey();
                getSortedArray(root.getNode(Node.Right_son), dataArray, index);
            }
    }

    public synchronized void rbTest(Vector summation, Vector ID, Long functionDepth, Integer staticFunctionDepth)
                throws InvocationTargetException
    {
        Globals.appendSumToSumationVector(MethodID[0], summation);

        if (CGT.shouldFinish())
            return;

        if (Globals.VERBOSE)
            System.out.println("test6.rbTest");

        if ((functionDepth.longValue() <= 0) && (staticFunctionDepth.intValue() <=  0))
            {
                return;
            }
        MethodData methodCallStr;
        Long numFcalls;
        Integer staticFcalls;

        if (staticFunctionDepth.intValue() > 0)
            {
                numFcalls = functionDepth;
                staticFcalls = new Integer(staticFunctionDepth.intValue()-1);
                methodCallStr = Globals.returnNextStaticMethod(MethodID[0]);
            }
        else
            {
                numFcalls = new Long(functionDepth.longValue() -1);
                staticFcalls = staticFunctionDepth;
                methodCallStr = Globals.nextRandomMethod();
            }

        RBTree myTree = new RBTree();
        int numElements = 1 + localNumGen.nextInt(maxEntries);
        int dataArray[] = new int[numElements];
        boolean insertArray[] = new boolean[numElements];

        Vector temp = new Vector(numElements);
        for(int i=0; i<numElements; i++)
            {                                         //code guarantees no duplicates
                int nextKey = localNumGen.nextInt(16385);
                while (temp.indexOf(new Integer(nextKey)) != -1)
                    nextKey = localNumGen.nextInt(16385);

                temp.addElement(new Integer(nextKey));
                dataArray[i] = nextKey;

                insertArray[i] = false;
            }
        temp = null;

        int numLoops = 10 + localNumGen.nextInt(1024);
        for (int i=0; i<numLoops; i++)
            {
                int nextIndex = localNumGen.nextInt(numElements);
                if (!insertArray[nextIndex])
                    {
                        myTree.RBInsert(dataArray[nextIndex]);
                        insertArray[nextIndex] = true;
                    }
                else
                    {
                        myTree.RBDelete(dataArray[nextIndex]);
                        insertArray[nextIndex] = false;
                    }
            }

        int numValid = 0;
        for (int i = 0; i<numElements; i++)
            {
                Node searchNode = myTree.Search(dataArray[i]);
                if (insertArray[i] && (searchNode == RBTree.treeNull))
                    {
                        System.out.println("Valid Node Not Found in Binary Tree");
                        System.out.println("Node " + dataArray[i]);
                        System.exit(1);
                    }
                else if ((!insertArray[i]) && (searchNode != RBTree.treeNull))
                    {
                        System.out.println("Deleted Node Found in Binary Tree");
                        System.out.println("Node " + dataArray[i]);
                        System.exit(1);
                    }
                else if (insertArray[i])
                    numValid++;
                insertArray[i] = true;        //so that verification is only done once
            }

        int [] sortedArray = new int[numValid];
        getSortedArray(myTree.getRoot(), sortedArray, new int [] {0});

        for (int i=1; i<numValid; i++)
            if (sortedArray[i] <= sortedArray[i-1])
                {
                    String outStr = new String("Actual ");
                    for (int j=0; j<sortedArray.length; j++)
                        outStr += sortedArray[j] +", ";
                    System.out.println("Binary Tree Property Not Held");
                    System.out.println("Root " + myTree.getRoot().getKey());
                    System.out.println(outStr);
                    System.exit(1);
                }

        //Should make more memory available for future instances
        myTree = null;
        sortedArray = null;
        dataArray = null;
        insertArray = null;
//        System.gc();

        Globals.addFunctionIDToVector(methodCallStr.id, ID);
        Globals.callMethod(methodCallStr,summation, ID, numFcalls, staticFcalls);


    }
}