deleted file mode 100644

@@ -1,72 +0,0 @@

-#ifndef __COGAPS_ATOMIC_DOMAIN_H__

-#define __COGAPS_ATOMIC_DOMAIN_H__

-

-#include "AtomAllocator.h"

-#include "data_structures/HashSets.h"

-#include "math/Random.h"

-#include "math/SIMD.h"

-#include "utils/Archive.h"

-

-#include <vector>

-

-struct AtomNeighborhood

-{

-    Atom* center;

-    Atom* left;

-    Atom* right;

-

-    AtomNeighborhood();

-    AtomNeighborhood(Atom *l, Atom *c, Atom *r);

-

-    bool hasLeft();

-    bool hasRight();

-};

-

-class ProposalQueue; // needed for friend

-

-class AtomicDomain

-{

-public:

-

-    AtomicDomain(uint64_t nBins);

-

-    // TODO can we have internal rng since these are always called sequentially

-    // access atoms

-    Atom* front();

-    Atom* randomAtom(GapsRng *rng);

-    AtomNeighborhood randomAtomWithNeighbors(GapsRng *rng);

-    AtomNeighborhood randomAtomWithRightNeighbor(GapsRng *rng);

-

-    uint64_t randomFreePosition(GapsRng *rng) const;

-    uint64_t size() const;

-

-    // this needs to happen concurrently without invalidating pointers

-    void erase(uint64_t pos);

-

-    // serialization

-    friend Archive& operator<<(Archive &ar, AtomicDomain &domain);

-    friend Archive& operator>>(Archive &ar, AtomicDomain &domain);

-   

-#ifdef GAPS_DEBUG

-    std::vector<Atom*>::iterator begin();

-    std::vector<Atom*>::iterator end();

-    bool isSorted();

-#endif

-

-#ifndef GAPS_INTERNAL_TESTS

-private:

-#endif

-

-    // only the proposal queue can insert

-    friend class ProposalQueue;

-    Atom* insert(uint64_t pos, float mass);

-

-    // size of atomic domain to ensure all bins are equal length

-    uint64_t mDomainLength;

-

-    // domain storage, sorted vector of pointers to atoms created by allocator

-    std::vector<Atom*> mAtoms;

-    AtomAllocator mAllocator;

-};

-

-#endif // __COGAPS_ATOMIC_DOMAIN_H__

@@ -30,6 +30,7 @@ public:

     AtomicDomain(uint64_t nBins);

+    // TODO can we have internal rng since these are always called sequentially

     // access atoms

     Atom* front();

     Atom* randomAtom(GapsRng *rng);

@@ -47,8 +47,8 @@ public:

     friend Archive& operator>>(Archive &ar, AtomicDomain &domain);

 #ifdef GAPS_DEBUG

-    std::vector<Atom*>::iterator begin() { return mAtoms.begin(); }

-    std::vector<Atom*>::iterator end() { return mAtoms.end(); }

+    std::vector<Atom*>::iterator begin();

+    std::vector<Atom*>::iterator end();

     bool isSorted();

 #endif

@@ -1,26 +1,14 @@

 #ifndef __COGAPS_ATOMIC_DOMAIN_H__

 #define __COGAPS_ATOMIC_DOMAIN_H__

+#include "AtomAllocator.h"

 #include "data_structures/HashSets.h"

 #include "math/Random.h"

+#include "math/SIMD.h"

 #include "utils/Archive.h"

 #include <vector>

-struct Atom

-{

-    uint64_t pos;

-    float mass;

-

-    Atom();

-    Atom(uint64_t p, float m);

-

-    void operator=(Atom other);

-

-    friend Archive& operator<<(Archive& ar, Atom &a);

-    friend Archive& operator>>(Archive& ar, Atom &a);

-};

-

 struct AtomNeighborhood

 {

     Atom* center;

@@ -41,34 +29,28 @@ class AtomicDomain

 public:

     AtomicDomain(uint64_t nBins);

-    ~AtomicDomain();

     // access atoms

     Atom* front();

-    Atom* randomAtom(GapsRng *rng, const SmallPairedHashSetU64 &moves);

+    Atom* randomAtom(GapsRng *rng);

     AtomNeighborhood randomAtomWithNeighbors(GapsRng *rng);

-    AtomNeighborhood randomAtomWithRightNeighbor(GapsRng *rng, const SmallPairedHashSetU64 &moves);

+    AtomNeighborhood randomAtomWithRightNeighbor(GapsRng *rng);

-    Atom* getLeftNeighbor(uint64_t pos);

-    Atom* getRightNeighbor(uint64_t pos);

-

-    uint64_t randomFreePosition(GapsRng *rng,

-        const std::vector<uint64_t> &possibleDeaths) const;

+    uint64_t randomFreePosition(GapsRng *rng) const;

     uint64_t size() const;

-    // these need to happen concurrently without invalidating pointers

+    // this needs to happen concurrently without invalidating pointers

     void erase(uint64_t pos);

-    //void move(uint64_t src, uint64_t dest);

-

-    // iterators

-    std::vector<Atom*>::iterator begin() { return mAtoms.begin(); }

-    std::vector<Atom*>::iterator end() { return mAtoms.end(); }

-    

-    bool isSorted();

     // serialization

     friend Archive& operator<<(Archive &ar, AtomicDomain &domain);

     friend Archive& operator>>(Archive &ar, AtomicDomain &domain);

+   

+#ifdef GAPS_DEBUG

+    std::vector<Atom*>::iterator begin() { return mAtoms.begin(); }

+    std::vector<Atom*>::iterator end() { return mAtoms.end(); }

+    bool isSorted();

+#endif

 #ifndef GAPS_INTERNAL_TESTS

 private:

@@ -81,8 +63,9 @@ private:

     // size of atomic domain to ensure all bins are equal length

     uint64_t mDomainLength;

-    // domain storage, sorted vector

+    // domain storage, sorted vector of pointers to atoms created by allocator

     std::vector<Atom*> mAtoms;

+    AtomAllocator mAllocator;

 };

-#endif // __COGAPS_ATOMIC_DOMAIN_H__

\ No newline at end of file

+#endif // __COGAPS_ATOMIC_DOMAIN_H__

@@ -1,8 +1,9 @@

 #ifndef __COGAPS_ATOMIC_DOMAIN_H__

 #define __COGAPS_ATOMIC_DOMAIN_H__

-#include "utils/Archive.h"

+#include "data_structures/HashSets.h"

 #include "math/Random.h"

+#include "utils/Archive.h"

 #include <vector>

@@ -44,9 +45,9 @@ public:

     // access atoms

     Atom* front();

-    Atom* randomAtom(GapsRng *rng);

+    Atom* randomAtom(GapsRng *rng, const SmallPairedHashSetU64 &moves);

     AtomNeighborhood randomAtomWithNeighbors(GapsRng *rng);

-    AtomNeighborhood randomAtomWithRightNeighbor(GapsRng *rng);

+    AtomNeighborhood randomAtomWithRightNeighbor(GapsRng *rng, const SmallPairedHashSetU64 &moves);

     Atom* getLeftNeighbor(uint64_t pos);

     Atom* getRightNeighbor(uint64_t pos);

@@ -57,7 +58,7 @@ public:

     // these need to happen concurrently without invalidating pointers

     void erase(uint64_t pos);

-    void move(uint64_t src, uint64_t dest);

+    //void move(uint64_t src, uint64_t dest);

     // iterators

     std::vector<Atom*>::iterator begin() { return mAtoms.begin(); }

@@ -59,6 +59,12 @@ public:

     void erase(uint64_t pos);

     void move(uint64_t src, uint64_t dest);

+    // iterators

+    std::vector<Atom*>::iterator begin() { return mAtoms.begin(); }

+    std::vector<Atom*>::iterator end() { return mAtoms.end(); }

+    

+    bool isSorted();

+

     // serialization

     friend Archive& operator<<(Archive &ar, AtomicDomain &domain);

     friend Archive& operator>>(Archive &ar, AtomicDomain &domain);

@@ -33,6 +33,8 @@ struct AtomNeighborhood

     bool hasRight();

 };

+class ProposalQueue; // needed for friend

+

 class AtomicDomain

 {

 public:

@@ -49,12 +51,13 @@ public:

     Atom* getLeftNeighbor(uint64_t pos);

     Atom* getRightNeighbor(uint64_t pos);

-    uint64_t randomFreePosition(GapsRng *rng) const;

+    uint64_t randomFreePosition(GapsRng *rng,

+        const std::vector<uint64_t> &possibleDeaths) const;

     uint64_t size() const;

     // these need to happen concurrently without invalidating pointers

     void erase(uint64_t pos);

-    Atom* insert(uint64_t pos, float mass);

+    void move(uint64_t src, uint64_t dest);

     // serialization

     friend Archive& operator<<(Archive &ar, AtomicDomain &domain);

@@ -64,6 +67,10 @@ public:

 private:

 #endif

+    // only the proposal queue can insert

+    friend class ProposalQueue;

+    Atom* insert(uint64_t pos, float mass);

+

     // size of atomic domain to ensure all bins are equal length

     uint64_t mDomainLength;

@@ -26,6 +26,7 @@ struct AtomNeighborhood

     Atom* left;

     Atom* right;

+    AtomNeighborhood();

     AtomNeighborhood(Atom *l, Atom *c, Atom *r);

     bool hasLeft();

@@ -37,6 +38,7 @@ class AtomicDomain

 public:

     AtomicDomain(uint64_t nBins);

+    ~AtomicDomain();

     // access atoms

     Atom* front();

@@ -44,11 +46,15 @@ public:

     AtomNeighborhood randomAtomWithNeighbors(GapsRng *rng);

     AtomNeighborhood randomAtomWithRightNeighbor(GapsRng *rng);

+    Atom* getLeftNeighbor(uint64_t pos);

+    Atom* getRightNeighbor(uint64_t pos);

+

     uint64_t randomFreePosition(GapsRng *rng) const;

     uint64_t size() const;

+    // these need to happen concurrently without invalidating pointers

     void erase(uint64_t pos);

-    void insert(uint64_t pos, float mass);

+    Atom* insert(uint64_t pos, float mass);

     // serialization

     friend Archive& operator<<(Archive &ar, AtomicDomain &domain);

@@ -62,7 +68,7 @@ private:

     uint64_t mDomainLength;

     // domain storage, sorted vector

-    std::vector<Atom> mAtoms;

+    std::vector<Atom*> mAtoms;

 };

-#endif

\ No newline at end of file

+#endif // __COGAPS_ATOMIC_DOMAIN_H__

\ No newline at end of file

@@ -40,11 +40,11 @@ public:

     // access atoms

     Atom* front();

-    Atom* randomAtom();

-    AtomNeighborhood randomAtomWithNeighbors();

-    AtomNeighborhood randomAtomWithRightNeighbor();

+    Atom* randomAtom(GapsRng *rng);

+    AtomNeighborhood randomAtomWithNeighbors(GapsRng *rng);

+    AtomNeighborhood randomAtomWithRightNeighbor(GapsRng *rng);

-    uint64_t randomFreePosition() const;

+    uint64_t randomFreePosition(GapsRng *rng) const;

     uint64_t size() const;

     void erase(uint64_t pos);

@@ -63,9 +63,6 @@ private:

     // domain storage, sorted vector

     std::vector<Atom> mAtoms;

-

-    // random number generator

-    mutable GapsRng mRng;

 };

 #endif

\ No newline at end of file

@@ -1,7 +1,7 @@

 #ifndef __COGAPS_ATOMIC_DOMAIN_H__

 #define __COGAPS_ATOMIC_DOMAIN_H__

-#include "Archive.h"

+#include "utils/Archive.h"

 #include "math/Random.h"

 #include <vector>

@@ -47,11 +47,8 @@ public:

     uint64_t randomFreePosition() const;

     uint64_t size() const;

-    // modify domain

-    void cacheInsert(uint64_t pos, float mass) const;

-    void cacheErase(uint64_t pos) const;

-    void flushCache();

-    void resetCache(unsigned n);

+    void erase(uint64_t pos);

+    void insert(uint64_t pos, float mass);

     // serialization

     friend Archive& operator<<(Archive &ar, AtomicDomain &domain);

@@ -67,23 +64,8 @@ private:

     // domain storage, sorted vector

     std::vector<Atom> mAtoms;

-    // holds cache of operations

-    mutable std::vector<Atom> mInsertCache;

-    mutable std::vector<uint64_t> mEraseCache;

-

-    // current index in the operation cache

-    mutable unsigned mInsertCacheIndex;

-    mutable unsigned mEraseCacheIndex;

-

     // random number generator

     mutable GapsRng mRng;

-

-    void erase(uint64_t pos);

-    void insert(uint64_t pos, float mass);

-

-    // serialization

-    friend Archive& operator<<(Archive &ar, AtomicDomain &domain);

-    friend Archive& operator>>(Archive &ar, AtomicDomain &domain);

 };

 #endif

\ No newline at end of file

@@ -36,7 +36,7 @@ class AtomicDomain

 {

 public:

-    AtomicDomain(unsigned nBins);

+    AtomicDomain(uint64_t nBins);

     // access atoms

     Atom* front();

@@ -64,7 +64,7 @@ private:

     // size of atomic domain to ensure all bins are equal length

     uint64_t mDomainLength;

-    // domain storage, specialized hash map

+    // domain storage, sorted vector

     std::vector<Atom> mAtoms;

     // holds cache of operations

@@ -5,7 +5,6 @@

 #include "math/Random.h"

 #include <vector>

-#include <set>

 struct Atom

 {

@@ -33,147 +32,12 @@ struct AtomNeighborhood

     bool hasRight();

 };

-class AtomBucket

-{

-public:

-

-    AtomBucket();

-

-    unsigned size() const;

-    bool isEmpty() const;

-    bool contains(uint64_t pos) const;

-

-    Atom* front();

-    Atom* operator[](unsigned index);

-

-    void insert(uint64_t pos, float mass);

-    void erase(uint64_t pos);

-        

-    AtomNeighborhood getNeighbors(unsigned index);

-    AtomNeighborhood getRightNeighbor(unsigned index);

-

-    void setRightAdjacentBucket(AtomBucket *bucket);

-    void setLeftAdjacentBucket(AtomBucket *bucket);

-

-    Atom* getLeft(unsigned index);

-    Atom* getRight(unsigned index);

-

-#ifndef GAPS_INTERNAL_TESTS

-private:

-#endif

-

-    Atom mBucket[2];

-    uint32_t mSize;

-    

-    AtomBucket *mOverflow;

-    AtomBucket *mPrev;

-    AtomBucket *mNext;

-

-    void eraseFront();

-    void connectAdjacent();

-

-    Atom* back();

-

-    AtomBucket& operator=(const AtomBucket& other); // prevent copies

-    

-    friend Archive& operator<<(Archive& ar, AtomBucket &b);

-    friend Archive& operator>>(Archive& ar, AtomBucket &b);

-};

-

-struct HashMapIndex

-{

-    unsigned bucket;

-    unsigned index;

-

-    HashMapIndex(unsigned b, unsigned i) : bucket(b), index(i) {}

-};

-

-// hash map of chained AtomBuckets

-// data structure that holds atoms

-// accessing happens much more than insert/erase so more time is spent

-// up front (sorting) to save time on access

-// note that atoms can never occupy position 0

-class AtomHashMap

-{

-public:

-

-    // required that length is a multiple of expectedNumAtoms

-    AtomHashMap(unsigned expectedNumAtoms);

-    void setTotalLength(uint64_t length);

-

-    // TODO while moving the atoms cannot change the atom order, it can

-    // move an atom from one bucket to another - this moved atom must be

-    // the front atom moving to the back of the prev bucket or the back

-    // atom moving to the front of the next atom - effectively creating

-    // a reorder event - it may even need allocation

-

-    Atom* front();

-    Atom* randomAtom();

-    AtomNeighborhood randomAtomWithNeighbors();

-    AtomNeighborhood randomAtomWithRightNeighbor();

-

-    bool contains(uint64_t pos) const;

-    unsigned size() const;

-

-    void insert(uint64_t pos, float mass);

-    void erase(uint64_t pos);

-    void move(uint64_t src, uint64_t dest, float mass); // cannot reorder

-

-    Atom* getLeft(uint64_t pos);

-    Atom* getRight(uint64_t pos);

-

-    bool hasLeft(uint64_t pos);

-    bool hasRight(uint64_t pos);

-

-    void updateMass(uint64_t pos, float newMass);

-

-#ifndef GAPS_INTERNAL_TESTS

-private:

-#endif

-

-    unsigned mSize;

-    unsigned mWhichLongestBucket;

-    unsigned mLongestBucketSize;

-

-    unsigned mExpectedNumAtoms;

-

-    uint64_t mBucketLength;

-    uint64_t mTotalLength;

-

-    std::vector<AtomBucket> mHashMap;

-    std::set<unsigned> mFullBuckets; // TODO use IntFixedHashSet

-

-    // random number generator

-    mutable GapsRng mRng;

-

-    unsigned hash(uint64_t pos) const;

-    HashMapIndex getRandomIndex() const;

-

-    friend Archive& operator<<(Archive& ar, AtomHashMap &h);

-    friend Archive& operator>>(Archive& ar, AtomHashMap &h);

-};

-

-struct MoveOperation

-{

-    uint64_t src;

-    uint64_t dest;

-    float mass;

-

-    MoveOperation() : src(0), dest(0), mass(0.f) {}

-

-    MoveOperation(uint64_t s, uint64_t d, float m) :

-        src(s), dest(d), mass(m)

-    {}

-};

-

 class AtomicDomain

 {

 public:

     AtomicDomain(unsigned nBins);

-    void setDomainSize(uint64_t size);

-

     // access atoms

     Atom* front();

     Atom* randomAtom();

@@ -186,7 +50,6 @@ public:

     // modify domain

     void cacheInsert(uint64_t pos, float mass) const;

     void cacheErase(uint64_t pos) const;

-    void cacheMove(uint64_t src, uint64_t dest, float mass) const;

     void flushCache();

     void resetCache(unsigned n);

@@ -194,27 +57,30 @@ public:

     friend Archive& operator<<(Archive &ar, AtomicDomain &domain);

     friend Archive& operator>>(Archive &ar, AtomicDomain &domain);

+#ifndef GAPS_INTERNAL_TESTS

 private:

+#endif

     // size of atomic domain to ensure all bins are equal length

     uint64_t mDomainLength;

     // domain storage, specialized hash map

-    mutable AtomHashMap mAtoms;

+    std::vector<Atom> mAtoms;

     // holds cache of operations

     mutable std::vector<Atom> mInsertCache;

     mutable std::vector<uint64_t> mEraseCache;

-    mutable std::vector<MoveOperation> mMoveCache;

     // current index in the operation cache

     mutable unsigned mInsertCacheIndex;

     mutable unsigned mEraseCacheIndex;

-    mutable unsigned mMoveCacheIndex;

     // random number generator

     mutable GapsRng mRng;

+    void erase(uint64_t pos);

+    void insert(uint64_t pos, float mass);

+

     // serialization

     friend Archive& operator<<(Archive &ar, AtomicDomain &domain);

     friend Archive& operator>>(Archive &ar, AtomicDomain &domain);

@@ -55,9 +55,6 @@ public:

     void setRightAdjacentBucket(AtomBucket *bucket);

     void setLeftAdjacentBucket(AtomBucket *bucket);

-    AtomBucket& operator=(const AtomBucket& other);

-

-    unsigned getIndex(uint64_t pos);

     Atom* getLeft(unsigned index);

     Atom* getRight(unsigned index);

@@ -65,8 +62,8 @@ public:

 private:

 #endif

-    Atom mBucket;

-    bool mFull;

+    Atom mBucket[2];

+    uint32_t mSize;

     AtomBucket *mOverflow;

     AtomBucket *mPrev;

@@ -76,6 +73,8 @@ private:

     void connectAdjacent();

     Atom* back();

+

+    AtomBucket& operator=(const AtomBucket& other); // prevent copies

     friend Archive& operator<<(Archive& ar, AtomBucket &b);

     friend Archive& operator>>(Archive& ar, AtomBucket &b);

@@ -4,109 +4,218 @@

 #include "Archive.h"

 #include "math/Random.h"

-#include <boost/unordered_map.hpp>

-

-#include <cstddef>

-#include <map>

-#include <stdint.h>

 #include <vector>

+#include <set>

-class AtomicDomain;

-

-// Want the neighbors to be pointers, but can't use pointers since vector

-// is resized, shifted integers allow for 0 to be "null" and 1 to be the

-// first index. AtomicDomain is responsible for managing this correctly.

-// TODO use get/set neighbor

 struct Atom

 {

-private:    

+    uint64_t pos;

+    float mass;

-    friend class AtomicDomain;

-    uint64_t leftNdx; // shift these up 1, 0 == no neighbor

-    uint64_t rightNdx;

+    Atom();

+    Atom(uint64_t p, float m);

-public:    

+    void operator=(Atom other);

-    uint64_t pos;

-    float mass;

+    friend Archive& operator<<(Archive& ar, Atom &a);

+    friend Archive& operator>>(Archive& ar, Atom &a);

+};

-    Atom(uint64_t p, float m)

-        : leftNdx(0), rightNdx(0), pos(p), mass(m)

-    {}

+struct AtomNeighborhood

+{

+    Atom* center;

+    Atom* left;

+    Atom* right;

-    bool operator==(const Atom &other) const

-    {

-        return pos == other.pos;

-    }

+    AtomNeighborhood(Atom *l, Atom *c, Atom *r);

-    bool operator!=(const Atom &other) const

-    {

-        return !(pos == other.pos);

-    }

+    bool hasLeft();

+    bool hasRight();

+};

-    // serialization

-    friend Archive& operator<<(Archive &ar, Atom &a);

-    friend Archive& operator>>(Archive &ar, Atom &a);

+class AtomBucket

+{

+public:

+

+    AtomBucket();

+

+    unsigned size() const;

+    bool isEmpty() const;

+    bool contains(uint64_t pos) const;

+

+    Atom* front();

+    Atom* operator[](unsigned index);

+

+    void insert(uint64_t pos, float mass);

+    void erase(uint64_t pos);

+        

+    AtomNeighborhood getNeighbors(unsigned index);

+    AtomNeighborhood getRightNeighbor(unsigned index);

+

+    void setRightAdjacentBucket(AtomBucket *bucket);

+    void setLeftAdjacentBucket(AtomBucket *bucket);

+

+    AtomBucket& operator=(const AtomBucket& other);

+

+    unsigned getIndex(uint64_t pos);

+    Atom* getLeft(unsigned index);

+    Atom* getRight(unsigned index);

+

+#ifndef GAPS_INTERNAL_TESTS

+private:

+#endif

+

+    Atom mBucket;

+    bool mFull;

+    

+    AtomBucket *mOverflow;

+    AtomBucket *mPrev;

+    AtomBucket *mNext;

+

+    void eraseFront();

+    void connectAdjacent();

+

+    Atom* back();

+    

+    friend Archive& operator<<(Archive& ar, AtomBucket &b);

+    friend Archive& operator>>(Archive& ar, AtomBucket &b);

 };

-struct RawAtom

+struct HashMapIndex

 {

-    uint64_t pos;

-    float mass;

+    unsigned bucket;

+    unsigned index;

-    RawAtom() : pos(0), mass(0.f) {}

-    RawAtom(uint64_t p, float m) : pos(p), mass(m) {}

+    HashMapIndex(unsigned b, unsigned i) : bucket(b), index(i) {}

 };

+// hash map of chained AtomBuckets

 // data structure that holds atoms

-class AtomicDomain

+// accessing happens much more than insert/erase so more time is spent

+// up front (sorting) to save time on access

+// note that atoms can never occupy position 0

+class AtomHashMap

 {

+public:

+

+    // required that length is a multiple of expectedNumAtoms

+    AtomHashMap(unsigned expectedNumAtoms);

+    void setTotalLength(uint64_t length);

+

+    // TODO while moving the atoms cannot change the atom order, it can

+    // move an atom from one bucket to another - this moved atom must be

+    // the front atom moving to the back of the prev bucket or the back

+    // atom moving to the front of the next atom - effectively creating

+    // a reorder event - it may even need allocation

+

+    Atom* front();

+    Atom* randomAtom();

+    AtomNeighborhood randomAtomWithNeighbors();

+    AtomNeighborhood randomAtomWithRightNeighbor();

+

+    bool contains(uint64_t pos) const;

+    unsigned size() const;

+

+    void insert(uint64_t pos, float mass);

+    void erase(uint64_t pos);

+    void move(uint64_t src, uint64_t dest, float mass); // cannot reorder

+

+    Atom* getLeft(uint64_t pos);

+    Atom* getRight(uint64_t pos);

+

+    bool hasLeft(uint64_t pos);

+    bool hasRight(uint64_t pos);

+

+    void updateMass(uint64_t pos, float newMass);

+

+#ifndef GAPS_INTERNAL_TESTS

 private:

+#endif

-    // size of atomic domain

-    uint64_t mDomainSize;

+    unsigned mSize;

+    unsigned mWhichLongestBucket;

+    unsigned mLongestBucketSize;

-    // domain storage

-    std::vector<Atom> mAtoms;

-    std::map<uint64_t, uint64_t> mAtomPositions;

-    boost::unordered_map<uint64_t, uint64_t> mPositionLookup;

+    unsigned mExpectedNumAtoms;

-    mutable std::vector<RawAtom> mInsertCache;

-    mutable std::vector<uint64_t> mEraseCache;

+    uint64_t mBucketLength;

+    uint64_t mTotalLength;

-    mutable unsigned mInsertCacheIndex;

-    mutable unsigned mEraseCacheIndex;

+    std::vector<AtomBucket> mHashMap;

+    std::set<unsigned> mFullBuckets; // TODO use IntFixedHashSet

+    // random number generator

     mutable GapsRng mRng;

-    Atom& _left(const Atom &atom);

-    Atom& _right(const Atom &atom);

+    unsigned hash(uint64_t pos) const;

+    HashMapIndex getRandomIndex() const;

-    void erase(uint64_t pos);

-    Atom insert(uint64_t pos, float mass);

+    friend Archive& operator<<(Archive& ar, AtomHashMap &h);

+    friend Archive& operator>>(Archive& ar, AtomHashMap &h);

+};

+

+struct MoveOperation

+{

+    uint64_t src;

+    uint64_t dest;

+    float mass;

+

+    MoveOperation() : src(0), dest(0), mass(0.f) {}

+

+    MoveOperation(uint64_t s, uint64_t d, float m) :

+        src(s), dest(d), mass(m)

+    {}

+};

+class AtomicDomain

+{

 public:

-    void setDomainSize(uint64_t size) { mDomainSize = size; }

+    AtomicDomain(unsigned nBins);

+

+    void setDomainSize(uint64_t size);

     // access atoms

-    Atom front() const;

-    Atom randomAtom() const;

+    Atom* front();

+    Atom* randomAtom();

+    AtomNeighborhood randomAtomWithNeighbors();