package hw.bst;

import static org.junit.jupiter.api.Assertions.*;
import java.util.ArrayList;
import java.util.List;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

/**
 * Unit tests for the BSTDictionary Class
 *
 * @author CS 240 Instructors
 * @version 11/2025
 */
class BSTDictionaryTest {

  String letters = "THEQUICKBROWNFOXJUMPSOVERTHELAZYDOG";
  BSTDictionary<Character, Integer> tree;

  @BeforeEach
  void setUp() throws Exception {
    tree = new BSTDictionary<>();

    for (int i = 0; i < letters.length(); i++) {
      tree.insert(letters.charAt(i), i);
    }

  }

  @Test
  void testFind() {
    assertEquals(25, tree.find('T'));
    assertEquals(26, tree.find('H'));
    assertEquals(28, tree.find('L'));
    assertNull(tree.find('1'));
    assertEquals(26, tree.size());
  }

  @Test
  void testRemove() {
    assertEquals(25, tree.remove('T'), 25);
    assertEquals(26, tree.remove('H'), 26);
    assertEquals(28, tree.remove('L'), 28);
    assertNull(tree.remove('1'));
    assertEquals(23, tree.size());
  }

  @Test
  void testRemoveAll() {
    int curSize = 26;
    for (int i = 0; i < letters.length(); i++) {
      if (tree.find(letters.charAt(i)) != null) {
        tree.remove(letters.charAt(i));
        curSize--;
      }
      assertEquals(curSize, tree.size());
      System.out.println(letters.charAt(i));
      assertNull(tree.find(letters.charAt(i)));
    }
  }

  @Test
  void testMinKey() {
    String letters = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    for (int i = 0; i < letters.length(); i++) {
      assertEquals(letters.charAt(i), tree.minKey());
      tree.remove(letters.charAt(i));
    }
    assertNull(tree.minKey());
  }

  @Test
  void testMaxKey() {

    String letters = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    for (int i = letters.length() - 1; i >= 0; i--) {
      assertEquals(letters.charAt(i), tree.maxKey());
      tree.remove(letters.charAt(i));
    }
    assertNull(tree.maxKey());
  }

  @Test
  void testHeight() {
    BSTDictionary<Character, Integer> smallTree = new BSTDictionary<>();
    assertEquals(-1, smallTree.height());
    smallTree.insert('R', 10);
    assertEquals(0, smallTree.height());
    smallTree.insert('E', 10);
    assertEquals(1, smallTree.height());
    smallTree.insert('V', 10);
    assertEquals(1, smallTree.height());
    smallTree.insert('C', 10);
    assertEquals(2, smallTree.height());
    smallTree.insert('D', 10);
    assertEquals(3, smallTree.height());
    assertEquals(8, tree.height());
  }

  @Test
  void testToKeyList() {

    // Test an empty tree
    BSTDictionary<Integer, Integer> smallTree = new BSTDictionary<>();
    assertEquals(new ArrayList<Integer>(), smallTree.keyList());

    // Test a tree with one element
    smallTree.insert(23, 56);
    assertEquals(List.of(23), smallTree.keyList());

    // Test our large tree
    String noRepeats = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    ArrayList<Character> keys = new ArrayList<>();
    for (int i = 0; i < noRepeats.length(); i++) {
      keys.add(noRepeats.charAt(i));
    }
    assertEquals(keys, tree.keyList());


    // Remove some elements and test again.
    tree.remove('G');
    tree.remove('H');
    tree.remove('I');
    tree.remove('P');
    tree.remove('Q');
    tree.remove('R');

    noRepeats = "ABCDEFJKLMNOSTUVWXYZ";
    keys = new ArrayList<>();

    for (int i = 0; i < noRepeats.length(); i++) {
      keys.add(noRepeats.charAt(i));
    }
    assertEquals(keys, tree.keyList());
  }

  @Test
  void testRangeSearch() {
    List<Character> result;

    result = tree.rangeSearch('7', '8');
    assertEquals(List.of(), result);

    result = tree.rangeSearch('T', 'T');
    assertEquals(List.of('T'), result);

    result = tree.rangeSearch('L', 'L');
    assertEquals(List.of('L'), result);

    result = tree.rangeSearch('A', 'C');
    assertEquals(List.of('A', 'B', 'C'), result);

    result = tree.rangeSearch('W', 'Z');
    assertEquals(List.of('W', 'X', 'Y', 'Z'), result);

    result = tree.rangeSearch('H', 'P');
    assertEquals(List.of('H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P'), result);
  }

  @Test
  void testIterator() {
    // Test empty tree
    BSTDictionary<Integer, Integer> emptyTree = new BSTDictionary<>();
    List<Integer> keys = new ArrayList<>();
    for (Integer key : emptyTree) {
      keys.add(key);
    }
    assertEquals(List.of(), keys);

    // Test single element
    BSTDictionary<Integer, Integer> singleTree = new BSTDictionary<>();
    singleTree.insert(5, 10);
    keys = new ArrayList<>();
    for (Integer key : singleTree) {
      keys.add(key);
    }
    assertEquals(List.of(5), keys);

    // Test main tree - should iterate in sorted order
    List<Character> treeKeys = new ArrayList<>();
    for (Character key : tree) {
      treeKeys.add(key);
    }
    String noRepeats = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    List<Character> expected = new ArrayList<>();
    for (int i = 0; i < noRepeats.length(); i++) {
      expected.add(noRepeats.charAt(i));
    }
    assertEquals(expected, treeKeys);

    // Test NoSuchElementException on empty tree
    var emptyIterator = emptyTree.iterator();
    assertFalse(emptyIterator.hasNext());
    assertThrows(java.util.NoSuchElementException.class, () -> emptyIterator.next());

    // Test NoSuchElementException after exhausting iterator
    var singleIterator = singleTree.iterator();
    assertTrue(singleIterator.hasNext());
    assertEquals(5, singleIterator.next());
    assertFalse(singleIterator.hasNext());
    assertThrows(java.util.NoSuchElementException.class, () -> singleIterator.next());

    // Test multiple calls to next() beyond end
    assertThrows(java.util.NoSuchElementException.class, () -> singleIterator.next());
  }

  @Test
  void testKeyDepth() {
    // Test with main tree
    assertEquals(0, tree.keyDepth('T')); // Root is at depth 0
    assertEquals(1, tree.keyDepth('H')); // H is left child of T
    assertEquals(5, tree.keyDepth('J'));
    assertEquals(-1, tree.keyDepth('1')); // Key not found
    assertEquals(5, tree.keyDepth('J'));
    assertEquals(5, tree.keyDepth('A'));
    assertEquals(5, tree.keyDepth('Y'));
    assertEquals(5, tree.keyDepth('O'));
    assertEquals(8, tree.keyDepth('L'));


    // Test empty tree
    BSTDictionary<Integer, Integer> emptyTree = new BSTDictionary<>();
    assertEquals(-1, emptyTree.keyDepth(1));
  }

  @Test
  void testNodeDepthHistogram() {
    // Test empty tree
    BSTDictionary<Integer, Integer> emptyTree = new BSTDictionary<>();
    BSTDictionary<Integer, Integer> emptyHist = emptyTree.nodeDepthHistogram();
    assertEquals(0, emptyHist.size());

    // Test single node tree
    BSTDictionary<Integer, String> singleTree = new BSTDictionary<>();
    singleTree.insert(5, "root");
    BSTDictionary<Integer, Integer> singleHist = singleTree.nodeDepthHistogram();
    assertEquals(1, singleHist.size());
    assertEquals(1, singleHist.find(0)); // 1 node at depth 0

    // Test the tree of letters
    BSTDictionary<Integer, Integer> hist = tree.nodeDepthHistogram();
    assertEquals(1, hist.find(0));
    assertEquals(2, hist.find(1));
    assertEquals(3, hist.find(2));
    assertEquals(6, hist.find(3));
    assertEquals(6, hist.find(4));
    assertEquals(4, hist.find(5));
    assertEquals(2, hist.find(6));
    assertEquals(1, hist.find(7));
    assertEquals(1, hist.find(8));
  }


}