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 SkipList}.
 * 
 * @author Michael D. Naper, Jr. <MichaelNaper.com>
 * @version 2010.07.14
 */
public class SkipListTest {

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

    private SkipList<Integer> list;

    private LinkedList<Integer> collection;

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

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

        list = new SkipList<Integer>();

        collection = new LinkedList<Integer>();

        collection.add(31);
        collection.add(41);
        collection.add(59);
        collection.add(26);
        collection.add(53);
        collection.add(58);
        collection.add(97);
        collection.add(93);
        collection.add(23);
        collection.add(84);
    }

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

        assertNotNull(list);

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

    // -------------------------------------------------------------------------
    /**
     * Test method for {@link SkipList#add(java.lang.Comparable)}.
     */
    @Test
    public void testAdd() {

        assertTrue(list.add(42));
        assertEquals(1, list.size());
        assertFalse(list.add(42));

        assertTrue(list.add(31));
        assertEquals(2, list.size());
        assertFalse(list.add(31));

        assertTrue(list.add(27));
        assertEquals(3, list.size());
        assertFalse(list.add(27));

        assertTrue(list.add(41));
        assertEquals(4, list.size());
        assertFalse(list.add(41));

        assertTrue(list.add(59));
        assertEquals(5, list.size());
        assertFalse(list.add(59));

        assertFalse(list.add(42));
        assertFalse(list.add(31));
        assertFalse(list.add(27));
        assertFalse(list.add(41));
    }

    // -------------------------------------------------------------------------
    /**
     * Test method for {@link SkipList#addAll(java.util.Collection)}.
     */
    @Test
    public void testAddAll() {

        assertTrue(list.addAll(collection));

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

        assertFalse(list.addAll(collection));

        list.clear();

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

        assertTrue(list.addAll(collection));

        assertFalse(list.addAll(collection));
    }

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

        assertFalse(list.contains(42));
        list.add(42);
        assertTrue(list.contains(42));

        assertFalse(list.contains(31));
        list.add(31);
        assertTrue(list.contains(31));

        assertFalse(list.contains(27));
        list.add(27);
        assertTrue(list.contains(27));

        assertFalse(list.contains(41));
        list.add(41);
        assertTrue(list.contains(41));

        assertFalse(list.contains(59));
        list.add(59);
        assertTrue(list.contains(59));
    }

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

        assertFalse(list.containsAll(collection));

        list.addAll(collection);

        assertTrue(list.containsAll(collection));

        list.clear();

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

        assertFalse(list.containsAll(collection));

        list.add(collection.getLast());

        assertTrue(list.containsAll(collection));
    }

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

        assertNull(list.find(42));
        list.add(42);
        assertNotNull(list.find(42));
        assertEquals(new Integer(42), list.find(42));

        assertNull(list.find(31));
        list.add(31);
        assertNotNull(list.find(31));
        assertEquals(new Integer(31), list.find(31));

        assertNull(list.find(27));
        list.add(27);
        assertNotNull(list.find(27));
        assertEquals(new Integer(27), list.find(27));

        assertNull(list.find(41));
        list.add(41);
        assertNotNull(list.find(41));
        assertEquals(new Integer(41), list.find(41));

        assertNull(list.find(59));
        list.add(59);
        assertNotNull(list.find(59));
        assertEquals(new Integer(59), list.find(59));
    }

    // -------------------------------------------------------------------------
    /**
     * Test method for {@link SkipList#indexOf(java.lang.Comparable)}.
     */
    @Test
    public void testIndexOf() {

        assertEquals(-1, list.indexOf(42));

        list.add(41);

        assertEquals(0, list.indexOf(41));

        list.add(84);

        assertEquals(1, list.indexOf(84));

        list.addAll(collection);

        assertEquals(0, list.indexOf(23));
        assertEquals(1, list.indexOf(26));
        assertEquals(2, list.indexOf(31));
        assertEquals(3, list.indexOf(41));
        assertEquals(4, list.indexOf(53));
        assertEquals(5, list.indexOf(58));
        assertEquals(6, list.indexOf(59));
        assertEquals(7, list.indexOf(84));
        assertEquals(8, list.indexOf(93));
        assertEquals(9, list.indexOf(97));

        list.remove(23);

        assertEquals(-1, list.indexOf(23));
        assertEquals(0, list.indexOf(26));
        assertEquals(1, list.indexOf(31));
        assertEquals(2, list.indexOf(41));
        assertEquals(3, list.indexOf(53));
        assertEquals(4, list.indexOf(58));
        assertEquals(5, list.indexOf(59));
        assertEquals(6, list.indexOf(84));
        assertEquals(7, list.indexOf(93));
        assertEquals(8, list.indexOf(97));
    }

    // -------------------------------------------------------------------------
    /**
     * Test method for {@link SkipList#get(int)}.
     */
    @Test
    public void testGet() {

        list.add(41);

        assertEquals(new Integer(41), list.get(0));

        list.add(84);

        assertEquals(new Integer(84), list.get(1));

        list.addAll(collection);

        assertEquals(new Integer(23), list.get(0));
        assertEquals(new Integer(26), list.get(1));
        assertEquals(new Integer(31), list.get(2));
        assertEquals(new Integer(41), list.get(3));
        assertEquals(new Integer(53), list.get(4));
        assertEquals(new Integer(58), list.get(5));
        assertEquals(new Integer(59), list.get(6));
        assertEquals(new Integer(84), list.get(7));
        assertEquals(new Integer(93), list.get(8));
        assertEquals(new Integer(97), list.get(9));

        list.remove(23);

        assertEquals(new Integer(26), list.get(0));
        assertEquals(new Integer(31), list.get(1));
        assertEquals(new Integer(41), list.get(2));
        assertEquals(new Integer(53), list.get(3));
        assertEquals(new Integer(58), list.get(4));
        assertEquals(new Integer(59), list.get(5));
        assertEquals(new Integer(84), list.get(6));
        assertEquals(new Integer(93), list.get(7));
        assertEquals(new Integer(97), list.get(8));
    }

    // -------------------------------------------------------------------------
    /**
     * Test method for {@link SkipList#getMin()}.
     */
    @Test
    public void testGetMin() {

        assertNull(list.getMin());

        list.addAll(collection);

        assertEquals(new Integer(23), list.getMin());

        list.remove(23);

        assertEquals(new Integer(26), list.getMin());
    }

    // -------------------------------------------------------------------------
    /**
     * Test method for {@link SkipList#getMax()}.
     */
    @Test
    public void testGetMax() {

        assertNull(list.getMax());

        list.addAll(collection);

        assertEquals(new Integer(97), list.getMax());

        list.remove(97);

        assertEquals(new Integer(93), list.getMax());
    }

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

        assertFalse(list.remove(42));

        list.add(42);

        assertEquals(1, list.size());

        assertTrue(list.remove(42));

        assertEquals(0, list.size());

        assertFalse(list.contains(42));
    }

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

        assertFalse(list.removeAll(collection));

        list.add(42);

        assertFalse(list.removeAll(collection));

        list.addAll(collection);

        assertTrue(list.removeAll(collection));

        assertEquals(1, list.size());

        list.clear();

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

        assertTrue(list.removeAll(collection));

        assertEquals(0, list.size());

        assertFalse(list.removeAll(collection));
    }

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

        assertNull(list.removeMin());

        list.addAll(collection);

        assertEquals(new Integer(23), list.removeMin());

        assertFalse(list.contains(23));

        assertEquals(new Integer(26), list.removeMin());

        assertFalse(list.contains(26));
    }

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

        assertNull(list.removeMax());

        list.addAll(collection);

        assertEquals(new Integer(97), list.removeMax());

        assertFalse(list.contains(97));

        assertEquals(new Integer(93), list.removeMax());

        assertFalse(list.contains(93));
    }

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

        list.addAll(collection);

        assertFalse(list.isEmpty());

        list.clear();

        assertTrue(list.isEmpty());
    }

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

        assertTrue(list.isEmpty());

        list.add(42);

        assertFalse(list.isEmpty());

        list.remove(42);

        assertTrue(list.isEmpty());
    }

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

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

        assertNotNull(iter);

        assertFalse(iter.hasNext());

        list.add(42);

        iter = list.iterator();

        assertTrue(iter.hasNext());

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

        assertFalse(iter.hasNext());

        list.clear();

        list.addAll(collection);

        iter = list.iterator();

        assertTrue(iter.hasNext());
        assertEquals(new Integer(23), iter.next());
        assertTrue(iter.hasNext());
        assertEquals(new Integer(26), iter.next());
        assertTrue(iter.hasNext());
        assertEquals(new Integer(31), iter.next());
        assertTrue(iter.hasNext());
        assertEquals(new Integer(41), iter.next());
        assertTrue(iter.hasNext());
        assertEquals(new Integer(53), iter.next());
        assertTrue(iter.hasNext());
        assertEquals(new Integer(58), iter.next());
        assertTrue(iter.hasNext());
        assertEquals(new Integer(59), iter.next());
        assertTrue(iter.hasNext());
        assertEquals(new Integer(84), iter.next());
        assertTrue(iter.hasNext());
        assertEquals(new Integer(93), iter.next());
        assertTrue(iter.hasNext());
        assertEquals(new Integer(97), iter.next());

        assertFalse(iter.hasNext());
    }

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

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

        assertArrayEquals(expected, list.toArray());

        list.addAll(collection);

        expected = new Integer[] { 23, 26, 31, 41, 53, 58, 59, 84, 93, 97 };

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

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

        list.addAll(collection);

        System.out.print(list);
    }
}