Changeset 3674 in josm for trunk

Timestamp:

2010-11-25T18:06:50+01:00 (14 years ago)

Author:

bastiK

Message:

Replace Bag by MultiMap.
Both collections are quite similar, but there is a technical difference: Bag is backed by an ArrayList and MultiMap by a LinkedHashSet. So with a Bag you could map a key multiple times to a certain value. I haven't found any usage where this behaviour is required or intended.
Also there could be a certain performance drawback with LinkedHashSet compared to ArrayList. However in the typical validator use case the value collection represents duplicate or crossing ways, so the number of elements is usually 1 or 2 and mostly smaller than the initial capacity (LHS=16, AL=10). (But I could have overlooked some use cases.)

Location:

trunk/src/org/openstreetmap/josm

Files:

• data/validation/TestError.java (modified) (4 diffs)
• data/validation/tests/DuplicateNode.java (modified) (16 diffs)
• data/validation/tests/DuplicateWay.java (modified) (9 diffs)
• data/validation/tests/OverlappingWays.java (modified) (6 diffs)
• data/validation/tests/SimilarNamedWays.java (modified) (6 diffs)
• data/validation/tests/TagChecker.java (modified) (16 diffs)
• data/validation/tests/UnclosedWays.java (modified) (4 diffs)
• data/validation/tests/WronglyOrderedWays.java (modified) (4 diffs)
• data/validation/util/Bag.java (deleted)
• gui/dialogs/validator/ValidatorTreePanel.java (modified) (8 diffs)
• gui/layer/ValidatorLayer.java (modified) (3 diffs)
• tools/MultiMap.java (modified) (4 diffs)
• tools/Utils.java (modified) (1 diff)

trunk/src/org/openstreetmap/josm/data/validation/TestError.java

@@ -34 +34 @@
     private String description_en;
     /** The affected primitives */
-    private List<? extends OsmPrimitive> primitives;
+    private Collection<? extends OsmPrimitive> primitives;
     /** The primitives to be highlighted */
-    private List<?> highlighted;
+    private Collection<?> highlighted;
     /** The tester that raised this error */
     private Test tester;
@@ -54 +54 @@
      */
     public TestError(Test tester, Severity severity, String message, String description, String description_en,
-            int code, List<? extends OsmPrimitive> primitives, List<?> highlighted) {
+            int code, Collection<? extends OsmPrimitive> primitives, Collection<?> highlighted) {
         this.tester = tester;
         this.severity = severity;
@@ -65 +65 @@
     }
 
-    public TestError(Test tester, Severity severity, String message, int code, List<? extends OsmPrimitive> primitives,
-            List<?> highlighted) {
+    public TestError(Test tester, Severity severity, String message, int code, Collection<? extends OsmPrimitive> primitives,
+            Collection<?> highlighted) {
         this(tester, severity, message, null, null, code, primitives, highlighted);
     }
 
     public TestError(Test tester, Severity severity, String message, String description, String description_en,
-            int code, List<? extends OsmPrimitive> primitives) {
+            int code, Collection<? extends OsmPrimitive> primitives) {
         this(tester, severity, message, description, description_en, code, primitives, primitives);
     }
 
-    public TestError(Test tester, Severity severity, String message, int code, List<? extends OsmPrimitive> primitives) {
+    public TestError(Test tester, Severity severity, String message, int code, Collection<? extends OsmPrimitive> primitives) {
         this(tester, severity, message, null, null, code, primitives, primitives);
     }
@@ -117 +117 @@
      * @return the list of primitives affected by this error
      */
-    public List<? extends OsmPrimitive> getPrimitives() {
+    public Collection<? extends OsmPrimitive> getPrimitives() {
         return primitives;
     }

trunk/src/org/openstreetmap/josm/data/validation/tests/DuplicateNode.java

@@ -15 +15 @@
 import java.util.List;
 import java.util.Map;
+import java.util.Set;
 
 import javax.swing.JLabel;
@@ -33 +34 @@
 import org.openstreetmap.josm.data.validation.Test;
 import org.openstreetmap.josm.data.validation.TestError;
-import org.openstreetmap.josm.data.validation.util.Bag;
 import org.openstreetmap.josm.gui.ConditionalOptionPaneUtil;
 import org.openstreetmap.josm.gui.progress.ProgressMonitor;
+import org.openstreetmap.josm.tools.MultiMap;
 
 /**
@@ -138 +139 @@
         List<TestError> errors = new ArrayList<TestError>();
 
-        Bag<Map<String,String>, OsmPrimitive> bag = new Bag<Map<String,String>, OsmPrimitive>();
+        MultiMap<Map<String,String>, OsmPrimitive> mm = new MultiMap<Map<String,String>, OsmPrimitive>();
         for (Node n: nodes) {
-            bag.add(n.getKeys(), n);
+            mm.put(n.getKeys(), n);
         }
 
@@ -150 +151 @@
         // the same tag set
         //
-        for (Iterator<Map<String,String>> it = bag.keySet().iterator(); it.hasNext();) {
+        for (Iterator<Map<String,String>> it = mm.keySet().iterator(); it.hasNext();) {
             Map<String,String> tagSet = it.next();
-            if (bag.get(tagSet).size() > 1) {
+            if (mm.get(tagSet).size() > 1) {
 
                 for (String type: types) {
@@ -158 +159 @@
                 }
 
-                for (OsmPrimitive p : bag.get(tagSet)) {
+                for (OsmPrimitive p : mm.get(tagSet)) {
                     if (p.getType()==OsmPrimitiveType.NODE) {
                         Node n = (Node) p;
@@ -198 +199 @@
                             msg,
                             DUPLICATE_NODE_MIXED,
-                            bag.get(tagSet)
+                            mm.get(tagSet)
                     ));
                 } else if (typeMap.get("highway")) {
@@ -209 +210 @@
                             msg,
                             DUPLICATE_NODE_HIGHWAY,
-                            bag.get(tagSet)
+                            mm.get(tagSet)
                     ));
                 } else if (typeMap.get("railway")) {
@@ -220 +221 @@
                             msg,
                             DUPLICATE_NODE_RAILWAY,
-                            bag.get(tagSet)
+                            mm.get(tagSet)
                     ));
                 } else if (typeMap.get("waterway")) {
@@ -231 +232 @@
                             msg,
                             DUPLICATE_NODE_WATERWAY,
-                            bag.get(tagSet)
+                            mm.get(tagSet)
                     ));
                 } else if (typeMap.get("boundary")) {
@@ -242 +243 @@
                             msg,
                             DUPLICATE_NODE_BOUNDARY,
-                            bag.get(tagSet)
+                            mm.get(tagSet)
                     ));
                 } else if (typeMap.get("power")) {
@@ -253 +254 @@
                             msg,
                             DUPLICATE_NODE_POWER,
-                            bag.get(tagSet)
+                            mm.get(tagSet)
                     ));
                 } else if (typeMap.get("natural")) {
@@ -264 +265 @@
                             msg,
                             DUPLICATE_NODE_NATURAL,
-                            bag.get(tagSet)
+                            mm.get(tagSet)
                     ));
                 } else if (typeMap.get("building")) {
@@ -275 +276 @@
                             msg,
                             DUPLICATE_NODE_BUILDING,
-                            bag.get(tagSet)
+                            mm.get(tagSet)
                     ));
                 } else if (typeMap.get("landuse")) {
@@ -286 +287 @@
                             msg,
                             DUPLICATE_NODE_LANDUSE,
-                            bag.get(tagSet)
+                            mm.get(tagSet)
                     ));
                 } else {
@@ -297 +298 @@
                             msg,
                             DUPLICATE_NODE_OTHER,
-                            bag.get(tagSet)
+                            mm.get(tagSet)
                     ));
 
@@ -308 +309 @@
         // differing tag sets
         //
-        if (!bag.isEmpty()) {
+        if (!mm.isEmpty()) {
             List<OsmPrimitive> duplicates = new ArrayList<OsmPrimitive>();
-            for (List<OsmPrimitive> l: bag.values()) {
+            for (Set<OsmPrimitive> l: mm.values()) {
                 duplicates.addAll(l);
             }

trunk/src/org/openstreetmap/josm/data/validation/tests/DuplicateWay.java

@@ -4 +4 @@
 import static org.openstreetmap.josm.tools.I18n.tr;
 
+import java.util.ArrayList;
 import java.util.Collection;
 import java.util.HashSet;
@@ -9 +10 @@
 import java.util.List;
 import java.util.Map;
-import java.util.Vector;
+import java.util.Set;
 
 import org.openstreetmap.josm.command.ChangeCommand;
@@ -24 +25 @@
 import org.openstreetmap.josm.data.validation.Test;
 import org.openstreetmap.josm.data.validation.TestError;
-import org.openstreetmap.josm.data.validation.util.Bag;
 import org.openstreetmap.josm.gui.progress.ProgressMonitor;
+import org.openstreetmap.josm.tools.MultiMap;
 
 /**
@@ -36 +37 @@
         public List<LatLon> coor;
         public Map<String, String> keys;
-        public WayPair(List<LatLon> _coor,Map<String, String> _keys) {
+        public WayPair(List<LatLon> _coor, Map<String, String> _keys) {
             coor=_coor;
             keys=_keys;
@@ -43 +44 @@
         @Override
         public int hashCode() {
-            return coor.hashCode()+keys.hashCode();
+            return coor.hashCode() + keys.hashCode();
         }
 
@@ -58 +59 @@
 
     /** Bag of all ways */
-    Bag<WayPair, OsmPrimitive> ways;
+    MultiMap<WayPair, OsmPrimitive> ways;
 
     /**
@@ -72 +73 @@
     public void startTest(ProgressMonitor monitor) {
         super.startTest(monitor);
-        ways = new Bag<WayPair, OsmPrimitive>(1000);
+        ways = new MultiMap<WayPair, OsmPrimitive>(1000);
     }
 
@@ -78 +79 @@
     public void endTest() {
         super.endTest();
-        for (List<OsmPrimitive> duplicated : ways.values()) {
+        for (Set<OsmPrimitive> duplicated : ways.values()) {
             if (duplicated.size() > 1) {
                 TestError testError = new TestError(this, Severity.ERROR, tr("Duplicated ways"), DUPLICATE_WAY, duplicated);
@@ -91 +92 @@
         if (!w.isUsable())
             return;
-        List<Node> wNodes=w.getNodes();
-        Vector<LatLon> wLat=new Vector<LatLon>(wNodes.size());
+        List<Node> wNodes = w.getNodes();
+        List<LatLon> wLat = new ArrayList<LatLon>(wNodes.size());
         for (int i=0;i<wNodes.size();i++) {
              wLat.add(wNodes.get(i).getCoor());
         }
-        Map<String, String> wkeys=w.getKeys();
+        Map<String, String> wkeys = w.getKeys();
         wkeys.remove("created_by");
-        WayPair wKey=new WayPair(wLat,wkeys);
-        ways.add(wKey, w);
+        WayPair wKey = new WayPair(wLat, wkeys);
+        ways.put(wKey, w);
     }
 

trunk/src/org/openstreetmap/josm/data/validation/tests/OverlappingWays.java

@@ -5 +5 @@
 
 import java.util.ArrayList;
+import java.util.Collection;
 import java.util.HashMap;
+import java.util.LinkedHashSet;
 import java.util.List;
 import java.util.Map;
@@ -17 +19 @@
 import org.openstreetmap.josm.data.validation.Test;
 import org.openstreetmap.josm.data.validation.TestError;
-import org.openstreetmap.josm.data.validation.util.Bag;
 import org.openstreetmap.josm.gui.progress.ProgressMonitor;
+import org.openstreetmap.josm.tools.MultiMap;
 import org.openstreetmap.josm.tools.Pair;
 
@@ -29 +31 @@
     
     /** Bag of all way segments */
-    Bag<Pair<Node,Node>, WaySegment> nodePairs;
+    MultiMap<Pair<Node,Node>, WaySegment> nodePairs;
 
     protected static int OVERLAPPING_HIGHWAY = 101;
@@ -49 +51 @@
     public void startTest(ProgressMonitor monitor)  {
         super.startTest(monitor);
-        nodePairs = new Bag<Pair<Node,Node>, WaySegment>(1000);
+        nodePairs = new MultiMap<Pair<Node,Node>, WaySegment>(1000);
     }
 
     @Override
     public void endTest() {
-        Map<List<Way>, List<WaySegment>> ways_seen = new HashMap<List<Way>, List<WaySegment>>(500);
+        Map<List<Way>, LinkedHashSet<WaySegment>> ways_seen = new HashMap<List<Way>, LinkedHashSet<WaySegment>>(500);
 
-        for (List<WaySegment> duplicated : nodePairs.values()) {
+        for (LinkedHashSet<WaySegment> duplicated : nodePairs.values()) {
             int ways = duplicated.size();
 
@@ -62 +64 @@
                 List<OsmPrimitive> prims = new ArrayList<OsmPrimitive>();
                 List<Way> current_ways = new ArrayList<Way>();
-                List<WaySegment> highlight;
+                Collection<WaySegment> highlight;
                 int highway = 0;
                 int railway = 0;
@@ -148 +150 @@
                 continue;
             }
-            nodePairs.add(Pair.sort(new Pair<Node,Node>(lastN, n)),
+            nodePairs.put(Pair.sort(new Pair<Node,Node>(lastN, n)),
                 new WaySegment(w, i));
             lastN = n;

trunk/src/org/openstreetmap/josm/data/validation/tests/SimilarNamedWays.java

@@ -15 +15 @@
 import org.openstreetmap.josm.data.validation.Test;
 import org.openstreetmap.josm.data.validation.TestError;
-import org.openstreetmap.josm.data.validation.util.Bag;
 import org.openstreetmap.josm.data.validation.util.ValUtil;
 import org.openstreetmap.josm.gui.progress.ProgressMonitor;
+import org.openstreetmap.josm.tools.MultiMap;
+import org.openstreetmap.josm.tools.Utils;
 
 /**
@@ -32 +33 @@
     Map<Point2D,List<Way>> cellWays;
     /** The already detected errors */
-    Bag<Way, Way> errorWays;
+    MultiMap<Way, Way> errorWays;
 
     /**
@@ -46 +47 @@
         super.startTest(monitor);
         cellWays = new HashMap<Point2D,List<Way>>(1000);
-        errorWays = new Bag<Way, Way>();
+        errorWays = new MultiMap<Way, Way>();
     }
 
@@ -83 +84 @@
                     primitives.add(w2);
                     errors.add(new TestError(this, Severity.WARNING, tr("Similarly named ways"), SIMILAR_NAMED, primitives));
-                    errorWays.add(w, w2);
+                    errorWays.put(w, w2);
                 }
             }
@@ -142 +143 @@
 
                 // Step 6
-                d[i][j] = min(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + cost);
+                d[i][j] = Utils.min(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + cost);
             }
         }
@@ -149 +150 @@
         return d[n][m];
     }
-
-    /** // FIXME: move to utils
-     * Get minimum of three values
-     * @param a First value
-     * @param b Second value
-     * @param c Third value
-     * @return The minimum of the three values
-     */
-    private static int min(int a, int b, int c) {
-        int mi = a;
-        if (b < mi) {
-            mi = b;
-        } if (c < mi) {
-            mi = c;
-        }
-        return mi;
-    }
 }

trunk/src/org/openstreetmap/josm/data/validation/tests/TagChecker.java

@@ -24 +24 @@
 import java.util.Map;
 import java.util.Map.Entry;
+import java.util.Set;
 import java.util.regex.Matcher;
 import java.util.regex.Pattern;
@@ -50 +51 @@
 import org.openstreetmap.josm.data.validation.Test;
 import org.openstreetmap.josm.data.validation.TestError;
-import org.openstreetmap.josm.data.validation.util.Bag;
 import org.openstreetmap.josm.data.validation.util.Entities;
 import org.openstreetmap.josm.data.validation.util.ValUtil;
@@ -59 +59 @@
 import org.openstreetmap.josm.io.MirroredInputStream;
 import org.openstreetmap.josm.tools.GBC;
+import org.openstreetmap.josm.tools.MultiMap;
 
 /**
@@ -75 +76 @@
     protected static Map<String, String> spellCheckKeyData;
     /** The spell check preset values */
-    protected static Bag<String, String> presetsValueData;
+    protected static MultiMap<String, String> presetsValueData;
     /** The TagChecker data */
     protected static List<CheckerData> checkerData = new ArrayList<CheckerData>();
@@ -294 +295 @@
         Collection<TaggingPreset> presets = TaggingPresetPreference.taggingPresets;
         if (presets != null) {
-            presetsValueData = new Bag<String, String>();
+            presetsValueData = new MultiMap<String, String>();
             for (String a : OsmPrimitive.getUninterestingKeys()) {
-                presetsValueData.add(a);
+                presetsValueData.putVoid(a);
             }
             // TODO directionKeys are no longer in OsmPrimitive (search pattern is used instead)
@@ -304 +305 @@
             for (String a : Main.pref.getCollection(ValidatorPreference.PREFIX + ".knownkeys",
                     Arrays.asList(new String[]{"is_in", "int_ref", "fixme", "population"}))) {
-                presetsValueData.add(a);
+                presetsValueData.putVoid(a);
             }
             for (TaggingPreset p : presets) {
@@ -312 +313 @@
                         if (combo.values != null) {
                             for(String value : combo.values.split(",")) {
-                                presetsValueData.add(combo.key, value);
+                                presetsValueData.put(combo.key, value);
                             }
                         }
                     } else if (i instanceof TaggingPreset.Key) {
                         TaggingPreset.Key k = (TaggingPreset.Key) i;
-                        presetsValueData.add(k.key, k.value);
+                        presetsValueData.put(k.key, k.value);
                     } else if (i instanceof TaggingPreset.Text) {
                         TaggingPreset.Text k = (TaggingPreset.Text) i;
-                        presetsValueData.add(k.key);
+                        presetsValueData.putVoid(k.key);
                     } else if (i instanceof TaggingPreset.Check) {
                         TaggingPreset.Check k = (TaggingPreset.Check) i;
-                        presetsValueData.add(k.key, "yes");
-                        presetsValueData.add(k.key, "no");
+                        presetsValueData.put(k.key, "yes");
+                        presetsValueData.put(k.key, "no");
                     }
                 }
@@ -366 +367 @@
     private void checkPrimitive(OsmPrimitive p) {
         // Just a collection to know if a primitive has been already marked with error
-        Bag<OsmPrimitive, String> withErrors = new Bag<OsmPrimitive, String>();
+        MultiMap<OsmPrimitive, String> withErrors = new MultiMap<OsmPrimitive, String>();
 
         if (checkComplex) {
@@ -400 +401 @@
                     errors.add( new TestError(this, Severity.ERROR, tr("Illegal tag/value combinations"),
                             tr("Illegal tag/value combinations"), tr("Illegal tag/value combinations"), 1272, p) );
-                    withErrors.add(p, "TC");
+                    withErrors.put(p, "TC");
                 }
             }
@@ -409 +410 @@
                     errors.add( new TestError(this, d.getSeverity(), tr("Illegal tag/value combinations"),
                             d.getDescription(), d.getDescriptionOrig(), d.getCode(), p) );
-                    withErrors.add(p, "TC");
+                    withErrors.put(p, "TC");
                 }
             }
@@ -422 +423 @@
                 errors.add( new TestError(this, Severity.WARNING, tr("Tag value contains character with code less than 0x20"),
                         tr(s, key), MessageFormat.format(s, key), LOW_CHAR_VALUE, p) );
-                withErrors.add(p, "ICV");
+                withErrors.put(p, "ICV");
             }
             if (checkKeys && (containsLow(key)) && !withErrors.contains(p, "ICK")) {
                 errors.add( new TestError(this, Severity.WARNING, tr("Tag key contains character with code less than 0x20"),
                         tr(s, key), MessageFormat.format(s, key), LOW_CHAR_KEY, p) );
-                withErrors.add(p, "ICK");
+                withErrors.put(p, "ICK");
             }
             if (checkValues && (value!=null && value.length() > 255) && !withErrors.contains(p, "LV")) {
                 errors.add( new TestError(this, Severity.ERROR, tr("Tag value longer than allowed"),
                         tr(s, key), MessageFormat.format(s, key), LONG_VALUE, p) );
-                withErrors.add(p, "LV");
+                withErrors.put(p, "LV");
             }
             if (checkKeys && (key!=null && key.length() > 255) && !withErrors.contains(p, "LK")) {
                 errors.add( new TestError(this, Severity.ERROR, tr("Tag key longer than allowed"),
                         tr(s, key), MessageFormat.format(s, key), LONG_KEY, p) );
-                withErrors.add(p, "LK");
+                withErrors.put(p, "LK");
             }
             if (checkValues && (value==null || value.trim().length() == 0) && !withErrors.contains(p, "EV")) {
                 errors.add( new TestError(this, Severity.WARNING, tr("Tags with empty values"),
                         tr(s, key), MessageFormat.format(s, key), EMPTY_VALUES, p) );
-                withErrors.add(p, "EV");
+                withErrors.put(p, "EV");
             }
             if (checkKeys && spellCheckKeyData.containsKey(key) && !withErrors.contains(p, "IPK")) {
                 errors.add( new TestError(this, Severity.WARNING, tr("Invalid property key"),
                         tr(s, key), MessageFormat.format(s, key), INVALID_KEY, p) );
-                withErrors.add(p, "IPK");
+                withErrors.put(p, "IPK");
             }
             if (checkKeys && key.indexOf(" ") >= 0 && !withErrors.contains(p, "IPK")) {
                 errors.add( new TestError(this, Severity.WARNING, tr("Invalid white space in property key"),
                         tr(s, key), MessageFormat.format(s, key), INVALID_KEY_SPACE, p) );
-                withErrors.add(p, "IPK");
+                withErrors.put(p, "IPK");
             }
             if (checkValues && value != null && (value.startsWith(" ") || value.endsWith(" ")) && !withErrors.contains(p, "SPACE")) {
                 errors.add( new TestError(this, Severity.OTHER, tr("Property values start or end with white space"),
                         tr(s, key), MessageFormat.format(s, key), INVALID_SPACE, p) );
-                withErrors.add(p, "SPACE");
+                withErrors.put(p, "SPACE");
             }
             if (checkValues && value != null && !value.equals(entities.unescape(value)) && !withErrors.contains(p, "HTML")) {
                 errors.add( new TestError(this, Severity.OTHER, tr("Property values contain HTML entity"),
                         tr(s, key), MessageFormat.format(s, key), INVALID_HTML, p) );
-                withErrors.add(p, "HTML");
+                withErrors.put(p, "HTML");
             }
             if (checkValues && value != null && value.length() > 0 && presetsValueData != null) {
-                List<String> values = presetsValueData.get(key);
+                Set<String> values = presetsValueData.get(key);
                 if (values == null) {
                     boolean ignore = false;
@@ -487 +488 @@
                         errors.add( new TestError(this, Severity.OTHER, tr("Presets do not contain property key"),
                                 tr(i, key), MessageFormat.format(i, key), INVALID_VALUE, p) );
-                        withErrors.add(p, "UPK");
+                        withErrors.put(p, "UPK");
                     }
                 } else if (values.size() > 0 && !values.contains(prop.getValue())) {
@@ -507 +508 @@
                         errors.add( new TestError(this, Severity.OTHER, tr("Presets do not contain property value"),
                                 tr(i, prop.getValue(), key), MessageFormat.format(i, prop.getValue(), key), INVALID_VALUE, p) );
-                        withErrors.add(p, "UPV");
+                        withErrors.put(p, "UPV");
                     }
                 }
@@ -518 +519 @@
                     errors.add(new TestError(this, Severity.OTHER,
                             tr("FIXMES"), FIXME, p));
-                    withErrors.add(p, "FIXME");
+                    withErrors.put(p, "FIXME");
                 }
             }
@@ -755 +756 @@
         List<Command> commands = new ArrayList<Command>(50);
 
-        int i = -1;
-        List<? extends OsmPrimitive> primitives = testError.getPrimitives();
+        Collection<? extends OsmPrimitive> primitives = testError.getPrimitives();
         for (OsmPrimitive p : primitives) {
-            i++;
             Map<String, String> tags = p.getKeys();
             if (tags == null || tags.isEmpty()) {
@@ -768 +767 @@
                 String value = prop.getValue();
                 if (value == null || value.trim().length() == 0) {
-                    commands.add(new ChangePropertyCommand(Collections.singleton(primitives.get(i)), key, null));
+                    commands.add(new ChangePropertyCommand(Collections.singleton(p), key, null));
                 } else if (value.startsWith(" ") || value.endsWith(" ")) {
-                    commands.add(new ChangePropertyCommand(Collections.singleton(primitives.get(i)), key, value.trim()));
+                    commands.add(new ChangePropertyCommand(Collections.singleton(p), key, value.trim()));
                 } else if (key.startsWith(" ") || key.endsWith(" ")) {
-                    commands.add(new ChangePropertyKeyCommand(Collections.singleton(primitives.get(i)), key, key.trim()));
+                    commands.add(new ChangePropertyKeyCommand(Collections.singleton(p), key, key.trim()));
                 } else {
                     String evalue = entities.unescape(value);
                     if (!evalue.equals(value)) {
-                        commands.add(new ChangePropertyCommand(Collections.singleton(primitives.get(i)), key, evalue));
+                        commands.add(new ChangePropertyCommand(Collections.singleton(p), key, evalue));
                     } else {
                         String replacementKey = spellCheckKeyData.get(key);
                         if (replacementKey != null) {
-                            commands.add(new ChangePropertyKeyCommand(Collections.singleton(primitives.get(i)),
+                            commands.add(new ChangePropertyKeyCommand(Collections.singleton(p),
                                     key, replacementKey));
                         }

trunk/src/org/openstreetmap/josm/data/validation/tests/UnclosedWays.java

@@ -17 +17 @@
 import org.openstreetmap.josm.data.validation.Test;
 import org.openstreetmap.josm.data.validation.TestError;
-import org.openstreetmap.josm.data.validation.util.Bag;
 import org.openstreetmap.josm.gui.progress.ProgressMonitor;
 
@@ -26 +25 @@
  */
 public class UnclosedWays extends Test {
-    /** The already detected errors */
-    protected Bag<Way, Way> errorWays;
 
     /**
@@ -39 +36 @@
     public void startTest(ProgressMonitor monitor) {
         super.startTest(monitor);
-        errorWays = new Bag<Way, Way>();
     }
 
     @Override
     public void endTest() {
-        errorWays = null;
         super.endTest();
     }
@@ -133 +128 @@
             errors.add(new TestError(this, Severity.WARNING, tr("Unclosed way"),
                             type, etype, mode, primitives, highlight));
-            errorWays.add(w, w);
         }
     }

trunk/src/org/openstreetmap/josm/data/validation/tests/WronglyOrderedWays.java

@@ -12 +12 @@
 import org.openstreetmap.josm.data.validation.Test;
 import org.openstreetmap.josm.data.validation.TestError;
-import org.openstreetmap.josm.data.validation.util.Bag;
 import org.openstreetmap.josm.gui.progress.ProgressMonitor;
 
@@ -26 +25 @@
     protected static int WRONGLY_ORDERED_LAND  = 1003;
 
-    /** The already detected errors */
-    protected Bag<Way, Way> errorWays;
-
     /**
      * Constructor
@@ -40 +36 @@
     public void startTest(ProgressMonitor monitor) {
         super.startTest(monitor);
-        errorWays = new Bag<Way, Way>();
     }
 
     @Override
     public void endTest() {
-        errorWays = null;
         super.endTest();
     }
@@ -96 +90 @@
                 primitives.add(w);
                 errors.add( new TestError(this, Severity.OTHER, errortype, type, primitives) );
-                errorWays.add(w,w);
             }
         }

trunk/src/org/openstreetmap/josm/gui/dialogs/validator/ValidatorTreePanel.java

@@ -8 +8 @@
 import java.util.HashMap;
 import java.util.HashSet;
+import java.util.LinkedHashSet;
 import java.util.List;
 import java.util.Map;
@@ -23 +24 @@
 import org.openstreetmap.josm.data.validation.Severity;
 import org.openstreetmap.josm.data.validation.TestError;
-import org.openstreetmap.josm.data.validation.util.Bag;
 import org.openstreetmap.josm.data.validation.util.MultipleNameVisitor;
+import org.openstreetmap.josm.tools.MultiMap;
 
 /**
@@ -138 +139 @@
         }
 
-        Map<Severity, Bag<String, TestError>> errorTree = new HashMap<Severity, Bag<String, TestError>>();
-        Map<Severity, HashMap<String, Bag<String, TestError>>> errorTreeDeep = new HashMap<Severity, HashMap<String, Bag<String, TestError>>>();
+        Map<Severity, MultiMap<String, TestError>> errorTree = new HashMap<Severity, MultiMap<String, TestError>>();
+        Map<Severity, HashMap<String, MultiMap<String, TestError>>> errorTreeDeep = new HashMap<Severity, HashMap<String, MultiMap<String, TestError>>>();
         for (Severity s : Severity.values()) {
-            errorTree.put(s, new Bag<String, TestError>(20));
-            errorTreeDeep.put(s, new HashMap<String, Bag<String, TestError>>());
+            errorTree.put(s, new MultiMap<String, TestError>(20));
+            errorTreeDeep.put(s, new HashMap<String, MultiMap<String, TestError>>());
         }
 
@@ -165 +166 @@
             }
             if (d != null) {
-                Bag<String, TestError> b = errorTreeDeep.get(s).get(m);
+                MultiMap<String, TestError> b = errorTreeDeep.get(s).get(m);
                 if (b == null) {
-                    b = new Bag<String, TestError>(20);
+                    b = new MultiMap<String, TestError>(20);
                     errorTreeDeep.get(s).put(m, b);
                 }
-                b.add(d, e);
+                b.put(d, e);
             } else {
-                errorTree.get(s).add(m, e);
+                errorTree.get(s).put(m, e);
             }
         }
@@ -178 +179 @@
         List<TreePath> expandedPaths = new ArrayList<TreePath>();
         for (Severity s : Severity.values()) {
-            Bag<String, TestError> severityErrors = errorTree.get(s);
-            Map<String, Bag<String, TestError>> severityErrorsDeep = errorTreeDeep.get(s);
+            MultiMap<String, TestError> severityErrors = errorTree.get(s);
+            Map<String, MultiMap<String, TestError>> severityErrorsDeep = errorTreeDeep.get(s);
             if (severityErrors.isEmpty() && severityErrorsDeep.isEmpty()) {
                 continue;
@@ -192 +193 @@
             }
 
-            for (Entry<String, List<TestError>> msgErrors : severityErrors.entrySet()) {
+            for (Entry<String, LinkedHashSet<TestError>> msgErrors : severityErrors.entrySet()) {
                 // Message node
-                List<TestError> errs = msgErrors.getValue();
+                Set<TestError> errs = msgErrors.getValue();
                 String msg = msgErrors.getKey() + " (" + errs.size() + ")";
                 DefaultMutableTreeNode messageNode = new DefaultMutableTreeNode(msg);
@@ -209 +210 @@
                 }
             }
-            for (Entry<String, Bag<String, TestError>> bag : severityErrorsDeep.entrySet()) {
+            for (Entry<String, MultiMap<String, TestError>> bag : severityErrorsDeep.entrySet()) {
                 // Group node
-                Bag<String, TestError> errorlist = bag.getValue();
+                MultiMap<String, TestError> errorlist = bag.getValue();
                 DefaultMutableTreeNode groupNode = null;
                 if (errorlist.size() > 1) {
@@ -222 +223 @@
                 }
 
-                for (Entry<String, List<TestError>> msgErrors : errorlist.entrySet()) {
+                for (Entry<String, LinkedHashSet<TestError>> msgErrors : errorlist.entrySet()) {
                     // Message node
-                    List<TestError> errs = msgErrors.getValue();
+                    Set<TestError> errs = msgErrors.getValue();
                     String msg;
                     if (groupNode != null) {

trunk/src/org/openstreetmap/josm/gui/layer/ValidatorLayer.java

@@ -19 +19 @@
 import org.openstreetmap.josm.data.validation.Severity;
 import org.openstreetmap.josm.data.validation.TestError;
-import org.openstreetmap.josm.data.validation.util.Bag;
 import org.openstreetmap.josm.gui.MapView;
 import org.openstreetmap.josm.gui.MapView.LayerChangeListener;
@@ -25 +24 @@
 import org.openstreetmap.josm.gui.dialogs.LayerListPopup;
 import org.openstreetmap.josm.tools.ImageProvider;
+import org.openstreetmap.josm.tools.MultiMap;
 
 /**
@@ -78 +78 @@
     @Override
     public String getToolTipText() {
-        Bag<Severity, TestError> errorTree = new Bag<Severity, TestError>();
+        MultiMap<Severity, TestError> errorTree = new MultiMap<Severity, TestError>();
         List<TestError> errors = Main.map.validatorDialog.tree.getErrors();
         for (TestError e : errors) {
-            errorTree.add(e.getSeverity(), e);
+            errorTree.put(e.getSeverity(), e);
         }
 

trunk/src/org/openstreetmap/josm/tools/MultiMap.java

@@ -2 +2 @@
 package org.openstreetmap.josm.tools;
 
+import java.util.Collection;
 import java.util.HashMap;
 import java.util.LinkedHashSet;
 import java.util.Map;
+import java.util.Map.Entry;
 import java.util.Set;
 
 /**
- * Maps keys to ordered sets of values.
+ * MultiMap - maps keys to multiple values
+ *
+ * Corresponds to Google guava LinkedHashMultimap and Apache Collections MultiValueMap
+ * but it is an independent (simplistic) implementation.
+ *
  */
-public class MultiMap<A, B>  {
+public class MultiMap<A, B> {
 
-    private final Map<A, LinkedHashSet<B>> map = new HashMap<A, LinkedHashSet<B>>();
+    private final Map<A, LinkedHashSet<B>> map;
+
+    public MultiMap() {
+        map = new HashMap<A, LinkedHashSet<B>>();
+    }
+
+    public MultiMap(int capacity) {
+        map = new HashMap<A, LinkedHashSet<B>>(capacity);
+    }
+
     /**
      * Map a key to a value. Can be called multiple times with the same key, but different value.
@@ -26 +41 @@
 
     /**
-     * Put a key that maps to nothing.
+     * Put a key that maps to nothing. (Only if it is not already in the map)
+     * Afterwards containsKey(key) will return true and get(key) will return
+     * an empty Set instead of null.
      */
     public void putVoid(A key) {
@@ -35 +52 @@
 
     /**
-     * Returns a list of values for the given key
-     * or an empty list, if it maps to nothing.
+     * Get the keySet
+     */
+    public Set<A> keySet() {
+        return map.keySet();
+    }
+
+    /**
+     * Return the Set associated with the given key. Result is null if
+     * nothing has been mapped to this key. Modifications of the returned list
+     * changes the underling map, but you should better not do that.
+     */
+    public Set<B> get(A key) {
+        return map.get(key);
+    }
+
+    /**
+     * Like get, but returns an empty Set if nothing has been mapped to the key.
      */
     public LinkedHashSet<B> getValues(A key) {
@@ -44 +76 @@
     }
 
-    public Set<A> keySet() {
-        return map.keySet();
+    public boolean isEmpty() {
+        return map.isEmpty();
     }
 
-    public Set<B> get(A key) {
-        return map.get(key);
+    public boolean containsKey(A key) {
+        return map.containsKey(key);
+    }
+
+    /**
+     * Returns true if the multimap contains a value for a key
+     * @param key The key
+     * @param value The value
+     * @return true if the key contains the value
+     */
+    public boolean contains(A key, B value) {
+        Set<B> values = get(key);
+        return (values == null) ? false : values.contains(value);
+    }
+
+    public void clear() {
+        map.clear();
+    }
+
+    public Set<Entry<A, LinkedHashSet<B>>> entrySet() {
+        return map.entrySet();
+    }
+
+    /**
+     * number of keys
+     */
+    public int size() {
+        return map.size();
+    }
+
+    /**
+     * returns a collection of all value sets
+     */
+    public Collection<LinkedHashSet<B>> values() {
+        return map.values();
     }
 }

trunk/src/org/openstreetmap/josm/tools/Utils.java

@@ -11 +11 @@
         return false;
     }
+
+    /**
+     * Get minimum of 3 values
+     */
+    public static int min(int a, int b, int c) {
+        if (b < c) {
+            if (a < b)
+                return a;
+            return b;
+        } else {
+            if (a < c) {
+                return a;
+            }
+            return c;
+        }
+    }
 }