5 #ifndef BALL_DATATYPE_HASHGRID_H 6 #define BALL_DATATYPE_HASHGRID_H 12 #ifndef BALL_CONCEPT_FORWARDITERATOR_H 16 #ifndef BALL_CONCEPT_VISITOR_H 20 #ifndef BALL_CONCEPT_PROCESSOR_H 24 #ifndef BALL_MATHS_VECTOR3_H 29 #include <forward_list> 53 template <
typename Item>
95 Item* find(
const Item &item);
98 const Item* find(
const Item& item)
const;
103 Size getSize()
const;
108 void insert(
const Item& item);
115 bool remove(
const Item& item);
122 bool removeAll(
const Item& item);
146 bool has(
const Item& item)
const;
151 bool isEmpty()
const;
159 bool isValid()
const;
161 void dump(std::ostream& s = std::cout,
Size depth = 0)
const;
206 bound_->getIndices(x_, y_, z_);
210 : bound_(traits.bound_),
211 cur_box_(traits.cur_box_),
212 position_(traits.position_),
246 return (position_ == traits.position_);
251 return (position_ != traits.position_);
256 return (bound_ && position_ < 27);
273 return (position_ == 0);
284 return (position_ == 27);
301 while ( position_ < 27
314 BoxIteratorPosition position_;
318 friend class BoxIteratorTraits;
332 return BoxIterator::begin(*
this);
338 return BoxIterator::end(*
this);
344 <HashGridBox3<Item>, HashGridBox3<Item>,
345 BoxIteratorPosition, BoxIteratorTraits>
351 return ConstBoxIterator::begin(*
this);
357 return ConstBoxIterator::end(*
this);
380 position_(bound_->data.begin())
385 : bound_(traits.bound_),
386 position_(traits.position_)
392 bound_ = traits.bound_;
393 position_ = traits.position_;
424 return (position_ == traits.position_);
429 return (position_ != traits.position_);
434 return (bound_ && position_ != bound_->data.end());
440 position_ = bound_->data.end();
445 position_ = bound_->data.begin();
450 return (position_ == bound_->data.begin());
455 position_ = bound_->data.end();
460 return (position_ == bound_->data.end());
480 HashGridBox3<Item>* bound_;
481 DataIteratorPosition position_;
484 friend class DataIteratorTraits;
497 return DataIterator::begin(*
this);
503 return DataIterator::end(*
this);
518 return ConstDataIterator::begin(*
this);
524 return ConstDataIterator::end(*
this);
534 template<
typename Item>
540 template<
typename Item>
546 template<
typename Item>
553 template<
typename Item>
559 template<
typename Item>
566 template<
typename Item>
571 if (found != data.end())
579 template<
typename Item>
586 template<
typename Item>
589 return std::distance(data.begin(), data.end());
592 template<
typename Item>
596 data.push_front(item);
599 template<
typename Item>
603 [&](
const Item&,
const Item& next){
return next == item; });
605 if (pos != data.end())
607 data.erase_after(pos);
614 template<
typename Item>
622 template <
typename Item>
626 visitor.visit(*
this);
629 template<
typename Item>
632 return (data == box.
data);
635 template<
typename Item>
639 return !(*
this == box);
642 template<
typename Item>
646 return (std::find(data.begin(), data.end(), item) != data.end());
649 template<
typename Item>
656 template<
typename Item>
663 template<
typename Item>
671 s <<
" size: " << getSize() << std::endl;
674 s <<
" data:" << std::endl;
675 for(
const Item& e: data)
678 s <<
" " << e << std::endl;
684 template <
typename Item>
687 if (!processor.
start())
696 result = processor(e);
698 if (result <= Processor::BREAK)
700 return result == Processor::BREAK;
704 return processor.
finish();
707 template <
typename Item>
710 if (!processor.start())
719 result = processor(*it);
721 if (result <= Processor::BREAK)
723 return result == Processor::BREAK;
727 return processor.finish();
753 template <
typename Item>
785 Size dimension_z,
float spacing_x,
float spacing_y,
float spacing_z);
794 Size dimension_z,
float spacing);
814 virtual void clear();
820 void clear(
const Vector3 &vector);
829 void destroy(
const Vector3& vector);
841 void set(
const Vector3& origin,
float unit,
Size size);
844 void set(
const HashGrid3& grid,
bool deep =
true);
853 void get(
HashGrid3& grid,
bool deep =
true)
const;
861 Size countNonEmptyBoxes()
const;
864 Size getSize()
const;
870 const Vector3& getOrigin()
const;
876 const Vector3& getUnit()
const;
879 Size getSizeX()
const;
882 Size getSizeY()
const;
885 Size getSizeZ()
const;
907 void insert(
const Vector3& vector,
const Item& item);
913 bool remove(
const Vector3& vector,
const Item& item);
935 bool isEmpty()
const;
943 virtual bool isValid()
const;
946 virtual void dump(std::ostream& s = std::cout,
Size depth = 0)
const;
963 const Item* getClosestItem(
const Vector3& point,
Size distance)
const;
1001 : bound_(traits.bound_),
1002 position_(traits.position_)
1008 bound_ = traits.bound_;
1009 position_ = traits.position_;
1040 return (position_ == traits.position_);
1045 return (position_ != traits.position_);
1050 return (bound_ && position_ < bound_->getSize());
1056 position_ = bound_->getSize()+1;
1066 return (position_ == 0);
1071 position_ = bound_->getSize();
1076 return (position_ == bound_->getSize());
1081 return bound_->box_[position_];
1086 return bound_->box_[position_];
1097 BoxIteratorPosition position_;
1100 friend class BoxIteratorTraits;
1111 return BoxIterator::begin(*
this);
1117 return BoxIterator::end(*
this);
1130 return ConstBoxIterator::begin(*
this);
1136 return ConstBoxIterator::end(*
this);
1157 vector<HashGridBox3<Item> > box_;
1164 template <
typename Item>
1174 template <
typename Item>
1178 float spacing_x,
float spacing_y,
float spacing_z)
1179 : origin_(originvector),
1180 unit_(spacing_x, spacing_y, spacing_z),
1181 dimension_x_(dimension_x),
1182 dimension_y_(dimension_y),
1183 dimension_z_(dimension_z),
1188 template <
typename Item>
1191 Size dimension_x,
Size dimension_y,
Size dimension_z,
float spacing)
1193 unit_(spacing, spacing, spacing),
1194 dimension_x_(dimension_x),
1195 dimension_y_(dimension_y),
1196 dimension_z_(dimension_z),
1202 template <
typename Item>
1206 unit_(spacing, spacing, spacing),
1207 dimension_x_((
Size)(size.x / spacing + 1.0)),
1208 dimension_y_((
Size)(size.y / spacing + 1.0)),
1209 dimension_z_((
Size)(size.z / spacing + 1.0)),
1210 box_(dimension_x_ * dimension_y_ * dimension_z_,
HashGridBox3<Item>(this))
1214 template <
typename Item>
1220 template <
typename Item>
1225 template <
typename Item>
1234 template <
typename Item>
1246 template <
typename Item>
1258 template <
typename Item>
1265 template <
typename Item>
1272 template <
typename Item>
1279 template <
typename Item>
1284 origin_.
set(origin);
1286 dimension_x_ = dimension_x;
1287 dimension_y_ = dimension_y;
1288 dimension_z_ = dimension_z;
1292 template <
typename Item>
1295 origin_.
set(origin);
1296 unit_.
set(unit, unit, unit);
1297 dimension_x_ = size;
1298 dimension_y_ = size;
1299 dimension_z_ = size;
1303 template <
typename Item>
1306 origin_.
set(grid.origin_);
1307 unit_.
set(grid.unit_);
1308 dimension_x_ = grid.dimension_x_;
1309 dimension_y_ = grid.dimension_y_;
1310 dimension_z_ = grid.dimension_z_;
1319 template <
typename Item>
1328 template <
typename Item>
1332 origin.
set(origin_);
1334 dimension_x = dimension_x_;
1335 dimension_y = dimension_y_;
1336 dimension_z = dimension_z_;
1339 template <
typename Item>
1343 grid.
set(*
this, deep);
1346 template <
typename Item>
1350 return std::count_if(box_.begin(), box_.end(),
1355 template <
typename Item>
1359 return (dimension_x_ * dimension_y_ * dimension_z_);
1362 template <
typename Item>
1369 template <
typename Item>
1376 template <
typename Item>
1383 template <
typename Item>
1390 template <
typename Item>
1394 return dimension_x_;
1397 template <
typename Item>
1401 return dimension_y_;
1404 template <
typename Item>
1408 return dimension_z_;
1411 template <
typename Item>
1418 getIndices(*box, x, y, z);
1420 const Item* item = 0;
1426 const Index xn = x + xi;
1429 const Index yn = y + yi;
1434 if (box_ptr != 0 && !box_ptr->
isEmpty())
1437 for (;hit != box_ptr->
endData(); hit++)
1439 const float new_dist = ((*hit)->getPosition() - point).getSquareLength();
1440 if (new_dist < distance)
1443 distance = new_dist;
1454 template <
typename Item>
1461 return pow((
double)((size.
x * size.
y * size.
z) / nr_boxes), (
double)(1.0 / 3.0));
1464 template <
typename Item>
1476 return &(box_[x * dimension_y_ * dimension_z_ + y * dimension_z_ + z]);
1480 template <
typename Item>
1487 template <
typename Item>
1491 float x = (vector.
x - origin_.
x) / unit_.
x;
1492 float y = (vector.
y - origin_.
y) / unit_.
y;
1493 float z = (vector.
z - origin_.
z) / unit_.
z;
1500 return getBox(x1, y1, z1);
1503 template <
typename Item>
1510 template <
typename Item>
1516 Index index = getIndex_(box);
1525 x = index / (dimension_y_ * dimension_z_);
1526 index -= x * dimension_y_ * dimension_z_;
1527 y = index / dimension_z_;
1528 z = index - y * dimension_z_;
1533 template <
typename Item>
1546 template <
typename Item>
1558 template <
typename Item>
1564 return box ? box->
remove(item) :
false;
1567 template <
typename Item>
1573 return box ? box->
remove(item) :
false;
1576 template <
typename Item>
1580 visitor.visit(*
this);
1583 template <
typename Item>
1587 if (getSize() != grid.
getSize()
1588 || origin_ != grid.origin_
1589 || unit_ != grid.unit_
1590 || dimension_x_ != grid.dimension_x_
1591 || dimension_y_ != grid.dimension_y_
1592 || dimension_z_ != grid.dimension_z_)
1597 return box_ == grid.box_;
1600 template <
typename Item>
1604 return !(*
this == grid);
1607 template <
typename Item>
1611 return (getSize() == 0);
1614 template <
typename Item>
1619 if(!e.isValid())
return false;
1624 template <
typename Item>
1632 s <<
" origin: " << origin_ << std::endl;
1635 s <<
" unit: " << unit_.
z << std::endl;
1638 s <<
" dimension: " << dimension_x_ <<
" " 1639 << dimension_y_ <<
" " 1640 << dimension_z_ << std::endl;
1642 Size size = getSize();
1644 s <<
" size: " << size << std::endl;
1647 s <<
" non empty boxes: " << countNonEmptyBoxes() << std::endl;
1650 s <<
" boxes:" << std::endl;
1655 getIndices(box_[index], x, y, z);
1656 s <<
" " << index <<
". box: (" 1657 << x <<
',' << y <<
',' << z <<
')' << std::endl;
1658 box_[index].dump(s, 1);
1662 s <<
" non-empty boxes:" << std::endl;
1666 if (!box_[i].isEmpty())
1667 s <<
" " << getIndex_(box_[i]) << std::endl;
1672 template <
typename Item>
1675 if (!processor.
start())
1686 result = processor(*item);
1688 if (result <= Processor::BREAK)
1690 return result == Processor::BREAK;
1695 return processor->
finish();
1698 template <
typename Item>
1701 if (!processor.start())
1711 result = processor(*box);
1713 if (result <= Processor::BREAK)
1715 return result == Processor::BREAK;
1719 return processor->finish();
1722 template <
typename Item>
1726 if ((&box < &box_[0]) || (&box - &box_[0] >= getSize()))
1732 return (
Index)(&box - &box_[0]);
1737 #endif // BALL_DATATYPE_HASHGRID_H BALL_EXPORT bool operator!=(const String &s1, const String &s2)
const HashGrid3 * getContainer() const
BoxIteratorPosition & getPosition()
const DataIteratorPosition & getPosition() const
BALL_ULONG64_TYPE LongSize
BoxIteratorTraits(const BoxIteratorTraits &traits, bool=true)
T max(const T &a, const T &b)
const HashGridBox3 * getContainer() const
std::forward_list< Item > DataContainer
BALL_LONG64_TYPE LongIndex
Three-dimensional Hash Grid Class.
const Item & getData() const
DataIteratorTraits(const HashGridBox3 &box)
BoxIteratorPosition & getPosition()
HashGrid3 * getContainer()
BoxIteratorTraits(const HashGridBox3 &box)
HashGridBox3 * getContainer()
ConstBoxIterator endBox() const
get the last box
#define BALL_DUMP_STREAM_SUFFIX(os)
HashGridBox3< Item > & getData()
bool getIndices(const HashGridBox3< Item > &box, Position &x, Position &y, Position &z) const
Get the position indices of a HashGridBox3.
ConstForwardIterator< HashGrid3< Item >, HashGridBox3< Item >, BoxIteratorPosition, BoxIteratorTraits > ConstBoxIterator
BoxIterator beginBox()
get the first box
const HashGridBox3< Item > & getData() const
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)
ForwardIterator< HashGridBox3< Item >, Item, DataIteratorPosition, DataIteratorTraits > DataIterator
Position BoxIteratorPosition
ForwardIterator< HashGrid3< Item >, HashGridBox3< Item >, BoxIteratorPosition, BoxIteratorTraits > BoxIterator
void clear()
Clears the grid box.
ConstBoxIterator endBox() const
virtual void clear()
Clears the whole grid.
HashGrid3< Item > * parent
Size getSize() const
Returns the size of a grid, i. e. ?????
const HashGridBox3 * getContainer() const
HashGridBox3< Item > & getData()
ConstDataIterator beginData() const
static const Index INVALID_Index
DataIteratorPosition & getPosition()
HashGridBox3 * getContainer()
BoxIterator endBox()
get the last box
#define BALL_DUMP_DEPTH(os, depth)
#define BALL_DUMP_STREAM_PREFIX(os)
HashGridBox3< Item > * getBox(Position x, Position y, Position z)
Return the HashGridBox3 at position (x, y, z)
HashGridBox3(HashGrid3< Item > *parent)
Default constructor.
const signed char BALL_EXPORT neighbour_table_[27][3]
ConstForwardIterator< HashGridBox3< Item >, HashGridBox3< Item >, BoxIteratorPosition, BoxIteratorTraits > ConstBoxIterator
This is the const version of BoxIterator .
BoxIteratorTraits(const HashGrid3 &grid)
const BoxIteratorPosition & getPosition() const
DataIteratorTraits(const DataIteratorTraits &traits, bool=true)
ConstBoxIterator beginBox() const
bool remove(const Item &item)
Position BoxIteratorPosition
const BoxIteratorPosition & getPosition() const
BoxIteratorTraits(const BoxIteratorTraits &traits, bool=true)
const HashGridBox3< Item > & getData() const
BALL_EXPORT bool operator==(const String &s1, const String &s2)
static const Position INVALID_Position
ConstBoxIterator beginBox() const
get the first box
void insert(const Item &item)
ConstForwardIterator< HashGridBox3< Item >, Item, DataIteratorPosition, DataIteratorTraits > ConstDataIterator
#define BALL_CREATE_DEEP(name)
DataContainer::iterator DataIteratorPosition
#define BALL_CREATE(name)
ConstDataIterator endData() const
ForwardIterator< HashGridBox3< Item >, HashGridBox3< Item >, BoxIteratorPosition, BoxIteratorTraits > BoxIterator