import 'mocha';
import { expect } from 'chai';
import { AVLTree } from '../../../src/ts/index';

describe('AVLTree', () => {
  let tree: AVLTree<number>;

  beforeEach(() => {
    tree = new AVLTree<number>();
  });

  it('starts empty', () => {
    expect(tree.getRoot()).to.equal(null);
  });

  function assertNode(node: any, key: number, left: number, right: number) {

    if (key != null) {
      expect(node.key).to.equal(key);
    } else {
      expect(node).to.equal(key);
      return;
    }

    if (left != null) {
      expect(node.left.key).to.equal(left);
    } else {
      expect(node.left).to.equal(left);
    }

    if (right != null) {
      expect(node.right.key).to.equal(right);
    } else {
      expect(node.right).to.equal(right);
    }
  }

  it('inserts elements in the AVLTree', () => {
    expect(tree.getRoot()).to.equal(null);

    tree.insert(11);
    tree.insert(7);
    tree.insert(16);
    tree.insert(5);
    tree.insert(3);
    /*
      3插入时，7不平衡，然后AVL会自动平衡（验证左-左）
            11              11
           /  \            /  \
          7   16          5    16
         /         ——>   / \
        5               3   7
       /
      3

    */
    let node = tree.getRoot();
    assertNode(node, 11, 5, 16);
    assertNode(node.left, 5, 3, 7);
    assertNode(node.right, 16, null, null);

    tree.insert(9);
    /*
      9插入时，11不平衡，然后AVL会自动平衡（验证左-右）
           11               7
          /  \             / \
         5   16           5   11
        / \       ——>    /    / \
       3   7            3    9  16
            \
             9
    */
    node = tree.getRoot();
    assertNode(node, 7, 5, 11);
    assertNode(node.left, 5, 3, null);
    assertNode(node.right, 11, 9, 16);

    tree.insert(8);
    tree.insert(10);
    tree.insert(13);
    tree.insert(12);
    /*
      12插入时，16不平衡，然后AVL会自动平衡（验证左-左）
             7                7
            / \              / \
           5   11           5   11
          /    / \         /    / \
         3    9  16  ——>  3    9   13
             /\  /             /\   /\
            8 10 13           8 10 12 16
                 /
                12
    */
    node = tree.getRoot();
    assertNode(node, 7, 5, 11);
    assertNode(node.left, 5, 3, null);
    assertNode(node.right, 11, 9, 13);
    assertNode(node.right.left, 9, 8, 10);
    assertNode(node.right.right, 13, 12, 16);

    tree.insert(14);
    /*
      14插入时，7不平衡，然后AVL会自动平衡（验证右-右）
             7                  11
            / \                /  \
           5   11             7    13
          /    / \           / \   / \
         3    9   13        5   9 12  16
             /\   /\       /   / \    /
            8 10 12 16    3   8  10  14
                    /
                   14
    */
    node = tree.getRoot();
    assertNode(node, 11, 7, 13);
    assertNode(node.left, 7, 5, 9);
    assertNode(node.left.left, 5, 3, null);
    assertNode(node.left.right, 9, 8, 10);
    assertNode(node.right, 13, 12, 16);
    assertNode(node.right.left, 12, null, null);
    assertNode(node.right.right, 16, 14, null);

    tree.insert(20);
    tree.insert(15);
    /*
      15插入时，13不平衡，然后AVL会自动平衡（验证右-左）
              11                     11
             /  \                   /   \
            7    13               7      14
           / \   / \             / \     / \
          5   9 12  16   ——>    5  9    13  16
         /   / \    / \        /  / \   /   / \
        3   8  10  14 20      3  8  10 12  15 20
                    \
                     15
    */
    node = tree.getRoot();
    assertNode(node, 11, 7, 14);
    assertNode(node.left, 7, 5, 9);
    assertNode(node.left.left, 5, 3, null);
    assertNode(node.left.right, 9, 8, 10);
    assertNode(node.right, 14, 13, 16);
    assertNode(node.right.left, 13, 12, null);
    assertNode(node.right.right, 16, 15, 20);
  });

  it('removes elements in the AVLTree', () => {
    expect(tree.getRoot()).to.equal(null);

    tree.insert(11);
    tree.insert(7);
    tree.insert(16);
    tree.insert(5);
    tree.insert(3);
    tree.insert(9);
    tree.insert(8);
    tree.insert(10);
    tree.insert(13);
    tree.insert(12);
    tree.insert(14);
    tree.insert(20);
    tree.insert(15);
    /*
      最后的结果呈现
               11
              /   \
            7      14
           / \     / \
          5  9    13  16
         /  / \   /   / \
        3  8  10 12  15 20
    */
    let node = tree.getRoot();
    assertNode(node, 11, 7, 14);
    assertNode(node.left, 7, 5, 9);
    assertNode(node.left.left, 5, 3, null);
    assertNode(node.left.right, 9, 8, 10);
    assertNode(node.right, 14, 13, 16);
    assertNode(node.right.left, 13, 12, null);
    assertNode(node.right.right, 16, 15, 20);

    // 开始删除元素
    tree.remove(12);
    tree.remove(13);
    /*
      删除12没问题，再删除13时，14会不平衡，然后AVL会自动平衡。
      是为了验证右-右时node.right的平衡因子为0时的场景（这里的node是14）
              11                     11
             /   \                  /  \
           7      14               7    16
          / \     - \      ——>    / \   / \
         5  9    13  16          5  9  14  20
        /  / \   -   / \        /  / \  \
       3  8  10 12  15 20      3  8  10  15
    */
    node = tree.getRoot();
    assertNode(node, 11, 7, 16);
    assertNode(node.left, 7, 5, 9);
    assertNode(node.left.left, 5, 3, null);
    assertNode(node.left.right, 9, 8, 10);
    assertNode(node.right, 16, 14, 20);
    assertNode(node.right.left, 14, null, 15);

    tree.remove(20);
    /*
      删除20时，16会不平衡，然后AVL会自动平衡（验证左-右）
             11                    11
            /  \                  /  \
           7    16               7    15
          / \   / -      ——>    / \   / \
         5  9  14  20          5   9  14 16
        /  / \  \             /   / \
       3  8  10  15          3   8   10
    */
    node = tree.getRoot();
    assertNode(node, 11, 7, 15);
    assertNode(node.left, 7, 5, 9);
    assertNode(node.left.left, 5, 3, null);
    assertNode(node.left.right, 9, 8, 10);
    assertNode(node.right, 15, 14, 16);

    tree.remove(7);
    /*
      删除7，单纯为了验证删除一个节点，这个节点同时拥有左右子树时，
      它会去这个节点的右子树里寻找最小的节点来替代删除后腾出的位置，也就是8会替代7
             11                    11
            /  \                  /  \
           7    15               8    15
          / \   / \      ——>    / \   / \
         5  9  14  16          5   9  14 16
        /  / \                /     \
       3  8  10              3       10
    */
    node = tree.getRoot();
    assertNode(node, 11, 8, 15);
    assertNode(node.left, 8, 5, 9);
    assertNode(node.left.left, 5, 3, null);
    assertNode(node.left.right, 9, null, 10);
    assertNode(node.right, 15, 14, 16);

    tree.remove(14);
    tree.remove(16);
    /*
      删除14没问题，再删除16时，11会不平衡，然后AVL会自动平衡。
      是为了验证左-左时node.left的平衡因子为0时的场景（这里的node是11）
             11                    8
            /  \                  /  \
           8    15               5    11
          / \   - -      ——>    /     / \
         5  9  14  16          3     9   15
        /    \                        \
       3     10                        10
    */
    node = tree.getRoot();
    assertNode(node, 8, 5, 11);
    assertNode(node.left, 5, 3, null);
    assertNode(node.right, 11, 9, 15);
    assertNode(node.right.left, 9, null, 10);

    tree.remove(3);
    /*
      删除3时，8会不平衡，然后AVL会自动平衡。（验证右-左）
             8                    9
            /  \                 / \
           5    11              8   11
          -     / \     ——>    /   /  \
         3     9   15         5   10   15
                \
                 10
    */
    node = tree.getRoot();
    assertNode(node, 9, 8, 11);
    assertNode(node.left, 8, 5, null);
    assertNode(node.right, 11, 10, 15);
  });
});