BALL 1.5.0
hashGrid.h
Go to the documentation of this file.
1// -*- Mode: C++; tab-width: 2; -*-
2// vi: set ts=2:
3//
4
5#ifndef BALL_DATATYPE_HASHGRID_H
6#define BALL_DATATYPE_HASHGRID_H
7
8#ifndef BALL_COMMON_H
9# include <BALL/common.h>
10#endif
11
12#ifndef BALL_CONCEPT_FORWARDITERATOR_H
14#endif
15
16#ifndef BALL_CONCEPT_VISITOR_H
17# include <BALL/CONCEPT/visitor.h>
18#endif
19
20#ifndef BALL_CONCEPT_PROCESSOR_H
22#endif
23
24#ifndef BALL_MATHS_VECTOR3_H
25# include <BALL/MATHS/vector3.h>
26#endif
27
28#include <algorithm>
29#include <forward_list>
30
31namespace BALL
32{
33 namespace __private
34 {
35 extern const signed char BALL_EXPORT neighbour_table_[27][3];
36 }
37
38 template <typename Item> class HashGrid3;
39
44
53 template <typename Item>
55 {
56 public:
57
61
64
66 void clear();
67
71 void destroy();
72
74
77
79
82
84
89
95 Item* find(const Item &item);
96
98 const Item* find(const Item& item) const;
99
103 Size getSize() const;
104
108 void insert(const Item& item);
109
115 bool remove(const Item& item);
116
122 bool removeAll(const Item& item);
123
125
128
132
135
137 bool operator == (const HashGridBox3& box) const;
138
140 bool operator != (const HashGridBox3& box) const;
141
146 bool has(const Item& item) const;
147
151 bool isEmpty() const;
152
154
157
159 bool isValid() const;
161 void dump(std::ostream& s = std::cout, Size depth = 0) const;
162
164
167
169 bool apply(UnaryProcessor<Item>& processor);
170
173
175
179
181 {
182 public:
183
185
186 virtual ~BoxIteratorTraits() {}
187
189 : bound_(nullptr),
190 cur_box_(nullptr),
191 position_(0),
192 x_(0),
193 y_(0),
194 z_(0)
195 {
196 }
197
199 : bound_((HashGridBox3 *)&box),
200 cur_box_(bound_),
201 position_(0),
202 x_(0),
203 y_(0),
204 z_(0)
205 {
206 bound_->getIndices(x_, y_, z_);
207 }
208
209 BoxIteratorTraits(const BoxIteratorTraits& traits, bool /* deep */ = true)
210 : bound_(traits.bound_),
211 cur_box_(traits.cur_box_),
212 position_(traits.position_),
213 x_(traits.x_),
214 y_(traits.y_),
215 z_(traits.z_)
216 {
217 }
218
220 {
221 return bound_;
222 }
223
225 {
226 return bound_;
227 }
228
229 bool isSingular() const
230 {
231 return !bound_;
232 }
233
235 {
236 return position_;
237 }
238
240 {
241 return position_;
242 }
243
244 bool operator == (const BoxIteratorTraits& traits) const
245 {
246 return (position_ == traits.position_);
247 }
248
249 bool operator != (const BoxIteratorTraits& traits) const
250 {
251 return (position_ != traits.position_);
252 }
253
254 bool isValid() const
255 {
256 return (bound_ && position_ < 27);
257 }
258
260 {
261 bound_ = nullptr;
262 position_ = 100;
263 }
264
265 void toBegin()
266 {
267 position_ = 0;
268 cur_box_ = bound_;
269 }
270
271 bool isBegin() const
272 {
273 return (position_ == 0);
274 }
275
276 void toEnd()
277 {
278 position_ = 27;
279 cur_box_ = 0;
280 }
281
282 bool isEnd() const
283 {
284 return (position_ == 27);
285 }
286
288 {
289 return *cur_box_;
290 }
291
293 {
294 return *cur_box_;
295 }
296
297 void forward()
298 {
299 ++position_;
300 // iterate to the next existing box
301 while ( position_ < 27
302 && !(cur_box_ = bound_->parent->getBox(x_ + __private::neighbour_table_[position_][0],
303 y_ + __private::neighbour_table_[position_][1],
304 z_ + __private::neighbour_table_[position_][2])))
305 {
306 ++position_;
307 }
308 }
309
310 private:
311
312 HashGridBox3<Item> *bound_;
313 HashGridBox3<Item> *cur_box_;
314 BoxIteratorPosition position_;
315 Position x_, y_, z_;
316 };
317
318 friend class BoxIteratorTraits;
319
324 typedef ForwardIterator
328
331 {
332 return BoxIterator::begin(*this);
333 }
334
337 {
338 return BoxIterator::end(*this);
339 }
340
341
347
350 {
351 return ConstBoxIterator::begin(*this);
352 }
353
356 {
357 return ConstBoxIterator::end(*this);
358 }
359
360 typedef typename std::forward_list<Item> DataContainer;
361
362 typedef typename DataContainer::iterator DataIteratorPosition;
363
365 {
366 public:
367
369
370 virtual ~DataIteratorTraits() {}
371
373 : bound_(nullptr),
374 position_()
375 {
376 }
377
379 : bound_((HashGridBox3 *)&box),
380 position_(bound_->data.begin())
381 {
382 }
383
384 DataIteratorTraits(const DataIteratorTraits& traits, bool /* deep */ = true)
385 : bound_(traits.bound_),
386 position_(traits.position_)
387 {
388 }
389
391 {
392 bound_ = traits.bound_;
393 position_ = traits.position_;
394 return *this;
395 }
396
398 {
399 return bound_;
400 }
401
403 {
404 return bound_;
405 }
406
407 bool isSingular() const
408 {
409 return !bound_;
410 }
411
413 {
414 return position_;
415 }
416
418 {
419 return position_;
420 }
421
422 bool operator == (const DataIteratorTraits &traits) const
423 {
424 return (position_ == traits.position_);
425 }
426
427 bool operator != (const DataIteratorTraits &traits) const
428 {
429 return (position_ != traits.position_);
430 }
431
432 bool isValid() const
433 {
434 return (bound_ && position_ != bound_->data.end());
435 }
436
438 {
439 bound_ = nullptr;
440 position_ = bound_->data.end();
441 }
442
443 void toBegin()
444 {
445 position_ = bound_->data.begin();
446 }
447
448 bool isBegin() const
449 {
450 return (position_ == bound_->data.begin());
451 }
452
453 void toEnd()
454 {
455 position_ = bound_->data.end();
456 }
457
458 bool isEnd() const
459 {
460 return (position_ == bound_->data.end());
461 }
462
463 Item& getData()
464 {
465 return *position_;
466 }
467
468 const Item& getData() const
469 {
470 return *position_;
471 }
472
473 void forward()
474 {
475 ++position_;
476 }
477
478 private:
479
480 HashGridBox3<Item>* bound_;
481 DataIteratorPosition position_;
482 };
483
484 friend class DataIteratorTraits;
485
489 typedef ForwardIterator
490 <HashGridBox3<Item>, Item,
493
496 {
497 return DataIterator::begin(*this);
498 }
499
502 {
503 return DataIterator::end(*this);
504 }
505
506
511 <HashGridBox3<Item>, Item,
514
517 {
518 return ConstDataIterator::begin(*this);
519 }
520
523 {
524 return ConstDataIterator::end(*this);
525 }
526
528
530
532 };
533
534 template<typename Item>
536 : parent(p)
537 {
538 }
539
540 template<typename Item>
542 {
543 data.clear();
544 }
545
546 template<typename Item>
549 {
550 clear();
551 }
552
553 template<typename Item>
555 {
556 parent = p;
557 }
558
559 template<typename Item>
562 {
563 parent->getIndices(*this, x, y, z);
564 }
565
566 template<typename Item>
567 Item* HashGridBox3<Item>::find(const Item& item)
568 {
569 DataIteratorPosition found = std::find(data.begin(), data.end(), item);
570
571 if (found != data.end())
572 {
573 return &(*found);
574 }
575
576 return nullptr;
577 }
578
579 template<typename Item>
581 const Item* HashGridBox3<Item>::find(const Item& item) const
582 {
583 return const_cast<HashGridBox3*>(this)->find(item);
584 }
585
586 template<typename Item>
588 {
589 return std::distance(data.begin(), data.end());
590 }
591
592 template<typename Item>
594 void HashGridBox3<Item>::insert(const Item& item)
595 {
596 data.push_front(item);
597 }
598
599 template<typename Item>
600 bool HashGridBox3<Item>::remove(const Item& item)
601 {
602 DataIteratorPosition pos = std::adjacent_find(data.before_begin(), data.end(),
603 [&](const Item&, const Item& next){ return next == item; });
604
605 if (pos != data.end())
606 {
607 data.erase_after(pos);
608 return true;
609 }
610
611 return false;
612 }
613
614 template<typename Item>
615 bool HashGridBox3<Item>::removeAll(const Item& item)
616 {
617 data.remove(item);
618
619 return true;
620 }
621
622 template <typename Item>
625 {
626 visitor.visit(*this);
627 }
628
629 template<typename Item>
631 {
632 return (data == box.data);
633 }
634
635 template<typename Item>
638 {
639 return !(*this == box);
640 }
641
642 template<typename Item>
644 bool HashGridBox3<Item>::has(const Item& item) const
645 {
646 return (std::find(data.begin(), data.end(), item) != data.end());
647 }
648
649 template<typename Item>
652 {
653 return data.empty();
654 }
655
656 template<typename Item>
658 {
659 // this is no longer required...
660 return true;
661 }
662
663 template<typename Item>
664 void HashGridBox3<Item>::dump(std::ostream& s, Size depth) const
665 {
667
668 BALL_DUMP_DEPTH(s, depth);
669
670 BALL_DUMP_DEPTH(s, depth);
671 s << " size: " << getSize() << std::endl;
672
673 BALL_DUMP_DEPTH(s, depth);
674 s << " data:" << std::endl;
675 for(const Item& e: data)
676 {
677 BALL_DUMP_DEPTH(s, depth);
678 s << " " << e << std::endl;
679 }
680
682 }
683
684 template <typename Item>
686 {
687 if (!processor.start())
688 {
689 return false;
690 }
691
692 Processor::Result result;
693
694 for(Item& e: data)
695 {
696 result = processor(e);
697
698 if (result <= Processor::BREAK)
699 {
700 return result == Processor::BREAK;
701 }
702 }
703
704 return processor.finish();
705 }
706
707 template <typename Item>
709 {
710 if (!processor.start())
711 {
712 return false;
713 }
714
715 Processor::Result result;
716
717 for (BoxIterator it = beginBox(); +it; ++it)
718 {
719 result = processor(*it);
720
721 if (result <= Processor::BREAK)
722 {
723 return result == Processor::BREAK;
724 }
725 }
726
727 return processor.finish();
728 }
729
753 template <typename Item>
755 {
756 public:
757
759
760
763
764
766
784 HashGrid3(const Vector3& origin, Size dimension_x, Size dimension_y,
785 Size dimension_z, float spacing_x, float spacing_y, float spacing_z);
786
793 HashGrid3(const Vector3& origin, Size dimension_x, Size dimension_y,
794 Size dimension_z, float spacing);
795
805 HashGrid3(const Vector3& origin, const Vector3& size, float spacing);
806
808 HashGrid3(const HashGrid3& grid, bool deep = true);
809
811 virtual ~HashGrid3();
812
814 virtual void clear();
815
818
820 void clear(const Vector3 &vector);
821
823 void destroy();
824
827
829 void destroy(const Vector3& vector);
830
832
835
837 void set(const Vector3& origin, const Vector3& unit,
838 Size dimension_x, Size dimension_y, Size dimension_z);
839
841 void set(const Vector3& origin, float unit, Size size);
842
844 void set(const HashGrid3& grid, bool deep = true);
845
847 const HashGrid3& operator = (const HashGrid3& grid);
848
850 void get(Vector3& origin, Vector3& unit, Size& dimension_x, Size& dimension_y, Size& dimension_z) const;
851
853 void get(HashGrid3& grid, bool deep = true) const;
854
856
859
862
864 Size getSize() const;
865
868
870 const Vector3& getOrigin() const;
871
874
876 const Vector3& getUnit() const;
877
879 Size getSizeX() const;
880
882 Size getSizeY() const;
883
885 Size getSizeZ() const;
886
889
891 const HashGridBox3<Item>* getBox(Position x, Position y, Position z) const;
892
894 HashGridBox3<Item>* getBox(const Vector3& vector);
895
897 const HashGridBox3<Item>* getBox(const Vector3 &vector) const;
898
900 bool getIndices(const HashGridBox3<Item>& box,
901 Position& x, Position& y, Position& z) const;
902
904 void insert(Position x, Position y, Position z, const Item& item);
905
907 void insert(const Vector3& vector, const Item& item);
908
910 bool remove(Position x, Position y, Position z, const Item& item);
911
913 bool remove(const Vector3& vector, const Item& item);
914
916
919
921 void host(Visitor<HashGrid3>& visitor);
922
924
927
929 bool operator == (const HashGrid3& grid) const;
930
932 bool operator != (const HashGrid3& grid) const;
933
935 bool isEmpty() const;
936
938
941
943 virtual bool isValid() const;
944
946 virtual void dump(std::ostream& s = std::cout, Size depth = 0) const;
947
949
953
955 bool apply(UnaryProcessor<Item> &processor);
956
958 bool apply(UnaryProcessor< HashGridBox3<Item> > &processor);
959
963 const Item* getClosestItem(const Vector3& point, Size distance) const;
964
971 static float calculateMinSpacing(LongIndex memory, const Vector3& size);
972
974
977
979
981 {
982 public:
983
985
986 virtual ~BoxIteratorTraits() {}
987
989 : bound_(nullptr),
990 position_(0)
991 {
992 }
993
995 : bound_((HashGrid3 *)&grid),
996 position_(0)
997 {
998 }
999
1000 BoxIteratorTraits(const BoxIteratorTraits& traits, bool /* deep */ = true)
1001 : bound_(traits.bound_),
1002 position_(traits.position_)
1003 {
1004 }
1005
1007 {
1008 bound_ = traits.bound_;
1009 position_ = traits.position_;
1010 return *this;
1011 }
1012
1014 {
1015 return bound_;
1016 }
1017
1019 {
1020 return bound_;
1021 }
1022
1023 bool isSingular() const
1024 {
1025 return !bound_;
1026 }
1027
1029 {
1030 return position_;
1031 }
1032
1034 {
1035 return position_;
1036 }
1037
1038 bool operator == (const BoxIteratorTraits& traits) const
1039 {
1040 return (position_ == traits.position_);
1041 }
1042
1043 bool operator != (const BoxIteratorTraits& traits) const
1044 {
1045 return (position_ != traits.position_);
1046 }
1047
1048 bool isValid() const
1049 {
1050 return (bound_ && position_ < bound_->getSize());
1051 }
1052
1054 {
1055 bound_ = nullptr;
1056 position_ = bound_->getSize()+1;
1057 }
1058
1059 void toBegin()
1060 {
1061 position_ = 0;
1062 }
1063
1064 bool isBegin() const
1065 {
1066 return (position_ == 0);
1067 }
1068
1069 void toEnd()
1070 {
1071 position_ = bound_->getSize();
1072 }
1073
1074 bool isEnd() const
1075 {
1076 return (position_ == bound_->getSize());
1077 }
1078
1080 {
1081 return bound_->box_[position_];
1082 }
1083
1085 {
1086 return bound_->box_[position_];
1087 }
1088
1089 void forward()
1090 {
1091 ++position_;
1092 }
1093
1094 private:
1095
1096 HashGrid3<Item>* bound_;
1097 BoxIteratorPosition position_;
1098 };
1099
1100 friend class BoxIteratorTraits;
1101
1103 typedef ForwardIterator
1107
1110 {
1111 return BoxIterator::begin(*this);
1112 }
1113
1116 {
1117 return BoxIterator::end(*this);
1118 }
1119
1120
1122 typedef ConstForwardIterator
1126
1129 {
1130 return ConstBoxIterator::begin(*this);
1131 }
1132
1135 {
1136 return ConstBoxIterator::end(*this);
1137 }
1138
1140
1141 private:
1142
1143 //_
1144 Index getIndex_(const HashGridBox3<Item>& box) const;
1145
1146 //_
1147 Vector3 origin_;
1148 //_
1149 Vector3 unit_;
1150 //_
1151 Size dimension_x_;
1152 //_
1153 Size dimension_y_;
1154 //_
1155 Size dimension_z_;
1156 //_
1157 vector<HashGridBox3<Item> > box_;
1158 };
1159
1160
1162
1163
1164 template <typename Item>
1166 : origin_(0,0,0),
1167 unit_(0,0,0),
1168 dimension_x_(0),
1169 dimension_y_(0),
1170 dimension_z_(0)
1171 {
1172 }
1173
1174 template <typename Item>
1176 (const Vector3 &originvector,
1177 Size dimension_x, Size dimension_y, Size dimension_z,
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),
1184 box_(dimension_x * dimension_y * dimension_z, HashGridBox3<Item>(this))
1185 {
1186 }
1187
1188 template <typename Item>
1190 (const Vector3& origin,
1191 Size dimension_x, Size dimension_y, Size dimension_z, float spacing)
1192 : origin_(origin),
1193 unit_(spacing, spacing, spacing),
1194 dimension_x_(dimension_x),
1195 dimension_y_(dimension_y),
1196 dimension_z_(dimension_z),
1197 box_(dimension_x * dimension_y * dimension_z, HashGridBox3<Item>(this))
1198 {
1199 }
1200
1201 // this constructor creates a linear array of HashGridBox3 objects.
1202 template <typename Item>
1203 HashGrid3<Item>::HashGrid3(const Vector3& origin, const Vector3& size,
1204 float spacing)
1205 : origin_(origin),
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))
1211 {
1212 }
1213
1214 template <typename Item>
1216 {
1217 set(grid, deep);
1218 }
1219
1220 template <typename Item>
1222 {
1223 }
1224
1225 template <typename Item>
1227 {
1228 for(HashGridBox3<Item>& e: box_)
1229 {
1230 e.clear();
1231 }
1232 }
1233
1234 template <typename Item>
1237 {
1238 HashGridBox3<Item>* box = getBox(x, y, z);
1239
1240 if (box)
1241 {
1242 box->clear();
1243 }
1244 }
1245
1246 template <typename Item>
1249 {
1250 HashGridBox3<Item>* box = getBox(vector);
1251
1252 if (box)
1253 {
1254 box->clear();
1255 }
1256 }
1257
1258 template <typename Item>
1261 {
1262 clear();
1263 }
1264
1265 template <typename Item>
1268 {
1269 clear(x, y, z);
1270 }
1271
1272 template <typename Item>
1275 {
1276 clear(vector);
1277 }
1278
1279 template <typename Item>
1281 (const Vector3& origin, const Vector3& unit,
1282 Size dimension_x, Size dimension_y, Size dimension_z)
1283 {
1284 origin_.set(origin);
1285 unit_.set(unit);
1286 dimension_x_ = dimension_x;
1287 dimension_y_ = dimension_y;
1288 dimension_z_ = dimension_z;
1289 box_.assign(getSize(), HashGridBox3<Item>(this));
1290 }
1291
1292 template <typename Item>
1293 void HashGrid3<Item>::set(const Vector3& origin, float unit, Size size)
1294 {
1295 origin_.set(origin);
1296 unit_.set(unit, unit, unit);
1297 dimension_x_ = size;
1298 dimension_y_ = size;
1299 dimension_z_ = size;
1300 box_.assign(getSize(), HashGridBox3<Item>(this));
1301 }
1302
1303 template <typename Item>
1304 void HashGrid3<Item>::set(const HashGrid3<Item>& grid, bool /* deep */)
1305 {
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_;
1311 box_ = grid.box_;
1312
1313 for(HashGridBox3<Item>& e: box_)
1314 {
1315 e.setParent(this);
1316 }
1317 }
1318
1319 template <typename Item>
1322 {
1323 set(grid);
1324
1325 return *this;
1326 }
1327
1328 template <typename Item>
1330 void HashGrid3<Item>::get(Vector3 &origin, Vector3 &unit, Size& dimension_x, Size& dimension_y, Size& dimension_z) const
1331 {
1332 origin.set(origin_);
1333 unit.set(unit_);
1334 dimension_x = dimension_x_;
1335 dimension_y = dimension_y_;
1336 dimension_z = dimension_z_;
1337 }
1338
1339 template <typename Item>
1340 BALL_INLINE void
1342 {
1343 grid.set(*this, deep);
1344 }
1345
1346 template <typename Item>
1347 Size
1349 {
1350 return std::count_if(box_.begin(), box_.end(),
1351 std::not1(std::mem_fun_ref(&HashGridBox3<Item>::isEmpty))
1352 );
1353 }
1354
1355 template <typename Item>
1358 {
1359 return (dimension_x_ * dimension_y_ * dimension_z_);
1360 }
1361
1362 template <typename Item>
1365 {
1366 return origin_;
1367 }
1368
1369 template <typename Item>
1372 {
1373 return origin_;
1374 }
1375
1376 template <typename Item>
1379 {
1380 return unit_;
1381 }
1382
1383 template <typename Item>
1386 {
1387 return unit_;
1388 }
1389
1390 template <typename Item>
1393 {
1394 return dimension_x_;
1395 }
1396
1397 template <typename Item>
1400 {
1401 return dimension_y_;
1402 }
1403
1404 template <typename Item>
1407 {
1408 return dimension_z_;
1409 }
1410
1411 template <typename Item>
1412 const Item* HashGrid3<Item>::getClosestItem(const Vector3& point, Size dist) const
1413 {
1414 const HashGridBox3<Item>* box = getBox(point);
1415 if (!box) return 0;
1416
1417 Position x, y, z;
1418 getIndices(*box, x, y, z);
1419
1420 const Item* item = 0;
1421 float distance = std::numeric_limits<float>::max();
1422
1423 // iterator over neighbour boxes
1424 for (Index xi = -(Index)dist; xi <= (Index)dist; xi++)
1425 {
1426 const Index xn = x + xi;
1427 for (Index yi = -(Index)dist; yi <= (Index)dist; yi++)
1428 {
1429 const Index yn = y + yi;
1430 for (Index zi = -(Index)dist; zi <= (Index)dist; zi++)
1431 {
1432 // iterate over all data items
1433 const HashGridBox3<Item>* const box_ptr = getBox(xn, yn, z+zi);
1434 if (box_ptr != 0 && !box_ptr->isEmpty())
1435 {
1436 typename HashGridBox3<Item>::ConstDataIterator hit = box_ptr->beginData();
1437 for (;hit != box_ptr->endData(); hit++)
1438 {
1439 const float new_dist = ((*hit)->getPosition() - point).getSquareLength();
1440 if (new_dist < distance)
1441 {
1442 item = &*hit;
1443 distance = new_dist;
1444 }
1445 }
1446 }
1447 }
1448 }
1449 }
1450
1451 return item;
1452 }
1453
1454 template <typename Item>
1457 {
1458 LongSize memory_for_box = sizeof(HashGridBox3<Item>) + sizeof(HashGridBox3<Item>*);
1459 LongSize nr_boxes =(LongSize)floor((float)(memory / memory_for_box));
1460
1461 return pow((double)((size.x * size.y * size.z) / nr_boxes), (double)(1.0 / 3.0));
1462 }
1463
1464 template <typename Item>
1467 {
1468 if (x >= (Position)dimension_x_ ||
1469 y >= (Position)dimension_y_ ||
1470 z >= (Position)dimension_z_)
1471 {
1472 return 0;
1473 }
1474 else
1475 {
1476 return &(box_[x * dimension_y_ * dimension_z_ + y * dimension_z_ + z]);
1477 }
1478 }
1479
1480 template <typename Item>
1483 {
1484 return ((HashGrid3*)this)->getBox(x, y, z);
1485 }
1486
1487 template <typename Item>
1490 {
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;
1494
1495 // workaround for MSVC 7, dont change this !!!
1496 Index x1 = (Index) Maths::floor(x);
1497 Index y1 = (Index) Maths::floor(y);
1498 Index z1 = (Index) Maths::floor(z);
1499
1500 return getBox(x1, y1, z1);
1501 }
1502
1503 template <typename Item>
1506 {
1507 return ((HashGrid3 *)this)->getBox(vector);
1508 }
1509
1510 template <typename Item>
1513 (const HashGridBox3<Item>& box,
1514 Position& x, Position& y, Position& z) const
1515 {
1516 Index index = getIndex_(box);
1517
1518 if (index == INVALID_Index)
1519 {
1520 x = y = z = INVALID_Position;
1521
1522 return false;
1523 }
1524
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_;
1529
1530 return true;
1531 }
1532
1533 template <typename Item>
1536 (Position x, Position y, Position z, const Item& item)
1537 {
1538 HashGridBox3<Item>* box = getBox(x, y, z);
1539
1540 if (box)
1541 {
1542 box->insert(item);
1543 }
1544 }
1545
1546 template <typename Item>
1548 void HashGrid3<Item>::insert(const Vector3& vector, const Item& item)
1549 {
1550 HashGridBox3<Item> *box = getBox(vector);
1551
1552 if (box)
1553 {
1554 box->insert(item);
1555 }
1556 }
1557
1558 template <typename Item>
1560 bool HashGrid3<Item>::remove(Position x, Position y, Position z, const Item& item)
1561 {
1562 HashGridBox3<Item>* box = getBox(x, y, z);
1563
1564 return box ? box->remove(item) : false;
1565 }
1566
1567 template <typename Item>
1569 bool HashGrid3<Item>::remove(const Vector3& vector, const Item& item)
1570 {
1571 HashGridBox3<Item>* box = getBox(vector);
1572
1573 return box ? box->remove(item) : false;
1574 }
1575
1576 template <typename Item>
1579 {
1580 visitor.visit(*this);
1581 }
1582
1583 template <typename Item>
1586 {
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_)
1593 {
1594 return false;
1595 }
1596
1597 return box_ == grid.box_;
1598 }
1599
1600 template <typename Item>
1603 {
1604 return !(*this == grid);
1605 }
1606
1607 template <typename Item>
1610 {
1611 return (getSize() == 0);
1612 }
1613
1614 template <typename Item>
1616 {
1617 for(const HashGridBox3<Item>& e: box_)
1618 {
1619 if(!e.isValid()) return false;
1620 }
1621 return true;
1622 }
1623
1624 template <typename Item>
1625 void HashGrid3<Item>::dump(std::ostream& s, Size depth) const
1626 {
1628
1629 BALL_DUMP_DEPTH(s, depth);
1630
1631 BALL_DUMP_DEPTH(s, depth);
1632 s << " origin: " << origin_ << std::endl;
1633
1634 BALL_DUMP_DEPTH(s, depth);
1635 s << " unit: " << unit_.z << std::endl;
1636
1637 BALL_DUMP_DEPTH(s, depth);
1638 s << " dimension: " << dimension_x_ << " "
1639 << dimension_y_ << " "
1640 << dimension_z_ << std::endl;
1641
1642 Size size = getSize();
1643 BALL_DUMP_DEPTH(s, depth);
1644 s << " size: " << size << std::endl;
1645
1646 BALL_DUMP_DEPTH(s, depth);
1647 s << " non empty boxes: " << countNonEmptyBoxes() << std::endl;
1648
1649 BALL_DUMP_DEPTH(s, depth);
1650 s << " boxes:" << std::endl;
1651 Position x, y, z;
1652 for (Position index = 0; index < (Position)size; ++index)
1653 {
1654 BALL_DUMP_DEPTH(s, depth);
1655 getIndices(box_[index], x, y, z);
1656 s << " " << index << ". box: ("
1657 << x << ',' << y << ',' << z << ')' << std::endl;
1658 box_[index].dump(s, 1);
1659 }
1660
1661 BALL_DUMP_DEPTH(s, depth);
1662 s << " non-empty boxes:" << std::endl;
1663
1664 for (Position i=0; i<27; ++i)
1665 {
1666 if (!box_[i].isEmpty())
1667 s << " " << getIndex_(box_[i]) << std::endl;
1668 }
1670 }
1671
1672 template <typename Item>
1674 {
1675 if (!processor.start())
1676 {
1677 return false;
1678 }
1679 Processor::Result result;
1680
1681 for (Position i=0; i<27; ++i)
1682 {
1683 HashGridBox3<Item>* box = &box_[i];
1684 for (typename HashGridBox3<Item>::DataIterator *item = box->beginData(); +item; ++item)
1685 {
1686 result = processor(*item);
1687
1688 if (result <= Processor::BREAK)
1689 {
1690 return result == Processor::BREAK;
1691 }
1692 }
1693 }
1694
1695 return processor->finish();
1696 }
1697
1698 template <typename Item>
1700 {
1701 if (!processor.start())
1702 {
1703 return false;
1704 }
1705
1706 Processor::Result result;
1707
1708 for (Position i=0; i<27; ++i)
1709 {
1710 HashGridBox3<Item>* box = &box_[i];
1711 result = processor(*box);
1712
1713 if (result <= Processor::BREAK)
1714 {
1715 return result == Processor::BREAK;
1716 }
1717 }
1718
1719 return processor->finish();
1720 }
1721
1722 template <typename Item>
1725 {
1726 if ((&box < &box_[0]) || (&box - &box_[0] >= getSize()))
1727 {
1728 return INVALID_Index;
1729 }
1730 else
1731 {
1732 return (Index)(&box - &box_[0]);
1733 }
1734 }
1735} // namespace BALL
1736
1737#endif // BALL_DATATYPE_HASHGRID_H
#define BALL_DUMP_STREAM_PREFIX(os)
Definition: macros.h:391
#define BALL_DUMP_STREAM_SUFFIX(os)
Definition: macros.h:395
#define BALL_DUMP_DEPTH(os, depth)
Definition: macros.h:390
#define BALL_INLINE
Definition: debug.h:15
#define BALL_CREATE(name)
Definition: create.h:62
#define BALL_CREATE_DEEP(name)
Definition: create.h:26
STL namespace.
Definition: constants.h:13
static const Position INVALID_Position
BALL_ULONG64_TYPE LongSize
static const Index INVALID_Index
BALL_SIZE_TYPE Position
BALL_LONG64_TYPE LongIndex
BALL_INDEX_TYPE Index
const signed char BALL_EXPORT neighbour_table_[27][3]
T max(const T &a, const T &b)
Definition: MATHS/common.h:75
long floor(const T &t)
Definition: MATHS/common.h:284
static ConstForwardIterator begin(const Container &container)
static ConstForwardIterator end(const Container &container)
static ForwardIterator begin(const Container &container)
static ForwardIterator end(const Container &container)
virtual bool start()
Definition: processor.h:92
virtual bool finish()
Definition: processor.h:99
Three-dimensional Hash Grid Class.
Definition: hashGrid.h:755
void destroy()
Destroys the grid (obsolete, only calls clear())
Definition: hashGrid.h:1260
bool isEmpty() const
Tests, whether this is empty.
Definition: hashGrid.h:1609
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)
Definition: hashGrid.h:1281
bool operator==(const HashGrid3 &grid) const
Equality operator.
Definition: hashGrid.h:1585
bool getIndices(const HashGridBox3< Item > &box, Position &x, Position &y, Position &z) const
Get the position indices of a HashGridBox3.
Definition: hashGrid.h:1513
virtual void dump(std::ostream &s=std::cout, Size depth=0) const
Dump the contents of a HashGrid3 to a stream.
Definition: hashGrid.h:1625
static float calculateMinSpacing(LongIndex memory, const Vector3 &size)
Definition: hashGrid.h:1456
Vector3 & getUnit()
Returns the unit of the grid.
Definition: hashGrid.h:1378
Vector3 & getOrigin()
Returns the origin of the grid.
Definition: hashGrid.h:1364
ForwardIterator< HashGrid3< Item >, HashGridBox3< Item >, BoxIteratorPosition, BoxIteratorTraits > BoxIterator
Definition: hashGrid.h:1106
bool remove(Position x, Position y, Position z, const Item &item)
Remove an item from position (x, y ,z)
Definition: hashGrid.h:1560
virtual bool isValid() const
Validity check.
Definition: hashGrid.h:1615
bool operator!=(const HashGrid3 &grid) const
Inequality operator.
Definition: hashGrid.h:1602
BoxIterator beginBox()
Definition: hashGrid.h:1109
virtual void clear()
Clears the whole grid.
Definition: hashGrid.h:1226
void insert(Position x, Position y, Position z, const Item &item)
Insert an item at position (x, y, z)
Definition: hashGrid.h:1536
virtual ~HashGrid3()
Destructor.
Definition: hashGrid.h:1221
Size countNonEmptyBoxes() const
Counts the non-empty boxes of a grid.
Definition: hashGrid.h:1348
bool apply(UnaryProcessor< Item > &processor)
Definition: hashGrid.h:1673
ConstForwardIterator< HashGrid3< Item >, HashGridBox3< Item >, BoxIteratorPosition, BoxIteratorTraits > ConstBoxIterator
Definition: hashGrid.h:1125
friend class BoxIteratorTraits
Definition: hashGrid.h:1100
const HashGrid3 & operator=(const HashGrid3 &grid)
Assignment operator.
Definition: hashGrid.h:1321
HashGridBox3< Item > * getBox(Position x, Position y, Position z)
Return the HashGridBox3 at position (x, y, z)
Definition: hashGrid.h:1466
BoxIterator endBox()
Definition: hashGrid.h:1115
void get(Vector3 &origin, Vector3 &unit, Size &dimension_x, Size &dimension_y, Size &dimension_z) const
Definition: hashGrid.h:1330
Size getSizeY() const
Get the y dimension of the grid.
Definition: hashGrid.h:1399
Size getSizeZ() const
Get the z dimension of the grid.
Definition: hashGrid.h:1406
ConstBoxIterator endBox() const
Definition: hashGrid.h:1134
Position BoxIteratorPosition
Definition: hashGrid.h:978
Size getSize() const
Returns the size of a grid, i. e. ?????
Definition: hashGrid.h:1357
ConstBoxIterator beginBox() const
Definition: hashGrid.h:1128
const Item * getClosestItem(const Vector3 &point, Size distance) const
Definition: hashGrid.h:1412
void host(Visitor< HashGrid3 > &visitor)
Definition: hashGrid.h:1578
HashGrid3()
Default constructor.
Definition: hashGrid.h:1165
Size getSizeX() const
Get the x dimension of the grid.
Definition: hashGrid.h:1392
ConstDataIterator endData() const
Definition: hashGrid.h:522
bool removeAll(const Item &item)
Definition: hashGrid.h:615
bool apply(UnaryProcessor< Item > &processor)
Definition: hashGrid.h:685
ConstForwardIterator< HashGridBox3< Item >, HashGridBox3< Item >, BoxIteratorPosition, BoxIteratorTraits > ConstBoxIterator
This is the const version of BoxIterator .
Definition: hashGrid.h:346
ForwardIterator< HashGridBox3< Item >, Item, DataIteratorPosition, DataIteratorTraits > DataIterator
Definition: hashGrid.h:492
bool remove(const Item &item)
Definition: hashGrid.h:600
const Item * find(const Item &item) const
The const version of find()
Definition: hashGrid.h:581
friend class DataIteratorTraits
Definition: hashGrid.h:484
ConstBoxIterator endBox() const
get the last box
Definition: hashGrid.h:355
void dump(std::ostream &s=std::cout, Size depth=0) const
Definition: hashGrid.h:664
ConstForwardIterator< HashGridBox3< Item >, Item, DataIteratorPosition, DataIteratorTraits > ConstDataIterator
Definition: hashGrid.h:513
DataIterator beginData()
Definition: hashGrid.h:495
void host(Visitor< HashGridBox3 > &visitor)
Host method.
Definition: hashGrid.h:624
bool isValid() const
Definition: hashGrid.h:657
DataContainer data
Definition: hashGrid.h:531
DataIterator endData()
Definition: hashGrid.h:501
ConstBoxIterator beginBox() const
get the first box
Definition: hashGrid.h:349
HashGridBox3(HashGrid3< Item > *parent)
Default constructor.
Definition: hashGrid.h:535
void getIndices(Position &x, Position &y, Position &z)
Definition: hashGrid.h:561
bool has(const Item &item) const
Definition: hashGrid.h:644
Position BoxIteratorPosition
Definition: hashGrid.h:178
bool isEmpty() const
Definition: hashGrid.h:651
friend class BoxIteratorTraits
Definition: hashGrid.h:318
ForwardIterator< HashGridBox3< Item >, HashGridBox3< Item >, BoxIteratorPosition, BoxIteratorTraits > BoxIterator
Definition: hashGrid.h:327
Item * find(const Item &item)
Definition: hashGrid.h:567
DataContainer::iterator DataIteratorPosition
Definition: hashGrid.h:362
bool apply(UnaryProcessor< HashGridBox3< Item > > &processor)
Definition: hashGrid.h:708
BoxIterator endBox()
get the last box
Definition: hashGrid.h:336
void setParent(HashGrid3< Item > *p)
Definition: hashGrid.h:554
std::forward_list< Item > DataContainer
Definition: hashGrid.h:360
void clear()
Clears the grid box.
Definition: hashGrid.h:541
bool operator==(const HashGridBox3 &box) const
Equality operator.
Definition: hashGrid.h:630
HashGrid3< Item > * parent
Definition: hashGrid.h:529
BoxIterator beginBox()
get the first box
Definition: hashGrid.h:330
bool operator!=(const HashGridBox3 &box) const
Inequality operator.
Definition: hashGrid.h:637
Size getSize() const
Definition: hashGrid.h:587
ConstDataIterator beginData() const
Definition: hashGrid.h:516
void insert(const Item &item)
Definition: hashGrid.h:594
BoxIteratorTraits(const HashGridBox3 &box)
Definition: hashGrid.h:198
bool operator!=(const BoxIteratorTraits &traits) const
Definition: hashGrid.h:249
const HashGridBox3 * getContainer() const
Definition: hashGrid.h:224
const HashGridBox3< Item > & getData() const
Definition: hashGrid.h:292
bool operator==(const BoxIteratorTraits &traits) const
Definition: hashGrid.h:244
BoxIteratorPosition & getPosition()
Definition: hashGrid.h:234
HashGridBox3< Item > & getData()
Definition: hashGrid.h:287
const BoxIteratorPosition & getPosition() const
Definition: hashGrid.h:239
BoxIteratorTraits(const BoxIteratorTraits &traits, bool=true)
Definition: hashGrid.h:209
bool operator!=(const DataIteratorTraits &traits) const
Definition: hashGrid.h:427
DataIteratorPosition & getPosition()
Definition: hashGrid.h:412
DataIteratorTraits(const DataIteratorTraits &traits, bool=true)
Definition: hashGrid.h:384
DataIteratorTraits(const HashGridBox3 &box)
Definition: hashGrid.h:378
const DataIteratorTraits & operator=(const DataIteratorTraits &traits)
Definition: hashGrid.h:390
const DataIteratorPosition & getPosition() const
Definition: hashGrid.h:417
const HashGridBox3 * getContainer() const
Definition: hashGrid.h:402
bool operator==(const DataIteratorTraits &traits) const
Definition: hashGrid.h:422
const HashGridBox3< Item > & getData() const
Definition: hashGrid.h:1084
HashGridBox3< Item > & getData()
Definition: hashGrid.h:1079
BoxIteratorPosition & getPosition()
Definition: hashGrid.h:1028
BoxIteratorTraits(const BoxIteratorTraits &traits, bool=true)
Definition: hashGrid.h:1000
const BoxIteratorPosition & getPosition() const
Definition: hashGrid.h:1033
BoxIteratorTraits(const HashGrid3 &grid)
Definition: hashGrid.h:994
const HashGrid3 * getContainer() const
Definition: hashGrid.h:1018
void set(const T *ptr)
Definition: vector3.h:615
#define BALL_EXPORT
Definition: COMMON/global.h:50