Index: src/World.cpp
===================================================================
--- src/World.cpp	(revision 40f92823967a356c96216f245f50835157d08ba3)
+++ src/World.cpp	(revision 127a8ed2e2c789fb778e76459224ec0726bd9de4)
@@ -25,4 +25,5 @@
 #include "Box.hpp"
 #include "Matrix.hpp"
+#include "defs.hpp"
 
 #include "Patterns/Singleton_impl.hpp"
@@ -121,6 +122,7 @@
   molecule *mol = NULL;
   mol = NewMolecule();
-  ASSERT(!molecules.count(currMoleculeId),"currMoleculeId did not specify an unused ID");
-  mol->setId(currMoleculeId++);
+  moleculeId_t id = getNextMoleculeId();
+  ASSERT(!molecules.count(id),"proposed id did not specify an unused ID");
+  mol->setId(id);
   // store the molecule by ID
   molecules[mol->getId()] = mol;
@@ -140,4 +142,5 @@
   DeleteMolecule(mol);
   molecules.erase(id);
+  releaseMoleculeId(id);
 }
 
@@ -145,4 +148,5 @@
   OBSERVE;
   atomId_t id = getNextAtomId();
+  ASSERT(!atoms.count(id),"proposed id did not specify an unused ID");
   atom *res = NewAtom(id);
   res->setWorld(this);
@@ -221,46 +225,198 @@
 
 atomId_t World::getNextAtomId(){
-  // see if we can reuse some Id
-  if(atomIdPool.empty()){
-    return currAtomId++;
-  }
-  else{
-    // we give out the first ID from the pool
-    atomId_t id = *(atomIdPool.begin());
-    atomIdPool.erase(id);
+  // try to find an Id in the pool;
+  if(!atomIdPool.empty()){
+    atomIdPool_t::iterator iter=atomIdPool.begin();
+    atomId_t id = iter->first;
+    pair<atomId_t,atomId_t> newRange = make_pair(id+1,iter->second);
+    // we wont use this iterator anymore, so we don't care about invalidating
+    atomIdPool.erase(iter);
+    if(newRange.first<newRange.second){
+      atomIdPool.insert(newRange);
+    }
     return id;
   }
+  // Nothing in the pool... we are out of luck
+  return currAtomId++;
 }
 
 void World::releaseAtomId(atomId_t id){
-  atomIdPool.insert(id);
-  // defragmentation of the pool
-  set<atomId_t>::reverse_iterator iter;
-  // go through all Ids in the pool that lie immediately below the border
-  while(!atomIdPool.empty() && *(atomIdPool.rbegin())==(currAtomId-1)){
-    atomIdPool.erase(--currAtomId);
-  }
+  atomIdPool.insert(make_pair(id,id+1));
+  defragAtomIdPool();
 }
 
 bool World::reserveAtomId(atomId_t id){
   if(id>=currAtomId ){
-    // add all ids between the new one and current border as available
-    for(atomId_t pos=currAtomId; pos<id; ++pos){
-      atomIdPool.insert(pos);
+    pair<atomId_t,atomId_t> newRange = make_pair(currAtomId,id);
+    if(newRange.first<newRange.second){
+      atomIdPool.insert(newRange);
     }
     currAtomId=id+1;
+    defragAtomIdPool();
     return true;
   }
-  else if(atomIdPool.count(id)){
-    atomIdPool.erase(id);
+  // look for a range that matches the request
+  for(atomIdPool_t::iterator iter=atomIdPool.begin();iter!=atomIdPool.end();++iter){
+    if(iter->first>id){
+      // we have coverd all available ranges... nothing to be found here
+      break;
+    }
+    // no need to check first, since it has to be <=id, since otherwise we would have broken out
+    if(iter->second > id){
+      // we found a matching range... get the id from this range
+
+      // split up this range at the point of id
+      pair<atomId_t,atomId_t> bottomRange = make_pair(iter->first,id);
+      pair<atomId_t,atomId_t> topRange = make_pair(id+1,iter->second);
+      // remove this range
+      atomIdPool.erase(iter);
+      if(bottomRange.first<bottomRange.second){
+        atomIdPool.insert(bottomRange);
+      }
+      if(topRange.first<topRange.second){
+        atomIdPool.insert(topRange);
+      }
+      defragAtomIdPool();
+      return true;
+    }
+  }
+  // this ID could not be reserved
+  return false;
+}
+
+void World::defragAtomIdPool(){
+  // check if the situation is bad enough to make defragging neccessary
+  if((numAtomDefragSkips<MAX_FRAGMENTATION_SKIPS) &&
+     (atomIdPool.size()<lastAtomPoolSize+MAX_POOL_FRAGMENTATION)){
+    ++numAtomDefragSkips;
+    return;
+  }
+  for(atomIdPool_t::iterator iter = atomIdPool.begin();iter!=atomIdPool.end();){
+    // see if this range is adjacent to the next one
+    atomIdPool_t::iterator next = iter;
+    next++;
+    if(next!=atomIdPool.end() && (next->first==iter->second)){
+      // merge the two ranges
+      pair<atomId_t,atomId_t> newRange = make_pair(iter->first,next->second);
+      atomIdPool.erase(iter);
+      atomIdPool.erase(next);
+      pair<atomIdPool_t::iterator,bool> res = atomIdPool.insert(newRange);
+      ASSERT(res.second,"Id-Pool was confused");
+      iter=res.first;
+      continue;
+    }
+    ++iter;
+  }
+  if(!atomIdPool.empty()){
+    // check if the last range is at the border
+    atomIdPool_t::iterator iter = atomIdPool.end();
+    iter--;
+    if(iter->second==currAtomId){
+      currAtomId=iter->first;
+      atomIdPool.erase(iter);
+    }
+  }
+  lastAtomPoolSize=atomIdPool.size();
+  numAtomDefragSkips=0;
+}
+
+// Molecules
+
+moleculeId_t World::getNextMoleculeId(){
+  // try to find an Id in the pool;
+  if(!moleculeIdPool.empty()){
+    moleculeIdPool_t::iterator iter=moleculeIdPool.begin();
+    moleculeId_t id = iter->first;
+    pair<moleculeId_t,moleculeId_t> newRange = make_pair(id+1,iter->second);
+    // we wont use this iterator anymore, so we don't care about invalidating
+    moleculeIdPool.erase(iter);
+    if(newRange.first<newRange.second){
+      moleculeIdPool.insert(newRange);
+    }
+    return id;
+  }
+  // Nothing in the pool... we are out of luck
+  return currMoleculeId++;
+}
+
+void World::releaseMoleculeId(moleculeId_t id){
+  moleculeIdPool.insert(make_pair(id,id+1));
+  defragMoleculeIdPool();
+}
+
+bool World::reserveMoleculeId(moleculeId_t id){
+  if(id>=currMoleculeId ){
+    pair<moleculeId_t,moleculeId_t> newRange = make_pair(currMoleculeId,id);
+    if(newRange.first<newRange.second){
+      moleculeIdPool.insert(newRange);
+    }
+    currMoleculeId=id+1;
+    defragMoleculeIdPool();
     return true;
   }
-  else{
-    // this ID could not be reserved
-    return false;
-  }
-}
-
-// Molecules
+  // look for a range that matches the request
+  for(moleculeIdPool_t::iterator iter=moleculeIdPool.begin();iter!=moleculeIdPool.end();++iter){
+    if(iter->first>id){
+      // we have coverd all available ranges... nothing to be found here
+      break;
+    }
+    // no need to check first, since it has to be <=id, since otherwise we would have broken out
+    if(iter->second > id){
+      // we found a matching range... get the id from this range
+
+      // split up this range at the point of id
+      pair<moleculeId_t,moleculeId_t> bottomRange = make_pair(iter->first,id);
+      pair<moleculeId_t,moleculeId_t> topRange = make_pair(id+1,iter->second);
+      // remove this range
+      moleculeIdPool.erase(iter);
+      if(bottomRange.first<bottomRange.second){
+        moleculeIdPool.insert(bottomRange);
+      }
+      if(topRange.first<topRange.second){
+        moleculeIdPool.insert(topRange);
+      }
+      defragMoleculeIdPool();
+      return true;
+    }
+  }
+  // this ID could not be reserved
+  return false;
+}
+
+void World::defragMoleculeIdPool(){
+  // check if the situation is bad enough to make defragging neccessary
+  if((numMoleculeDefragSkips<MAX_FRAGMENTATION_SKIPS) &&
+     (moleculeIdPool.size()<lastMoleculePoolSize+MAX_POOL_FRAGMENTATION)){
+    ++numMoleculeDefragSkips;
+    return;
+  }
+  for(moleculeIdPool_t::iterator iter = moleculeIdPool.begin();iter!=moleculeIdPool.end();){
+    // see if this range is adjacent to the next one
+    moleculeIdPool_t::iterator next = iter;
+    next++;
+    if(next!=moleculeIdPool.end() && (next->first==iter->second)){
+      // merge the two ranges
+      pair<moleculeId_t,moleculeId_t> newRange = make_pair(iter->first,next->second);
+      moleculeIdPool.erase(iter);
+      moleculeIdPool.erase(next);
+      pair<moleculeIdPool_t::iterator,bool> res = moleculeIdPool.insert(newRange);
+      ASSERT(res.second,"Id-Pool was confused");
+      iter=res.first;
+      continue;
+    }
+    ++iter;
+  }
+  if(!moleculeIdPool.empty()){
+    // check if the last range is at the border
+    moleculeIdPool_t::iterator iter = moleculeIdPool.end();
+    iter--;
+    if(iter->second==currMoleculeId){
+      currMoleculeId=iter->first;
+      moleculeIdPool.erase(iter);
+    }
+  }
+  lastMoleculePoolSize=moleculeIdPool.size();
+  numMoleculeDefragSkips=0;
+}
 
 /******************************* Iterators ********************************/
@@ -322,4 +478,6 @@
     atoms(this),
     currAtomId(0),
+    lastAtomPoolSize(0),
+    numAtomDefragSkips(0),
     molecules(),
     currMoleculeId(0),
Index: src/World.hpp
===================================================================
--- src/World.hpp	(revision 40f92823967a356c96216f245f50835157d08ba3)
+++ src/World.hpp	(revision 127a8ed2e2c789fb778e76459224ec0726bd9de4)
@@ -288,4 +288,10 @@
   void releaseAtomId(atomId_t);
   bool reserveAtomId(atomId_t);
+  void defragAtomIdPool();
+
+  moleculeId_t getNextMoleculeId();
+  void releaseMoleculeId(moleculeId_t);
+  bool reserveMoleculeId(moleculeId_t);
+  void defragMoleculeIdPool();
 
   periodentafel *periode;
@@ -298,8 +304,22 @@
   AtomSet atoms;
 private:
-  std::set<atomId_t> atomIdPool; //<!stores the pool for all available AtomIds below currAtomId
+  typedef std::set<std::pair<atomId_t, atomId_t> > atomIdPool_t;
+
+  /**
+   * stores the pool for all available AtomIds below currAtomId
+   *
+   * The pool contains ranges of free ids in the form [bottom,top).
+   */
+  atomIdPool_t atomIdPool;
   atomId_t currAtomId; //!< stores the next available Id for atoms
+  size_t lastAtomPoolSize; //!< size of the pool after last defrag, to skip some defrags
+  unsigned int numAtomDefragSkips;
+
   MoleculeSet molecules;
+  typedef std::set<std::pair<moleculeId_t, moleculeId_t> > moleculeIdPool_t;
+  moleculeIdPool_t moleculeIdPool;
   moleculeId_t currMoleculeId;
+  size_t lastMoleculePoolSize; //!< size of the pool after last defrag, to skip some defrags
+  unsigned int numMoleculeDefragSkips;
 private:
   /**
Index: src/defs.hpp
===================================================================
--- src/defs.hpp	(revision 40f92823967a356c96216f245f50835157d08ba3)
+++ src/defs.hpp	(revision 127a8ed2e2c789fb778e76459224ec0726bd9de4)
@@ -84,3 +84,6 @@
 #define MOLECUILDER_NAME "Molecuilder"
 
+const unsigned int MAX_POOL_FRAGMENTATION=20;
+const unsigned int MAX_FRAGMENTATION_SKIPS=100;
+
 #endif /*DEFS_HPP_*/
