// Copyright 2010 The Closure Library Authors. All Rights Reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS-IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

goog.provide('goog.structs.TreeNodeTest');
goog.setTestOnly('goog.structs.TreeNodeTest');

goog.require('goog.structs.TreeNode');
goog.require('goog.testing.jsunit');

function testConstructor() {
  var node = new goog.structs.TreeNode('key', 'value');
  assertEquals('key', 'key', node.getKey());
  assertEquals('value', 'value', node.getValue());
  assertNull('parent', node.getParent());
  assertArrayEquals('children', [], node.getChildren());
  assertTrue('leaf', node.isLeaf());
}

function testClone() {
  var node1 = new goog.structs.TreeNode(1, '1');
  var node2 = new goog.structs.TreeNode(2, '2');
  var node3 = new goog.structs.TreeNode(3, '3');
  node1.addChild(node2);
  node2.addChild(node3);

  var clone = node2.clone();
  assertEquals('key', 2, clone.getKey());
  assertEquals('value', '2', clone.getValue());
  assertNull('parent', clone.getParent());
  assertArrayEquals('children', [], clone.getChildren());
}

function testDeepClone() {
  var node1 = new goog.structs.TreeNode(1, '1');
  var node2 = new goog.structs.TreeNode(2, '2');
  var node3 = new goog.structs.TreeNode(3, '3');
  node1.addChild(node2);
  node2.addChild(node3);

  var clone = node2.deepClone();
  assertEquals('key', 2, clone.getKey());
  assertEquals('value', '2', clone.getValue());
  assertNull('parent', clone.getParent());
  assertEquals('number of children', 1, clone.getChildren().length);
  assertEquals('first child key', 3, clone.getChildAt(0).getKey());
  assertNotEquals('first child has been cloned', node3, clone.getChildAt(0));
}

function testGetParent() {
  var node1 = new goog.structs.TreeNode(1, null);
  var node2 = new goog.structs.TreeNode(2, null);
  node1.addChild(node2);
  assertEquals('parent', node1, node2.getParent());
  assertNull('orphan', node1.getParent());
}

function testIsLeaf() {
  var node1 = new goog.structs.TreeNode(1, null);
  var node2 = new goog.structs.TreeNode(2, null);
  node1.addChild(node2);
  assertFalse('not leaf', node1.isLeaf());
  assertTrue('leaf', node2.isLeaf());
}

function testIsLastChild() {
  var node1 = new goog.structs.TreeNode(1, '1');
  var node2 = new goog.structs.TreeNode(2, '2');
  var node3 = new goog.structs.TreeNode(3, '3');
  node1.addChild(node2);
  node1.addChild(node3);
  assertFalse('root', node1.isLastChild());
  assertFalse('first child out of the two', node2.isLastChild());
  assertTrue('second child out of the two', node3.isLastChild());
}

function testGetChildren() {
  var node1 = new goog.structs.TreeNode(1, null);
  var node2 = new goog.structs.TreeNode(2, null);
  node1.addChild(node2);
  assertArrayEquals('1 child', [node2], node1.getChildren());
  assertArrayEquals('no children', [], node2.getChildren());
}

function testGetChildAt() {
  var node1 = new goog.structs.TreeNode(1, null);
  var node2 = new goog.structs.TreeNode(2, null);
  node1.addChild(node2);
  assertNull('index too low', node1.getChildAt(-1));
  assertEquals('first child', node2, node1.getChildAt(0));
  assertNull('index too high', node1.getChildAt(1));
  assertNull('no children', node2.getChildAt(0));
}

function testGetChildCount() {
  var node1 = new goog.structs.TreeNode(1, null);
  var node2 = new goog.structs.TreeNode(2, null);
  node1.addChild(node2);
  assertEquals('child count of root node', 1, node1.getChildCount());
  assertEquals('child count of leaf node', 0, node2.getChildCount());
}

function testGetDepth() {
  var node1 = new goog.structs.TreeNode(1, null);
  var node2 = new goog.structs.TreeNode(2, null);
  var node3 = new goog.structs.TreeNode(3, null);
  node1.addChild(node2);
  node2.addChild(node3);
  assertEquals('no parent', 0, node1.getDepth());
  assertEquals('1 ancestor', 1, node2.getDepth());
  assertEquals('2 ancestors', 2, node3.getDepth());
}

function testGetAncestors() {
  var node1 = new goog.structs.TreeNode(1, null);
  var node2 = new goog.structs.TreeNode(2, null);
  var node3 = new goog.structs.TreeNode(3, null);
  node1.addChild(node2);
  node2.addChild(node3);
  assertArrayEquals('no ancestors', [], node1.getAncestors());
  assertArrayEquals('2 ancestors', [node2, node1], node3.getAncestors());
}

function testGetRoot() {
  var node1 = new goog.structs.TreeNode(1, null);
  var node2 = new goog.structs.TreeNode(2, null);
  node1.addChild(node2);
  assertEquals('no ancestors', node1, node1.getRoot());
  assertEquals('has ancestors', node1, node2.getRoot());
}

function testGetSubtreeKeys() {
  var root = new goog.structs.TreeNode('root', null);
  var child1 = new goog.structs.TreeNode('child1', null);
  var child2 = new goog.structs.TreeNode('child2', null);
  var grandchild = new goog.structs.TreeNode('grandchild', null);
  root.addChild(child1);
  root.addChild(child2);
  child1.addChild(grandchild);
  assertArrayEquals(
      'node hierarchy', ['child1', ['grandchild'], 'child2'],
      root.getSubtreeKeys());
}

function testContains() {
  var node1 = new goog.structs.TreeNode(1, null);
  var node2 = new goog.structs.TreeNode(2, null);
  var node3 = new goog.structs.TreeNode(3, null);
  var node4 = new goog.structs.TreeNode(4, null);
  node1.addChild(node2);
  node2.addChild(node3);
  node2.addChild(node4);

  assertTrue('parent', node1.contains(node2));
  assertTrue('grandparent', node1.contains(node3));
  assertFalse('child', node2.contains(node1));
  assertFalse('grandchild', node3.contains(node1));
  assertFalse('sibling', node3.contains(node4));
}

function testFindCommonAncestor() {
  var findCommonAncestor = goog.structs.TreeNode.findCommonAncestor;
  var node1 = new goog.structs.TreeNode(1, null);
  var node2 = new goog.structs.TreeNode(2, null);
  var node3 = new goog.structs.TreeNode(3, null);
  var node4 = new goog.structs.TreeNode(4, null);
  var node5 = new goog.structs.TreeNode(5, null);
  node1.addChild(node2);
  node2.addChild(node3);
  node1.addChild(node4);

  assertNull('0 nodes', findCommonAncestor());
  assertEquals('1 node', node2, findCommonAncestor(node2));
  assertEquals('same nodes', node3, findCommonAncestor(node3, node3));
  assertEquals('node and child node', node2, findCommonAncestor(node2, node3));
  assertEquals('node and parent node', node1, findCommonAncestor(node2, node1));
  assertEquals('siblings', node1, findCommonAncestor(node2, node4));
  assertEquals(
      'all nodes', node1, findCommonAncestor(node2, node3, node4, node1));
  assertNull('disconnected nodes', findCommonAncestor(node3, node5));
}

function testGetNodeByKey() {
  var node1 = new goog.structs.TreeNode(1, null);
  var node2 = new goog.structs.TreeNode(2, null);
  var node3 = new goog.structs.TreeNode(3, null);
  var node4 = new goog.structs.TreeNode(4, null);
  var node5 = new goog.structs.TreeNode(2, null);
  var node6 = new goog.structs.TreeNode(3, null);
  node1.addChild(node2);
  node2.addChild(node3);
  node1.addChild(node4);
  node4.addChild(node5);
  node1.addChild(node6);

  assertEquals('root', node1, node1.getNodeByKey(1));
  assertEquals('child with unique key', node5, node4.getNodeByKey(2));
  assertEquals('child with duplicate keys', node2, node1.getNodeByKey(2));
  assertEquals('grandchild with duplicate keys', node3, node1.getNodeByKey(3));
  assertNull('disconnected', node2.getNodeByKey(4));
  assertNull('missing', node1.getNodeByKey(5));
}

function testForEachChild() {
  var node1 = new goog.structs.TreeNode(1, null);
  var node2 = new goog.structs.TreeNode(2, null);
  var node3 = new goog.structs.TreeNode(3, null);
  node1.addChild(node2);
  node1.addChild(node3);

  var thisContext = {};
  var visitedNodes = [];
  var indices = [];
  node1.forEachChild(function(node, index, children) {
    assertEquals('value of this', thisContext, this);
    visitedNodes.push(node);
    indices.push(index);
    assertArrayEquals('children argument', [node2, node3], children);
  }, thisContext);
  assertArrayEquals('visited nodes', [node2, node3], visitedNodes);
  assertArrayEquals('index of visited nodes', [0, 1], indices);
}

function testForEachDescendant() {
  var node1 = new goog.structs.TreeNode(1, null);
  var node2 = new goog.structs.TreeNode(2, null);
  var node3 = new goog.structs.TreeNode(3, null);
  var node4 = new goog.structs.TreeNode(4, null);
  node1.addChild(node2);
  node2.addChild(node3);
  node2.addChild(node4);

  var thisContext = {};
  var visitedNodes = [];
  node1.forEachDescendant(function(node) {
    assertEquals('value of this', thisContext, this);
    visitedNodes.push(node);
  }, thisContext);
  assertArrayEquals('visited nodes', [node2, node3, node4], visitedNodes);
}

function testTraverse() {
  var node1 = new goog.structs.TreeNode(1, null);
  var node2 = new goog.structs.TreeNode(2, null);
  var node3 = new goog.structs.TreeNode(3, null);
  var node4 = new goog.structs.TreeNode(4, null);
  node1.addChild(node2);
  node2.addChild(node3);
  node2.addChild(node4);

  var thisContext = {};
  var visitedNodes = [];
  node1.traverse(function(node) {
    assertEquals('value of this', thisContext, this);
    visitedNodes.push(node);
  }, thisContext);
  assertArrayEquals(
      'callback returns nothing => all nodes are visited',
      [node1, node2, node3, node4], visitedNodes);

  visitedNodes = [];
  node1.traverse(function(node) {
    visitedNodes.push(node);
    return node != node2;  // Cut off at node2.
  });
  assertArrayEquals(
      'children of node2 are skipped', [node1, node2], visitedNodes);
}

function testAddChild() {
  var node1 = new goog.structs.TreeNode(1, null);
  var node2 = new goog.structs.TreeNode(2, null);
  var node3 = new goog.structs.TreeNode(3, null);
  assertArrayEquals('0 children', [], node1.getChildren());
  node1.addChild(node2);
  assertArrayEquals('1 child', [node2], node1.getChildren());
  assertEquals('parent is set', node1, node2.getParent());
  node1.addChild(node3);
  assertArrayEquals('2 children', [node2, node3], node1.getChildren());
}

function testAddChildAt() {
  var node1 = new goog.structs.TreeNode(1, null);
  var node2 = new goog.structs.TreeNode(2, null);
  var node3 = new goog.structs.TreeNode(3, null);
  var node4 = new goog.structs.TreeNode(4, null);
  var node5 = new goog.structs.TreeNode(5, null);
  node1.addChildAt(node2, 0);
  assertArrayEquals('add first child', [node2], node1.getChildren());
  assertEquals('parent is set', node1, node2.getParent());
  node1.addChildAt(node3, 0);
  assertArrayEquals('add to the front', [node3, node2], node1.getChildren());
  node1.addChildAt(node4, 1);
  assertArrayEquals(
      'add to the middle', [node3, node4, node2], node1.getChildren());
  node1.addChildAt(node5, 3);
  assertArrayEquals(
      'add to the end', [node3, node4, node2, node5], node1.getChildren());
}

function testReplaceChildAt() {
  var root = new goog.structs.TreeNode(0, null);
  var node1 = new goog.structs.TreeNode(1, null);
  root.addChild(node1);

  var node2 = new goog.structs.TreeNode(2, null);
  assertEquals('original node', node1, root.replaceChildAt(node2, 0));
  assertEquals('parent is set', root, node2.getParent());
  assertArrayEquals('children are updated', [node2], root.getChildren());
  assertNull('old child node is detached', node1.getParent());
}

function testReplaceChild() {
  var root = new goog.structs.TreeNode(0, null);
  var node1 = new goog.structs.TreeNode(1, null);
  root.addChild(node1);

  var node2 = new goog.structs.TreeNode(2, null);
  assertEquals('original node', node1, root.replaceChild(node2, node1));
  assertEquals('parent is set', root, node2.getParent());
  assertArrayEquals('children are updated', [node2], root.getChildren());
  assertNull('old child node is detached', node1.getParent());
}

function testRemoveChildAt() {
  var node1 = new goog.structs.TreeNode(1, null);
  var node2 = new goog.structs.TreeNode(2, null);
  var node3 = new goog.structs.TreeNode(3, null);
  node1.addChild(node2);
  node1.addChild(node3);

  assertNull('index too low', node1.removeChildAt(-1));
  assertNull('index too high', node1.removeChildAt(2));
  assertArrayEquals('node1 is intact', [node2, node3], node1.getChildren());

  assertEquals('remove first child', node2, node1.removeChildAt(0));
  assertArrayEquals('remove from the front', [node3], node1.getChildren());
  assertNull('parent is unset', node2.getParent());

  assertEquals('remove last child', node3, node1.removeChildAt(0));
  assertArrayEquals('remove last child', [], node1.getChildren());
  assertTrue('node1 became leaf', node1.isLeaf());
}

function testRemoveChild() {
  var node1 = new goog.structs.TreeNode(1, null);
  var node2 = new goog.structs.TreeNode(2, null);
  var node3 = new goog.structs.TreeNode(3, null);
  node1.addChild(node2);
  node1.addChild(node3);

  assertNull('remove null', node1.removeChild(null));
  assertNull('remove non-child', node1.removeChild(node1));
  assertArrayEquals('node1 is intact', [node2, node3], node1.getChildren());

  assertEquals('remove node3, return value', node3, node1.removeChild(node3));
  assertArrayEquals('node is removed', [node2], node1.getChildren());
}

function testRemoveChildren() {
  var node1 = new goog.structs.TreeNode(1, null);
  var node2 = new goog.structs.TreeNode(2, null);
  var node3 = new goog.structs.TreeNode(3, null);
  node1.addChild(node2);
  node1.addChild(node3);

  node2.removeChildren();
  assertArrayEquals(
      'removing a leaf node\'s children has no effect', [],
      node2.getChildren());
  assertEquals('node still has parent', node1, node2.getParent());

  node1.removeChildren();
  assertArrayEquals('children have been removed', [], node1.getChildren());
  assertNull('children\'s parents have been unset', node2.getParent());
}