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        boolean locked = writeLock();
280        try {
281            super.load(data);
282
283            WayData wayData = (WayData) data;
284
285            if (!wayData.getNodes().isEmpty() && getDataSet() == null) {
286                throw new AssertionError("Data consistency problem - way without dataset detected");
287            }
288
289            List<Node> newNodes = new ArrayList<>(wayData.getNodes().size());
290            for (Long nodeId : wayData.getNodes()) {
291                Node node = (Node) getDataSet().getPrimitiveById(nodeId, OsmPrimitiveType.NODE);
292                if (node != null) {
293                    newNodes.add(node);
294                } else {
295                    throw new AssertionError("Data consistency problem - way with missing node detected");
296                }
297            }
298            setNodes(newNodes);
299        } finally {
300            writeUnlock(locked);
301        }
302    }
303
304    @Override
305    public WayData save() {
306        WayData data = new WayData();
307        saveCommonAttributes(data);
308        for (Node node:nodes) {
309            data.getNodes().add(node.getUniqueId());
310        }
311        return data;
312    }
313
314    @Override
315    public void cloneFrom(OsmPrimitive osm) {
316        boolean locked = writeLock();
317        try {
318            super.cloneFrom(osm);
319            Way otherWay = (Way) osm;
320            setNodes(otherWay.getNodes());
321        } finally {
322            writeUnlock(locked);
323        }
324    }
325
326    @Override
327    public String toString() {
328        String nodesDesc = isIncomplete() ? "(incomplete)" : "nodes=" + Arrays.toString(nodes);
329        return "{Way id=" + getUniqueId() + " version=" + getVersion()+ ' ' + getFlagsAsString() + ' ' + nodesDesc + '}';
330    }
331
332    @Override
333    public boolean hasEqualSemanticAttributes(OsmPrimitive other, boolean testInterestingTagsOnly) {
334        if (!(other instanceof Way))
335            return false;
336        if (!super.hasEqualSemanticAttributes(other, testInterestingTagsOnly))
337            return false;
338        Way w = (Way) other;
339        if (getNodesCount() != w.getNodesCount()) return false;
340        for (int i = 0; i < getNodesCount(); i++) {
341            if (!getNode(i).hasEqualSemanticAttributes(w.getNode(i)))
342                return false;
343        }
344        return true;
345    }
346
347    @Override
348    public int compareTo(OsmPrimitive o) {
349        if (o instanceof Relation)
350            return 1;
351        return o instanceof Way ? Long.compare(getUniqueId(), o.getUniqueId()) : -1;
352    }
353
354    /**
355     * Removes the given {@link Node} from this way. Ignored, if n is null.
356     * @param n The node to remove. Ignored, if null
357     * @since 1463
358     */
359    public void removeNode(Node n) {
360        if (n == null || isIncomplete()) return;
361        boolean locked = writeLock();
362        try {
363            boolean closed = lastNode() == n && firstNode() == n;
364            int i;
365            List<Node> copy = getNodes();
366            while ((i = copy.indexOf(n)) >= 0) {
367                copy.remove(i);
368            }
369            i = copy.size();
370            if (closed && i > 2) {
371                copy.add(copy.get(0));
372            } else if (i >= 2 && i <= 3 && copy.get(0) == copy.get(i-1)) {
373                copy.remove(i-1);
374            }
375            setNodes(removeDouble(copy));
376            n.clearCachedStyle();
377        } finally {
378            writeUnlock(locked);
379        }
380    }
381
382    /**
383     * Removes the given set of {@link Node nodes} from this way. Ignored, if selection is null.
384     * @param selection The selection of nodes to remove. Ignored, if null
385     * @since 5408
386     */
387    public void removeNodes(Set<? extends Node> selection) {
388        if (selection == null || isIncomplete()) return;
389        boolean locked = writeLock();
390        try {
391            boolean closed = isClosed() && selection.contains(lastNode());
392            List<Node> copy = new ArrayList<>();
393
394            for (Node n: nodes) {
395                if (!selection.contains(n)) {
396                    copy.add(n);
397                }
398            }
399
400            int i = copy.size();
401            if (closed && i > 2) {
402                copy.add(copy.get(0));
403            } else if (i >= 2 && i <= 3 && copy.get(0) == copy.get(i-1)) {
404                copy.remove(i-1);
405            }
406            setNodes(removeDouble(copy));
407            for (Node n : selection) {
408                n.clearCachedStyle();
409            }
410        } finally {
411            writeUnlock(locked);
412        }
413    }
414
415    /**
416     * Adds a node to the end of the list of nodes. Ignored, if n is null.
417     *
418     * @param n the node. Ignored, if null
419     * @throws IllegalStateException if this way is marked as incomplete. We can't add a node
420     * to an incomplete way
421     * @since 1313
422     */
423    public void addNode(Node n) {
424        if (n == null) return;
425
426        boolean locked = writeLock();
427        try {
428            if (isIncomplete())
429                throw new IllegalStateException(tr("Cannot add node {0} to incomplete way {1}.", n.getId(), getId()));
430            clearCachedStyle();
431            n.addReferrer(this);
432            nodes = Utils.addInArrayCopy(nodes, n);
433            n.clearCachedStyle();
434            fireNodesChanged();
435        } finally {
436            writeUnlock(locked);
437        }
438    }
439
440    /**
441     * Adds a node at position offs.
442     *
443     * @param offs the offset
444     * @param n the node. Ignored, if null.
445     * @throws IllegalStateException if this way is marked as incomplete. We can't add a node
446     * to an incomplete way
447     * @throws IndexOutOfBoundsException if offs is out of bounds
448     * @since 1313
449     */
450    public void addNode(int offs, Node n) {
451        if (n == null) return;
452
453        boolean locked = writeLock();
454        try {
455            if (isIncomplete())
456                throw new IllegalStateException(tr("Cannot add node {0} to incomplete way {1}.", n.getId(), getId()));
457
458            clearCachedStyle();
459            n.addReferrer(this);
460            Node[] newNodes = new Node[nodes.length + 1];
461            System.arraycopy(nodes, 0, newNodes, 0, offs);
462            System.arraycopy(nodes, offs, newNodes, offs + 1, nodes.length - offs);
463            newNodes[offs] = n;
464            nodes = newNodes;
465            n.clearCachedStyle();
466            fireNodesChanged();
467        } finally {
468            writeUnlock(locked);
469        }
470    }
471
472    @Override
473    public void setDeleted(boolean deleted) {
474        boolean locked = writeLock();
475        try {
476            for (Node n:nodes) {
477                if (deleted) {
478                    n.removeReferrer(this);
479                } else {
480                    n.addReferrer(this);
481                }
482                n.clearCachedStyle();
483            }
484            fireNodesChanged();
485            super.setDeleted(deleted);
486        } finally {
487            writeUnlock(locked);
488        }
489    }
490
491    @Override
492    public boolean isClosed() {
493        if (isIncomplete()) return false;
494
495        Node[] nodes = this.nodes;
496        return nodes.length >= 3 && nodes[nodes.length-1] == nodes[0];
497    }
498
499    /**
500     * Determines if this way denotes an area (closed way with at least three distinct nodes).
501     * @return {@code true} if this way is closed and contains at least three distinct nodes
502     * @see #isClosed
503     * @since 5490
504     */
505    public boolean isArea() {
506        if (this.nodes.length >= 4 && isClosed()) {
507            Node distinctNode = null;
508            for (int i = 1; i < nodes.length-1; i++) {
509                if (distinctNode == null && nodes[i] != nodes[0]) {
510                    distinctNode = nodes[i];
511                } else if (distinctNode != null && nodes[i] != nodes[0] && nodes[i] != distinctNode) {
512                    return true;
513                }
514            }
515        }
516        return false;
517    }
518
519    /**
520     * Returns the last node of this way.
521     * The result equals <tt>{@link #getNode getNode}({@link #getNodesCount getNodesCount} - 1)</tt>.
522     * @return the last node of this way
523     * @since 1400
524     */
525    public Node lastNode() {
526        Node[] nodes = this.nodes;
527        if (isIncomplete() || nodes.length == 0) return null;
528        return nodes[nodes.length-1];
529    }
530
531    /**
532     * Returns the first node of this way.
533     * The result equals {@link #getNode getNode}{@code (0)}.
534     * @return the first node of this way
535     * @since 1400
536     */
537    public Node firstNode() {
538        Node[] nodes = this.nodes;
539        if (isIncomplete() || nodes.length == 0) return null;
540        return nodes[0];
541    }
542
543    /**
544     * Replies true if the given node is the first or the last one of this way, false otherwise.
545     * @param n The node to test
546     * @return true if the {@code n} is the first or the last node, false otherwise.
547     * @since 1400
548     */
549    public boolean isFirstLastNode(Node n) {
550        Node[] nodes = this.nodes;
551        if (isIncomplete() || nodes.length == 0) return false;
552        return n == nodes[0] || n == nodes[nodes.length -1];
553    }
554
555    /**
556     * Replies true if the given node is an inner node of this way, false otherwise.
557     * @param n The node to test
558     * @return true if the {@code n} is an inner node, false otherwise.
559     * @since 3515
560     */
561    public boolean isInnerNode(Node n) {
562        Node[] nodes = this.nodes;
563        if (isIncomplete() || nodes.length <= 2) return false;
564        /* circular ways have only inner nodes, so return true for them! */
565        if (n == nodes[0] && n == nodes[nodes.length-1]) return true;
566        for (int i = 1; i < nodes.length - 1; ++i) {
567            if (nodes[i] == n) return true;
568        }
569        return false;
570    }
571
572    @Override
573    public String getDisplayName(NameFormatter formatter) {
574        return formatter.format(this);
575    }
576
577    @Override
578    public OsmPrimitiveType getType() {
579        return OsmPrimitiveType.WAY;
580    }
581
582    @Override
583    public OsmPrimitiveType getDisplayType() {
584        return isClosed() ? OsmPrimitiveType.CLOSEDWAY : OsmPrimitiveType.WAY;
585    }
586
587    private void checkNodes() {
588        DataSet dataSet = getDataSet();
589        if (dataSet != null) {
590            Node[] nodes = this.nodes;
591            for (Node n: nodes) {
592                if (n.getDataSet() != dataSet)
593                    throw new DataIntegrityProblemException("Nodes in way must be in the same dataset",
594                            tr("Nodes in way must be in the same dataset"));
595                if (n.isDeleted())
596                    throw new DataIntegrityProblemException("Deleted node referenced: " + toString(),
597                            "<html>" + tr("Deleted node referenced by {0}",
598                                    DefaultNameFormatter.getInstance().formatAsHtmlUnorderedList(this)) + "</html>");
599            }
600            if (Main.pref.getBoolean("debug.checkNullCoor", true)) {
601                for (Node n: nodes) {
602                    if (n.isVisible() && !n.isIncomplete() && !n.isLatLonKnown())
603                        throw new DataIntegrityProblemException("Complete visible node with null coordinates: " + toString(),
604                                "<html>" + tr("Complete node {0} with null coordinates in way {1}",
605                                DefaultNameFormatter.getInstance().formatAsHtmlUnorderedList(n),
606                                DefaultNameFormatter.getInstance().formatAsHtmlUnorderedList(this)) + "</html>");
607                }
608            }
609        }
610    }
611
612    private void fireNodesChanged() {
613        checkNodes();
614        if (getDataSet() != null) {
615            getDataSet().fireWayNodesChanged(this);
616        }
617    }
618
619    @Override
620    void setDataset(DataSet dataSet) {
621        super.setDataset(dataSet);
622        checkNodes();
623    }
624
625    @Override
626    public BBox getBBox() {
627        if (getDataSet() == null)
628            return new BBox(this);
629        if (bbox == null) {
630            bbox = new BBox(this);
631        }
632        return new BBox(bbox);
633    }
634
635    @Override
636    public void updatePosition() {
637        bbox = new BBox(this);
638    }
639
640    /**
641     * Replies true if this way has incomplete nodes, false otherwise.
642     * @return true if this way has incomplete nodes, false otherwise.
643     * @since 2587
644     */
645    public boolean hasIncompleteNodes() {
646        Node[] nodes = this.nodes;
647        for (Node node : nodes) {
648            if (node.isIncomplete())
649                return true;
650        }
651        return false;
652    }
653
654    @Override
655    public boolean isUsable() {
656        return super.isUsable() && !hasIncompleteNodes();
657    }
658
659    @Override
660    public boolean isDrawable() {
661        return super.isDrawable() && !hasIncompleteNodes();
662    }
663
664    /**
665     * Replies the length of the way, in metres, as computed by {@link LatLon#greatCircleDistance}.
666     * @return The length of the way, in metres
667     * @since 4138
668     */
669    public double getLength() {
670        double length = 0;
671        Node lastN = null;
672        for (Node n:nodes) {
673            if (lastN != null) {
674                LatLon lastNcoor = lastN.getCoor();
675                LatLon coor = n.getCoor();
676                if (lastNcoor != null && coor != null) {
677                    length += coor.greatCircleDistance(lastNcoor);
678                }
679            }
680            lastN = n;
681        }
682        return length;
683    }
684
685    /**
686     * Replies the length of the longest segment of the way, in metres, as computed by {@link LatLon#greatCircleDistance}.
687     * @return The length of the segment, in metres
688     * @since 8320
689     */
690    public double getLongestSegmentLength() {
691        double length = 0;
692        Node lastN = null;
693        for (Node n:nodes) {
694            if (lastN != null) {
695                LatLon lastNcoor = lastN.getCoor();
696                LatLon coor = n.getCoor();
697                if (lastNcoor != null && coor != null) {
698                    double l = coor.greatCircleDistance(lastNcoor);
699                    if (l > length) {
700                        length = l;
701                    }
702                }
703            }
704            lastN = n;
705        }
706        return length;
707    }
708
709    /**
710     * Tests if this way is a oneway.
711     * @return {@code 1} if the way is a oneway,
712     *         {@code -1} if the way is a reversed oneway,
713     *         {@code 0} otherwise.
714     * @since 5199
715     */
716    public int isOneway() {
717        String oneway = get("oneway");
718        if (oneway != null) {
719            if ("-1".equals(oneway)) {
720                return -1;
721            } else {
722                Boolean isOneway = OsmUtils.getOsmBoolean(oneway);
723                if (isOneway != null && isOneway) {
724                    return 1;
725                }
726            }
727        }
728        return 0;
729    }
730
731    /**
732     * Replies the first node of this way, respecting or not its oneway state.
733     * @param respectOneway If true and if this way is a reversed oneway, replies the last node. Otherwise, replies the first node.
734     * @return the first node of this way, according to {@code respectOneway} and its oneway state.
735     * @since 5199
736     */
737    public Node firstNode(boolean respectOneway) {
738        return !respectOneway || isOneway() != -1 ? firstNode() : lastNode();
739    }
740
741    /**
742     * Replies the last node of this way, respecting or not its oneway state.
743     * @param respectOneway If true and if this way is a reversed oneway, replies the first node. Otherwise, replies the last node.
744     * @return the last node of this way, according to {@code respectOneway} and its oneway state.
745     * @since 5199
746     */
747    public Node lastNode(boolean respectOneway) {
748        return !respectOneway || isOneway() != -1 ? lastNode() : firstNode();
749    }
750
751    @Override
752    public boolean concernsArea() {
753        return hasAreaTags();
754    }
755
756    @Override
757    public boolean isOutsideDownloadArea() {
758        for (final Node n : nodes) {
759            if (n.isOutsideDownloadArea()) {
760                return true;
761            }
762        }
763        return false;
764    }
765
766    @Override
767    protected void keysChangedImpl(Map<String, String> originalKeys) {
768        super.keysChangedImpl(originalKeys);
769        clearCachedNodeStyles();
770    }
771
772    public void clearCachedNodeStyles() {
773        for (final Node n : nodes) {
774            n.clearCachedStyle();
775        }
776    }
777}