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