BALL  1.4.1
hashGrid.h
Go to the documentation of this file.
00001 // -*- Mode: C++; tab-width: 2; -*-
00002 // vi: set ts=2:
00003 //
00004 
00005 #ifndef BALL_DATATYPE_HASHGRID_H
00006 #define BALL_DATATYPE_HASHGRID_H
00007 
00008 #ifndef BALL_COMMON_H
00009 # include <BALL/common.h>
00010 #endif
00011 
00012 #ifndef BALL_CONCEPT_FORWARDITERATOR_H
00013 # include <BALL/CONCEPT/forwardIterator.h>
00014 #endif
00015 
00016 #ifndef BALL_CONCEPT_VISITOR_H
00017 # include <BALL/CONCEPT/visitor.h>
00018 #endif
00019 
00020 #ifndef BALL_CONCEPT_PROCESSOR_H
00021 # include <BALL/CONCEPT/processor.h>
00022 #endif
00023 
00024 #ifndef BALL_MATHS_VECTOR3_H
00025 # include <BALL/MATHS/vector3.h>
00026 #endif
00027 
00028 #ifdef BALL_HAS_GNU_SLIST
00029 #include <ext/slist>
00030 #else
00031 #include <list>
00032 #endif
00033 
00034 #include <algorithm>
00035 
00036 namespace BALL 
00037 {
00038   namespace __private
00039   {
00040     extern const signed char BALL_EXPORT neighbour_table_[27][3];
00041   }
00042 
00043   template <typename Item> class HashGrid3;
00044 
00049 
00058   template <typename Item>
00059   class HashGridBox3
00060   {
00061     public:
00062 
00066 
00068     HashGridBox3(HashGrid3<Item>* parent);
00069 
00071     void clear();
00072 
00076     void destroy();
00077   
00079 
00082 
00084 
00087 
00088     void setParent(HashGrid3<Item>* p);
00089 
00093     void getIndices(Position& x, Position& y, Position& z);
00094 
00100     Item* find(const Item &item);
00101 
00103     const Item* find(const Item& item) const;
00104 
00108     Size getSize() const;
00109 
00113     void insert(const Item& item);
00114 
00120     bool remove(const Item& item);
00121 
00127     bool removeAll(const Item& item);
00128       
00130 
00133     
00135     void host(Visitor<HashGridBox3> &visitor);
00137 
00140 
00142     bool operator == (const HashGridBox3& box) const;
00143 
00145     bool operator != (const HashGridBox3& box) const;
00146 
00151     bool has(const Item& item) const;
00152 
00156     bool isEmpty() const;
00157 
00159 
00162     
00164     bool isValid() const;
00166     void dump(std::ostream& s = std::cout, Size depth = 0) const;
00167 
00169 
00172 
00174     bool apply(UnaryProcessor<Item>& processor);
00175 
00177     bool apply(UnaryProcessor< HashGridBox3<Item> >& processor);
00178 
00180 
00183     typedef Position BoxIteratorPosition;
00184     
00185     class BoxIteratorTraits
00186     {
00187       public:
00188 
00189       BALL_CREATE_DEEP(BoxIteratorTraits)
00190 
00191       virtual ~BoxIteratorTraits() {}
00192 
00193       BoxIteratorTraits()
00194         : bound_(0),
00195           position_(0),
00196           x_(0), y_(0), z_(0)
00197       {
00198       }
00199 
00200       BoxIteratorTraits(const HashGridBox3& box)
00201         : bound_((HashGridBox3 *)&box),
00202           position_(0)
00203       {
00204         bound_->getIndices(x_, y_, z_);
00205       }
00206 
00207       BoxIteratorTraits(const BoxIteratorTraits& traits, bool /* deep */ = true)
00208         : bound_(traits.bound_),
00209           position_(traits.position_)
00210       {
00211       }
00212 
00213       HashGridBox3* getContainer()
00214       {
00215         return bound_;
00216       }
00217 
00218       const HashGridBox3* getContainer() const
00219       {
00220         return bound_;
00221       }
00222 
00223       bool isSingular() const
00224       {
00225         return (bound_ == 0);
00226       }
00227         
00228       BoxIteratorPosition& getPosition()
00229       {
00230         return position_;
00231       }
00232 
00233       const BoxIteratorPosition& getPosition() const
00234       {
00235         return position_;
00236       }
00237 
00238       bool operator == (const BoxIteratorTraits& traits) const
00239       {
00240         return (position_ == traits.position_);
00241       }
00242 
00243       bool operator != (const BoxIteratorTraits& traits) const
00244       {
00245         return (position_ != traits.position_);
00246       }
00247         
00248       bool isValid() const
00249       {
00250         return (bound_ != 0 && position_ < 27);
00251       }
00252 
00253       void invalidate()
00254       {
00255         bound_ = 0;
00256         position_ = 100;
00257       }
00258 
00259       void toBegin()
00260       {
00261         position_ = 0;
00262         cur_box_ = bound_;
00263       }
00264 
00265       bool isBegin() const
00266       {
00267         return (position_ == 0);
00268       }
00269 
00270       void toEnd()
00271       {
00272         position_ = 27;
00273         cur_box_ = 0;
00274       }
00275 
00276       bool isEnd() const
00277       {
00278         return (position_ == 27);
00279       }
00280 
00281       HashGridBox3<Item>& getData()
00282       {
00283         return *cur_box_;
00284       }
00285 
00286       const HashGridBox3<Item>& getData() const
00287       {
00288         return *cur_box_;
00289       }
00290 
00291       void forward()
00292       {
00293         ++position_;
00294         // iterate to the next existing box
00295         while (     position_ < 27
00296                && !(cur_box_ = bound_->parent->getBox(x_ + __private::neighbour_table_[position_][0],
00297                                                       y_ + __private::neighbour_table_[position_][1],
00298                                                       z_ + __private::neighbour_table_[position_][2])))
00299         {
00300           ++position_;
00301         }
00302       }
00303     
00304       private:
00305 
00306       HashGridBox3<Item> *bound_;
00307       HashGridBox3<Item> *cur_box_;
00308       BoxIteratorPosition position_;
00309       Position x_, y_, z_;
00310     };
00311 
00312     friend class BoxIteratorTraits;
00313 
00318     typedef ForwardIterator
00319       <HashGridBox3<Item>, HashGridBox3<Item>,
00320       BoxIteratorPosition, BoxIteratorTraits>
00321         BoxIterator;
00322 
00324     BoxIterator beginBox()
00325     {
00326       return BoxIterator::begin(*this);
00327     }
00328 
00330     BoxIterator endBox()
00331     {
00332       return BoxIterator::end(*this);
00333     }
00334 
00335 
00337     typedef ConstForwardIterator
00338       <HashGridBox3<Item>, HashGridBox3<Item>,
00339       BoxIteratorPosition, BoxIteratorTraits>
00340         ConstBoxIterator;
00341 
00343     ConstBoxIterator beginBox() const
00344     {
00345       return ConstBoxIterator::begin(*this);
00346     }
00347 
00349     ConstBoxIterator endBox() const
00350     {
00351       return ConstBoxIterator::end(*this);
00352     }
00353 
00354 #ifdef BALL_HAS_GNU_SLIST
00355     typedef typename __gnu_cxx::slist<Item> DataContainer;
00356 #else
00357     typedef typename std::list<Item> DataContainer;
00358 #endif
00359 
00360     typedef typename DataContainer::iterator DataIteratorPosition;
00361     
00362     class DataIteratorTraits
00363     {
00364       public:
00365 
00366       BALL_CREATE_DEEP(DataIteratorTraits)
00367 
00368         virtual ~DataIteratorTraits() {}
00369 
00370       DataIteratorTraits()
00371       : bound_(0),
00372         position_()
00373       {
00374       }
00375         
00376       DataIteratorTraits(const HashGridBox3& box)
00377       : bound_((HashGridBox3 *)&box),
00378         position_(bound_->data.begin())
00379       {
00380       }
00381         
00382       DataIteratorTraits(const DataIteratorTraits& traits, bool /* deep */ = true)
00383       : bound_(traits.bound_),
00384         position_(traits.position_)
00385       {
00386       }
00387         
00388       const DataIteratorTraits& operator = (const DataIteratorTraits &traits)
00389       {
00390         bound_ = traits.bound_;
00391         position_ = traits.position_;
00392         return *this;
00393       }
00394 
00395       HashGridBox3* getContainer()
00396       {
00397         return bound_;
00398       }
00399 
00400       const HashGridBox3* getContainer() const
00401       {
00402         return bound_;
00403       }
00404 
00405       bool isSingular() const
00406       {
00407         return (bound_ == 0);
00408       }
00409         
00410       DataIteratorPosition& getPosition()
00411       {
00412         return position_;
00413       }
00414 
00415       const DataIteratorPosition& getPosition() const
00416       {
00417         return position_;
00418       }
00419 
00420       bool operator == (const DataIteratorTraits &traits) const
00421       {
00422         return (position_ == traits.position_);
00423       }
00424 
00425       bool operator != (const DataIteratorTraits &traits) const
00426       {
00427         return (position_ != traits.position_);
00428       }
00429 
00430       bool isValid() const
00431       {
00432         return (bound_ != 0 && position_ != bound_->data.end());
00433       }
00434 
00435       void invalidate()
00436       {
00437         bound_ = 0;
00438         position_ = bound_->data.end();
00439       }
00440 
00441       void toBegin()
00442       {
00443         position_ = bound_->data.begin();
00444       }
00445 
00446       bool isBegin() const
00447       {
00448         return (position_ == bound_->data.begin());
00449       }
00450 
00451       void toEnd()
00452       {
00453         position_ = bound_->data.end();
00454       }
00455 
00456       bool isEnd() const
00457       {
00458         return (position_ == bound_->data.end());
00459       }
00460 
00461       Item& getData()
00462       {
00463         return *position_;
00464       }
00465 
00466       const Item& getData() const
00467       {
00468         return *position_;
00469       }
00470 
00471       void forward()
00472       {
00473         ++position_;
00474       }
00475   
00476       private:
00477 
00478       HashGridBox3<Item>*   bound_;
00479       DataIteratorPosition  position_;
00480     };
00481 
00482     friend class DataIteratorTraits;
00483 
00487     typedef ForwardIterator
00488       <HashGridBox3<Item>, Item,
00489        DataIteratorPosition, DataIteratorTraits>
00490       DataIterator;
00491 
00493     DataIterator beginData()
00494     {
00495       return DataIterator::begin(*this);
00496     }
00497 
00499     DataIterator endData()
00500     {
00501       return DataIterator::end(*this);
00502     }
00503 
00504 
00508     typedef ConstForwardIterator
00509       <HashGridBox3<Item>, Item,
00510        DataIteratorPosition, DataIteratorTraits>
00511       ConstDataIterator;
00512 
00514     ConstDataIterator beginData() const
00515     {
00516       return ConstDataIterator::begin(*this);
00517     }
00518 
00520     ConstDataIterator endData() const
00521     {
00522       return ConstDataIterator::end(*this);
00523     }
00524 
00526 
00527     HashGrid3<Item>* parent;
00528 
00529     DataContainer data;
00530   };
00531 
00532   template<typename Item>  
00533   HashGridBox3<Item>::HashGridBox3(HashGrid3<Item>* p)
00534     : parent(p)
00535   {
00536   }
00537 
00538   template<typename Item>  
00539   void HashGridBox3<Item>::clear()
00540   {
00541     data.clear();
00542   }
00543 
00544   template<typename Item>  
00545   BALL_INLINE 
00546   void HashGridBox3<Item>::destroy()
00547   {
00548     clear();
00549   }
00550 
00551   template<typename Item>
00552   BALL_INLINE void HashGridBox3<Item>::setParent(HashGrid3<Item>* p)
00553   {
00554     parent = p;
00555   }
00556 
00557   template<typename Item>
00558   BALL_INLINE
00559   void HashGridBox3<Item>::getIndices(Position& x, Position& y, Position& z)
00560   {
00561     parent->getIndices(*this, x, y, z);
00562   }
00563 
00564   template<typename Item>  
00565   Item* HashGridBox3<Item>::find(const Item& item)
00566   {
00567     typename DataContainer::iterator found = std::find(data.begin(), data.end(), item);
00568 
00569     if (found != data.end())
00570     {
00571       return &(*found);
00572     }
00573 
00574     return 0;
00575   }
00576 
00577   template<typename Item>  
00578   BALL_INLINE 
00579   const Item* HashGridBox3<Item>::find(const Item& item) const
00580   {
00581     return const_cast<HashGridBox3*>(this)->find(item);
00582   }
00583 
00584   template<typename Item>  
00585   Size HashGridBox3<Item>::getSize() const
00586   {
00587     return data.size();
00588   }
00589 
00590   template<typename Item>  
00591   BALL_INLINE 
00592   void HashGridBox3<Item>::insert(const Item& item)
00593   {
00594     data.push_front(item);
00595   }
00596 
00597   template<typename Item>  
00598   bool HashGridBox3<Item>::remove(const Item& item)
00599   {
00600 #ifdef BALL_HAS_GNU_SLIST
00601     if(data.empty())
00602     {
00603       return false;
00604     }
00605 
00606     if(*data.begin() == item)
00607     {
00608       data.pop_front();
00609       return true;
00610     }
00611 
00612     DataIteratorPosition prev = data.begin();
00613     DataIteratorPosition pos = prev;
00614     for(++pos; pos != data.end(); ++pos)
00615     {
00616       if(*pos == item)
00617       {
00618         data.erase_after(prev);
00619         return true;
00620       }
00621 
00622       prev = pos;
00623     }
00624     return false;
00625 #else
00626     DataIteratorPosition pos = std::find(data.begin(), data.end(), item);
00627 
00628     if (pos != data.end())
00629     {
00630       data.erase(pos);
00631 
00632       return true;
00633     }
00634 
00635     return false;
00636 #endif
00637   }
00638 
00639   template<typename Item>  
00640   bool HashGridBox3<Item>::removeAll(const Item& item)
00641   {
00642     data.remove(item);
00643 
00644     return true;
00645   }
00646 
00647   template <typename Item>
00648   BALL_INLINE 
00649   void HashGridBox3<Item>::host(Visitor< HashGridBox3<Item> >& visitor)
00650   {
00651     visitor.visit(*this);
00652   }
00653 
00654   template<typename Item>  
00655   bool HashGridBox3<Item>::operator == (const HashGridBox3<Item>& box) const
00656   {
00657     return (data == box.data);
00658   }
00659 
00660   template<typename Item>  
00661   BALL_INLINE 
00662   bool HashGridBox3<Item>::operator != (const HashGridBox3<Item>& box) const
00663   {
00664     return !(*this == box);
00665   }
00666 
00667   template<typename Item>  
00668   BALL_INLINE 
00669   bool HashGridBox3<Item>::has(const Item& item) const
00670   {
00671     return (std::find(data.begin(), data.end(), item) != data.end());
00672   }
00673 
00674   template<typename Item>  
00675   BALL_INLINE 
00676   bool HashGridBox3<Item>::isEmpty() const
00677   {
00678     return data.empty();
00679   }
00680 
00681   template<typename Item>  
00682   bool HashGridBox3<Item>::isValid() const
00683   {
00684     // this is no longer required...
00685     return true;
00686   }
00687 
00688   template<typename Item>  
00689   void HashGridBox3<Item>::dump(std::ostream& s, Size depth) const
00690   {
00691     BALL_DUMP_STREAM_PREFIX(s);
00692     
00693     BALL_DUMP_DEPTH(s, depth);
00694     
00695     BALL_DUMP_DEPTH(s, depth);
00696     s << "  size: " << getSize() << std::endl;
00697     
00698     BALL_DUMP_DEPTH(s, depth);
00699     s << "  data:" << std::endl;
00700     for (typename DataContainer::const_iterator d_it = data.begin(); d_it != data.end(); ++d_it)
00701     {
00702       BALL_DUMP_DEPTH(s, depth);
00703       s << "    " << *d_it << std::endl;
00704     }
00705 
00706     BALL_DUMP_STREAM_SUFFIX(s);
00707   }
00708 
00709   template <typename Item>
00710   bool HashGridBox3<Item>::apply(UnaryProcessor<Item>& processor)
00711   {
00712     if (processor.start() == false)
00713     {
00714       return false;
00715     }
00716 
00717     Processor::Result result;
00718       
00719     for (typename DataContainer::iterator d_it = data.begin(); d_it != data.end(); ++d_it)
00720     {
00721       result = processor(*d_it);
00722 
00723       if (result <= Processor::BREAK)
00724       {
00725         return (result == Processor::BREAK) ? true : false;
00726       }
00727     }
00728 
00729     return processor.finish(); 
00730   }
00731 
00732   template <typename Item>
00733   bool HashGridBox3<Item>::apply(UnaryProcessor< HashGridBox3<Item> >& processor)
00734   {
00735     if (processor.start() == false)
00736     {
00737       return false;
00738     }
00739  
00740     Processor::Result result;
00741 
00742     for (BoxIterator it = beginBox(); +it; ++it)
00743     {
00744       result = processor(*it);
00745 
00746       if (result <= Processor::BREAK)
00747       {
00748         return (result == Processor::BREAK) ? true : false;
00749       }
00750     }
00751 
00752     return processor.finish(); 
00753   }
00754 
00759   template <typename Item>
00760   class HashGrid3
00761   {
00762     public:
00763 
00764     BALL_CREATE(HashGrid3)
00765 
00766     
00769 
00771     HashGrid3();
00772       
00783     HashGrid3(const Vector3& origin, Size dimension_x, Size dimension_y,
00784         Size dimension_z, float spacing_x, float spacing_y, float spacing_z);
00785 
00789     HashGrid3(const Vector3& origin, Size dimension_x, Size dimension_y, 
00790         Size dimension_z, float spacing);
00791 
00801     HashGrid3(const Vector3& origin, const Vector3& size, float spacing);
00802 
00804     HashGrid3(const HashGrid3& grid, bool deep = true);
00805 
00807     virtual ~HashGrid3();
00808 
00810     virtual void clear();
00811 
00813     void clear(Position x, Position y, Position z);
00814 
00816     void clear(const Vector3 &vector);
00817 
00819     void destroy();
00820 
00822     void destroy(Position x, Position y, Position z);
00823 
00825     void destroy(const Vector3& vector);
00826 
00828 
00831 
00833     void set(const Vector3& origin, const Vector3& unit, 
00834         Size  dimension_x, Size dimension_y, Size dimension_z);
00835 
00837     void set(const Vector3& origin, float unit, Size size);
00838 
00840     void set(const HashGrid3& grid, bool deep = true);
00841 
00843     const HashGrid3& operator = (const HashGrid3& grid);
00844 
00846     void get(Vector3& origin, Vector3& unit, Size&  dimension_x, Size&  dimension_y, Size&  dimension_z) const; 
00847 
00849     void get(HashGrid3& grid, bool deep = true) const;
00850 
00852 
00855 
00857     Size countNonEmptyBoxes() const;
00858     
00860     Size getSize() const;
00861 
00863     Vector3& getOrigin();
00864 
00866     const Vector3& getOrigin() const;
00867 
00869     Vector3& getUnit();
00870 
00872     const Vector3& getUnit() const;
00873 
00875     Size getSizeX() const;
00876 
00878     Size getSizeY() const;
00879 
00881     Size getSizeZ() const;
00882 
00884     HashGridBox3<Item>* getBox(Position x, Position y, Position z);
00885 
00887     const HashGridBox3<Item>* getBox(Position x, Position y, Position z) const;
00888 
00890     HashGridBox3<Item>* getBox(const Vector3& vector);
00891 
00893     const HashGridBox3<Item>* getBox(const Vector3 &vector) const;
00894 
00896     bool getIndices(const HashGridBox3<Item>& box, 
00897         Position& x, Position& y, Position& z) const;
00898 
00900     void insert(Position x, Position y, Position z, const Item& item);
00901     
00903     void insert(const Vector3& vector, const Item& item);
00904 
00906     bool remove(Position x, Position y, Position z, const Item& item);
00907 
00909     bool remove(const Vector3& vector, const Item& item);
00910 
00912 
00915 
00917     void host(Visitor<HashGrid3>& visitor);
00918 
00920 
00923 
00925     bool operator == (const HashGrid3& grid) const;
00926 
00928     bool operator != (const HashGrid3& grid) const;
00929 
00931     bool isEmpty() const;
00932 
00934 
00937 
00939     virtual bool isValid() const;
00940 
00942     virtual void dump(std::ostream& s = std::cout, Size depth = 0) const;
00943 
00945 
00949 
00951     bool apply(UnaryProcessor<Item> &processor);
00952 
00954     bool apply(UnaryProcessor< HashGridBox3<Item> > &processor);
00955 
00959     const Item* getClosestItem(const Vector3& point, Size distance) const;
00960 
00967     static float calculateMinSpacing(LongIndex memory, const Vector3& size);
00968 
00970 
00973 
00974     typedef Position BoxIteratorPosition;
00975     
00976     class BoxIteratorTraits
00977     {
00978       public:
00979 
00980       BALL_CREATE_DEEP(BoxIteratorTraits)
00981 
00982       virtual ~BoxIteratorTraits() {}
00983 
00984       BoxIteratorTraits()
00985         : bound_(0),
00986           position_(0)
00987       {
00988       }
00989         
00990       BoxIteratorTraits(const HashGrid3 &grid)
00991         : bound_((HashGrid3 *)&grid),
00992           position_(0)
00993       {
00994       }
00995         
00996       BoxIteratorTraits(const BoxIteratorTraits& traits, bool /* deep */ = true)
00997         : bound_(traits.bound_),
00998           position_(traits.position_)
00999       {
01000       }
01001         
01002       const BoxIteratorTraits& operator = (const BoxIteratorTraits& traits)
01003       {
01004         bound_ = traits.bound_;
01005         position_ = traits.position_;
01006         return *this;
01007       }
01008 
01009       HashGrid3* getContainer()
01010       {
01011         return bound_;
01012       }
01013 
01014       const HashGrid3* getContainer() const
01015       {
01016         return bound_;
01017       }
01018 
01019       bool isSingular() const
01020       {
01021         return (bound_ == 0);
01022       }
01023         
01024       BoxIteratorPosition& getPosition()
01025       {
01026         return position_;
01027       }
01028 
01029       const BoxIteratorPosition& getPosition() const
01030       {
01031         return position_;
01032       }
01033 
01034       bool operator == (const BoxIteratorTraits& traits) const
01035       {
01036         return (position_ == traits.position_);
01037       }
01038 
01039       bool operator != (const BoxIteratorTraits& traits) const
01040       {
01041         return (position_ != traits.position_);
01042       }
01043         
01044       bool isValid() const
01045       {
01046         return (bound_ != 0 && position_ < bound_->getSize());
01047       }
01048 
01049       void invalidate()
01050       {
01051         bound_ = 0;
01052         position_ = bound_->getSize()+1;
01053       }
01054 
01055       void toBegin()
01056       {
01057         position_ = 0;
01058       }
01059 
01060       bool isBegin() const
01061       {
01062         return (position_ == 0);
01063       }
01064 
01065       void toEnd()
01066       {
01067         position_ = bound_->getSize();
01068       }
01069 
01070       bool isEnd() const
01071       {
01072         return (position_ == bound_->getSize());
01073       }
01074 
01075       HashGridBox3<Item>& getData()
01076       {
01077         return bound_->box_[position_];
01078       }
01079 
01080       const HashGridBox3<Item>& getData() const
01081       {
01082         return bound_->box_[position_];
01083       }
01084 
01085       void forward()
01086       {
01087         ++position_;
01088       }
01089     
01090       private:
01091 
01092       HashGrid3<Item>* bound_;
01093       BoxIteratorPosition position_;
01094     };
01095 
01096     friend class BoxIteratorTraits;
01097 
01099     typedef ForwardIterator
01100       <HashGrid3<Item>, HashGridBox3<Item>,
01101        BoxIteratorPosition, BoxIteratorTraits>
01102       BoxIterator;
01103 
01105     BoxIterator beginBox()
01106     {
01107       return BoxIterator::begin(*this);
01108     }
01109 
01111     BoxIterator endBox()
01112     {
01113       return BoxIterator::end(*this);
01114     }
01115 
01116 
01118     typedef ConstForwardIterator
01119       <HashGrid3<Item>, HashGridBox3<Item>,
01120        BoxIteratorPosition, BoxIteratorTraits>
01121       ConstBoxIterator;
01122 
01124     ConstBoxIterator beginBox() const
01125     {
01126       return ConstBoxIterator::begin(*this);
01127     }
01128 
01130     ConstBoxIterator endBox() const
01131     {
01132       return ConstBoxIterator::end(*this);
01133     }
01134 
01136 
01137     private:
01138 
01139     //_
01140     Index getIndex_(const HashGridBox3<Item>& box) const;
01141 
01142     //_
01143     Vector3 origin_;
01144     //_
01145     Vector3 unit_;
01146     //_
01147     Size dimension_x_;
01148     //_
01149     Size dimension_y_;
01150     //_
01151     Size dimension_z_;
01152     //_
01153     vector<HashGridBox3<Item> > box_;
01154   };
01155 
01156     
01158 
01159 
01160   template <typename Item>
01161   HashGrid3<Item>::HashGrid3()
01162     : origin_(0,0,0),
01163       unit_(0,0,0),
01164       dimension_x_(0),
01165       dimension_y_(0),
01166       dimension_z_(0)
01167   {
01168   }
01169 
01170   template <typename Item>
01171   HashGrid3<Item>::HashGrid3
01172     (const Vector3 &originvector,
01173      Size dimension_x, Size dimension_y, Size dimension_z,
01174      float spacing_x, float spacing_y, float spacing_z)
01175     : origin_(originvector),
01176       unit_(spacing_x, spacing_y, spacing_z),
01177       dimension_x_(dimension_x),
01178       dimension_y_(dimension_y),
01179       dimension_z_(dimension_z),
01180       box_(dimension_x * dimension_y * dimension_z, HashGridBox3<Item>(this))
01181   {
01182   }
01183 
01184   template <typename Item>
01185   HashGrid3<Item>::HashGrid3
01186     (const Vector3& origin,
01187      Size dimension_x, Size dimension_y, Size dimension_z, float spacing)
01188     : origin_(origin),
01189       unit_(spacing, spacing, spacing),
01190       dimension_x_(dimension_x),
01191       dimension_y_(dimension_y),
01192       dimension_z_(dimension_z),
01193       box_(dimension_x * dimension_y * dimension_z, HashGridBox3<Item>(this))
01194   {
01195   }
01196 
01197   // this constructor creates a linear array of HashGridBox3 objects.
01198   template <typename Item>
01199   HashGrid3<Item>::HashGrid3(const Vector3& origin, const Vector3& size,
01200       float spacing)
01201     : origin_(origin),
01202       unit_(spacing, spacing, spacing),
01203       dimension_x_((Size)(size.x / spacing + 1.0)),
01204       dimension_y_((Size)(size.y / spacing + 1.0)),
01205       dimension_z_((Size)(size.z / spacing + 1.0)),
01206       box_(dimension_x_ * dimension_y_ * dimension_z_, HashGridBox3<Item>(this))
01207   {
01208   }
01209 
01210   template <typename Item>
01211   HashGrid3<Item>::HashGrid3(const HashGrid3<Item>& grid, bool deep)
01212   {
01213     set(grid, deep);
01214   }
01215 
01216   template <typename Item>
01217   HashGrid3<Item>::~HashGrid3()
01218   {
01219   }
01220 
01221   template <typename Item>
01222   void HashGrid3<Item>::clear()
01223   {
01224     Size size = dimension_x_ * dimension_y_ * dimension_z_;
01225 
01226     for (Position index = 0; index < (Position)size; ++index)
01227     {
01228       box_[index].clear();
01229     }
01230   }
01231 
01232   template <typename Item>
01233   BALL_INLINE 
01234   void HashGrid3<Item>::clear(Position x, Position y, Position z)
01235   {
01236     HashGridBox3<Item>* box = getBox(x, y, z);
01237     
01238     if (box != 0)
01239     {
01240       box->clear();
01241     }
01242   }
01243 
01244   template <typename Item>
01245   BALL_INLINE 
01246   void HashGrid3<Item>::clear(const Vector3& vector)
01247   {
01248     HashGridBox3<Item>* box = getBox(vector);
01249     
01250     if (box != 0)
01251     {
01252       box->clear();
01253     }
01254   }
01255 
01256   template <typename Item>
01257   BALL_INLINE 
01258   void HashGrid3<Item>::destroy()
01259   {
01260     clear();
01261   }
01262 
01263   template <typename Item>
01264   BALL_INLINE 
01265   void HashGrid3<Item>::destroy(Position x, Position y, Position z)
01266   {
01267     clear(x, y, z);
01268   }
01269 
01270   template <typename Item>
01271   BALL_INLINE 
01272   void HashGrid3<Item>::destroy(const Vector3 &vector)
01273   {
01274     clear(vector);
01275   }
01276 
01277   template <typename Item>
01278   void HashGrid3<Item>::set
01279     (const Vector3& origin, const Vector3& unit,
01280      Size dimension_x, Size dimension_y, Size dimension_z)
01281   {
01282     origin_.set(origin);
01283     unit_.set(unit);
01284     dimension_x_ = dimension_x;
01285     dimension_y_ = dimension_y;
01286     dimension_z_ = dimension_z;
01287     box_.assign(getSize(), HashGridBox3<Item>(this));
01288   }
01289 
01290   template <typename Item>
01291   void HashGrid3<Item>::set(const Vector3& origin, float unit, Size size)
01292   {
01293     origin_.set(origin);
01294     unit_.set(unit, unit, unit);
01295     dimension_x_ = size;
01296     dimension_y_ = size;
01297     dimension_z_ = size;
01298     box_.assign(getSize(), HashGridBox3<Item>(this));
01299   }
01300 
01301   template <typename Item>
01302   void HashGrid3<Item>::set(const HashGrid3<Item>& grid, bool /* deep */)
01303   {
01304     origin_.set(grid.origin_);
01305     unit_.set(grid.unit_);
01306     dimension_x_ = grid.dimension_x_;
01307     dimension_y_ = grid.dimension_y_;
01308     dimension_z_ = grid.dimension_z_;
01309     box_ = grid.box_;
01310 
01311     for(Position i = 0; i < box_.size(); ++i)
01312     {
01313       box_[i].setParent(this);
01314     }
01315   }
01316 
01317   template <typename Item>
01318   BALL_INLINE 
01319   const HashGrid3<Item>& HashGrid3<Item>::operator = (const HashGrid3<Item> &grid)
01320   {
01321     set(grid);
01322     
01323     return *this;
01324   }
01325 
01326   template <typename Item>
01327   BALL_INLINE 
01328   void HashGrid3<Item>::get(Vector3 &origin, Vector3 &unit,
01329                             Size& dimension_x, Size& dimension_y, Size& dimension_z) const
01330   {
01331     origin.set(origin_);
01332     unit.set(unit_);
01333     dimension_x = dimension_x_;
01334     dimension_y = dimension_y_;
01335     dimension_z = dimension_z_;
01336   }
01337 
01338   template <typename Item>
01339   BALL_INLINE void 
01340   HashGrid3<Item>::get(HashGrid3<Item> &grid, bool deep) const
01341   {
01342     grid.set(*this, deep);
01343   }
01344 
01345   template <typename Item>
01346   Size 
01347   HashGrid3<Item>::countNonEmptyBoxes() const
01348   {
01349     Size size = 0;
01350 
01351     for (Position i=0; i<27; ++i)
01352     {
01353       if (!box_[i].isEmpty())
01354         ++size;
01355     }
01356 
01357     return size;
01358   }
01359 
01360   template <typename Item>
01361   BALL_INLINE 
01362   Size HashGrid3<Item>::getSize() const
01363   {
01364     return (dimension_x_ * dimension_y_ * dimension_z_);
01365   }
01366 
01367   template <typename Item>
01368   BALL_INLINE 
01369   Vector3& HashGrid3<Item>::getOrigin()
01370   {
01371     return origin_;
01372   }
01373 
01374   template <typename Item>
01375   BALL_INLINE 
01376   const Vector3& HashGrid3<Item>::getOrigin() const
01377   {
01378     return origin_;
01379   }
01380 
01381   template <typename Item>
01382   BALL_INLINE 
01383   Vector3& HashGrid3<Item>::getUnit()
01384   {
01385     return unit_;
01386   }
01387 
01388   template <typename Item>
01389   BALL_INLINE 
01390   const Vector3& HashGrid3<Item>::getUnit() const
01391   {
01392     return unit_;
01393   }
01394 
01395   template <typename Item>
01396   BALL_INLINE 
01397   Size HashGrid3<Item>::getSizeX() const
01398   {
01399     return dimension_x_;
01400   }
01401 
01402   template <typename Item>
01403   BALL_INLINE 
01404   Size HashGrid3<Item>::getSizeY() const
01405   {
01406     return dimension_y_;
01407   }
01408 
01409   template <typename Item>
01410   BALL_INLINE 
01411   Size HashGrid3<Item>::getSizeZ() const
01412   {
01413     return dimension_z_;
01414   }
01415 
01416   template <typename Item>
01417   const Item* HashGrid3<Item>::getClosestItem(const Vector3& point, Size dist) const
01418   {
01419     const HashGridBox3<Item>* box = getBox(point);
01420     if (!box) return 0;
01421 
01422     Position x, y, z;
01423     getIndices(*box, x, y, z);
01424 
01425     const Item* item = 0;
01426     float distance = FLT_MAX;
01427 
01428     // iterator over neighbour boxes
01429     for (Index xi = -(Index)dist; xi <= (Index)dist; xi++)
01430     {
01431       const Index xn = x + xi;
01432       for (Index yi = -(Index)dist; yi <= (Index)dist; yi++)
01433       {
01434         const Index yn = y + yi;
01435         for (Index zi = -(Index)dist; zi <= (Index)dist; zi++)
01436         {
01437           // iterate over all data items
01438           const HashGridBox3<Item>* const box_ptr = getBox(xn, yn, z+zi); 
01439           if (box_ptr != 0 && !box_ptr->isEmpty())
01440           {
01441             typename HashGridBox3<Item>::ConstDataIterator hit = box_ptr->beginData();
01442             for (;hit != box_ptr->endData(); hit++)
01443             {
01444               const float new_dist = ((*hit)->getPosition() - point).getSquareLength();
01445               if (new_dist < distance)
01446               {
01447                 item = &*hit;
01448                 distance = new_dist;
01449               }
01450             }
01451           }
01452         }
01453       }
01454     }
01455 
01456     return item;
01457   }
01458 
01459   template <typename Item>
01460   BALL_INLINE
01461   float HashGrid3<Item>::calculateMinSpacing(LongIndex memory, const Vector3& size)
01462   {
01463     LongSize memory_for_box = sizeof(HashGridBox3<Item>) + sizeof(HashGridBox3<Item>*);
01464     LongSize nr_boxes =(LongSize)floor((float)(memory / memory_for_box));
01465 
01466     return pow((double)((size.x * size.y * size.z) / nr_boxes), (double)(1.0 / 3.0));
01467   }
01468 
01469   template <typename Item>
01470   BALL_INLINE
01471   HashGridBox3<Item>* HashGrid3<Item>::getBox(Position x, Position y, Position z)
01472   {
01473     if (x >= (Position)dimension_x_ ||
01474         y >= (Position)dimension_y_ ||
01475         z >= (Position)dimension_z_)
01476     {
01477       return 0;
01478     } 
01479     else 
01480     {
01481       return &(box_[x * dimension_y_ * dimension_z_ + y * dimension_z_ + z]);
01482     }
01483   }
01484 
01485   template <typename Item>
01486   BALL_INLINE 
01487   const HashGridBox3<Item>* HashGrid3<Item>::getBox(Position x, Position y, Position z) const
01488   {
01489     return ((HashGrid3*)this)->getBox(x, y, z);
01490   }
01491 
01492   template <typename Item>
01493   BALL_INLINE 
01494   HashGridBox3<Item>* HashGrid3<Item>::getBox(const Vector3& vector)
01495   {
01496     float x = (vector.x - origin_.x) / unit_.x;
01497     float y = (vector.y - origin_.y) / unit_.y;
01498     float z = (vector.z - origin_.z) / unit_.z;
01499 
01500     // workaround for MSVC 7, dont change this !!!
01501     Index x1 = (Index) Maths::floor(x);
01502     Index y1 = (Index) Maths::floor(y);
01503     Index z1 = (Index) Maths::floor(z);
01504 
01505     return getBox(x1, y1, z1);
01506   }
01507 
01508   template <typename Item>
01509   BALL_INLINE 
01510   const HashGridBox3<Item>* HashGrid3<Item>::getBox(const Vector3& vector) const
01511   {
01512     return ((HashGrid3 *)this)->getBox(vector);
01513   }
01514 
01515   template <typename Item>
01516   BALL_INLINE 
01517   bool HashGrid3<Item>::getIndices
01518     (const HashGridBox3<Item>& box,
01519      Position& x, Position& y, Position& z) const
01520   {
01521     Index index = getIndex_(box);
01522     
01523     if (index == INVALID_INDEX)
01524     {
01525       x = y = z = INVALID_POSITION;
01526       
01527       return false;
01528     }
01529     
01530     x = index / (dimension_y_ * dimension_z_);
01531     index  -= x * dimension_y_ * dimension_z_;
01532     y = index / dimension_z_;
01533     z = index - y * dimension_z_;
01534     
01535     return true;
01536   }
01537 
01538   template <typename Item>
01539   BALL_INLINE 
01540   void HashGrid3<Item>::insert
01541     (Position x, Position y, Position z, const Item& item)
01542   {
01543     HashGridBox3<Item>* box = getBox(x, y, z);
01544     
01545     if (box != 0)
01546     {
01547       box->insert(item);
01548     }
01549   }
01550 
01551   template <typename Item>
01552   BALL_INLINE 
01553   void HashGrid3<Item>::insert(const Vector3& vector, const Item& item)
01554   {
01555     HashGridBox3<Item> *box = getBox(vector);
01556     
01557     if (box != 0)
01558     {
01559       box->insert(item);
01560     }
01561   }
01562 
01563   template <typename Item>
01564   BALL_INLINE 
01565   bool HashGrid3<Item>::remove(Position x, Position y, Position z, const Item& item)
01566   {
01567     HashGridBox3<Item>* box = getBox(x, y, z);
01568     
01569     if (box != 0)
01570     {
01571       return box->remove(item);
01572     }
01573     
01574     return false;
01575   }
01576 
01577   template <typename Item>
01578   BALL_INLINE 
01579   bool HashGrid3<Item>::remove(const Vector3& vector, const Item& item)
01580   {
01581     HashGridBox3<Item>* box = getBox(vector);
01582     
01583     if (box != 0)
01584     {
01585       return box->remove(item);
01586     }
01587 
01588     return false;
01589   }
01590 
01591   template <typename Item>
01592   BALL_INLINE 
01593   void HashGrid3<Item>::host(Visitor< HashGrid3<Item> >& visitor)
01594   {
01595     visitor.visit(*this);
01596   }
01597 
01598   template <typename Item>
01599   BALL_INLINE 
01600   bool HashGrid3<Item>::operator == (const HashGrid3<Item>& grid) const
01601   {
01602     if (getSize() != grid.getSize()
01603         || origin_ != grid.origin_
01604         || unit_ != grid.unit_
01605         || dimension_x_ != grid.dimension_x_
01606         || dimension_y_ != grid.dimension_y_
01607         || dimension_z_ != grid.dimension_z_)
01608     {
01609       return false;
01610     }
01611 
01612     return box_ == grid.box_;
01613   }
01614 
01615   template <typename Item>
01616   BALL_INLINE 
01617   bool HashGrid3<Item>::operator !=	(const HashGrid3<Item>& grid) const
01618   {
01619     return !(*this == grid);
01620   }
01621 
01622   template <typename Item>
01623   BALL_INLINE 
01624   bool HashGrid3<Item>::isEmpty() const
01625   {
01626     return (getSize() == 0);
01627   }
01628 
01629   template <typename Item>
01630   bool HashGrid3<Item>::isValid() const
01631   {
01632     Size size = getSize();
01633     
01634     for (Position index = 0; index < (Position)size; ++index)
01635     {
01636       if (box_[index].isValid() == false)
01637       {
01638         return false;
01639       }
01640     }
01641 
01642     return true;
01643   }
01644 
01645   template <typename Item>
01646   void HashGrid3<Item>::dump(std::ostream& s, Size depth) const
01647   {
01648     BALL_DUMP_STREAM_PREFIX(s);
01649     
01650     BALL_DUMP_DEPTH(s, depth);
01651     
01652     BALL_DUMP_DEPTH(s, depth);
01653     s << "  origin: " << origin_ << std::endl;
01654     
01655     BALL_DUMP_DEPTH(s, depth);
01656     s << "  unit: " << unit_.z << std::endl;
01657     
01658     BALL_DUMP_DEPTH(s, depth);
01659     s << "  dimension: " << dimension_x_ << " " 
01660       << dimension_y_ << " " 
01661       << dimension_z_ << std::endl;
01662     
01663     Size size = getSize();
01664     BALL_DUMP_DEPTH(s, depth);
01665     s << "  size: " << size << std::endl;
01666 
01667     BALL_DUMP_DEPTH(s, depth);
01668     s << "  non empty boxes: " << countNonEmptyBoxes() << std::endl;
01669     
01670     BALL_DUMP_DEPTH(s, depth);
01671     s << "  boxes:" << std::endl;
01672     Position x, y, z;
01673     for (Position index = 0; index < (Position)size; ++index)
01674     {
01675       BALL_DUMP_DEPTH(s, depth);
01676       getIndices(box_[index], x, y, z);
01677       s << "    " << index << ". box: (" 
01678         << x << ',' << y << ',' << z << ')' << std::endl;
01679       box_[index].dump(s, 1);
01680     }
01681     
01682     BALL_DUMP_DEPTH(s, depth);
01683     s << "  non-empty boxes:" << std::endl;
01684 
01685     for (Position i=0; i<27; ++i)
01686     {
01687       if (!box_[i].isEmpty())
01688         s << "    " << getIndex_(box_[i]) << std::endl;
01689     }
01690     BALL_DUMP_STREAM_SUFFIX(s);
01691   }
01692 
01693   template <typename Item>
01694   bool HashGrid3<Item>::apply(UnaryProcessor<Item>& processor)
01695   {
01696     if (processor.start() == false)
01697     {
01698       return false;
01699     }
01700     Processor::Result result;
01701 
01702     for (Position i=0; i<27; ++i)
01703     {
01704       HashGridBox3<Item>* box = &box_[i];
01705       for (typename HashGridBox3<Item>::DataIterator *item = box->beginData(); +item; ++item)
01706       {
01707         result = processor(*item);
01708 
01709         if (result <= Processor::BREAK)
01710         {
01711           return (result == Processor::BREAK) ? true : false;
01712         }
01713       }
01714     }
01715 
01716     return processor->finish();
01717   }
01718 
01719   template <typename Item>
01720   bool HashGrid3<Item>::apply(UnaryProcessor< HashGridBox3<Item> >& processor)
01721   {
01722     if (processor.start() == false)
01723     {
01724       return false;
01725     }
01726 
01727     Processor::Result result;
01728 
01729     for (Position i=0; i<27; ++i)
01730     {
01731       HashGridBox3<Item>* box = &box_[i];
01732       result = processor(*box);
01733 
01734       if (result <= Processor::BREAK)
01735       {
01736         return (result == Processor::BREAK) ? true : false;
01737       }
01738     }
01739 
01740     return processor->finish();
01741   }
01742 
01743   template <typename Item>
01744   BALL_INLINE 
01745   Index HashGrid3<Item>::getIndex_(const HashGridBox3<Item>& box) const
01746   {
01747     if ((&box < &box_[0]) || (&box - &box_[0]  >= getSize()))
01748     {
01749       return INVALID_INDEX;
01750     } 
01751     else 
01752     {
01753       return (Index)(&box - &box_[0]);
01754     }
01755   }
01756 } // namespace BALL
01757 
01758 #endif // BALL_DATATYPE_HASHGRID_H
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Defines