SheafSystem  0.0.0.0
d_tree_point_locator_node.impl.h
Go to the documentation of this file.
1 
2 //
3 // Copyright (c) 2014 Limit Point Systems, Inc.
4 //
5 // Licensed under the Apache License, Version 2.0 (the "License");
6 // you may not use this file except in compliance with the License.
7 // You may obtain a copy of the License at
8 //
9 // http://www.apache.org/licenses/LICENSE-2.0
10 //
11 // Unless required by applicable law or agreed to in writing, software
12 // distributed under the License is distributed on an "AS IS" BASIS,
13 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 // See the License for the specific language governing permissions and
15 // limitations under the License.
16 //
17 
20 
21 #ifndef D_TREE_POINT_LOCATOR_NODE_IMPL_H
22 #define D_TREE_POINT_LOCATOR_NODE_IMPL_H
23 
24 #ifndef SHEAF_DLL_SPEC_H
25 #include "SheafSystem/sheaf_dll_spec.h"
26 #endif
27 
28 #ifndef ASSERT_CONTRACT_H
29 #include "SheafSystem/assert_contract.h"
30 #endif
31 
32 #ifndef ERROR_MESSAGE_H
33 #include "SheafSystem/error_message.h"
34 #endif
35 
36 #ifndef D_TREE_POINT_LOCATOR_H
37 #include "SheafSystem/d_tree_point_locator.h"
38 #endif
39 
40 #ifndef D_TREE_POINT_LOCATOR_PATH_H
41 #include "SheafSystem/d_tree_point_locator_path.h"
42 #endif
43 
44 #ifndef STD_SSTREAM_H
45 #include "SheafSystem/std_sstream.h"
46 #endif
47 
48 //#undef DIAGNOSTIC_OUTPUT
49 //#define DIAGNOSTIC_OUTPUT
50 
51 namespace geometry
52 {
53 
54 // ============================================================================
55 // D_TREE_POINT_LOCATOR_NODE FACET
56 // ============================================================================
57 
58 // PUBLIC MEMBER FUNCTIONS
59 
60 template <int DC, int DB>
63 
64 {
65  // Preconditions:
66 
67  // Body:
68 
69  // Initialize the branches to null.
70 
71  for(int i=0; i<DEGREE; ++i)
72  {
73  _branches[i] = 0;
74  }
75 
76  _branch_ct = 0;
77 
78  // Postconditions:
79 
80 }
81 
82 template <int DC, int DB>
85 {
86  // Preconditions:
87 
88  // Body:
89 
90  (*this) = xother;
91 
92  // Postconditions:
93 
94  ensure(*this == xother);
95 
96  // Exit:
97 
98  return;
99 }
100 
101 template <int DC, int DB>
105 {
106  // Preconditions:
107 
108  // Body:
109 
110  if(this == &xother)
111  return *this;
112 
113  _box_list = xother._box_list;
114 
115  for(int i=0; i<DEGREE; ++i)
116  _branches[i] = xother._branches[i];
117 
118  _branch_ct = xother._branch_ct;
119 
120  // Postconditions:
121 
122  ensure(*this == xother);
123 
124  return *this;
125 }
126 
127 template <int DC, int DB>
128 bool
131 {
132  // Preconditions:
133 
134  // Body:
135 
136  if(this == &xother)
137  return true;
138 
139  bool result = (_box_list == xother._box_list);
140 
141  for(int i=0; i<DEGREE; ++i)
142  {
143  result = result && ( _branches[i] == xother._branches[i]);
144  }
145 
146  result == result && (_branch_ct == xother._branch_ct);
147 
148  // Postconditions:
149 
150  // Exit:
151 
152  return result;
153 }
154 
155 template <int DC, int DB>
158 {
159  // Preconditions:
160 
161  // Body:
162 
163  // Nothing to do.
164 
165  // Postconditions:
166 
167  // Exit:
168 
169  return;
170 }
171 
172 template <int DC, int DB>
173 bool
175 invariant() const
176 {
177  bool result = true;
178 
179  invariance(branch_ct() <= degree());
180  invariance_for_all(i, 0, degree(), (is_leaf() ? branch(i) == 0 : true));
181 
182  return result;
183 }
184 
185 template <int DC, int DB>
188 branch(int xindex) const
189 {
191 
192  // Preconditions:
193 
194  require((0 <= xindex) && (xindex < degree()));
195 
196  // Body:
197 
198  result = _branches[xindex];
199 
200  // Postconditions:
201 
202 
203  // Exit:
204 
205  return result;
206 }
207 
208 template <int DC, int DB>
209 bool
211 is_leaf() const
212 {
213  bool result;
214 
215  // Preconditions:
216 
217  // Body:
218 
219  result = (_branch_ct == 0);
220 
221  // Postconditions:
222 
223 
224  // Exit:
225 
226  return result;
227 }
228 
229 template <int DC, int DB>
230 bool
232 is_empty() const
233 {
234  bool result;
235 
236  // Preconditions:
237 
238 
239  // Body:
240 
241  result = _box_list.empty();
242 
243  // Postconditions:
244 
245 
246  // Exit:
247 
248  return result;
249 }
250 
251 
252 template <int DC, int DB>
253 void
257 {
258  // Preconditions:
259 
260  require(xpath.intersects(xbox));
261 
262  // Body:
263 
264  define_old_variable(size_type old_xpath_depth = xpath.depth());
265 
266  if(xpath.depth() == xpath.tree()->depth())
267  {
268  // We are as deep as we can go; insert the box here.
269 
270  _box_list.push_front(xbox);
271  }
272  else
273  {
274  // We're not as deep as we can go; keep descending.
275 
277  xpath.tree()->node_pool();
278 
279  if(!is_empty())
280  {
281  // This node is a leaf that already contains exactly one box.
282 
283  assertion(++(_box_list.begin()) == _box_list.end());
284 
285  // We'll have to subdivide the node and move the box;
286  // iterate over all the possible branches:
287 
288  const d_bounding_box<DC, DB>* lfirst_box = _box_list.front();
289 
290  xpath.descend();
291  for(size_type i=0; i<DEGREE; i++)
292  {
293  d_tree_point_locator_node* lbranch = _branches[i];
294 
295  // This branch is a new leaf;
296 
297  assertion(lbranch == 0);
298 
299  xpath.put_head(i);
300  if(xpath.intersects(lfirst_box))
301  {
302  // This leaf intersects the box;
303  // create the leaf and store the box.
304 
305  _branches[i] = lnode_pool.allocate();
306  _branch_ct++;
307  _branches[i]->_box_list.push_front(lfirst_box);
308  }
309  }
310  xpath.put_head(0);
311  xpath.ascend();
312  _box_list.pop_front();
313  }
314 
315  // Now this node is an interior node that contains no boxes.
316 
317  assertion(_box_list.empty());
318 
319  // Descend the branches.
320 
321  xpath.descend();
322  for(size_type i=0; i<DEGREE; i++)
323  {
324  xpath.put_head(i);
325  if(xpath.intersects(xbox))
326  {
327  // This branch intersects the box.
328 
329  d_tree_point_locator_node* lbranch = _branches[i];
330 
331  if(lbranch == 0)
332  {
333  // This branch is a new leaf;
334  // create it and store the box.
335 
336  _branches[i] = lnode_pool.allocate();
337  _branch_ct++;
338  _branches[i]->_box_list.push_front(xbox);
339  }
340  else
341  {
342  // Descend the branch.
343 
344  lbranch->insert_box(xbox, xpath);
345  }
346  }
347  }
348  xpath.put_head(0);
349  xpath.ascend();
350  }
351 
352  // Postconditions:
353 
354  // Following is unexecutable for efficiency.
355 
356  ensure(unexecutable(contains_box(xbox, xpath)));
357  ensure(xpath.depth() == old_xpath_depth);
358 
359  // Exit:
360 
361  return;
362 }
363 
364 template <int DC, int DB>
365 void
369 {
370  // Preconditions:
371 
372  require(xpath.intersects(xbox));
373 
374  //require(is_empty() ? xpath.depth() > xpath.tree()->depth() : true);
375  require(is_empty() ? xpath.depth() < xpath.tree()->depth() : true);
376 
377  // Body:
378 
379  define_old_variable(size_type old_xpath_depth = xpath.depth());
380 
382  xpath.tree()->node_pool();
383 
384  if(is_empty())
385  {
386  // Nothing in this node; descend the branches.
387 
388  xpath.descend();
389  for(size_type i=0; i<DEGREE; i++)
390  {
391  xpath.put_head(i);
392  if(xpath.intersects(xbox))
393  {
394  // Descend the branch.
395 
396  d_tree_point_locator_node* lbranch = _branches[i];
397  lbranch->remove_box(xbox, xpath);
398  if(lbranch->is_leaf() && lbranch->is_empty())
399  {
400  lnode_pool.deallocate(lbranch);
401  _branches[i] = 0;
402  _branch_ct--;
403  }
404  }
405  }
406  xpath.put_head(0);
407  xpath.ascend();
408  }
409  else
410  {
411  // This node has a box list; it must contain xbox.
412  // Find it and erase it.
413 
414  if(xbox == _box_list.front())
415  {
416  _box_list.pop_front();
417  }
418  else
419  {
420  typename box_list_type::iterator lprev = _box_list.begin();
421  typename box_list_type::iterator lcur = ++lprev;
422  while(lcur != _box_list.end())
423  {
424  if(xbox == *lcur)
425  {
426  _box_list.erase_after(lprev);
427  break;
428  }
429  lprev = lcur;
430  ++lcur;
431  }
432  }
433  }
434 
435 
436  // Postconditions:
437 
438  // Following is unexecutable for efficiency.
439 
440  ensure(unexecutable(!contains_box(xbox, xpath)));
441  ensure(xpath.depth() == old_xpath_depth);
442 
443  // Exit:
444 
445  return;
446 }
447 
448 
449 template <int DC, int DB>
450 bool
454 {
455  bool result = false;
456 
457  // Preconditions:
458 
459  require(is_empty() ? xpath.depth() < xpath.tree()->depth() : true);
460 
461  // Body:
462 
463  define_old_variable(size_type old_xpath_depth = xpath.depth());
464 
465  if(is_empty())
466  {
467  // Nothing in this node; descend the branches.
468 
469  xpath.descend();
470  for(size_type i=0; !result && (i<DEGREE); i++)
471  {
472  xpath.put_head(i);
473  if(xpath.intersects(xbox))
474  {
475  // Descend the branch.
476 
477  d_tree_point_locator_node* lbranch = _branches[i];
478  result = lbranch->contains_box(xbox, xpath);
479  }
480  }
481  xpath.put_head(0);
482  xpath.ascend();
483  }
484  else
485  {
486  // This node has a box list; search it for xbox.
487 
488  typename box_list_type::const_iterator litr = _box_list.begin();
489  while(!result && (litr != _box_list.end()))
490  {
491  result = (*litr == xbox);
492  ++litr;
493  }
494  }
495 
496  // Postconditions:
497 
498  ensure(xpath.depth() == old_xpath_depth);
499 
500  // Exit:
501 
502  return result;
503 }
504 
505 template <int DC, int DB>
506 void
509 {
510  // Preconditions:
511 
512 
513  // Body:
514 
515  for(int i=0; i<DEGREE; i++)
516  {
517  _branches[i] = 0;
518  }
519 
520  //$$SCRIBBLE: Added the following so that is_leaf() == true.
521  _branch_ct = 0;
522 
523  _box_list.clear();
524 
525  // Postconditions:
526 
527  ensure(is_empty());
528  ensure(is_leaf());
529 
530  // Exit:
531 
532  return;
533 }
534 
535 template <int DC, int DB>
539 {
540  // Preconditions:
541 
542  require(xpath.depth() == xpath.tree()->depth() ? is_leaf() : true);
543 
544  // Body
545 
546  define_old_variable(size_type old_xpath_depth = xpath.depth());
547 
548  const box_list_type* lresult_ptr;
549 
550  if(is_leaf())
551  {
552  lresult_ptr = &_box_list;
553  }
554  else
555  {
556  // Descend the path.
557 
558  xpath.descend();
559  lresult_ptr = &(_branches[xpath.head()]->box_list(xpath));
560  xpath.ascend();
561  }
562 
563  // Postconditions:
564 
565  ensure(xpath.depth() == old_xpath_depth);
566 
567  // Exit:
568 
569  return *lresult_ptr;
570 }
571 
572 template <int DC, int DB>
575 box_list() const
576 {
577  // Preconditions:
578 
579 
580  // Body
581 
582  const box_list_type& result = _box_list;
583 
584  // Postconditions:
585 
586  // Exit:
587 
588  return result;
589 }
590 
591 template <int DC, int DB>
592 std::string*
594 to_string() const
595 {
596  using namespace std;
597 
598  ostringstream ostr;
599 
600  ostr << "d_tree_point_locator_node:" << endl;
601 
602  ostr << "this = " << this << endl;
603 
604 // cout << "d_tree_point_locator_node:" << endl;
605 
606 // cout << "this = " << this << endl;
607 
608  //$$SCRIBBLE: In at least one simple test case box_list().end() == NULL
609  // and the iteration never terminates. So, comment it out for now.
610 
611 // ostr << "box_list() = " << endl;
612 // cout << "box_list() = " << endl;
613 
614 // typename box_list_type::const_iterator lbox_itr = box_list().begin();
615 // while(lbox_itr != box_list().end())
616 // {
617 // ostr << **lbox_itr << endl;
618 // }
619 
620 // cout << "DEGREE = " << DEGREE << endl;
621 
622  for(int i=0; i<DEGREE; ++i)
623  {
624  ostr << "_branches[i] = " << _branches[i] << endl;
625 // cout << "_branches[i] = " << _branches[i] << endl;
626  }
627 
628  for(int i=0; i<DEGREE; ++i)
629  {
630  if(_branches[i] != 0)
631  {
632 // cout << "+++ _branches[i] = " << _branches[i] << endl;
633  string* s = _branches[i]->to_string();
634  ostr << *s;
635  delete s;
636  }
637  }
638 
639  ostr << ends;
640 
641  string* result = new string(ostr.str());
642 
643 // cout << "*result = " << *result << endl;
644 
645  return result;
646 }
647 
648 
649 template <int DC, int DB>
650 size_type
653 {
654  size_type result;
655 
656  // Preconditions:
657 
658 
659  // Body:
660 
661  result = DEGREE;
662 
663  // Postconditions:
664 
665  ensure(result == DEGREE);
666 
667  // Exit:
668 
669  return result;
670 }
671 
672 template <int DC, int DB>
673 size_type
675 branch_ct() const
676 {
677  size_type result;
678 
679  // Preconditions:
680 
681 
682  // Body:
683 
684  result = _branch_ct;
685 
686  // Postconditions:
687 
688 
689  // Exit:
690 
691  return result;
692 }
693 
694 
695 // PROTECTED MEMBER FUNCTIONS
696 
697 template <int DC, int DB>
700 next() const
701 {
703 
704  // Preconditions:
705 
706 
707  // Body:
708 
709  result = _branches[0];
710 
711  // Postconditions:
712 
713 
714  // Exit:
715 
716  return result;
717 }
718 
719 template <int DC, int DB>
720 void
723 {
724  // Preconditions:
725 
726 
727  // Body:
728 
729  _branches[0] = xnode;
730 
731  // Postconditions:
732 
733  ensure(next() == xnode);
734 
735  // Exit:
736 
737  return;
738 }
739 
740 } // namespace geometry
741 
742 // ===========================================================
743 // NON-MEMBER FUNCTIONS
744 // ===========================================================
745 
746 #ifndef DOXYGEN_SHOULD_SKIP_THIS
747 
748 template <int DC, int DB>
749 std::ostream&
750 geometry::operator<<(std::ostream& xos, const geometry::d_tree_point_locator_node<DC, DB>& xnode)
751 {
752  std::string* s = xnode.to_string();
753  xos << *s;
754  delete s;
755 
756  return xos;
757 }
758 
759 #endif // ifndef DOXYGEN_SHOULD_SKIP_THIS
760 
761 #endif // D_TREE_POINT_LOCATOR_NODE_IMPL_H
bool contains_box(const d_bounding_box< DC, DB > *xbox, d_tree_point_locator_path< DC, DB > &xpath) const
True if xbox is in the box list of this or its branches, recursively.
T * allocate()
Allocate next available object from the free list.
d_tree_point_locator_node< DC, DB > & operator=(const d_tree_point_locator_node< DC, DB > &xother)
Assignment operator.
d_tree_point_locator_node< DC, DB > * branch(int xindex) const
The xindex-th branch.
std::string * to_string() const
Get instance information as a string.
size_type depth() const
The current depth.
static size_type degree()
The maximum number of branches a node may have.
d_tree_point_locator_node< DC, DB > * next() const
The next node in the free list; intended for use only by class ptr_linked_pool.
void ascend()
Ascend one level in the path.
size_type head() const
The branch index of the head of the path.
A reallocatable pool of objects of type T. Objects in the pool are either "allocated" or linked toget...
STL namespace.
bool is_empty() const
True if box_list() is empty.
box_list_type _box_list
The list of bounding boxes associated with this.
void clear()
Clears all branches and all boxes from this. Warning: this function does not deallocate the branches ...
size_type _branch_ct
The number of non-null branches.
bool operator==(const d_tree_point_locator_node< DC, DB > &xother)
Equality operator.
void remove_box(const d_bounding_box< DC, DB > *xbox, d_tree_point_locator_path< DC, DB > &xpath)
Removes xbox from this and its branches, recursively.
const box_list_type & box_list() const
The bounding boxes which intersect this.
size_type branch_ct() const
The number of non-null branches.
bool intersects(const d_bounding_box< DC, DB > *xbox) const
True if the tree box represented by the current head intersects the box with lower bound xlb and uppe...
sheaf::size_type size_type
An unsigned integral type used to represent sizes and capacities.
A bounding box that can be strung together into a list.
A path in an d_tree_point_locator search structure.
void push_front(const T &value)
Prepends the given element value to the beginning of the container.
void descend()
Descend one level in the path.
void put_head(size_type xhead)
Set the current head to xhead.
d_tree_point_locator< DC, DB > * tree() const
The tree this is a path in.
void put_next(d_tree_point_locator_node< DC, DB > *xnode)
Sets the next node in the free list to xnode; intended for use only by class ptr_linked_pool.
d_tree_point_locator_node< DC, DB > * _branches[DEGREE]
The branches of this node.
A node in a d_tree_point_locator search structure.
Namespace for geometry component of sheaf system.
Definition: field_vd.h:54
void insert_box(const d_bounding_box< DC, DB > *xbox, d_tree_point_locator_path< DC, DB > &xpath)
Inserts xbox in this or somewhere on one of its branches.
Wrapper class for forward_list or slist depending on compiler. The class replicates the minimum subse...
bool is_leaf() const
True if this node is a leaf node.