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