/*******************************************************************************
 * Copyright (c) 2000, 2006 IBM Corporation and others.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors:
 *     IBM Corporation - initial API and implementation
 *******************************************************************************/
package org.eclipse.core.internal.dtree;

import org.eclipse.core.internal.utils.*;
import org.eclipse.core.runtime.Assert;
import org.eclipse.core.runtime.IPath;

/**
 * <code>DataTreeNode</code>s are the nodes of a <code>DataTree</code>.  Their
 * information and their subtrees are complete, and do not represent deltas on
 * another node or subtree.
 */
public class DataTreeNode extends AbstractDataTreeNode {
	protected Object data;

	/**
	 * Creates a new node
	 *
	 * @param name name of node
	 * @param data data for node
	 */
	public DataTreeNode(String name, Object data) {
		super(name, AbstractDataTreeNode.NO_CHILDREN);
		this.data = data;
	}

	/**
	 * Creates a new node
	 *
	 * @param name name of node
	 * @param data data for node
	 * @param children children for new node
	 */
	public DataTreeNode(String name, Object data, AbstractDataTreeNode[] children) {
		super(name, children);
		this.data = data;
	}

	/**
	 * @see AbstractDataTreeNode#asBackwardDelta(DeltaDataTree, DeltaDataTree, IPath)
	 */
	AbstractDataTreeNode asBackwardDelta(DeltaDataTree myTree, DeltaDataTree parentTree, IPath key) {
		if (parentTree.includes(key))
			return parentTree.copyCompleteSubtree(key);
		return new DeletedNode(name);
	}

	/**
	 * If this node is a node in a comparison tree, this method reverses
	 * the comparison for this node and all children.  Returns null
	 * if this node should no longer be included in the comparison tree.
	 */
	AbstractDataTreeNode asReverseComparisonNode(IComparator comparator) {
		NodeComparison comparison = null;
		try {
			comparison = ((NodeComparison) data).asReverseComparison(comparator);
		} catch (ClassCastException e) {
			Assert.isTrue(false, Messages.dtree_reverse);
		}

		int nextChild = 0;
		for (int i = 0; i < children.length; i++) {
			AbstractDataTreeNode child = children[i].asReverseComparisonNode(comparator);
			if (child != null) {
				children[nextChild++] = child;
			}
		}

		if (nextChild == 0 && comparison.getUserComparison() == 0) {
			/* no children and no change */
			return null;
		}

		/* set the new data */
		data = comparison;

		/* shrink child array as necessary */
		if (nextChild < children.length) {
			AbstractDataTreeNode[] newChildren = new AbstractDataTreeNode[nextChild];
			System.arraycopy(children, 0, newChildren, 0, nextChild);
			children = newChildren;
		}

		return this;
	}

	AbstractDataTreeNode compareWith(DataTreeNode other, IComparator comparator) {
		AbstractDataTreeNode[] comparedChildren = compareWith(children, other.children, comparator);
		Object oldData = data;
		Object newData = other.data;

		/* don't allow comparison of implicit root node */
		int userComparison = 0;
		if (name != null) {
			userComparison = comparator.compare(oldData, newData);
		}

		return new DataTreeNode(name, new NodeComparison(oldData, newData, NodeComparison.K_CHANGED, userComparison), comparedChildren);
	}

	AbstractDataTreeNode compareWithParent(IPath key, DeltaDataTree parent, IComparator comparator) {
		if (!parent.includes(key))
			return convertToAddedComparisonNode(this, NodeComparison.K_ADDED);
		DataTreeNode inParent = (DataTreeNode) parent.copyCompleteSubtree(key);
		return inParent.compareWith(this, comparator);
	}

	/**
	 * Creates and returns a new copy of the receiver.
	 */
	AbstractDataTreeNode copy() {
		if (children.length > 0) {
			AbstractDataTreeNode[] childrenCopy = new AbstractDataTreeNode[children.length];
			System.arraycopy(children, 0, childrenCopy, 0, children.length);
			return new DataTreeNode(name, data, childrenCopy);
		}
		return new DataTreeNode(name, data, children);
	}

	/**
	 * Returns a new node containing a child with the given local name in 
	 * addition to the receiver's current children and data.
	 * 
	 * @param localName
	 *	name of new child
	 * @param childNode
	 *	new child node
	 */
	DataTreeNode copyWithNewChild(String localName, DataTreeNode childNode) {

		AbstractDataTreeNode[] children = this.children;
		int left = 0;
		int right = children.length - 1;
		while (left <= right) {
			int mid = (left + right) / 2;
			int compare = localName.compareTo(children[mid].name);
			if (compare < 0) {
				right = mid - 1;
			} else if (compare > 0) {
				left = mid + 1;
			} else {
				throw new Error(); // it shouldn't have been here yet
			}
		}

		AbstractDataTreeNode[] newChildren = new AbstractDataTreeNode[children.length + 1];
		System.arraycopy(children, 0, newChildren, 0, left);
		childNode.setName(localName);
		newChildren[left] = childNode;
		System.arraycopy(children, left, newChildren, left + 1, children.length - left);
		return new DataTreeNode(this.getName(), this.getData(), newChildren);
	}

	/**
	 * Returns a new node without the specified child, but with the rest
	 * of the receiver's current children and its data.
	 *
	 * @param localName
	 *	name of child to exclude
	 */
	DataTreeNode copyWithoutChild(String localName) {

		int index, newSize;
		DataTreeNode newNode;
		AbstractDataTreeNode children[];

		index = this.indexOfChild(localName);
		if (index == -1) {
			newNode = (DataTreeNode) this.copy();
		} else {
			newSize = this.size() - 1;
			children = new AbstractDataTreeNode[newSize];
			newNode = new DataTreeNode(this.getName(), this.getData(), children);
			newNode.copyChildren(0, index - 1, this, 0); //#from:to:with:startingAt:
			newNode.copyChildren(index, newSize - 1, this, index + 1);
		}
		return newNode;
	}

	/**
	 * Returns an array of delta nodes representing the forward delta between
	 * the given two lists of nodes.
	 * The given nodes must all be complete nodes.
	 */
	protected static AbstractDataTreeNode[] forwardDeltaWith(AbstractDataTreeNode[] oldNodes, AbstractDataTreeNode[] newNodes, IComparator comparer) {
		if (oldNodes.length == 0 && newNodes.length == 0) {
			return NO_CHILDREN;
		}

		AbstractDataTreeNode[] childDeltas = null;
		int numChildDeltas = 0;
		int childDeltaMax = 0;

		// do a merge
		int oldIndex = 0;
		int newIndex = 0;
		while (oldIndex < oldNodes.length && newIndex < newNodes.length) {
			String oldName = oldNodes[oldIndex].name;
			String newName = newNodes[newIndex].name;
			int compare = oldName.compareTo(newName);
			if (compare == 0) {
				AbstractDataTreeNode deltaNode = forwardDeltaWithOrNullIfEqual(oldNodes[oldIndex++], newNodes[newIndex++], comparer);
				if (deltaNode != null) {
					if (numChildDeltas >= childDeltaMax) {
						if (childDeltas == null)
							childDeltas = new AbstractDataTreeNode[childDeltaMax = 5];
						else
							System.arraycopy(childDeltas, 0, childDeltas = new AbstractDataTreeNode[childDeltaMax = childDeltaMax * 2 + 1], 0, numChildDeltas);
					}
					childDeltas[numChildDeltas++] = deltaNode;
				}
			} else if (compare < 0) {
				if (numChildDeltas >= childDeltaMax) {
					if (childDeltas == null)
						childDeltas = new AbstractDataTreeNode[childDeltaMax = 5];
					else
						System.arraycopy(childDeltas, 0, childDeltas = new AbstractDataTreeNode[childDeltaMax = childDeltaMax * 2 + 1], 0, numChildDeltas);
				}
				childDeltas[numChildDeltas++] = new DeletedNode(oldName);
				oldIndex++;
			} else {
				if (numChildDeltas >= childDeltaMax) {
					if (childDeltas == null)
						childDeltas = new AbstractDataTreeNode[childDeltaMax = 5];
					else
						System.arraycopy(childDeltas, 0, childDeltas = new AbstractDataTreeNode[childDeltaMax = childDeltaMax * 2 + 1], 0, numChildDeltas);
				}
				childDeltas[numChildDeltas++] = newNodes[newIndex++];
			}
		}
		while (oldIndex < oldNodes.length) {
			if (numChildDeltas >= childDeltaMax) {
				if (childDeltas == null)
					childDeltas = new AbstractDataTreeNode[childDeltaMax = 5];
				else
					System.arraycopy(childDeltas, 0, childDeltas = new AbstractDataTreeNode[childDeltaMax = childDeltaMax * 2 + 1], 0, numChildDeltas);
			}
			childDeltas[numChildDeltas++] = new DeletedNode(oldNodes[oldIndex++].name);
		}
		while (newIndex < newNodes.length) {
			if (numChildDeltas >= childDeltaMax) {
				if (childDeltas == null)
					childDeltas = new AbstractDataTreeNode[childDeltaMax = 5];
				else
					System.arraycopy(childDeltas, 0, childDeltas = new AbstractDataTreeNode[childDeltaMax = childDeltaMax * 2 + 1], 0, numChildDeltas);
			}
			childDeltas[numChildDeltas++] = newNodes[newIndex++];
		}

		// trim size of result
		if (numChildDeltas == 0) {
			return NO_CHILDREN;
		}
		if (numChildDeltas < childDeltaMax) {
			System.arraycopy(childDeltas, 0, childDeltas = new AbstractDataTreeNode[numChildDeltas], 0, numChildDeltas);
		}
		return childDeltas;
	}

	/**
	 * Returns a node representing the forward delta between
	 * the given two (complete) nodes.
	 */
	protected AbstractDataTreeNode forwardDeltaWith(DataTreeNode other, IComparator comparer) {
		AbstractDataTreeNode deltaNode = forwardDeltaWithOrNullIfEqual(this, other, comparer);
		if (deltaNode == null) {
			return new NoDataDeltaNode(name, NO_CHILDREN);
		}
		return deltaNode;
	}

	/**
	 * Returns a node representing the forward delta between
	 * the given two (complete) nodes, or null if the two nodes are equal.
	 * Although typed as abstract nodes, the given nodes must be complete.
	 */
	protected static AbstractDataTreeNode forwardDeltaWithOrNullIfEqual(AbstractDataTreeNode oldNode, AbstractDataTreeNode newNode, IComparator comparer) {
		AbstractDataTreeNode[] childDeltas = forwardDeltaWith(oldNode.children, newNode.children, comparer);
		Object newData = newNode.getData();
		if (comparer.compare(oldNode.getData(), newData) == 0) {
			if (childDeltas.length == 0) {
				return null;
			}
			return new NoDataDeltaNode(newNode.name, childDeltas);
		}
		return new DataDeltaNode(newNode.name, newData, childDeltas);
	}

	/**
	 * Returns the data for the node 
	 */
	public Object getData() {
		return data;
	}

	/**
	 * Returns true if the receiver can carry data, false otherwise.
	 */
	boolean hasData() {
		return true;
	}

	/**
	 * Sets the data for the node
	 */
	void setData(Object o) {
		data = o;
	}

	/** 
	 * Simplifies the given node, and answers its replacement.
	 */
	AbstractDataTreeNode simplifyWithParent(IPath key, DeltaDataTree parent, IComparator comparer) {
		/* If not in parent, can't be simplified */
		if (!parent.includes(key)) {
			return this;
		}
		/* Can't just call simplify on children since this will miss the case
		 where a child exists in the parent but does not in this. 
		 See PR 1FH5RYA. */
		DataTreeNode parentsNode = (DataTreeNode) parent.copyCompleteSubtree(key);
		return parentsNode.forwardDeltaWith(this, comparer);
	}

	/* (non-Javadoc
	 * Method declared on IStringPoolParticipant
	 */
	public void storeStrings(StringPool set) {
		super.storeStrings(set);
		//copy data for thread safety
		Object o = data;
		if (o instanceof IStringPoolParticipant)
			((IStringPoolParticipant) o).shareStrings(set);
	}

	/**
	 * Returns a unicode representation of the node.  This method is used
	 * for debugging purposes only (no NLS support needed)
	 */
	public String toString() {
		return "a DataTreeNode(" + this.getName() + ") with " + getChildren().length + " children."; //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$
	}

	/**
	 * Returns a constant describing the type of node.
	 */
	int type() {
		return T_COMPLETE_NODE;
	}
}
