Changeset 21177 in osm


Ignore:
Timestamp:
2010-05-08T15:24:20+02:00 (14 years ago)
Author:
jttt
Message:

Optimization of duplicate nodes test

File:
1 edited

Legend:

Unmodified
Added
Removed

  • applications/editors/josm/plugins/validator/src/org/openstreetmap/josm/plugins/validator/tests/DuplicateNode.java

    r21128 r21177  
    88import java.util.ArrayList;
    99import java.util.Collection;
    10 import java.util.HashMap;
    1110import java.util.Iterator;
    1211import java.util.LinkedHashSet;
    … …  
    1413import java.util.List;
    1514import java.util.Map;
    16 import java.util.Map.Entry;
    1715
    1816import javax.swing.JLabel;
    … …  
    2422import org.openstreetmap.josm.command.Command;
    2523import org.openstreetmap.josm.data.coor.LatLon;
     24import org.openstreetmap.josm.data.osm.Hash;
    2625import org.openstreetmap.josm.data.osm.Node;
    2726import org.openstreetmap.josm.data.osm.OsmPrimitive;
     27import org.openstreetmap.josm.data.osm.Storage;
    2828import org.openstreetmap.josm.gui.ConditionalOptionPaneUtil;
    2929import org.openstreetmap.josm.gui.progress.ProgressMonitor;
    … …  
    3939public class DuplicateNode extends Test{
    4040
     41    private class NodeHash implements Hash<Object, Object> {
     42
     43        @SuppressWarnings("unchecked")
     44        private LatLon getLatLon(Object o) {
     45            if (o instanceof Node) {
     46                return ((Node) o).getCoor().getRoundedToOsmPrecision();
     47            } else if (o instanceof List<?>) {
     48                return ((List<Node>) o).get(0).getCoor().getRoundedToOsmPrecision();
     49            } else {
     50                throw new AssertionError();
     51            }
     52        }
     53
     54        public boolean equals(Object k, Object t) {
     55            return getLatLon(k).equals(getLatLon(t));
     56        }
     57
     58        public int getHashCode(Object k) {
     59            return getLatLon(k).hashCode();
     60        }
     61
     62    }
     63
    4164    protected static int DUPLICATE_NODE = 1;
    4265
    … …  
    4770     * <pos, NodesByEqualTagsMap>
    4871     */
    49     Map<LatLon,Object> potentialDuplicates;
     72    Storage<Object> potentialDuplicates;
    5073
    5174    /**
    … …  
    5578    {
    5679        super(tr("Duplicated nodes")+".",
    57               tr("This test checks that there are no nodes at the very same location."));
     80                tr("This test checks that there are no nodes at the very same location."));
    5881    }
    5982
    6083    @Override
    6184    public void startTest(ProgressMonitor monitor) {
    62         super.startTest(monitor);
    63         potentialDuplicates = new HashMap<LatLon, Object>();
    64     }
    65 
    66 
    67         @Override
    68         public void endTest() {
    69                 for (Entry<LatLon, Object> entry: potentialDuplicates.entrySet()) {
    70                         Object v = entry.getValue();
    71                         if (v instanceof Node) {
    72                                 // just one node at this position. Nothing to report as
    73                                 // error
    74                                 continue;
    75                         }
    76 
    77                         // multiple nodes at the same position -> report errors
    78                         //
    79                         NodesByEqualTagsMap map = (NodesByEqualTagsMap)v;
    80                         errors.addAll(map.buildTestErrors(this));
    81                 }
    82                 super.endTest();
    83                 potentialDuplicates = null;
    84         }
    85 
    86         @Override
    87         public void visit(Node n) {
    88                 if (n.isUsable()) {
    89                         LatLon rounded = n.getCoor().getRoundedToOsmPrecision();
    90                         if (potentialDuplicates.get(rounded) == null) {
    91                                 // in most cases there is just one node at a given position. We
    92                                 // avoid to create an extra object and add remember the node
    93                                 // itself at this position
    94                                 potentialDuplicates.put(rounded, n);
    95                         } else if (potentialDuplicates.get(rounded) instanceof Node) {
    96                                 // we have an additional node at the same position. Create an extra
    97                                 // object to keep track of the nodes at this position.
    98                                 //
    99                                 Node n1 = (Node)potentialDuplicates.get(rounded);
    100                                 NodesByEqualTagsMap map = new NodesByEqualTagsMap();
    101                                 map.add(n1);
    102                                 map.add(n);
    103                                 potentialDuplicates.put(rounded, map);
    104                         } else if (potentialDuplicates.get(rounded) instanceof NodesByEqualTagsMap) {
    105                                 // we have multiple nodes at the same position.
    106                                 //
    107                                 NodesByEqualTagsMap map = (NodesByEqualTagsMap)potentialDuplicates.get(rounded);
    108                                 map.add(n);
    109                         }
    110                 }
    111         }
     85        super.startTest(monitor);
     86        potentialDuplicates = new Storage<Object>(new NodeHash());
     87    }
     88
     89
     90    @SuppressWarnings("unchecked")
     91    @Override
     92    public void endTest() {
     93        for (Object v: potentialDuplicates) {
     94            if (v instanceof Node) {
     95                // just one node at this position. Nothing to report as
     96                // error
     97                continue;
     98            }
     99
     100            // multiple nodes at the same position -> report errors
     101            //
     102            List<Node> nodes = (List<Node>)v;
     103            errors.addAll(buildTestErrors(this, nodes));
     104        }
     105        super.endTest();
     106        potentialDuplicates = null;
     107    }
     108
     109    public List<TestError> buildTestErrors(Test parentTest, List<Node> nodes) {
     110        List<TestError> errors = new ArrayList<TestError>();
     111
     112        Bag<Map<String,String>, OsmPrimitive> bag = new Bag<Map<String,String>, OsmPrimitive>();
     113        for (Node n: nodes) {
     114            bag.add(n.getKeys(), n);
     115        }
     116        // check whether we have multiple nodes at the same position with
     117        // the same tag set
     118        //
     119        for (Iterator<Map<String,String>> it = bag.keySet().iterator(); it.hasNext(); ) {
     120            Map<String,String> tagSet = it.next();
     121            if (bag.get(tagSet).size() > 1) {
     122                errors.add(new TestError(
     123                        parentTest,
     124                        Severity.ERROR,
     125                        tr("Duplicated nodes"),
     126                        DUPLICATE_NODE,
     127                        bag.get(tagSet)
     128                ));
     129                it.remove();
     130            }
     131
     132        }
     133
     134        // check whether we have multiple nodes at the same position with
     135        // differing tag sets
     136        //
     137        if (!bag.isEmpty()) {
     138            List<OsmPrimitive> duplicates = new ArrayList<OsmPrimitive>();
     139            for (List<OsmPrimitive> l: bag.values()) {
     140                duplicates.addAll(l);
     141            }
     142            if (duplicates.size() > 1) {
     143                errors.add(new TestError(
     144                        parentTest,
     145                        Severity.WARNING,
     146                        tr("Nodes at same position"),
     147                        DUPLICATE_NODE,
     148                        duplicates
     149                ));
     150            }
     151        }
     152        return errors;
     153    }
     154
     155    @SuppressWarnings("unchecked")
     156    @Override
     157    public void visit(Node n) {
     158        if (n.isUsable()) {
     159            if (potentialDuplicates.get(n) == null) {
     160                // in most cases there is just one node at a given position. We
     161                // avoid to create an extra object and add remember the node
     162                // itself at this position
     163                potentialDuplicates.put(n);
     164            } else if (potentialDuplicates.get(n) instanceof Node) {
     165                // we have an additional node at the same position. Create an extra
     166                // object to keep track of the nodes at this position.
     167                //
     168                Node n1 = (Node)potentialDuplicates.get(n);
     169                List<Node> nodes = new ArrayList<Node>(2);
     170                nodes.add(n1);
     171                nodes.add(n);
     172                potentialDuplicates.put(nodes);
     173            } else if (potentialDuplicates.get(n) instanceof List<?>) {
     174                // we have multiple nodes at the same position.
     175                //
     176                List<Node> nodes = (List<Node>)potentialDuplicates.get(n);
     177                nodes.add(n);
     178            }
     179        }
     180    }
    112181
    113182    /**
    … …  
    139208    }
    140209
    141         @Override
    142         public boolean isFixable(TestError testError) {
    143                 return (testError.getTester() instanceof DuplicateNode);
    144         }
     210    @Override
     211    public boolean isFixable(TestError testError) {
     212        return (testError.getTester() instanceof DuplicateNode);
     213    }
    145214
    146215    /**
    … …  
    166235
    167236                        return ConditionalOptionPaneUtil.showConfirmationDialog(
    168                             "delete_outside_nodes",
    169                             Main.parent,
    170                             msg,
    171                             tr("Delete confirmation"),
    172                             JOptionPane.YES_NO_OPTION,
    173                             JOptionPane.QUESTION_MESSAGE,
    174                             JOptionPane.YES_OPTION);
     237                                "delete_outside_nodes",
     238                                Main.parent,
     239                                msg,
     240                                tr("Delete confirmation"),
     241                                JOptionPane.YES_NO_OPTION,
     242                                JOptionPane.QUESTION_MESSAGE,
     243                                JOptionPane.YES_OPTION);
    175244                    }
    176245                }
    … …  
    179248        return true;
    180249    }
    181 
    182     static private class NodesByEqualTagsMap {
    183         /**
    184          * a bag of primitives with the same position. The bag key is represented
    185          * by the tag set of the primitive. This allows for easily find nodes at
    186          * the same position with the same tag sets later.
    187          */
    188         private Bag<Map<String,String>, OsmPrimitive> bag;
    189 
    190         public NodesByEqualTagsMap() {
    191                 bag = new Bag<Map<String,String>, OsmPrimitive>();
    192         }
    193 
    194         public void add(Node n) {
    195                 bag.add(n.getKeys(), n);
    196         }
    197 
    198         public List<TestError> buildTestErrors(Test parentTest) {
    199                 List<TestError> errors = new ArrayList<TestError>();
    200                 // check whether we have multiple nodes at the same position with
    201                 // the same tag set
    202                 //
    203                 for (Iterator<Map<String,String>> it = bag.keySet().iterator(); it.hasNext(); ) {
    204                         Map<String,String> tagSet = it.next();
    205                         if (bag.get(tagSet).size() > 1) {
    206                                 errors.add(new TestError(
    207                                                 parentTest,
    208                                                 Severity.ERROR,
    209                                                 tr("Duplicated nodes"),
    210                                                 DUPLICATE_NODE,
    211                                                 bag.get(tagSet)
    212                                 ));
    213                                 it.remove();
    214                         }
    215 
    216                 }
    217 
    218                 // check whether we have multiple nodes at the same position with
    219                 // differing tag sets
    220                 //
    221                 if (!bag.isEmpty()) {
    222                         List<OsmPrimitive> duplicates = new ArrayList<OsmPrimitive>();
    223                         for (List<OsmPrimitive> l: bag.values()) {
    224                                 duplicates.addAll(l);
    225                         }
    226                         if (duplicates.size() > 1) {
    227                                 errors.add(new TestError(
    228                                                 parentTest,
    229                                                 Severity.WARNING,
    230                                                         tr("Nodes at same position"),
    231                                                         DUPLICATE_NODE,
    232                                                         duplicates
    233                                         ));
    234                         }
    235                 }
    236                 return errors;
    237         }
    238     }
    239250}
Note: See TracChangeset for help on using the changeset viewer.