package org.apache.avalon.excalibur.collections;

import java.util.NoSuchElementException;

public class TestBinaryHeap
{

    //	--------------------------------------------------------------------
    //	Test Driver
    //	--------------------------------------------------------------------

    public static class UnitTestDriver
    {

        public void
        recordSuccess(String pTestName)
        {
            System.out.println("Successfully ran " + pTestName);
        }

        public void
        recordFailure(String pTestName, String pErrorString)
        {
            System.out.println("FAILED " + pTestName);
        }

        public void
        recordFailure(String pTestName, Exception pException)
        {
            System.out.println("FAILED " + pTestName);
            pException.printStackTrace(System.out);
        }

    }

    //	--------------------------------------------------------------------
    //	Test Case Entry Point
    //	--------------------------------------------------------------------

    public void
    runTests(UnitTestDriver pDriver)
    {
        testAddingElements(pDriver);
        testRemovingElements(pDriver);
        testAddingAndRemovingElements(pDriver);
    }

    //	--------------------------------------------------------------------
    //	Unit Test Cases
    //	--------------------------------------------------------------------

    protected void
    testAddingElements(UnitTestDriver pDriver)
    {
        String lTestName = null;

        try
        {
            BinaryHeap 	lBinaryHeap = new BinaryHeap(BinaryHeap.MAX_COMPARATOR);
            int		lSize = lBinaryHeap.size();

            lTestName = "Add (non-null) element";
            lBinaryHeap.insert(new Integer(1));
            if (lBinaryHeap.size() != lSize + 1)
                pDriver.recordFailure(lTestName, "incorrect BinaryHeap size");
            else if (((Integer)(lBinaryHeap.peek())).intValue() != 1)
                pDriver.recordFailure(lTestName, "incorrect peek value");
            else
                pDriver.recordSuccess(lTestName);

            lTestName = "Add (unique, larger, non-null) element";
            lSize = lBinaryHeap.size();
            lBinaryHeap.insert(new Integer(2));
            if (lBinaryHeap.size() != lSize + 1)
                pDriver.recordFailure(lTestName, "incorrect BinaryHeap size");
            else if (((Integer)(lBinaryHeap.peek())).intValue() != 2)
                pDriver.recordFailure(lTestName, "incorrect peek value");
            else
                pDriver.recordSuccess(lTestName);

            lTestName = "Add (unique, smaller, non-null) element";
            lSize = lBinaryHeap.size();
            lBinaryHeap.insert(new Integer(0));
            if (lBinaryHeap.size() != lSize + 1)
                pDriver.recordFailure(lTestName, "incorrect BinaryHeap size");
            else if (((Integer)(lBinaryHeap.peek())).intValue() != 2)
                pDriver.recordFailure(lTestName, "incorrect peek value");
            else
                pDriver.recordSuccess(lTestName);

            lTestName = "Add (duplicate, non-null) element";
            lSize = lBinaryHeap.size();
            lBinaryHeap.insert(new Integer(0));
            if (lBinaryHeap.size() != lSize + 1)
                pDriver.recordFailure(lTestName, "incorrect BinaryHeap size");
            else if (((Integer)(lBinaryHeap.peek())).intValue() != 2)
                pDriver.recordFailure(lTestName, "incorrect peek value");
            else
                pDriver.recordSuccess(lTestName);

            // Commented out since Excalibur's heaps do not check for non-null element
            // on insert
            /*
            lTestName = "Add (null) element";
            lSize = lBinaryHeap.size();
            try
            {
                lBinaryHeap.insert(null);
                pDriver.recordFailure(lTestName, "no exception raised");
            }
            catch(IllegalArgumentException pException)
            {
                if (lBinaryHeap.size() != lSize)
                    pDriver.recordFailure(lTestName, "incorrect BinaryHeap size");
                else if (((Integer)(lBinaryHeap.peek())).intValue() != 2)
                    pDriver.recordFailure(lTestName, "incorrect peek value");
                else
                    pDriver.recordSuccess(lTestName);
            }
            */
        }
        catch(Exception pException)
        {
            pDriver.recordFailure(lTestName, pException);
        }
    }

    protected void
    testRemovingElements(UnitTestDriver pDriver)
    {
        String lTestName = null;

        try
        {
            BinaryHeap 	lBinaryHeap = new BinaryHeap(BinaryHeap.MAX_COMPARATOR);
            int		lSize = lBinaryHeap.size();

            lTestName = "Try to take a peek at an empty BinaryHeap";
            try
            {
                if (lBinaryHeap.peek() != null)
                    pDriver.recordFailure(lTestName, "peek returned non-null element");
                else
                    pDriver.recordFailure(lTestName, "peek did not throw exception");
            }
            catch(NoSuchElementException pException)
            {
                pDriver.recordSuccess(lTestName);
            }

            lTestName = "Try to remove the top element from an empty BinaryHeap";
            try
            {
                if (lBinaryHeap.pop() != null)
                    pDriver.recordFailure(lTestName, "pop returned non-null element");
                else
                    pDriver.recordFailure(lTestName, "pop did not throw exception");
            }
            catch(NoSuchElementException pException)
            {
                pDriver.recordSuccess(lTestName);
            }

            lTestName = "Remove the top element from a single-item BinaryHeap";
            lBinaryHeap.insert(new Integer(1));
            lBinaryHeap.pop();
            try
            {
                if (lBinaryHeap.peek() != null)
                    pDriver.recordFailure(lTestName, "peek returned non-null element");
                else
                    pDriver.recordFailure(lTestName, "peek did not throw exception");
            }
            catch(NoSuchElementException pException)
            {
                pDriver.recordSuccess(lTestName);
            }
        }
        catch(Exception pException)
        {
            pDriver.recordFailure(lTestName, pException);
        }
    }

    protected void
    testAddingAndRemovingElements(UnitTestDriver pDriver)
    {
        String lTestName = null;

        try
        {
            BinaryHeap	lBinaryHeap = new BinaryHeap(BinaryHeap.MAX_COMPARATOR);
            int		lSize = 0;
            boolean	lFailureFlag = false;

            //	Note that the test loops are set to 22 elements so that
            //	four levels of the BinaryHeap are touched (given the default
            //	branching factor of 4)

            lTestName = "Add elements in ascending order, then removing all";
            for (int i = 0; i < 22; i++)
                lBinaryHeap.insert(new Integer(i));
            for (int i = 21; i >= 0 && !lFailureFlag; i--)
            {
                Integer lInteger = (Integer)(lBinaryHeap.peek());
                if (lInteger == null)
                {
                    pDriver.recordFailure(lTestName, "got null element: " + i);
                    lFailureFlag = true;
                }
                else if (lInteger.intValue() != i)
                {
                    pDriver.recordFailure(lTestName, "peek element not correct: " + i);
                    lFailureFlag = true;
                }
                lBinaryHeap.pop();
            }
            if (!lFailureFlag)
            {
                if (lBinaryHeap.size() != 0)
                    pDriver.recordFailure(lTestName, "incorrect size");
                else
                    pDriver.recordSuccess(lTestName);
            }

            lTestName = "Add elements in descending order, then removing all";
            for (int i = 21; i >= 0; i--)
                lBinaryHeap.insert(new Integer(i));
            for (int i = 21; i >= 0 && !lFailureFlag; i--)
            {
                Integer lInteger = (Integer)(lBinaryHeap.peek());
                if (lInteger == null)
                {
                    pDriver.recordFailure(lTestName, "got null element: " + i);
                    lFailureFlag = true;
                }
                else if (lInteger.intValue() != i)
                {
                    pDriver.recordFailure(lTestName, "peek element not correct: " + i);
                    lFailureFlag = true;
                }
                lBinaryHeap.pop();
            }
            if (!lFailureFlag)
            {
                if (lBinaryHeap.size() != 0)
                    pDriver.recordFailure(lTestName, "incorrect size");
                else
                    pDriver.recordSuccess(lTestName);
            }
        }
        catch(Exception pException)
        {
            pDriver.recordFailure(lTestName, pException);
        }
    }

    //	--------------------------------------------------------------------
    //	Unit Test Driver
    //	--------------------------------------------------------------------

    public static void
    main(String[] args)
    {
        TestBinaryHeap lTest = new TestBinaryHeap();
        UnitTestDriver	lDriver = new UnitTestDriver();

        lTest.runTests(lDriver);
    }

}