path: root/org.eclipse.text.quicksearch/src/org/eclipse/text/quicksearch/internal/core/priority/PrioriTree.java

/*******************************************************************************
 * Copyright (c) 2013 Pivotal Software, Inc.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v2.0
 * which accompanies this distribution, and is available at
 * https://www.eclipse.org/legal/epl-2.0/
 *
 * SPDX-License-Identifier: EPL-2.0
 *
 * Contributors:
 *    Pivotal Software, Inc. - initial API and implementation
 *******************************************************************************/
package org.eclipse.text.quicksearch.internal.core.priority;

import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;

import org.eclipse.core.resources.IResource;
import org.eclipse.core.runtime.IPath;

/**
 * A PrioriTree is an implementation of PriorityFunction that is based on assigning specific priorities
 * to a finite set of paths. The paths are kept in a tree-like structure internally so that
 * assigning a priority to a given path also implicitly forces all the children leading to that
 * path to have a priority that is at least as high as that of the path itself.
 *
 * TODO: The priority function produced by this tree would probably be better if it also raised/affected
 * the priority of nodes in a subtree of a node, but not by as much as the node itself.
 *
 * @author Kris De Volder
 */
public class PrioriTree extends DefaultPriorityFunction {

	private static final boolean DEBUG =  false; //(""+Platform.getLocation()).contains("kdvolder");

	/**
	 * Creates an empty PrioriTree. This tree assigns provided default priority to any path.
	 */
	public static PrioriTree create() {
		return new PrioriTree(0, PRIORITY_DEFAULT);
	}

	private PrioriTree(int level, double defaultPriority) {
		this.level = level;
		this.priority = defaultPriority;
		this.childPriority = defaultPriority;
	}

	private static void debug(String string) {
		if (DEBUG) {
			System.out.println(string);
		}
	}

	/**
	 * Level of this node in the tree. This corresponds to the length of path ending in this node. I.e. 0 for the root node,
	 * 1 for children of root, 2 for children of level 1 nodes etc.
	 * <p>
	 * Level is used to easily check whether a node lookup returned an exact matching node or an ancestor.
	 */
	private int level;

	/**
	 * Priority assigned to any path lookup that ends here.
	 */
	private double priority = PRIORITY_IGNORE;
		//Must start out as low as possible because putting stuff into the tree will raise the priorities monotonically.
		//Note that normally we will not create a PrioriTree node unless there is some reason to
	    // assign a priority. So this value is expected to be always overwritten shortly after
	    // a node is created.

	/**
	 * Default priority assigned to all children of this node
	 */
	private double childPriority = PRIORITY_IGNORE;

	/**
	 * Children indexed by first segment in the path. This is only initialised if there's at least one
	 * child.
	 */
	private Map<String, PrioriTree> children = null;

	/**
	 * Set the priority for a given path. Also forces an update of all 'ancestor' nodes in the
	 * tree leading to this path to ensure that a parent node always has a priority at least as high as any
	 * of its children.
	 * <p>
	 * Also assigns the same priority to any descendants of the target path (but not the descendants of
	 * implicitly set parent nodes.
	 * <p>
	 * THe picture below illustrates: # marks a target node * marks nodes that implicitly
	 * also get set. And '-' marks nodes that are unaffected.
	 * <p>
	 * <pre>
	 *                                       *
	 *                                     /   \
	 *                                    -     *
	 *                                         / \
	 *                                        -  #
	 *                                          /  \
	 *                                         *    *
	 *                                        /\    /\
	 *                                       *  *  *  *
	 * </pre>
	 * <p>
	 * Note: this operation never reduces the priority of any path already in the tree.
	 * Thus if the same path gets assigned a priority more than once, only the highest priority will
	 * be retained in the tree node for that path.
	 */
	public void setPriority(IPath path, double priority) {
		this.priority = Math.max(this.priority, priority); //Use Math.max, never reduce priorities!
		if (path.segmentCount()>0) {
			// path leads to a child node
			PrioriTree child = ensureChild(path.segment(0));
			child.setPriority(path.removeFirstSegments(1), priority);
		} else {
			// path ends here
			setChildPriority(priority);
		}
	}

	private void setChildPriority(double priority) {
		double newChildPriority = Math.max(priority, childPriority);
		if (newChildPriority!=childPriority) {
			//Must update default child priority as well check if already created children priorities need
			// to be raised.
			this.childPriority = newChildPriority;
			if (children!=null) {
				for (PrioriTree child : children.values()) {
					//TODO: remove children that became redundant because the increase of childPriority in parent
					// makes them have no observable effect.
					//Currently this cleanup is not happening. This is inefficient but not incorrect.
					child.priority = Math.max(child.priority, newChildPriority);
					child.setChildPriority(newChildPriority);
				}
			}
		}
	}

	/**
	 * Ensure that this node has a child for a given segment string. If no node exists yet, create it.
	 * @param segment
	 * @return {@link PrioriTree} the existing or newly created child, never null.
	 */
	private PrioriTree ensureChild(String segment) {
		if (children==null) {
			children = new HashMap<>();
		}
		PrioriTree child = children.get(segment);
		if (child==null) {
			child = new PrioriTree(level+1, childPriority);
			children.put(segment, child);
		}
		return child;
	}

	@Override
	public double priority(IResource r) {
		double result = super.priority(r);
		if (result==PRIORITY_IGNORE) {
			//Ignored paths shouldn't be changed ... ever.
			return PRIORITY_IGNORE;
		}
		IPath path = r.getFullPath();
		PrioriTree node = this.lookup(path);
		if (node.level == path.segmentCount()) {
			//exact node found
			result = node.priority;
		} else {
			//ancestor node found
			result = node.childPriority;
		}
		debug("Priority for "+r.getFullPath() + " = " + result); //$NON-NLS-1$ //$NON-NLS-2$
		return result;
	}


	/**
	 * Locate tree node corresponding to a given path.
	 * @param path
	 * @return The node or null if no corresponding node exists in the tree.
	 */
	private PrioriTree lookup(IPath path) {
		PrioriTree found = null;
		if (path.segmentCount()>0) {
			PrioriTree child = getChild(path.segment(0));
			if (child!=null) {
				found = child.lookup(path.removeFirstSegments(1));
			}
		}
		return found==null?this:found;
	}

	/**
	 * Fetch the child for the corresponding segment String.
	 * @param segment
	 * @return The child or null if there is no such child.
	 */
	private PrioriTree getChild(String segment) {
		if (children!=null) {
			return children.get(segment);
		}
		return null;
	}

	/**
	 * For debugging purposes. Dumps tree data onto System.out
	 */
	public void dump() {
		dump("/", 0); //$NON-NLS-1$
	}

	private void dump(String name, int indent) {
		indent(indent);
		System.out.println(name + " : " +priority); //$NON-NLS-1$
		if (children!=null) {
			for (Entry<String, PrioriTree> c : children.entrySet()) {
				c.getValue().dump(c.getKey(), indent+1);
			}
		}
	}

	private void indent(int i) {
		for (int j = 0; j < i; j++) {
			System.out.print("  "); //$NON-NLS-1$
		}
	}

}