package com.asteele.clrs.data_structures;

import java.util.List;

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

import com.asteele.clrs.ListGenerationUtilities;

import junit.framework.TestCase;

public class AVLTreeTests extends TestCase {

    private static final int NUMBER_OF_ELEMENTS = 10000;

    private List<Integer> sortedList;
    
    private List<Integer> unsortedList;
    
    private List<Integer> reverseList;
    
    
    @Before
    @Override
    public void setUp() {
    	sortedList = ListGenerationUtilities.generateSortedList(NUMBER_OF_ELEMENTS);
    	unsortedList = ListGenerationUtilities.generateUnsortedList(NUMBER_OF_ELEMENTS);
    	reverseList = ListGenerationUtilities.generateReversedList(NUMBER_OF_ELEMENTS);
    }
    
    @Test
    public void testInsertLeftLeft() {
        AVLTree<Integer> tree = new AVLTree<>();
        tree.add(50);
        tree.add(45);
        tree.add(30);
        assertTrue(false); // Not implemented.
        
    }
    
    @Test
    public void testInsertRightRight() {
        AVLTree<Integer> tree = new AVLTree<>();
        tree.add(50);
        tree.add(60);
        tree.add(75);
        assertTrue(false); // Not implemented.
    }
    
    @Test
    public void testInsertRightLeft() {
        AVLTree<Integer> tree = new AVLTree<>();
        tree.add(50);
        tree.add(60);
        tree.add(55);
        assertTrue(false); // Not implemented.
    }
    
    @Test
    public void testInsertLeftRight() {
        AVLTree<Integer> tree = new AVLTree<>();
        tree.add(50);
        tree.add(40);
        tree.add(45);
        assertTrue(false); // Not implemented.
    }
    
    @Test
    public void testSortedOrder() {
        AVLTree<Integer> tree = new AVLTree<>();
        for (Integer e : sortedList) {
            tree.add(e);
        }
        
        assertTrue(tree.size() == sortedList.size());
        
        for (Integer e : sortedList) {
            assertTrue(tree.contains(e));
        }
        
        List<Integer> outputList = new java.util.ArrayList<>();
        tree.inOrderTraversal(outputList);
        assertTrue(com.asteele.clrs.sorting.SortingAlgorithmsTests.verifySorted(outputList));
        
        for (int i = sortedList.size() + 1; i < sortedList.size() * 2; i++) {
            assertTrue(!tree.contains(i));
        }
    }
    
    @Test 
    public void testUnsortedOrder() {
        AVLTree<Integer> tree = new AVLTree<>();
        for (Integer e : unsortedList) {
            tree.add(e);
        }
        
        assertTrue(tree.size() == unsortedList.size());
        
        for (Integer e : unsortedList) {
            assertTrue(tree.contains(e));
        }
        
        List<Integer> outputList = new java.util.ArrayList<>();
        tree.inOrderTraversal(outputList);
        assertTrue(com.asteele.clrs.sorting.SortingAlgorithmsTests.verifySorted(outputList));
    }
    
    @Test
    public void testReverseOrder() {
        AVLTree<Integer> tree = new AVLTree<>();
        for (Integer e : reverseList) {
            tree.add(e);
        }
        
        assertTrue(tree.size() == reverseList.size());
        
        for (Integer e : reverseList) {
            assertTrue(tree.contains(e));
        }
        
        List<Integer> outputList = new java.util.ArrayList<>();
        tree.inOrderTraversal(outputList);
        assertTrue(com.asteele.clrs.sorting.SortingAlgorithmsTests.verifySorted(outputList));
    }

}
