[6380] | 1 | // License: GPL. For details, see LICENSE file.
|
---|
[283] | 2 | package org.openstreetmap.josm.actions;
|
---|
| 3 |
|
---|
[2564] | 4 | import static org.openstreetmap.josm.gui.help.HelpUtil.ht;
|
---|
[283] | 5 | import static org.openstreetmap.josm.tools.I18n.tr;
|
---|
[6507] | 6 | import static org.openstreetmap.josm.tools.I18n.trn;
|
---|
[283] | 7 |
|
---|
| 8 | import java.awt.event.ActionEvent;
|
---|
| 9 | import java.awt.event.KeyEvent;
|
---|
[1951] | 10 | import java.util.ArrayList;
|
---|
[283] | 11 | import java.util.Collection;
|
---|
[2210] | 12 | import java.util.Collections;
|
---|
[3445] | 13 | import java.util.LinkedHashMap;
|
---|
| 14 | import java.util.LinkedHashSet;
|
---|
[283] | 15 | import java.util.LinkedList;
|
---|
[343] | 16 | import java.util.List;
|
---|
[6317] | 17 | import java.util.Map;
|
---|
[9371] | 18 | import java.util.Objects;
|
---|
[283] | 19 | import java.util.Set;
|
---|
[8856] | 20 | import java.util.Stack;
|
---|
[283] | 21 |
|
---|
| 22 | import javax.swing.JOptionPane;
|
---|
| 23 |
|
---|
| 24 | import org.openstreetmap.josm.Main;
|
---|
| 25 | import org.openstreetmap.josm.command.ChangeCommand;
|
---|
| 26 | import org.openstreetmap.josm.command.Command;
|
---|
| 27 | import org.openstreetmap.josm.command.DeleteCommand;
|
---|
| 28 | import org.openstreetmap.josm.command.SequenceCommand;
|
---|
[2573] | 29 | import org.openstreetmap.josm.corrector.ReverseWayTagCorrector;
|
---|
[10382] | 30 | import org.openstreetmap.josm.data.osm.DataSet;
|
---|
[582] | 31 | import org.openstreetmap.josm.data.osm.Node;
|
---|
[283] | 32 | import org.openstreetmap.josm.data.osm.OsmPrimitive;
|
---|
[2070] | 33 | import org.openstreetmap.josm.data.osm.TagCollection;
|
---|
[283] | 34 | import org.openstreetmap.josm.data.osm.Way;
|
---|
[3409] | 35 | import org.openstreetmap.josm.data.preferences.BooleanProperty;
|
---|
[1397] | 36 | import org.openstreetmap.josm.gui.ExtendedDialog;
|
---|
[6130] | 37 | import org.openstreetmap.josm.gui.Notification;
|
---|
[2095] | 38 | import org.openstreetmap.josm.gui.conflict.tags.CombinePrimitiveResolverDialog;
|
---|
[5452] | 39 | import org.openstreetmap.josm.gui.util.GuiHelper;
|
---|
[429] | 40 | import org.openstreetmap.josm.tools.Pair;
|
---|
[1084] | 41 | import org.openstreetmap.josm.tools.Shortcut;
|
---|
[8919] | 42 | import org.openstreetmap.josm.tools.UserCancelException;
|
---|
[2573] | 43 |
|
---|
[283] | 44 | /**
|
---|
| 45 | * Combines multiple ways into one.
|
---|
[6156] | 46 | * @since 213
|
---|
[283] | 47 | */
|
---|
[1820] | 48 | public class CombineWayAction extends JosmAction {
|
---|
[283] | 49 |
|
---|
[3409] | 50 | private static final BooleanProperty PROP_REVERSE_WAY = new BooleanProperty("tag-correction.reverse-way", true);
|
---|
| 51 |
|
---|
[6156] | 52 | /**
|
---|
| 53 | * Constructs a new {@code CombineWayAction}.
|
---|
| 54 | */
|
---|
[1169] | 55 | public CombineWayAction() {
|
---|
| 56 | super(tr("Combine Way"), "combineway", tr("Combine several ways into one."),
|
---|
[4982] | 57 | Shortcut.registerShortcut("tools:combineway", tr("Tool: {0}", tr("Combine Way")), KeyEvent.VK_C, Shortcut.DIRECT), true);
|
---|
[2323] | 58 | putValue("help", ht("/Action/CombineWay"));
|
---|
[1169] | 59 | }
|
---|
[283] | 60 |
|
---|
[3504] | 61 | protected static boolean confirmChangeDirectionOfWays() {
|
---|
[2070] | 62 | ExtendedDialog ed = new ExtendedDialog(Main.parent,
|
---|
| 63 | tr("Change directions?"),
|
---|
| 64 | new String[] {tr("Reverse and Combine"), tr("Cancel")});
|
---|
[8061] | 65 | ed.setButtonIcons(new String[] {"wayflip", "cancel"});
|
---|
[2070] | 66 | ed.setContent(tr("The ways can not be combined in their current directions. "
|
---|
| 67 | + "Do you want to reverse some of them?"));
|
---|
[6596] | 68 | ed.toggleEnable("combineway-reverse");
|
---|
[2070] | 69 | ed.showDialog();
|
---|
| 70 | return ed.getValue() == 1;
|
---|
| 71 | }
|
---|
| 72 |
|
---|
[3504] | 73 | protected static void warnCombiningImpossible() {
|
---|
[6130] | 74 | String msg = tr("Could not combine ways<br>"
|
---|
[2070] | 75 | + "(They could not be merged into a single string of nodes)");
|
---|
[6130] | 76 | new Notification(msg)
|
---|
| 77 | .setIcon(JOptionPane.INFORMATION_MESSAGE)
|
---|
| 78 | .show();
|
---|
[2070] | 79 | return;
|
---|
| 80 | }
|
---|
| 81 |
|
---|
[3504] | 82 | protected static Way getTargetWay(Collection<Way> combinedWays) {
|
---|
[2070] | 83 | // init with an arbitrary way
|
---|
| 84 | Way targetWay = combinedWays.iterator().next();
|
---|
| 85 |
|
---|
| 86 | // look for the first way already existing on
|
---|
| 87 | // the server
|
---|
| 88 | for (Way w : combinedWays) {
|
---|
| 89 | targetWay = w;
|
---|
[2273] | 90 | if (!w.isNew()) {
|
---|
[2070] | 91 | break;
|
---|
| 92 | }
|
---|
| 93 | }
|
---|
| 94 | return targetWay;
|
---|
| 95 | }
|
---|
| 96 |
|
---|
[2564] | 97 | /**
|
---|
[8181] | 98 | * Combine multiple ways into one.
|
---|
| 99 | * @param ways the way to combine to one way
|
---|
[8459] | 100 | * @return null if ways cannot be combined. Otherwise returns the combined ways and the commands to combine
|
---|
| 101 | * @throws UserCancelException if the user cancelled a dialog.
|
---|
[3504] | 102 | */
|
---|
| 103 | public static Pair<Way, Command> combineWaysWorker(Collection<Way> ways) throws UserCancelException {
|
---|
| 104 |
|
---|
[2070] | 105 | // prepare and clean the list of ways to combine
|
---|
| 106 | //
|
---|
| 107 | if (ways == null || ways.isEmpty())
|
---|
[3230] | 108 | return null;
|
---|
[2070] | 109 | ways.remove(null); // just in case - remove all null ways from the collection
|
---|
| 110 |
|
---|
[3445] | 111 | // remove duplicates, preserving order
|
---|
[7005] | 112 | ways = new LinkedHashSet<>(ways);
|
---|
[3445] | 113 |
|
---|
[8459] | 114 | // try to build a new way which includes all the combined ways
|
---|
[2070] | 115 | //
|
---|
[8181] | 116 | NodeGraph graph = NodeGraph.createNearlyUndirectedGraphFromNodeWays(ways);
|
---|
[2070] | 117 | List<Node> path = graph.buildSpanningPath();
|
---|
| 118 | if (path == null) {
|
---|
[2573] | 119 | warnCombiningImpossible();
|
---|
[3230] | 120 | return null;
|
---|
[2573] | 121 | }
|
---|
| 122 | // check whether any ways have been reversed in the process
|
---|
| 123 | // and build the collection of tags used by the ways to combine
|
---|
| 124 | //
|
---|
| 125 | TagCollection wayTags = TagCollection.unionOfAllPrimitives(ways);
|
---|
| 126 |
|
---|
[9439] | 127 | final List<Command> reverseWayTagCommands = new LinkedList<>();
|
---|
[7005] | 128 | List<Way> reversedWays = new LinkedList<>();
|
---|
| 129 | List<Way> unreversedWays = new LinkedList<>();
|
---|
[2573] | 130 | for (Way w: ways) {
|
---|
[6156] | 131 | // Treat zero or one-node ways as unreversed as Combine action action is a good way to fix them (see #8971)
|
---|
| 132 | if (w.getNodesCount() < 2 || (path.indexOf(w.getNode(0)) + 1) == path.lastIndexOf(w.getNode(1))) {
|
---|
[2573] | 133 | unreversedWays.add(w);
|
---|
[2070] | 134 | } else {
|
---|
[2573] | 135 | reversedWays.add(w);
|
---|
[2070] | 136 | }
|
---|
| 137 | }
|
---|
[2573] | 138 | // reverse path if all ways have been reversed
|
---|
| 139 | if (unreversedWays.isEmpty()) {
|
---|
| 140 | Collections.reverse(path);
|
---|
| 141 | unreversedWays = reversedWays;
|
---|
| 142 | reversedWays = null;
|
---|
| 143 | }
|
---|
| 144 | if ((reversedWays != null) && !reversedWays.isEmpty()) {
|
---|
[3230] | 145 | if (!confirmChangeDirectionOfWays()) return null;
|
---|
[2573] | 146 | // filter out ways that have no direction-dependent tags
|
---|
| 147 | unreversedWays = ReverseWayTagCorrector.irreversibleWays(unreversedWays);
|
---|
| 148 | reversedWays = ReverseWayTagCorrector.irreversibleWays(reversedWays);
|
---|
| 149 | // reverse path if there are more reversed than unreversed ways with direction-dependent tags
|
---|
| 150 | if (reversedWays.size() > unreversedWays.size()) {
|
---|
| 151 | Collections.reverse(path);
|
---|
| 152 | List<Way> tempWays = unreversedWays;
|
---|
| 153 | unreversedWays = reversedWays;
|
---|
| 154 | reversedWays = tempWays;
|
---|
| 155 | }
|
---|
| 156 | // if there are still reversed ways with direction-dependent tags, reverse their tags
|
---|
[3409] | 157 | if (!reversedWays.isEmpty() && PROP_REVERSE_WAY.get()) {
|
---|
[7005] | 158 | List<Way> unreversedTagWays = new ArrayList<>(ways);
|
---|
[2573] | 159 | unreversedTagWays.removeAll(reversedWays);
|
---|
| 160 | ReverseWayTagCorrector reverseWayTagCorrector = new ReverseWayTagCorrector();
|
---|
[7005] | 161 | List<Way> reversedTagWays = new ArrayList<>(reversedWays.size());
|
---|
[2573] | 162 | for (Way w : reversedWays) {
|
---|
| 163 | Way wnew = new Way(w);
|
---|
| 164 | reversedTagWays.add(wnew);
|
---|
[9439] | 165 | reverseWayTagCommands.addAll(reverseWayTagCorrector.execute(w, wnew));
|
---|
[2573] | 166 | }
|
---|
[9439] | 167 | if (!reverseWayTagCommands.isEmpty()) {
|
---|
| 168 | // commands need to be executed for CombinePrimitiveResolverDialog
|
---|
| 169 | Main.main.undoRedo.add(new SequenceCommand(tr("Reverse Ways"), reverseWayTagCommands));
|
---|
[2573] | 170 | }
|
---|
| 171 | wayTags = TagCollection.unionOfAllPrimitives(reversedTagWays);
|
---|
| 172 | wayTags.add(TagCollection.unionOfAllPrimitives(unreversedTagWays));
|
---|
| 173 | }
|
---|
| 174 | }
|
---|
[2070] | 175 |
|
---|
| 176 | // create the new way and apply the new node list
|
---|
| 177 | //
|
---|
| 178 | Way targetWay = getTargetWay(ways);
|
---|
| 179 | Way modifiedTargetWay = new Way(targetWay);
|
---|
| 180 | modifiedTargetWay.setNodes(path);
|
---|
| 181 |
|
---|
[9439] | 182 | final List<Command> resolution;
|
---|
| 183 | try {
|
---|
| 184 | resolution = CombinePrimitiveResolverDialog.launchIfNecessary(wayTags, ways, Collections.singleton(targetWay));
|
---|
| 185 | } finally {
|
---|
| 186 | if (!reverseWayTagCommands.isEmpty()) {
|
---|
| 187 | // undo reverseWayTagCorrector and merge into SequenceCommand below
|
---|
| 188 | Main.main.undoRedo.undo();
|
---|
| 189 | }
|
---|
| 190 | }
|
---|
[2079] | 191 |
|
---|
[8338] | 192 | List<Command> cmds = new LinkedList<>();
|
---|
| 193 | List<Way> deletedWays = new LinkedList<>(ways);
|
---|
[2070] | 194 | deletedWays.remove(targetWay);
|
---|
| 195 |
|
---|
| 196 | cmds.add(new ChangeCommand(targetWay, modifiedTargetWay));
|
---|
[9439] | 197 | cmds.addAll(reverseWayTagCommands);
|
---|
[5132] | 198 | cmds.addAll(resolution);
|
---|
[3170] | 199 | cmds.add(new DeleteCommand(deletedWays));
|
---|
[9070] | 200 | final Command sequenceCommand = new SequenceCommand(/* for correct i18n of plural forms - see #9110 */
|
---|
[6679] | 201 | trn("Combine {0} way", "Combine {0} ways", ways.size(), ways.size()), cmds);
|
---|
[2070] | 202 |
|
---|
[9070] | 203 | return new Pair<>(targetWay, sequenceCommand);
|
---|
[2070] | 204 | }
|
---|
| 205 |
|
---|
[6084] | 206 | @Override
|
---|
[1169] | 207 | public void actionPerformed(ActionEvent event) {
|
---|
[10382] | 208 | final DataSet ds = getLayerManager().getEditDataSet();
|
---|
| 209 | if (ds == null)
|
---|
[1817] | 210 | return;
|
---|
[10382] | 211 | Collection<OsmPrimitive> selection = ds.getSelected();
|
---|
[2070] | 212 | Set<Way> selectedWays = OsmPrimitive.getFilteredSet(selection, Way.class);
|
---|
[1169] | 213 | if (selectedWays.size() < 2) {
|
---|
[6130] | 214 | new Notification(
|
---|
| 215 | tr("Please select at least two ways to combine."))
|
---|
| 216 | .setIcon(JOptionPane.INFORMATION_MESSAGE)
|
---|
| 217 | .setDuration(Notification.TIME_SHORT)
|
---|
| 218 | .show();
|
---|
[1169] | 219 | return;
|
---|
| 220 | }
|
---|
[3230] | 221 | // combine and update gui
|
---|
[3504] | 222 | Pair<Way, Command> combineResult;
|
---|
| 223 | try {
|
---|
| 224 | combineResult = combineWaysWorker(selectedWays);
|
---|
| 225 | } catch (UserCancelException ex) {
|
---|
[10463] | 226 | Main.trace(ex);
|
---|
[3504] | 227 | return;
|
---|
| 228 | }
|
---|
| 229 |
|
---|
| 230 | if (combineResult == null)
|
---|
| 231 | return;
|
---|
| 232 | final Way selectedWay = combineResult.a;
|
---|
| 233 | Main.main.undoRedo.add(combineResult.b);
|
---|
[8510] | 234 | if (selectedWay != null) {
|
---|
[10601] | 235 | GuiHelper.runInEDT(() -> ds.setSelected(selectedWay));
|
---|
[3230] | 236 | }
|
---|
[2070] | 237 | }
|
---|
[426] | 238 |
|
---|
[2070] | 239 | @Override
|
---|
| 240 | protected void updateEnabledState() {
|
---|
[10548] | 241 | updateEnabledStateOnCurrentSelection();
|
---|
[2256] | 242 | }
|
---|
| 243 |
|
---|
| 244 | @Override
|
---|
| 245 | protected void updateEnabledState(Collection<? extends OsmPrimitive> selection) {
|
---|
[2070] | 246 | int numWays = 0;
|
---|
[8513] | 247 | for (OsmPrimitive osm : selection) {
|
---|
[2070] | 248 | if (osm instanceof Way) {
|
---|
| 249 | numWays++;
|
---|
| 250 | }
|
---|
[8513] | 251 | }
|
---|
[2070] | 252 | setEnabled(numWays >= 2);
|
---|
| 253 | }
|
---|
[426] | 254 |
|
---|
[6156] | 255 | /**
|
---|
| 256 | * A pair of nodes.
|
---|
| 257 | */
|
---|
[6889] | 258 | public static class NodePair {
|
---|
[6156] | 259 | private final Node a;
|
---|
| 260 | private final Node b;
|
---|
[7509] | 261 |
|
---|
[6156] | 262 | /**
|
---|
| 263 | * Constructs a new {@code NodePair}.
|
---|
| 264 | * @param a The first node
|
---|
| 265 | * @param b The second node
|
---|
| 266 | */
|
---|
[2070] | 267 | public NodePair(Node a, Node b) {
|
---|
[6156] | 268 | this.a = a;
|
---|
[2070] | 269 | this.b = b;
|
---|
| 270 | }
|
---|
| 271 |
|
---|
[6156] | 272 | /**
|
---|
| 273 | * Constructs a new {@code NodePair}.
|
---|
| 274 | * @param pair An existing {@code Pair} of nodes
|
---|
| 275 | */
|
---|
[8510] | 276 | public NodePair(Pair<Node, Node> pair) {
|
---|
[6156] | 277 | this(pair.a, pair.b);
|
---|
[2070] | 278 | }
|
---|
| 279 |
|
---|
[6156] | 280 | /**
|
---|
| 281 | * Replies the first node.
|
---|
| 282 | * @return The first node
|
---|
| 283 | */
|
---|
[2070] | 284 | public Node getA() {
|
---|
| 285 | return a;
|
---|
| 286 | }
|
---|
| 287 |
|
---|
[6156] | 288 | /**
|
---|
| 289 | * Replies the second node
|
---|
| 290 | * @return The second node
|
---|
| 291 | */
|
---|
[2070] | 292 | public Node getB() {
|
---|
| 293 | return b;
|
---|
| 294 | }
|
---|
| 295 |
|
---|
| 296 | public boolean isSuccessorOf(NodePair other) {
|
---|
[10662] | 297 | return other.getB() == a;
|
---|
[2070] | 298 | }
|
---|
| 299 |
|
---|
| 300 | public boolean isPredecessorOf(NodePair other) {
|
---|
[10662] | 301 | return b == other.getA();
|
---|
[2070] | 302 | }
|
---|
| 303 |
|
---|
| 304 | public NodePair swap() {
|
---|
[8510] | 305 | return new NodePair(b, a);
|
---|
[2070] | 306 | }
|
---|
| 307 |
|
---|
| 308 | @Override
|
---|
| 309 | public String toString() {
|
---|
| 310 | return new StringBuilder()
|
---|
[8390] | 311 | .append('[')
|
---|
[2070] | 312 | .append(a.getId())
|
---|
[8390] | 313 | .append(',')
|
---|
[2070] | 314 | .append(b.getId())
|
---|
[8390] | 315 | .append(']')
|
---|
[2070] | 316 | .toString();
|
---|
| 317 | }
|
---|
| 318 |
|
---|
[6156] | 319 | /**
|
---|
| 320 | * Determines if this pair contains the given node.
|
---|
| 321 | * @param n The node to look for
|
---|
| 322 | * @return {@code true} if {@code n} is in the pair, {@code false} otherwise
|
---|
| 323 | */
|
---|
[2070] | 324 | public boolean contains(Node n) {
|
---|
[10662] | 325 | return a == n || b == n;
|
---|
[2070] | 326 | }
|
---|
| 327 |
|
---|
| 328 | @Override
|
---|
| 329 | public int hashCode() {
|
---|
[9371] | 330 | return Objects.hash(a, b);
|
---|
[2070] | 331 | }
|
---|
[7509] | 332 |
|
---|
[2070] | 333 | @Override
|
---|
| 334 | public boolean equals(Object obj) {
|
---|
[9371] | 335 | if (this == obj) return true;
|
---|
| 336 | if (obj == null || getClass() != obj.getClass()) return false;
|
---|
| 337 | NodePair nodePair = (NodePair) obj;
|
---|
| 338 | return Objects.equals(a, nodePair.a) &&
|
---|
[10659] | 339 | Objects.equals(b, nodePair.b);
|
---|
[2070] | 340 | }
|
---|
| 341 | }
|
---|
| 342 |
|
---|
[6889] | 343 | public static class NodeGraph {
|
---|
| 344 | public static List<NodePair> buildNodePairs(Way way, boolean directed) {
|
---|
[7005] | 345 | List<NodePair> pairs = new ArrayList<>();
|
---|
[8510] | 346 | for (Pair<Node, Node> pair: way.getNodePairs(false /* don't sort */)) {
|
---|
[2070] | 347 | pairs.add(new NodePair(pair));
|
---|
| 348 | if (!directed) {
|
---|
| 349 | pairs.add(new NodePair(pair).swap());
|
---|
[1814] | 350 | }
|
---|
[1169] | 351 | }
|
---|
[2070] | 352 | return pairs;
|
---|
[1169] | 353 | }
|
---|
[343] | 354 |
|
---|
[6889] | 355 | public static List<NodePair> buildNodePairs(List<Way> ways, boolean directed) {
|
---|
[7005] | 356 | List<NodePair> pairs = new ArrayList<>();
|
---|
[2070] | 357 | for (Way w: ways) {
|
---|
| 358 | pairs.addAll(buildNodePairs(w, directed));
|
---|
| 359 | }
|
---|
| 360 | return pairs;
|
---|
| 361 | }
|
---|
[2032] | 362 |
|
---|
[6889] | 363 | public static List<NodePair> eliminateDuplicateNodePairs(List<NodePair> pairs) {
|
---|
[7005] | 364 | List<NodePair> cleaned = new ArrayList<>();
|
---|
[8510] | 365 | for (NodePair p: pairs) {
|
---|
[2070] | 366 | if (!cleaned.contains(p) && !cleaned.contains(p.swap())) {
|
---|
| 367 | cleaned.add(p);
|
---|
| 368 | }
|
---|
[1169] | 369 | }
|
---|
[2070] | 370 | return cleaned;
|
---|
[1169] | 371 | }
|
---|
[343] | 372 |
|
---|
[6889] | 373 | public static NodeGraph createDirectedGraphFromNodePairs(List<NodePair> pairs) {
|
---|
[2070] | 374 | NodeGraph graph = new NodeGraph();
|
---|
| 375 | for (NodePair pair: pairs) {
|
---|
| 376 | graph.add(pair);
|
---|
| 377 | }
|
---|
| 378 | return graph;
|
---|
| 379 | }
|
---|
[699] | 380 |
|
---|
[6889] | 381 | public static NodeGraph createDirectedGraphFromWays(Collection<Way> ways) {
|
---|
[2070] | 382 | NodeGraph graph = new NodeGraph();
|
---|
| 383 | for (Way w: ways) {
|
---|
| 384 | graph.add(buildNodePairs(w, true /* directed */));
|
---|
[1814] | 385 | }
|
---|
[2070] | 386 | return graph;
|
---|
[1169] | 387 | }
|
---|
[699] | 388 |
|
---|
[8181] | 389 | /**
|
---|
[8440] | 390 | * Create an undirected graph from the given node pairs.
|
---|
| 391 | * @param pairs Node pairs to build the graph from
|
---|
[8181] | 392 | * @return node graph structure
|
---|
| 393 | */
|
---|
[6889] | 394 | public static NodeGraph createUndirectedGraphFromNodeList(List<NodePair> pairs) {
|
---|
[2070] | 395 | NodeGraph graph = new NodeGraph();
|
---|
| 396 | for (NodePair pair: pairs) {
|
---|
| 397 | graph.add(pair);
|
---|
| 398 | graph.add(pair.swap());
|
---|
| 399 | }
|
---|
| 400 | return graph;
|
---|
| 401 | }
|
---|
[426] | 402 |
|
---|
[8181] | 403 | /**
|
---|
| 404 | * Create an undirected graph from the given ways, but prevent reversing of all
|
---|
| 405 | * non-new ways by fix one direction.
|
---|
| 406 | * @param ways Ways to build the graph from
|
---|
| 407 | * @return node graph structure
|
---|
| 408 | * @since 8181
|
---|
| 409 | */
|
---|
[6317] | 410 | public static NodeGraph createUndirectedGraphFromNodeWays(Collection<Way> ways) {
|
---|
[2070] | 411 | NodeGraph graph = new NodeGraph();
|
---|
| 412 | for (Way w: ways) {
|
---|
| 413 | graph.add(buildNodePairs(w, false /* undirected */));
|
---|
[1530] | 414 | }
|
---|
[2070] | 415 | return graph;
|
---|
[1169] | 416 | }
|
---|
[426] | 417 |
|
---|
[8181] | 418 | public static NodeGraph createNearlyUndirectedGraphFromNodeWays(Collection<Way> ways) {
|
---|
| 419 | boolean dir = true;
|
---|
| 420 | NodeGraph graph = new NodeGraph();
|
---|
| 421 | for (Way w: ways) {
|
---|
[8510] | 422 | if (!w.isNew()) {
|
---|
[8181] | 423 | /* let the first non-new way give the direction (see #5880) */
|
---|
| 424 | graph.add(buildNodePairs(w, dir));
|
---|
| 425 | dir = false;
|
---|
| 426 | } else {
|
---|
| 427 | graph.add(buildNodePairs(w, false /* undirected */));
|
---|
| 428 | }
|
---|
| 429 | }
|
---|
| 430 | return graph;
|
---|
| 431 | }
|
---|
| 432 |
|
---|
[9067] | 433 | private final Set<NodePair> edges;
|
---|
[8840] | 434 | private int numUndirectedEges;
|
---|
[10250] | 435 | private final Map<Node, List<NodePair>> successors = new LinkedHashMap<>();
|
---|
| 436 | private final Map<Node, List<NodePair>> predecessors = new LinkedHashMap<>();
|
---|
[2032] | 437 |
|
---|
[2210] | 438 | protected void rememberSuccessor(NodePair pair) {
|
---|
| 439 | if (successors.containsKey(pair.getA())) {
|
---|
| 440 | if (!successors.get(pair.getA()).contains(pair)) {
|
---|
| 441 | successors.get(pair.getA()).add(pair);
|
---|
| 442 | }
|
---|
| 443 | } else {
|
---|
[7005] | 444 | List<NodePair> l = new ArrayList<>();
|
---|
[2210] | 445 | l.add(pair);
|
---|
| 446 | successors.put(pair.getA(), l);
|
---|
| 447 | }
|
---|
| 448 | }
|
---|
| 449 |
|
---|
| 450 | protected void rememberPredecessors(NodePair pair) {
|
---|
| 451 | if (predecessors.containsKey(pair.getB())) {
|
---|
| 452 | if (!predecessors.get(pair.getB()).contains(pair)) {
|
---|
| 453 | predecessors.get(pair.getB()).add(pair);
|
---|
| 454 | }
|
---|
| 455 | } else {
|
---|
[7005] | 456 | List<NodePair> l = new ArrayList<>();
|
---|
[2210] | 457 | l.add(pair);
|
---|
| 458 | predecessors.put(pair.getB(), l);
|
---|
| 459 | }
|
---|
| 460 | }
|
---|
| 461 |
|
---|
| 462 | protected boolean isTerminalNode(Node n) {
|
---|
| 463 | if (successors.get(n) == null) return false;
|
---|
| 464 | if (successors.get(n).size() != 1) return false;
|
---|
| 465 | if (predecessors.get(n) == null) return true;
|
---|
| 466 | if (predecessors.get(n).size() == 1) {
|
---|
[8846] | 467 | NodePair p1 = successors.get(n).get(0);
|
---|
| 468 | NodePair p2 = predecessors.get(n).get(0);
|
---|
[2210] | 469 | return p1.equals(p2.swap());
|
---|
| 470 | }
|
---|
| 471 | return false;
|
---|
| 472 | }
|
---|
| 473 |
|
---|
| 474 | protected void prepare() {
|
---|
[7005] | 475 | Set<NodePair> undirectedEdges = new LinkedHashSet<>();
|
---|
[10250] | 476 | successors.clear();
|
---|
| 477 | predecessors.clear();
|
---|
[2210] | 478 |
|
---|
[2070] | 479 | for (NodePair pair: edges) {
|
---|
[8443] | 480 | if (!undirectedEdges.contains(pair) && !undirectedEdges.contains(pair.swap())) {
|
---|
[2070] | 481 | undirectedEdges.add(pair);
|
---|
| 482 | }
|
---|
[2210] | 483 | rememberSuccessor(pair);
|
---|
| 484 | rememberPredecessors(pair);
|
---|
[2070] | 485 | }
|
---|
| 486 | numUndirectedEges = undirectedEdges.size();
|
---|
| 487 | }
|
---|
[1621] | 488 |
|
---|
[6156] | 489 | /**
|
---|
| 490 | * Constructs a new {@code NodeGraph}.
|
---|
| 491 | */
|
---|
[2070] | 492 | public NodeGraph() {
|
---|
[7005] | 493 | edges = new LinkedHashSet<>();
|
---|
[2070] | 494 | }
|
---|
[2032] | 495 |
|
---|
[2070] | 496 | public void add(NodePair pair) {
|
---|
| 497 | if (!edges.contains(pair)) {
|
---|
| 498 | edges.add(pair);
|
---|
[1814] | 499 | }
|
---|
[1169] | 500 | }
|
---|
[283] | 501 |
|
---|
[2070] | 502 | public void add(List<NodePair> pairs) {
|
---|
| 503 | for (NodePair pair: pairs) {
|
---|
| 504 | add(pair);
|
---|
| 505 | }
|
---|
| 506 | }
|
---|
[426] | 507 |
|
---|
[2210] | 508 | protected Set<Node> getTerminalNodes() {
|
---|
[7005] | 509 | Set<Node> ret = new LinkedHashSet<>();
|
---|
[2210] | 510 | for (Node n: getNodes()) {
|
---|
| 511 | if (isTerminalNode(n)) {
|
---|
| 512 | ret.add(n);
|
---|
| 513 | }
|
---|
| 514 | }
|
---|
| 515 | return ret;
|
---|
| 516 | }
|
---|
| 517 |
|
---|
[2070] | 518 | protected List<NodePair> getOutboundPairs(NodePair pair) {
|
---|
[2210] | 519 | return getOutboundPairs(pair.getB());
|
---|
[2070] | 520 | }
|
---|
| 521 |
|
---|
| 522 | protected List<NodePair> getOutboundPairs(Node node) {
|
---|
[2210] | 523 | List<NodePair> l = successors.get(node);
|
---|
[2356] | 524 | if (l == null)
|
---|
| 525 | return Collections.emptyList();
|
---|
| 526 | return l;
|
---|
[1169] | 527 | }
|
---|
[283] | 528 |
|
---|
[2070] | 529 | protected Set<Node> getNodes() {
|
---|
[7005] | 530 | Set<Node> nodes = new LinkedHashSet<>(2 * edges.size());
|
---|
[2070] | 531 | for (NodePair pair: edges) {
|
---|
| 532 | nodes.add(pair.getA());
|
---|
| 533 | nodes.add(pair.getB());
|
---|
| 534 | }
|
---|
| 535 | return nodes;
|
---|
| 536 | }
|
---|
[426] | 537 |
|
---|
[8856] | 538 | protected boolean isSpanningWay(Stack<NodePair> way) {
|
---|
[2070] | 539 | return numUndirectedEges == way.size();
|
---|
[1814] | 540 | }
|
---|
[343] | 541 |
|
---|
[8856] | 542 | protected List<Node> buildPathFromNodePairs(Stack<NodePair> path) {
|
---|
[8338] | 543 | List<Node> ret = new LinkedList<>();
|
---|
[2070] | 544 | for (NodePair pair: path) {
|
---|
| 545 | ret.add(pair.getA());
|
---|
[1169] | 546 | }
|
---|
[2070] | 547 | ret.add(path.peek().getB());
|
---|
| 548 | return ret;
|
---|
[1169] | 549 | }
|
---|
[343] | 550 |
|
---|
[2210] | 551 | /**
|
---|
| 552 | * Tries to find a spanning path starting from node <code>startNode</code>.
|
---|
[2512] | 553 | *
|
---|
[2210] | 554 | * Traverses the path in depth-first order.
|
---|
[2512] | 555 | *
|
---|
[2210] | 556 | * @param startNode the start node
|
---|
| 557 | * @return the spanning path; null, if no path is found
|
---|
| 558 | */
|
---|
[2070] | 559 | protected List<Node> buildSpanningPath(Node startNode) {
|
---|
| 560 | if (startNode == null)
|
---|
| 561 | return null;
|
---|
[8856] | 562 | Stack<NodePair> path = new Stack<>();
|
---|
[10378] | 563 | Stack<NodePair> nextPairs = new Stack<>();
|
---|
[2070] | 564 | nextPairs.addAll(getOutboundPairs(startNode));
|
---|
[8510] | 565 | while (!nextPairs.isEmpty()) {
|
---|
| 566 | NodePair cur = nextPairs.pop();
|
---|
[8443] | 567 | if (!path.contains(cur) && !path.contains(cur.swap())) {
|
---|
[8510] | 568 | while (!path.isEmpty() && !path.peek().isPredecessorOf(cur)) {
|
---|
[2210] | 569 | path.pop();
|
---|
| 570 | }
|
---|
| 571 | path.push(cur);
|
---|
| 572 | if (isSpanningWay(path)) return buildPathFromNodePairs(path);
|
---|
| 573 | nextPairs.addAll(getOutboundPairs(path.peek()));
|
---|
| 574 | }
|
---|
[2070] | 575 | }
|
---|
| 576 | return null;
|
---|
[1817] | 577 | }
|
---|
| 578 |
|
---|
[2210] | 579 | /**
|
---|
| 580 | * Tries to find a path through the graph which visits each edge (i.e.
|
---|
[8181] | 581 | * the segment of a way) exactly once.
|
---|
[2512] | 582 | *
|
---|
[2210] | 583 | * @return the path; null, if no path was found
|
---|
| 584 | */
|
---|
[2070] | 585 | public List<Node> buildSpanningPath() {
|
---|
[2210] | 586 | prepare();
|
---|
| 587 | // try to find a path from each "terminal node", i.e. from a
|
---|
| 588 | // node which is connected by exactly one undirected edges (or
|
---|
| 589 | // two directed edges in opposite direction) to the graph. A
|
---|
| 590 | // graph built up from way segments is likely to include such
|
---|
| 591 | // nodes, unless all ways are closed.
|
---|
[8459] | 592 | // In the worst case this loops over all nodes which is very slow for large ways.
|
---|
[2210] | 593 | //
|
---|
| 594 | Set<Node> nodes = getTerminalNodes();
|
---|
| 595 | nodes = nodes.isEmpty() ? getNodes() : nodes;
|
---|
| 596 | for (Node n: nodes) {
|
---|
[2070] | 597 | List<Node> path = buildSpanningPath(n);
|
---|
| 598 | if (path != null)
|
---|
| 599 | return path;
|
---|
[1169] | 600 | }
|
---|
[2070] | 601 | return null;
|
---|
| 602 | }
|
---|
[1169] | 603 | }
|
---|
[283] | 604 | }
|
---|