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