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<Double> bd;
040    /* data objects for each scale range */
041    private final List<T> data;
042
043    protected DividedScale() {
044        bd = new ArrayList<>();
045        bd.add(0.0);
046        bd.add(Double.POSITIVE_INFINITY);
047        data = new ArrayList<>();
048        data.add(null);
049    }
050
051    protected DividedScale(DividedScale<T> s) {
052        bd = new ArrayList<>(s.bd);
053        data = new ArrayList<>(s.data);
054    }
055
056    /**
057     * Looks up the data object for a certain scale value.
058     *
059     * @param scale scale
060     * @return the data object at the given scale, can be null
061     */
062    public T get(double scale) {
063        if (scale <= 0)
064            throw new IllegalArgumentException("scale must be <= 0 but is "+scale);
065        for (int i = 0; i < data.size(); ++i) {
066            if (bd.get(i) < scale && scale <= bd.get(i+1)) {
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            if (bd.get(i) < scale && scale <= bd.get(i+1)) {
085                return new Pair<>(data.get(i), new Range(bd.get(i), bd.get(i+1)));
086            }
087        }
088        throw new AssertionError();
089    }
090
091    /**
092     * Add data object which is valid for the given range.
093     *
094     * This is only possible, if there is no data for the given range yet.
095     *
096     * @param o data object
097     * @param r the valid range
098     * @return a new, updated, <code>DividedScale</code> object
099     */
100    public DividedScale<T> put(T o, Range r) {
101        DividedScale<T> s = new DividedScale<>(this);
102        s.putImpl(o, r.getLower(), r.getUpper());
103        s.consistencyTest();
104        return s;
105    }
106
107    /**
108     * Implementation of the <code>put</code> operation.
109     *
110     * ASCII-art explanation:
111     *
112     *              data[i]
113     *  --|-------|---------|--
114     * bd[i-1]  bd[i]    bd[i+1]
115     *
116     *         (--------]
117     *       lower     upper
118     * @param o data object
119     * @param lower lower bound
120     * @param upper upper bound
121     */
122    private void putImpl(T o, double lower, double upper) {
123        int i = 0;
124        while (bd.get(i) < lower) {
125            ++i;
126        }
127        if (bd.get(i) == lower) {
128            if (upper > bd.get(i+1))
129                throw new RangeViolatedError("the new range must be within a single subrange (1)");
130            if (data.get(i) != null)
131                throw new RangeViolatedError("the new range must be within a subrange that has no data");
132
133            if (bd.get(i+1) == upper) {
134                //  --|-------|--------|--
135                //   i-1      i       i+1
136                //            (--------]
137                data.set(i, o);
138            } else {
139                //  --|-------|--------|--
140                //   i-1      i       i+1
141                //            (-----]
142                bd.add(i+1, upper);
143                data.add(i, o);
144            }
145        } else {
146            if (bd.get(i) < upper)
147                throw new RangeViolatedError("the new range must be within a single subrange (2)");
148            if (data.get(i-1) != null)
149                throw new AssertionError();
150
151            //  --|-------|--------|--
152            //   i-1      i       i+1
153            //       (--]   or
154            //       (----]
155            bd.add(i, lower);
156            data.add(i, o);
157
158            //  --|--|----|--------|--
159            //   i-1 i   i+1      i+2
160            //       (--]
161            if (bd.get(i+1) > upper) {
162                bd.add(i+1, upper);
163                data.add(i+1, null);
164            }
165        }
166    }
167
168    /**
169     * Runs a consistency test.
170     * @throws AssertionError When an invariant is broken.
171     */
172    public void consistencyTest() {
173        if (bd.size() < 2) throw new AssertionError(bd);
174        if (data.isEmpty()) throw new AssertionError(data);
175        if (bd.size() != data.size() + 1) throw new AssertionError();
176        if (bd.get(0) != 0) throw new AssertionError();
177        if (bd.get(bd.size() - 1) != Double.POSITIVE_INFINITY) throw new AssertionError();
178        for (int i = 0; i < data.size() - 1; ++i) {
179            if (bd.get(i) >= bd.get(i + 1)) throw new AssertionError();
180        }
181    }
182
183    @Override
184    public boolean equals(Object obj) {
185        if (this == obj) return true;
186        if (obj == null || getClass() != obj.getClass()) return false;
187        DividedScale<?> that = (DividedScale<?>) obj;
188        return Objects.equals(bd, that.bd) &&
189                Objects.equals(data, that.data);
190    }
191
192    @Override
193    public int hashCode() {
194        return Objects.hash(bd, data);
195    }
196
197    @Override
198    public String toString() {
199        return "DS{" + bd + ' ' + data + '}';
200    }
201}