Index: /trunk/src/org/openstreetmap/josm/actions/search/SearchAction.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/actions/search/SearchAction.java	(revision 2789)
+++ /trunk/src/org/openstreetmap/josm/actions/search/SearchAction.java	(revision 2790)
@@ -12,4 +12,5 @@
 import java.util.Collection;
 import java.util.Collections;
+import java.util.HashSet;
 import java.util.LinkedList;
 import java.util.List;
@@ -201,6 +202,6 @@
     }
 
-    public static Integer getSelection(SearchSetting s, Collection<OsmPrimitive> sel, Function f) {
-        Integer foundMatches = 0;
+    public static int getSelection(SearchSetting s, Collection<OsmPrimitive> sel, Function f) {
+        int foundMatches = 0;
         try {
             String searchText = s.text;
@@ -211,5 +212,9 @@
             /*System.out.println(searchText);*/
             SearchCompiler.Match matcher = SearchCompiler.compile(searchText, s.caseSensitive, s.regexSearch);
-            foundMatches = 0;
+
+            if (s.mode == SearchMode.replace) {
+                sel.clear();
+            }
+
             for (OsmPrimitive osm : Main.main.getCurrentDataSet().allNonDeletedCompletePrimitives()) {
                 if (s.mode == SearchMode.replace) {
@@ -217,6 +222,4 @@
                         sel.add(osm);
                         ++foundMatches;
-                    } else {
-                        sel.remove(osm);
                     }
                 } else if (s.mode == SearchMode.add && !f.isSomething(osm) && matcher.match(osm)) {
@@ -262,5 +265,5 @@
 
         final DataSet ds = Main.main.getCurrentDataSet();
-        Collection<OsmPrimitive> sel = ds.getSelected();
+        Collection<OsmPrimitive> sel = new HashSet<OsmPrimitive>(ds.getSelected());
         int foundMatches = getSelection(s, sel, new Function(){
             public Boolean isSomething(OsmPrimitive o){