001package net.kreatious.pianoleopard.intervalset;
002
003import java.util.Iterator;
004import java.util.Optional;
005import java.util.function.Predicate;
006
007/**
008 * An ordered tree data structure for holding intervals. The user can
009 * efficiently find all intervals that overlap with a given interval or point.
010 * <p>
011 * Interval sets are optimized for being queried far more often than they are
012 * modified.
013 * <p>
014 * This set does not support null keys or values, but does support duplicate
015 * intervals.
016 *
017 * @author Jay-R Studer
018 * @param <V>
019 *            the type of mapped values
020 */
021public class IntervalSet<V> implements Iterable<V> {
022    private Optional<Entry<V>> root = Optional.empty();
023    private int size;
024    private int modifications;
025
026    /**
027     * Removes all values from this set.
028     */
029    public void clear() {
030        root = Optional.empty();
031        size = 0;
032        modifications++;
033    }
034
035    /**
036     * Returns the size of this set.
037     *
038     * @return the number of values in this collection
039     */
040    public int size() {
041        return size;
042    }
043
044    /**
045     * Associates the specified interval with the specified value in this set.
046     * If this set previously contained a mapping for the interval, the old
047     * value is replaced. If the specified interval is invalid, nothing is
048     * inserted.
049     *
050     * @param low
051     *            the low end of the range the specified value to associate
052     * @param high
053     *            the high end of the range the specified value to associate
054     * @param value
055     *            value to be associated with the specified key
056     * @return the previous value associated with the interval, or empty if
057     *         there was no mapping for the interval.
058     * @throws NullPointerException
059     *             if the specified key or value is null
060     */
061    public Optional<V> put(long low, long high, V value) {
062        if (low > high) {
063            return Optional.empty();
064        }
065
066        final Interval key = new Interval(low, high);
067        if (!root.isPresent()) {
068            root = Optional.of(new Entry<>(key, value, Optional.empty()));
069            size = 1;
070            modifications++;
071            return Optional.empty();
072        }
073
074        final Optional<Entry<V>> parent = root.get().binarySearchInexact(key);
075        if (parent.filter(p -> p.getKey().compareTo(key) == 0).isPresent()) {
076            if (parent.get().addValue(value)) {
077                size++;
078                modifications++;
079                return Optional.empty();
080            }
081            return Optional.of(value);
082        }
083
084        final Entry<V> entry = new Entry<>(key, value, parent);
085        parent.get().insertNode(entry);
086        root = entry.rebalance(root);
087        size++;
088        modifications++;
089        return Optional.empty();
090    }
091
092    /**
093     * Removes the first value for the specified interval from this set that
094     * matches the given criteria.
095     *
096     * @param low
097     *            the low end of the range the specified value to associate
098     * @param high
099     *            the high end of the range the specified value to associate
100     * @param criteria
101     *            the value to delete
102     * @return the removed value, or empty if no value was removed
103     * @throws IllegalArgumentException
104     *             if {@code low} is greater than {@code high}
105     * @throws NullPointerException
106     *             if the specified key is null
107     */
108    public Optional<V> removeFirst(long low, long high, Predicate<? super V> criteria) {
109        final Optional<Entry<V>> entryToRemove = root
110                .flatMap(entry -> entry.binarySearchExact(new Interval(low, high)));
111        if (!entryToRemove.isPresent()) {
112            return Optional.empty();
113        }
114
115        final Entry<V> entry = entryToRemove.get();
116        final Optional<V> result = entry.getValues().stream().filter(criteria).findAny();
117        if (!result.isPresent()) {
118            return Optional.empty();
119        }
120
121        entry.getValues().remove(result.get());
122        if (entry.getValues().isEmpty()) {
123            root = entry.remove(root);
124        }
125        size--;
126        modifications++;
127        return result;
128    }
129
130    /**
131     * Returns an iterable read only view of the values in this set that
132     * overlaps the specified interval. If {@code low} and {@code high} are
133     * equal, the returned view contains the intervals containing a single
134     * point.
135     *
136     * @param low
137     *            low portion of the interval to retrieve
138     * @param high
139     *            high portion of the interval to retrieve
140     * @throws IllegalArgumentException
141     *             if {@code low} is greater than {@code high}
142     * @return a read only view of the portion of this set overlapping the
143     *         specified interval.
144     */
145    public Iterable<V> subSet(long low, long high) {
146        return new RangeIterable<>(this, low, high);
147    }
148
149    @Override
150    public Iterator<V> iterator() {
151        return new InOrderIterator<>(this);
152    }
153
154    int getModifications() {
155        return modifications;
156    }
157
158    Optional<Entry<V>> getRoot() {
159        return root;
160    }
161}