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