Copyright (c) 2000, 2014 IBM Corporation and others.
This program and the accompanying materials
are made available under the terms of the Eclipse Public License 2.0
which accompanies this distribution, and is available at
https://www.eclipse.org/legal/epl-2.0/
SPDX-License-Identifier: EPL-2.0
Contributors:
    IBM Corporation - initial API and implementation
/*******************************************************************************
 * Copyright (c) 2000, 2014 IBM Corporation and others.
 *
 * This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License 2.0
 * which accompanies this distribution, and is available at
 * https://www.eclipse.org/legal/epl-2.0/
 *
 * SPDX-License-Identifier: EPL-2.0
 *
 * Contributors:
 *     IBM Corporation - initial API and implementation
 *******************************************************************************/
package org.eclipse.core.internal.dtree;

import org.eclipse.core.runtime.IPath;

A DataTree represents the complete information of a source tree.
The tree contains all information within its branches, and has no relation to any
other source trees (no parent and no children).
/**
 * A <code>DataTree</code> represents the complete information of a source tree.
 * The tree contains all information within its branches, and has no relation to any
 * other source trees (no parent and no children).
 */
public class DataTree extends AbstractDataTree {

	
the root node of the tree
/**
	 * the root node of the tree
	 */
	private DataTreeNode rootNode;

	
Creates a new empty tree
/**
	 * Creates a new empty tree
	 */
	public DataTree() {
		this.empty();
	}

	
Returns a copy of the node subtree rooted at the given key.
Params:
key – 
Key of subtree to copy/**
	 * Returns a copy of the node subtree rooted at the given key.
	 *
	 * @param key
	 *	Key of subtree to copy
	 */
	@Override
	public AbstractDataTreeNode copyCompleteSubtree(IPath key) {
		DataTreeNode node = findNodeAt(key);
		if (node == null) {
			handleNotFound(key);
		}
		return copyHierarchy(node);
	}

	
Returns a deep copy of a node and all its children.
Params:
node – 
Node to be copied./**
	 * Returns a deep copy of a node and all its children.
	 *
	 * @param node
	 *	Node to be copied.
	 */
	DataTreeNode copyHierarchy(DataTreeNode node) {
		DataTreeNode newNode;
		int size = node.size();
		if (size == 0) {
			newNode = new DataTreeNode(node.getName(), node.getData());
		} else {
			AbstractDataTreeNode[] children = node.getChildren();
			DataTreeNode[] newChildren = new DataTreeNode[size];
			for (int i = size; --i >= 0;) {
				newChildren[i] = this.copyHierarchy((DataTreeNode) children[i]);
			}
			newNode = new DataTreeNode(node.getName(), node.getData(), newChildren);
		}

		return newNode;
	}

	
Creates a new child in the tree.
See Also:
createChild.createChild(IPath, String)/**
	 * Creates a new child in the tree.
	 * @see AbstractDataTree#createChild(IPath, String)
	 */
	@Override
	public void createChild(IPath parentKey, String localName) {
		createChild(parentKey, localName, null);
	}

	
Creates a new child in the tree.
See Also:
createChild.createChild(IPath, String, Object)/**
	 * Creates a new child in the tree.
	 * @see AbstractDataTree#createChild(IPath, String, Object)
	 */
	@Override
	public void createChild(IPath parentKey, String localName, Object data) {
		DataTreeNode node = findNodeAt(parentKey);
		if (node == null)
			handleNotFound(parentKey);
		if (this.isImmutable())
			handleImmutableTree();
		/* If node already exists, replace */
		if (node.includesChild(localName)) {
			node.replaceChild(localName, new DataTreeNode(localName, data));
		} else {
			this.replaceNode(parentKey, node.copyWithNewChild(localName, new DataTreeNode(localName, data)));
		}
	}

	
Creates and returns an instance of the receiver.  This is an
implementation of the factory method creational pattern for allowing
abstract methods to create instances
/**
	 * Creates and returns an instance of the receiver.  This is an
	 * implementation of the factory method creational pattern for allowing
	 * abstract methods to create instances
	 */
	@Override
	protected AbstractDataTree createInstance() {
		return new DataTree();
	}

	
Creates or replaces a subtree in the tree.  The parent node must exist.
Params:
key – 
Key of parent node whose subtree we want to create/replace.
subtree – 
New node to insert into tree./**
	 * Creates or replaces a subtree in the tree.  The parent node must exist.
	 *
	 * @param key
	 *	Key of parent node whose subtree we want to create/replace.
	 * @param subtree
	 *	New node to insert into tree.
	 */
	@Override
	public void createSubtree(IPath key, AbstractDataTreeNode subtree) {

		// Copy it since destructive mods are allowed on the original
		// and shouldn't affect this tree.
		DataTreeNode newNode = copyHierarchy((DataTreeNode) subtree);

		if (this.isImmutable()) {
			handleImmutableTree();
		}

		if (key.isRoot()) {
			setRootNode(newNode);
		} else {
			String localName = key.lastSegment();
			newNode.setName(localName); // Another mod, but it's OK we've already copied

			IPath parentKey = key.removeLastSegments(1);

			DataTreeNode node = findNodeAt(parentKey);
			if (node == null) {
				handleNotFound(parentKey);
			}

			/* If node already exists, replace */
			if (node.includesChild(localName)) {
				node.replaceChild(localName, newNode);
			}

			this.replaceNode(parentKey, node.copyWithNewChild(localName, newNode));
		}
	}

	
Deletes a child of the tree.
See Also:
deleteChild.deleteChild(IPath, String)/**
	 * Deletes a child of the tree.
	 * @see AbstractDataTree#deleteChild(IPath, String)
	 */
	@Override
	public void deleteChild(IPath parentKey, String localName) {
		if (this.isImmutable())
			handleImmutableTree();
		DataTreeNode node = findNodeAt(parentKey);
		if (node == null || (!node.includesChild(localName))) {
			handleNotFound(node == null ? parentKey : parentKey.append(localName));
		} else {
			this.replaceNode(parentKey, node.copyWithoutChild(localName));
		}
	}

	
Initializes the receiver.
See Also:
empty.empty()/**
	 * Initializes the receiver.
	 * @see AbstractDataTree#empty()
	 */
	@Override
	public void empty() {
		this.setRootNode(new DataTreeNode(null, null));
	}

	
Returns the specified node if it is present, otherwise returns null.
Params:
key – 
Key of node to return/**
	 * Returns the specified node if it is present, otherwise returns null.
	 *
	 * @param key
	 *	Key of node to return
	 */
	public DataTreeNode findNodeAt(IPath key) {
		AbstractDataTreeNode node = this.getRootNode();
		int keyLength = key.segmentCount();
		for (int i = 0; i < keyLength; i++) {
			try {
				node = node.childAt(key.segment(i));
			} catch (ObjectNotFoundException notFound) {
				return null;
			}
		}
		return (DataTreeNode) node;
	}

	
Returns the data at the specified node.
Params:
key – 
Node whose data to return./**
	 * Returns the data at the specified node.
	 *
	 * @param key
	 *	Node whose data to return.
	 */
	@Override
	public Object getData(IPath key) {
		DataTreeNode node = findNodeAt(key);
		if (node == null) {
			handleNotFound(key);
			return null;
		}
		return node.getData();
	}

	
Returns the names of the children of a node.
See Also:
getNamesOfChildren.getNamesOfChildren(IPath)/**
	 * Returns the names of the children of a node.
	 * @see AbstractDataTree#getNamesOfChildren(IPath)
	 */
	@Override
	public String[] getNamesOfChildren(IPath parentKey) {
		DataTreeNode parentNode;
		parentNode = findNodeAt(parentKey);
		if (parentNode == null) {
			handleNotFound(parentKey);
			return null;
		}
		return parentNode.namesOfChildren();
	}

	
Returns the root node of the tree
/**
	 * Returns the root node of the tree
	 */
	@Override
	AbstractDataTreeNode getRootNode() {
		return rootNode;
	}

	
Returns true if the receiver includes a node with
the given key, false otherwise.
/**
	 * Returns true if the receiver includes a node with
	 * the given key, false otherwise.
	 */
	@Override
	public boolean includes(IPath key) {
		return (findNodeAt(key) != null);
	}

	
Returns an object containing:
	- a flag indicating whether the specified node was found
 - the data for the node, if it was found
Params:
key – 
key of node for which we want to retrieve data./**
	 * Returns an object containing:
	 * 	- a flag indicating whether the specified node was found
	 *  - the data for the node, if it was found
	 * @param key
	 *	key of node for which we want to retrieve data.
	 */
	@Override
	public DataTreeLookup lookup(IPath key) {
		DataTreeNode node = this.findNodeAt(key);
		if (node == null)
			return DataTreeLookup.newLookup(key, false, null);
		return DataTreeLookup.newLookup(key, true, node.getData());
	}

	
Replaces the node at the specified key with the given node
/**
	 * Replaces the node at the specified key with the given node
	 */
	protected void replaceNode(IPath key, DataTreeNode node) {
		DataTreeNode found;
		if (key.isRoot()) {
			this.setRootNode(node);
		} else {
			found = this.findNodeAt(key.removeLastSegments(1));
			found.replaceChild(key.lastSegment(), node);
		}
	}

	
Sets the data at the specified node.
See Also:
setData.setData(IPath, Object)/**
	 * Sets the data at the specified node.
	 * @see AbstractDataTree#setData(IPath, Object)
	 */
	@Override
	public void setData(IPath key, Object data) {
		DataTreeNode node = this.findNodeAt(key);
		if (this.isImmutable())
			handleImmutableTree();
		if (node == null) {
			handleNotFound(key);
		} else {
			node.setData(data);
		}
	}

	
Sets the root node of the tree
See Also:
setRootNode.setRootNode(AbstractDataTreeNode)/**
	 * Sets the root node of the tree
	 * @see AbstractDataTree#setRootNode(AbstractDataTreeNode)
	 */
	void setRootNode(DataTreeNode aNode) {
		rootNode = aNode;
	}
}