001// License: GPL. For details, see LICENSE file.
002package org.openstreetmap.josm.tools;
003
004import java.util.Collection;
005
006import org.openstreetmap.josm.data.coor.ILatLon;
007import org.openstreetmap.josm.data.coor.LatLon;
008import org.openstreetmap.josm.data.osm.BBox;
009
010/**
011 * Fast index to look up properties of the earth surface.
012 * <p>
013 * It is expected that there is a relatively slow method to look up the property
014 * for a certain coordinate and that there are larger areas with a uniform
015 * property.
016 * <p>
017 * This index tries to find rectangles with uniform property and caches them.
018 * Rectangles are subdivided, if there are different properties within.
019 * (Up to a maximum level, when the slow method is used again.)
020 *
021 * @param <T> the property (like land/water or nation)
022 */
023public class GeoPropertyIndex<T> {
024
025    private final int maxLevel;
026    private final GeoProperty<T> geoProp;
027    private final GPLevel<T> root;
028    private GPLevel<T> lastLevelUsed;
029
030    private static final boolean DEBUG = false;
031
032    /**
033     * Create new GeoPropertyIndex.
034     * @param geoProp the input property that should be made faster by this index
035     * @param maxLevel max level
036     */
037    public GeoPropertyIndex(GeoProperty<T> geoProp, int maxLevel) {
038        this.geoProp = geoProp;
039        this.maxLevel = maxLevel;
040        this.root = new GPLevel<>(0, new BBox(-180, -90, 180, 90), null, this);
041        this.lastLevelUsed = root;
042    }
043
044    /**
045     * Look up the property for a certain point.
046     * This gives the same result as {@link GeoProperty#get(LatLon)}, but
047     * should be faster.
048     * @param ll the point coordinates
049     * @return property value at that point
050     */
051    public T get(LatLon ll) {
052        return lastLevelUsed.get(ll);
053    }
054
055    /**
056     * Returns the geo property.
057     * @return the geo property
058     * @since 14484
059     */
060    public final GeoProperty<T> getGeoProperty() {
061        return geoProp;
062    }
063
064    protected static class GPLevel<T> {
065        private final T val;
066        private final int level;
067        private final BBox bbox;
068        private final GPLevel<T> parent;
069        private final GeoPropertyIndex<T> owner;
070
071        // child order by index is sw, nw, se, ne
072        private GPLevel<T>[] children;
073
074        public GPLevel(int level, BBox bbox, GPLevel<T> parent, GeoPropertyIndex<T> owner) {
075            this.level = level;
076            this.bbox = bbox;
077            this.parent = parent;
078            this.owner = owner;
079            this.val = owner.geoProp.get(bbox);
080        }
081
082        public T get(LatLon ll) {
083            if (isInside(ll))
084                return getBounded(ll);
085            if (DEBUG) Logging.trace("up[{0}]", level);
086            return parent != null ? parent.get(ll) : null;
087        }
088
089        private T getBounded(LatLon ll) {
090            if (DEBUG) Logging.trace("GPLevel[{0}]{1}", level, bbox);
091            if (!isInside(ll)) {
092                throw new AssertionError("Point "+ll+" should be inside "+bbox);
093            }
094            if (val != null) {
095                if (DEBUG) Logging.trace("GPLevel[{0}]{1} hit! {2}", level, bbox, val);
096                owner.lastLevelUsed = this;
097                return val;
098            }
099            if (level >= owner.maxLevel) {
100                if (DEBUG) Logging.trace("GPLevel[{0}]{1} max level reached !", level, bbox);
101                return owner.geoProp.get(ll);
102            }
103
104            GPLevel<T>[] currentChildren = this.getChildren();
105
106            LatLon center = bbox.getCenter();
107            for (int idx = 0; idx < 4; idx++) {
108                BBox testBBox = null;
109                if (currentChildren[idx] != null)
110                    testBBox = currentChildren[idx].bbox;
111
112                if (testBBox == null) {
113                    testBBox = generateTestBBox(idx, center.lon(), center.lat());
114                }
115                if (isInside(testBBox, ll)) {
116                    generateChild(currentChildren, testBBox, idx);
117                    return currentChildren[idx].getBounded(ll);
118                }
119            }
120            throw new AssertionError("Point "+ll+" should be inside one of the children of "+bbox);
121        }
122
123        /**
124         * Generate the bbox for the specified index in the {@link #getChildren()} array
125         * @param idx The index in the {@link #getChildren()} array
126         * @param lon2 The longitude of the center of the previous level
127         * @param lat2 The latitude of the center of the previous level
128         * @return The test bbox for the specified index in the {@link #getChildren()} array
129         */
130        private BBox generateTestBBox(int idx, double lon2, double lat2) {
131            double lon1;
132            double lat1;
133            switch (idx) {
134                case 0:
135                    lon1 = bbox.getTopLeftLon();
136                    lat1 = bbox.getBottomRightLat();
137                    break;
138                case 1:
139                    lon1 = bbox.getTopLeftLon();
140                    lat1 = bbox.getTopLeftLat();
141                    break;
142                case 2:
143                    lon1 = bbox.getBottomRightLon();
144                    lat1 = bbox.getBottomRightLat();
145                    break;
146                case 3:
147                    lon1 = bbox.getBottomRightLon();
148                    lat1 = bbox.getTopLeftLat();
149                    break;
150                default:
151                    throw new AssertionError();
152            }
153            return new BBox(lon1, lat1, lon2, lat2);
154        }
155
156        /**
157         * Safely generate the child in a multi-threaded environment
158         * @param currentChildren The children array to check
159         * @param testBBox The current bbox (will be used to create the new {@link GPLevel})
160         * @param idx The index in the child array
161         */
162        private synchronized void generateChild(GPLevel<T>[] currentChildren, BBox testBBox, int idx) {
163            if (currentChildren[idx] == null) {
164                if (DEBUG) Logging.trace("GPLevel[{0}]{1} - new with idx {2}", level, bbox, idx);
165                currentChildren[idx] = new GPLevel<>(level + 1, testBBox, this, owner);
166            }
167        }
168
169        /**
170         * Get the children array safely in a multi-threaded environment.
171         * If this ends up being a performance issue, look up the "immutable" double-checked locking idiom.
172         * Just be certain you have a good test when checking the performance differences.
173         * See #23309/#23036. The issue there is that {@link Territories#getRegionalTaginfoUrls(LatLon)}
174         * uses a {@link Collection#parallelStream}.
175         * @return The children array (sw, nw, se, ne)
176         */
177        private synchronized GPLevel<T>[] getChildren() {
178            GPLevel<T>[] currentChildren = this.children;
179            if (currentChildren == null) {
180                @SuppressWarnings("unchecked")
181                GPLevel<T>[] tmp = new GPLevel[4];
182                currentChildren = tmp;
183                this.children = currentChildren;
184            }
185            return currentChildren;
186        }
187
188        /**
189         * Checks, if a point is inside this tile.
190         * Makes sure, that neighboring tiles do not overlap, i.e. a point exactly
191         * on the border of two tiles must be inside exactly one of the tiles.
192         * @param ll the coordinates of the point
193         * @return true, if it is inside of the box
194         */
195        boolean isInside(ILatLon ll) {
196            return isInside(bbox, ll);
197        }
198
199        /**
200         * Checks, if a point is inside this tile.
201         * Makes sure, that neighboring tiles do not overlap, i.e. a point exactly
202         * on the border of two tiles must be inside exactly one of the tiles.
203         * @param bbox the tile
204         * @param ll the coordinates of the point
205         * @return true, if it is inside of the box
206         */
207        boolean isInside(BBox bbox, ILatLon ll) {
208            return bbox.getTopLeftLon() <= ll.lon() &&
209                    (ll.lon() < bbox.getBottomRightLon() || (ll.lon() == 180.0 && bbox.getBottomRightLon() == 180.0)) &&
210                    bbox.getBottomRightLat() <= ll.lat() &&
211                    (ll.lat() < bbox.getTopLeftLat() || (ll.lat() == 90.0 && bbox.getTopLeftLat() == 90.0));
212        }
213
214        @Override
215        public String toString() {
216            return "GPLevel [val=" + val + ", level=" + level + ", bbox=" + bbox + ']';
217        }
218    }
219
220    @Override
221    public String toString() {
222        return "GeoPropertyIndex [maxLevel=" + maxLevel + ", geoProp=" + geoProp + ", root=" + root + ", lastLevelUsed="
223                + lastLevelUsed + ']';
224    }
225}