001// License: GPL. For details, see LICENSE file.
002package org.openstreetmap.josm.data.osm;
003
004import static org.openstreetmap.josm.tools.I18n.tr;
005
006import java.util.ArrayList;
007import java.util.Arrays;
008import java.util.HashSet;
009import java.util.List;
010import java.util.Map;
011import java.util.Set;
012import java.util.stream.Collectors;
013import java.util.stream.IntStream;
014
015import org.openstreetmap.josm.data.coor.LatLon;
016import org.openstreetmap.josm.data.osm.visitor.OsmPrimitiveVisitor;
017import org.openstreetmap.josm.data.osm.visitor.PrimitiveVisitor;
018import org.openstreetmap.josm.spi.preferences.Config;
019import org.openstreetmap.josm.tools.CopyList;
020import org.openstreetmap.josm.tools.Geometry;
021import org.openstreetmap.josm.tools.Pair;
022import org.openstreetmap.josm.tools.Utils;
023
024/**
025 * One full way, consisting of a list of way {@link Node nodes}.
026 *
027 * @author imi
028 * @since 64
029 */
030public final class Way extends OsmPrimitive implements IWay<Node> {
031
032    static final UniqueIdGenerator idGenerator = new UniqueIdGenerator();
033    private static final Node[] EMPTY_NODES = new Node[0];
034
035    /**
036     * All way nodes in this way
037     */
038    private Node[] nodes = EMPTY_NODES;
039    private BBox bbox;
040
041    @Override
042    public List<Node> getNodes() {
043        return new CopyList<>(nodes);
044    }
045
046    @Override
047    public void setNodes(List<Node> nodes) {
048        checkDatasetNotReadOnly();
049        boolean locked = writeLock();
050        try {
051            for (Node node:this.nodes) {
052                node.removeReferrer(this);
053                node.clearCachedStyle();
054            }
055
056            if (Utils.isEmpty(nodes)) {
057                this.nodes = EMPTY_NODES;
058            } else {
059                this.nodes = nodes.toArray(EMPTY_NODES);
060            }
061            for (Node node: this.nodes) {
062                node.addReferrer(this);
063                node.clearCachedStyle();
064            }
065
066            clearCachedStyle();
067            fireNodesChanged();
068        } finally {
069            writeUnlock(locked);
070        }
071    }
072
073    /**
074     * Prevent directly following identical nodes in ways.
075     * @param nodes list of nodes
076     * @return {@code nodes} with consecutive identical nodes removed
077     */
078    private static List<Node> removeDouble(List<Node> nodes) {
079        Node last = null;
080        int count = nodes.size();
081        for (int i = 0; i < count && count > 2;) {
082            Node n = nodes.get(i);
083            if (last == n) {
084                nodes.remove(i);
085                --count;
086            } else {
087                last = n;
088                ++i;
089            }
090        }
091        return nodes;
092    }
093
094    @Override
095    public int getNodesCount() {
096        return nodes.length;
097    }
098
099    @Override
100    public Node getNode(int index) {
101        return nodes[index];
102    }
103
104    @Override
105    public long getNodeId(int idx) {
106        return nodes[idx].getUniqueId();
107    }
108
109    @Override
110    public List<Long> getNodeIds() {
111        return Arrays.stream(nodes).map(Node::getId).collect(Collectors.toList());
112    }
113
114    /**
115     * Replies true if this way contains the node <code>node</code>, false
116     * otherwise. Replies false if  <code>node</code> is null.
117     *
118     * @param node the node. May be null.
119     * @return true if this way contains the node <code>node</code>, false
120     * otherwise
121     * @since 1911
122     */
123    public boolean containsNode(Node node) {
124        return node != null && Arrays.asList(nodes).contains(node);
125    }
126
127    /**
128     * Return nodes adjacent to <code>node</code>
129     *
130     * @param node the node. May be null.
131     * @return Set of nodes adjacent to <code>node</code>
132     * @since 4671
133     */
134    public Set<Node> getNeighbours(Node node) {
135        Set<Node> neigh = new HashSet<>();
136
137        if (node == null) return neigh;
138
139        for (int i = 0; i < nodes.length; i++) {
140            if (nodes[i].equals(node)) {
141                if (i > 0)
142                    neigh.add(nodes[i-1]);
143                if (i < nodes.length-1)
144                    neigh.add(nodes[i+1]);
145            }
146        }
147        return neigh;
148    }
149
150    /**
151     * Replies the ordered {@link List} of chunks of this way. Each chunk is replied as a {@link Pair} of {@link Node nodes}.
152     * @param sort If true, the nodes of each pair are sorted as defined by {@link Pair#sort}.
153     *             If false, Pair.a and Pair.b are in the way order
154     *             (i.e for a given Pair(n), Pair(n-1).b == Pair(n).a, Pair(n).b == Pair(n+1).a, etc.)
155     * @return The ordered list of chunks of this way.
156     * @since 3348
157     */
158    public List<Pair<Node, Node>> getNodePairs(boolean sort) {
159        List<Pair<Node, Node>> chunkSet = new ArrayList<>();
160        if (isIncomplete()) return chunkSet;
161        Node lastN = null;
162        for (Node n : nodes) {
163            if (lastN == null) {
164                lastN = n;
165                continue;
166            }
167            Pair<Node, Node> np = new Pair<>(lastN, n);
168            if (sort) {
169                Pair.sort(np);
170            }
171            chunkSet.add(np);
172            lastN = n;
173        }
174        return chunkSet;
175    }
176
177    @Override public void accept(OsmPrimitiveVisitor visitor) {
178        visitor.visit(this);
179    }
180
181    @Override public void accept(PrimitiveVisitor visitor) {
182        visitor.visit(this);
183    }
184
185    Way(long id, boolean allowNegative) {
186        super(id, allowNegative);
187    }
188
189    /**
190     * Constructs a new {@code Way} with id 0.
191     * @since 86
192     */
193    public Way() {
194        super(0, false);
195    }
196
197    /**
198     * Constructs a new {@code Way} from an existing {@code Way}.
199     * This adds links from all way nodes to the clone. See #19885 for possible memory leaks.
200     * @param original The original {@code Way} to be identically cloned. Must not be null
201     * @param clearMetadata If {@code true}, clears the OSM id and other metadata as defined by {@link #clearOsmMetadata}.
202     * If {@code false}, does nothing
203     * @param copyNodes whether to copy nodes too
204     * @since 16212
205     */
206    public Way(Way original, boolean clearMetadata, boolean copyNodes) {
207        super(original.getUniqueId(), true);
208        cloneFrom(original, copyNodes);
209        if (clearMetadata) {
210            clearOsmMetadata();
211        }
212    }
213
214    /**
215     * Constructs a new {@code Way} from an existing {@code Way}.
216     * This adds links from all way nodes to the clone. See #19885 for possible memory leaks.
217     * @param original The original {@code Way} to be identically cloned. Must not be null
218     * @param clearMetadata If {@code true}, clears the OSM id and other metadata as defined by {@link #clearOsmMetadata}.
219     * If {@code false}, does nothing
220     * @since 2410
221     */
222    public Way(Way original, boolean clearMetadata) {
223        this(original, clearMetadata, true);
224    }
225
226    /**
227     * Constructs a new {@code Way} from an existing {@code Way} (including its id).
228     * This adds links from all way nodes to the clone. See #19885 for possible memory leaks.
229     * @param original The original {@code Way} to be identically cloned. Must not be null
230     * @since 86
231     */
232    public Way(Way original) {
233        this(original, false);
234    }
235
236    /**
237     * Constructs a new {@code Way} for the given id. If the id &gt; 0, the way is marked
238     * as incomplete. If id == 0 then way is marked as new
239     *
240     * @param id the id. &gt;= 0 required
241     * @throws IllegalArgumentException if id &lt; 0
242     * @since 343
243     */
244    public Way(long id) {
245        super(id, false);
246    }
247
248    /**
249     * Constructs a new {@code Way} with given id and version.
250     * @param id the id. &gt;= 0 required
251     * @param version the version
252     * @throws IllegalArgumentException if id &lt; 0
253     * @since 2620
254     */
255    public Way(long id, int version) {
256        super(id, version, false);
257    }
258
259    @Override
260    public void load(PrimitiveData data) {
261        if (!(data instanceof WayData))
262            throw new IllegalArgumentException("Not a way data: " + data);
263        boolean locked = writeLock();
264        try {
265            super.load(data);
266
267            List<Long> nodeIds = ((WayData) data).getNodeIds();
268
269            if (!nodeIds.isEmpty() && getDataSet() == null) {
270                throw new AssertionError("Data consistency problem - way without dataset detected");
271            }
272
273            List<Node> newNodes = new ArrayList<>(nodeIds.size());
274            for (Long nodeId : nodeIds) {
275                Node node = (Node) getDataSet().getPrimitiveById(nodeId, OsmPrimitiveType.NODE);
276                if (node != null) {
277                    newNodes.add(node);
278                } else {
279                    throw new AssertionError("Data consistency problem - way with missing node detected");
280                }
281            }
282            setNodes(newNodes);
283        } finally {
284            writeUnlock(locked);
285        }
286    }
287
288    @Override
289    public WayData save() {
290        WayData data = new WayData();
291        saveCommonAttributes(data);
292        for (Node node:nodes) {
293            data.getNodeIds().add(node.getUniqueId());
294        }
295        return data;
296    }
297
298    @Override
299    public void cloneFrom(OsmPrimitive osm, boolean copyNodes) {
300        if (!(osm instanceof Way))
301            throw new IllegalArgumentException("Not a way: " + osm);
302        boolean locked = writeLock();
303        try {
304            super.cloneFrom(osm, copyNodes);
305            if (copyNodes) {
306                setNodes(((Way) osm).getNodes());
307            }
308        } finally {
309            writeUnlock(locked);
310        }
311    }
312
313    @Override
314    public String toString() {
315        String nodesDesc = isIncomplete() ? "(incomplete)" : ("nodes=" + Arrays.toString(nodes));
316        return "{Way id=" + getUniqueId() + " version=" + getVersion()+ ' ' + getFlagsAsString() + ' ' + nodesDesc + '}';
317    }
318
319    @Override
320    public boolean hasEqualSemanticAttributes(OsmPrimitive other, boolean testInterestingTagsOnly) {
321        if (!(other instanceof Way))
322            return false;
323        Way w = (Way) other;
324        if (getNodesCount() != w.getNodesCount()) return false;
325        if (!super.hasEqualSemanticAttributes(other, testInterestingTagsOnly))
326            return false;
327        return IntStream.range(0, getNodesCount())
328                .allMatch(i -> getNode(i).hasEqualSemanticAttributes(w.getNode(i)));
329    }
330
331    /**
332     * Removes the given {@link Node} from this way. Ignored, if n is null.
333     * @param n The node to remove. Ignored, if null
334     * @since 1463
335     */
336    public void removeNode(Node n) {
337        checkDatasetNotReadOnly();
338        if (n == null || isIncomplete()) return;
339        boolean locked = writeLock();
340        try {
341            boolean closed = lastNode() == n && firstNode() == n;
342            int i;
343            List<Node> copy = getNodes();
344            while ((i = copy.indexOf(n)) >= 0) {
345                copy.remove(i);
346            }
347            i = copy.size();
348            if (closed && i > 2) {
349                copy.add(copy.get(0));
350            } else if (i >= 2 && i <= 3 && copy.get(0) == copy.get(i-1)) {
351                copy.remove(i-1);
352            }
353            setNodes(removeDouble(copy));
354            n.clearCachedStyle();
355        } finally {
356            writeUnlock(locked);
357        }
358    }
359
360    /**
361     * Removes the given set of {@link Node nodes} from this way. Ignored, if selection is null.
362     * @param selection The selection of nodes to remove. Ignored, if null
363     * @since 5408
364     */
365    public void removeNodes(Set<? extends Node> selection) {
366        checkDatasetNotReadOnly();
367        if (selection == null || isIncomplete()) return;
368        boolean locked = writeLock();
369        try {
370            setNodes(calculateRemoveNodes(selection));
371            for (Node n : selection) {
372                n.clearCachedStyle();
373            }
374        } finally {
375            writeUnlock(locked);
376        }
377    }
378
379    /**
380     * Calculate the remaining nodes after a removal of the given set of {@link Node nodes} from this way.
381     * @param selection The selection of nodes to remove. Ignored, if null
382     * @return result of the removal, can be empty
383     * @since 17102
384     */
385    public List<Node> calculateRemoveNodes(Set<? extends Node> selection) {
386        if (selection == null || isIncomplete())
387            return getNodes();
388        boolean closed = isClosed() && selection.contains(lastNode());
389        List<Node> copy = Arrays.stream(nodes)
390                .filter(n -> !selection.contains(n))
391                .collect(Collectors.toList());
392
393        int i = copy.size();
394        if (closed && i > 2) {
395            copy.add(copy.get(0));
396        } else if (i >= 2 && i <= 3 && copy.get(0) == copy.get(i-1)) {
397            copy.remove(i-1);
398        }
399        return removeDouble(copy);
400    }
401
402    /**
403     * Adds a node to the end of the list of nodes. Ignored, if n is null.
404     *
405     * @param n the node. Ignored, if null
406     * @throws IllegalStateException if this way is marked as incomplete. We can't add a node
407     * to an incomplete way
408     * @since 1313
409     */
410    public void addNode(Node n) {
411        checkDatasetNotReadOnly();
412        if (n == null) return;
413
414        boolean locked = writeLock();
415        try {
416            if (isIncomplete())
417                throw new IllegalStateException(tr("Cannot add node {0} to incomplete way {1}.", n.getId(), getId()));
418            clearCachedStyle();
419            n.addReferrer(this);
420            nodes = Utils.addInArrayCopy(nodes, n);
421            n.clearCachedStyle();
422            fireNodesChanged();
423        } finally {
424            writeUnlock(locked);
425        }
426    }
427
428    /**
429     * Adds a node at position offs.
430     *
431     * @param offs the offset
432     * @param n the node. Ignored, if null.
433     * @throws IllegalStateException if this way is marked as incomplete. We can't add a node
434     * to an incomplete way
435     * @throws IndexOutOfBoundsException if offs is out of bounds
436     * @since 1313
437     */
438    public void addNode(int offs, Node n) {
439        checkDatasetNotReadOnly();
440        if (n == null) return;
441
442        boolean locked = writeLock();
443        try {
444            if (isIncomplete())
445                throw new IllegalStateException(tr("Cannot add node {0} to incomplete way {1}.", n.getId(), getId()));
446
447            clearCachedStyle();
448            n.addReferrer(this);
449            Node[] newNodes = new Node[nodes.length + 1];
450            System.arraycopy(nodes, 0, newNodes, 0, offs);
451            System.arraycopy(nodes, offs, newNodes, offs + 1, nodes.length - offs);
452            newNodes[offs] = n;
453            nodes = newNodes;
454            n.clearCachedStyle();
455            fireNodesChanged();
456        } finally {
457            writeUnlock(locked);
458        }
459    }
460
461    @Override
462    public void setDeleted(boolean deleted) {
463        boolean locked = writeLock();
464        try {
465            for (Node n:nodes) {
466                if (deleted) {
467                    n.removeReferrer(this);
468                } else {
469                    n.addReferrer(this);
470                }
471                n.clearCachedStyle();
472            }
473            fireNodesChanged();
474            super.setDeleted(deleted);
475        } finally {
476            writeUnlock(locked);
477        }
478    }
479
480    @Override
481    public boolean isClosed() {
482        if (isIncomplete()) return false;
483
484        return nodes.length >= 3 && nodes[nodes.length-1] == nodes[0];
485    }
486
487    /**
488     * Determines if this way denotes an area (closed way with at least three distinct nodes).
489     * @return {@code true} if this way is closed and contains at least three distinct nodes
490     * @see #isClosed
491     * @since 5490
492     */
493    public boolean isArea() {
494        if (this.nodes.length >= 4 && isClosed()) {
495            Node distinctNode = null;
496            for (int i = 1; i < nodes.length-1; i++) {
497                if (distinctNode == null && nodes[i] != nodes[0]) {
498                    distinctNode = nodes[i];
499                } else if (distinctNode != null && nodes[i] != nodes[0] && nodes[i] != distinctNode) {
500                    return true;
501                }
502            }
503        }
504        return false;
505    }
506
507    @Override
508    public Node lastNode() {
509        if (isIncomplete() || nodes.length == 0) return null;
510        return nodes[nodes.length-1];
511    }
512
513    @Override
514    public Node firstNode() {
515        if (isIncomplete() || nodes.length == 0) return null;
516        return nodes[0];
517    }
518
519    @Override
520    public boolean isFirstLastNode(INode n) {
521        if (isIncomplete() || nodes.length == 0) return false;
522        return n == nodes[0] || n == nodes[nodes.length -1];
523    }
524
525    @Override
526    public boolean isInnerNode(INode n) {
527        if (isIncomplete() || nodes.length <= 2) return false;
528        /* circular ways have only inner nodes, so return true for them! */
529        if (n == nodes[0] && n == nodes[nodes.length-1]) return true;
530        return IntStream.range(1, nodes.length - 1)
531                .anyMatch(i -> nodes[i] == n);
532    }
533
534    @Override
535    public OsmPrimitiveType getType() {
536        return OsmPrimitiveType.WAY;
537    }
538
539    @Override
540    public OsmPrimitiveType getDisplayType() {
541        return isClosed() ? OsmPrimitiveType.CLOSEDWAY : OsmPrimitiveType.WAY;
542    }
543
544    private void checkNodes() {
545        DataSet dataSet = getDataSet();
546        if (dataSet != null) {
547            for (Node n: nodes) {
548                if (n.getDataSet() != dataSet)
549                    throw new DataIntegrityProblemException("Nodes in way must be in the same dataset",
550                            tr("Nodes in way must be in the same dataset"));
551                if (n.isDeleted())
552                    throw new DataIntegrityProblemException("Deleted node referenced: " + toString(),
553                            "<html>" + tr("Deleted node referenced by {0}",
554                                    DefaultNameFormatter.getInstance().formatAsHtmlUnorderedList(this)) + "</html>",
555                            this, n);
556            }
557            if (Config.getPref().getBoolean("debug.checkNullCoor", true)) {
558                for (Node n: nodes) {
559                    if (n.isVisible() && !n.isIncomplete() && !n.isLatLonKnown())
560                        throw new DataIntegrityProblemException("Complete visible node with null coordinates: " + toString(),
561                                "<html>" + tr("Complete node {0} with null coordinates in way {1}",
562                                        DefaultNameFormatter.getInstance().formatAsHtmlUnorderedList(n),
563                                        DefaultNameFormatter.getInstance().formatAsHtmlUnorderedList(this)) + "</html>",
564                                this, n);
565                }
566            }
567        }
568    }
569
570    private void fireNodesChanged() {
571        checkNodes();
572        if (getDataSet() != null) {
573            getDataSet().fireWayNodesChanged(this);
574        }
575    }
576
577    @Override
578    void setDataset(DataSet dataSet) {
579        super.setDataset(dataSet);
580        checkNodes();
581    }
582
583    @Override
584    public BBox getBBox() {
585        if (getDataSet() == null)
586            return new BBox(this);
587        if (bbox == null) {
588            setBBox(new BBox(this));
589        }
590        return bbox;
591    }
592
593    @Override
594    protected void addToBBox(BBox box, Set<PrimitiveId> visited) {
595        box.add(getBBox());
596    }
597
598    private void setBBox(BBox bbox) {
599        this.bbox = bbox == null ? null : bbox.toImmutable();
600    }
601
602    @Override
603    public void updatePosition() {
604        setBBox(new BBox(this));
605        clearCachedStyle();
606    }
607
608    @Override
609    public boolean hasIncompleteNodes() {
610        return Arrays.stream(nodes).anyMatch(Node::isIncomplete);
611    }
612
613    /**
614     * Replies true if all nodes of the way have known lat/lon, false otherwise.
615     * @return true if all nodes of the way have known lat/lon, false otherwise
616     * @since 13033
617     */
618    public boolean hasOnlyLocatableNodes() {
619        return Arrays.stream(nodes).allMatch(Node::isLatLonKnown);
620    }
621
622    @Override
623    public boolean isUsable() {
624        return super.isUsable() && !hasIncompleteNodes();
625    }
626
627    @Override
628    public boolean isDrawable() {
629        return super.isDrawable() && hasOnlyLocatableNodes();
630    }
631
632    /**
633     * Replies the length of the way, in metres, as computed by {@link LatLon#greatCircleDistance}.
634     * @return The length of the way, in metres
635     * @since 4138
636     */
637    public double getLength() {
638        double length = 0;
639        Node lastN = null;
640        for (Node n:nodes) {
641            if (lastN != null) {
642                LatLon lastNcoor = lastN.getCoor();
643                LatLon coor = n.getCoor();
644                if (lastNcoor != null && coor != null) {
645                    length += coor.greatCircleDistance(lastNcoor);
646                }
647            }
648            lastN = n;
649        }
650        return length;
651    }
652
653    /**
654     * Replies the length of the longest segment of the way, in metres, as computed by {@link LatLon#greatCircleDistance}.
655     * @return The length of the segment, in metres
656     * @since 8320
657     */
658    public double getLongestSegmentLength() {
659        double length = 0;
660        Node lastN = null;
661        for (Node n:nodes) {
662            if (lastN != null) {
663                LatLon lastNcoor = lastN.getCoor();
664                LatLon coor = n.getCoor();
665                if (lastNcoor != null && coor != null) {
666                    double l = coor.greatCircleDistance(lastNcoor);
667                    if (l > length) {
668                        length = l;
669                    }
670                }
671            }
672            lastN = n;
673        }
674        return length;
675    }
676
677    /**
678     * Tests if this way is a oneway.
679     * @return {@code 1} if the way is a oneway,
680     *         {@code -1} if the way is a reversed oneway,
681     *         {@code 0} otherwise.
682     * @since 5199
683     */
684    public int isOneway() {
685        String oneway = get("oneway");
686        if (oneway != null) {
687            if ("-1".equals(oneway)) {
688                return -1;
689            } else {
690                Boolean isOneway = OsmUtils.getOsmBoolean(oneway);
691                if (isOneway != null && isOneway) {
692                    return 1;
693                }
694            }
695        }
696        return 0;
697    }
698
699    /**
700     * Replies the first node of this way, respecting or not its oneway state.
701     * @param respectOneway If true and if this way is a reversed oneway, replies the last node. Otherwise, replies the first node.
702     * @return the first node of this way, according to {@code respectOneway} and its oneway state.
703     * @since 5199
704     */
705    public Node firstNode(boolean respectOneway) {
706        return !respectOneway || isOneway() != -1 ? firstNode() : lastNode();
707    }
708
709    /**
710     * Replies the last node of this way, respecting or not its oneway state.
711     * @param respectOneway If true and if this way is a reversed oneway, replies the first node. Otherwise, replies the last node.
712     * @return the last node of this way, according to {@code respectOneway} and its oneway state.
713     * @since 5199
714     */
715    public Node lastNode(boolean respectOneway) {
716        return !respectOneway || isOneway() != -1 ? lastNode() : firstNode();
717    }
718
719    @Override
720    public boolean concernsArea() {
721        return hasAreaTags();
722    }
723
724    @Override
725    public boolean isOutsideDownloadArea() {
726        return Arrays.stream(nodes).anyMatch(Node::isOutsideDownloadArea);
727    }
728
729    @Override
730    protected void keysChangedImpl(Map<String, String> originalKeys) {
731        super.keysChangedImpl(originalKeys);
732        clearCachedNodeStyles();
733    }
734
735    /**
736     * Clears all cached styles for all nodes of this way. This should not be called from outside.
737     * @see Node#clearCachedStyle()
738     */
739    public void clearCachedNodeStyles() {
740        for (final Node n : nodes) {
741            n.clearCachedStyle();
742        }
743    }
744
745    /**
746     * Returns angles of vertices.
747     * @return angles of the way
748     * @since 13670
749     */
750    public synchronized List<Pair<Double, Node>> getAngles() {
751        List<Pair<Double, Node>> angles = new ArrayList<>();
752
753        for (int i = 1; i < nodes.length - 1; i++) {
754            Node n0 = nodes[i - 1];
755            Node n1 = nodes[i];
756            Node n2 = nodes[i + 1];
757
758            double angle = Geometry.getNormalizedAngleInDegrees(Geometry.getCornerAngle(
759                    n0.getEastNorth(), n1.getEastNorth(), n2.getEastNorth()));
760            angles.add(new Pair<>(angle, n1));
761        }
762
763        angles.add(new Pair<>(Geometry.getNormalizedAngleInDegrees(Geometry.getCornerAngle(
764                nodes[nodes.length - 2].getEastNorth(),
765                nodes[0].getEastNorth(),
766                nodes[1].getEastNorth())), nodes[0]));
767
768        return angles;
769    }
770
771    @Override
772    public UniqueIdGenerator getIdGenerator() {
773        return idGenerator;
774    }
775}