Index: /trunk/src/org/openstreetmap/josm/actions/UploadSelectionAction.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/actions/UploadSelectionAction.java	(revision 2398)
+++ /trunk/src/org/openstreetmap/josm/actions/UploadSelectionAction.java	(revision 2399)
@@ -2,4 +2,5 @@
 package org.openstreetmap.josm.actions;
 
+import static org.openstreetmap.josm.gui.help.HelpUtil.ht;
 import static org.openstreetmap.josm.tools.I18n.tr;
 
@@ -21,5 +22,4 @@
 import org.openstreetmap.josm.data.osm.Node;
 import org.openstreetmap.josm.data.osm.OsmPrimitive;
-import org.openstreetmap.josm.data.osm.OsmPrimitiveType;
 import org.openstreetmap.josm.data.osm.Relation;
 import org.openstreetmap.josm.data.osm.Way;
@@ -33,5 +33,4 @@
 import org.openstreetmap.josm.tools.ExceptionUtil;
 import org.xml.sax.SAXException;
-import static org.openstreetmap.josm.gui.help.HelpUtil.ht;
 
 /**
@@ -326,5 +325,5 @@
                     for (OsmPrimitive p: ds.allPrimitives()) {
                         if (canceled) return;
-                        OsmPrimitive myDeletedParent = layer.data.getPrimitiveById(p.getId(), OsmPrimitiveType.from(p));
+                        OsmPrimitive myDeletedParent = layer.data.getPrimitiveById(p);
                         // our local dataset includes a deleted parent of a primitive we want
                         // to delete. Include this parent in the collection of uploaded primitives
Index: /trunk/src/org/openstreetmap/josm/command/AddPrimitivesCommand.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/command/AddPrimitivesCommand.java	(revision 2398)
+++ /trunk/src/org/openstreetmap/josm/command/AddPrimitivesCommand.java	(revision 2399)
@@ -13,5 +13,4 @@
 
 import org.openstreetmap.josm.data.osm.OsmPrimitive;
-import org.openstreetmap.josm.data.osm.OsmPrimitiveType;
 import org.openstreetmap.josm.data.osm.PrimitiveData;
 
@@ -29,5 +28,5 @@
 
         for (PrimitiveData pd:data) {
-            createdPrimitives.add(getLayer().data.getPrimitiveById(pd.getId(), OsmPrimitiveType.fromData(pd), true));
+            createdPrimitives.add(getLayer().data.getPrimitiveById(pd, true));
         }
 
@@ -41,5 +40,5 @@
     @Override public void undoCommand() {
         for (PrimitiveData p:data) {
-            getLayer().data.removePrimitive(p.getId(), OsmPrimitiveType.fromData(p));
+            getLayer().data.removePrimitive(p);
         }
     }
@@ -47,5 +46,5 @@
     @Override
     public MutableTreeNode description() {
-         return new DefaultMutableTreeNode(
+        return new DefaultMutableTreeNode(
                 new JLabel(tr("Added {0} objects", data.size()), null,
                         JLabel.HORIZONTAL
Index: /trunk/src/org/openstreetmap/josm/data/osm/DataIntegrityProblemException.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/data/osm/DataIntegrityProblemException.java	(revision 2399)
+++ /trunk/src/org/openstreetmap/josm/data/osm/DataIntegrityProblemException.java	(revision 2399)
@@ -0,0 +1,10 @@
+// License: GPL. For details, see LICENSE file.
+package org.openstreetmap.josm.data.osm;
+
+public class DataIntegrityProblemException extends RuntimeException {
+
+    public DataIntegrityProblemException(String message) {
+        super(message);
+    }
+
+}
Index: /trunk/src/org/openstreetmap/josm/data/osm/DataSet.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/data/osm/DataSet.java	(revision 2398)
+++ /trunk/src/org/openstreetmap/josm/data/osm/DataSet.java	(revision 2399)
@@ -1,4 +1,6 @@
 // License: GPL. Copyright 2007 by Immanuel Scholz and others
 package org.openstreetmap.josm.data.osm;
+
+import static org.openstreetmap.josm.tools.I18n.tr;
 
 import java.awt.geom.Area;
@@ -14,4 +16,5 @@
 import java.util.LinkedList;
 import java.util.List;
+import java.util.Map;
 import java.util.Set;
 
@@ -30,4 +33,16 @@
 public class DataSet implements Cloneable {
 
+    private static class IdHash implements Hash<PrimitiveId,OsmPrimitive> {
+
+        public int getHashCode(PrimitiveId k) {
+            return (int)k.getUniqueId() ^ k.getType().hashCode();
+        }
+
+        public boolean equals(PrimitiveId key, OsmPrimitive value) {
+            if (key == null || value == null) return false;
+            return key.getUniqueId() == value.getUniqueId() && key.getType() == value.getType();
+        }
+    }
+
     /**
      * A list of listeners to selection changed events. The list is static, as listeners register
@@ -48,4 +63,7 @@
         }
     }
+
+    private Storage<OsmPrimitive> allPrimitives = new Storage<OsmPrimitive>(new IdHash());
+    private Map<PrimitiveId, OsmPrimitive> primitivesMap = allPrimitives.foreignKey(new IdHash());
 
     /**
@@ -179,4 +197,8 @@
      */
     public void addPrimitive(OsmPrimitive primitive) {
+        if (getPrimitiveById(primitive) != null)
+            throw new DataIntegrityProblemException(
+                    tr("Unable to add primitive {0} to the dataset because it's already included", primitive.toString()));
+
         if (primitive instanceof Node) {
             nodes.add((Node) primitive);
@@ -186,21 +208,19 @@
             relations.add((Relation) primitive);
         }
+        allPrimitives.add(primitive);
     }
 
     public OsmPrimitive addPrimitive(PrimitiveData data) {
+        OsmPrimitive result;
         if (data instanceof NodeData) {
-            Node node = new Node((NodeData)data, this);
-            nodes.add(node);
-            return node;
+            result = new Node((NodeData)data, this);
         } else if (data instanceof WayData) {
-            Way way = new Way((WayData)data, this);
-            ways.add(way);
-            return way;
+            result = new Way((WayData)data, this);
         } else if (data instanceof RelationData) {
-            Relation relation = new Relation((RelationData)data, this);
-            relations.add(relation);
-            return relation;
+            result = new Relation((RelationData)data, this);
         } else
             throw new AssertionError();
+        addPrimitive(result);
+        return result;
     }
 
@@ -214,7 +234,11 @@
      * @param primitive the primitive. Ignored if null.
      */
-    public void removePrimitive(OsmPrimitive primitive) {
-        if (primitive == null)
+    public void removePrimitive(PrimitiveId primitiveId) {
+        OsmPrimitive primitive = getPrimitiveById(primitiveId);
+        if (primitive == null) {
+            System.out.println("Warning: somebody is trying to remove nonexisting primitive from the Dataset. Action will be ignored. You can report this problem on http://josm.openstreetmap.de");
+            new Exception().printStackTrace();
             return;
+        }
         if (primitive instanceof Node) {
             nodes.remove(primitive);
@@ -225,8 +249,5 @@
         }
         selectedPrimitives.remove(primitive);
-    }
-
-    public void removePrimitive(long id, OsmPrimitiveType type) {
-        removePrimitive(getPrimitiveById(id, type));
+        allPrimitives.remove(primitive);
     }
 
@@ -542,29 +563,24 @@
      */
     public OsmPrimitive getPrimitiveById(long id, OsmPrimitiveType type) {
-        return getPrimitiveById(id, type, false);
-    }
-
-    public OsmPrimitive getPrimitiveById(long id, OsmPrimitiveType type, boolean createNew) {
-        Collection<? extends OsmPrimitive> primitives = null;
-        switch(type) {
-        case NODE: primitives = nodes; break;
-        case WAY: primitives = ways; break;
-        case RELATION: primitives = relations; break;
-        }
-        for (OsmPrimitive primitive : primitives) {
-            if (primitive.getUniqueId() == id) return primitive;
-        }
-
-        if (createNew) {
-            OsmPrimitive result = null;
-            switch (type) {
-            case NODE: result = new Node(id, true); break;
-            case WAY: result = new Way(id, true); break;
-            case RELATION: result = new Relation(id, true); break;
+        return getPrimitiveById(new SimplePrimitiveId(id, type), false);
+    }
+
+    public OsmPrimitive getPrimitiveById(PrimitiveId primitiveId) {
+        return getPrimitiveById(primitiveId, false);
+    }
+
+    public OsmPrimitive getPrimitiveById(PrimitiveId primitiveId, boolean createNew) {
+        OsmPrimitive result = primitivesMap.get(primitiveId);
+
+        if (result == null && createNew) {
+            switch (primitiveId.getType()) {
+            case NODE: result = new Node(primitiveId.getUniqueId(), true); break;
+            case WAY: result = new Way(primitiveId.getUniqueId(), true); break;
+            case RELATION: result = new Relation(primitiveId.getUniqueId(), true); break;
             }
             addPrimitive(result);
-            return result;
-        } else
-            return null;
+        }
+
+        return result;
     }
 
Index: /trunk/src/org/openstreetmap/josm/data/osm/Hash.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/data/osm/Hash.java	(revision 2399)
+++ /trunk/src/org/openstreetmap/josm/data/osm/Hash.java	(revision 2399)
@@ -0,0 +1,54 @@
+/*
+ *  JOSMng - a Java Open Street Map editor, the next generation.
+ * 
+ *  Copyright (C) 2008 Petr Nejedly <P.Nejedly@sh.cvut.cz>
+ *
+ *  This program is free software; you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation; either version 2 of the License, or
+ *  (at your option) any later version.
+ *
+ *  This program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+
+ *  You should have received a copy of the GNU General Public License along
+ *  with this program; if not, write to the Free Software Foundation, Inc.,
+ *  51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
+ */
+
+package org.openstreetmap.josm.data.osm;
+
+/**
+ * An interface allowing injection of hashcode and equality implementation
+ * based on some inner state of an object for a set.
+ * It supports two type parameters to implement effective foreign key implementation
+ * inside (@link Storage}, but for basic use, both type parameters are the same.
+ * 
+ * For use cases, see {@link Storage}.
+ * @author nenik
+ */
+public interface Hash<K,T> {
+    
+    /**
+     * Get hashcode for given instance, based on some inner state of the
+     * instance. The returned hashcode should remain constant over the time,
+     * so it should be based on some instance invariant.
+     * 
+     * @param k the object to compute hashcode for
+     * @return computed hashcode
+     */
+    public int getHashCode(K k);
+    
+    /**
+     * Compare two instances for semantic or lookup equality. For use cases
+     * where it compares different types, refer to {@link Storage}.
+     * 
+     * @param k the object to compare
+     * @param t the object to compare
+     * @return true if the objects are semantically equivalent, or if k
+     * uniquely identifies t in given class.
+     */
+    public boolean equals(K k, T t);
+}
Index: /trunk/src/org/openstreetmap/josm/data/osm/Node.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/data/osm/Node.java	(revision 2398)
+++ /trunk/src/org/openstreetmap/josm/data/osm/Node.java	(revision 2399)
@@ -139,3 +139,7 @@
         return formatter.format(this);
     }
+
+    public OsmPrimitiveType getType() {
+        return OsmPrimitiveType.NODE;
+    }
 }
Index: /trunk/src/org/openstreetmap/josm/data/osm/NodeData.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/data/osm/NodeData.java	(revision 2398)
+++ /trunk/src/org/openstreetmap/josm/data/osm/NodeData.java	(revision 2399)
@@ -59,3 +59,7 @@
     }
 
+    public OsmPrimitiveType getType() {
+        return OsmPrimitiveType.NODE;
+    }
+
 }
Index: /trunk/src/org/openstreetmap/josm/data/osm/OsmPrimitive.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/data/osm/OsmPrimitive.java	(revision 2398)
+++ /trunk/src/org/openstreetmap/josm/data/osm/OsmPrimitive.java	(revision 2399)
@@ -10,5 +10,4 @@
 import java.util.Date;
 import java.util.HashMap;
-import java.util.HashSet;
 import java.util.LinkedHashSet;
 import java.util.LinkedList;
@@ -16,5 +15,4 @@
 import java.util.Locale;
 import java.util.Map;
-import java.util.Set;
 import java.util.Map.Entry;
 import java.util.concurrent.atomic.AtomicLong;
@@ -35,5 +33,5 @@
  * @author imi
  */
-abstract public class OsmPrimitive implements Comparable<OsmPrimitive>, Tagged {
+abstract public class OsmPrimitive implements Comparable<OsmPrimitive>, Tagged, PrimitiveId {
 
     private static final AtomicLong idCounter = new AtomicLong(0);
Index: /trunk/src/org/openstreetmap/josm/data/osm/PrimitiveData.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/data/osm/PrimitiveData.java	(revision 2398)
+++ /trunk/src/org/openstreetmap/josm/data/osm/PrimitiveData.java	(revision 2399)
@@ -15,5 +15,5 @@
  *
  */
-public abstract class PrimitiveData implements Tagged {
+public abstract class PrimitiveData implements Tagged, PrimitiveId {
 
     // Useful?
@@ -169,4 +169,11 @@
     }
 
+    /**
+     * PrimitiveId implementation. Returns the same value as getId()
+     */
+    public long getUniqueId() {
+        return id;
+    }
+
 
 
Index: /trunk/src/org/openstreetmap/josm/data/osm/PrimitiveId.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/data/osm/PrimitiveId.java	(revision 2399)
+++ /trunk/src/org/openstreetmap/josm/data/osm/PrimitiveId.java	(revision 2399)
@@ -0,0 +1,10 @@
+// License: GPL. For details, see LICENSE file.
+package org.openstreetmap.josm.data.osm;
+
+public interface PrimitiveId {
+
+    long getUniqueId();
+
+    OsmPrimitiveType getType();
+
+}
Index: /trunk/src/org/openstreetmap/josm/data/osm/Relation.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/data/osm/Relation.java	(revision 2398)
+++ /trunk/src/org/openstreetmap/josm/data/osm/Relation.java	(revision 2399)
@@ -171,13 +171,13 @@
         for (RelationMemberData member : relationData.getMembers()) {
             switch (member.getMemberType()) {
-                case NODE:
-                    nodes.put(member.getMemberId(), nodeMarker);
-                    break;
-                case WAY:
-                    ways.put(member.getMemberId(), wayMarker);
-                    break;
-                case RELATION:
-                    relations.put(member.getMemberId(), relationMarker);
-                    break;
+            case NODE:
+                nodes.put(member.getMemberId(), nodeMarker);
+                break;
+            case WAY:
+                ways.put(member.getMemberId(), wayMarker);
+                break;
+            case RELATION:
+                relations.put(member.getMemberId(), relationMarker);
+                break;
             }
         }
@@ -203,19 +203,19 @@
             OsmPrimitive foundMember = null;
             switch (member.getMemberType()) {
-                case NODE:
-                    foundMember = nodes.get(member.getMemberId());
-                    if (foundMember == nodeMarker)
-                        throw new AssertionError("Data consistency problem - relation with missing member detected");
-                    break;
-                case WAY:
-                    foundMember = ways.get(member.getMemberId());
-                    if (foundMember == wayMarker)
-                        throw new AssertionError("Data consistency problem - relation with missing member detected");
-                    break;
-                case RELATION:
-                    foundMember = relations.get(member.getMemberId());
-                    if (foundMember == relationMarker)
-                        throw new AssertionError("Data consistency problem - relation with missing member detected");
-                    break;
+            case NODE:
+                foundMember = nodes.get(member.getMemberId());
+                if (foundMember == nodeMarker)
+                    throw new AssertionError("Data consistency problem - relation with missing member detected");
+                break;
+            case WAY:
+                foundMember = ways.get(member.getMemberId());
+                if (foundMember == wayMarker)
+                    throw new AssertionError("Data consistency problem - relation with missing member detected");
+                break;
+            case RELATION:
+                foundMember = relations.get(member.getMemberId());
+                if (foundMember == relationMarker)
+                    throw new AssertionError("Data consistency problem - relation with missing member detected");
+                break;
             }
             newMembers.add(new RelationMember(member.getRole(), foundMember));
@@ -340,3 +340,7 @@
         return ret;
     }
+
+    public OsmPrimitiveType getType() {
+        return OsmPrimitiveType.RELATION;
+    }
 }
Index: /trunk/src/org/openstreetmap/josm/data/osm/RelationData.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/data/osm/RelationData.java	(revision 2398)
+++ /trunk/src/org/openstreetmap/josm/data/osm/RelationData.java	(revision 2399)
@@ -37,3 +37,7 @@
     }
 
+    public OsmPrimitiveType getType() {
+        return OsmPrimitiveType.RELATION;
+    }
+
 }
Index: /trunk/src/org/openstreetmap/josm/data/osm/RelationMember.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/data/osm/RelationMember.java	(revision 2398)
+++ /trunk/src/org/openstreetmap/josm/data/osm/RelationMember.java	(revision 2399)
@@ -7,5 +7,5 @@
  *
  */
-public class RelationMember {
+public class RelationMember implements PrimitiveId {
 
     /**
@@ -157,3 +157,17 @@
             return false;
     }
+
+    /**
+     * PrimitiveId implementation. Returns the same value as getMember().getType()
+     */
+    public OsmPrimitiveType getType() {
+        return member.getType();
+    }
+
+    /**
+     * PrimitiveId implementation. Returns the same value as getMemberType().getUniqueId()
+     */
+    public long getUniqueId() {
+        return member.getUniqueId();
+    }
 }
Index: /trunk/src/org/openstreetmap/josm/data/osm/RelationMemberData.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/data/osm/RelationMemberData.java	(revision 2398)
+++ /trunk/src/org/openstreetmap/josm/data/osm/RelationMemberData.java	(revision 2399)
@@ -2,5 +2,5 @@
 package org.openstreetmap.josm.data.osm;
 
-public class RelationMemberData {
+public class RelationMemberData implements PrimitiveId {
 
     private final String role;
@@ -33,3 +33,17 @@
     }
 
+    /**
+     * PrimitiveId implementation. Returns the same value as {@link #getMemberType()}
+     */
+    public OsmPrimitiveType getType() {
+        return memberType;
+    }
+
+    /**
+     * PrimitiveId implementation. Returns the same value as {@link #getMemberId()()}
+     */
+    public long getUniqueId() {
+        return memberId;
+    }
+
 }
Index: /trunk/src/org/openstreetmap/josm/data/osm/SimplePrimitiveId.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/data/osm/SimplePrimitiveId.java	(revision 2399)
+++ /trunk/src/org/openstreetmap/josm/data/osm/SimplePrimitiveId.java	(revision 2399)
@@ -0,0 +1,24 @@
+// License: GPL. For details, see LICENSE file.
+package org.openstreetmap.josm.data.osm;
+
+public class SimplePrimitiveId implements PrimitiveId {
+
+    private final long id;
+    private final OsmPrimitiveType type;
+
+    public SimplePrimitiveId(long id, OsmPrimitiveType type) {
+        this.id = id;
+        this.type = type;
+    }
+
+    public OsmPrimitiveType getType() {
+        return type;
+    }
+
+    public long getUniqueId() {
+        return id;
+    }
+
+
+
+}
Index: /trunk/src/org/openstreetmap/josm/data/osm/Storage.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/data/osm/Storage.java	(revision 2399)
+++ /trunk/src/org/openstreetmap/josm/data/osm/Storage.java	(revision 2399)
@@ -0,0 +1,411 @@
+/*
+ *  JOSMng - a Java Open Street Map editor, the next generation.
+ *
+ *  Copyright (C) 2008 Petr Nejedly <P.Nejedly@sh.cvut.cz>
+ *
+ *  This program is free software; you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation; either version 2 of the License, or
+ *  (at your option) any later version.
+ *
+ *  This program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+
+ *  You should have received a copy of the GNU General Public License along
+ *  with this program; if not, write to the Free Software Foundation, Inc.,
+ *  51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
+ */
+
+package org.openstreetmap.josm.data.osm;
+
+import java.util.AbstractSet;
+import java.util.Collection;
+import java.util.ConcurrentModificationException;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.NoSuchElementException;
+import java.util.Set;
+
+/**
+ * A Set-like class that allows looking up equivalent preexising instance.
+ * It is useful whereever one would use self-mapping construct like
+ * <code>Map<T,T>.put(t,t), that is, for caches, uniqueness filters or similar.
+ *
+ * The semantics of equivalency can be external to the object, using the
+ * {@link Hash} interface. The set also supports querying for entries using
+ * different key type, in case you can provide a Hash implementation
+ * that can resolve the equality.
+ *
+ * <h2>Examples</h2>
+ * <ul><li>A String cache:
+ * <pre>
+ * Storage<String> cache = new Storage(); // use default Hash
+ * for (String input : data) {
+ *     String onlyOne = cache.putIfUnique(input);
+ *     ....
+ * }
+ * </pre></li>
+ * <li>Identity-based set:
+ * <pre>
+ * Storage<Object> identity = new Storage(new Hash<Object,Object> {
+ *     public int getHashCode(Object o) {
+ *         return System.identityHashCode(o);
+ *     }
+ *     public boolean equals(Object o1, Object o2) {
+ *         return o1 == o2;
+ *     }
+ *  });
+ * </pre></li>
+ * <li>An object with int ID and id-based lookup:
+ * <pre>
+ * class Thing { int id; }
+ * Storage<Thing> things = new Storage(new Hash<Thing,Thing>() {
+ *     public int getHashCode(Thing t) {
+ *         return t.id;
+ *     }
+ *     public boolean equals(Thing t1, Thing t2) {
+ *         return t1 == t2;
+ *     }
+ *  });
+ * Map<Integer,Thing> fk = things.foreignKey(new Hash<Integer,Thing>() {
+ *     public int getHashCode(Integer i) {
+ *         return i.getIntValue();
+ *     }
+ *     public boolean equals(Integer k, Thing t) {
+ *         return t.id == k.getIntvalue();
+ *     }
+ * }
+ *
+ * things.put(new Thing(3));
+ * assert things.get(new Thing(3)) == fk.get(3);
+ * </pre></li>
+*
+ *
+ * @author nenik
+ */
+public class Storage<T> extends AbstractSet<T> {
+    private final Hash<? super T,? super T> hash;
+    private Object[] data;
+    private int mask;
+    private int size;
+    private transient volatile int modCount = 0;
+    private float loadFactor = 0.6f;
+
+    public Storage() {
+        this(Storage.<T>defaultHash());
+    }
+
+    public Storage(int capacity) {
+        this(Storage.<T>defaultHash(), capacity);
+    }
+
+    public Storage(Hash<? super T,? super T> ha) {
+        this(ha, 16);
+    }
+
+    public Storage(Hash<? super T, ? super T> ha, int capacity) {
+        this.hash = ha;
+        int cap = 1 << (int)(Math.ceil(Math.log(capacity/loadFactor) / Math.log(2)));
+        data = new Object[cap];
+        mask = data.length - 1;
+    }
+
+    // --------------- Collection implementation ------------------------
+    public int size() {
+        return size;
+    }
+
+    public Iterator<T> iterator() {
+        return new Iter();
+    }
+
+    public @Override boolean contains(Object o) {
+        int bucket = getBucket(hash, (T)o);
+        return bucket >= 0;
+    }
+
+    public @Override boolean add(T t) {
+        T orig = putUnique(t);
+        return orig != t;
+    }
+
+    public @Override boolean remove(Object o) {
+        T orig = removeElem((T)o);
+        return orig != null;
+    }
+
+    public @Override void clear() {
+        modCount++;
+        size = 0;
+        for (int i = 0; i<data.length; i++) data[i] = null;
+    }
+
+    public @Override int hashCode() {
+	int h = 0;
+        for (T t : this) h += hash.getHashCode(t);
+	return h;
+    }
+
+    // ----------------- Extended API ----------------------------
+
+    public T put(T t) {
+        modCount++;
+        ensureSpace();
+
+        int bucket = getBucket(hash, t);
+        if (bucket < 0) {
+            size++;
+            bucket = ~bucket;
+            assert data[bucket] == null;
+        }
+
+        T old = (T)data[bucket];
+        data[bucket] = t;
+
+        return old;
+    }
+
+    public T get(T t) {
+        int bucket = getBucket(hash, t);
+        return bucket < 0 ? null : (T)data[bucket];
+    }
+
+    public T putUnique(T t) {
+        modCount++;
+        ensureSpace();
+
+        int bucket = getBucket(hash, t);
+        if (bucket < 0) { // unique
+            size++;
+            assert data[~bucket] == null;
+            data[~bucket] = t;
+            return t;
+        }
+
+        return (T)data[bucket];
+    }
+
+    public T removeElem(T t) {
+        modCount++;
+        int bucket = getBucket(hash, t);
+        return bucket < 0 ? null : doRemove(bucket);
+    }
+
+    public <K> Map<K,T> foreignKey(Hash<K,? super T> h) {
+        return new FMap(h);
+    }
+
+    // ---------------- Implementation
+
+    /**
+     * Additional mixing of hash
+     */
+    private int rehash(int h) {
+        //return 54435761*h;
+        return 1103515245*h >> 2;
+    }
+
+    /**
+     * Finds a bucket for given key.
+     *
+     * @param key The key to compare
+     * @return the bucket equivalent to the key or -(bucket) as an empty slot
+     * where such an entry can be stored.
+     */
+    private <K> int getBucket(Hash<K,? super T> ha, K key) {
+        T entry;
+        int hcode = rehash(ha.getHashCode(key));
+        int bucket = hcode & mask;
+        while ((entry = (T)data[bucket]) != null) {
+            if (ha.equals(key, entry)) {
+                return bucket;
+            }
+            bucket = (bucket+1) & mask;
+        }
+        return ~bucket;
+    }
+
+    private T doRemove(int slot) {
+        T t = (T)data[slot];
+        assert t != null;
+
+        fillTheHole(slot); // fill the hole (or null it)
+        size--;
+        return t;
+    }
+
+    private void fillTheHole(int hole) {
+        int bucket = (hole+1) & mask;
+        T entry;
+
+        while ((entry = (T)data[bucket]) != null) {
+            int right = rehash(hash.getHashCode(entry)) & mask;
+            // if the entry should be in <hole+1,bucket-1> (circular-wise)
+            // we can't move it. The move can be proved safe otherwise,
+            // because the entry safely belongs to <previous_null+1,hole>
+            if ((bucket < right && (right <= hole || hole <= bucket)) ||
+                    (right <=hole && hole <= bucket)) {
+
+                data[hole] = data[bucket];
+                hole = bucket;
+            }
+            bucket = (bucket+1) & mask;
+        }
+
+        // no entry belongs here, just null out the slot
+        data[hole] = null;
+    }
+
+
+
+    private void ensureSpace() {
+        if (size > data.length*loadFactor) { // rehash
+            Object[] big = new Object[data.length * 2];
+            int nMask = big.length - 1;
+
+            for (Object o : data) {
+                if (o == null) continue;
+                int bucket = rehash(hash.getHashCode((T)o)) & nMask;
+                while (big[bucket] != null) bucket = (bucket+1) & nMask;
+                big[bucket] = o;
+            }
+
+            data = big;
+            mask = nMask;
+        }
+    }
+
+
+    // -------------- factories --------------------
+    /**
+     * A factory for default hash implementation.
+     * @return a hash implementation that just delegates to object's own
+     * hashCode and equals.
+     */
+    public static <O> Hash<O,O> defaultHash() {
+        return new Hash<O,O>() {
+            public int getHashCode(O t) {
+                return t.hashCode();
+            }
+            public boolean equals(O t1, O t2) {
+                return t1.equals(t2);
+            }
+        };
+    }
+/*
+    public static <O> Hash<O,O> identityHash() {
+        return new Hash<O,O>() {
+            public int getHashCode(O t) {
+                return System.identityHashCode(t);
+            }
+            public boolean equals(O t1, O t2) {
+                return t1 == t2;
+            }
+        };
+    }
+*/
+
+    private class FMap<K> implements Map<K,T> {
+        Hash<K,? super T> fHash;
+
+        private FMap(Hash<K,? super T> h) {
+            fHash = h;
+        }
+
+        public int size() {
+            return Storage.this.size();
+        }
+
+        public boolean isEmpty() {
+            return Storage.this.isEmpty();
+        }
+
+        public boolean containsKey(Object key) {
+            int bucket = getBucket(fHash, (K)key);
+            return bucket >= 0;
+        }
+
+        public boolean containsValue(Object value) {
+            return Storage.this.contains(value);
+        }
+
+        public T get(Object key) {
+            int bucket = getBucket(fHash, (K)key);
+            return bucket < 0 ? null : (T)data[bucket];
+        }
+
+        public T put(K key, T value) {
+            if (!fHash.equals(key, value)) throw new IllegalArgumentException("inconsistent key");
+            return Storage.this.put(value);
+        }
+
+        public T remove(Object key) {
+            modCount++;
+            int bucket = getBucket(fHash,(K)key);
+
+            return bucket < 0 ? null : doRemove(bucket);
+        }
+
+        public void putAll(Map<? extends K, ? extends T> m) {
+            if (m instanceof Storage.FMap) {
+                Storage.this.addAll(((Storage.FMap)m).values());
+            } else {
+                for (Map.Entry<? extends K, ? extends T> e : m.entrySet())
+                    put(e.getKey(), e.getValue());
+            }
+        }
+
+        public void clear() {
+            Storage.this.clear();
+        }
+
+        public Set<K> keySet() {
+            throw new UnsupportedOperationException();
+        }
+
+        public Collection<T> values() {
+            return Storage.this;
+        }
+
+        public Set<Entry<K, T>> entrySet() {
+            throw new UnsupportedOperationException();
+        }
+    }
+
+    private final class Iter implements Iterator<T> {
+        private final int mods;
+        int slot = 0;
+        int removeSlot = -1;
+
+        Iter() {
+            mods = modCount;
+        }
+
+        public boolean hasNext() {
+            align();
+            return slot < data.length;
+        }
+
+        public T next() {
+            if (!hasNext()) throw new NoSuchElementException();
+            removeSlot = slot;
+            return (T)data[slot++];
+        }
+
+        public void remove() {
+            if (removeSlot == -1) throw new IllegalStateException();
+
+            doRemove(removeSlot);
+            slot = removeSlot; // some entry might have been relocated here
+            removeSlot = -1;
+        }
+
+        private void align() {
+            if (mods != modCount) throw new ConcurrentModificationException();
+            while (slot < data.length && data[slot] == null) slot++;
+        }
+    }
+
+}
Index: /trunk/src/org/openstreetmap/josm/data/osm/Way.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/data/osm/Way.java	(revision 2398)
+++ /trunk/src/org/openstreetmap/josm/data/osm/Way.java	(revision 2399)
@@ -328,3 +328,7 @@
         return formatter.format(this);
     }
+
+    public OsmPrimitiveType getType() {
+        return OsmPrimitiveType.WAY;
+    }
 }
Index: /trunk/src/org/openstreetmap/josm/data/osm/WayData.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/data/osm/WayData.java	(revision 2398)
+++ /trunk/src/org/openstreetmap/josm/data/osm/WayData.java	(revision 2399)
@@ -37,3 +37,7 @@
     }
 
+    public OsmPrimitiveType getType() {
+        return OsmPrimitiveType.WAY;
+    }
+
 }
Index: /trunk/test/functional/org/openstreetmap/josm/io/MultiFetchServerObjectReaderTest.java
===================================================================
--- /trunk/test/functional/org/openstreetmap/josm/io/MultiFetchServerObjectReaderTest.java	(revision 2398)
+++ /trunk/test/functional/org/openstreetmap/josm/io/MultiFetchServerObjectReaderTest.java	(revision 2399)
@@ -247,5 +247,5 @@
         assertEquals(10, out.getNodes().size());
         for (Node n1:out.getNodes()) {
-            Node n2 = (Node)ds.getPrimitiveById(n1.getId(), OsmPrimitiveType.NODE);
+            Node n2 = (Node)ds.getPrimitiveById(n1);
             assertNotNull(n2);
             assertEquals(n2.get("name"),n2.get("name"));
@@ -264,5 +264,5 @@
         assertEquals(10, out.getWays().size());
         for (Way w1: out.getWays()) {
-            Way w2 = (Way)ds.getPrimitiveById(w1.getId(), OsmPrimitiveType.WAY);
+            Way w2 = (Way)ds.getPrimitiveById(w1);
             assertNotNull(w2);
             assertEquals(w2.getNodesCount(), w1.getNodesCount());
@@ -300,5 +300,5 @@
         assertEquals(812, out.getNodes().size());
         for (Node n1:out.getNodes()) {
-            Node n2 = (Node)ds.getPrimitiveById(n1.getId(), OsmPrimitiveType.NODE);
+            Node n2 = (Node)ds.getPrimitiveById(n1);
             assertNotNull(n2);
             assertEquals(n2.get("name"),n2.get("name"));
@@ -319,5 +319,5 @@
         assertEquals(10, out.getNodes().size());
         for (Node n1:out.getNodes()) {
-            Node n2 = (Node)ds.getPrimitiveById(n1.getId(), OsmPrimitiveType.NODE);
+            Node n2 = (Node)ds.getPrimitiveById(n1);
             assertNotNull(n2);
             assertEquals(n2.get("name"),n2.get("name"));
Index: /trunk/test/functional/org/openstreetmap/josm/io/OsmServerBackreferenceReaderTest.java
===================================================================
--- /trunk/test/functional/org/openstreetmap/josm/io/OsmServerBackreferenceReaderTest.java	(revision 2398)
+++ /trunk/test/functional/org/openstreetmap/josm/io/OsmServerBackreferenceReaderTest.java	(revision 2399)
@@ -322,5 +322,5 @@
         Set<Long> expectedNodeIds = new HashSet<Long>();
         for (Way way : referers.getWays()) {
-            Way orig = (Way) ds.getPrimitiveById(way.getId(), OsmPrimitiveType.WAY);
+            Way orig = (Way) ds.getPrimitiveById(way);
             for (Node n : orig.getNodes()) {
                 expectedNodeIds.add(n.getId());