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