package de.renew.net;

import java.io.Serializable;
import java.util.NoSuchElementException;


/**
 * A TimeSet collects a set of doubles interpreted as
 * points of time. The handling is done by an AVL tree,
 * which handles all requests in O(log n) time.
 */
public class TimeSet implements Serializable {
    /** A special singleton object that denotes the empty set.*/
    public static final TimeSet EMPTY = new TimeSet(null, 0, 0, null);

    /**
     * A special singleton object that denotes the
     * set with a single object 0.
     */
    public static final TimeSet ZERO = EMPTY.including(0.0);

    // All instance variables are supposed to be final,
    // but they must not be declared that way due to a compiler bug.

    /** The left subtree which handles the earlier events. */
    private final TimeSet _left;

    /** The local time of the {@code TimeSet}. */
    private final double _time;

    /** The right subtree which handles the later events. */
    private final TimeSet _right;

    /**
     * The number of times that the time of this {@code TimeSet} is contained in the
     * set. This is useful if there are time instances when lots of events happen at once.
     * This is especially important for untimed situations.
     */
    private final int _mult;

    /** The height of this {@code TimeSet}. It is used to balance the tree. */
    private final int _height;

    /** The size of this {@code TimeSet}, which may be queried. */
    private final int _size;

    /** The size of this {@code TimeSet} without counting duplicates. It may be queried. */
    private final int _uniqueSize;

    /**
     * This constructor of a tree node takes care of rotating
     * other tree nodes as required. No modifications are
     * performed for other tree nodes.
     */
    private TimeSet(TimeSet left, double time, int mult, TimeSet right) {
        if (mult == 0) {
            // This is the special empty set.
            if (left != null || right != null || time != 0) {
                throw new RuntimeException("Bad empty time set parameters.");
            }
            _left = null;
            _right = null;
            _mult = 0;
            _time = 0;
            _height = 0;
            _size = 0;
            _uniqueSize = 0;
        } else {
            // This is an ordinary time set.
            int diff = left._height - right._height;
            if (diff >= 2) {
                // Left side too high.
                if (left._left._height > left._right._height) {
                    _left = left._left;
                    _time = left._time;
                    _mult = left._mult;
                    _right = new TimeSet(left._right, time, mult, right);
                } else {
                    _left = new TimeSet(left._left, left._time, left._mult, left._right._left);
                    _time = left._right._time;
                    _mult = left._right._mult;
                    _right = new TimeSet(left._right._right, time, mult, right);
                }
            } else if (diff <= -2) {
                // Right side too high.
                if (right._right._height > right._left._height) {
                    _left = new TimeSet(left, time, mult, right._left);
                    _time = right._time;
                    _mult = right._mult;
                    _right = right._right;
                } else {
                    _left = new TimeSet(left, time, mult, right._left._left);
                    _time = right._left._time;
                    _mult = right._left._mult;
                    _right =
                        new TimeSet(right._left._right, right._time, right._mult, right._right);
                }
            } else {
                // Already well-balanced.
                _left = left;
                _time = time;
                _mult = mult;
                _right = right;
            }


            // This might be optimized and included in the
            // individual cases.
            _height = Math.max(left._height, right._height) + 1;
            _size = left._size + right._size + mult;
            _uniqueSize = left._uniqueSize + right._uniqueSize + 1;
        }
    }

    /**
     * Returns whether the TimeSet is empty.
     *
     * @return whether the TimeSet is empty
     */
    public boolean isEmpty() {
        return _mult == 0;
    }

    // The factory method exposes less of the internal structure 
    // of the time set.
    /**
     * Make a new {@code TimeSet} with the given time and multiplicity.
     *
     * @param time the time value
     * @param mult how often that time value occurs in the set
     * @return a newly created {@code TimeSet} initialized with the given time and multiplicity
     */
    public static TimeSet make(double time, int mult) {
        return new TimeSet(EMPTY, time, mult, EMPTY);
    }

    /**
     * Returns the TimeSet's size.
     *
     * @return the TimeSet's size
     */
    public int getSize() {
        return _size;
    }

    private TimeSet findNode(double searchTime) {
        TimeSet current = this;
        while (current._mult != 0) {
            if (current._time == searchTime) {
                return current;
            } else if (current._time < searchTime) {
                current = current._right;
            } else {
                current = current._left;
            }
        }

        return EMPTY;
    }

    /**
     * Finds how often a given point in time is included in the TimeSet (its multiplicity).
     *
     * @param searchTime the point in time whose multiplicity should be returned
     * @return how often the given time is included in the TimeSet
     */
    public int multiplicity(double searchTime) {
        return findNode(searchTime)._mult;
    }

    /**
     * Returns a copy of this {@code TimeSet} that includes the given {@code newTime} one
     * additional time.
     *
     * @param newTime the point in time to insert into the copy
     * @return a copy of this {@code TimeSet} that includes {@code newTime} one additional time
     */
    public TimeSet including(double newTime) {
        return including(newTime, 1);
    }

    /**
     * Returns a copy of this {@code TimeSet} that includes the given {@code newTime} an additional
     * {@code n} times.
     *
     * @param newTime the point in time to insert into the copy
     * @param n the number of extra times that {@code newTime} should be included in the returned set
     * @return a copy of this TimeSet that includes {@code newTime} an additional {@code n} times
     */
    public TimeSet including(double newTime, int n) {
        if (_mult == 0) {
            // This is an empty time set.
            return make(newTime, n);
        }
        if (newTime == _time) {
            return new TimeSet(_left, _time, _mult + n, _right);
        }

        final TimeSet newLeft;
        final TimeSet newRight;

        // One of the subtrees must be recreated.
        if (newTime < _time) {
            newLeft = _left.including(newTime, n);
            newRight = _right;
        } else {
            newLeft = _left;
            newRight = _right.including(newTime, n);
        }
        return new TimeSet(newLeft, _time, _mult, newRight);
    }

    /**
     * Returns a copy of this {@code TimeSet} from which one occurrence of the given {@code oldTime}
     * has been removed.
     *
     * @param oldTime the time to remove once from the copy
     * @return a copy of this {@code TimeSet} from which one occurrence of {@code oldTime} has been removed
     * @throws NoSuchElementException if {@code oldTime} is not contained in the TimeSet
     */
    public TimeSet excluding(double oldTime) {
        if (_mult == 0) {
            throw new NoSuchElementException();
        }

        TimeSet newLeft;
        TimeSet newRight;
        double newTime;
        int newMult;

        if (oldTime == _time) {
            if (_mult > 1) {
                newLeft = _left;
                newRight = _right;
                newTime = _time;
                newMult = _mult - 1;
            } else if (_right._mult == 0) {
                return _left;
            } else if (_left._mult == 0) {
                return _right;
            } else {
                TimeSetResult reordered = _right.extractLeftmost();
                newLeft = _left;
                newRight = reordered._tree;
                newTime = reordered._time;
                newMult = reordered._mult;
            }
        } else {
            if (oldTime < _time) {
                newLeft = _left.excluding(oldTime);
                newRight = _right;
            } else {
                newLeft = _left;
                newRight = _right.excluding(oldTime);
            }
            newTime = _time;
            newMult = _mult;
        }

        return new TimeSet(newLeft, newTime, newMult, newRight);
    }

    // Must not be called on the empty set.
    private TimeSetResult extractLeftmost() {
        if (_mult == 0) {
            throw new RuntimeException("Illegal invocation of extractLeftmost().");
        }

        if (_left._mult == 0) {
            return new TimeSetResult(_right, _time, _mult);
        }

        TimeSetResult lifted = _left.extractLeftmost();
        return new TimeSetResult(
            new TimeSet(lifted._tree, _time, _mult, _right), lifted._time, lifted._mult);
    }

    /**
     * Fetches the earliest point in time contained in this collection.
     *
     * @return the earliest point in time contained in this collection
     */
    public double earliestTime() {
        TimeSet tree = this;
        while (tree._left._mult != 0) {
            tree = tree._left;
        }
        return tree._time;
    }


    /**
     * Fetches the latest point in time contained in this collection.
     *
     * @return the latest point in time contained in this collection
     */
    public double latestTime() {
        TimeSet tree = this;
        if (_mult == 0) {
            throw new NoSuchElementException();
        }

        while (tree._right._mult != 0) {
            tree = tree._right;
        }

        return tree._time;
    }

    /**
     * Fetches the last point in time that allows a certain delay
     * without missing a given deadline. It is not the same to
     * use deadline-delay as the new deadline, as round-off
     * errors might bias the possible values.
     *
     * @param delay the amount by which the result should be able to be delayed without missing the deadline
     * @param deadline the deadline after which checking for a matching point in time will stop
     * @throws NoSuchElementException if the deadline is missed by all points in time with the given delay
     * @return the last point in time that allows the delay without missing the deadline
    */
    public double latestWithDelay(double delay, double deadline) {
        TimeSet current = this;
        TimeSet best = null;

        while (current._mult != 0) {
            if (current._time + delay <= deadline) {
                // The current node is a possible candidate
                // because it can meet the deadline.
                best = current;

                // Proceed down the right subtree to find better estimates.
                // The left subtree has only worse solutions.
                current = current._right;
            } else {
                // Only the left subtree might have solutions.
                current = current._left;
            }
        }

        if (best == null) {
            throw new NoSuchElementException();
        }

        return best._time;
    }

    /**
     * Returns the unique contents of this set as an array.
     *
     * @return the unique contents of this set as an array
     */
    public double[] asUniqueArray() {
        double[] result = new double[_uniqueSize];
        fillIn(result, 0, true);
        return result;
    }

    /**
     * Returns the contents of this set as a sorted array.
     *
     * @return the contents of this set as a sorted array
     */
    public double[] asArray() {
        double[] result = new double[_size];
        fillIn(result, 0, false);
        return result;
    }

    // Copy the contents of this set into an array.
    private void fillIn(double[] result, int start, boolean unique) {
        if (_mult == 0) {
            return;
        }
        _left.fillIn(result, start, unique);
        if (unique) {
            start = start + _left._uniqueSize;
            result[start++] = _time;
        } else {
            start = start + _left._size;
            for (int i = 0; i < _mult; i++) {
                result[start++] = _time;
            }
        }
        _right.fillIn(result, start, unique);
    }

    /**
     * Computes the earliest time in the set if its earliest n times are each delayed by the given amounts.
     * Requires O(min(size,that.size)).
     *
     * @param that the set of times representing the delays that will be applied to the earliest n points in time,
     *             with n being the size of this given set. They will be applied in order (the smallest delay will be
     *             applied to the highest value etc.).
     * @return the point in time from the earliest n times that is the latest after applying the delay
     */
    public double computeEarliestTime(TimeSet that) {
        return computeEarliestTime(that.asArray());
    }

    /**
     * Computes the earliest time in the set if its earliest n times are each delayed by the given amounts.
     * Requires O(min(size,times.length)).
     *
     * @param delays the values by which the earliest n times are delayed, with n being the length of the array
     * @return the point in time from the earliest n times that is the latest after applying the delay
     */
    public double computeEarliestTime(double[] delays) {
        if (delays.length > _size) {
            // The other set contains more elements than I do.
            // I cannot match it in number, no matter how long 
            // we wait.
            return Double.POSITIVE_INFINITY;
        }
        return computeEarliestTime(delays, delays.length - 1);
    }

    // Check part of the necessary comparisons.
    private double computeEarliestTime(double[] delays, int offset) {
        double earliest = Double.NEGATIVE_INFINITY;
        if (_mult > 0) {
            earliest = _left.computeEarliestTime(delays, offset);
            offset -= _left._size;
            if (offset >= 0) {
                // Regardless of the multiplier, we only need to check against
                // the last entry in the array, because the array is ordered.
                earliest = Math.max(earliest, _time + delays[offset]);
                offset -= _mult;
                if (offset >= 0) {
                    earliest = Math.max(earliest, _right.computeEarliestTime(delays, offset));
                }
            }
        }
        return earliest;
    }

    @Override
    public String toString() {
        StringBuffer buffer = new StringBuffer();
        buffer.append("TimeSet(");
        toString(buffer);
        buffer.append(')');
        return buffer.toString();
    }

    private void toString(StringBuffer buffer) {
        if (_mult == 0) {
            return;
        } else {
            _left.toString(buffer);
            for (int i = 0; i < _mult; i++) {
                buffer.append(' ');
                buffer.append(_time);
            }
            _right.toString(buffer);
        }
    }
}
