Logo Search packages:      
Sourcecode: ball version File versions

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 
{
      /**   \defgroup GenericHash3D Three-dimensional Hash Grid
      \ingroup  GenericHash
      */
      //@{

      /**   Grid Box Class.
                  These boxes represent the buckets of a threedimensional hash grid.
                  Every such box contains a linear list of the objects that are
                  contained in this box. This list is accessible through a
                  DataIterator. \par

                  \ingroup GenericHash3D
      */
      template <typename Item>
00048       class HashGridBox3
      {
            public:

            /**   @name Constructors and Destructors 
            */    
            //@{

            ///   Default constructor
            HashGridBox3();
                  
            /// Copy constructor
            HashGridBox3(const HashGridBox3& grid_box, bool deep = true);

            /// Destructor
            ~HashGridBox3();

            /// Clears the grid box
            void clear();

            /** Clears the grid box.
                        Same as clear.
            */
            void destroy();
      
            //@}
            /**   @name Assignment 
            */
            //@{

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

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

            //@}
            /**   @name Accessors 
            */
            //@{

            /** Find an item in the item list of this grid box.
                        @param item the item to be searched for
                        @return a pointer to the desired item or a NULL pointer, if the 
                                                item could not be found.
            */
            Item* find(const Item &item);

            /// The const version of find()
            const Item* find(const Item& item) const;

            /** Counts all items in the data item list.
                        @return the size of the data item list.
            */
            Size getSize() const;

            /** Insert an item into the data item list of a grid box.
                        @param item the item to  be inserted
            */
            void insert(const Item& item);

            /** Remove the first occurrence of a certain item from the data item list.
                        @param item the item to be removed
                        @return bool - <tt>true</tt>, if the item could be removed, <tt>false</tt> 
                                                otherwise.
            */
            bool remove(const Item& item);

            /** Remove all occurences of a certain item from the data item list.
                        @param item the item to be removed
                        @return bool - <tt>true</tt>, if the item could be removed, <tt>false</tt> 
                                                otherwise.
            */
            bool removeAll(const Item& item);
                  
            //@}              
            /**   @name Miscellaneous 
            */
            //@{
            
            /// Host method
            void host(Visitor<HashGridBox3> &visitor);
            //@}
            /**   @name Predicates 
            */
            //@{

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

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

            /** Test whether an item is in the data item list
                        @param item
                        @return bool - <tt>true</tt> if instance has <tt>item</tt>, <tt>false</tt> otherwise.
            */
            bool has(const Item& item) const;

            /** Test, whether this box is empty, i. e. the data item list contains nothing
                        @return bool - <tt>true</tt>, if <tt>this</tt> is empty. <tt>false</tt> otherwise. 
            */
            bool isEmpty() const;

            //@}
            /**   @name Debugging and Diagnostics 
            */
            //@{
            
            ///
            bool isValid() const;
            ///
            void dump(std::ostream& s = std::cout, Size depth = 0) const;

            //@}
            /**   @name Internal Iterators 
            */
            //@{

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

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

            //@}
            /** @name   External Iterators 
            */
            //@{

            /// ?????
00181             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;

            /** BoxIterators iterate over all boxes that lie in the
                        direct neighborhood to a box, and over the box itself. 
                        Such an iterator traverses over 27 boxes.
            */
            typedef ForwardIterator
                  <HashGridBox3<Item>, HashGridBox3<Item>,
                  BoxIteratorPosition, BoxIteratorTraits>
00337                         BoxIterator;

            /// get the first box 
00340             BoxIterator beginBox()
            {
                  return BoxIterator::begin(*this);
            }

            /// get the last box
00346             BoxIterator endBox()
            {
                  return BoxIterator::end(*this);
            }


            /// This is the const version of  \link BoxIterator BoxIterator \endlink 
            typedef ConstForwardIterator
                  <HashGridBox3<Item>, HashGridBox3<Item>,
                  BoxIteratorPosition, BoxIteratorTraits>
00356                         ConstBoxIterator;

            /// get the first box 
00359             ConstBoxIterator beginBox() const
            {
                  return ConstBoxIterator::begin(*this);
            }

            /// get the last box
00365             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;

            /** Data iterator for grid boxes.
                        This iterator traverses the list of data items store in a  \link HashGridBox3 HashGridBox3 \endlink .
            */
            typedef ForwardIterator
                  <HashGridBox3<Item>, Item,
                   DataIteratorPosition, DataIteratorTraits>
00501                   DataIterator;

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

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


            /** Const data iterator for grid boxes.
                        This is the const version of  \link DataIterator DataIterator \endlink 
            */
            typedef ConstForwardIterator
                  <HashGridBox3<Item>, Item,
                   DataIteratorPosition, DataIteratorTraits>
00522                   ConstDataIterator;

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

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

            //@}  

            /// This array stores a pointer to the box itself and the 26 neighbours of the current box
00539             HashGridBox3* neighbours[27];
            //  private:
      
            DataItem*                           first_item_;
      };

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

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

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

      template<typename Item>  
00566       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 
00577       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>  
00601       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 
00616       const Item* HashGridBox3<Item>::find(const Item& item) const
      {
            return const_cast<HashGridBox3*>(this)->find(item);
      }

      template<typename Item>  
00622       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 
00634       void HashGridBox3<Item>::insert(const Item& item)
      {
            first_item_ = new DataItem(item, first_item_);
      }

      template<typename Item>  
00640       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>  
00671       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 
00711       void HashGridBox3<Item>::host(Visitor< HashGridBox3<Item> >& visitor)
      {
            visitor.visit(*this);
      }

      template<typename Item>  
00717       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 
00735       bool HashGridBox3<Item>::operator != (const HashGridBox3<Item>& box) const
      {
            return !(*this == box);
      }

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

      template<typename Item>  
      BALL_INLINE 
00749       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(); 
      }

      /**   Three-dimensional Hash Grid Class.
                  ????? \par
                  
      */
      template <typename Item>
00855       class HashGrid3
      {
            public:

            BALL_CREATE(HashGrid3)

            /**   @name Constructors and destructor 
            */
            //@{

            /// Default constructor
            HashGrid3();
                  
            /** Constructor using origin, dimensions, and spacings of the grid.
                        It creates a hashgrid at <tt>origin</tt> with axis-dependant spacings. 
                        @param origin
                        @param dimension_x
                        @param dimension_y
                        @param dimension_z
                        @param spacing_x
                        @param spacing_y
                        @param spacing_z
            */
            HashGrid3(const Vector3& origin, Size dimension_x, Size dimension_y,
                        Size dimension_z, float spacing_x, float spacing_y, float spacing_z);

            /** Constructor using origin, dimensions, and a single spacing (only
                        cubic grids)
            */ 
            HashGrid3(const Vector3& origin, Size dimension_x, Size dimension_y, 
                        Size dimension_z, float spacing);

            /** Constructor using two vectors and a single spacing.
                        This constructor creates a hash grid at <tt>origin</tt> with spacing
                        <tt>spacing</tt>. The vector <tt>size</tt> has to be relative to <tt>origin</tt>
                        and defines the opposite corner of the grid, thereby setting the size 
                        of the grid.
                        @param origin a vector defining the origin of our cubic hash grid
                        @param size a vector defining the opposite corner of the cubic grid
                        @param spacing this float will be used as spacing in all three dimensions
            */
            HashGrid3(const Vector3& origin, const Vector3& size, float spacing);

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

            /// Destructor
            virtual ~HashGrid3();

            /// Clears the whole grid
            virtual void clear();

            /// Clears the HashGridBox3 at position (x, y, z)
            void clear(Position x, Position y, Position z);

            /// Clears the HashGridBox3 at position <tt>vector</tt>
            void clear(const Vector3 &vector);

            /// Destroys the grid (obsolete, only calls clear())
            void destroy();

            /// Destroys a box of the grid (obsolete, only calls clear())
            void destroy(Position x, Position y, Position z);

            /// Destroys a box of the grid (obsolete, only calls clear())
            void destroy(const Vector3& vector);

            //@}
            /**   @name Assignment 
            */
            //@{

            /// assigns the content of a hash grid (obsolete)
            void set(const Vector3& origin, const Vector3& unit, 
                        Size  dimension_x, Size dimension_y, Size dimension_z);

            /// assigns the content of a hash grid (obsolete)
            void set(const Vector3& origin, float unit, Size size);

            /// assigns the content of a hash grid (obsolete)
            void set(const HashGrid3& grid, bool deep = true);

            /// Assignment operator
            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;

            //@}
            /**   @name Accessors 
            */
            //@{

            /// Counts the non-empty boxes of a grid.
            Size countNonEmptyBoxes() const;
            
            /// Returns the size of a grid, i. e. ?????
            Size getSize() const;

            /// Returns the origin of the grid
            Vector3& getOrigin();

            /// Returns a const reference of the grid origin
            const Vector3& getOrigin() const;

            /// Returns the unit of the grid
            Vector3& getUnit();

            /// Returns the unit of the grid (const version)
            const Vector3& getUnit() const;

            /// Get the x dimension of the grid
            Size getSizeX() const;

            /// Get the y dimension of the grid
            Size getSizeY() const;

            /// Get the z dimension of the grid
            Size getSizeZ() const;

            /// Return the HashGridBox3 at position (x, y, z)
            HashGridBox3<Item>* getBox(Position x, Position y, Position z);

            /// Return the HashGridBox3 at position (x, y, z) (const version)
            const HashGridBox3<Item>* getBox(Position x, Position y, Position z) const;

            /// Return the HashGridBox3 at position vector 
            HashGridBox3<Item>* getBox(const Vector3& vector);

            /// Return the HashGridBox3 at position vector (const version)
            const HashGridBox3<Item>* getBox(const Vector3 &vector) const;

            /// Get the position indices of a HashGridBox3
            bool getIndices(const HashGridBox3<Item>& box, 
                        Position& x, Position& y, Position& z) const;

            /// Insert an item at position (x, y, z)
            void insert(Position x, Position y, Position z, const Item& item);
            
            /// Insert an item at position <tt>vector</tt>
            void insert(const Vector3& vector, const Item& item);

            /// Remove an item from position (x, y ,z)
            bool remove(Position x, Position y, Position z, const Item& item);

            /// Remove an item from position <tt>vector</tt>
            bool remove(const Vector3& vector, const Item& item);

            //@}
            /**   @name Miscellaneous 
            */
            //@{

            ///
            void host(Visitor<HashGrid3>& visitor);

            //@}
            /**   @name Predicates 
            */
            //@{

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

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

            /// Tests, whether <tt>this</tt> is empty
            bool isEmpty() const;

            //@}
            /**   @name Debugging and Diagnostics 
            */
            //@{

            /// Validity check
            virtual bool isValid() const;

            /// Dump the contents of a HashGrid3 to a stream
            virtual void dump(std::ostream& s = std::cout, Size depth = 0) const;

            //@}

            /**   @name Internal Iterators 
            */
            //@{

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

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

            /** Get the nearest item for a point
                        @param distance number of adjacted boxes in each direction to search in
            */
            const Item* getClosestItem(const Vector3& point, Size distance) const;

            /** Calculate the minimum required spacing to build a HashGrid3 with the given size
                        and less than the given memory consumption.
                        @param memory the amount of memory in bytes
                        @param size   the diagonal of the grid
                        @return the minimal needed spacing
            */
            static float calculateMinSpacing(LongIndex memory, const Vector3& size);

            //@}
            /**   @name External Iterators 
            */
            //@{

            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;

            /// update the neighbour information in the individual boxes
            void setNeighbours_();

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

            
      //@}


      template <typename Item>
01259       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
01271             (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
01287             (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>
01302       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>
01316       HashGrid3<Item>::HashGrid3(const HashGrid3<Item>& grid, bool deep)
            :     box_(0),
                  origin_(),
                  unit_()
      {
            set(grid, deep);
      }

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

      template <typename Item>
01332       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 
01347       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 
01359       void HashGrid3<Item>::clear(const Vector3& vector)
      {
            HashGridBox3<Item>* box = getBox(vector);
            
            if (box != 0)
            {
                  box->clear();
            }
      }

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

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

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

      template <typename Item>
      void HashGrid3<Item>::set
01392             (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>
01411       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>
01428       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 
01452       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 
01480       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 
01495       Size HashGrid3<Item>::getSize() const
      {
            return (dimension_x_ * dimension_y_ * dimension_z_);
      }

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

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

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

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

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

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

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

      template <typename Item>
01550       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
01594       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
01604       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 
01620       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 
01627       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 
01643       const HashGridBox3<Item>* HashGrid3<Item>::getBox(const Vector3& vector) const
      {
            return ((HashGrid3 *)this)->getBox(vector);
      }

      template <typename Item>
      BALL_INLINE 
      bool HashGrid3<Item>::getIndices
01651             (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
01674             (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 
01686       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 
01698       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 
01712       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 
01733       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 
01764       bool HashGrid3<Item>::operator !=	(const HashGrid3<Item>& grid) const
      {
            return !(*this == grid);
      }

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

      template <typename Item>
01777       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>
01793       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
01906       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

Generated by  Doxygen 1.6.0   Back to index