source: osm/applications/editors/josm/plugins/reltoolbox/src/relcontext/actions/TheRing.java@ 36217

Last change on this file since 36217 was 36217, checked in by GerdP, 23 months ago

fix #23521: fix some memory leaks

  • dispose dialogs
  • either avoid to create clones of ways or relations or use setNodes(null) / setMembers(null)
  • replaces most ChangeCommand instances by better specialized alternatives
  • add some comments
  • fix some checkstyle / sonar issues
File size: 23.7 KB
Line 
1// License: GPL. For details, see LICENSE file.
2package relcontext.actions;
3
4import static org.openstreetmap.josm.tools.I18n.tr;
5
6import java.util.ArrayList;
7import java.util.Collection;
8import java.util.Collections;
9import java.util.HashMap;
10import java.util.List;
11import java.util.Map;
12
13import javax.swing.JOptionPane;
14
15import org.openstreetmap.josm.command.AddCommand;
16import org.openstreetmap.josm.command.ChangeCommand;
17import org.openstreetmap.josm.command.ChangeMembersCommand;
18import org.openstreetmap.josm.command.ChangeNodesCommand;
19import org.openstreetmap.josm.command.ChangePropertyCommand;
20import org.openstreetmap.josm.command.Command;
21import org.openstreetmap.josm.command.DeleteCommand;
22import org.openstreetmap.josm.data.osm.DataSet;
23import org.openstreetmap.josm.data.osm.Node;
24import org.openstreetmap.josm.data.osm.OsmPrimitive;
25import org.openstreetmap.josm.data.osm.Relation;
26import org.openstreetmap.josm.data.osm.RelationMember;
27import org.openstreetmap.josm.data.osm.Way;
28import org.openstreetmap.josm.gui.MainApplication;
29import org.openstreetmap.josm.spi.preferences.Config;
30import org.openstreetmap.josm.tools.Geometry;
31import org.openstreetmap.josm.tools.Geometry.PolygonIntersection;
32import org.openstreetmap.josm.tools.Logging;
33
34/**
35 * One ring that contains segments forming an outer way of multipolygon.
36 * This class is used in {@link CreateMultipolygonAction#makeManySimpleMultipolygons(java.util.Collection)}.
37 *
38 * @author Zverik
39 */
40public class TheRing {
41 private static final String PREF_MULTIPOLY = "reltoolbox.multipolygon.";
42
43 private final Way source;
44 private final List<RingSegment> segments;
45 private Relation relation;
46
47 public TheRing(Way source) {
48 this.source = source;
49 segments = new ArrayList<>(1);
50 segments.add(new RingSegment(source));
51 }
52
53 public static boolean areAllOfThoseRings(Collection<Way> ways) {
54 List<Way> rings = new ArrayList<>();
55 for (Way way : ways) {
56 if (way.isClosed()) {
57 rings.add(way);
58 } else
59 return false;
60 }
61 if (rings.isEmpty() || ways.size() == 1)
62 return false;
63
64 // check for non-containment of rings
65 for (int i = 0; i < rings.size() - 1; i++) {
66 for (int j = i + 1; j < rings.size(); j++) {
67 PolygonIntersection intersection = Geometry.polygonIntersection(rings.get(i).getNodes(), rings.get(j).getNodes());
68 if (intersection == PolygonIntersection.FIRST_INSIDE_SECOND || intersection == PolygonIntersection.SECOND_INSIDE_FIRST)
69 return false;
70 }
71 }
72
73 return true;
74 }
75
76 /**
77 * Creates ALOT of Multipolygons and pets him gently.
78 * @return list of new relations.
79 */
80 public static List<Relation> makeManySimpleMultipolygons(Collection<Way> selection, List<Command> commands) {
81 log("---------------------------------------");
82 List<TheRing> rings = new ArrayList<>(selection.size());
83 for (Way w : selection) {
84 rings.add(new TheRing(w));
85 }
86 for (int i = 0; i < rings.size() - 1; i++) {
87 for (int j = i + 1; j < rings.size(); j++) {
88 rings.get(i).collide(rings.get(j));
89 }
90 }
91 redistributeSegments(rings);
92 List<Relation> relations = new ArrayList<>();
93 Map<Relation, Relation> relationCache = new HashMap<>();
94 for (TheRing r : rings) {
95 commands.addAll(r.getCommands(relationCache));
96 relations.add(r.getRelation());
97 }
98 updateCommandsWithRelations(commands, relationCache);
99 return relations;
100 }
101
102 public void collide(TheRing other) {
103 boolean collideNoted = false;
104 for (int i = 0; i < segments.size(); i++) {
105 RingSegment segment1 = segments.get(i);
106 if (!segment1.isReference()) {
107 for (int j = 0; j < other.segments.size(); j++) {
108 RingSegment segment2 = other.segments.get(j);
109 if (!segment2.isReference()) {
110 log("Comparing " + segment1 + " and " + segment2);
111 Node[] split = getSplitNodes(segment1.getNodes(), segment2.getNodes(), segment1.isRing(), segment2.isRing());
112 if (split != null) {
113 if (!collideNoted) {
114 log("Rings for ways " + source.getUniqueId() + " and " + other.source.getUniqueId() + " collide.");
115 collideNoted = true;
116 }
117 RingSegment segment = splitRingAt(i, split[0], split[1]);
118 RingSegment otherSegment = other.splitRingAt(j, split[2], split[3]);
119 if (!areSegmentsEqual(segment, otherSegment))
120 throw new IllegalArgumentException(
121 "Error: algorithm gave incorrect segments: " + segment + " and " + otherSegment);
122 segment.makeReference(otherSegment);
123 }
124 }
125 if (segment1.isReference()) {
126 break;
127 }
128 }
129 }
130 }
131 }
132
133 /**
134 * Returns array of {start1, last1, start2, last2} or null if there is no common nodes.
135 */
136 public static Node[] getSplitNodes(List<Node> nodes1, List<Node> nodes2, boolean isRing1, boolean isRing2) {
137 int pos = 0;
138 while (pos < nodes1.size() && !nodes2.contains(nodes1.get(pos))) {
139 pos++;
140 }
141 boolean collideFound = pos == nodes1.size();
142 if (pos == 0 && isRing1) {
143 // rewind a bit
144 pos = nodes1.size() - 1;
145 while (pos > 0 && nodes2.contains(nodes1.get(pos))) {
146 pos--;
147 }
148 if (pos == 0 && nodes1.size() == nodes2.size()) {
149 JOptionPane.showMessageDialog(MainApplication.getMainFrame(),
150 tr("Two rings are equal, and this must not be."), tr("Multipolygon from rings"), JOptionPane.ERROR_MESSAGE);
151 return null;
152 }
153 pos = pos == nodes1.size() - 1 ? 0 : pos + 1;
154 }
155 int firstPos = isRing1 ? pos : nodes1.size();
156 while (!collideFound) {
157 log("pos=" + pos);
158 int start1 = pos;
159 int start2 = nodes2.indexOf(nodes1.get(start1));
160 int last1 = incrementBy(start1, 1, nodes1.size(), isRing1);
161 int last2 = start2;
162 int increment2 = 0;
163 if (last1 >= 0) {
164 last2 = incrementBy(start2, -1, nodes2.size(), isRing2);
165 if (last2 >= 0 && nodes1.get(last1).equals(nodes2.get(last2))) {
166 increment2 = -1;
167 } else {
168 last2 = incrementBy(start2, 1, nodes2.size(), isRing2);
169 if (last2 >= 0 && nodes1.get(last1).equals(nodes2.get(last2))) {
170 increment2 = 1;
171 }
172 }
173 }
174 log("last1=" + last1 + " last2=" + last2 + " increment2=" + increment2);
175 if (increment2 != 0) {
176 // find the first nodes
177 boolean reachedEnd = false;
178 while (!reachedEnd) {
179 int newLast1 = incrementBy(last1, 1, nodes1.size(), isRing1);
180 int newLast2 = incrementBy(last2, increment2, nodes2.size(), isRing2);
181 if (newLast1 < 0 || newLast2 < 0 || !nodes1.get(newLast1).equals(nodes2.get(newLast2))) {
182 reachedEnd = true;
183 } else {
184 last1 = newLast1;
185 last2 = newLast2;
186 }
187 }
188 log("last1=" + last1 + " last2=" + last2);
189 if (increment2 < 0) {
190 int tmp = start2;
191 start2 = last2;
192 last2 = tmp;
193 }
194 return new Node[] {nodes1.get(start1), nodes1.get(last1), nodes2.get(start2), nodes2.get(last2)};
195 } else {
196 pos = last1;
197 while (pos != firstPos && pos >= 0 && !nodes2.contains(nodes1.get(pos))) {
198 pos = incrementBy(pos, 1, nodes1.size(), isRing1);
199 }
200 if (pos < 0 || pos == firstPos || !nodes2.contains(nodes1.get(pos))) {
201 collideFound = true;
202 }
203 }
204 }
205 return null;
206 }
207
208 private static int incrementBy(int value, int increment, int limit1, boolean isRing) {
209 int result = value + increment;
210 if (result < 0)
211 return isRing ? result + limit1 : -1;
212 else if (result >= limit1)
213 return isRing ? result - limit1 : -1;
214 else
215 return result;
216 }
217
218 private static boolean areSegmentsEqual(RingSegment seg1, RingSegment seg2) {
219 List<Node> nodes1 = seg1.getNodes();
220 List<Node> nodes2 = seg2.getNodes();
221 int size = nodes1.size();
222 if (size != nodes2.size())
223 return false;
224 boolean reverse = size > 1 && !nodes1.get(0).equals(nodes2.get(0));
225 for (int i = 0; i < size; i++) {
226 if (!nodes1.get(i).equals(nodes2.get(reverse ? size-1-i : i)))
227 return false;
228 }
229 return true;
230 }
231
232 /**
233 * Split the segment in this ring at those nodes.
234 * @return The segment between nodes.
235 */
236 private RingSegment splitRingAt(int segmentIndex, Node n1, Node n2) {
237 if (n1.equals(n2))
238 throw new IllegalArgumentException("Both nodes are equal, id=" + n1.getUniqueId());
239 RingSegment segment = segments.get(segmentIndex);
240 boolean isRing = segment.isRing();
241 log("Split segment " + segment + " at nodes " + n1.getUniqueId() + " and " + n2.getUniqueId());
242 boolean reversed = segment.getNodes().indexOf(n2) < segment.getNodes().indexOf(n1);
243 if (reversed && !isRing) {
244 // order nodes
245 Node tmp = n1;
246 n1 = n2;
247 n2 = tmp;
248 }
249 RingSegment secondPart = isRing ? segment.split(n1, n2) : segment.split(n1);
250 // if secondPart == null, then n1 == firstNode
251 RingSegment thirdPart = isRing ? null : secondPart == null ? segment.split(n2) : secondPart.split(n2);
252 // if secondPart == null, then thirdPart is between n1 and n2
253 // otherwise, thirdPart is between n2 and lastNode
254 // if thirdPart == null, then n2 == lastNode
255 int pos = segmentIndex + 1;
256 if (secondPart != null) {
257 segments.add(pos++, secondPart);
258 }
259 if (thirdPart != null) {
260 segments.add(pos++, thirdPart);
261 }
262 return isRing || secondPart == null ? segment : secondPart;
263 }
264
265 /**
266 * Tries to arrange segments in order for each ring to have at least one.
267 * Also, sets source way for all rings.
268 * <p>
269 * If this method is not called, do not forget to call {@link #putSourceWayFirst()} for all rings.
270 */
271 public static void redistributeSegments(List<TheRing> rings) {
272 // build segments map
273 Map<RingSegment, TheRing> segmentMap = new HashMap<>();
274 for (TheRing ring : rings) {
275 for (RingSegment seg : ring.segments) {
276 if (!seg.isReference()) {
277 segmentMap.put(seg, ring);
278 }
279 }
280 }
281
282 // rearrange references
283 for (TheRing ring : rings) {
284 if (ring.countNonReferenceSegments() == 0) {
285 // need to find one non-reference segment
286 for (RingSegment seg : ring.segments) {
287 TheRing otherRing = segmentMap.get(seg.references);
288 if (otherRing.countNonReferenceSegments() > 1) {
289 // we could check for >0, but it is prone to deadlocking
290 seg.swapReference();
291 }
292 }
293 }
294 }
295
296 // initializing source way for each ring
297 for (TheRing ring : rings) {
298 ring.putSourceWayFirst();
299 }
300 }
301
302 private int countNonReferenceSegments() {
303 int count = 0;
304 for (RingSegment seg : segments) {
305 if (!seg.isReference()) {
306 count++;
307 }
308 }
309 return count;
310 }
311
312 public void putSourceWayFirst() {
313 for (RingSegment seg : segments) {
314 if (!seg.isReference()) {
315 seg.overrideWay(source);
316 return;
317 }
318 }
319 }
320
321 public List<Command> getCommands() {
322 return getCommands(true, null);
323 }
324
325 public List<Command> getCommands(Map<Relation, Relation> relationChangeMap) {
326 return getCommands(true, relationChangeMap);
327 }
328
329 /**
330 * Returns a list of commands to make a new relation and all newly created ways.
331 * The first way is copied from the source one, ChangeCommand is issued in this case.
332 */
333 public List<Command> getCommands(boolean createMultipolygon, Map<Relation, Relation> relationChangeMap) {
334 Way sourceCopy = new Way(source);
335 Map<String, String> tagsToRemove = new HashMap<>();
336 if (createMultipolygon) {
337 Collection<String> linearTags = Config.getPref().getList(PREF_MULTIPOLY + "lineartags",
338 CreateMultipolygonAction.DEFAULT_LINEAR_TAGS);
339 relation = new Relation();
340 relation.put("type", "multipolygon");
341 for (String key : source.keySet()) {
342 if (linearTags.contains(key)
343 || ("natural".equals(key) && "coastline".equals(source.get("natural"))))
344 continue;
345
346 relation.put(key, source.get(key));
347 sourceCopy.remove(key);
348 tagsToRemove.put(key, null);
349 }
350 }
351
352 // build a map of referencing relations
353 Map<Relation, Integer> referencingRelations = new HashMap<>();
354 List<Command> relationCommands = new ArrayList<>();
355 for (OsmPrimitive p : source.getReferrers()) {
356 if (p instanceof Relation) {
357 Relation rel;
358 if (relationChangeMap != null) {
359 rel = relationChangeMap.get(p);
360 if (rel == null) {
361 rel = new Relation((Relation) p);
362 relationChangeMap.put((Relation) p, rel);
363 }
364 } else {
365 rel = new Relation((Relation) p);
366 relationCommands.add(new ChangeCommand(p, rel)); // should not happen
367 }
368 for (int i = 0; i < rel.getMembersCount(); i++) {
369 if (rel.getMember(i).getMember().equals(source)) {
370 referencingRelations.put(rel, i);
371 }
372 }
373 }
374 }
375
376 DataSet ds = MainApplication.getLayerManager().getEditDataSet();
377 List<Command> commands = new ArrayList<>();
378 boolean foundOwnWay = false;
379 for (RingSegment seg : segments) {
380 boolean needAdding = !seg.isWayConstructed();
381 Way w = seg.constructWay(seg.isReference() ? null : sourceCopy);
382 if (needAdding) {
383 commands.add(new AddCommand(ds, w));
384 }
385 if (w.equals(source)) {
386 if (createMultipolygon || !seg.getWayNodes().equals(source.getNodes())) {
387 sourceCopy.setNodes(seg.getWayNodes());
388 if (!tagsToRemove.isEmpty()) {
389 commands.add(new ChangePropertyCommand(Collections.singleton(source), tagsToRemove));
390 }
391 if (!sourceCopy.getNodes().equals(source.getNodes()))
392 commands.add(new ChangeNodesCommand(source, sourceCopy.getNodes()));
393 }
394 foundOwnWay = true;
395 } else {
396 for (Map.Entry<Relation, Integer> entry : referencingRelations.entrySet()) {
397 Relation rel = entry.getKey();
398 int relIndex = entry.getValue();
399 rel.addMember(new RelationMember(rel.getMember(relIndex).getRole(), w));
400 }
401 }
402 if (createMultipolygon) {
403 relation.addMember(new RelationMember("outer", w));
404 }
405 }
406 sourceCopy.setNodes(null); // see #19885
407 if (!foundOwnWay) {
408 final Command deleteCommand = DeleteCommand.delete(Collections.singleton(source));
409 if (deleteCommand != null) {
410 commands.add(deleteCommand);
411 }
412 }
413 commands.addAll(relationCommands);
414 if (createMultipolygon) {
415 commands.add(new AddCommand(ds, relation));
416 }
417 return commands;
418 }
419
420 public static void updateCommandsWithRelations(List<Command> commands, Map<Relation, Relation> relationCache) {
421 for (Map.Entry<Relation, Relation> entry : relationCache.entrySet()) {
422 Relation oldRel = entry.getKey();
423 Relation newRel = entry.getValue();
424 if (oldRel.getKeys().equals(newRel.getKeys())) {
425 commands.add(new ChangeMembersCommand(oldRel, newRel.getMembers()));
426 newRel.setMembers(null); // see #19885
427 } else {
428 commands.add(new ChangeCommand(oldRel, newRel)); // should not happen
429 }
430 }
431 }
432
433 /**
434 * Returns the relation created in {@link #getCommands()}.
435 */
436 public Relation getRelation() {
437 return relation;
438 }
439
440 @Override
441 public String toString() {
442 StringBuilder sb = new StringBuilder("TheRing@");
443 sb.append(this.hashCode()).append('[').append("wayId: ").append(source == null ? "null" : source.getUniqueId()).append("; segments: ");
444 if (segments.isEmpty()) {
445 sb.append("empty");
446 } else {
447 sb.append(segments.get(0));
448 for (int i = 1; i < segments.size(); i++) {
449 sb.append(", ").append(segments.get(i));
450 }
451 }
452 return sb.append(']').toString();
453 }
454
455 private static void log(String s) {
456 Logging.debug(s);
457 }
458
459 private static class RingSegment {
460 private List<Node> nodes;
461 private RingSegment references;
462 private Way resultingWay;
463 private boolean wasTemplateApplied;
464 private boolean isRing;
465
466 RingSegment(Way w) {
467 this(w.getNodes());
468 }
469
470 RingSegment(List<Node> nodes) {
471 this.nodes = nodes;
472 isRing = nodes.size() > 1 && nodes.get(0).equals(nodes.get(nodes.size() - 1));
473 if (isRing) {
474 nodes.remove(nodes.size() - 1);
475 }
476 references = null;
477 }
478
479 /**
480 * Splits this segment at node n. Retains nodes 0..n and moves
481 * nodes n..N to a separate segment that is returned.
482 * @param n node at which to split.
483 * @return new segment, {@code null} if splitting is unnecessary.
484 */
485 public RingSegment split(Node n) {
486 if (nodes == null)
487 throw new IllegalArgumentException("Cannot split segment: it is a reference");
488 int pos = nodes.indexOf(n);
489 if (pos <= 0 || pos >= nodes.size() - 1)
490 return null;
491 List<Node> newNodes = new ArrayList<>(nodes.subList(pos, nodes.size()));
492 nodes.subList(pos + 1, nodes.size()).clear();
493 return new RingSegment(newNodes);
494 }
495
496 /**
497 * Split this segment as a way at two nodes. If one of them is null or at the end,
498 * split as an arc. Note: order of nodes is important.
499 * @return A new segment from n2 to n1.
500 */
501 public RingSegment split(Node n1, Node n2) {
502 if (nodes == null)
503 throw new IllegalArgumentException("Cannot split segment: it is a reference");
504 if (!isRing) {
505 if (n1 == null || nodes.get(0).equals(n1) || nodes.get(nodes.size() - 1).equals(n1))
506 return split(n2);
507 if (n2 == null || nodes.get(0).equals(n2) || nodes.get(nodes.size() - 1).equals(n2))
508 return split(n1);
509 throw new IllegalArgumentException("Split for two nodes is called for not-ring: " + this);
510 }
511 int pos1 = nodes.indexOf(n1);
512 int pos2 = nodes.indexOf(n2);
513 if (pos1 == pos2)
514 return null;
515
516 List<Node> newNodes = new ArrayList<>();
517 if (pos2 > pos1) {
518 newNodes.addAll(nodes.subList(pos2, nodes.size()));
519 newNodes.addAll(nodes.subList(0, pos1 + 1));
520 if (pos2 + 1 < nodes.size()) {
521 nodes.subList(pos2 + 1, nodes.size()).clear();
522 }
523 if (pos1 > 0) {
524 nodes.subList(0, pos1).clear();
525 }
526 } else {
527 newNodes.addAll(nodes.subList(pos2, pos1 + 1));
528 nodes.addAll(new ArrayList<>(nodes.subList(0, pos2 + 1)));
529 nodes.subList(0, pos1).clear();
530 }
531 isRing = false;
532 return new RingSegment(newNodes);
533 }
534
535 public List<Node> getNodes() {
536 return nodes == null ? references.nodes : nodes;
537 }
538
539 public List<Node> getWayNodes() {
540 if (nodes == null)
541 throw new IllegalArgumentException("Won't give you wayNodes: it is a reference");
542 List<Node> wayNodes = new ArrayList<>(nodes);
543 if (isRing) {
544 wayNodes.add(wayNodes.get(0));
545 }
546 return wayNodes;
547 }
548
549 public boolean isReference() {
550 return nodes == null;
551 }
552
553 public boolean isRing() {
554 return isRing;
555 }
556
557 public void makeReference(RingSegment segment) {
558 log(this + " was made a reference to " + segment);
559 this.nodes = null;
560 this.references = segment;
561 }
562
563 public void swapReference() {
564 this.nodes = references.nodes;
565 references.nodes = null;
566 references.references = this;
567 this.references = null;
568 }
569
570 public boolean isWayConstructed() {
571 return isReference() ? references.isWayConstructed() : resultingWay != null;
572 }
573
574 public Way constructWay(Way template) {
575 if (isReference())
576 return references.constructWay(template);
577 if (resultingWay == null) {
578 resultingWay = new Way();
579 resultingWay.setNodes(getWayNodes());
580 }
581 if (template != null && !wasTemplateApplied) {
582 resultingWay.setKeys(template.getKeys());
583 wasTemplateApplied = true;
584 }
585 return resultingWay;
586 }
587
588 public void overrideWay(Way source) {
589 if (isReference()) {
590 references.overrideWay(source);
591 } else {
592 resultingWay = source;
593 wasTemplateApplied = true;
594 }
595 }
596
597 @Override
598 public String toString() {
599 StringBuilder sb = new StringBuilder("RingSegment@");
600 sb.append(this.hashCode()).append('[');
601 if (isReference()) {
602 sb.append("references ").append(references.hashCode());
603 } else if (nodes.isEmpty()) {
604 sb.append("empty");
605 } else {
606 if (isRing) {
607 sb.append("ring:");
608 }
609 sb.append(nodes.get(0).getUniqueId());
610 for (int i = 1; i < nodes.size(); i++) {
611 sb.append(',').append(nodes.get(i).getUniqueId());
612 }
613 }
614 return sb.append(']').toString();
615 }
616 }
617}
Note: See TracBrowser for help on using the repository browser.