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