bundles/org.eclipse.team.core/src/org/eclipse/team/internal/core/mapping/PathTree.java

/*******************************************************************************
 * Copyright (c) 2000, 2017 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.team.internal.core.mapping;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.eclipse.core.runtime.IPath;

/**
 * A tree of objects keyed by path
 */
public class PathTree {

	class Node {
		Object payload;
		Set<IPath> descendantsWithPayload;
		int flags;
		public boolean isEmpty() {
			return payload == null && (descendantsWithPayload == null || descendantsWithPayload.isEmpty());
		}
		public Object getPayload() {
			return payload;
		}
		public void setPayload(Object payload) {
			this.payload = payload;
		}
		public boolean hasDescendants() {
			return descendantsWithPayload != null && !descendantsWithPayload.isEmpty();
		}
		public boolean hasFlag(int propertyBit) {
			return (flags & propertyBit) != 0;
		}
		public void setProperty(int propertyBit, boolean value) {
			if (value)
				flags |= propertyBit;
			else
				flags ^= propertyBit;
		}
		public boolean descendantHasFlag(int property) {
			if (hasDescendants()) {
				for (IPath path : descendantsWithPayload) {
					Node child = getNode(path);
					if (child.hasFlag(property)) {
						return true;
					}
				}
			}
			return false;
		}
	}

	private Map<IPath, Node> objects = new HashMap<>();

	/**
	 * Return the object at the given path or <code>null</code>
	 * if there is no object at that path
	 * @param path the path
	 * @return the object at the given path or <code>null</code>
	 */
	public synchronized Object get(IPath path) {
		Node node = getNode(path);
		if (node == null)
			return null;
		return node.getPayload();
	}

	/**
	 * Put the object at the given path. Return the
	 * previous object at that path or <code>null</code>
	 * if the path did not previously have an object.
	 * @param path the path of the object
	 * @param object the object
	 * @return the previous object at that path or <code>null</code>
	 */
	public synchronized Object put(IPath path, Object object) {
		Node node = getNode(path);
		if (node == null) {
			node = addNode(path);
		}
		Object previous = node.getPayload();
		node.setPayload(object);
		if(previous == null) {
			addToParents(path, path);
		}
		return previous;
	}

	/**
	 * Remove the object at the given path and return
	 * the removed object or <code>null</code> if no
	 * object was removed.
	 * @param path the path  to remove
	 * @return the removed object at the given path and return
	 * the removed object or <code>null</code>
	 */
	public synchronized Object remove(IPath path) {
		Node node = getNode(path);
		if (node == null)
			return null;
		Object previous = node.getPayload();
		node.setPayload(null);
		if(previous != null) {
			removeFromParents(path, path);
			if (node.isEmpty()) {
				removeNode(path);
			}
		}
		return previous;

	}

	/**
	 * Return whether the given path has children in the tree
	 * @param path
	 * @return whether there are children for the given path
	 */
	public synchronized boolean hasChildren(IPath path) {
		if (path.isEmpty()) return !objects.isEmpty();
		Node node = getNode(path);
		if (node == null)
			return false;
		return node.hasDescendants();
	}

	/**
	 * Return the paths for any children of the given path in this set.
	 * @param path the path
	 * @return the paths for any children of the given path in this set
	 */
	public synchronized IPath[] getChildren(IPath path) {
		// OPTIMIZE: could be optimized so that we don't traverse all the deep
		// children to find the immediate ones.
		Set<IPath> children = new HashSet<>();
		Node node = getNode(path);
		if (node != null) {
			Set possibleChildren = node.descendantsWithPayload;
			if(possibleChildren != null) {
				for (Object next : possibleChildren) {
					IPath descendantPath = (IPath)next;
					IPath childPath = null;
					if(descendantPath.segmentCount() == (path.segmentCount() +  1)) {
						childPath = descendantPath;
					} else if (descendantPath.segmentCount() > path.segmentCount()) {
						childPath = descendantPath.removeLastSegments(descendantPath.segmentCount() - path.segmentCount() - 1);
					}
					if (childPath != null) {
						children.add(childPath);
					}
				}
			}
		}
		return children.toArray(new IPath[children.size()]);
	}

	private boolean addToParents(IPath path, IPath parent) {
		// this flag is used to indicate if the parent was previously in the set
		boolean addedParent = false;
		if (path == parent) {
			// this is the leaf that was just added
			addedParent = true;
		} else {
			Node node = getNode(parent);
			if (node == null)
				node = addNode(parent);
			Set<IPath> children = node.descendantsWithPayload;
			if (children == null) {
				children = new HashSet<>();
				node.descendantsWithPayload = children;
				// this is a new folder in the sync set
				addedParent = true;
			}
			children.add(path);
		}
		// if the parent already existed and the resource is new, record it
		if ((parent.segmentCount() == 0 || !addToParents(path, parent.removeLastSegments(1))) && addedParent) {
			// TODO: we may not need to record the removed subtree
			// internalAddedSubtreeRoot(parent);
		}
		return addedParent;
	}

	private boolean removeFromParents(IPath path, IPath parent) {
		// this flag is used to indicate if the parent was removed from the set
		boolean removedParent = false;
		Node node = getNode(parent);
		if (node == null) {
			// this is the leaf
			removedParent = true;
		} else {
			Set children = node.descendantsWithPayload;
			if (children == null) {
				// this is the leaf
				removedParent = true;
			} else {
				children.remove(path);
				if (children.isEmpty()) {
					node.descendantsWithPayload = null;
					if (node.isEmpty())
						removeNode(parent);
					removedParent = true;
				}
			}
		}
		//	if the parent wasn't removed and the resource was, record it
		if ((parent.segmentCount() == 0 || !removeFromParents(path, parent.removeLastSegments(1))) && removedParent) {
			// TODO: may not need to record this
			//internalRemovedSubtreeRoot(parent);
		}
		return removedParent;
	}

	/**
	 * Clear all entries from the path tree.
	 */
	public synchronized void clear() {
		objects.clear();
	}

	/**
	 * Return whether the path tree is empty.
	 * @return whether the path tree is empty
	 */
	public synchronized boolean isEmpty() {
		return objects.isEmpty();
	}

	/**
	 * Return the paths in this tree that contain diffs.
	 * @return the paths in this tree that contain diffs.
	 */
	public synchronized IPath[] getPaths() {
		List<IPath> result = new ArrayList<>();
		for (IPath path : objects.keySet()) {
			Node node = getNode(path);
			if (node.getPayload() != null)
				result.add(path);
		}
		return result.toArray(new IPath[result.size()]);
	}

	/**
	 * Return all the values contained in this path tree.
	 * @return all the values in the tree
	 */
	public synchronized Collection<Object> values() {
		List<Object> result = new ArrayList<>();
		for (IPath path : objects.keySet()) {
			Node node = getNode(path);
			if (node.getPayload() != null)
				result.add(node.getPayload());
		}
		return result;
	}

	/**
	 * Return the number of nodes contained in this path tree.
	 * @return the number of nodes contained in this path tree
	 */
	public int size() {
		return values().size();
	}

	private Node getNode(IPath path) {
		return objects.get(path);
	}

	private Node addNode(IPath path) {
		Node node;
		node = new Node();
		objects.put(path, node);
		return node;
	}

	private Object removeNode(IPath path) {
		return objects.remove(path);
	}

	/**
	 * Set the property for the given path and propogate the
	 * bit to the root. The property is only set if the given path
	 * already exists in the tree.
	 * @param path the path
	 * @param property the property bit to set
	 * @param value whether the bit should be on or off
	 * @return the paths whose bit changed
	 */
	public synchronized IPath[] setPropogatedProperty(IPath path, int property, boolean value) {
		Set<IPath> changed = new HashSet<>();
		internalSetPropertyBit(path, property, value, changed);
		return changed.toArray(new IPath[changed.size()]);
	}

	private void internalSetPropertyBit(IPath path, int property, boolean value, Set<IPath> changed) {
		if (path.segmentCount() == 0)
			return;
		Node node = getNode(path);
		if (node == null)
			return;
		// No need to set it if the value hans't changed
		if (value == node.hasFlag(property))
			return;
		// Only unset the property if no descendants have the flag set
		if (!value && node.descendantHasFlag(property))
			return;
		node.setProperty(property, value);
		changed.add(path);
		internalSetPropertyBit(path.removeLastSegments(1), property, value, changed);
	}

	public synchronized boolean getProperty(IPath path, int property) {
		if (path.segmentCount() == 0)
			return false;
		Node node = getNode(path);
		if (node == null)
			return false;
		return (node.hasFlag(property));
	}

}