import static org.junit.Assert.*;

import java.util.Iterator;
import java.util.LinkedList;

import org.junit.Before;
import org.junit.Test;

// ------------------------------------------------------------------------------
/**
 * Test class for {@link AVLTree}.
 * 
 * @author Michael D. Naper, Jr. <MichaelNaper.com>
 * @version 2010.07.08
 */
public class AVLTreeTest {

    // ~ Instance Variables ....................................................

    private AVLTree<Integer> tree;

    private LinkedList<Integer> collection;

    // ~ Methods ...............................................................

    // -------------------------------------------------------------------------
    /**
     * @throws java.lang.Exception
     */
    @Before
    public void setUp() throws Exception {

        tree = new AVLTree<Integer>();

        collection = new LinkedList<Integer>();

        collection.add(3);
        collection.add(2);
        collection.add(1);
        collection.add(4);
        collection.add(5);
        collection.add(6);
        collection.add(7);
        collection.add(16);
        collection.add(15);
        collection.add(14);
        collection.add(13);
        collection.add(12);
        collection.add(11);
        collection.add(10);
        collection.add(8);
        collection.add(9);
    }

    // -------------------------------------------------------------------------
    /**
     * Test method for {@link AVLTree#AVLTree()}.
     */
    @Test
    public void testAVLTree() {

        assertNotNull(tree);

        assertEquals(0, tree.size());
    }

    // -------------------------------------------------------------------------
    /**
     * Test method for {@link AVLTree#insert(java.lang.Comparable)}.
     */
    @Test
    public void testInsert() {

        assertTrue(tree.insert(3));
        assertEquals(1, tree.size());
        assertFalse(tree.insert(3));

        assertTrue(tree.insert(2));
        assertEquals(2, tree.size());
        assertFalse(tree.insert(2));

        assertTrue(tree.insert(1));
        assertEquals(3, tree.size());
        assertFalse(tree.insert(1));

        assertTrue(tree.insert(4));
        assertEquals(4, tree.size());
        assertFalse(tree.insert(4));

        assertTrue(tree.insert(5));
        assertEquals(5, tree.size());
        assertFalse(tree.insert(5));

        assertTrue(tree.insert(6));
        assertEquals(6, tree.size());
        assertFalse(tree.insert(6));

        assertTrue(tree.insert(7));
        assertEquals(7, tree.size());
        assertFalse(tree.insert(7));

        assertTrue(tree.insert(16));
        assertEquals(8, tree.size());
        assertFalse(tree.insert(16));

        assertTrue(tree.insert(15));
        assertEquals(9, tree.size());
        assertFalse(tree.insert(15));

        assertTrue(tree.insert(14));
        assertEquals(10, tree.size());
        assertFalse(tree.insert(14));

        assertTrue(tree.insert(13));
        assertEquals(11, tree.size());
        assertFalse(tree.insert(13));

        assertTrue(tree.insert(12));
        assertEquals(12, tree.size());
        assertFalse(tree.insert(12));

        assertTrue(tree.insert(11));
        assertEquals(13, tree.size());
        assertFalse(tree.insert(11));

        assertTrue(tree.insert(10));
        assertEquals(14, tree.size());
        assertFalse(tree.insert(10));

        assertTrue(tree.insert(8));
        assertEquals(15, tree.size());
        assertFalse(tree.insert(8));

        assertTrue(tree.insert(9));
        assertEquals(16, tree.size());
        assertFalse(tree.insert(9));

        assertFalse(tree.insert(3));
        assertFalse(tree.insert(2));
        assertFalse(tree.insert(1));
        assertFalse(tree.insert(4));
        assertFalse(tree.insert(5));
        assertFalse(tree.insert(6));
        assertFalse(tree.insert(7));
        assertFalse(tree.insert(16));
        assertFalse(tree.insert(15));
        assertFalse(tree.insert(14));
        assertFalse(tree.insert(13));
        assertFalse(tree.insert(12));
        assertFalse(tree.insert(11));
        assertFalse(tree.insert(10));
        assertFalse(tree.insert(8));
        assertFalse(tree.insert(9));
    }

    // -------------------------------------------------------------------------
    /**
     * Test method for {@link AVLTree#insertAll(java.util.Collection)}.
     */
    @Test
    public void testInsertAll() {

        assertTrue(tree.insertAll(collection));

        assertEquals(collection.size(), tree.size());

        assertFalse(tree.insertAll(collection));

        tree.clear();

        for (int i = 0; i < collection.size() - 1; i++) {
            tree.insert(collection.get(i));
        }

        assertTrue(tree.insertAll(collection));

        assertFalse(tree.insertAll(collection));
    }

    // -------------------------------------------------------------------------
    /**
     * Test method for {@link AVLTree#contains(java.lang.Comparable)}.
     */
    @Test
    public void testContains() {

        assertFalse(tree.contains(42));
        tree.insert(42);
        assertTrue(tree.contains(42));

        assertFalse(tree.contains(31));
        tree.insert(31);
        assertTrue(tree.contains(31));

        assertFalse(tree.contains(27));
        tree.insert(27);
        assertTrue(tree.contains(27));

        assertFalse(tree.contains(41));
        tree.insert(41);
        assertTrue(tree.contains(41));

        assertFalse(tree.contains(59));
        tree.insert(59);
        assertTrue(tree.contains(59));
    }

    // -------------------------------------------------------------------------
    /**
     * Test method for {@link AVLTree#containsAll(java.util.Collection)}.
     */
    @Test
    public void testContainsAll() {

        assertFalse(tree.containsAll(collection));

        tree.insertAll(collection);

        assertTrue(tree.containsAll(collection));

        tree.clear();

        for (int i = 0; i < collection.size() - 1; i++) {
            tree.insert(collection.get(i));
        }

        assertFalse(tree.containsAll(collection));

        tree.insert(collection.getLast());

        assertTrue(tree.containsAll(collection));
    }

    // -------------------------------------------------------------------------
    /**
     * Test method for {@link AVLTree#find(java.lang.Comparable)}.
     */
    @Test
    public void testFind() {

        assertNull(tree.find(42));
        tree.insert(42);
        assertNotNull(tree.find(42));
        assertEquals(new Integer(42), tree.find(42));

        assertNull(tree.find(31));
        tree.insert(31);
        assertNotNull(tree.find(31));
        assertEquals(new Integer(31), tree.find(31));

        assertNull(tree.find(27));
        tree.insert(27);
        assertNotNull(tree.find(27));
        assertEquals(new Integer(27), tree.find(27));

        assertNull(tree.find(41));
        tree.insert(41);
        assertNotNull(tree.find(41));
        assertEquals(new Integer(41), tree.find(41));

        assertNull(tree.find(59));
        tree.insert(59);
        assertNotNull(tree.find(59));
        assertEquals(new Integer(59), tree.find(59));
    }

    // -------------------------------------------------------------------------
    /**
     * Test method for {@link AVLTree#findMin()}.
     */
    @Test
    public void testFindMin() {

        tree.insertAll(collection);

        assertEquals(new Integer(1), tree.findMin());

        tree.remove(1);

        assertEquals(new Integer(2), tree.findMin());
    }

    // -------------------------------------------------------------------------
    /**
     * Test method for {@link AVLTree#findMax()}.
     */
    @Test
    public void testFindMax() {

        tree.insertAll(collection);

        assertEquals(new Integer(16), tree.findMax());

        tree.remove(16);

        assertEquals(new Integer(15), tree.findMax());
    }

    // -------------------------------------------------------------------------
    /**
     * Test method for {@link AVLTree#remove(java.lang.Comparable)}.
     */
    @Test
    public void testRemove() {

        assertFalse(tree.remove(3));

        tree.insert(3);
        assertEquals(1, tree.size());
        assertTrue(tree.remove(3));
        assertEquals(0, tree.size());
        assertFalse(tree.contains(3));

        tree.insert(2);
        tree.insert(1);
        tree.insert(3);
        tree.insert(4);

        assertEquals(4, tree.size());
        assertTrue(tree.remove(1));
        assertEquals(3, tree.size());
        assertFalse(tree.contains(1));

        tree.insert(1);

        assertEquals(4, tree.size());
        assertTrue(tree.remove(4));
        assertEquals(3, tree.size());
        assertFalse(tree.contains(4));

        tree.insert(4);
        tree.insert(5);

        assertEquals(5, tree.size());
        assertTrue(tree.remove(1));
        assertEquals(4, tree.size());
        assertFalse(tree.contains(1));

        tree.insert(1);

        assertEquals(5, tree.size());
        assertTrue(tree.remove(5));
        assertEquals(4, tree.size());
        assertFalse(tree.contains(5));

        assertTrue(tree.remove(1));
        assertEquals(3, tree.size());
        assertFalse(tree.contains(1));

        assertTrue(tree.remove(3));
        tree.insert(5);
        tree.insert(3);

        assertEquals(4, tree.size());
        assertTrue(tree.remove(5));
        assertEquals(3, tree.size());
        assertFalse(tree.contains(5));

        assertTrue(tree.remove(2));
        assertTrue(tree.remove(3));
        assertTrue(tree.remove(4));

        assertFalse(tree.remove(1));
        assertFalse(tree.remove(2));
        assertFalse(tree.remove(3));
        assertFalse(tree.remove(4));
        assertFalse(tree.remove(5));
    }

    // -------------------------------------------------------------------------
    /**
     * Test method for {@link AVLTree#removeAll(java.util.Collection)}.
     */
    @Test
    public void testRemoveAll() {

        assertFalse(tree.removeAll(collection));

        tree.insert(42);

        assertFalse(tree.removeAll(collection));

        tree.insertAll(collection);

        assertTrue(tree.removeAll(collection));

        assertEquals(1, tree.size());

        tree.clear();

        for (int i = 0; i < collection.size() - 1; i++) {
            tree.insert(collection.get(i));
        }

        assertTrue(tree.removeAll(collection));

        assertEquals(0, tree.size());

        assertFalse(tree.removeAll(collection));
    }

    // -------------------------------------------------------------------------
    /**
     * Test method for {@link AVLTree_Recursive#removeMin()}.
     */
    @Test
    public void testRemoveMin() {

        assertNull(tree.removeMin());

        tree.insertAll(collection);

        assertEquals(new Integer(1), tree.removeMin());

        assertEquals(collection.size() - 1, tree.size());

        assertFalse(tree.contains(1));

        assertEquals(new Integer(2), tree.removeMin());

        assertEquals(collection.size() - 2, tree.size());

        assertFalse(tree.contains(2));
    }

    // -------------------------------------------------------------------------
    /**
     * Test method for {@link AVLTree_Recursive#removeMax()}.
     */
    @Test
    public void testRemoveMax() {

        assertNull(tree.removeMin());

        tree.insertAll(collection);

        assertEquals(new Integer(16), tree.removeMax());

        assertEquals(collection.size() - 1, tree.size());

        assertFalse(tree.contains(16));

        assertEquals(new Integer(15), tree.removeMax());

        assertEquals(collection.size() - 2, tree.size());

        assertFalse(tree.contains(15));
    }

    // -------------------------------------------------------------------------
    /**
     * Test method for {@link AVLTree#clear()}.
     */
    @Test
    public void testClear() {

        tree.insertAll(collection);

        assertFalse(tree.isEmpty());

        tree.clear();

        assertTrue(tree.isEmpty());
    }

    // -------------------------------------------------------------------------
    /**
     * Test method for {@link AVLTree#isEmpty()}.
     */
    @Test
    public void testIsEmpty() {

        assertTrue(tree.isEmpty());

        tree.insert(42);

        assertFalse(tree.isEmpty());

        tree.remove(42);

        assertTrue(tree.isEmpty());
    }

    // -------------------------------------------------------------------------
    /**
     * Test method for {@link AVLTree#iterator()}.
     */
    @Test
    public void testIterator() {

        Iterator<Integer> iter = tree.iterator();

        assertNotNull(iter);

        assertFalse(iter.hasNext());

        tree.insert(42);

        iter = tree.iterator();

        assertTrue(iter.hasNext());

        assertEquals(new Integer(42), iter.next());

        assertFalse(iter.hasNext());

        tree.clear();

        tree.insertAll(collection);

        iter = tree.iterator();

        assertTrue(iter.hasNext());
        assertEquals(new Integer(1), iter.next());
        assertTrue(iter.hasNext());
        assertEquals(new Integer(2), iter.next());
        assertTrue(iter.hasNext());
        assertEquals(new Integer(3), iter.next());
        assertTrue(iter.hasNext());
        assertEquals(new Integer(4), iter.next());
        assertTrue(iter.hasNext());
        assertEquals(new Integer(5), iter.next());
        assertTrue(iter.hasNext());
        assertEquals(new Integer(6), iter.next());
        assertTrue(iter.hasNext());
        assertEquals(new Integer(7), iter.next());
        assertTrue(iter.hasNext());
        assertEquals(new Integer(8), iter.next());
        assertTrue(iter.hasNext());
        assertEquals(new Integer(9), iter.next());
        assertTrue(iter.hasNext());
        assertEquals(new Integer(10), iter.next());
        assertTrue(iter.hasNext());
        assertEquals(new Integer(11), iter.next());
        assertTrue(iter.hasNext());
        assertEquals(new Integer(12), iter.next());
        assertTrue(iter.hasNext());
        assertEquals(new Integer(13), iter.next());
        assertTrue(iter.hasNext());
        assertEquals(new Integer(14), iter.next());
        assertTrue(iter.hasNext());
        assertEquals(new Integer(15), iter.next());
        assertTrue(iter.hasNext());
        assertEquals(new Integer(16), iter.next());

        assertFalse(iter.hasNext());
    }

    // -------------------------------------------------------------------------
    /**
     * Test method for {@link AVLTree#toArray()}.
     */
    @Test
    public void testToArray() {

        Integer[] expected = new Integer[] {};

        assertArrayEquals(expected, tree.toArray());

        tree.insertAll(collection);

        expected = new Integer[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,
                14, 15, 16 };

        assertArrayEquals(expected, tree.toArray());
    }

    // -------------------------------------------------------------------------
    /**
     * Test method for {@link AVLTree#toString()}.
     */
    @Test
    public void testToString() {

        tree.insertAll(collection);

        System.out.print(tree);
    }
}