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    @Override
102    public int getNodesCount() {
103        return nodes.length;
104    }
105
106    /**
107     * Replies the real number of nodes in this way (full number of nodes minus one if this way is closed)
108     *
109     * @return the real number of nodes in this way.
110     *
111     * @see #getNodesCount()
112     * @see #isClosed()
113     * @since 5847
114     */
115    public int getRealNodesCount() {
116        int count = getNodesCount();
117        return isClosed() ? count-1 : count;
118    }
119
120    /**
121     * Replies the node at position <code>index</code>.
122     *
123     * @param index the position
124     * @return  the node at position <code>index</code>
125     * @throws IndexOutOfBoundsException if <code>index</code> &lt; 0
126     * or <code>index</code> &gt;= {@link #getNodesCount()}
127     * @since 1862
128     */
129    public Node getNode(int index) {
130        return nodes[index];
131    }
132
133    @Override
134    public long getNodeId(int idx) {
135        return nodes[idx].getUniqueId();
136    }
137
138    /**
139     * Replies true if this way contains the node <code>node</code>, false
140     * otherwise. Replies false if  <code>node</code> is null.
141     *
142     * @param node the node. May be null.
143     * @return true if this way contains the node <code>node</code>, false
144     * otherwise
145     * @since 1911
146     */
147    public boolean containsNode(Node node) {
148        if (node == null) return false;
149
150        Node[] nodes = this.nodes;
151        for (Node n : nodes) {
152            if (n.equals(node))
153                return true;
154        }
155        return false;
156    }
157
158    /**
159     * Return nodes adjacent to <code>node</code>
160     *
161     * @param node the node. May be null.
162     * @return Set of nodes adjacent to <code>node</code>
163     * @since 4671
164     */
165    public Set<Node> getNeighbours(Node node) {
166        Set<Node> neigh = new HashSet<>();
167
168        if (node == null) return neigh;
169
170        Node[] nodes = this.nodes;
171        for (int i = 0; i < nodes.length; i++) {
172            if (nodes[i].equals(node)) {
173                if (i > 0)
174                    neigh.add(nodes[i-1]);
175                if (i < nodes.length-1)
176                    neigh.add(nodes[i+1]);
177            }
178        }
179        return neigh;
180    }
181
182    /**
183     * Replies the ordered {@link List} of chunks of this way. Each chunk is replied as a {@link Pair} of {@link Node nodes}.
184     * @param sort If true, the nodes of each pair are sorted as defined by {@link Pair#sort}.
185     *             If false, Pair.a and Pair.b are in the way order
186     *             (i.e for a given Pair(n), Pair(n-1).b == Pair(n).a, Pair(n).b == Pair(n+1).a, etc.)
187     * @return The ordered list of chunks of this way.
188     * @since 3348
189     */
190    public List<Pair<Node, Node>> getNodePairs(boolean sort) {
191        List<Pair<Node, Node>> chunkSet = new ArrayList<>();
192        if (isIncomplete()) return chunkSet;
193        Node lastN = null;
194        Node[] nodes = this.nodes;
195        for (Node n : nodes) {
196            if (lastN == null) {
197                lastN = n;
198                continue;
199            }
200            Pair<Node, Node> np = new Pair<>(lastN, n);
201            if (sort) {
202                Pair.sort(np);
203            }
204            chunkSet.add(np);
205            lastN = n;
206        }
207        return chunkSet;
208    }
209
210    @Override public void accept(Visitor visitor) {
211        visitor.visit(this);
212    }
213
214    @Override public void accept(PrimitiveVisitor visitor) {
215        visitor.visit(this);
216    }
217
218    protected Way(long id, boolean allowNegative) {
219        super(id, allowNegative);
220    }
221
222    /**
223     * Contructs a new {@code Way} with id 0.
224     * @since 86
225     */
226    public Way() {
227        super(0, false);
228    }
229
230    /**
231     * Contructs a new {@code Way} from an existing {@code Way}.
232     * @param original The original {@code Way} to be identically cloned. Must not be null
233     * @param clearMetadata If {@code true}, clears the OSM id and other metadata as defined by {@link #clearOsmMetadata}.
234     * If {@code false}, does nothing
235     * @since 2410
236     */
237    public Way(Way original, boolean clearMetadata) {
238        super(original.getUniqueId(), true);
239        cloneFrom(original);
240        if (clearMetadata) {
241            clearOsmMetadata();
242        }
243    }
244
245    /**
246     * Contructs a new {@code Way} from an existing {@code Way} (including its id).
247     * @param original The original {@code Way} to be identically cloned. Must not be null
248     * @since 86
249     */
250    public Way(Way original) {
251        this(original, false);
252    }
253
254    /**
255     * Contructs a new {@code Way} for the given id. If the id &gt; 0, the way is marked
256     * as incomplete. If id == 0 then way is marked as new
257     *
258     * @param id the id. &gt;= 0 required
259     * @throws IllegalArgumentException if id &lt; 0
260     * @since 343
261     */
262    public Way(long id) {
263        super(id, false);
264    }
265
266    /**
267     * Contructs a new {@code Way} with given id and version.
268     * @param id the id. &gt;= 0 required
269     * @param version the version
270     * @throws IllegalArgumentException if id &lt; 0
271     * @since 2620
272     */
273    public Way(long id, int version) {
274        super(id, version, false);
275    }
276
277    @Override
278    public void load(PrimitiveData data) {
279        if (!(data instanceof WayData))
280            throw new IllegalArgumentException("Not a way data: " + data);
281        boolean locked = writeLock();
282        try {
283            super.load(data);
284
285            WayData wayData = (WayData) data;
286
287            if (!wayData.getNodes().isEmpty() && getDataSet() == null) {
288                throw new AssertionError("Data consistency problem - way without dataset detected");
289            }
290
291            List<Node> newNodes = new ArrayList<>(wayData.getNodes().size());
292            for (Long nodeId : wayData.getNodes()) {
293                Node node = (Node) getDataSet().getPrimitiveById(nodeId, OsmPrimitiveType.NODE);
294                if (node != null) {
295                    newNodes.add(node);
296                } else {
297                    throw new AssertionError("Data consistency problem - way with missing node detected");
298                }
299            }
300            setNodes(newNodes);
301        } finally {
302            writeUnlock(locked);
303        }
304    }
305
306    @Override
307    public WayData save() {
308        WayData data = new WayData();
309        saveCommonAttributes(data);
310        for (Node node:nodes) {
311            data.getNodes().add(node.getUniqueId());
312        }
313        return data;
314    }
315
316    @Override
317    public void cloneFrom(OsmPrimitive osm) {
318        if (!(osm instanceof Way))
319            throw new IllegalArgumentException("Not a way: " + 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, boolean testInterestingTagsOnly) {
338        if (!(other instanceof Way))
339            return false;
340        Way w = (Way) other;
341        if (getNodesCount() != w.getNodesCount()) return false;
342        if (!super.hasEqualSemanticAttributes(other, testInterestingTagsOnly))
343            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) {
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    protected void addToBBox(BBox box, Set<PrimitiveId> visited) {
641        box.add(getBBox());
642    }
643
644    @Override
645    public void updatePosition() {
646        bbox = new BBox(this);
647    }
648
649    /**
650     * Replies true if this way has incomplete nodes, false otherwise.
651     * @return true if this way has incomplete nodes, false otherwise.
652     * @since 2587
653     */
654    public boolean hasIncompleteNodes() {
655        Node[] nodes = this.nodes;
656        for (Node node : nodes) {
657            if (node.isIncomplete())
658                return true;
659        }
660        return false;
661    }
662
663    @Override
664    public boolean isUsable() {
665        return super.isUsable() && !hasIncompleteNodes();
666    }
667
668    @Override
669    public boolean isDrawable() {
670        return super.isDrawable() && !hasIncompleteNodes();
671    }
672
673    /**
674     * Replies the length of the way, in metres, as computed by {@link LatLon#greatCircleDistance}.
675     * @return The length of the way, in metres
676     * @since 4138
677     */
678    public double getLength() {
679        double length = 0;
680        Node lastN = null;
681        for (Node n:nodes) {
682            if (lastN != null) {
683                LatLon lastNcoor = lastN.getCoor();
684                LatLon coor = n.getCoor();
685                if (lastNcoor != null && coor != null) {
686                    length += coor.greatCircleDistance(lastNcoor);
687                }
688            }
689            lastN = n;
690        }
691        return length;
692    }
693
694    /**
695     * Replies the length of the longest segment of the way, in metres, as computed by {@link LatLon#greatCircleDistance}.
696     * @return The length of the segment, in metres
697     * @since 8320
698     */
699    public double getLongestSegmentLength() {
700        double length = 0;
701        Node lastN = null;
702        for (Node n:nodes) {
703            if (lastN != null) {
704                LatLon lastNcoor = lastN.getCoor();
705                LatLon coor = n.getCoor();
706                if (lastNcoor != null && coor != null) {
707                    double l = coor.greatCircleDistance(lastNcoor);
708                    if (l > length) {
709                        length = l;
710                    }
711                }
712            }
713            lastN = n;
714        }
715        return length;
716    }
717
718    /**
719     * Tests if this way is a oneway.
720     * @return {@code 1} if the way is a oneway,
721     *         {@code -1} if the way is a reversed oneway,
722     *         {@code 0} otherwise.
723     * @since 5199
724     */
725    public int isOneway() {
726        String oneway = get("oneway");
727        if (oneway != null) {
728            if ("-1".equals(oneway)) {
729                return -1;
730            } else {
731                Boolean isOneway = OsmUtils.getOsmBoolean(oneway);
732                if (isOneway != null && isOneway) {
733                    return 1;
734                }
735            }
736        }
737        return 0;
738    }
739
740    /**
741     * Replies the first node of this way, respecting or not its oneway state.
742     * @param respectOneway If true and if this way is a reversed oneway, replies the last node. Otherwise, replies the first node.
743     * @return the first node of this way, according to {@code respectOneway} and its oneway state.
744     * @since 5199
745     */
746    public Node firstNode(boolean respectOneway) {
747        return !respectOneway || isOneway() != -1 ? firstNode() : lastNode();
748    }
749
750    /**
751     * Replies the last node of this way, respecting or not its oneway state.
752     * @param respectOneway If true and if this way is a reversed oneway, replies the first node. Otherwise, replies the last node.
753     * @return the last node of this way, according to {@code respectOneway} and its oneway state.
754     * @since 5199
755     */
756    public Node lastNode(boolean respectOneway) {
757        return !respectOneway || isOneway() != -1 ? lastNode() : firstNode();
758    }
759
760    @Override
761    public boolean concernsArea() {
762        return hasAreaTags();
763    }
764
765    @Override
766    public boolean isOutsideDownloadArea() {
767        for (final Node n : nodes) {
768            if (n.isOutsideDownloadArea()) {
769                return true;
770            }
771        }
772        return false;
773    }
774
775    @Override
776    protected void keysChangedImpl(Map<String, String> originalKeys) {
777        super.keysChangedImpl(originalKeys);
778        clearCachedNodeStyles();
779    }
780
781    public void clearCachedNodeStyles() {
782        for (final Node n : nodes) {
783            n.clearCachedStyle();
784        }
785    }
786}