<commit_before>package contrib.edu.stanford.nlp.util;

import java.util.AbstractCollection;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Queue;
import java.util.Stack;
import java.util.TreeMap;

import org.eclipse.jdt.annotation.Nullable;

import uk.org.cinquin.mutinack.misc_util.collections.ResizingArrayQueue;
import uk.org.cinquin.mutinack.misc_util.exceptions.AssertionFailedException;

/**
 * An interval tree maintains a tree so that all intervals to the left start
 * before current interval and all intervals to the right start after.
 *
 * @author <NAME>
 */
public class IntervalTree<E extends Comparable<E>, T extends HasInterval<E>> extends AbstractCollection<T>
{
	private static final double defaultAlpha = 0.65; // How balanced we want this tree (between 0.5 and 1.0)
	private static final boolean debug = false;

	private TreeNode<E,T> root = new TreeNode<>();

	// Tree node
	public static class TreeNode<E extends Comparable<E>, T extends HasInterval<E>> {
		T value;
		E maxEnd;    // Maximum end in this subtree
		int size;

		TreeNode<E,T> left;
		TreeNode<E,T> right;

		TreeNode<E,T> parent; // Parent for convenience

		public boolean isEmpty() { return value == null; }

		public void clear() {
			value = null;
			maxEnd = null;
			size = 0;
			left = null;
			right = null;
			//parent = null;
		}
	}

	@Override
	public boolean isEmpty() { return root.isEmpty(); }

	@Override
	public void clear() {
		root.clear();
	}

	@Override
	public String toString() {
		return "Size: " + root.size;
	}

	@Override
	public boolean add(T target) {
		return add(root, target, defaultAlpha);
	}

	public boolean add(TreeNode<E,T> node, T target) {
		return add(node, target, defaultAlpha);
	}

	// Add node to tree - attempting to maintain alpha balance
	public boolean add(TreeNode<E,T> node, T target, double alpha) {
		if (target == null) return false;
		TreeNode<E,T> n = node;
		int depth = 0;
		int thresholdDepth = (node.size > 10)? ((int) (-Math.log(node.size)/Math.log(alpha)+1)):10;
		while (n != null) {
			if (n.value == null) {
				n.value = target;
				n.maxEnd = target.getInterval().getEnd();
				n.size = 1;
				if (depth > thresholdDepth) {
					// Do rebalancing
					TreeNode<E,T> p = n.parent;
					while (p != null) {
						if (p.size > 10 && !isAlphaBalanced(p,alpha)) {
							TreeNode<E,T> newParent = balance(p);
							if (p == root) root = newParent;
							if (debug) this.check();
							break;
						}
						p = p.parent;
					}
				}
				return true;
			} else {
				depth++;
				n.maxEnd = Interval.max(n.maxEnd, target.getInterval().getEnd());
				n.size++;
				if (target.getInterval().compareTo(n.value.getInterval()) <= 0) {
					// Should go on left
					if (n.left == null) {
						n.left = new TreeNode<>();
						n.left.parent = n;
					}
					n = n.left;
				} else {
					// Should go on right
					if (n.right == null) {
						n.right = new TreeNode<>();
						n.right.parent = n;
					}
					n = n.right;
				}
			}
		}
		return false;
	}

	@Override
	public int size()
	{
		return root.size;
	}

	@Override
	public Iterator<T> iterator() {
		return new TreeNodeIterator<>(root);
	}

	private static class TreeNodeIterator<E extends Comparable<E>, T extends HasInterval<E>> extends AbstractIterator<T> {
		TreeNode<E,T> node;
		Iterator<T> curIter;
		int stage = -1;
		@Nullable T next;

		public TreeNodeIterator(TreeNode<E,T> node) {
			this.node = node;
			if (node.isEmpty()) {
				stage = 3;
			}
		}

		@Override
		public boolean hasNext() {
			if (next == null) {
				next = getNext();
			}
			return next != null;
		}

		@Override
		public T next() {
			if (hasNext()) {
				@SuppressWarnings("null")
				T x = next;
				next = getNext();
				return x;
			} else throw new NoSuchElementException();
		}

		private @Nullable T getNext() {
			// TODO: Do more efficient traversal down the tree
			if (stage > 2) return null;
			while (curIter == null || !curIter.hasNext()) {
				stage++;
				switch (stage) {
					case 0:
						curIter = (node.left != null)? new TreeNodeIterator<>(node.left):null;
						break;
					case 1:
						curIter = null;
						return node.value;
					case 2:
						curIter = (node.right != null)? new TreeNodeIterator<>(node.right):null;
						break;
					default:<commit_msg>Remove unncessary suppress warning.<commit_after>package contrib.edu.stanford.nlp.util;

import java.util.AbstractCollection;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Queue;
import java.util.Stack;
import java.util.TreeMap;

import org.eclipse.jdt.annotation.Nullable;

import uk.org.cinquin.mutinack.misc_util.collections.ResizingArrayQueue;
import uk.org.cinquin.mutinack.misc_util.exceptions.AssertionFailedException;

/**
 * An interval tree maintains a tree so that all intervals to the left start
 * before current interval and all intervals to the right start after.
 *
 * @author <NAME>
 */
public class IntervalTree<E extends Comparable<E>, T extends HasInterval<E>> extends AbstractCollection<T>
{
	private static final double defaultAlpha = 0.65; // How balanced we want this tree (between 0.5 and 1.0)
	private static final boolean debug = false;

	private TreeNode<E,T> root = new TreeNode<>();

	// Tree node
	public static class TreeNode<E extends Comparable<E>, T extends HasInterval<E>> {
		T value;
		E maxEnd;    // Maximum end in this subtree
		int size;

		TreeNode<E,T> left;
		TreeNode<E,T> right;

		TreeNode<E,T> parent; // Parent for convenience

		public boolean isEmpty() { return value == null; }

		public void clear() {
			value = null;
			maxEnd = null;
			size = 0;
			left = null;
			right = null;
			//parent = null;
		}
	}

	@Override
	public boolean isEmpty() { return root.isEmpty(); }

	@Override
	public void clear() {
		root.clear();
	}

	@Override
	public String toString() {
		return "Size: " + root.size;
	}

	@Override
	public boolean add(T target) {
		return add(root, target, defaultAlpha);
	}

	public boolean add(TreeNode<E,T> node, T target) {
		return add(node, target, defaultAlpha);
	}

	// Add node to tree - attempting to maintain alpha balance
	public boolean add(TreeNode<E,T> node, T target, double alpha) {
		if (target == null) return false;
		TreeNode<E,T> n = node;
		int depth = 0;
		int thresholdDepth = (node.size > 10)? ((int) (-Math.log(node.size)/Math.log(alpha)+1)):10;
		while (n != null) {
			if (n.value == null) {
				n.value = target;
				n.maxEnd = target.getInterval().getEnd();
				n.size = 1;
				if (depth > thresholdDepth) {
					// Do rebalancing
					TreeNode<E,T> p = n.parent;
					while (p != null) {
						if (p.size > 10 && !isAlphaBalanced(p,alpha)) {
							TreeNode<E,T> newParent = balance(p);
							if (p == root) root = newParent;
							if (debug) this.check();
							break;
						}
						p = p.parent;
					}
				}
				return true;
			} else {
				depth++;
				n.maxEnd = Interval.max(n.maxEnd, target.getInterval().getEnd());
				n.size++;
				if (target.getInterval().compareTo(n.value.getInterval()) <= 0) {
					// Should go on left
					if (n.left == null) {
						n.left = new TreeNode<>();
						n.left.parent = n;
					}
					n = n.left;
				} else {
					// Should go on right
					if (n.right == null) {
						n.right = new TreeNode<>();
						n.right.parent = n;
					}
					n = n.right;
				}
			}
		}
		return false;
	}

	@Override
	public int size()
	{
		return root.size;
	}

	@Override
	public Iterator<T> iterator() {
		return new TreeNodeIterator<>(root);
	}

	private static class TreeNodeIterator<E extends Comparable<E>, T extends HasInterval<E>> extends AbstractIterator<T> {
		TreeNode<E,T> node;
		Iterator<T> curIter;
		int stage = -1;
		@Nullable T next;

		public TreeNodeIterator(TreeNode<E,T> node) {
			this.node = node;
			if (node.isEmpty()) {
				stage = 3;
			}
		}

		@Override
		public boolean hasNext() {
			if (next == null) {
				next = getNext();
			}
			return next != null;
		}

		@Override
		public T next() {
			if (hasNext()) {
				T x = next;
				next = getNext();
				return x;
			} else throw new NoSuchElementException();
		}

		private @Nullable T getNext() {
			// TODO: Do more efficient traversal down the tree
			if (stage > 2) return null;
			while (curIter == null || !curIter.hasNext()) {
				stage++;
				switch (stage) {
					case 0:
						curIter = (node.left != null)? new TreeNodeIterator<>(node.left):null;
						break;
					case 1:
						curIter = null;
						return node.value;
					case 2:
						curIter = (node.right != null)? new TreeNodeIterator<>(node.right):null;
						break;
					default:
{'fraction_non_alphanumeric': 0.134070796460177, 'fraction_numerical': 0.005309734513274336, 'mean_word_length': 2.9723198594024605, 'pattern_counts': {'":': 0, '<': 67, '<?xml version=': 0, '>': 73, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6641568', 'n_tokens_mistral': 3642, 'n_tokens_neox': 2992, 'n_words': 853}