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