hashGrid.h

// -*- Mode: C++; tab-width: 2; -*-
// vi: set ts=2:
//

#ifndef BALL_DATATYPE_HASHGRID_H
#define BALL_DATATYPE_HASHGRID_H

#ifndef BALL_COMMON_H
# include <BALL/common.h>
#endif

#ifndef BALL_CONCEPT_FORWARDITERATOR_H
# include <BALL/CONCEPT/forwardIterator.h>
#endif

#ifndef BALL_CONCEPT_VISITOR_H
# include <BALL/CONCEPT/visitor.h>
#endif

#ifndef BALL_CONCEPT_PROCESSOR_H
# include <BALL/CONCEPT/processor.h>
#endif

#ifndef BALL_MATHS_VECTOR3_H
# include <BALL/MATHS/vector3.h>
#endif

#ifndef BALL_DATATYPE_LIST_H
# include <BALL/DATATYPE/list.h>
#endif

namespace BALL 
{

  template <typename Item>
  class HashGridBox3
  {
    public:


    HashGridBox3();
      
    HashGridBox3(const HashGridBox3& grid_box, bool deep = true);

    ~HashGridBox3();

    void clear();

    void destroy();
  


    void set(const HashGridBox3& box,bool /* deep */ = true)
      throw(Exception::NotImplemented);

    const HashGridBox3& operator = (const HashGridBox3& box)
      throw(Exception::NotImplemented);



    Item* find(const Item &item);

    const Item* find(const Item& item) const;

    Size getSize() const;

    void insert(const Item& item);

    bool remove(const Item& item);

    bool removeAll(const Item& item);
      

    
    void host(Visitor<HashGridBox3> &visitor);


    bool operator == (const HashGridBox3& box) const;

    bool operator != (const HashGridBox3& box) const;

    bool has(const Item& item) const;

    bool isEmpty() const;


    
    bool isValid() const;
    void dump(std::ostream& s = std::cout, Size depth = 0) const;



    bool apply(UnaryProcessor<Item>& processor);

    bool apply(UnaryProcessor< HashGridBox3<Item> >& processor);



    class DataItem
    {
      public:
    
      DataItem(const Item& item, DataItem* next)
      : item_(item),
        previous_(0),
        next_(next)
      {
        if (next_ != 0)
        {
          next_->previous_ = this;
        }
      }

      Item      item_;
      DataItem* previous_;
      DataItem* next_;
    };

    typedef Position BoxIteratorPosition;
    
    class BoxIteratorTraits
    {
      public:

      BALL_CREATE_DEEP(BoxIteratorTraits)

      virtual ~BoxIteratorTraits() throw () {}

      BoxIteratorTraits()
        : bound_(0),
          position_(0)
      {
      }
        
      BoxIteratorTraits(const HashGridBox3& box)
        : bound_((HashGridBox3 *)&box),
          position_(0)
      {
      }
        
      BoxIteratorTraits(const BoxIteratorTraits& traits, bool /* deep */ = true)
        : bound_(traits.bound_),
          position_(traits.position_)
      {
      }
        
      const BoxIteratorTraits& operator = (const BoxIteratorTraits& traits)
      {
        bound_ = traits.bound_;
        position_ = traits.position_;
        return *this;
      }

      HashGridBox3* getContainer()
      {
        return bound_;
      }

      const HashGridBox3* getContainer() const
      {
        return bound_;
      }

      bool isSingular() const
      {
        return (bound_ == 0);
      }
        
      BoxIteratorPosition& getPosition()
      {
        return position_;
      }

      const BoxIteratorPosition& getPosition() const
      {
        return position_;
      }

      bool operator == (const BoxIteratorTraits& traits) const
      {
        return (position_ == traits.position_);
      }

      bool operator != (const BoxIteratorTraits& traits) const
      {
        return (position_ != traits.position_);
      }
        
      bool isValid() const
      {
        return (bound_ != 0 && position_ < 27);
      }

      void invalidate()
      {
        bound_ = 0;
        position_ = 100;
      }

      void toBegin()
      {
        position_ = 0;
      }

      bool isBegin() const
      {
        return (position_ == 0);
      }

      void toEnd()
      {
        position_ = 27;
      }

      bool isEnd() const
      {
        return (position_ == 27);
      }

      HashGridBox3<Item>& getData()
      {
        return *bound_->neighbours[position_];
      }

      const HashGridBox3<Item>& getData() const
      {
        return *bound_->neighbours[position_];
      }

      void forward()
      {
        ++position_;
        // iterate to the next existing box
        while (position_<27 && !(bound_->neighbours[position_]))
        {
          ++position_;
        }
      }
    
      private:

      HashGridBox3<Item> *bound_;
      BoxIteratorPosition position_;
    };

    friend class BoxIteratorTraits;

    typedef ForwardIterator
      <HashGridBox3<Item>, HashGridBox3<Item>,
      BoxIteratorPosition, BoxIteratorTraits>
        BoxIterator;

    BoxIterator beginBox()
    {
      return BoxIterator::begin(*this);
    }

    BoxIterator endBox()
    {
      return BoxIterator::end(*this);
    }


    typedef ConstForwardIterator
      <HashGridBox3<Item>, HashGridBox3<Item>,
      BoxIteratorPosition, BoxIteratorTraits>
        ConstBoxIterator;

    ConstBoxIterator beginBox() const
    {
      return ConstBoxIterator::begin(*this);
    }

    ConstBoxIterator endBox() const
    {
      return ConstBoxIterator::end(*this);
    }


    typedef DataItem* DataIteratorPosition;
    
  class DataIteratorTraits
    {
      public:

      BALL_CREATE_DEEP(DataIteratorTraits)

        virtual ~DataIteratorTraits() {}

      DataIteratorTraits()
      : bound_(0),
        position_(0)
      {
      }
        
      DataIteratorTraits(const HashGridBox3& box)
      : bound_((HashGridBox3 *)&box),
        position_(0)
      {
      }
        
      DataIteratorTraits(const DataIteratorTraits& traits, bool /* deep */ = true)
      : bound_(traits.bound_),
        position_(traits.position_)
      {
      }
        
      const DataIteratorTraits& operator = (const DataIteratorTraits &traits)
      {
        bound_ = traits.bound_;
        position_ = traits.position_;
        return *this;
      }

      HashGridBox3* getContainer()
      {
        return bound_;
      }

      const HashGridBox3* getContainer() const
      {
        return bound_;
      }

      bool isSingular() const
      {
        return (bound_ == 0);
      }
        
      DataIteratorPosition& getPosition()
      {
        return position_;
      }

      const DataIteratorPosition& getPosition() const
      {
        return position_;
      }

      bool operator == (const DataIteratorTraits &traits) const
      {
        return (position_ == traits.position_);
      }

      bool operator != (const DataIteratorTraits &traits) const
      {
        return (position_ != traits.position_);
      }

      bool isValid() const
      {
        return (bound_ != 0 && position_ != 0);
      }

      void invalidate()
      {
        bound_ = 0;
        position_ = 0;
      }

      void toBegin()
      {
        position_ = bound_->first_item_;
      }

      bool isBegin() const
      {
        return (position_ == bound_->first_item_);
      }

      void toEnd()
      {
        position_ = 0;
      }

      bool isEnd() const
      {
        return (position_ == 0);
      }

      Item& getData()
      {
        return position_->item_;
      }

      const Item& getData() const
      {
        return position_->item_;
      }

      void forward()
      {
        position_ = position_->next_;
      }
  
      private:

      HashGridBox3<Item>*   bound_;
      DataIteratorPosition  position_;
    };

    friend class DataIteratorTraits;

    typedef ForwardIterator
      <HashGridBox3<Item>, Item,
       DataIteratorPosition, DataIteratorTraits>
      DataIterator;

    DataIterator beginData()
    {
      return DataIterator::begin(*this);
    }

    DataIterator endData()
    {
      return DataIterator::end(*this);
    }


    typedef ConstForwardIterator
      <HashGridBox3<Item>, Item,
       DataIteratorPosition, DataIteratorTraits>
      ConstDataIterator;

    ConstDataIterator beginData() const
    {
      return ConstDataIterator::begin(*this);
    }

    ConstDataIterator endData() const
    {
      return ConstDataIterator::end(*this);
    }


    HashGridBox3* neighbours[27];
    //  private:
  
    DataItem*           first_item_;
  };

  template<typename Item>  
  HashGridBox3<Item>::HashGridBox3()
    : first_item_(0)
  {
    memset(neighbours, 0, 27*sizeof(HashGridBox3*));
  }

  template<typename Item>  
  HashGridBox3<Item>::HashGridBox3(const HashGridBox3<Item>& box, bool deep)
    : first_item_(0)
  {
    set(box, deep);
  }

  template<typename Item>  
  HashGridBox3<Item>::~HashGridBox3()
  {
    clear();
  }

  template<typename Item>  
  void HashGridBox3<Item>::clear()
  {
    for (DataItem* next_item = 0; first_item_ != 0; first_item_ = next_item)
    {
      next_item = first_item_->next_;
      delete first_item_;
    }
  }

  template<typename Item>  
  BALL_INLINE 
  void HashGridBox3<Item>::destroy()
  {
    clear();
  }

  template<typename Item>  
  void HashGridBox3<Item>::set(const HashGridBox3<Item>& box,  bool deep)
    throw(Exception::NotImplemented)
  { 
    // ????? - not implemented
    throw Exception::NotImplemented(__FILE__, __LINE__);
  }
 
  template<typename Item>  
  BALL_INLINE 
  const HashGridBox3<Item>& HashGridBox3<Item>::operator = (const HashGridBox3<Item>& box)
    throw(Exception::NotImplemented)
  {
    set(box);
    
    return *this;
  }

  template<typename Item>  
  Item* HashGridBox3<Item>::find(const Item& item)
  {
    for (DataItem* item_ptr= first_item_; item_ptr != 0; item_ptr = item_ptr->next_)
    {
      if (item_ptr->item_ == item)
      {
        return &(item_ptr->item_);
      }
    }

    return 0;
  }

  template<typename Item>  
  BALL_INLINE 
  const Item* HashGridBox3<Item>::find(const Item& item) const
  {
    return const_cast<HashGridBox3*>(this)->find(item);
  }

  template<typename Item>  
  Size HashGridBox3<Item>::getSize() const
  {
    Size size = 0;

    // count all items in the box
    for (const DataItem* item = first_item_; item != 0; item = item->next_, size++) {};
    
    return size;
  }

  template<typename Item>  
  BALL_INLINE 
  void HashGridBox3<Item>::insert(const Item& item)
  {
    first_item_ = new DataItem(item, first_item_);
  }

  template<typename Item>  
  bool HashGridBox3<Item>::remove(const Item& item)
  {
    for (DataItem* item_ptr = first_item_; item_ptr != 0; item_ptr = item_ptr->next_)
    {
      if (item_ptr->item_ == item)
      {
        if (item_ptr == first_item_)
        {
          first_item_ = first_item_->next_;
        }
      
        if (item_ptr->next_ != 0)
        {
          item_ptr->next_->previous_ = item_ptr->previous_;
        }
      
        if (item_ptr->previous_ != 0)
        {
          item_ptr->previous_->next_ = item_ptr->next_;
        }
      
        delete item_ptr;
        
        return true;
      }
    }
    
    return false;
  }

  template<typename Item>  
  bool HashGridBox3<Item>::removeAll(const Item& item)
  {
    bool found = false;
    DataItem* next_item = 0;
    DataItem* item_ptr = first_item_;
    
    while(item_ptr != 0)
    {
      next_item = item_ptr->next_;

      if (item_ptr->item_ == item)
      {
        if (item_ptr == first_item_)
        {
          first_item_ = first_item_->next_;
        }
        
        if (item_ptr->next_ != 0)
        {
          item_ptr->next_->previous_ = item_ptr->previous_;
        }
      
        if (item_ptr->previous_ != 0)
        {
          item_ptr->previous_->next_ = item_ptr->next_;
        }
      
        delete item_ptr;
        
        found = true;
      }
      
      item_ptr = next_item;
    }

    return found;
  }

  template <typename Item>
  BALL_INLINE 
  void HashGridBox3<Item>::host(Visitor< HashGridBox3<Item> >& visitor)
  {
    visitor.visit(*this);
  }

  template<typename Item>  
  bool HashGridBox3<Item>::operator == (const HashGridBox3<Item>& box) const
  {
    const DataItem* a = first_item_;
    const DataItem* b = box.first_item_;
    
    for (; a != 0 && b != 0; a = a->next_, b = b->next_)
    {
      if (a->item_ != b->item_)
      {
        return false;
      }
    }
    
    return (a == b);
  }

  template<typename Item>  
  BALL_INLINE 
  bool HashGridBox3<Item>::operator != (const HashGridBox3<Item>& box) const
  {
    return !(*this == box);
  }

  template<typename Item>  
  BALL_INLINE 
  bool HashGridBox3<Item>::has(const Item& item) const
  {
    return (find(item) != 0);
  }

  template<typename Item>  
  BALL_INLINE 
  bool HashGridBox3<Item>::isEmpty() const
  {
    return (first_item_ == 0);
  }

  template<typename Item>  
  bool HashGridBox3<Item>::isValid() const
  {
    Size size = 0;
    DataItem* item = 0;
    
    for (item = first_item_; item != 0; item = item->next_)
    {
      ++size;
      
      if (item->next_ == 0)
      {
        break;
      }
    }
    
    for (; item != 0; item = item->previous_, --size) {};
    
    return (size == 0);
  }

  template<typename Item>  
  void HashGridBox3<Item>::dump(std::ostream& s, Size depth) const
  {
    BALL_DUMP_STREAM_PREFIX(s);
    
    BALL_DUMP_DEPTH(s, depth);
    
    BALL_DUMP_DEPTH(s, depth);
    s << "  size: " << getSize() << std::endl;
    
    BALL_DUMP_DEPTH(s, depth);
    s << "  data:" << std::endl;
    for (DataItem *item = first_item_; item != 0; item = item->next_)
    {
      BALL_DUMP_DEPTH(s, depth);
      s << "    " << item->item_ << std::endl;
    }
    
    BALL_DUMP_DEPTH(s, depth);
    s << "  neighbor boxes:" << std::endl;
    for (Position i=0; i<27; ++i)
    {
      BALL_DUMP_DEPTH(s, depth);
      s << "    " << neighbours[i] << std::endl;
    }
    
    BALL_DUMP_STREAM_SUFFIX(s);
  }

  template <typename Item>
  bool HashGridBox3<Item>::apply(UnaryProcessor<Item>& processor)
  {
    if (processor.start() == false)
    {
      return false;
    }

    Processor::Result result;
      
    for (DataItem *item = first_item_; item != 0; item = item->next_)
    {
      result = processor(item->item_);

      if (result <= Processor::BREAK)
      {
        return (result == Processor::BREAK) ? true : false;
      }
    }

    return processor.finish(); 
  }

  template <typename Item>
  bool HashGridBox3<Item>::apply(UnaryProcessor< HashGridBox3<Item> >& processor)
  {
    if (processor.start() == false)
    {
      return false;
    }
 
    Processor::Result result;

    for (Position i=0; i<27; ++i)
    {
      result = processor(*neighbours[i]);

      if (result <= Processor::BREAK)
      {
        return (result == Processor::BREAK) ? true : false;
      }
    }

    return processor.finish(); 
  }

  template <typename Item>
  class HashGrid3
  {
    public:

    BALL_CREATE(HashGrid3)

    

    HashGrid3();
      
    HashGrid3(const Vector3& origin, Size dimension_x, Size dimension_y,
        Size dimension_z, float spacing_x, float spacing_y, float spacing_z);

    HashGrid3(const Vector3& origin, Size dimension_x, Size dimension_y, 
        Size dimension_z, float spacing);

    HashGrid3(const Vector3& origin, const Vector3& size, float spacing);

    HashGrid3(const HashGrid3& grid, bool deep = true);

    virtual ~HashGrid3();

    virtual void clear();

    void clear(Position x, Position y, Position z);

    void clear(const Vector3 &vector);

    void destroy();

    void destroy(Position x, Position y, Position z);

    void destroy(const Vector3& vector);



    void set(const Vector3& origin, const Vector3& unit, 
        Size  dimension_x, Size dimension_y, Size dimension_z);

    void set(const Vector3& origin, float unit, Size size);

    void set(const HashGrid3& grid, bool deep = true);

    const HashGrid3& operator = (const HashGrid3& grid);

    void get(Vector3& origin, Vector3& unit, Size&  dimension_x, Size&  dimension_y, Size&  dimension_z) const; 

    void get(HashGrid3& grid, bool deep = true) const;



    Size countNonEmptyBoxes() const;
    
    Size getSize() const;

    Vector3& getOrigin();

    const Vector3& getOrigin() const;

    Vector3& getUnit();

    const Vector3& getUnit() const;

    Size getSizeX() const;

    Size getSizeY() const;

    Size getSizeZ() const;

    HashGridBox3<Item>* getBox(Position x, Position y, Position z);

    const HashGridBox3<Item>* getBox(Position x, Position y, Position z) const;

    HashGridBox3<Item>* getBox(const Vector3& vector);

    const HashGridBox3<Item>* getBox(const Vector3 &vector) const;

    bool getIndices(const HashGridBox3<Item>& box, 
        Position& x, Position& y, Position& z) const;

    void insert(Position x, Position y, Position z, const Item& item);
    
    void insert(const Vector3& vector, const Item& item);

    bool remove(Position x, Position y, Position z, const Item& item);

    bool remove(const Vector3& vector, const Item& item);



    void host(Visitor<HashGrid3>& visitor);



    bool operator == (const HashGrid3& grid) const;

    bool operator != (const HashGrid3& grid) const;

    bool isEmpty() const;



    virtual bool isValid() const;

    virtual void dump(std::ostream& s = std::cout, Size depth = 0) const;



    bool apply(UnaryProcessor<Item> &processor);

    bool apply(UnaryProcessor< HashGridBox3<Item> > &processor);

    const Item* getClosestItem(const Vector3& point, Size distance) const;

    static float calculateMinSpacing(LongIndex memory, const Vector3& size);



    typedef Position BoxIteratorPosition;
    
    class BoxIteratorTraits
    {
      public:

      BALL_CREATE_DEEP(BoxIteratorTraits)

      virtual ~BoxIteratorTraits() {}

      BoxIteratorTraits()
        : bound_(0),
          position_(0)
      {
      }
        
      BoxIteratorTraits(const HashGrid3 &grid)
        : bound_((HashGrid3 *)&grid),
          position_(0)
      {
      }
        
      BoxIteratorTraits(const BoxIteratorTraits& traits, bool /* deep */ = true)
        : bound_(traits.bound_),
          position_(traits.position_)
      {
      }
        
      const BoxIteratorTraits& operator = (const BoxIteratorTraits& traits)
      {
        bound_ = traits.bound_;
        position_ = traits.position_;
        return *this;
      }

      HashGrid3* getContainer()
      {
        return bound_;
      }

      const HashGrid3* getContainer() const
      {
        return bound_;
      }

      bool isSingular() const
      {
        return (bound_ == 0);
      }
        
      BoxIteratorPosition& getPosition()
      {
        return position_;
      }

      const BoxIteratorPosition& getPosition() const
      {
        return position_;
      }

      bool operator == (const BoxIteratorTraits& traits) const
      {
        return (position_ == traits.position_);
      }

      bool operator != (const BoxIteratorTraits& traits) const
      {
        return (position_ != traits.position_);
      }
        
      bool isValid() const
      {
        return (bound_ != 0 && position_ < bound_->getSize());
      }

      void invalidate()
      {
        bound_ = 0;
        position_ = bound_->getSize()+1;
      }

      void toBegin()
      {
        position_ = 0;
      }

      bool isBegin() const
      {
        return (position_ == 0);
      }

      void toEnd()
      {
        position_ = bound_->getSize();
      }

      bool isEnd() const
      {
        return (position_ == bound_->getSize());
      }

      HashGridBox3<Item>& getData()
      {
        return bound_->box_[position_];
      }

      const HashGridBox3<Item>& getData() const
      {
        return bound_->box_[position_];
      }

      void forward()
      {
        ++position_;
      }
    
      private:

      HashGrid3<Item>* bound_;
      BoxIteratorPosition position_;
    };

    friend class BoxIteratorTraits;

    typedef ForwardIterator
      <HashGrid3<Item>, HashGridBox3<Item>,
       BoxIteratorPosition, BoxIteratorTraits>
      BoxIterator;

    BoxIterator beginBox()
    {
      return BoxIterator::begin(*this);
    }

    BoxIterator endBox()
    {
      return BoxIterator::end(*this);
    }


    typedef ConstForwardIterator
      <HashGrid3<Item>, HashGridBox3<Item>,
       BoxIteratorPosition, BoxIteratorTraits>
      ConstBoxIterator;

    ConstBoxIterator beginBox() const
    {
      return ConstBoxIterator::begin(*this);
    }

    ConstBoxIterator endBox() const
    {
      return ConstBoxIterator::end(*this);
    }


    private:

    //_
    Index getIndex_(const HashGridBox3<Item>& box) const;

    void setNeighbours_();

    //_
    HashGridBox3<Item>* box_;
    //_
    Vector3 origin_;
    //_
    Vector3 unit_;
    //_
    Size  dimension_x_;
    //_
    Size  dimension_y_;
    //_
    Size  dimension_z_;
  };

    


  template <typename Item>
  HashGrid3<Item>::HashGrid3()
    : box_(0),
      origin_(0,0,0),
      unit_(0,0,0),
      dimension_x_(0),
      dimension_y_(0),
      dimension_z_(0)
  {
  }

  template <typename Item>
  HashGrid3<Item>::HashGrid3
    (const Vector3 &originvector,
     Size dimension_x, Size dimension_y, Size dimension_z,
     float spacing_x, float spacing_y, float spacing_z)
    : box_(0),
      origin_(originvector),
      unit_(spacing_x, spacing_y, spacing_z),
      dimension_x_(dimension_x),
      dimension_y_(dimension_y),
      dimension_z_(dimension_z)
  {
    box_ = new HashGridBox3<Item>[dimension_x * dimension_y * dimension_z];
    setNeighbours_();
  }

  template <typename Item>
  HashGrid3<Item>::HashGrid3
    (const Vector3& origin,
     Size dimension_x, Size dimension_y, Size dimension_z, float spacing)
   :  box_(0),
      origin_(origin),
      unit_(spacing, spacing, spacing),
      dimension_x_(dimension_x),
      dimension_y_(dimension_y),
      dimension_z_(dimension_z)
  {
    box_ = new HashGridBox3<Item>[dimension_x * dimension_y * dimension_z];
    setNeighbours_();
  }

  // this constructor creates a linear array of HashGridBox3 objects.
  template <typename Item>
  HashGrid3<Item>::HashGrid3(const Vector3& origin, const Vector3& size,
      float spacing)
    : box_(0),
      origin_(origin),
      unit_(spacing, spacing, spacing),
      dimension_x_((Size)(size.x / spacing + 1.0)),
      dimension_y_((Size)(size.y / spacing + 1.0)),
      dimension_z_((Size)(size.z / spacing + 1.0))
  {
    box_ = new HashGridBox3<Item>[dimension_x_ * dimension_y_ * dimension_z_];
    setNeighbours_();
  }

  template <typename Item>
  HashGrid3<Item>::HashGrid3(const HashGrid3<Item>& grid, bool deep)
    : box_(0),
      origin_(),
      unit_()
  {
    set(grid, deep);
  }

  template <typename Item>
  HashGrid3<Item>::~HashGrid3()
  {
    clear();
    delete [] box_;
  }

  template <typename Item>
  void HashGrid3<Item>::clear()
  {
    if (box_ != 0)
    {
      Size size = dimension_x_ * dimension_y_ * dimension_z_;

      for (Position index = 0; index < (Position)size; ++index)
      {
        box_[index].clear();
      }
    }
  }

  template <typename Item>
  BALL_INLINE 
  void HashGrid3<Item>::clear(Position x, Position y, Position z)
  {
    HashGridBox3<Item>* box = getBox(x, y, z);
    
    if (box != 0)
    {
      box->clear();
    }
  }

  template <typename Item>
  BALL_INLINE 
  void HashGrid3<Item>::clear(const Vector3& vector)
  {
    HashGridBox3<Item>* box = getBox(vector);
    
    if (box != 0)
    {
      box->clear();
    }
  }

  template <typename Item>
  BALL_INLINE 
  void HashGrid3<Item>::destroy()
  {
    clear();
  }

  template <typename Item>
  BALL_INLINE 
  void HashGrid3<Item>::destroy(Position x, Position y, Position z)
  {
    clear(x, y, z);
  }

  template <typename Item>
  BALL_INLINE 
  void HashGrid3<Item>::destroy(const Vector3 &vector)
  {
    clear(vector);
  }

  template <typename Item>
  void HashGrid3<Item>::set
    (const Vector3& origin, const Vector3& unit,
     Size dimension_x, Size dimension_y, Size dimension_z)
  {
    clear();
    if (box_ != 0)
    {
      delete [] box_;
    }
    origin_.set(origin);
    unit_.set(unit);
    dimension_x_ = dimension_x;
    dimension_y_ = dimension_y;
    dimension_z_ = dimension_z;
    Size n = getSize();
    box_ = new HashGridBox3<Item> [n];
    setNeighbours_();
  }

  template <typename Item>
  void HashGrid3<Item>::set(const Vector3& origin, float unit, Size size)
  {
    clear();
    if (box_ != 0)
    {
      delete [] box_;
    }
    origin_.set(origin);
    unit_.set(unit, unit, unit);
    dimension_x_ = size;
    dimension_y_ = size;
    dimension_z_ = size;
    box_ = new HashGridBox3<Item>[getSize()];
    setNeighbours_();
  }

  template <typename Item>
  void HashGrid3<Item>::set(const HashGrid3<Item>& grid, bool /* deep */)
  {
    set(grid.origin_, grid.unit_, grid.dimension_x_, grid.dimension_y_, grid.dimension_z_);

    const HashGridBox3<Item>* sourcebox = grid.box_;
    
    HashGridBox3<Item>* targetbox = box_;
    
    const HashGridBox3<Item>* endbox = &grid.box_[grid.getSize()];
    
    for (; sourcebox < endbox; ++sourcebox, ++targetbox)
    {
      if (sourcebox->isEmpty() == false)
      {
        for (typename HashGridBox3<Item>::DataItem* item  = sourcebox->first_item_; item != 0; item = item->next_)
        {
          targetbox->insert(item->item_);
        }
      }
    }
  }

  template <typename Item>
  BALL_INLINE 
  const HashGrid3<Item>& HashGrid3<Item>::operator = (const HashGrid3<Item> &grid)
  {
    set(grid);
    
    return *this;
  }

  template <typename Item>
  BALL_INLINE 
  void HashGrid3<Item>::get(Vector3 &origin, Vector3 &unit,
                            Size& dimension_x, Size& dimension_y, Size& dimension_z) const
  {
    origin.set(origin_);
    unit.set(unit_);
    dimension_x = dimension_x_;
    dimension_y = dimension_y_;
    dimension_z = dimension_z_;
  }

  template <typename Item>
  BALL_INLINE void 
  HashGrid3<Item>::get(HashGrid3<Item> &grid, bool deep) const
  {
    grid.set(*this, deep);
  }

  template <typename Item>
  Size 
  HashGrid3<Item>::countNonEmptyBoxes() const
  {
    Size size = 0;

    for (Position i=0; i<27; ++i)
    {
      if (!box_[i].isEmpty())
        ++size;
    }

    return size;
  }

  template <typename Item>
  BALL_INLINE 
  Size HashGrid3<Item>::getSize() const
  {
    return (dimension_x_ * dimension_y_ * dimension_z_);
  }

  template <typename Item>
  BALL_INLINE 
  Vector3& HashGrid3<Item>::getOrigin()
  {
    return origin_;
  }

  template <typename Item>
  BALL_INLINE 
  const Vector3& HashGrid3<Item>::getOrigin() const
  {
    return origin_;
  }

  template <typename Item>
  BALL_INLINE 
  Vector3& HashGrid3<Item>::getUnit()
  {
    return unit_;
  }

  template <typename Item>
  BALL_INLINE 
  const Vector3& HashGrid3<Item>::getUnit() const
  {
    return unit_;
  }

  template <typename Item>
  BALL_INLINE 
  Size HashGrid3<Item>::getSizeX() const
  {
    return dimension_x_;
  }

  template <typename Item>
  BALL_INLINE 
  Size HashGrid3<Item>::getSizeY() const
  {
    return dimension_y_;
  }

  template <typename Item>
  BALL_INLINE 
  Size HashGrid3<Item>::getSizeZ() const
  {
    return dimension_z_;
  }

  template <typename Item>
  const Item* HashGrid3<Item>::getClosestItem(const Vector3& point, Size dist) const
  {
    const HashGridBox3<Item>* box = getBox(point);
    if (!box) return 0;

    Position x, y, z;
    getIndices(*box, x, y, z);

    const Item* item = 0;
    float distance = FLT_MAX;

    // iterator over neighbour boxes
    for (Index xi = -(Index)dist; xi <= (Index)dist; xi++)
    {
      const Index xn = x + xi;
      for (Index yi = -(Index)dist; yi <= (Index)dist; yi++)
      {
        const Index yn = y + yi;
        for (Index zi = -(Index)dist; zi <= (Index)dist; zi++)
        {
          // iterate over all data items
          const HashGridBox3<Item>* const box_ptr = getBox(xn, yn, z+zi); 
          if (box_ptr != 0 && !box_ptr->isEmpty())
          {
            typename HashGridBox3<Item>::ConstDataIterator hit = box_ptr->beginData();
            for (;hit != box_ptr->endData(); hit++)
            {
              const float new_dist = ((*hit)->getPosition() - point).getSquareLength();
              if (new_dist < distance)
              {
                item = &*hit;
                distance = new_dist;
              }
            }
          }
        }
      }
    }

    return item;
  }

  template <typename Item>
  BALL_INLINE
  float HashGrid3<Item>::calculateMinSpacing(LongIndex memory, const Vector3& size)
  {
    LongSize memory_for_box = sizeof(HashGridBox3<Item>) + sizeof(HashGridBox3<Item>*);
    LongSize nr_boxes =(LongSize)floor((float)(memory / memory_for_box));

    return pow((double)((size.x * size.y * size.z) / nr_boxes), (double)(1.0 / 3.0));
  }

  template <typename Item>
  BALL_INLINE
  HashGridBox3<Item>* HashGrid3<Item>::getBox(Position x, Position y, Position z)
  {
    if (x >= (Position)dimension_x_ ||
        y >= (Position)dimension_y_ ||
        z >= (Position)dimension_z_)
    {
      return 0;
    } 
    else 
    {
      return &(box_[x * dimension_y_ * dimension_z_ + y * dimension_z_ + z]);
    }
  }

  template <typename Item>
  BALL_INLINE 
  const HashGridBox3<Item>* HashGrid3<Item>::getBox(Position x, Position y, Position z) const
  {
    return ((HashGrid3*)this)->getBox(x, y, z);
  }

  template <typename Item>
  BALL_INLINE 
  HashGridBox3<Item>* HashGrid3<Item>::getBox(const Vector3& vector)
  {
    float x = (vector.x - origin_.x) / unit_.x;
    float y = (vector.y - origin_.y) / unit_.y;
    float z = (vector.z - origin_.z) / unit_.z;

    // workaround for MSVC 7, dont change this !!!
    Index x1 = (Index) Maths::floor(x);
    Index y1 = (Index) Maths::floor(y);
    Index z1 = (Index) Maths::floor(z);

    return getBox(x1, y1, z1);
  }

  template <typename Item>
  BALL_INLINE 
  const HashGridBox3<Item>* HashGrid3<Item>::getBox(const Vector3& vector) const
  {
    return ((HashGrid3 *)this)->getBox(vector);
  }

  template <typename Item>
  BALL_INLINE 
  bool HashGrid3<Item>::getIndices
    (const HashGridBox3<Item>& box,
     Position& x, Position& y, Position& z) const
  {
    Index index = getIndex_(box);
    
    if (index == INVALID_INDEX)
    {
      x = y = z = INVALID_POSITION;
      
      return false;
    }
    
    x = index / (dimension_y_ * dimension_z_);
    index  -= x * dimension_y_ * dimension_z_;
    y = index / dimension_z_;
    z = index - y * dimension_z_;
    
    return true;
  }

  template <typename Item>
  BALL_INLINE 
  void HashGrid3<Item>::insert
    (Position x, Position y, Position z, const Item& item)
  {
    HashGridBox3<Item>* box = getBox(x, y, z);
    
    if (box != 0)
    {
      box->insert(item);
    }
  }

  template <typename Item>
  BALL_INLINE 
  void HashGrid3<Item>::insert(const Vector3& vector, const Item& item)
  {
    HashGridBox3<Item> *box = getBox(vector);
    
    if (box != 0)
    {
      box->insert(item);
    }
  }

  template <typename Item>
  BALL_INLINE 
  bool HashGrid3<Item>::remove(Position x, Position y, Position z, const Item& item)
  {
    HashGridBox3<Item>* box = getBox(x, y, z);
    
    if (box != 0)
    {
      return box->remove(item);
    }
    
    return false;
  }

  template <typename Item>
  BALL_INLINE 
  bool HashGrid3<Item>::remove(const Vector3& vector, const Item& item)
  {
    HashGridBox3<Item>* box = getBox(vector);
    
    if (box != 0)
    {
      return box->remove(item);
    }

    return false;
  }

  template <typename Item>
  BALL_INLINE 
  void HashGrid3<Item>::host(Visitor< HashGrid3<Item> >& visitor)
  {
    visitor.visit(*this);
  }

  template <typename Item>
  BALL_INLINE 
  bool HashGrid3<Item>::operator ==    (const HashGrid3<Item>& grid) const
  {
    if (getSize() != grid.getSize()
        || origin_ != grid.origin_
        || unit_ != grid.unit_
        || dimension_x_ != grid.dimension_x_
        || dimension_y_ != grid.dimension_y_
        || dimension_z_ != grid.dimension_z_)
    {
      return false;
    }
    
    const HashGridBox3<Item>* abox = box_;
    
    const HashGridBox3<Item>* bbox = grid.box_;
    
    const HashGridBox3<Item>* endbox = &box_[getSize()];
    
    while (abox < endbox)
    {
      if (*abox++ != *bbox++)
      {
        return false;
      }
    }
    
    return true;
  }

  template <typename Item>
  BALL_INLINE 
  bool HashGrid3<Item>::operator !=  (const HashGrid3<Item>& grid) const
  {
    return !(*this == grid);
  }

  template <typename Item>
  BALL_INLINE 
  bool HashGrid3<Item>::isEmpty() const
  {
    return (getSize() == 0);
  }

  template <typename Item>
  bool HashGrid3<Item>::isValid() const
  {
    Size size = getSize();
    
    for (Position index = 0; index < (Position)size; ++index)
    {
      if (box_[index].isValid() == false)
      {
        return false;
      }
    }

    return true;
  }

  template <typename Item>
  void HashGrid3<Item>::dump(std::ostream& s, Size depth) const
  {
    BALL_DUMP_STREAM_PREFIX(s);
    
    BALL_DUMP_DEPTH(s, depth);
    
    BALL_DUMP_DEPTH(s, depth);
    s << "  origin: " << origin_ << std::endl;
    
    BALL_DUMP_DEPTH(s, depth);
    s << "  unit: " << unit_.z << std::endl;
    
    BALL_DUMP_DEPTH(s, depth);
    s << "  dimension: " << dimension_x_ << " " 
      << dimension_y_ << " " 
      << dimension_z_ << std::endl;
    
    Size size = getSize();
    BALL_DUMP_DEPTH(s, depth);
    s << "  size: " << size << std::endl;

    BALL_DUMP_DEPTH(s, depth);
    s << "  non empty boxes: " << countNonEmptyBoxes() << std::endl;
    
    BALL_DUMP_DEPTH(s, depth);
    s << "  boxes:" << std::endl;
    Position x, y, z;
    for (Position index = 0; index < (Position)size; ++index)
    {
      BALL_DUMP_DEPTH(s, depth);
      getIndices(box_[index], x, y, z);
      s << "    " << index << ". box: (" 
        << x << ',' << y << ',' << z << ')' << std::endl;
      box_[index].dump(s, 1);
    }
    
    BALL_DUMP_DEPTH(s, depth);
    s << "  non-empty boxes:" << std::endl;

    for (Position i=0; i<27; ++i)
    {
      if (!box_[i].isEmpty())
        s << "    " << getIndex_(box_[i]) << std::endl;
    }
    BALL_DUMP_STREAM_SUFFIX(s);
  }

  template <typename Item>
  bool HashGrid3<Item>::apply(UnaryProcessor<Item>& processor)
  {
    if (processor.start() == false)
    {
      return false;
    }
    Processor::Result result;

    for (Position i=0; i<27; ++i)
    {
      HashGridBox3<Item>* box = &box_[i];
      for (typename HashGridBox3<Item>::DataItem *item = box->first_item_; item != 0; item = item->next_)
      {
        result = processor(item->item_);

        if (result <= Processor::BREAK)
        {
          return (result == Processor::BREAK) ? true : false;
        }
      }
    }

    return processor->finish();
  }

  template <typename Item>
  bool HashGrid3<Item>::apply(UnaryProcessor< HashGridBox3<Item> >& processor)
  {
    if (processor.start() == false)
    {
      return false;
    }

    Processor::Result result;

    for (Position i=0; i<27; ++i)
    {
      HashGridBox3<Item>* box = &box_[i];
      result = processor(*box);

      if (result <= Processor::BREAK)
      {
        return (result == Processor::BREAK) ? true : false;
      }
    }

    return processor->finish();
  }

  template <typename Item>
  BALL_INLINE 
  Index HashGrid3<Item>::getIndex_(const HashGridBox3<Item>& box) const
  {
    if (&box < box_ ||& box >= &box_[getSize()])
    {
      return INVALID_INDEX;
    } 
    else 
    {
      return (Index)(&box - box_);
    }
  }

  template <typename Item>
  BALL_INLINE
  void HashGrid3<Item>::setNeighbours_()
  {
    for (Position i=0; i<getSize(); ++i)
    {
      Position x, y, z;
      getIndices(box_[i], x, y, z);

      box_[i].neighbours[0] = &box_[i];

      Position current_neighbour = 1;
      // iterate over all the neighbouring boxes
      for (int nx = x-1; (nx < (int)x+2); nx++)
      {
        for (int ny = y-1; (ny < (int)y+2); ny++)
        {
          for (int nz = z-1; (nz < (int)z+2); nz++)
          {
            HashGridBox3<Item>* nbox = getBox(nx, ny, nz);

            if (nbox != &box_[i])
            {
              // NOTE: getBox returns 0 if indices are invalid, so this automatically works
              box_[i].neighbours[current_neighbour++] = nbox;
            }
          }
        }
      }
    }
  }

} // namespace BALL

#endif // BALL_DATATYPE_HASHGRID_H

---