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