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