Copyright (c) 2000, 2016 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, 2016 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.jdt.internal.core;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import org.eclipse.jdt.core.IJavaElement;
import org.eclipse.jdt.core.IRegion;

See Also:
IRegion/**
 * @see IRegion
 */

public class Region implements IRegion {

	private static final class Node {
		private Map<IJavaElement, Node> children = Collections.emptyMap();

		public Node() {
		}

		public void clearChildren() {
			this.children = Collections.emptyMap();
		}

		public Node createChildFor(IJavaElement element) {
			if (this.children.isEmpty()) {
				this.children = new HashMap<>();
			}

			Node child = this.children.get(element);

			if (child == null) {
				child = new Node();
				this.children.put(element, child);
			}

			return child;
		}

		public Node findChildFor(IJavaElement element) {
			return this.children.get(element);
		}

		public int countLeafNodes() {
			if (isEmpty()) {
				return 1;
			}

			int result = 0;
			for (Node next : this.children.values()) {
				result += next.countLeafNodes();
			}
			return result;
		}

		boolean isEmpty() {
			return this.children.isEmpty();
		}

		public int gatherLeaves(IJavaElement[] result, int i) {
			for (Map.Entry<IJavaElement, Node> next : this.children.entrySet()) {
				Node nextNode = next.getValue();
				if (nextNode.isEmpty()) {
					result[i++] = next.getKey();
				} else {
					i = nextNode.gatherLeaves(result, i);
				}
			}
			return i;
		}

		public void removeChild(IJavaElement currentElement) {
			this.children.remove(currentElement);
		}
	}

	private Node root = new Node();

	@Override
	public void add(IJavaElement element) {
		if (contains(element)) {
			return;
		}
		Node node = createNodeFor(element);
		node.clearChildren();
	}

	private Node createNodeFor(IJavaElement element) {
		if (element == null) {
			return this.root;
		}

		Node parentNode = createNodeFor(getParent(element));

		return parentNode.createChildFor(element);
	}

	@Override
	public boolean contains(IJavaElement element) {
		Node existingNode = findMostSpecificNodeFor(element);

		if (existingNode == this.root) {
			return false;
		}
		return existingNode.isEmpty();
	}

	private Node findMostSpecificNodeFor(IJavaElement element) {
		if (element == null) {
			return this.root;
		}

		Node parentNode = findMostSpecificNodeFor(getParent(element));
		Node child = parentNode.findChildFor(element);
		if (child == null) {
			return parentNode;
		}
		return child;
	}

	@Override
	public IJavaElement[] getElements() {
		int leaves = countLeafNodes();

		IJavaElement[] result = new IJavaElement[leaves];
		int insertions = this.root.gatherLeaves(result, 0);

		assert insertions == leaves;

		return result;
	}

	private int countLeafNodes() {
		if (this.root.isEmpty()) {
			return 0;
		}
		return this.root.countLeafNodes();
	}

	private Node findExactNode(IJavaElement element) {
		if (element == null) {
			return this.root;
		}

		Node parentNode = findExactNode(getParent(element));

		if (parentNode == null) {
			return null;
		}

		return parentNode.findChildFor(element);
	}

	@Override
	public boolean remove(IJavaElement element) {
		Node node = findExactNode(element);

		if (node == null) {
			return false;
		}
		node.clearChildren();
		boolean returnValue = node.isEmpty();

		List<Node> ancestors = new ArrayList<>();
		findPath(ancestors, element);

		IJavaElement currentElement = element;
		int idx = ancestors.size();

		while (--idx > 0 && currentElement != null) {
			Node current = ancestors.get(idx);
			Node parent = ancestors.get(idx - 1);

			if (current.isEmpty()) {
				parent.removeChild(currentElement);
			} else {
				break;
			}
			currentElement = getParent(currentElement);
		}

		return returnValue;
	}

	protected IJavaElement getParent(IJavaElement element) {
		return element.getParent();
	}

	private void findPath(List<Node> ancestors, IJavaElement element) {
		if (element == null) {
			ancestors.add(this.root);
			return;
		}

		findPath(ancestors, getParent(element));

		Node last = ancestors.get(ancestors.size() - 1);
		Node next = last.findChildFor(element);
		if (next != null) {
			ancestors.add(next);
		}
	}
}