// 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.

/**
 * @fileoverview Generic tree node data structure with arbitrary number of child
 * nodes.
 *
 */

goog.provide('goog.structs.TreeNode');

goog.require('goog.array');
goog.require('goog.asserts');
goog.require('goog.structs.Node');



/**
 * Generic tree node data structure with arbitrary number of child nodes.
 * It is possible to create a dynamic tree structure by overriding
 * {@link #getParent} and {@link #getChildren} in a subclass. All other getters
 * will automatically work.
 *
 * @param {KEY} key Key.
 * @param {VALUE} value Value.
 * @constructor
 * @extends {goog.structs.Node<KEY, VALUE>}
 * @template KEY, VALUE
 */
goog.structs.TreeNode = function(key, value) {
  goog.structs.Node.call(this, key, value);

  /**
   * Reference to the parent node or null if it has no parent.
   * @private {goog.structs.TreeNode<KEY, VALUE>}
   */
  this.parent_ = null;

  /**
   * Child nodes or null in case of leaf node.
   * @private {Array<!goog.structs.TreeNode<KEY, VALUE>>}
   */
  this.children_ = null;
};
goog.inherits(goog.structs.TreeNode, goog.structs.Node);


/**
 * Constant for empty array to avoid unnecessary allocations.
 * @private
 */
goog.structs.TreeNode.EMPTY_ARRAY_ = [];


/**
 * @return {!goog.structs.TreeNode} Clone of the tree node without its parent
 *     and child nodes. The key and the value are copied by reference.
 * @override
 */
goog.structs.TreeNode.prototype.clone = function() {
  return new goog.structs.TreeNode(this.getKey(), this.getValue());
};


/**
 * @return {!goog.structs.TreeNode} Clone of the subtree with this node as root.
 */
goog.structs.TreeNode.prototype.deepClone = function() {
  var clone = this.clone();
  this.forEachChild(function(child) { clone.addChild(child.deepClone()); });
  return clone;
};


/**
 * @return {goog.structs.TreeNode<KEY, VALUE>} Parent node or null if it has no
 *     parent.
 */
goog.structs.TreeNode.prototype.getParent = function() {
  return this.parent_;
};


/**
 * @return {boolean} Whether the node is a leaf node.
 */
goog.structs.TreeNode.prototype.isLeaf = function() {
  return !this.getChildCount();
};


/**
 * Tells if the node is the last child of its parent. This method helps how to
 * connect the tree nodes with lines: L shapes should be used before the last
 * children and |- shapes before the rest. Schematic tree visualization:
 *
 * <pre>
 * Node1
 * |-Node2
 * | L-Node3
 * |   |-Node4
 * |   L-Node5
 * L-Node6
 * </pre>
 *
 * @return {boolean} Whether the node has parent and is the last child of it.
 */
goog.structs.TreeNode.prototype.isLastChild = function() {
  var parent = this.getParent();
  return Boolean(parent && this == goog.array.peek(parent.getChildren()));
};


/**
 * @return {!Array<!goog.structs.TreeNode<KEY, VALUE>>} Immutable child nodes.
 */
goog.structs.TreeNode.prototype.getChildren = function() {
  return this.children_ || goog.structs.TreeNode.EMPTY_ARRAY_;
};


/**
 * Gets the child node of this node at the given index.
 * @param {number} index Child index.
 * @return {goog.structs.TreeNode<KEY, VALUE>} The node at the given index or
 *     null if not found.
 */
goog.structs.TreeNode.prototype.getChildAt = function(index) {
  return this.getChildren()[index] || null;
};


/**
 * @return {number} The number of children.
 */
goog.structs.TreeNode.prototype.getChildCount = function() {
  return this.getChildren().length;
};


/**
 * @return {number} The number of ancestors of the node.
 */
goog.structs.TreeNode.prototype.getDepth = function() {
  var depth = 0;
  var node = this;
  while (node.getParent()) {
    depth++;
    node = node.getParent();
  }
  return depth;
};


/**
 * @return {!Array<!goog.structs.TreeNode<KEY, VALUE>>} All ancestor nodes in
 *     bottom-up order.
 */
goog.structs.TreeNode.prototype.getAncestors = function() {
  var ancestors = [];
  var node = this.getParent();
  while (node) {
    ancestors.push(node);
    node = node.getParent();
  }
  return ancestors;
};


/**
 * @return {!goog.structs.TreeNode<KEY, VALUE>} The root of the tree structure,
 *     i.e. the farthest ancestor of the node or the node itself if it has no
 *     parents.
 */
goog.structs.TreeNode.prototype.getRoot = function() {
  var root = this;
  while (root.getParent()) {
    root = root.getParent();
  }
  return root;
};


/**
 * Builds a nested array structure from the node keys in this node's subtree to
 * facilitate testing tree operations that change the hierarchy.
 * @return {!Array<KEY>} The structure of this node's descendants as nested
 *     array of node keys. The number of unclosed opening brackets up to a
 *     particular node is proportional to the indentation of that node in the
 *     graphical representation of the tree. Example:
 *     <pre>
 *       this
 *       |- child1
 *       |  L- grandchild
 *       L- child2
 *     </pre>
 *     is represented as ['child1', ['grandchild'], 'child2'].
 */
goog.structs.TreeNode.prototype.getSubtreeKeys = function() {
  var ret = [];
  this.forEachChild(function(child) {
    ret.push(child.getKey());
    if (!child.isLeaf()) {
      ret.push(child.getSubtreeKeys());
    }
  });
  return ret;
};


/**
 * Tells whether this node is the ancestor of the given node.
 * @param {!goog.structs.TreeNode<KEY, VALUE>} node A node.
 * @return {boolean} Whether this node is the ancestor of {@code node}.
 */
goog.structs.TreeNode.prototype.contains = function(node) {
  var current = node;
  do {
    current = current.getParent();
  } while (current && current != this);
  return Boolean(current);
};


/**
 * Finds the deepest common ancestor of the given nodes. The concept of
 * ancestor is not strict in this case, it includes the node itself.
 * @param {...!goog.structs.TreeNode<KEY, VALUE>} var_args The nodes.
 * @return {goog.structs.TreeNode<KEY, VALUE>} The common ancestor of the nodes
 *     or null if they are from different trees.
 * @template KEY, VALUE
 */
goog.structs.TreeNode.findCommonAncestor = function(var_args) {
  /** @type {goog.structs.TreeNode} */
  var ret = arguments[0];
  if (!ret) {
    return null;
  }

  var retDepth = ret.getDepth();
  for (var i = 1; i < arguments.length; i++) {
    /** @type {goog.structs.TreeNode} */
    var node = arguments[i];
    var depth = node.getDepth();
    while (node != ret) {
      if (depth <= retDepth) {
        ret = ret.getParent();
        retDepth--;
      }
      if (depth > retDepth) {
        node = node.getParent();
        depth--;
      }
    }
  }

  return ret;
};


/**
 * Returns a node whose key matches the given one in the hierarchy rooted at
 * this node. The hierarchy is searched using an in-order traversal.
 * @param {KEY} key The key to search for.
 * @return {goog.structs.TreeNode<KEY, VALUE>} The node with the given key, or
 *     null if no node with the given key exists in the hierarchy.
 */
goog.structs.TreeNode.prototype.getNodeByKey = function(key) {
  if (this.getKey() == key) {
    return this;
  }
  var children = this.getChildren();
  for (var i = 0; i < children.length; i++) {
    var descendant = children[i].getNodeByKey(key);
    if (descendant) {
      return descendant;
    }
  }
  return null;
};


/**
 * Traverses all child nodes.
 * @param {function(this:THIS, !goog.structs.TreeNode<KEY, VALUE>, number,
 *     !Array<!goog.structs.TreeNode<KEY, VALUE>>)} f Callback function. It
 *     takes the node, its index and the array of all child nodes as arguments.
 * @param {THIS=} opt_this The object to be used as the value of {@code this}
 *     within {@code f}.
 * @template THIS
 */
goog.structs.TreeNode.prototype.forEachChild = function(f, opt_this) {
  goog.array.forEach(this.getChildren(), f, opt_this);
};


/**
 * Traverses all child nodes recursively in preorder.
 * @param {function(this:THIS, !goog.structs.TreeNode<KEY, VALUE>)} f Callback
 *     function.  It takes the node as argument.
 * @param {THIS=} opt_this The object to be used as the value of {@code this}
 *     within {@code f}.
 * @template THIS
 */
goog.structs.TreeNode.prototype.forEachDescendant = function(f, opt_this) {
  var children = this.getChildren();
  for (var i = 0; i < children.length; i++) {
    f.call(opt_this, children[i]);
    children[i].forEachDescendant(f, opt_this);
  }
};


/**
 * Traverses the subtree with the possibility to skip branches. Starts with
 * this node, and visits the descendant nodes depth-first, in preorder.
 * @param {function(this:THIS, !goog.structs.TreeNode<KEY, VALUE>):
 *     (boolean|undefined)} f Callback function. It takes the node as argument.
 *     The children of this node will be visited if the callback returns true or
 *     undefined, and will be skipped if the callback returns false.
 * @param {THIS=} opt_this The object to be used as the value of {@code this}
 *     within {@code f}.
 * @template THIS
 */
goog.structs.TreeNode.prototype.traverse = function(f, opt_this) {
  if (f.call(opt_this, this) !== false) {
    var children = this.getChildren();
    for (var i = 0; i < children.length; i++) {
      children[i].traverse(f, opt_this);
    }
  }
};


/**
 * Sets the parent node of this node. The callers must ensure that the parent
 * node and only that has this node among its children.
 * @param {goog.structs.TreeNode<KEY, VALUE>} parent The parent to set. If
 *     null, the node will be detached from the tree.
 * @protected
 */
goog.structs.TreeNode.prototype.setParent = function(parent) {
  this.parent_ = parent;
};


/**
 * Appends a child node to this node.
 * @param {!goog.structs.TreeNode<KEY, VALUE>} child Orphan child node.
 */
goog.structs.TreeNode.prototype.addChild = function(child) {
  this.addChildAt(child, this.children_ ? this.children_.length : 0);
};


/**
 * Inserts a child node at the given index.
 * @param {!goog.structs.TreeNode<KEY, VALUE>} child Orphan child node.
 * @param {number} index The position to insert at.
 */
goog.structs.TreeNode.prototype.addChildAt = function(child, index) {
  goog.asserts.assert(!child.getParent());
  child.setParent(this);
  this.children_ = this.children_ || [];
  goog.asserts.assert(index >= 0 && index <= this.children_.length);
  goog.array.insertAt(this.children_, child, index);
};


/**
 * Replaces a child node at the given index.
 * @param {!goog.structs.TreeNode<KEY, VALUE>} newChild Child node to set. It
 *     must not have parent node.
 * @param {number} index Valid index of the old child to replace.
 * @return {!goog.structs.TreeNode<KEY, VALUE>} The original child node,
 *     detached from its parent.
 */
goog.structs.TreeNode.prototype.replaceChildAt = function(newChild, index) {
  goog.asserts.assert(
      !newChild.getParent(), 'newChild must not have parent node');
  var children = this.getChildren();
  var oldChild = children[index];
  goog.asserts.assert(oldChild, 'Invalid child or child index is given.');
  oldChild.setParent(null);
  children[index] = newChild;
  newChild.setParent(this);
  return oldChild;
};


/**
 * Replaces the given child node.
 * @param {!goog.structs.TreeNode<KEY, VALUE>} newChild New node to replace
 *     {@code oldChild}. It must not have parent node.
 * @param {!goog.structs.TreeNode<KEY, VALUE>} oldChild Existing child node to
 *     be replaced.
 * @return {!goog.structs.TreeNode<KEY, VALUE>} The replaced child node
 *     detached from its parent.
 */
goog.structs.TreeNode.prototype.replaceChild = function(newChild, oldChild) {
  return this.replaceChildAt(
      newChild, goog.array.indexOf(this.getChildren(), oldChild));
};


/**
 * Removes the child node at the given index.
 * @param {number} index The position to remove from.
 * @return {goog.structs.TreeNode<KEY, VALUE>} The removed node if any.
 */
goog.structs.TreeNode.prototype.removeChildAt = function(index) {
  var child = this.children_ && this.children_[index];
  if (child) {
    child.setParent(null);
    goog.array.removeAt(this.children_, index);
    if (this.children_.length == 0) {
      this.children_ = null;
    }
    return child;
  }
  return null;
};


/**
 * Removes the given child node of this node.
 * @param {goog.structs.TreeNode<KEY, VALUE>} child The node to remove.
 * @return {goog.structs.TreeNode<KEY, VALUE>} The removed node if any.
 */
goog.structs.TreeNode.prototype.removeChild = function(child) {
  return child &&
      this.removeChildAt(goog.array.indexOf(this.getChildren(), child));
};


/**
 * Removes all child nodes of this node.
 */
goog.structs.TreeNode.prototype.removeChildren = function() {
  if (this.children_) {
    for (var i = 0; i < this.children_.length; i++) {
      this.children_[i].setParent(null);
    }
    this.children_ = null;
  }
};