path: root/dep/g3dlite/include/G3D/PointHashGrid.h

/**
   \file PointHashGrid.h

   \maintainer Morgan McGuire, http://graphics.cs.williams.edu
   \created 2008-07-01
   \edited  2010-11-28

   Copyright 2000-2012, Morgan McGuire.
   All rights reserved.
*/
#ifndef G3D_PointHashGrid_h
#define G3D_PointHashGrid_h

#include "G3D/platform.h"
#include "G3D/EqualsTrait.h"
#include "G3D/HashTrait.h"
#include "G3D/Vector3.h"
#include "G3D/Vector3int32.h"
#include "G3D/Array.h"
#include "G3D/Table.h"
#include "G3D/AABox.h"
#include "G3D/Sphere.h"
#include "G3D/SmallArray.h"

namespace G3D {

/** 
    \brief A sparse 3D grid of point-based data.  
    
    The space cost for <I>n</I> elements is O(<I>n</I>).  For data with
    approximately uniform density (with respect to the radius hint),
    the time cost of searching for neighbors is O(1).

    You can move members of the data set by first removing them and then
    adding them with a new location.
    
    Template argument \a PosFunc must provide a static <code>getPosition</code> method 
    and \a EqualsFunc must provide a static <code>equals</code> method, as described below.  
    You can either write classes that support these yourself, provide template specializations of
    G3D::PositionTrait and
    G3D::EqualsTrait, or rely on the default template specializations, which already exist for
    common G3D classes like G3D::Point3.  For example:

    \code
    class PosFunc {
    public:
        static void getPosition(const Data& d, Vector3& pos) {
            pos = d.location;
        }
    };

    class EqualsFunc {
    public:
        static bool equals(const Data& p, const Data& q) {
            return p == q;
        }
    };
    
    PointHashGrid<Data, Data::PosFunc, Data::EqualsFunc> grid;
   \endcode

   If the \a Value class defines <code>operator==</code>, then the \a Equalsfunc is optional, so you can just write:

   \code
    PointHashGrid<Data, Data::PosFunc> grid;
   \endcode

   The simplest way to define these is often to make them both methods
   of the parameter class itself, e.g.,

   \code
   
    class Data {
    public:
        Point3     location;
        ...

        bool operator==(const Data& other) const {
            return (location == other.location) && ...;
        }

        static void getPosition(const Data& p, Vector3& pos) {
            pos = p.location;
        } 
   };

   typedef PointHashGrid<Data, Data> DataGrid;
   \endcode  

*/
template<class Value,
         class PosFunc    = PositionTrait<Value>, 
         class EqualsFunc = EqualsTrait<Value> >
class PointHashGrid {
private:

#   define expectedCellSize (10)

#   define ThisType PointHashGrid<Value, PosFunc, EqualsFunc>

    /** A value annotated with precomputed position and hash code.*/
    class Entry {
    public:
        Point3             position;
        Value             value;
    };

    /** One cell of the grid. */
    typedef SmallArray<Entry, expectedCellSize> Cell;
    typedef Table<Point3int32, Cell >           CellTable;

    /** The cube of +/-1 along each dimension. Initialized by initOffsetArray.*/
    Vector3int32        m_offsetArray[3*3*3];

    /** Incremented every time the data structure is mutated. 
        Used by the iterators to determine if the data structure
        has changed since iteration began. */
    int                 m_epoch;

    /** Extent of a cell along one dimension. */
    float               m_cellWidth;

    /** 1.0 / cell width */
    float               m_invCellWidth;

    /** Conservative bounds; the actual data may be smaller. */
    AABox               m_bounds;

    /** Number of elements. */
    int                 m_size;

    /** Non-empty cells indexed by grid position. Actual 3D position is 
        <code>position * m_cellWidth</code>*/
    CellTable           m_data;

    MemoryManager::Ref  m_memoryManager;

    /** Intentionally unimplemented: prevent copy construction. */
    PointHashGrid(const ThisType&);


    /** Intentionally unimplemented: prevent assignment. */
    PointHashGrid& operator=(const ThisType&);


    /** Locate the cell and index within that cell containing v. Called by
        remove() and contains(). */
    bool find
       (const Value&    v, 
        Point3int32&   foundCellCoord, 
        Cell*&          foundCell, 
        int&            index) {
        
        Point3 pos;
        PosFunc::getPosition(v, pos);

        Point3int32 cellCoord;
        getCellCoord(pos, cellCoord);
        for (int i = 0; i < 27; ++i) {
            Point3int32 c = cellCoord + m_offsetArray[i];
            Cell* cell = m_data.getPointer(c);
            if (cell != NULL) {
                // The cell exists
                for (int j = 0; j < cell->size(); ++j) {
                    if (EqualsFunc::equals((*cell)[j].value, v)) {
                        foundCell = cell;
                        index = j;
                        foundCellCoord = c;
                        return true;
                    }
                }
            }            
        }

        // Not found
        return false;        
    }

public:

    /** \brief Compute the grid cell index of a real position. 
        This is used extensively internally by PointHashGrid.
        It is useful to calling code to determine when an object
        is about to move between cells.
     */
    inline void getCellCoord(const Point3& pos, Point3int32& cellCoord) const {
        for (int a = 0; a < 3; ++a) {
            cellCoord[a] = iFloor(pos[a] * m_invCellWidth);
        }
    }

protected:

    /** Initializes m_offsetArray. */
    void initOffsetArray() {
        int i = 0;
        Point3int32 d;
        for (d.x = -1; d.x <= +1; ++d.x) {
            for (d.y = -1; d.y <= +1; ++d.y) {
                for (d.z = -1; d.z <= +1; ++d.z) {
                    m_offsetArray[i] = d;
                    ++i;
                }
            }
        }
        
        // Put (0, 0, 0) first, so that contains() is most likely to find
        // the value quickly.
        i = (1 * 3 + 1) * 3 + 1;
        debugAssert(m_offsetArray[i] == Vector3int32(0,0,0));
        Vector3int32 temp = m_offsetArray[0];
        m_offsetArray[0] = m_offsetArray[i];
        m_offsetArray[i] = temp;
    }

public:

    /** 
        \param radiusHint the radius that will typically be used with 
        beginBallIntersection and beginBoxIntersection. If two <i>Value</i>s are equal,
        their positions must be within this radius as well.  You can later change this
        value with clearAndSetRadiusHint().
    */
    PointHashGrid(float radiusHint, const MemoryManager::Ref& m = MemoryManager::create()) : m_size(0), m_memoryManager(m) {
        initOffsetArray();
        m_data.clearAndSetMemoryManager(m_memoryManager);

        debugAssertM(radiusHint > 0, "Cell radius must be positive");
        m_cellWidth = radiusHint;
        m_invCellWidth = 1.0f / m_cellWidth;
    }

    /** \sa clearAndSetRadiusHint() */
    float radiusHint() const {
        return m_cellWidth;
    }
    
    void clear(float radiusHint) {
        debugAssertM(radiusHint > 0, "Cell radius must be positive");
        clear();
        m_cellWidth = radiusHint;
        m_invCellWidth = 1.0f / m_cellWidth;
    }

    void clearAndSetRadiusHint(float radiusHint) {
        return clear(radiusHint);
    }
        
    /**
       If \a radiusHint is negative, it is automatically chosen to put 
       about 5 values in each grid cell (which means about 27 * 5 
       values for each beginIntersection call).
       
       \sa clearAndSetRadiusHint()
    */
    PointHashGrid(const Array<Value>& init, float radiusHint = -1.0f, const MemoryManager::Ref& m = MemoryManager::create()) : m_size(0), m_memoryManager(m) {        
        initOffsetArray();
        m_data.clearAndSetMemoryManager(m_memoryManager);

        Point3 lo(Vector3::inf());
        Point3 hi(-lo);

        // Compute bounds
        Array<Entry> entry(init.size());
        for (int i = 0; i < entry.size(); ++i) {
            const Value& value = init[i];
            Point3 pos;

            entry[i].value     = value;
            entry[i].hashCode  = m_hashFunc(value);
            PosFunc::getPosition(value, entry[i].position);

            lo = lo.min(pos);
            hi = hi.max(pos);
        }

        m_bounds = AABox(lo, hi);

        if (radiusHint <= 0) {
            // Compute a good cell width based on the bounds.
            //
            //   N        numPerCell
            // -----   =  ---------
            // volume        r^3

            float numPerCell = 5;
            radiusHint = 
                (float)pow(numPerCell * m_bounds.volume() / init.size(), 1.0 / 3.0);

            if (radiusHint == 0) {
                // Volume must have been zero because all points were colocated.
                radiusHint = 0.1f;
            }
        }

        insert(init);
    }

    /** Returns the number of elements. */
    int size() const {
        return m_size;
    }

    /** Returns a conservative bounding box around the contents. This is 
        conservative because it is not updated when elements are removed. */
    const AABox& conservativeBoxBounds() const {
        return m_bounds;
    }

    void debugPrintStatistics() const {
        debugPrintf("Deepest bucket size    = %d\n", (int)m_data.debugGetDeepestBucketSize());
        debugPrintf("Average bucket size    = %g\n", m_data.debugGetAverageBucketSize());
        debugPrintf("Load factor            = %g\n", m_data.debugGetLoad());
    }

    /** Insert @a v at position @a p given by <code>getPosition(v, p)</code>.  
        Multiple elements that are equal may be inserted; all copies will be
        in the data structure. */
    void insert(const Value& v) {
        Point3 pos;
        PosFunc::getPosition(v, pos);
        Point3int32 cellCoord;
        getCellCoord(pos, cellCoord);

        // See if the cell already exists
        Cell& cell = m_data.getCreate(cellCoord);

        if (cell.size() == 0) {
            // Use the same memory manager as for the whole class
            cell.clearAndSetMemoryManager(m_memoryManager);
        }

        Entry& entry    = cell.next();
        entry.value     = v;
        entry.position  = pos;

        // Update the bounds
        if (size() == 0) {
            m_bounds = AABox(pos);
        } else {
            m_bounds.merge(pos);
        }

        ++m_size;
        ++m_epoch;
    }


    /** Inserts all elements of the array. */
    void insert(const Array<Value>& v) {
        for (int i = 0; i < v.size(); ++i) {
            insert(v[i]);
        }
    }


    /** If there are multiple copies of an element, you must
        delete them multiple times.

        @param shrinkIfNecessary If <b>true</b>, deallocate underlying data 
        structures as they are emptied.  False increases performace at 
        the cost of memory overhead for dynamic structures.
        
        @return true if the element was found.
    */
    bool remove(const Value& v, bool shrinkIfNecessary = true) {
        Cell* cell = NULL;
        int   index = 0;
        Vector3int32 cellCoord;

        if (find(v, cellCoord, cell, index)) {
            cell->fastRemove(index, shrinkIfNecessary);
            --m_size;
            ++m_epoch;

            if ((cell->size() == 0) && shrinkIfNecessary) {
                // Remove the cell itself

                // Drop our pointer, which is about to dangle
                cell = NULL;
                const bool success = m_data.remove(cellCoord);
                (void)success;
                debugAssertM(success, "Data structure corrupt: "
                             "tried to remove a cell that doesn't exist.");
            }

            return true;

        } else {
            return false;
        }
    }

    /** Removes all elements of \a v. */
    void remove(const Array<Value>& v, bool shrink = true) {
        for (int i = 0; i < v.size(); ++i) {
            remove(v[i], shrink);
        }
    }

    ///////////////////////////////////////////////////////////////////////////
    ///////////////////////////////////////////////////////////////////////////

    class Iterator {
    private:
        friend class ThisType;

        bool                                    m_isEnd;

        const ThisType*                         m_grid;
        
        typename CellTable::Iterator            m_tableIterator;

        /** Index within m_tableIterator->value of the current value. */
        int                                     m_arrayIndex;

        const int                               m_epoch;

        /** End iterator. Note that the m_tableIterator is initialized to the end iterator
            of a temporary value!  This is ok because we'll never look at the value of the 
            m_tableIterator, since we're initializing the "end" Iterator.*/
        Iterator() : m_isEnd(true), m_grid(NULL), m_tableIterator(CellTable().end()), 
                     m_arrayIndex(0), m_epoch(0) {}

        Iterator(const ThisType* grid) : 
            m_isEnd(grid->size() == 0),
            m_grid(grid),
            m_tableIterator( grid->m_data.begin() ),
            m_arrayIndex(0),
            m_epoch(grid->m_epoch) { }

    private:

        const Value& value() const {
            debugAssert(! m_isEnd);
            debugAssertM(m_tableIterator->value.size() > m_arrayIndex, 
                         "No more elements");
            return m_tableIterator->value[m_arrayIndex].value;
        }

    public:

        inline bool operator!=(const Iterator& other) const {
            if (other.m_isEnd && m_isEnd) {
                return false;
            } else {
                return (m_isEnd         != other.m_isEnd) ||
                    (m_tableIterator != other.m_tableIterator) || 
                    (m_arrayIndex    != other.m_arrayIndex);
            }
        }

        bool isValid() const {
            return ! m_isEnd;
        }

        /** @deprecated  Use isValid */
        bool hasMore() const {
            return ! m_isEnd;
        }

        bool operator==(const Iterator& other) const {
            return !(*this != other);
        }

        /** Preincrement */
        Iterator& operator++() {
            debugAssert(! m_isEnd);
            debugAssertM(m_epoch == m_grid->m_epoch, 
                         "It is illegal to mutate the HashGrid "
                         "while iterating through it.");

            ++m_arrayIndex;

            if (m_arrayIndex >= m_tableIterator->value.size()) {
                // Move on to the next cell
                ++m_tableIterator;
                m_arrayIndex = 0;

                // Check to see if we're at the end
                m_isEnd = (m_tableIterator == m_grid->m_data.end());
            }

            return *this;
        }

        /** Post increment (slower) */
        Iterator operator++(int) {
            debugAssert(! m_isEnd);
            Iterator old = *this;
            ++(*this);
            return old;
        }

        const Value& operator*()  const { return  value(); }
        const Value* operator->() const { return &value(); }
        operator Value*()         const { return &value(); }
    }; // Iterator


    /** Iterate through all members.  It is an error to mutate the HashGrid 
        while iterating through it. Each member can be accessed by "dereferencing"
        the iterator:
        
        <pre>
        for (Grid::Iterator i = grid.begin(); i != grid.end(), ++i) {
        const Value& = *i;
        ...
        }
        </pre>
    */
    Iterator begin() const {
        return Iterator(this);
    }

    const Iterator& end() const {
        static const Iterator it;
        return it;
    }

    ///////////////////////////////////////////////////////////////////////////
    ///////////////////////////////////////////////////////////////////////////

    // Forward declaration required by older gcc versions for friend declaration in BoxIterator
    class SphereIterator;
    class BoxIterator {
    private:
        friend class ThisType;
        friend class SphereIterator;

        bool                                    m_isEnd;

        const ThisType*                         m_grid;

        /** Lower bound on the boxes covered, inclusive. */
        Vector3int32                            m_lo;

        /** Upper bound on the boxes covered, inclusive.*/
        Vector3int32                            m_hi;
        
        /** If true, test values against m_box before returning them.*/
        bool                                    m_exact;

        /** The underlying box in 3D space */
        AABox                                   m_box;

        /** The iterator winds through the 3D grid between m_lo and (m_lo + m_extent) in
            Z,Y,X-major order.  This is the index keeping track of how
            far it has come */
        Vector3int32                            m_current;
        
        /** The current cell. */
        Cell*                                   m_cell;

        /** Index within m_cell of the current value */
        int                                     m_arrayIndex;

        const int                               m_epoch;
      

        /** Called from advance() */
        void advanceCell() {
            do {
                ++m_current.x;
                if (m_current.x > m_hi.x) {
                    m_current.x = m_lo.x;
                    ++m_current.y;
                    if (m_current.y > m_hi.y) {
                        m_current.y = m_lo.y;
                        ++m_current.z;
                        if (m_current.z > m_hi.z) {
                            m_isEnd = true;
                            return;
                        }
                    }
                }

                // Pick up the new cell
                m_cell = m_grid->m_data.getPointer(m_current);
                // Keep advancing if the cell does not exist
            } while ((m_cell == NULL) || (m_cell->size() == 0));
        }

        /** Advance to the next value */
        void advance() {
            debugAssert(! m_isEnd);

            do {
                ++m_arrayIndex;
                bool inConstructor = (m_cell == NULL);
                if (inConstructor || m_arrayIndex >= m_cell->size()) {
                    advanceCell();
                    m_arrayIndex = 0;

                    if (m_isEnd) {
                        // Ran out of values
                        return;
                    }
                    debugAssert(m_cell != NULL);
                }

                // Advance until we have a value that can be returned, either
                // because we don't care about exactness or because it is 
                // guaranteed to be within the box.
            } while (m_exact && ! m_box.contains(position()));
        }


        /** End iterator */
        BoxIterator() : m_isEnd(true), m_grid(NULL), m_exact(true), m_current(0,0,0), m_cell(NULL), m_arrayIndex(0), m_epoch(0) {}

        /** Begin iterator */
        BoxIterator(const ThisType* grid, bool exact, const AABox& box) : 
            m_isEnd(false),
            m_grid(grid),
            m_exact(exact),
            m_box(box),
            m_current(-1, 0 ,0),
            m_cell(NULL),
            m_arrayIndex(0),
            m_epoch(grid->m_epoch) { 

            m_grid->getCellCoord(box.low(), m_lo);
            m_grid->getCellCoord(box.high(), m_hi);
            
            // Get to the first value
            m_current = m_lo;
            // Back up one so that advancing takes us to the first
            --m_current.x;
            advance();
        }

        const Value& value() const {
            debugAssert(! m_isEnd);
            return (*m_cell)[m_arrayIndex].value;
        }

        /** Used by SphereIterator::advance() */
        const Vector3& position() const {
            debugAssert(! m_isEnd);
            return (*m_cell)[m_arrayIndex].position;
        }

        // Intentionally unimplemented
        BoxIterator& operator=(const BoxIterator&);

    public:

        inline bool operator!=(const BoxIterator& other) const {
            if (other.m_isEnd && m_isEnd) {
                return false;
            } else {
                return (m_isEnd         != other.m_isEnd) ||
                    (m_cell          != other.m_cell) || 
                    (m_arrayIndex    != other.m_arrayIndex);
            }
        }

        bool operator==(const BoxIterator& other) const {
            return !(*this != other);
        }

        /** Preincrement */
        BoxIterator& operator++() {
            debugAssert(! m_isEnd);
            debugAssertM(m_epoch == m_grid->m_epoch, 
                         "It is illegal to mutate the HashGrid "
                         "while iterating through it.");

            advance();

            return *this;
        }

        /** Post increment (slower) */
        BoxIterator operator++(int) {
            Iterator old = *this;
            ++(*this);
            return old;
        }

        const Value& operator*()  const { return  value(); }
        const Value* operator->() const { return &value(); }
        operator Value*()         const { return &value(); }

        /** \deprecated Use isValid */
        bool hasMore() const {
            return ! m_isEnd;
        }

        bool isValid() const {
            return ! m_isEnd;
        }
    }; // BoxIterator

    /** 
        Finds all values whose positions are within @a box.  It is an error to 
        mutate the PointHashGrid while iterating through it.

        @param exact If false, the iterator will execute more quickly but will likely return some
        values that lie outside the box. Set exact = false if you are going to test the 
        results against the yourself box anyway.
    */
    BoxIterator beginBoxIntersection(const AABox& box, bool exact = true) const {
        return BoxIterator(this, exact, box);
    }

    const BoxIterator& endBoxIntersection() const {
        static const BoxIterator it;
        return it;
    }

    ///////////////////////////////////////////////////////////////////////////
    ///////////////////////////////////////////////////////////////////////////
    
    class SphereIterator {
    private:

        friend class ThisType;

        bool                m_isEnd;
        Sphere              m_sphere;
        BoxIterator         m_boxIterator;

        SphereIterator() : m_isEnd(true) {}

        void advance() {
            if (! m_boxIterator.isValid()) {
                m_isEnd = true;
                return;
            }

            while (! m_sphere.contains(m_boxIterator.position())) {
                ++m_boxIterator;
                
                if (! m_boxIterator.isValid()) {
                    m_isEnd = true;
                    return;
                }
            } 
        }

        static AABox getBoundingBox(const Sphere& s) {
            AABox box;
            s.getBounds(box);
            return box;
        }

        SphereIterator(const ThisType* grid, const Sphere& sphere) : 
            m_isEnd(false),
            m_sphere(sphere),
            m_boxIterator(grid, false, getBoundingBox(sphere)) {
            
            // Find the first element that is actually in the sphere,
            // not just the box.
            advance();
        }

        const Value& value() const {            
            return *m_boxIterator;
        }

        // TODO: if the sphere is very big compared to radius, check each
        // cell's box to see if the cell itself is actually inside the sphere
        // before iterating through it, since there may be many boxes outside the sphere.

        // Intentionally unimplemented
        SphereIterator& operator=(const SphereIterator&);

    public:

        inline bool operator!=(const SphereIterator& other) const {
            if (other.m_isEnd && m_isEnd) {
                return false;
            } else {
                return 
                    (m_isEnd         != other.m_isEnd) ||
                    (m_sphere        != other.m_sphere) ||
                    (m_boxIterator   != other.m_boxIterator);
            }
        }

        bool operator==(const SphereIterator& other) const {
            return !(*this != other);
        }

        /** Preincrement */
        SphereIterator& operator++() {
            debugAssert(! m_isEnd);

            ++m_boxIterator;
            advance();

            return *this;
        }

        /** Post increment (slower) */
        SphereIterator operator++(int) {
            Iterator old = *this;
            ++(*this);
            return old;
        }

        const Value& operator*()  const { return  value(); }
        const Value* operator->() const { return &value(); }
        operator Value*()         const { return &value(); }

        /** \deprecated use isValid */
        bool G3D_DEPRECATED hasMore() const {
            return ! m_isEnd;
        }

        bool isValid() const {
            return ! m_isEnd;
        }
    }; // SphereIterator

    /** Finds all values whose positions are within \a sphere.  It is
        an error to mutate the PointHashGrid while iterating through
        it. */
    SphereIterator begin(const Sphere& sphere) const {
        return SphereIterator(this, sphere);
    }


    /** \deprecated \sa beginIntersection */
    SphereIterator G3D_DEPRECATED beginSphereIntersection(const Sphere& sphere) const {
        return SphereIterator(this, sphere);
    }


    /** \deprecated \sa SphereIterator::hasMore */
    const SphereIterator& endSphereIntersection() const {
        static const SphereIterator it;
        return it;
    }

    
    /** Appends results */
    void getIntersectingMembers(const Sphere& sphere, Array<Value>& result) const {
        for (SphereIterator it = beginSphereIntersection(sphere); it.isValid(); ++it) {
            result.append(*it);
        }
    }


    ///////////////////////////////////////////////////////////////////////////
    ///////////////////////////////////////////////////////////////////////////

    /**
       Dereference to access the bounds() and size() [element count] of the underlying
       cell object.

       Example:
       <pre>
       for(PointHashGrid<Vector3>::CellIterator iter = grid.beginCells(); iter != grid.endCells(); ++iter) {    
       entriesFound += iter->size();
       }
       </pre>
    */
    class CellIterator {
    private:
        friend class ThisType;

        bool                                    m_isEnd;
        const ThisType*                         m_grid;
        typename CellTable::Iterator            m_tableIterator;
        const int                               m_epoch;


        Cell& cell() {
            return m_tableIterator->value;
        }

    public:
        
        class CellObject {
            friend class CellIterator;
        private:
            const CellIterator* m_parent;

            CellObject() : m_parent(NULL) {}

        public:

            /** Returns the bounds on this cell */
            AABox bounds() const {
                const Vector3int32& k = m_parent->m_tableIterator->key;
                return AABox(Vector3(k) * m_parent->m_grid->m_cellWidth, 
                             Vector3(k + Vector3int32(1, 1, 1)) * m_parent->m_grid->m_cellWidth);
            }

            /** Number of elements inside this cell */
            int size() const {
                debugAssert(! m_parent->m_isEnd);
                return m_parent->m_tableIterator->value.size();
            }
        };

    private:
        /** Used to make the indirection work.*/
        CellObject m_indirection;

        /** End iterator. Note that the m_tableIterator is initialized to the end iterator
            of a temporary value!  This is ok because we'll never look at the value of the 
            m_tableIterator, since we're initializing the "end" Iterator.*/
        CellIterator() : 
            m_isEnd(true),
            m_grid(NULL),
            m_tableIterator( CellTable().end() ),
            m_epoch(0) {}
        
        CellIterator(const ThisType* grid) : 
            m_isEnd(false),
            m_grid(grid),
            m_tableIterator( grid->m_data.begin()),
            m_epoch(grid->m_epoch) {
            m_indirection.m_parent = this;
            m_isEnd = ! m_tableIterator.isValid();
        }
        
        // Intentionally unimplemented
        CellIterator& operator=(const CellIterator&);

    public:

        const CellObject& operator*()  const { return  m_indirection; }
        const CellObject* operator->() const { return &m_indirection; }
        operator CellObject*()         const { return &m_indirection; }

        inline bool operator!=(const CellIterator& other) const {
            // != is called more often than == during iteration
            return !(
                     (m_isEnd && other.m_isEnd) ||
                     ((m_isEnd == other.m_isEnd) && 
                      (m_tableIterator != other.m_tableIterator)));
        }

        bool operator==(const CellIterator& other) const {
            return !(*this != other);
        }

        /** Preincrement */
        CellIterator& operator++() {
            debugAssertM(m_epoch == m_grid->m_epoch, 
                         "It is illegal to mutate the HashGrid while "
                         "iterating through it.");
            ++m_tableIterator;
            m_isEnd = ! m_tableIterator.isValid();
            return *this;
        }

        /** Post increment (slower) */
        CellIterator operator++(int) {
            Iterator old = *this;
            ++(*this);
            return old;
        }

        /** \deprecated Use isValid */
        bool hasMore() const {
            return ! m_isEnd;
        }

        bool isValid() const {
            return ! m_isEnd;
        }
    }; // CellIterator

    /** Iterates through the non-empty cells.  This is intended primarily for
        debugging and visualizing the data structure.*/
    CellIterator beginCells() const {
        return CellIterator(this);
    }

    const CellIterator& endCells() const {
        static const CellIterator it;
        return it;
    }

    ///////////////////////////////////////////////////////////////////////////
    ///////////////////////////////////////////////////////////////////////////

    /** Returns true if there is a value that is exactly equal to @a v. This will 
        check all neighboring cells to avoid roundoff error at cell boundaries. 
    */
    bool contains(const Value& v) const {
        Cell* cell = NULL;
        int   index = 0;
        Vector3int32 cellCoord;
        return const_cast<ThisType*>(this)->find(v, cellCoord, cell, index);
    }

    /** Calls delete on all of the values, which are assumed to be pointers. 
        This is a helper to avoid requiring you to iterate through the data 
        structure, removing and deleting each one. Clears the PointHashGrid at the
        end.
        
        Using objects (instead of pointers) or reference counted pointers is 
        recommended over using pointers and this deleteAll method.*/
    void deleteAll() {
        for (Iterator it = begin(); it.isValid(); ++it) {
            delete *it;
        }
        clear();
    }

    void clearAndSetMemoryManager(const MemoryManager::Ref& m) {
        ++m_epoch;
        m_size = 0;
        m_bounds = AABox();

        m_data.clearAndSetMemoryManager(m);
        m_memoryManager = m;
    }

    /** Removes all data. 
        @param shrink If true, underlying structures are deallocated as
        they are freed.*/
    void clear(bool shrink = true) {
        m_size = 0;
        m_bounds = AABox();
        if (! shrink) {
            // Remove all data
            for (CellIterator it = beginCells(); it.isValid(); ++it) {
                it.cell().clear(true);
            }
        } else {
            m_data.clear();
        }
        ++m_epoch;
    }

    int debugGetDeepestBucketSize() const {
        return (int)m_data.debugGetDeepestBucketSize();
    }

    float debugGetAverageBucketSize() const {
        return m_data.debugGetAverageBucketSize();
    }
#undef ThisType 
};

} // G3D
#endif