001// License: GPL. For details, see LICENSE file.
002package org.openstreetmap.josm.gui.mappaint;
003
004import java.util.ArrayList;
005import java.util.List;
006import java.util.Objects;
007
008import org.openstreetmap.josm.gui.mappaint.styleelement.StyleElement;
009import org.openstreetmap.josm.tools.Pair;
010
011/**
012 * Splits the range of possible scale values (0 < scale < +Infinity) into
013 * multiple subranges, for each scale range it keeps a data object of a certain
014 * type T (can be null).
015 *
016 * Used for caching style information for different zoom levels.
017 *
018 * Immutable class, equals & hashCode is required (the same for
019 * {@link StyleElementList}, {@link StyleElement} and its subclasses).
020 *
021 * @param <T> the type of the data objects
022 */
023public class DividedScale<T> {
024
025    /**
026     * This exception type is for debugging #8997 and can later be replaced by AssertionError
027     */
028    public static class RangeViolatedError extends RuntimeException {
029        /**
030         * Constructs a new {@code RangeViolatedError}
031         * @param message error message
032         */
033        public RangeViolatedError(String message) {
034            super(message);
035        }
036    }
037
038    /* list of boundaries for the scale ranges */
039    private final List<Range> ranges;
040    /* data objects for each scale range */
041    private final List<T> data;
042
043    protected DividedScale() {
044        ranges = new ArrayList<>();
045        ranges.add(Range.ZERO_TO_INFINITY);
046        data = new ArrayList<>();
047        data.add(null);
048    }
049
050    protected DividedScale(DividedScale<T> s) {
051        ranges = new ArrayList<>(s.ranges);
052        data = new ArrayList<>(s.data);
053    }
054
055    /**
056     * Looks up the data object for a certain scale value.
057     *
058     * @param scale scale
059     * @return the data object at the given scale, can be null
060     */
061    public T get(double scale) {
062        if (scale <= 0)
063            throw new IllegalArgumentException("scale must be <= 0 but is "+scale);
064        for (int i = 0; i < data.size(); ++i) {
065            Range range = ranges.get(i);
066            if (range.contains(scale)) {
067                return data.get(i);
068            }
069        }
070        throw new AssertionError();
071    }
072
073    /**
074     * Looks up the data object for a certain scale value and additionally returns
075     * the scale range where the object is valid.
076     *
077     * @param scale scale
078     * @return pair containing data object and range
079     */
080    public Pair<T, Range> getWithRange(double scale) {
081        if (scale <= 0)
082            throw new IllegalArgumentException("scale must be <= 0 but is "+scale);
083        for (int i = 0; i < data.size(); ++i) {
084            Range range = ranges.get(i);
085            if (range.contains(scale)) {
086                return new Pair<>(data.get(i), range);
087            }
088        }
089        throw new AssertionError();
090    }
091
092    /**
093     * Add data object which is valid for the given range.
094     *
095     * This is only possible, if there is no data for the given range yet.
096     *
097     * @param o data object
098     * @param r the valid range
099     * @return a new, updated, <code>DividedScale</code> object
100     */
101    public DividedScale<T> put(T o, Range r) {
102        DividedScale<T> s = new DividedScale<>(this);
103        s.putImpl(o, r.getLower(), r.getUpper());
104        s.consistencyTest();
105        return s;
106    }
107
108    /**
109     * Implementation of the <code>put</code> operation.
110     *
111     * ASCII-art explanation:
112     *
113     *    data[i-1]      data[i]      data[i+1
114     * |--------------|------------|--------------|
115     * (--range[i-1]--]
116     *                (--range[i]--]
117     *                             (--range[i+1]--]
118     *                       (--------]
119     *                     lower     upper
120     * @param o data object
121     * @param lower lower bound
122     * @param upper upper bound
123     */
124    private void putImpl(T o, double lower, double upper) {
125        int i = 0;
126        while (ranges.get(i).getUpper() <= lower) {
127            ++i;
128        }
129        Range split = ranges.get(i);
130        if (split.getUpper() < upper) {
131            throw new RangeViolatedError("the new range must be within a single subrange");
132        } else if (data.get(i) != null) {
133            throw new RangeViolatedError("the new range must be within a subrange that has no data");
134        } else if (split.getLower() == lower && split.getUpper() == upper) {
135            data.set(i, o);
136        } else if (split.getLower() == lower) {
137            ranges.set(i, new Range(split.getLower(), upper));
138            ranges.add(i + 1, new Range(upper, split.getUpper()));
139            data.add(i, o);
140        } else if (split.getUpper() == upper) {
141            ranges.set(i, new Range(split.getLower(), lower));
142            ranges.add(i + 1, new Range(lower, split.getUpper()));
143            data.add(i + 1, o);
144        } else {
145            ranges.set(i, new Range(split.getLower(), lower));
146            ranges.add(i + 1, new Range(lower, upper));
147            ranges.add(i + 2, new Range(upper, split.getUpper()));
148            data.add(i + 1, o);
149            data.add(i + 2, null);
150        }
151    }
152
153    /**
154     * Runs a consistency test.
155     * @throws AssertionError When an invariant is broken.
156     */
157    public void consistencyTest() {
158        if (ranges.isEmpty()) throw new AssertionError(ranges);
159        if (data.isEmpty()) throw new AssertionError(data);
160        if (ranges.size() != data.size()) throw new AssertionError();
161        if (ranges.get(0).getLower() != 0) throw new AssertionError();
162        if (ranges.get(ranges.size() - 1).getUpper() != Double.POSITIVE_INFINITY) throw new AssertionError();
163        for (int i = 0; i < data.size() - 1; ++i) {
164            if (ranges.get(i).getUpper() != ranges.get(i + 1).getLower()) throw new AssertionError();
165        }
166    }
167
168    @Override
169    public boolean equals(Object obj) {
170        if (this == obj) return true;
171        if (obj == null || getClass() != obj.getClass()) return false;
172        DividedScale<?> that = (DividedScale<?>) obj;
173        return Objects.equals(ranges, that.ranges) &&
174                Objects.equals(data, that.data);
175    }
176
177    @Override
178    public int hashCode() {
179        return 31 * ranges.hashCode() + data.hashCode();
180    }
181
182    @Override
183    public String toString() {
184        return "DS{" + ranges + ' ' + data + '}';
185    }
186}