IntervalTreeMultiSet.java

/*
 * Created by: Karol Sobczak (napewnotrafi@gmail.com)
 */
package org.adblocktv.tagsserver.utils.rbtree;

import java.util.*;
import org.adblocktv.tagsserver.utils.*;

/**
 * An implementation of an interval tree multi-set.
 * @author Karol Sobczak
 */
public class IntervalTreeMultiSet<K extends Comparable, V>
        extends RedBlackTree<K, IntervalTreeMultiSet<K, V>.IntervalTreeNode>
        implements Iterable<IntervalTreeMultiSet<K, V>.IntervalTreeNode> {

    /**
     * An interval tree specific node.
     */
    public class IntervalTreeNode
            extends RedBlackTree<K, IntervalTreeMultiSet<K, V>.IntervalTreeNode>.Node {

        /**
         * An actual interval.
         */
        private Pair<K, K> interval;
        /**
         * The lowest value in a current node subtree.
         */
        private K min;
        /**
         * The highest value in a current node subtree.
         */
        private K max;
        /**
         * An interval tree node specific value.
         */
        private V value;

        @Override
        protected void updatePath() {
            Node nil = getNilNode();
            Node node = this;
            while (node != nil) {
                node.updateSingle();
                node = node.getParent();
            }
        }

        @Override
        protected void updateSingle() {
            //fix extreme values
            IntervalTreeNode left = getLeftChild().getInternalValue();
            IntervalTreeNode right = getRightChild().getInternalValue();
            min = interval.a;
            max = interval.b;
            if (left != null) {
                min = min.compareTo(left.min) < 0 ? min : left.min;
                max = max.compareTo(left.max) > 0 ? max : left.max;
            }
            if (right != null) {
                max = max.compareTo(right.max) > 0 ? max : right.max;
            }
        }

        @Override
        protected void rotateUpdate() {
            updateSingle();
        }

        /**
         * Constructs an interval tree node.
         * @param interval
         */
        private IntervalTreeNode(Pair<K, K> interval, V value) {
            super(interval.a, null);
            this.interval = interval;
            this.value = value;
            setInternalValue(this);
        }

        /**
         * Returns a current node interval.
         * @return a current node interval
         */
        public Pair<K, K> getInterval() {
            return interval;
        }

        /**
         * Returns an interval tree node value.
         * @return an interval tree node value
         */
        public V getValue() {
            return value;
        }

        @Override
        public String toString() {
            return "{ <" + interval.a + "," + interval.b + "> <" + min + "," + max + "> "
                    + (getLeftChild() != getNilNode() ? getLeftChild().toString() : "{ null }")
                    + (getRightChild() != getNilNode() ? getRightChild().toString() : "{ null }")
                    + " }";
        }
    }

    /**
     * An iterator over interval tree nodes.
     */
    private class IntervalTreeMultiSetIterator implements Iterator<IntervalTreeNode> {

        private Iterator<Node> nodesIterator = nodesIterator();

        @Override
        public boolean hasNext() {
            return nodesIterator.hasNext();
        }

        @Override
        public IntervalTreeNode next() {
            return nodesIterator.next().getInternalValue();
        }

        @Override
        public void remove() {
        }
    }
    /**
     * A flag determining if intervals are left exclusive.
     */
    private final boolean leftExclusive;
    /**
     * A flag determining if intervals are right exclusive
     */
    private final boolean rightExclusive;

    /**
     * Compares a low value from a first interval with a high value from a second
     * one (depending on exclusiveness equality might not be possible at all).
     */
    private int compareLowHigh(K low, K high) {
        int result = low.compareTo(high);
        return result != 0 ? result : (leftExclusive | rightExclusive ? 1 : 0);
    }

    /**
     * Compares a low value from an interval with a point value.
     */
    private int compareLowPoint(K low, K point) {
        int result = low.compareTo(point);
        return result != 0 ? result : (leftExclusive ? 1 : 0);
    }

    /**
     * Compares a high value from an interval with a point value.
     */
    private int compareHighPoint(K high, K point) {
        int result = high.compareTo(point);
        return result != 0 ? result : (rightExclusive ? -1 : 0);
    }

    /**
     * Checks whether intervals intersect.
     */
    private boolean intersect(Pair<K, K> x, Pair<K, K> y) {
        return compareLowHigh(x.a, y.b) <= 0 && compareLowHigh(y.a, x.b) <= 0;
    }

    /**
     * Checks whether interval intersects point.
     */
    private boolean intersect(Pair<K, K> x, K point) {
        return compareLowPoint(x.a, point) <= 0 && compareHighPoint(x.b, point) >= 0;
    }

    /**
     * Searches for all nodes intersecting a given interval.
     */
    private void searchAll(
            Pair<K, K> interval,
            IntervalTreeNode node,
            List<IntervalTreeNode> resultNodes) {
        //check whether there are possible intersections in left subtree
        IntervalTreeNode left = node.getLeftChild().getInternalValue();
        if (left != null && compareLowHigh(interval.a, left.max) <= 0) {
            searchAll(interval, left, resultNodes);
        }
        //check whether current node intersects
        if (intersect(node.interval, interval)) {
            resultNodes.add(node);
        }
        //check whether there are possible intersections in right subtree
        IntervalTreeNode right = node.getRightChild().getInternalValue();
        if (right != null && compareLowHigh(right.min, interval.b) <= 0) {
            searchAll(interval, right, resultNodes);
        }
    }

    /**
     * Searches for all nodes intersecting a given point.
     */
    private void searchAll(
            K point,
            IntervalTreeNode node,
            List<IntervalTreeNode> resultNodes) {
        //check whether there are possible intersections in left subtree
        IntervalTreeNode left = node.getLeftChild().getInternalValue();
        if (left != null && compareHighPoint(left.max, point) >= 0) {
            searchAll(point, left, resultNodes);
        }
        //checks whether current node intersects
        if (intersect(node.interval, point)) {
            resultNodes.add(node);
        }
        //check whether there are possible intersections in right subtree
        IntervalTreeNode right = node.getRightChild().getInternalValue();
        if (right != null && compareLowPoint(right.min, point) <= 0) {
            searchAll(point, right, resultNodes);
        }
    }

    /**
     * Constructs an IntervalTreeMultiSet instance.
     * @param leftExclusive a flag determining if intervals are left exclusive
     * @param rightExclusive a flag determining if intervals are right exclusive
     */
    public IntervalTreeMultiSet(boolean leftExclusive, boolean rightExclusive) {
        this.leftExclusive = leftExclusive;
        this.rightExclusive = rightExclusive;
    }

    /**
     * Adds an interval to the interval tree multi-set.
     * @param interval an interval
     * @param value an interval tree node value
     * @return an interval tree node instance (can be used to remove the
     * interval later)
     */
    public IntervalTreeNode add(Pair<K, K> interval, V value) {
        IntervalTreeNode intervalTreeNode = new IntervalTreeNode(interval, value);
        add(intervalTreeNode);
        return intervalTreeNode;
    }

    /**
     * Removes an interval tree node from the interval tree.
     * @param intervalTreeNode an interval tree node instance to be removed
     */
    public void remove(IntervalTreeNode intervalTreeNode) {
        super.remove(intervalTreeNode);
    }

    /**
     * Searches for an interval tree node intersecting with a given interval or
     * null if there is no such node.
     * @param interval an interval
     * @return an interval tree node that intersects with a given interval or
     * null if there is no such node
     */
    public IntervalTreeNode search(Pair<K, K> interval) {
        IntervalTreeNode node = getRootNode().getInternalValue();
        while (node != null && !intersect(node.interval, interval)) {
            IntervalTreeNode left = node.getLeftChild().getInternalValue();
            if (left != null && compareLowHigh(interval.a, left.max) <= 0) {
                node = left;
            } else {
                node = node.getRightChild().getInternalValue();
            }
        }
        return node;
    }

    /**
     * Searches for an interval tree node intersecting with a given point or null
     * if there is no such node.
     * @param point a point
     * @return an interval tree node that intersects with a given point or null
     * if there is no such node
     */
    public IntervalTreeNode search(K point) {
        IntervalTreeNode node = getRootNode().getInternalValue();
        while (node != null && !intersect(node.interval, point)) {
            IntervalTreeNode left = node.getLeftChild().getInternalValue();
            if (left != null && compareHighPoint(left.max, point) >= 0) {
                node = left;
            } else {
                node = node.getRightChild().getInternalValue();
            }
        }
        return node;
    }

    /**
     * Searches for all interval tree nodes intersecting with a given interval.
     * @param interval an interval
     * @return a left ordered list of interval tree nodes intersecting with
     * a given interval
     */
    public List<IntervalTreeNode> searchAll(Pair<K, K> interval) {
        List<IntervalTreeNode> resultNodes = new LinkedList();
        IntervalTreeNode root = getRootNode().getInternalValue();
        if (root != null) {
            searchAll(interval, root, resultNodes);
        }
        return resultNodes;
    }

    /**
     * Searches for all interval tree nodes intersecting with a given point.
     * @param point a point
     * @return a left ordered list of interval tree nodes intersecting with
     * a given point
     */
    public List<IntervalTreeNode> searchAll(K point) {
        List<IntervalTreeNode> resultNodes = new LinkedList();
        IntervalTreeNode root = getRootNode().getInternalValue();
        if (root != null) {
            searchAll(point, root, resultNodes);
        }
        return resultNodes;
    }

    /**
     * Returns an iterator for interval tree nodes.
     * @return an iterator for interval tree nodes
     */
    @Override
    public Iterator<IntervalTreeNode> iterator() {
        return new IntervalTreeMultiSetIterator();
    }
}