Ignore:
Timestamp:
2009-09-06T23:07:33+02:00 (15 years ago)
Author:
Gubaer
Message:

new: rewrite of CombineWay action
new: conflict resolution dialog for CombineWay, including conflicts for different relation memberships
cleanup: cleanup in OsmReader, reduces memory footprint and reduces parsing time
cleanup: made most of the public fields in OsmPrimitive @deprecated, added accessors and changed the code
cleanup: replaced usages of @deprecated constructors for ExtendedDialog
fixed #3208: Combine ways brokes relation order

WARNING: this changeset touches a lot of code all over the code base. "latest" might become slightly unstable in the next days. Also experience incompatibility issues with plugins in the next few days.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/src/org/openstreetmap/josm/actions/CombineWayAction.java

    r2032 r2070  
    44import static org.openstreetmap.josm.tools.I18n.tr;
    55
    6 import java.awt.GridBagLayout;
    76import java.awt.event.ActionEvent;
    87import java.awt.event.KeyEvent;
    … …  
    1312import java.util.LinkedList;
    1413import java.util.List;
    15 import java.util.ListIterator;
    1614import java.util.Map;
    1715import java.util.Set;
    18 import java.util.TreeMap;
    19 import java.util.TreeSet;
    20 import java.util.Map.Entry;
    21 
    22 import javax.swing.Box;
    23 import javax.swing.JComboBox;
    24 import javax.swing.JLabel;
     16import java.util.Stack;
     17
    2518import javax.swing.JOptionPane;
    26 import javax.swing.JPanel;
     19import javax.swing.SwingUtilities;
    2720
    2821import org.openstreetmap.josm.Main;
    … …  
    3124import org.openstreetmap.josm.command.DeleteCommand;
    3225import org.openstreetmap.josm.command.SequenceCommand;
     26import org.openstreetmap.josm.data.osm.DataSet;
    3327import org.openstreetmap.josm.data.osm.Node;
    3428import org.openstreetmap.josm.data.osm.OsmPrimitive;
    3529import org.openstreetmap.josm.data.osm.Relation;
    3630import org.openstreetmap.josm.data.osm.RelationMember;
    37 import org.openstreetmap.josm.data.osm.TigerUtils;
     31import org.openstreetmap.josm.data.osm.Tag;
     32import org.openstreetmap.josm.data.osm.TagCollection;
    3833import org.openstreetmap.josm.data.osm.Way;
    3934import org.openstreetmap.josm.gui.ExtendedDialog;
    40 import org.openstreetmap.josm.tools.GBC;
     35import org.openstreetmap.josm.gui.conflict.tags.CombineWaysConflictResolverDialog;
    4136import org.openstreetmap.josm.tools.Pair;
    4237import org.openstreetmap.josm.tools.Shortcut;
    … …  
    4540 * Combines multiple ways into one.
    4641 *
    47  * @author Imi
    4842 */
    4943public class CombineWayAction extends JosmAction {
    … …  
    5448    }
    5549
    56     @SuppressWarnings("unchecked")
     50    protected Set<OsmPrimitive> intersect(Set<? extends OsmPrimitive> s1, Set<? extends OsmPrimitive> s2) {
     51        HashSet<OsmPrimitive> ret = new HashSet<OsmPrimitive>(s1);
     52        ret.retainAll(s2);
     53        return ret;
     54    }
     55
     56    protected boolean confirmCombiningWithConflictsInRelationMemberships() {
     57        ExtendedDialog ed = new ExtendedDialog(Main.parent,
     58                tr("Combine ways with different memberships?"),
     59                new String[] {tr("Combine Anyway"), tr("Cancel")});
     60        ed.setButtonIcons(new String[] {"combineway.png", "cancel.png"});
     61        ed.setContent(tr("The selected ways have differing relation memberships.  "
     62                + "Do you still want to combine them?"));
     63        ed.showDialog();
     64
     65        return ed.getValue() == 1;
     66    }
     67
     68    protected boolean confirmChangeDirectionOfWays() {
     69        ExtendedDialog ed = new ExtendedDialog(Main.parent,
     70                tr("Change directions?"),
     71                new String[] {tr("Reverse and Combine"), tr("Cancel")});
     72        ed.setButtonIcons(new String[] {"wayflip.png", "cancel.png"});
     73        ed.setContent(tr("The ways can not be combined in their current directions.  "
     74                + "Do you want to reverse some of them?"));
     75        ed.showDialog();
     76        return ed.getValue() == 1;
     77    }
     78
     79    protected void warnCombiningImpossible() {
     80        String msg = tr("Could not combine ways "
     81                + "(They could not be merged into a single string of nodes)");
     82        JOptionPane.showMessageDialog(
     83                Main.parent,
     84                msg,  //FIXME: not sure whether this fits in a dialog
     85                tr("Information"),
     86                JOptionPane.INFORMATION_MESSAGE
     87        );
     88        return;
     89    }
     90
     91    protected Way getTargetWay(Collection<Way> combinedWays) {
     92        // init with an arbitrary way
     93        Way targetWay = combinedWays.iterator().next();
     94
     95        // look for the first way already existing on
     96        // the server
     97        for (Way w : combinedWays) {
     98            targetWay = w;
     99            if (w.getId() != 0) {
     100                break;
     101            }
     102        }
     103        return targetWay;
     104    }
     105
     106    protected void completeTagCollectionWithMissingTags(TagCollection tc, Collection<Way> combinedWays) {
     107        for (String key: tc.getKeys()) {
     108            // make sure the empty value is in the tag set such that we can delete the tag
     109            // in the conflict dialog if necessary
     110            //
     111            tc.add(new Tag(key,""));
     112            for (Way w: combinedWays) {
     113                if (w.get(key) == null) {
     114                    tc.add(new Tag(key)); // add a tag with key and empty value
     115                }
     116            }
     117        }
     118        // remove irrelevant tags
     119        //
     120        tc.removeByKey("created_by");
     121    }
     122
     123    public void combineWays(Collection<Way> ways) {
     124
     125        // prepare and clean the list of ways to combine
     126        //
     127        if (ways == null || ways.isEmpty())
     128            return;
     129        ways.remove(null); // just in case -  remove all null ways from the collection
     130        ways = new HashSet<Way>(ways); // remove duplicates
     131
     132        // build the list of relations referring to the ways to combine
     133        //
     134        WayReferringRelations referringRelations = new WayReferringRelations(ways);
     135        referringRelations.build(getCurrentDataSet());
     136
     137        // build the collection of tags used by the ways to combine
     138        //
     139        TagCollection wayTags = TagCollection.unionOfAllPrimitives(ways);
     140        completeTagCollectionWithMissingTags(wayTags, ways);
     141
     142        // try to build a new way out of the combination of ways
     143        // which are combined
     144        //
     145        NodeGraph graph = NodeGraph.createDirectedGraphFromWays(ways);
     146        List<Node> path = graph.buildSpanningPath();
     147        if (path == null) {
     148            graph = NodeGraph.createUndirectedGraphFromNodeWays(ways);
     149            path = graph.buildSpanningPath();
     150            if (path != null) {
     151                if (!confirmChangeDirectionOfWays())
     152                    return;
     153            } else {
     154                warnCombiningImpossible();
     155                return;
     156            }
     157        }
     158
     159        // create the new way and apply the new node list
     160        //
     161        Way targetWay = getTargetWay(ways);
     162        Way modifiedTargetWay = new Way(targetWay);
     163        modifiedTargetWay.setNodes(path);
     164
     165        CombineWaysConflictResolverDialog dialog = CombineWaysConflictResolverDialog.getInstance();
     166        dialog.getTagConflictResolverModel().populate(wayTags);
     167        dialog.setTargetWay(targetWay);
     168        dialog.getRelationMemberConflictResolverModel().populate(
     169                referringRelations.getRelations(),
     170                referringRelations.getWays()
     171        );
     172        dialog.prepareDefaultDecisions();
     173
     174        // resolve tag conflicts if necessary
     175        //
     176        if (!wayTags.isApplicableToPrimitive() || !referringRelations.getRelations().isEmpty()) {
     177            dialog.setVisible(true);
     178            if (dialog.isCancelled())
     179                return;
     180        }
     181
     182
     183
     184        LinkedList<Command> cmds = new LinkedList<Command>();
     185        LinkedList<Way> deletedWays = new LinkedList<Way>(ways);
     186        deletedWays.remove(targetWay);
     187
     188        cmds.add(new DeleteCommand(deletedWays));
     189        cmds.add(new ChangeCommand(targetWay, modifiedTargetWay));
     190        cmds.addAll(dialog.buildResolutionCommands(targetWay));
     191        final SequenceCommand sequenceCommand = new SequenceCommand(tr("Combine {0} ways", ways.size()), cmds);
     192
     193        // update gui
     194        final Way selectedWay = targetWay;
     195        Runnable guiTask = new Runnable() {
     196            public void run() {
     197                Main.main.undoRedo.add(sequenceCommand);
     198                getCurrentDataSet().setSelected(selectedWay);
     199            }
     200        };
     201        if (SwingUtilities.isEventDispatchThread()) {
     202            guiTask.run();
     203        } else {
     204            SwingUtilities.invokeLater(guiTask);
     205        }
     206    }
     207
     208
    57209    public void actionPerformed(ActionEvent event) {
    58210        if (getCurrentDataSet() == null)
    59211            return;
    60212        Collection<OsmPrimitive> selection = getCurrentDataSet().getSelected();
    61         LinkedList<Way> selectedWays = new LinkedList<Way>();
    62 
    63         for (OsmPrimitive osm : selection)
    64             if (osm instanceof Way) {
    65                 selectedWays.add((Way)osm);
    66             }
    67 
     213        Set<Way> selectedWays = OsmPrimitive.getFilteredSet(selection, Way.class);
    68214        if (selectedWays.size() < 2) {
    69215            JOptionPane.showMessageDialog(
    … …  
    75221            return;
    76222        }
    77 
    78         // Check whether all ways have identical relationship membership. More
    79         // specifically: If one of the selected ways is a member of relation X
    80         // in role Y, then all selected ways must be members of X in role Y.
    81 
    82         // FIXME: In a later revision, we should display some sort of conflict
    83         // dialog like we do for tags, to let the user choose which relations
    84         // should be kept.
    85 
    86         // Step 1, iterate over all relations and figure out which of our
    87         // selected ways are members of a relation.
    88         HashMap<Pair<Relation,String>, HashSet<Way>> backlinks =
    89             new HashMap<Pair<Relation,String>, HashSet<Way>>();
    90         HashSet<Relation> relationsUsingWays = new HashSet<Relation>();
    91         for (Relation r : getCurrentDataSet().relations) {
    92             if (r.isDeleted() || r.incomplete) {
    93                 continue;
    94             }
    95             for (RelationMember rm : r.getMembers()) {
    96                 if (rm.isWay()) {
    97                     for(Way w : selectedWays) {
    98                         if (rm.getMember() == w) {
    99                             Pair<Relation,String> pair = new Pair<Relation,String>(r, rm.getRole());
    100                             HashSet<Way> waylinks = new HashSet<Way>();
    101                             if (backlinks.containsKey(pair)) {
    102                                 waylinks = backlinks.get(pair);
    103                             } else {
    104                                 waylinks = new HashSet<Way>();
    105                                 backlinks.put(pair, waylinks);
    106                             }
    107                             waylinks.add(w);
    108 
    109                             // this is just a cache for later use
    110                             relationsUsingWays.add(r);
    111                         }
    112                     }
    113                 }
    114             }
    115         }
    116 
    117         // Complain to the user if the ways don't have equal memberships.
    118         for (HashSet<Way> waylinks : backlinks.values()) {
    119             if (!waylinks.containsAll(selectedWays)) {
    120 
    121                 ExtendedDialog ed = new ExtendedDialog(Main.parent,
    122                         tr("Combine ways with different memberships?"),
    123                         new String[] {tr("Combine Anyway"), tr("Cancel")});
    124                 ed.setButtonIcons(new String[] {"combineway.png", "cancel.png"});
    125                 ed.setContent(tr("The selected ways have differing relation memberships.  "
    126                         + "Do you still want to combine them?"));
    127                 ed.showDialog();
    128 
    129                 if (ed.getValue() == 1) {
    130                     break;
    131                 }
    132 
    133                 return;
    134             }
    135         }
    136 
    137         // collect properties for later conflict resolving
    138         Map<String, Set<String>> props = new TreeMap<String, Set<String>>();
    139         for (Way w : selectedWays) {
    140             for (Entry<String,String> e : w.entrySet()) {
    141                 if (!props.containsKey(e.getKey())) {
    142                     props.put(e.getKey(), new TreeSet<String>());
    143                 }
    144                 props.get(e.getKey()).add(e.getValue());
    145             }
    146         }
    147 
    148         List<Node> nodeList = null;
    149         Object firstTry = actuallyCombineWays(selectedWays, false);
    150         if (firstTry instanceof List<?>) {
    151             nodeList = (List<Node>) firstTry;
    152         } else {
    153             Object secondTry = actuallyCombineWays(selectedWays, true);
    154             if (secondTry instanceof List<?>) {
    155                 ExtendedDialog ed = new ExtendedDialog(Main.parent,
    156                         tr("Change directions?"),
    157                         new String[] {tr("Reverse and Combine"), tr("Cancel")});
    158                 ed.setButtonIcons(new String[] {"wayflip.png", "cancel.png"});
    159                 ed.setContent(tr("The ways can not be combined in their current directions.  "
    160                         + "Do you want to reverse some of them?"));
    161                 ed.showDialog();
    162                 if (ed.getValue() != 1) return;
    163 
    164                 nodeList = (List<Node>) secondTry;
    165             } else {
    166                 JOptionPane.showMessageDialog(
    167                         Main.parent,
    168                         secondTry, // FIXME: not sure whether this fits in a dialog
    169                         tr("Information"),
    170                         JOptionPane.INFORMATION_MESSAGE
    171                 );
    172                 return;
    173             }
    174         }
    175 
    176         // Find the most appropriate way to modify.
    177 
    178         // Eventually this might want to be the way with the longest
    179         // history or the longest selected way but for now just attempt
    180         // to reuse an existing id.
    181         Way modifyWay = selectedWays.peek();
    182         for (Way w : selectedWays) {
    183             modifyWay = w;
    184             if (w.getId() != 0) {
    185                 break;
    186             }
    187         }
    188         Way newWay = new Way(modifyWay);
    189 
    190         newWay.setNodes(nodeList);
    191 
    192         // display conflict dialog
    193         Map<String, JComboBox> components = new HashMap<String, JComboBox>();
    194         JPanel p = new JPanel(new GridBagLayout());
    195         for (Entry<String, Set<String>> e : props.entrySet()) {
    196             if (TigerUtils.isTigerTag(e.getKey())) {
    197                 String combined = TigerUtils.combineTags(e.getKey(), e.getValue());
    198                 newWay.put(e.getKey(), combined);
    199             } else if (e.getValue().size() > 1) {
    200                 JComboBox c = new JComboBox(e.getValue().toArray());
    201                 c.setEditable(true);
    202                 p.add(new JLabel(e.getKey()), GBC.std());
    203                 p.add(Box.createHorizontalStrut(10), GBC.std());
    204                 p.add(c, GBC.eol());
    205                 components.put(e.getKey(), c);
    206             } else {
    207                 newWay.put(e.getKey(), e.getValue().iterator().next());
    208             }
    209         }
    210 
    211         if (!components.isEmpty()) {
    212 
    213             ExtendedDialog ed = new ExtendedDialog(Main.parent,
    214                     tr("Enter values for all conflicts."),
    215                     new String[] {tr("Solve Conflicts"), tr("Cancel")});
    216             ed.setButtonIcons(new String[] {"dialogs/conflict.png", "cancel.png"});
    217             ed.setContent(p);
    218             ed.showDialog();
    219 
    220             if (ed.getValue() != 1) return;
    221 
    222             for (Entry<String, JComboBox> e : components.entrySet()) {
    223                 newWay.put(e.getKey(), e.getValue().getEditor().getItem().toString());
    224             }
    225         }
    226 
    227         LinkedList<Command> cmds = new LinkedList<Command>();
    228         LinkedList<Way> deletedWays = new LinkedList<Way>(selectedWays);
    229         deletedWays.remove(modifyWay);
    230         cmds.add(new DeleteCommand(deletedWays));
    231         cmds.add(new ChangeCommand(modifyWay, newWay));
    232 
    233         // modify all relations containing the now-deleted ways
    234         for (Relation r : relationsUsingWays) {
    235             List<RelationMember> newMembers = new ArrayList<RelationMember>();
    236             HashSet<String> rolesToReAdd = new HashSet<String>();
    237             for (RelationMember rm : r.getMembers()) {
    238                 // Don't copy the member if it to one of our ways, just keep a
    239                 // note to re-add it later on.
    240                 if (selectedWays.contains(rm.getMember())) {
    241                     rolesToReAdd.add(rm.getRole());
    242                 } else {
    243                     newMembers.add(rm);
    244                 }
    245             }
    246             for (String role : rolesToReAdd) {
    247                 newMembers.add(new RelationMember(role, modifyWay));
    248             }
    249             Relation newRel = new Relation(r);
    250             newRel.setMembers(newMembers);
    251             cmds.add(new ChangeCommand(r, newRel));
    252         }
    253         Main.main.undoRedo.add(new SequenceCommand(tr("Combine {0} ways", selectedWays.size()), cmds));
    254         getCurrentDataSet().setSelected(modifyWay);
    255     }
    256 
    257     /**
    258      * @return a message if combining failed, else a list of nodes.
    259      */
    260     private Object actuallyCombineWays(List<Way> ways, boolean ignoreDirection) {
    261         // Battle plan:
    262         //  1. Split the ways into small chunks of 2 nodes and weed out
    263         //     duplicates.
    264         //  2. Take a chunk and see if others could be appended or prepended,
    265         //     if so, do it and remove it from the list of remaining chunks.
    266         //     Rather, rinse, repeat.
    267         //  3. If this algorithm does not produce a single way,
    268         //     complain to the user.
    269         //  4. Profit!
    270 
    271         HashSet<Pair<Node,Node>> chunkSet = new HashSet<Pair<Node,Node>>();
    272         for (Way w : ways) {
    273             chunkSet.addAll(w.getNodePairs(ignoreDirection));
    274         }
    275 
    276         LinkedList<Pair<Node,Node>> chunks = new LinkedList<Pair<Node,Node>>(chunkSet);
    277 
    278         if (chunks.isEmpty())
    279             return tr("All the ways were empty");
    280 
    281         List<Node> nodeList = Pair.toArrayList(chunks.poll());
    282         while (!chunks.isEmpty()) {
    283             ListIterator<Pair<Node,Node>> it = chunks.listIterator();
    284             boolean foundChunk = false;
    285             while (it.hasNext()) {
    286                 Pair<Node,Node> curChunk = it.next();
    287                 if (curChunk.a == nodeList.get(nodeList.size() - 1)) { // append
    288                     nodeList.add(curChunk.b);
    289                 } else if (curChunk.b == nodeList.get(0)) { // prepend
    290                     nodeList.add(0, curChunk.a);
    291                 } else if (ignoreDirection && curChunk.b == nodeList.get(nodeList.size() - 1)) { // append
    292                     nodeList.add(curChunk.a);
    293                 } else if (ignoreDirection && curChunk.a == nodeList.get(0)) { // prepend
    294                     nodeList.add(0, curChunk.b);
    295                 } else {
    296                     continue;
    297                 }
    298 
    299                 foundChunk = true;
    300                 it.remove();
    301                 break;
    302             }
    303             if (!foundChunk) {
    304                 break;
    305             }
    306         }
    307 
    308         if (!chunks.isEmpty())
    309             return tr("Could not combine ways "
    310                     + "(They could not be merged into a single string of nodes)");
    311 
    312         return nodeList;
     223        combineWays(selectedWays);
    313224    }
    314225
    … …  
    328239        setEnabled(numWays >= 2);
    329240    }
     241
     242    /**
     243     * This is a collection of relations referring to at least one out of a set of
     244     * ways.
     245     *
     246     *
     247     */
     248    static private class WayReferringRelations {
     249        /**
     250         * the map references between relations and ways. The key is a ways, the value is a
     251         * set of relations referring to that way.
     252         */
     253        private Map<Way, Set<Relation>> wayRelationMap;
     254
     255        /**
     256         *
     257         * @param ways  a collection of ways
     258         */
     259        public WayReferringRelations(Collection<Way> ways) {
     260            wayRelationMap = new HashMap<Way, Set<Relation>>();
     261            if (ways == null) return;
     262            ways.remove(null); // just in case - remove null values
     263            for (Way way: ways) {
     264                if (!wayRelationMap.containsKey(way)) {
     265                    wayRelationMap.put(way, new HashSet<Relation>());
     266                }
     267            }
     268        }
     269
     270        /**
     271         * build the sets of referring relations from the relations in the dataset <code>ds</code>
     272         *
     273         * @param ds the data set
     274         */
     275        public void build(DataSet ds) {
     276            for (Relation r: ds.relations) {
     277                if (r.isDeleted() || r.incomplete) {
     278                    continue;
     279                }
     280                Set<Way> referringWays = OsmPrimitive.getFilteredSet(r.getMemberPrimitives(), Way.class);
     281                for (Way w : wayRelationMap.keySet()) {
     282                    if (referringWays.contains(w)) {
     283                        wayRelationMap.get(w).add(r);
     284                    }
     285                }
     286            }
     287        }
     288
     289        /**
     290         * Replies the ways
     291         * @return the ways
     292         */
     293        public Set<Way> getWays() {
     294            return wayRelationMap.keySet();
     295        }
     296
     297        /**
     298         * Replies the set of referring relations
     299         *
     300         * @return the set of referring relations
     301         */
     302        public Set<Relation> getRelations() {
     303            HashSet<Relation> ret = new HashSet<Relation>();
     304            for (Way w: wayRelationMap.keySet()) {
     305                ret.addAll(wayRelationMap.get(w));
     306            }
     307            return ret;
     308        }
     309
     310        /**
     311         * Replies the set of referring relations for a specific way
     312         *
     313         * @return the set of referring relations
     314         */
     315        public Set<Relation> getRelations(Way way) {
     316            return wayRelationMap.get(way);
     317        }
     318
     319        protected Command buildRelationUpdateCommand(Relation relation, Collection<Way> ways, Way targetWay) {
     320            List<RelationMember> newMembers = new ArrayList<RelationMember>();
     321            for (RelationMember rm : relation.getMembers()) {
     322                if (ways.contains(rm.getMember())) {
     323                    RelationMember newMember = new RelationMember(rm.getRole(),targetWay);
     324                    newMembers.add(newMember);
     325                } else {
     326                    newMembers.add(rm);
     327                }
     328            }
     329            Relation newRelation = new Relation(relation);
     330            newRelation.setMembers(newMembers);
     331            return new ChangeCommand(relation, newRelation);
     332        }
     333
     334        public List<Command> buildRelationUpdateCommands(Way targetWay) {
     335            Collection<Way> toRemove = getWays();
     336            toRemove.remove(targetWay);
     337            ArrayList<Command> cmds = new ArrayList<Command>();
     338            for (Relation r : getRelations()) {
     339                Command cmd = buildRelationUpdateCommand(r, toRemove, targetWay);
     340                cmds.add(cmd);
     341            }
     342            return cmds;
     343        }
     344    }
     345
     346    static public class NodePair {
     347        private Node a;
     348        private Node b;
     349        public NodePair(Node a, Node b) {
     350            this.a =a;
     351            this.b = b;
     352        }
     353
     354        public NodePair(Pair<Node,Node> pair) {
     355            this.a = pair.a;
     356            this.b = pair.b;
     357        }
     358
     359        public NodePair(NodePair other) {
     360            this.a = other.a;
     361            this.b = other.b;
     362        }
     363
     364        public Node getA() {
     365            return a;
     366        }
     367
     368        public Node getB() {
     369            return b;
     370        }
     371
     372        public boolean isAdjacentToA(NodePair other) {
     373            return other.getA() == a || other.getB() == a;
     374        }
     375
     376        public boolean isAdjacentToB(NodePair other) {
     377            return other.getA() == b || other.getB() == b;
     378        }
     379
     380        public boolean isSuccessorOf(NodePair other) {
     381            return other.getB() == a;
     382        }
     383
     384        public boolean isPredecessorOf(NodePair other) {
     385            return b == other.getA();
     386        }
     387
     388        public NodePair swap() {
     389            return new NodePair(b,a);
     390        }
     391
     392        @Override
     393        public String toString() {
     394            return new StringBuilder()
     395            .append("[")
     396            .append(a.getId())
     397            .append(",")
     398            .append(b.getId())
     399            .append("]")
     400            .toString();
     401        }
     402
     403        public boolean contains(Node n) {
     404            return a == n || b == n;
     405        }
     406
     407        @Override
     408        public int hashCode() {
     409            final int prime = 31;
     410            int result = 1;
     411            result = prime * result + ((a == null) ? 0 : a.hashCode());
     412            result = prime * result + ((b == null) ? 0 : b.hashCode());
     413            return result;
     414        }
     415        @Override
     416        public boolean equals(Object obj) {
     417            if (this == obj)
     418                return true;
     419            if (obj == null)
     420                return false;
     421            if (getClass() != obj.getClass())
     422                return false;
     423            NodePair other = (NodePair) obj;
     424            if (a == null) {
     425                if (other.a != null)
     426                    return false;
     427            } else if (!a.equals(other.a))
     428                return false;
     429            if (b == null) {
     430                if (other.b != null)
     431                    return false;
     432            } else if (!b.equals(other.b))
     433                return false;
     434            return true;
     435        }
     436    }
     437
     438
     439    static public class NodeGraph {
     440        static public List<NodePair> buildNodePairs(Way way, boolean directed) {
     441            ArrayList<NodePair> pairs = new ArrayList<NodePair>();
     442            for (Pair<Node,Node> pair: way.getNodePairs(false /* don't sort */)) {
     443                pairs.add(new NodePair(pair));
     444                if (!directed) {
     445                    pairs.add(new NodePair(pair).swap());
     446                }
     447            }
     448            return pairs;
     449        }
     450
     451        static public List<NodePair> buildNodePairs(List<Way> ways, boolean directed) {
     452            ArrayList<NodePair> pairs = new ArrayList<NodePair>();
     453            for (Way w: ways) {
     454                pairs.addAll(buildNodePairs(w, directed));
     455            }
     456            return pairs;
     457        }
     458
     459        static public List<NodePair> eliminateDuplicateNodePairs(List<NodePair> pairs) {
     460            ArrayList<NodePair> cleaned = new ArrayList<NodePair>();
     461            for(NodePair p: pairs) {
     462                if (!cleaned.contains(p) && !cleaned.contains(p.swap())) {
     463                    cleaned.add(p);
     464                }
     465            }
     466            return cleaned;
     467        }
     468
     469        static public NodeGraph createDirectedGraphFromNodePairs(List<NodePair> pairs) {
     470            NodeGraph graph = new NodeGraph();
     471            for (NodePair pair: pairs) {
     472                graph.add(pair);
     473            }
     474            return graph;
     475        }
     476
     477        static public NodeGraph createDirectedGraphFromWays(Collection<Way> ways) {
     478            NodeGraph graph = new NodeGraph();
     479            for (Way w: ways) {
     480                graph.add(buildNodePairs(w, true /* directed */));
     481            }
     482            return graph;
     483        }
     484
     485        static public NodeGraph createUndirectedGraphFromNodeList(List<NodePair> pairs) {
     486            NodeGraph graph = new NodeGraph();
     487            for (NodePair pair: pairs) {
     488                graph.add(pair);
     489                graph.add(pair.swap());
     490            }
     491            return graph;
     492        }
     493
     494        static public NodeGraph createUndirectedGraphFromNodeWays(Collection<Way> ways) {
     495            NodeGraph graph = new NodeGraph();
     496            for (Way w: ways) {
     497                graph.add(buildNodePairs(w, false /* undirected */));
     498            }
     499            return graph;
     500        }
     501
     502        private Set<NodePair> edges;
     503        private int numUndirectedEges = 0;
     504
     505        protected void computeNumEdges() {
     506            Set<NodePair> undirectedEdges = new HashSet<NodePair>();
     507            for (NodePair pair: edges) {
     508                if (!undirectedEdges.contains(pair) && ! undirectedEdges.contains(pair.swap())) {
     509                    undirectedEdges.add(pair);
     510                }
     511            }
     512            numUndirectedEges = undirectedEdges.size();
     513        }
     514
     515        public NodeGraph() {
     516            edges = new HashSet<NodePair>();
     517        }
     518
     519        public void add(NodePair pair) {
     520            if (!edges.contains(pair)) {
     521                edges.add(pair);
     522            }
     523        }
     524
     525        public void add(List<NodePair> pairs) {
     526            for (NodePair pair: pairs) {
     527                add(pair);
     528            }
     529        }
     530
     531        protected Node getStartNode() {
     532            return edges.iterator().next().getA();
     533        }
     534
     535        protected Set<Node> getNodes(Stack<NodePair> pairs) {
     536            HashSet<Node> nodes = new HashSet<Node>();
     537            for (NodePair pair: pairs) {
     538                nodes.add(pair.getA());
     539                nodes.add(pair.getB());
     540            }
     541            return nodes;
     542        }
     543
     544        protected List<NodePair> getOutboundPairs(NodePair pair) {
     545            LinkedList<NodePair> outbound = new LinkedList<NodePair>();
     546            for (NodePair candidate:edges) {
     547                if (candidate.equals(pair)) {
     548                    continue;
     549                }
     550                if (candidate.isSuccessorOf(pair)) {
     551                    outbound.add(candidate);
     552                }
     553            }
     554            return outbound;
     555        }
     556
     557        protected List<NodePair> getOutboundPairs(Node node) {
     558            LinkedList<NodePair> outbound = new LinkedList<NodePair>();
     559            for (NodePair candidate:edges) {
     560                if (candidate.getA() == node) {
     561                    outbound.add(candidate);
     562                }
     563            }
     564            return outbound;
     565        }
     566
     567        protected Set<Node> getNodes() {
     568            Set<Node> nodes = new HashSet<Node>();
     569            for (NodePair pair: edges) {
     570                nodes.add(pair.getA());
     571                nodes.add(pair.getB());
     572            }
     573            return nodes;
     574        }
     575
     576        protected boolean isSpanningWay(Stack<NodePair> way) {
     577            return numUndirectedEges == way.size();
     578        }
     579
     580
     581        protected boolean advance(Stack<NodePair> path) {
     582            // found a spanning path ?
     583            //
     584            if (isSpanningWay(path))
     585                return true;
     586
     587            // advance with one of the possible follow up nodes
     588            //
     589            Stack<NodePair> nextPairs = new Stack<NodePair>();
     590            nextPairs.addAll(getOutboundPairs(path.peek()));
     591            while(!nextPairs.isEmpty()) {
     592                NodePair next = nextPairs.pop();
     593                if (path.contains(next) || path.contains(next.swap())) {
     594                    continue;
     595                }
     596                path.push(next);
     597                if (advance(path)) return true;
     598                path.pop();
     599            }
     600            return false;
     601        }
     602
     603        protected List<Node> buildPathFromNodePairs(Stack<NodePair> path) {
     604            LinkedList<Node> ret = new LinkedList<Node>();
     605            for (NodePair pair: path) {
     606                ret.add(pair.getA());
     607            }
     608            ret.add(path.peek().getB());
     609            return ret;
     610        }
     611
     612        protected List<Node> buildSpanningPath(Node startNode) {
     613            if (startNode == null)
     614                return null;
     615            Stack<NodePair> path = new Stack<NodePair>();
     616            // advance with one of the possible follow up nodes
     617            //
     618            Stack<NodePair> nextPairs  = new Stack<NodePair>();
     619            nextPairs.addAll(getOutboundPairs(startNode));
     620            while(!nextPairs.isEmpty()) {
     621                path.push(nextPairs.pop());
     622                if (advance(path))
     623                    return buildPathFromNodePairs(path);
     624                path.pop();
     625            }
     626            return null;
     627        }
     628
     629        public List<Node> buildSpanningPath() {
     630            computeNumEdges();
     631            for (Node n : getNodes()) {
     632                List<Node> path = buildSpanningPath(n);
     633                if (path != null)
     634                    return path;
     635            }
     636            return null;
     637        }
     638    }
    330639}
Note: See TracChangeset for help on using the changeset viewer.