From ba167247757d76df603a6527d9ad51c3d9f150b9 Mon Sep 17 00:00:00 2001 From: Kristóf Marussy Date: Thu, 9 May 2019 20:24:56 -0400 Subject: Interval aggregation operators --- .../logic2viatra/interval/Interval.xtend | 88 +- .../interval/IntervalAggregationMode.java | 66 + .../interval/IntervalAggregationOperator.xtend | 48 + .../interval/IntervalRedBlackNode.xtend | 177 +++ .../logic2viatra/interval/RedBlackNode.java | 1392 ++++++++++++++++++++ .../logic2viatra/interval/Reference.java | 51 + 6 files changed, 1806 insertions(+), 16 deletions(-) create mode 100644 Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.logic2viatra/src/hu/bme/mit/inf/dslreasoner/viatrasolver/logic2viatra/interval/IntervalAggregationMode.java create mode 100644 Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.logic2viatra/src/hu/bme/mit/inf/dslreasoner/viatrasolver/logic2viatra/interval/IntervalAggregationOperator.xtend create mode 100644 Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.logic2viatra/src/hu/bme/mit/inf/dslreasoner/viatrasolver/logic2viatra/interval/IntervalRedBlackNode.xtend create mode 100644 Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.logic2viatra/src/hu/bme/mit/inf/dslreasoner/viatrasolver/logic2viatra/interval/RedBlackNode.java create mode 100644 Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.logic2viatra/src/hu/bme/mit/inf/dslreasoner/viatrasolver/logic2viatra/interval/Reference.java (limited to 'Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.logic2viatra/src/hu/bme/mit/inf') diff --git a/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.logic2viatra/src/hu/bme/mit/inf/dslreasoner/viatrasolver/logic2viatra/interval/Interval.xtend b/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.logic2viatra/src/hu/bme/mit/inf/dslreasoner/viatrasolver/logic2viatra/interval/Interval.xtend index 6ea96866..229656c0 100644 --- a/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.logic2viatra/src/hu/bme/mit/inf/dslreasoner/viatrasolver/logic2viatra/interval/Interval.xtend +++ b/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.logic2viatra/src/hu/bme/mit/inf/dslreasoner/viatrasolver/logic2viatra/interval/Interval.xtend @@ -5,7 +5,7 @@ import java.math.MathContext import java.math.RoundingMode import org.eclipse.xtend.lib.annotations.Data -abstract class Interval { +abstract class Interval implements Comparable { static val PRECISION = 32 static val ROUND_DOWN = new MathContext(PRECISION, RoundingMode.FLOOR) static val ROUND_UP = new MathContext(PRECISION, RoundingMode.CEILING) @@ -24,35 +24,35 @@ abstract class Interval { def mayNotEqual(Interval other) { !mustEqual(other) } - + abstract def boolean mustBeLessThan(Interval other) - + abstract def boolean mayBeLessThan(Interval other) - + def mustBeLessThanOrEqual(Interval other) { !mayBeGreaterThan(other) } - + def mayBeLessThanOrEqual(Interval other) { !mustBeGreaterThan(other) } - + def mustBeGreaterThan(Interval other) { other.mustBeLessThan(this) } - + def mayBeGreaterThan(Interval other) { other.mayBeLessThan(this) } - + def mustBeGreaterThanOrEqual(Interval other) { other.mustBeLessThanOrEqual(this) } - + def mayBeGreaterThanOrEqual(Interval other) { other.mayBeLessThanOrEqual(this) } - + abstract def Interval join(Interval other) def operator_plus() { @@ -65,6 +65,8 @@ abstract class Interval { abstract def Interval operator_minus(Interval other) + abstract def Interval operator_multiply(int count) + abstract def Interval operator_multiply(Interval other) abstract def Interval operator_divide(Interval other) @@ -77,15 +79,15 @@ abstract class Interval { override mayEqual(Interval other) { false } - + override mustBeLessThan(Interval other) { true } - + override mayBeLessThan(Interval other) { false } - + override join(Interval other) { other } @@ -102,6 +104,10 @@ abstract class Interval { EMPTY } + override operator_multiply(int count) { + EMPTY + } + override operator_multiply(Interval other) { EMPTY } @@ -113,6 +119,15 @@ abstract class Interval { override toString() { "∅" } + + override compareTo(Interval o) { + if (o == EMPTY) { + 0 + } else { + -1 + } + } + } public static val Interval ZERO = new NonEmpty(BigDecimal.ZERO, BigDecimal.ZERO) @@ -170,7 +185,7 @@ abstract class Interval { false } } - + override mustBeLessThan(Interval other) { switch (other) { case EMPTY: true @@ -178,7 +193,7 @@ abstract class Interval { default: throw new IllegalArgumentException("") } } - + override mayBeLessThan(Interval other) { if (other instanceof NonEmpty) { lower === null || other.upper === null || lower < other.upper @@ -186,7 +201,7 @@ abstract class Interval { false } } - + override join(Interval other) { switch (other) { case EMPTY: this @@ -245,6 +260,14 @@ abstract class Interval { } } + override operator_multiply(int count) { + val bigCount = new BigDecimal(count) + new NonEmpty( + lower.tryMultiply(bigCount, ROUND_DOWN), + upper.tryMultiply(bigCount, ROUND_UP) + ) + } + override operator_multiply(Interval other) { switch (other) { case EMPTY: EMPTY @@ -431,5 +454,38 @@ abstract class Interval { override toString() { '''«IF lower === null»(-∞«ELSE»[«lower»«ENDIF», «IF upper === null»∞)«ELSE»«upper»]«ENDIF»''' } + + override compareTo(Interval o) { + switch (o) { + case EMPTY: 1 + NonEmpty: compareTo(o) + default: throw new IllegalArgumentException("") + } + } + + def compareTo(NonEmpty o) { + if (lower === null) { + if (o.lower !== null) { + return -1 + } + } else if (o.lower === null) { // lower !== null + return 1 + } else { // both lower and o.lower are finite + val lowerDifference = lower.compareTo(o.lower) + if (lowerDifference != 0) { + return lowerDifference + } + } + if (upper === null) { + if (o.upper === null) { + return 0 + } else { + return 1 + } + } else if (o.upper === null) { // upper !== null + return -1 + } + upper.compareTo(o.upper) + } } } diff --git a/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.logic2viatra/src/hu/bme/mit/inf/dslreasoner/viatrasolver/logic2viatra/interval/IntervalAggregationMode.java b/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.logic2viatra/src/hu/bme/mit/inf/dslreasoner/viatrasolver/logic2viatra/interval/IntervalAggregationMode.java new file mode 100644 index 00000000..f5bd2efc --- /dev/null +++ b/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.logic2viatra/src/hu/bme/mit/inf/dslreasoner/viatrasolver/logic2viatra/interval/IntervalAggregationMode.java @@ -0,0 +1,66 @@ +package hu.bme.mit.inf.dslreasoner.viatrasolver.logic2viatra.interval; + +import java.util.function.BinaryOperator; + +public enum IntervalAggregationMode implements BinaryOperator { + SUM("intervalSum", "Sum a set of intervals") { + @Override + public IntervalRedBlackNode createNode(Interval interval) { + return new IntervalRedBlackNode(interval) { + public boolean isMultiplicitySensitive() { + return true; + } + + public Interval multiply(Interval interval, int count) { + return interval.operator_multiply(count); + }; + + @Override + public Interval op(Interval left, Interval right) { + return left.operator_plus(right); + } + }; + } + }, + + JOIN("intervalJoin", "Calculate the smallest interval containing all the intervals in a set") { + @Override + public IntervalRedBlackNode createNode(Interval interval) { + return new IntervalRedBlackNode(interval) { + @Override + public Interval op(Interval left, Interval right) { + return left.join(right); + } + }; + } + }; + + private final String modeName; + private final String description; + private final IntervalRedBlackNode empty; + + IntervalAggregationMode(String modeName, String description) { + this.modeName = modeName; + this.description = description; + empty = createNode(null); + } + + public String getModeName() { + return modeName; + } + + public String getDescription() { + return description; + } + + public IntervalRedBlackNode getEmpty() { + return empty; + } + + @Override + public Interval apply(Interval left, Interval right) { + return empty.op(left, right); + } + + public abstract IntervalRedBlackNode createNode(Interval interval); +} diff --git a/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.logic2viatra/src/hu/bme/mit/inf/dslreasoner/viatrasolver/logic2viatra/interval/IntervalAggregationOperator.xtend b/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.logic2viatra/src/hu/bme/mit/inf/dslreasoner/viatrasolver/logic2viatra/interval/IntervalAggregationOperator.xtend new file mode 100644 index 00000000..940c71bb --- /dev/null +++ b/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.logic2viatra/src/hu/bme/mit/inf/dslreasoner/viatrasolver/logic2viatra/interval/IntervalAggregationOperator.xtend @@ -0,0 +1,48 @@ +package hu.bme.mit.inf.dslreasoner.viatrasolver.logic2viatra.interval + +import java.util.stream.Stream +import org.eclipse.viatra.query.runtime.matchers.psystem.aggregations.IMultisetAggregationOperator +import org.eclipse.xtend.lib.annotations.Accessors +import org.eclipse.xtend.lib.annotations.FinalFieldsConstructor + +@FinalFieldsConstructor +class IntervalAggregationOperator implements IMultisetAggregationOperator { + @Accessors val IntervalAggregationMode mode + + override getName() { + mode.modeName + } + + override getShortDescription() { + mode.description + } + + override createNeutral() { + mode.empty + } + + override isNeutral(IntervalRedBlackNode result) { + result.leaf + } + + override update(IntervalRedBlackNode oldResult, Interval updateValue, boolean isInsertion) { + if (isInsertion) { + val newNode = mode.createNode(updateValue) + oldResult.add(newNode) + } else { + oldResult.remove(updateValue) + } + } + + override getAggregate(IntervalRedBlackNode result) { + if (result.leaf) { + null + } else { + result.result + } + } + + override aggregateStream(Stream stream) { + stream.reduce(mode).orElse(null) + } +} diff --git a/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.logic2viatra/src/hu/bme/mit/inf/dslreasoner/viatrasolver/logic2viatra/interval/IntervalRedBlackNode.xtend b/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.logic2viatra/src/hu/bme/mit/inf/dslreasoner/viatrasolver/logic2viatra/interval/IntervalRedBlackNode.xtend new file mode 100644 index 00000000..3aa575bc --- /dev/null +++ b/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.logic2viatra/src/hu/bme/mit/inf/dslreasoner/viatrasolver/logic2viatra/interval/IntervalRedBlackNode.xtend @@ -0,0 +1,177 @@ +package hu.bme.mit.inf.dslreasoner.viatrasolver.logic2viatra.interval + +abstract class IntervalRedBlackNode extends RedBlackNode { + public val Interval interval + public var int count = 1 + public var Interval result + + new(Interval interval) { + this.interval = interval + } + + def boolean isMultiplicitySensitive() { + false + } + + def Interval multiply(Interval interval, int count) { + interval + } + + abstract def Interval op(Interval left, Interval right) + + override augment() { + val value = calcualteAugmentation() + if (result == value) { + false + } else { + result = value + true + } + } + + private def calcualteAugmentation() { + var value = multiply(interval, count) + if (!left.leaf) { + value = op(value, left.result) + } + if (!right.leaf) { + value = op(value, right.result) + } + value + } + + override assertNodeIsValid() { + super.assertNodeIsValid() + if (leaf) { + return + } + if (count <= 0) { + throw new IllegalStateException("Node with nonpositive count") + } + val value = calcualteAugmentation() + if (result != value) { + throw new IllegalStateException("Node with invalid augmentation: " + result + " != " + value) + } + } + + override assertSubtreeIsValid() { + super.assertSubtreeIsValid() + assertNodeIsValid() + } + + override compareTo(IntervalRedBlackNode other) { + if (leaf || other.leaf) { + throw new IllegalArgumentException("One of the nodes is a leaf node") + } + interval.compareTo(other.interval) + } + + def add(IntervalRedBlackNode newNode) { + if (parent !== null) { + throw new IllegalArgumentException("This is not the root of a tree") + } + if (leaf) { + newNode.isRed = false + newNode.left = this + newNode.right = this + newNode.parent = null + newNode.augment + return newNode + } + val modifiedNode = addWithoutFixup(newNode) + if (modifiedNode === newNode) { + // Must augment here, because fixInsertion() might call augment() + // on a node repeatedly, which might lose the change notification the + // second time it is called, and the augmentation will fail to + // reach the root. + modifiedNode.augmentRecursively + modifiedNode.isRed = true + return modifiedNode.fixInsertion + } + if (multiplicitySensitive) { + modifiedNode.augmentRecursively + } + this + } + + private def addWithoutFixup(IntervalRedBlackNode newNode) { + var node = this + while (!node.leaf) { + val comparison = node.interval.compareTo(newNode.interval) + if (comparison < 0) { + if (node.left.leaf) { + newNode.left = node.left + newNode.right = node.left + node.left = newNode + newNode.parent = node + return newNode + } else { + node = node.left + } + } else if (comparison > 0) { + if (node.right.leaf) { + newNode.left = node.right + newNode.right = node.right + node.right = newNode + newNode.parent = node + return newNode + } else { + node = node.right + } + } else { // comparison == 0 + newNode.parent = null + node.count++ + return node + } + } + throw new IllegalStateException("Reached leaf node while searching for insertion point") + } + + private def augmentRecursively() { + for (var node = this; node !== null; node = node.parent) { + if (!node.augment) { + return + } + } + } + + def remove(Interval interval) { + val node = find(interval) + node.count-- + if (node.count == 0) { + return node.remove + } + if (multiplicitySensitive) { + node.augmentRecursively + } + this + } + + private def find(Interval interval) { + var node = this + while (!node.leaf) { + val comparison = node.interval.compareTo(interval) + if (comparison < 0) { + node = node.left + } else if (comparison > 0) { + node = node.right + } else { // comparison == 0 + return node + } + } + throw new IllegalStateException("Reached leaf node while searching for interval to remove") + } + + override toString() { + if (leaf) { + "L" + } else { + ''' + «IF isRed»R«ELSE»B«ENDIF» «count»«interval» : «result» + «left» + «right» + ''' + } + } + +} diff --git a/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.logic2viatra/src/hu/bme/mit/inf/dslreasoner/viatrasolver/logic2viatra/interval/RedBlackNode.java b/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.logic2viatra/src/hu/bme/mit/inf/dslreasoner/viatrasolver/logic2viatra/interval/RedBlackNode.java new file mode 100644 index 00000000..8c40816b --- /dev/null +++ b/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.logic2viatra/src/hu/bme/mit/inf/dslreasoner/viatrasolver/logic2viatra/interval/RedBlackNode.java @@ -0,0 +1,1392 @@ +/* + * The MIT License (MIT) + * + * Copyright (c) 2016 btrekkie + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ +package hu.bme.mit.inf.dslreasoner.viatrasolver.logic2viatra.interval; + +import java.lang.reflect.Array; +import java.util.Collection; +import java.util.Comparator; +import java.util.HashSet; +import java.util.Iterator; +import java.util.Set; + +/** + * A node in a red-black tree ( https://en.wikipedia.org/wiki/Red%E2%80%93black_tree ). Compared to a class like Java's + * TreeMap, RedBlackNode is a low-level data structure. The internals of a node are exposed as public fields, allowing + * clients to directly observe and manipulate the structure of the tree. This gives clients flexibility, although it + * also enables them to violate the red-black or BST properties. The RedBlackNode class provides methods for performing + * various standard operations, such as insertion and removal. + * + * Unlike most implementations of binary search trees, RedBlackNode supports arbitrary augmentation. By subclassing + * RedBlackNode, clients can add arbitrary data and augmentation information to each node. For example, if we were to + * use a RedBlackNode subclass to implement a sorted set, the subclass would have a field storing an element in the set. + * If we wanted to keep track of the number of non-leaf nodes in each subtree, we would store this as a "size" field and + * override augment() to update this field. All RedBlackNode methods (such as "insert" and remove()) call augment() as + * necessary to correctly maintain the augmentation information, unless otherwise indicated. + * + * The values of the tree are stored in the non-leaf nodes. RedBlackNode does not support use cases where values must be + * stored in the leaf nodes. It is recommended that all of the leaf nodes in a given tree be the same (black) + * RedBlackNode instance, to save space. The root of an empty tree is a leaf node, as opposed to null. + * + * For reference, a red-black tree is a binary search tree satisfying the following properties: + * + * - Every node is colored red or black. + * - The leaf nodes, which are dummy nodes that do not store any values, are colored black. + * - The root is black. + * - Both children of each red node are black. + * - Every path from the root to a leaf contains the same number of black nodes. + * + * @param The type of node in the tree. For example, we might have + * "class FooNode extends RedBlackNode>". + * @author Bill Jacobs + */ +public abstract class RedBlackNode> implements Comparable { + /** A Comparator that compares Comparable elements using their natural order. */ + private static final Comparator> NATURAL_ORDER = new Comparator>() { + @Override + public int compare(Comparable value1, Comparable value2) { + return value1.compareTo(value2); + } + }; + + /** The parent of this node, if any. "parent" is null if this is a leaf node. */ + public N parent; + + /** The left child of this node. "left" is null if this is a leaf node. */ + public N left; + + /** The right child of this node. "right" is null if this is a leaf node. */ + public N right; + + /** Whether the node is colored red, as opposed to black. */ + public boolean isRed; + + /** + * Sets any augmentation information about the subtree rooted at this node that is stored in this node. For + * example, if we augment each node by subtree size (the number of non-leaf nodes in the subtree), this method would + * set the size field of this node to be equal to the size field of the left child plus the size field of the right + * child plus one. + * + * "Augmentation information" is information that we can compute about a subtree rooted at some node, preferably + * based only on the augmentation information in the node's two children and the information in the node. Examples + * of augmentation information are the sum of the values in a subtree and the number of non-leaf nodes in a subtree. + * Augmentation information may not depend on the colors of the nodes. + * + * This method returns whether the augmentation information in any of the ancestors of this node might have been + * affected by changes in this subtree since the last call to augment(). In the usual case, where the augmentation + * information depends only on the information in this node and the augmentation information in its immediate + * children, this is equivalent to whether the augmentation information changed as a result of this call to + * augment(). For example, in the case of subtree size, this returns whether the value of the size field prior to + * calling augment() differed from the size field of the left child plus the size field of the right child plus one. + * False positives are permitted. The return value is unspecified if we have not called augment() on this node + * before. + * + * This method may assume that this is not a leaf node. It may not assume that the augmentation information stored + * in any of the tree's nodes is correct. However, if the augmentation information stored in all of the node's + * descendants is correct, then the augmentation information stored in this node must be correct after calling + * augment(). + */ + public boolean augment() { + return false; + } + + /** + * Throws a RuntimeException if we detect that this node locally violates any invariants specific to this subclass + * of RedBlackNode. For example, if this stores the size of the subtree rooted at this node, this should throw a + * RuntimeException if the size field of this is not equal to the size field of the left child plus the size field + * of the right child plus one. Note that we may call this on a leaf node. + * + * assertSubtreeIsValid() calls assertNodeIsValid() on each node, or at least starts to do so until it detects a + * problem. assertNodeIsValid() should assume the node is in a tree that satisfies all properties common to all + * red-black trees, as assertSubtreeIsValid() is responsible for such checks. assertNodeIsValid() should be + * "downward-looking", i.e. it should ignore any information in "parent", and it should be "local", i.e. it should + * only check a constant number of descendants. To include "global" checks, such as verifying the BST property + * concerning ordering, override assertSubtreeIsValid(). assertOrderIsValid is useful for checking the BST + * property. + */ + public void assertNodeIsValid() { + + } + + /** Returns whether this is a leaf node. */ + public boolean isLeaf() { + return left == null; + } + + /** Returns the root of the tree that contains this node. */ + public N root() { + @SuppressWarnings("unchecked") + N node = (N)this; + while (node.parent != null) { + node = node.parent; + } + return node; + } + + /** Returns the first node in the subtree rooted at this node, if any. */ + public N min() { + if (isLeaf()) { + return null; + } + @SuppressWarnings("unchecked") + N node = (N)this; + while (!node.left.isLeaf()) { + node = node.left; + } + return node; + } + + /** Returns the last node in the subtree rooted at this node, if any. */ + public N max() { + if (isLeaf()) { + return null; + } + @SuppressWarnings("unchecked") + N node = (N)this; + while (!node.right.isLeaf()) { + node = node.right; + } + return node; + } + + /** Returns the node immediately before this in the tree that contains this node, if any. */ + public N predecessor() { + if (!left.isLeaf()) { + N node; + for (node = left; !node.right.isLeaf(); node = node.right); + return node; + } else if (parent == null) { + return null; + } else { + @SuppressWarnings("unchecked") + N node = (N)this; + while (node.parent != null && node.parent.left == node) { + node = node.parent; + } + return node.parent; + } + } + + /** Returns the node immediately after this in the tree that contains this node, if any. */ + public N successor() { + if (!right.isLeaf()) { + N node; + for (node = right; !node.left.isLeaf(); node = node.left); + return node; + } else if (parent == null) { + return null; + } else { + @SuppressWarnings("unchecked") + N node = (N)this; + while (node.parent != null && node.parent.right == node) { + node = node.parent; + } + return node.parent; + } + } + + /** + * Performs a left rotation about this node. This method assumes that !isLeaf() && !right.isLeaf(). It calls + * augment() on this node and on its resulting parent. However, it does not call augment() on any of the resulting + * parent's ancestors, because that is normally the responsibility of the caller. + * @return The return value from calling augment() on the resulting parent. + */ + public boolean rotateLeft() { + if (isLeaf() || right.isLeaf()) { + throw new IllegalArgumentException("The node or its right child is a leaf"); + } + N newParent = right; + right = newParent.left; + @SuppressWarnings("unchecked") + N nThis = (N)this; + if (!right.isLeaf()) { + right.parent = nThis; + } + newParent.parent = parent; + parent = newParent; + newParent.left = nThis; + if (newParent.parent != null) { + if (newParent.parent.left == this) { + newParent.parent.left = newParent; + } else { + newParent.parent.right = newParent; + } + } + augment(); + return newParent.augment(); + } + + /** + * Performs a right rotation about this node. This method assumes that !isLeaf() && !left.isLeaf(). It calls + * augment() on this node and on its resulting parent. However, it does not call augment() on any of the resulting + * parent's ancestors, because that is normally the responsibility of the caller. + * @return The return value from calling augment() on the resulting parent. + */ + public boolean rotateRight() { + if (isLeaf() || left.isLeaf()) { + throw new IllegalArgumentException("The node or its left child is a leaf"); + } + N newParent = left; + left = newParent.right; + @SuppressWarnings("unchecked") + N nThis = (N)this; + if (!left.isLeaf()) { + left.parent = nThis; + } + newParent.parent = parent; + parent = newParent; + newParent.right = nThis; + if (newParent.parent != null) { + if (newParent.parent.left == this) { + newParent.parent.left = newParent; + } else { + newParent.parent.right = newParent; + } + } + augment(); + return newParent.augment(); + } + + /** + * Performs red-black insertion fixup. To be more precise, this fixes a tree that satisfies all of the requirements + * of red-black trees, except that this may be a red child of a red node, and if this is the root, the root may be + * red. node.isRed must initially be true. This method assumes that this is not a leaf node. The method performs + * any rotations by calling rotateLeft() and rotateRight(). This method is more efficient than fixInsertion if + * "augment" is false or augment() might return false. + * @param augment Whether to set the augmentation information for "node" and its ancestors, by calling augment(). + */ + public void fixInsertionWithoutGettingRoot(boolean augment) { + if (!isRed) { + throw new IllegalArgumentException("The node must be red"); + } + boolean changed = augment; + if (augment) { + augment(); + } + + RedBlackNode node = this; + while (node.parent != null && node.parent.isRed) { + N parent = node.parent; + N grandparent = parent.parent; + if (grandparent.left.isRed && grandparent.right.isRed) { + grandparent.left.isRed = false; + grandparent.right.isRed = false; + grandparent.isRed = true; + + if (changed) { + changed = parent.augment(); + if (changed) { + changed = grandparent.augment(); + } + } + node = grandparent; + } else { + if (parent.left == node) { + if (grandparent.right == parent) { + parent.rotateRight(); + node = parent; + parent = node.parent; + } + } else if (grandparent.left == parent) { + parent.rotateLeft(); + node = parent; + parent = node.parent; + } + + if (parent.left == node) { + boolean grandparentChanged = grandparent.rotateRight(); + if (augment) { + changed = grandparentChanged; + } + } else { + boolean grandparentChanged = grandparent.rotateLeft(); + if (augment) { + changed = grandparentChanged; + } + } + + parent.isRed = false; + grandparent.isRed = true; + node = parent; + break; + } + } + + if (node.parent == null) { + node.isRed = false; + } + if (changed) { + for (node = node.parent; node != null; node = node.parent) { + if (!node.augment()) { + break; + } + } + } + } + + /** + * Performs red-black insertion fixup. To be more precise, this fixes a tree that satisfies all of the requirements + * of red-black trees, except that this may be a red child of a red node, and if this is the root, the root may be + * red. node.isRed must initially be true. This method assumes that this is not a leaf node. The method performs + * any rotations by calling rotateLeft() and rotateRight(). This method is more efficient than fixInsertion() if + * augment() might return false. + */ + public void fixInsertionWithoutGettingRoot() { + fixInsertionWithoutGettingRoot(true); + } + + /** + * Performs red-black insertion fixup. To be more precise, this fixes a tree that satisfies all of the requirements + * of red-black trees, except that this may be a red child of a red node, and if this is the root, the root may be + * red. node.isRed must initially be true. This method assumes that this is not a leaf node. The method performs + * any rotations by calling rotateLeft() and rotateRight(). + * @param augment Whether to set the augmentation information for "node" and its ancestors, by calling augment(). + * @return The root of the resulting tree. + */ + public N fixInsertion(boolean augment) { + fixInsertionWithoutGettingRoot(augment); + return root(); + } + + /** + * Performs red-black insertion fixup. To be more precise, this fixes a tree that satisfies all of the requirements + * of red-black trees, except that this may be a red child of a red node, and if this is the root, the root may be + * red. node.isRed must initially be true. This method assumes that this is not a leaf node. The method performs + * any rotations by calling rotateLeft() and rotateRight(). + * @return The root of the resulting tree. + */ + public N fixInsertion() { + fixInsertionWithoutGettingRoot(true); + return root(); + } + + /** Returns a Comparator that compares instances of N using their natural order, as in N.compareTo. */ + @SuppressWarnings({"rawtypes", "unchecked"}) + private Comparator naturalOrder() { + Comparator comparator = (Comparator)NATURAL_ORDER; + return (Comparator)comparator; + } + + /** + * Inserts the specified node into the tree rooted at this node. Assumes this is the root. We treat newNode as a + * solitary node that does not belong to any tree, and we ignore its initial "parent", "left", "right", and isRed + * fields. + * + * If it is not efficient or convenient to find the location for a node using a Comparator, then you should manually + * add the node to the appropriate location, color it red, and call fixInsertion(). + * + * @param newNode The node to insert. + * @param allowDuplicates Whether to insert newNode if there is an equal node in the tree. To check whether we + * inserted newNode, check whether newNode.parent is null and the return value differs from newNode. + * @param comparator A comparator indicating where to put the node. If this is null, we use the nodes' natural + * order, as in N.compareTo. If you are passing null, then you must override the compareTo method, because the + * default implementation requires the nodes to already be in the same tree. + * @return The root of the resulting tree. + */ + public N insert(N newNode, boolean allowDuplicates, Comparator comparator) { + if (parent != null) { + throw new IllegalArgumentException("This is not the root of a tree"); + } + @SuppressWarnings("unchecked") + N nThis = (N)this; + if (isLeaf()) { + newNode.isRed = false; + newNode.left = nThis; + newNode.right = nThis; + newNode.parent = null; + newNode.augment(); + return newNode; + } + if (comparator == null) { + comparator = naturalOrder(); + } + + N node = nThis; + int comparison; + while (true) { + comparison = comparator.compare(newNode, node); + if (comparison < 0) { + if (!node.left.isLeaf()) { + node = node.left; + } else { + newNode.left = node.left; + newNode.right = node.left; + node.left = newNode; + newNode.parent = node; + break; + } + } else if (comparison > 0 || allowDuplicates) { + if (!node.right.isLeaf()) { + node = node.right; + } else { + newNode.left = node.right; + newNode.right = node.right; + node.right = newNode; + newNode.parent = node; + break; + } + } else { + newNode.parent = null; + return nThis; + } + } + newNode.isRed = true; + return newNode.fixInsertion(); + } + + /** + * Moves this node to its successor's former position in the tree and vice versa, i.e. sets the "left", "right", + * "parent", and isRed fields of each. This method assumes that this is not a leaf node. + * @return The node with which we swapped. + */ + private N swapWithSuccessor() { + N replacement = successor(); + boolean oldReplacementIsRed = replacement.isRed; + N oldReplacementLeft = replacement.left; + N oldReplacementRight = replacement.right; + N oldReplacementParent = replacement.parent; + + replacement.isRed = isRed; + replacement.left = left; + replacement.right = right; + replacement.parent = parent; + if (parent != null) { + if (parent.left == this) { + parent.left = replacement; + } else { + parent.right = replacement; + } + } + + @SuppressWarnings("unchecked") + N nThis = (N)this; + isRed = oldReplacementIsRed; + left = oldReplacementLeft; + right = oldReplacementRight; + if (oldReplacementParent == this) { + parent = replacement; + parent.right = nThis; + } else { + parent = oldReplacementParent; + parent.left = nThis; + } + + replacement.right.parent = replacement; + if (!replacement.left.isLeaf()) { + replacement.left.parent = replacement; + } + if (!right.isLeaf()) { + right.parent = nThis; + } + return replacement; + } + + /** + * Performs red-black deletion fixup. To be more precise, this fixes a tree that satisfies all of the requirements + * of red-black trees, except that all paths from the root to a leaf that pass through the sibling of this node have + * one fewer black node than all other root-to-leaf paths. This method assumes that this is not a leaf node. + */ + private void fixSiblingDeletion() { + RedBlackNode sibling = this; + boolean changed = true; + boolean haveAugmentedParent = false; + boolean haveAugmentedGrandparent = false; + while (true) { + N parent = sibling.parent; + if (sibling.isRed) { + parent.isRed = true; + sibling.isRed = false; + if (parent.left == sibling) { + changed = parent.rotateRight(); + sibling = parent.left; + } else { + changed = parent.rotateLeft(); + sibling = parent.right; + } + haveAugmentedParent = true; + haveAugmentedGrandparent = true; + } else if (!sibling.left.isRed && !sibling.right.isRed) { + sibling.isRed = true; + if (parent.isRed) { + parent.isRed = false; + break; + } else { + if (changed && !haveAugmentedParent) { + changed = parent.augment(); + } + N grandparent = parent.parent; + if (grandparent == null) { + break; + } else if (grandparent.left == parent) { + sibling = grandparent.right; + } else { + sibling = grandparent.left; + } + haveAugmentedParent = haveAugmentedGrandparent; + haveAugmentedGrandparent = false; + } + } else { + if (sibling == parent.left) { + if (!sibling.left.isRed) { + sibling.rotateLeft(); + sibling = sibling.parent; + } + } else if (!sibling.right.isRed) { + sibling.rotateRight(); + sibling = sibling.parent; + } + sibling.isRed = parent.isRed; + parent.isRed = false; + if (sibling == parent.left) { + sibling.left.isRed = false; + changed = parent.rotateRight(); + } else { + sibling.right.isRed = false; + changed = parent.rotateLeft(); + } + haveAugmentedParent = haveAugmentedGrandparent; + haveAugmentedGrandparent = false; + break; + } + } + + // Update augmentation info + N parent = sibling.parent; + if (changed && parent != null) { + if (!haveAugmentedParent) { + changed = parent.augment(); + } + if (changed && parent.parent != null) { + parent = parent.parent; + if (!haveAugmentedGrandparent) { + changed = parent.augment(); + } + if (changed) { + for (parent = parent.parent; parent != null; parent = parent.parent) { + if (!parent.augment()) { + break; + } + } + } + } + } + } + + /** + * Removes this node from the tree that contains it. The effect of this method on the fields of this node is + * unspecified. This method assumes that this is not a leaf node. This method is more efficient than remove() if + * augment() might return false. + * + * If the node has two children, we begin by moving the node's successor to its former position, by changing the + * successor's "left", "right", "parent", and isRed fields. + */ + public void removeWithoutGettingRoot() { + if (isLeaf()) { + throw new IllegalArgumentException("Attempted to remove a leaf node"); + } + N replacement; + if (left.isLeaf() || right.isLeaf()) { + replacement = null; + } else { + replacement = swapWithSuccessor(); + } + + N child; + if (!left.isLeaf()) { + child = left; + } else if (!right.isLeaf()) { + child = right; + } else { + child = null; + } + + if (child != null) { + // Replace this node with its child + child.parent = parent; + if (parent != null) { + if (parent.left == this) { + parent.left = child; + } else { + parent.right = child; + } + } + child.isRed = false; + + if (child.parent != null) { + N parent; + for (parent = child.parent; parent != null; parent = parent.parent) { + if (!parent.augment()) { + break; + } + } + } + } else if (parent != null) { + // Replace this node with a leaf node + N leaf = left; + N parent = this.parent; + N sibling; + if (parent.left == this) { + parent.left = leaf; + sibling = parent.right; + } else { + parent.right = leaf; + sibling = parent.left; + } + + if (!isRed) { + RedBlackNode siblingNode = sibling; + siblingNode.fixSiblingDeletion(); + } else { + while (parent != null) { + if (!parent.augment()) { + break; + } + parent = parent.parent; + } + } + } + + if (replacement != null) { + replacement.augment(); + for (N parent = replacement.parent; parent != null; parent = parent.parent) { + if (!parent.augment()) { + break; + } + } + } + + // Clear any previously existing links, so that we're more likely to encounter an exception if we attempt to + // access the removed node + parent = null; + left = null; + right = null; + isRed = true; + } + + /** + * Removes this node from the tree that contains it. The effect of this method on the fields of this node is + * unspecified. This method assumes that this is not a leaf node. + * + * If the node has two children, we begin by moving the node's successor to its former position, by changing the + * successor's "left", "right", "parent", and isRed fields. + * + * @return The root of the resulting tree. + */ + public N remove() { + if (isLeaf()) { + throw new IllegalArgumentException("Attempted to remove a leaf node"); + } + + // Find an arbitrary non-leaf node in the tree other than this node + N node; + if (parent != null) { + node = parent; + } else if (!left.isLeaf()) { + node = left; + } else if (!right.isLeaf()) { + node = right; + } else { + return left; + } + + removeWithoutGettingRoot(); + return node.root(); + } + + /** + * Returns the root of a perfectly height-balanced subtree containing the next "size" (non-leaf) nodes from + * "iterator", in iteration order. This method is responsible for setting the "left", "right", "parent", and isRed + * fields of the nodes, and calling augment() as appropriate. It ignores the initial values of the "left", "right", + * "parent", and isRed fields. + * @param iterator The nodes. + * @param size The number of nodes. + * @param height The "height" of the subtree's root node above the deepest leaf in the tree that contains it. Since + * insertion fixup is slow if there are too many red nodes and deleteion fixup is slow if there are too few red + * nodes, we compromise and have red nodes at every fourth level. We color a node red iff its "height" is equal + * to 1 mod 4. + * @param leaf The leaf node. + * @return The root of the subtree. + */ + private static > N createTree( + Iterator iterator, int size, int height, N leaf) { + if (size == 0) { + return leaf; + } else { + N left = createTree(iterator, (size - 1) / 2, height - 1, leaf); + N node = iterator.next(); + N right = createTree(iterator, size / 2, height - 1, leaf); + + node.isRed = height % 4 == 1; + node.left = left; + node.right = right; + if (!left.isLeaf()) { + left.parent = node; + } + if (!right.isLeaf()) { + right.parent = node; + } + + node.augment(); + return node; + } + } + + /** + * Returns the root of a perfectly height-balanced tree containing the specified nodes, in iteration order. This + * method is responsible for setting the "left", "right", "parent", and isRed fields of the nodes (excluding + * "leaf"), and calling augment() as appropriate. It ignores the initial values of the "left", "right", "parent", + * and isRed fields. + * @param nodes The nodes. + * @param leaf The leaf node. + * @return The root of the tree. + */ + public static > N createTree(Collection nodes, N leaf) { + int size = nodes.size(); + if (size == 0) { + return leaf; + } + + int height = 0; + for (int subtreeSize = size; subtreeSize > 0; subtreeSize /= 2) { + height++; + } + + N node = createTree(nodes.iterator(), size, height, leaf); + node.parent = null; + node.isRed = false; + return node; + } + + /** + * Concatenates to the end of the tree rooted at this node. To be precise, given that all of the nodes in this + * precede the node "pivot", which precedes all of the nodes in "last", this returns the root of a tree containing + * all of these nodes. This method destroys the trees rooted at "this" and "last". We treat "pivot" as a solitary + * node that does not belong to any tree, and we ignore its initial "parent", "left", "right", and isRed fields. + * This method assumes that this node and "last" are the roots of their respective trees. + * + * This method takes O(log N) time. It is more efficient than inserting "pivot" and then calling concatenate(last). + * It is considerably more efficient than inserting "pivot" and all of the nodes in "last". + */ + public N concatenate(N last, N pivot) { + // If the black height of "first", where first = this, is less than or equal to that of "last", starting at the + // root of "last", we keep going left until we reach a black node whose black height is equal to that of + // "first". Then, we make "pivot" the parent of that node and of "first", coloring it red, and perform + // insertion fixup on the pivot. If the black height of "first" is greater than that of "last", we do the + // mirror image of the above. + + if (parent != null) { + throw new IllegalArgumentException("This is not the root of a tree"); + } + if (last.parent != null) { + throw new IllegalArgumentException("\"last\" is not the root of a tree"); + } + + // Compute the black height of the trees + int firstBlackHeight = 0; + @SuppressWarnings("unchecked") + N first = (N)this; + for (N node = first; node != null; node = node.right) { + if (!node.isRed) { + firstBlackHeight++; + } + } + int lastBlackHeight = 0; + for (N node = last; node != null; node = node.right) { + if (!node.isRed) { + lastBlackHeight++; + } + } + + // Identify the children and parent of pivot + N firstChild = first; + N lastChild = last; + N parent; + if (firstBlackHeight <= lastBlackHeight) { + parent = null; + int blackHeight = lastBlackHeight; + while (blackHeight > firstBlackHeight) { + if (!lastChild.isRed) { + blackHeight--; + } + parent = lastChild; + lastChild = lastChild.left; + } + if (lastChild.isRed) { + parent = lastChild; + lastChild = lastChild.left; + } + } else { + parent = null; + int blackHeight = firstBlackHeight; + while (blackHeight > lastBlackHeight) { + if (!firstChild.isRed) { + blackHeight--; + } + parent = firstChild; + firstChild = firstChild.right; + } + if (firstChild.isRed) { + parent = firstChild; + firstChild = firstChild.right; + } + } + + // Add "pivot" to the tree + pivot.isRed = true; + pivot.parent = parent; + if (parent != null) { + if (firstBlackHeight < lastBlackHeight) { + parent.left = pivot; + } else { + parent.right = pivot; + } + } + pivot.left = firstChild; + if (!firstChild.isLeaf()) { + firstChild.parent = pivot; + } + pivot.right = lastChild; + if (!lastChild.isLeaf()) { + lastChild.parent = pivot; + } + + // Perform insertion fixup + return pivot.fixInsertion(); + } + + /** + * Concatenates the tree rooted at "last" to the end of the tree rooted at this node. To be precise, given that all + * of the nodes in this precede all of the nodes in "last", this returns the root of a tree containing all of these + * nodes. This method destroys the trees rooted at "this" and "last". It assumes that this node and "last" are the + * roots of their respective trees. This method takes O(log N) time. It is considerably more efficient than + * inserting all of the nodes in "last". + */ + public N concatenate(N last) { + if (parent != null || last.parent != null) { + throw new IllegalArgumentException("The node is not the root of a tree"); + } + if (isLeaf()) { + return last; + } else if (last.isLeaf()) { + @SuppressWarnings("unchecked") + N nThis = (N)this; + return nThis; + } else { + N node = last.min(); + last = node.remove(); + return concatenate(last, node); + } + } + + /** + * Splits the tree rooted at this node into two trees, so that the first element of the return value is the root of + * a tree consisting of the nodes that were before the specified node, and the second element of the return value is + * the root of a tree consisting of the nodes that were equal to or after the specified node. This method is + * destructive, meaning it does not preserve the original tree. It assumes that this node is the root and is in the + * same tree as splitNode. It takes O(log N) time. It is considerably more efficient than removing all of the + * nodes at or after splitNode and then creating a new tree from those nodes. + * @param The node at which to split the tree. + * @return An array consisting of the resulting trees. + */ + public N[] split(N splitNode) { + // To split the tree, we accumulate a pre-split tree and a post-split tree. We walk down the tree toward the + // position where we are splitting. Whenever we go left, we concatenate the right subtree with the post-split + // tree, and whenever we go right, we concatenate the pre-split tree with the left subtree. We use the + // concatenation algorithm described in concatenate(Object, Object). For the pivot, we use the last node where + // we went left in the case of a left move, and the last node where we went right in the case of a right move. + // + // The method uses the following variables: + // + // node: The current node in our walk down the tree. + // first: A node on the right spine of the pre-split tree. At the beginning of each iteration, it is the black + // node with the same black height as "node". If the pre-split tree is empty, this is null instead. + // firstParent: The parent of "first". If the pre-split tree is empty, this is null. Otherwise, this is the + // same as first.parent, unless first.isLeaf(). + // firstPivot: The node where we last went right, i.e. the next node to use as a pivot when concatenating with + // the pre-split tree. + // advanceFirst: Whether to set "first" to be its next black descendant at the end of the loop. + // last, lastParent, lastPivot, advanceLast: Analogous to "first", firstParent, firstPivot, and advanceFirst, + // but for the post-split tree. + if (parent != null) { + throw new IllegalArgumentException("This is not the root of a tree"); + } + if (isLeaf() || splitNode.isLeaf()) { + throw new IllegalArgumentException("The root or the split node is a leaf"); + } + + // Create an array containing the path from the root to splitNode + int depth = 1; + N parent; + for (parent = splitNode; parent.parent != null; parent = parent.parent) { + depth++; + } + if (parent != this) { + throw new IllegalArgumentException("The split node does not belong to this tree"); + } + RedBlackNode[] path = new RedBlackNode[depth]; + for (parent = splitNode; parent != null; parent = parent.parent) { + depth--; + path[depth] = parent; + } + + @SuppressWarnings("unchecked") + N node = (N)this; + N first = null; + N firstParent = null; + N last = null; + N lastParent = null; + N firstPivot = null; + N lastPivot = null; + while (!node.isLeaf()) { + boolean advanceFirst = !node.isRed && firstPivot != null; + boolean advanceLast = !node.isRed && lastPivot != null; + if ((depth + 1 < path.length && path[depth + 1] == node.left) || depth + 1 == path.length) { + // Left move + if (lastPivot == null) { + // The post-split tree is empty + last = node.right; + last.parent = null; + if (last.isRed) { + last.isRed = false; + lastParent = last; + last = last.left; + } + } else { + // Concatenate node.right and the post-split tree + if (node.right.isRed) { + node.right.isRed = false; + } else if (!node.isRed) { + lastParent = last; + last = last.left; + if (last.isRed) { + lastParent = last; + last = last.left; + } + advanceLast = false; + } + lastPivot.isRed = true; + lastPivot.parent = lastParent; + if (lastParent != null) { + lastParent.left = lastPivot; + } + lastPivot.left = node.right; + if (!lastPivot.left.isLeaf()) { + lastPivot.left.parent = lastPivot; + } + lastPivot.right = last; + if (!last.isLeaf()) { + last.parent = lastPivot; + } + last = lastPivot.left; + lastParent = lastPivot; + lastPivot.fixInsertionWithoutGettingRoot(false); + } + lastPivot = node; + node = node.left; + } else { + // Right move + if (firstPivot == null) { + // The pre-split tree is empty + first = node.left; + first.parent = null; + if (first.isRed) { + first.isRed = false; + firstParent = first; + first = first.right; + } + } else { + // Concatenate the post-split tree and node.left + if (node.left.isRed) { + node.left.isRed = false; + } else if (!node.isRed) { + firstParent = first; + first = first.right; + if (first.isRed) { + firstParent = first; + first = first.right; + } + advanceFirst = false; + } + firstPivot.isRed = true; + firstPivot.parent = firstParent; + if (firstParent != null) { + firstParent.right = firstPivot; + } + firstPivot.right = node.left; + if (!firstPivot.right.isLeaf()) { + firstPivot.right.parent = firstPivot; + } + firstPivot.left = first; + if (!first.isLeaf()) { + first.parent = firstPivot; + } + first = firstPivot.right; + firstParent = firstPivot; + firstPivot.fixInsertionWithoutGettingRoot(false); + } + firstPivot = node; + node = node.right; + } + + depth++; + + // Update "first" and "last" to be the nodes at the proper black height + if (advanceFirst) { + firstParent = first; + first = first.right; + if (first.isRed) { + firstParent = first; + first = first.right; + } + } + if (advanceLast) { + lastParent = last; + last = last.left; + if (last.isRed) { + lastParent = last; + last = last.left; + } + } + } + + // Add firstPivot to the pre-split tree + N leaf = node; + if (first == null) { + first = leaf; + } else { + firstPivot.isRed = true; + firstPivot.parent = firstParent; + if (firstParent != null) { + firstParent.right = firstPivot; + } + firstPivot.left = leaf; + firstPivot.right = leaf; + firstPivot.fixInsertionWithoutGettingRoot(false); + for (first = firstPivot; first.parent != null; first = first.parent) { + first.augment(); + } + first.augment(); + } + + // Add lastPivot to the post-split tree + lastPivot.isRed = true; + lastPivot.parent = lastParent; + if (lastParent != null) { + lastParent.left = lastPivot; + } + lastPivot.left = leaf; + lastPivot.right = leaf; + lastPivot.fixInsertionWithoutGettingRoot(false); + for (last = lastPivot; last.parent != null; last = last.parent) { + last.augment(); + } + last.augment(); + + @SuppressWarnings("unchecked") + N[] result = (N[])Array.newInstance(getClass(), 2); + result[0] = first; + result[1] = last; + return result; + } + + /** + * Returns the lowest common ancestor of this node and "other" - the node that is an ancestor of both and is not the + * parent of a node that is an ancestor of both. Assumes that this is in the same tree as "other". Assumes that + * neither "this" nor "other" is a leaf node. This method may return "this" or "other". + * + * Note that while it is possible to compute the lowest common ancestor in O(P) time, where P is the length of the + * path from this node to "other", the "lca" method is not guaranteed to take O(P) time. If your application + * requires this, then you should write your own lowest common ancestor method. + */ + public N lca(N other) { + if (isLeaf() || other.isLeaf()) { + throw new IllegalArgumentException("One of the nodes is a leaf node"); + } + + // Compute the depth of each node + int depth = 0; + for (N parent = this.parent; parent != null; parent = parent.parent) { + depth++; + } + int otherDepth = 0; + for (N parent = other.parent; parent != null; parent = parent.parent) { + otherDepth++; + } + + // Go up to nodes of the same depth + @SuppressWarnings("unchecked") + N parent = (N)this; + N otherParent = other; + if (depth <= otherDepth) { + for (int i = otherDepth; i > depth; i--) { + otherParent = otherParent.parent; + } + } else { + for (int i = depth; i > otherDepth; i--) { + parent = parent.parent; + } + } + + // Find the LCA + while (parent != otherParent) { + parent = parent.parent; + otherParent = otherParent.parent; + } + if (parent != null) { + return parent; + } else { + throw new IllegalArgumentException("The nodes do not belong to the same tree"); + } + } + + /** + * Returns an integer comparing the position of this node in the tree that contains it with that of "other". Returns + * a negative number if this is earlier, a positive number if this is later, and 0 if this is at the same position. + * Assumes that this is in the same tree as "other". Assumes that neither "this" nor "other" is a leaf node. + * + * The base class's implementation takes O(log N) time. If a RedBlackNode subclass stores a value used to order the + * nodes, then it could override compareTo to compare the nodes' values, which would take O(1) time. + * + * Note that while it is possible to compare the positions of two nodes in O(P) time, where P is the length of the + * path from this node to "other", the default implementation of compareTo is not guaranteed to take O(P) time. If + * your application requires this, then you should write your own comparison method. + */ + @Override + public int compareTo(N other) { + if (isLeaf() || other.isLeaf()) { + throw new IllegalArgumentException("One of the nodes is a leaf node"); + } + + // The algorithm operates as follows: compare the depth of this node to that of "other". If the depth of + // "other" is greater, keep moving up from "other" until we find the ancestor at the same depth. Then, keep + // moving up from "this" and from that node until we reach the lowest common ancestor. The node that arrived + // from the left child of the common ancestor is earlier. The algorithm is analogous if the depth of "other" is + // not greater. + if (this == other) { + return 0; + } + + // Compute the depth of each node + int depth = 0; + RedBlackNode parent; + for (parent = this; parent.parent != null; parent = parent.parent) { + depth++; + } + int otherDepth = 0; + N otherParent; + for (otherParent = other; otherParent.parent != null; otherParent = otherParent.parent) { + otherDepth++; + } + + // Go up to nodes of the same depth + if (depth < otherDepth) { + otherParent = other; + for (int i = otherDepth - 1; i > depth; i--) { + otherParent = otherParent.parent; + } + if (otherParent.parent != this) { + otherParent = otherParent.parent; + } else if (left == otherParent) { + return 1; + } else { + return -1; + } + parent = this; + } else if (depth > otherDepth) { + parent = this; + for (int i = depth - 1; i > otherDepth; i--) { + parent = parent.parent; + } + if (parent.parent != other) { + parent = parent.parent; + } else if (other.left == parent) { + return -1; + } else { + return 1; + } + otherParent = other; + } else { + parent = this; + otherParent = other; + } + + // Keep going up until we reach the lowest common ancestor + while (parent.parent != otherParent.parent) { + parent = parent.parent; + otherParent = otherParent.parent; + } + if (parent.parent == null) { + throw new IllegalArgumentException("The nodes do not belong to the same tree"); + } + if (parent.parent.left == parent) { + return -1; + } else { + return 1; + } + } + + /** Throws a RuntimeException if the RedBlackNode fields of this are not correct for a leaf node. */ + private void assertIsValidLeaf() { + if (left != null || right != null || parent != null || isRed) { + throw new RuntimeException("A leaf node's \"left\", \"right\", \"parent\", or isRed field is incorrect"); + } + } + + /** + * Throws a RuntimeException if the subtree rooted at this node does not satisfy the red-black properties, excluding + * the requirement that the root be black, or it contains a repeated node other than a leaf node. + * @param blackHeight The required number of black nodes in each path from this to a leaf node, including this and + * the leaf node. + * @param visited The nodes we have reached thus far, other than leaf nodes. This method adds the non-leaf nodes in + * the subtree rooted at this node to "visited". + */ + private void assertSubtreeIsValidRedBlack(int blackHeight, Set> visited) { + @SuppressWarnings("unchecked") + N nThis = (N)this; + if (left == null || right == null) { + assertIsValidLeaf(); + if (blackHeight != 1) { + throw new RuntimeException("Not all root-to-leaf paths have the same number of black nodes"); + } + return; + } else if (!visited.add(new Reference(nThis))) { + throw new RuntimeException("The tree contains a repeated non-leaf node"); + } else { + int childBlackHeight; + if (isRed) { + if ((!left.isLeaf() && left.isRed) || (!right.isLeaf() && right.isRed)) { + throw new RuntimeException("A red node has a red child"); + } + childBlackHeight = blackHeight; + } else if (blackHeight == 0) { + throw new RuntimeException("Not all root-to-leaf paths have the same number of black nodes"); + } else { + childBlackHeight = blackHeight - 1; + } + + if (!left.isLeaf() && left.parent != this) { + throw new RuntimeException("left.parent != this"); + } + if (!right.isLeaf() && right.parent != this) { + throw new RuntimeException("right.parent != this"); + } + RedBlackNode leftNode = left; + RedBlackNode rightNode = right; + leftNode.assertSubtreeIsValidRedBlack(childBlackHeight, visited); + rightNode.assertSubtreeIsValidRedBlack(childBlackHeight, visited); + } + } + + /** Calls assertNodeIsValid() on every node in the subtree rooted at this node. */ + private void assertNodesAreValid() { + assertNodeIsValid(); + if (left != null) { + RedBlackNode leftNode = left; + RedBlackNode rightNode = right; + leftNode.assertNodesAreValid(); + rightNode.assertNodesAreValid(); + } + } + + /** + * Throws a RuntimeException if the subtree rooted at this node is not a valid red-black tree, e.g. if a red node + * has a red child or it contains a non-leaf node "node" for which node.left.parent != node. (If parent != null, + * it's okay if isRed is true.) This method is useful for debugging. See also assertSubtreeIsValid(). + */ + public void assertSubtreeIsValidRedBlack() { + if (isLeaf()) { + assertIsValidLeaf(); + } else { + if (parent == null && isRed) { + throw new RuntimeException("The root is red"); + } + + // Compute the black height of the tree + Set> nodes = new HashSet>(); + int blackHeight = 0; + @SuppressWarnings("unchecked") + N node = (N)this; + while (node != null) { + if (!nodes.add(new Reference(node))) { + throw new RuntimeException("The tree contains a repeated non-leaf node"); + } + if (!node.isRed) { + blackHeight++; + } + node = node.left; + } + + assertSubtreeIsValidRedBlack(blackHeight, new HashSet>()); + } + } + + /** + * Throws a RuntimeException if we detect a problem with the subtree rooted at this node, such as a red child of a + * red node or a non-leaf descendant "node" for which node.left.parent != node. This method is useful for + * debugging. RedBlackNode subclasses may want to override assertSubtreeIsValid() to call assertOrderIsValid. + */ + public void assertSubtreeIsValid() { + assertSubtreeIsValidRedBlack(); + assertNodesAreValid(); + } + + /** + * Throws a RuntimeException if the nodes in the subtree rooted at this node are not in the specified order or they + * do not lie in the specified range. Assumes that the subtree rooted at this node is a valid binary tree, i.e. it + * has no repeated nodes other than leaf nodes. + * @param comparator A comparator indicating how the nodes should be ordered. + * @param start The lower limit for nodes in the subtree, if any. + * @param end The upper limit for nodes in the subtree, if any. + */ + private void assertOrderIsValid(Comparator comparator, N start, N end) { + if (!isLeaf()) { + @SuppressWarnings("unchecked") + N nThis = (N)this; + if (start != null && comparator.compare(nThis, start) < 0) { + throw new RuntimeException("The nodes are not ordered correctly"); + } + if (end != null && comparator.compare(nThis, end) > 0) { + throw new RuntimeException("The nodes are not ordered correctly"); + } + RedBlackNode leftNode = left; + RedBlackNode rightNode = right; + leftNode.assertOrderIsValid(comparator, start, nThis); + rightNode.assertOrderIsValid(comparator, nThis, end); + } + } + + /** + * Throws a RuntimeException if the nodes in the subtree rooted at this node are not in the specified order. + * Assumes that this is a valid binary tree, i.e. there are no repeated nodes other than leaf nodes. This method is + * useful for debugging. RedBlackNode subclasses may want to override assertSubtreeIsValid() to call + * assertOrderIsValid. + * @param comparator A comparator indicating how the nodes should be ordered. If this is null, we use the nodes' + * natural order, as in N.compareTo. + */ + public void assertOrderIsValid(Comparator comparator) { + if (comparator == null) { + comparator = naturalOrder(); + } + assertOrderIsValid(comparator, null, null); + } +} diff --git a/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.logic2viatra/src/hu/bme/mit/inf/dslreasoner/viatrasolver/logic2viatra/interval/Reference.java b/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.logic2viatra/src/hu/bme/mit/inf/dslreasoner/viatrasolver/logic2viatra/interval/Reference.java new file mode 100644 index 00000000..a25c167d --- /dev/null +++ b/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.logic2viatra/src/hu/bme/mit/inf/dslreasoner/viatrasolver/logic2viatra/interval/Reference.java @@ -0,0 +1,51 @@ +/* + * The MIT License (MIT) + * + * Copyright (c) 2016 btrekkie + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ +package hu.bme.mit.inf.dslreasoner.viatrasolver.logic2viatra.interval; + +/** + * Wraps a value using reference equality. In other words, two references are equal only if their values are the same + * object instance, as in ==. + * @param The type of value. + */ +class Reference { + /** The value this wraps. */ + private final T value; + + public Reference(T value) { + this.value = value; + } + + public boolean equals(Object obj) { + if (!(obj instanceof Reference)) { + return false; + } + Reference reference = (Reference)obj; + return value == reference.value; + } + + @Override + public int hashCode() { + return System.identityHashCode(value); + } +} -- cgit v1.2.3-54-g00ecf