SheafSystem  0.0.0.0
depth_first_itr.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 DEPTH_FIRST_ITR_IMPL_H
22 #define DEPTH_FIRST_ITR_IMPL_H
23 
24 #ifndef SHEAF_DLL_SPEC_H
25 #include "SheafSystem/sheaf_dll_spec.h"
26 #endif
27 #endif
28 
29 #ifndef ASSERT_CONTRACT_H
30 #include "SheafSystem/assert_contract.h"
31 #endif
32 
33 #ifndef DEPTH_FIRST_ITR_H
34 #include "SheafSystem/depth_first_itr.h"
35 #endif
36 
37 #ifndef INDEX_SPACE_ITERATOR_H
38 #include "SheafSystem/index_space_iterator.h"
39 #endif
40 
41 //#define DIAGNOSTIC_OUTPUT
42 
43 namespace sheaf
44 {
45 
46 // ===========================================================
47 // DEPTH_FIRST_ITR FACET
48 // ===========================================================
49 
50 // PUBLIC MEMBER FUNCTIONS
51 
52 template <typename T>
55 {
56  // Preconditions:
57 
58  // Body:
59 
60  // Release cover iterators.
61 
62  release_cover_id_space_iterators();
63 
64  // Delete the anchor;
65 
66  if(_anchor != 0)
67  {
68  _anchor->detach_from_state();
69  delete _anchor;
70  }
71 
72  // Detach the client filter.
73 
74  _client_filter.detach_from_state();
75 
76  // Delete the filter and visited marker
77 
78  if(_new_filter)
79  delete _filter;
80  if(_has_visited != 0)
81  delete _has_visited;
82 
83  // Postconditions:
84 
85  // Exit:
86 
87  return;
88 }
89 
90 template <typename T>
91 const char*
93 NULL_FILTER = "";
94 
95 // PROTECTED MEMBER FUNCTIONS
96 
97 template <typename T>
100 {
101 
102  // Preconditions:
103 
104 
105  // Body:
106 
107  // Set other members to default values.
108 
109  _anchor = 0;
110  _action = NOT_AN_ACTION;
111  _index.invalidate();
112  _client_filter.detach_from_state();
113  _new_filter = false;
114  _descending = true;
115  _strict = false;
116  initialize_order(NOT_AN_ORDER);
117  _state = NOT_A_STATE;
118  _visit_once = true;
119  _has_visited = 0;
120  _filter = 0;
121  _path_head_lc = 0;
122  _path_head = 0;
123 
124  // Postconditions:
125 
126  ensure(invariant());
127  ensure(order() == NOT_AN_ORDER);
128  ensure(!is_initialized());
129  ensure(descending());
130  ensure(!strict());
131  ensure(visit_once());
132  ensure(is_done());
133 
134  // Exit
135 
136  return;
137 }
138 
139 template <typename T>
142 {
143  // Preconditions:
144 
145  // Body:
146 
147  // Initialize to default state, like default constructor,
148  // then call assignment operator.
149 
150  _anchor = 0;
151  _action = NOT_AN_ACTION;
152  _index.invalidate();
153  _client_filter.detach_from_state();
154  _new_filter = false;
155  _descending = true;
156  _strict = false;
157  initialize_order(NOT_AN_ORDER);
158  _state = NOT_A_STATE;
159  _visit_once = true;
160  _has_visited = 0;
161  _filter = 0;
162  _path_head_lc = 0;
163  _path_head = 0;
164 
165 // // Ensure !is_initialized(), then call assigment operator.
166 
167 // _anchor = 0;
168 // _new_filter = false;
169 // _filter = 0;
170 
171  (*this) = xother;
172 
173  if(is_initialized())
174  {
175  // Assignemnt operator ensures is_done, so must reset,
176  // but markers have already been initialized.
177 
178  reset(NO_RESET);
179  }
180  else
181  {
182  // xother was not initialized, can't reset
183  }
184 
185  // Postconditions:
186 
187  ensure(invariant());
188  ensure(order() == xother.order());
189  ensure(is_initialized() == xother.is_initialized());
190  ensure(is_initialized() ? anchor().is_same_state(&xother.anchor()) : true);
191  ensure(is_initialized() ? anchor().version() == xother.anchor().version() : true);
192  ensure(is_initialized() ? filter().is_same_state(&(const_cast<depth_first_itr&>(xother).filter())) : true);
193  ensure(is_initialized() ? descending() == xother.descending() : true);
194  ensure(is_initialized() ? strict() == xother.strict() : true);
195  ensure(visit_once() == xother.visit_once());
196  ensure(unexecutable(this is first member of iteration or is_done()));
197 
198  // Exit
199 
200  return;
201 }
202 
203 template <typename T>
207 {
208 
209  // Preconditions:
210 
211  // Body:
212 
213  if(this == &xother)
214  {
215  // lhs is same object as rhs.
216  // Don't have to copy any data, but have to
217  // force_is_done in order to satisfy postcondition.
218  // This is a weird side effect, but not much else we can do.
219 
220  force_is_done();
221  }
222  else
223  {
224  depth_first_itr& lother = const_cast<depth_first_itr&>(xother);
225 
226  if(is_initialized())
227  {
228  // Force this into an uninitialized state.
229 
230  force_is_done();
231 
232  _anchor->detach_from_state();
233  delete _anchor;
234  _anchor = 0;
235 
236  // _action set in force_is_done().
237  // _index set in force is done()
238 
239  _client_filter.detach_from_state();
240 
241  if(_new_filter)
242  {
243  delete _filter;
244  _filter = 0;
245  _new_filter = false;
246  }
247 
248  _descending = true;
249  _strict = false;
250  initialize_order(NOT_AN_ORDER);
251 
252  // _state set in force_is_done()
253 
254  _visit_once = true;
255 
256  delete _has_visited;
257  _has_visited = 0;
258 
259  // _filter set above
260  }
261 
262  // Now this is not initialized, which implies is_done
263 
264  assertion(!is_initialized());
265  assertion(is_done());
266 
267  if(lother.is_initialized())
268  {
269  // Initialize this to the same state as xother.
270 
271  initialize_order(lother._order);
272  _descending = lother._descending;
273  _strict = lother._strict;
274 
275  initialize_traversal(lother.anchor());
276  if(lother.filter().index() !=~ lother.anchor().version_index())
277  {
278  initialize_filter(lother.filter().index());
279  }
280  }
281 
282  _visit_once = lother._visit_once;
283  }
284 
285 
286  // Postconditions:
287 
288  ensure(invariant());
289  ensure(order() == xother.order());
290  ensure(is_initialized() == xother.is_initialized());
291  ensure(is_initialized() ? anchor().is_same_state(&xother.anchor()) : true);
292  ensure(is_initialized() ? anchor().version() == xother.anchor().version() : true);
293  ensure(is_initialized() ? filter().is_same_state(&(const_cast<depth_first_itr&>(xother).filter())) : true);
294  ensure(is_initialized() ? descending() == xother.descending() : true);
295  ensure(is_initialized() ? strict() == xother.strict() : true);
296  ensure(visit_once() == xother.visit_once());
297  ensure(is_done());
298 
299  // Exit
300 
301  return *this;
302 }
303 
304 template <typename T>
305 void
308 {
309  // Preconditions:
310 
311  require(is_initialized());
312  require(_path_tail.empty()); // must be looking for first member
313 
314  // Body:
315 
316  disable_invariant_check();
317 
318  // Initialize_index; needed by call to upper/lower_cover
319  // in first pass through state init_cover_iterator.
320 
321  _index = _anchor->index();
322 
323  // Mark the anchor as visited.
324 
325  put_has_visited(_index, true);
326 
327  // Now in the previsit position of _path_head, before the previsit action
328  // has been taken and before iteration over the cover has begun.
329 
330  _state = _transition_fcn[FIRST][PASS];
331 
332  next();
333 
334  enable_invariant_check();
335 
336  // Postconditions:
337 
338  ensure(invariant());
339 
340  // Exit
341 
342  return;
343 }
344 
345 template <typename T>
346 void
349 {
350 
351  // Preconditions:
352 
353  require(is_initialized());
354  require(anchor().state_is_read_write_accessible());
355  require(xmbr != 0);
356  require(xmbr->is_attached());
357  require(anchor().host()->contains_member(xmbr));
358 
359  // Body:
360 
361  put_has_visited(xmbr->index(), true);
362 
363  // Postconditions:
364 
365  ensure(has_visited(xmbr));
366 }
367 
368 template <typename T>
369 void
372 {
373  // Preconditions:
374 
375  require(is_initialized());
376  require(xmbr != 0);
377  require(xmbr->is_attached());
378  require(anchor().state_is_read_accessible());
379  require(anchor().host()->contains_member(xmbr));
380 
381  // Body:
382 
383  put_has_visited(xmbr->index(), false);
384 
385  // Postconditions:
386 
387  ensure(!has_visited(xmbr));
388 }
389 
390 template <typename T>
391 void
394 {
395  // Preconditions:
396 
397  // Body:
398 
399  // Empty in the class; intended for redefinition in descendants;
400 
401  // Postconditions:
402 
403  // Exit
404 
405  return;
406 }
407 
408 template <typename T>
409 void
412 {
413  // Preconditions:
414 
415  // Body:
416 
417  // Empty in the class; intended for redefinition in descendants;
418 
419  // Postconditions:
420 
421  // Exit
422 
423  return;
424 }
425 
426 template <typename T>
427 void
430 {
431  // Preconditions:
432 
433  // Body:
434 
435  _order = xorder;
436 
437  switch (_order)
438  {
439  case PREORDER :
440  _transition_fcn = PREORDER_TRANSITION_FCN;
441  break;
442  case POSTORDER :
443  _transition_fcn = POSTORDER_TRANSITION_FCN;
444  break;
445  case LINKORDER :
446  _transition_fcn = LINKORDER_TRANSITION_FCN;
447  break;
448  case BIORDER :
449  _transition_fcn = BIORDER_TRANSITION_FCN;
450  break;
451  case TRIORDER :
452  _transition_fcn = TRIORDER_TRANSITION_FCN;
453  break;
454  case NOT_AN_ORDER :
455  _transition_fcn = 0;
456  break;
457  }
458 
459  // Postconditions:
460 
461  ensure(order() == xorder);
462 
463  // Exit
464 
465  return;
466 }
467 
468 template <typename T>
469 void
472 {
473  // Preconditions:
474 
475  require(anchor_is_ancestor_of(xanchor));
476  require(xanchor.state_is_read_accessible());
477  require(is_done());
478 
479  // Body:
480 
481  define_old_variable(bool old_descending = _descending);
482  define_old_variable(bool old_strict = _strict);
483 
484  // Allocate anchor if needed and attach to
485  // the state and version of xanchor.
486 
487  initialize_anchor(xanchor);
488 
489  // (Re)allocate markers and initialize to false.
490 
491  initialize_has_visited(xanchor);
492 
493  // Initialize the filter
494 
495  initialize_filter(_anchor->version_index());
496 
497 #ifdef DIAGNOSTIC_OUTPUT
498 
499  cout << "in depth_first_itr<T>::initialize_traversal(xanchor): " << endl
500  << "_anchor = " << *_anchor << endl
501  << "_filter = " << _filter << endl;
502 #endif
503 
504  // Postconditions:
505 
506  ensure(invariant());
507  ensure(is_initialized());
508  ensure(is_done());
509  ensure(anchor().is_same_state(&xanchor));
510  ensure(anchor().is_same_type(&xanchor));
511  ensure(anchor().version() == xanchor.version());
512  ensure(filter().index() == anchor().version_index());
513  ensure(descending() == old_descending);
514  ensure(strict() == old_strict);
515 
516  // Exit
517 
518  return;
519 }
520 
521 template <typename T>
522 void
525 {
526  // Preconditions:
527 
528  require(is_initialized());
529  require(anchor().state_is_read_accessible());
530  require(anchor().host()->contains_member(xanchor_hub_id));
531  require(is_done());
532 
533  // Body:
534 
535  define_old_variable(bool old_descending = _descending);
536  define_old_variable(bool old_strict = _strict);
537  define_old_variable(scoped_index old_filter_index = filter().index());
538  define_old_variable(int old_anchor_version = anchor().version());
539 
540  // Set the anchor
541 
542  _anchor->attach_to_state(xanchor_hub_id);
543 
544  // Force the iterator to is_done so
545  // client must reset before using this.
546 
547  force_is_done();
548 
549 #ifdef DIAGNOSTIC_OUTPUT
550 
551  cout << "in depth_first_itr<T>::initialize_traversal(xanchor_hub_id): " << endl
552  << "_anchor = " << *_anchor << endl
553  << "_filter = " << *_filter << endl;
554 #endif
555 
556  // Postconditions:
557 
558  ensure(invariant());
559  ensure(is_initialized());
560  ensure(is_done());
561  ensure(anchor().index() == xanchor_hub_id);
562  ensure(anchor().version() == old_anchor_version);
563  ensure(filter().index() == old_filter_index);
564  ensure(descending() == old_descending);
565  ensure(strict() == old_strict);
566 
567  // Exit
568 
569  return;
570 }
571 
572 template <typename T>
573 void
576 {
577  // Preconditions:
578 
579  require(is_initialized());
580  require(anchor().state_is_read_accessible());
581  require(anchor().host()->contains_member(xanchor_id));
582  require(is_done());
583 
584  // Body:
585 
586  define_old_variable(bool old_descending = _descending);
587  define_old_variable(bool old_strict = _strict);
588  define_old_variable(scoped_index old_filter_index = filter().index());
589  define_old_variable(int old_anchor_version = anchor().version());
590 
591  initialize_traversal(xanchor_id.hub_pod());
592 
593  // Postconditions:
594 
595  ensure(invariant());
596  ensure(is_initialized());
597  ensure(is_done());
598  ensure(anchor().index() ==~ xanchor_id);
599  ensure(anchor().version() == old_anchor_version);
600  ensure(filter().index() == old_filter_index);
601  ensure(descending() == old_descending);
602  ensure(strict() == old_strict);
603 
604  // Exit
605 
606  return;
607 }
608 
609 template <typename T>
610 void
613 {
614  // Preconditions:
615 
616  require(anchor_is_ancestor_of(xanchor));
617  require(xanchor.state_is_read_accessible());
618  require(is_done());
619 
620  // Body:
621 
622  if(_anchor == 0)
623  {
624  _anchor = xanchor.clone();
625  }
626  else if(!_anchor->is_same_type(&xanchor))
627  {
628  release_cover_id_space_iterators();
629 
630  _anchor->detach_from_state();
631  delete _anchor;
632  _anchor = xanchor.clone();
633  }
634 
635  _anchor->attach_to_state(&xanchor);
636 
637  // Set _index to the member id space of _anchor.
638 
639  _index = _anchor->host()->member_id(false);
640  _greater_index = _index;
641  _lesser_index = _index;
642 
643  // Postconditions:
644 
645  // Can't use anchor() yet because it requres is_initialized().
646 
647  ensure(_anchor != 0);
648  ensure(_anchor->is_same_state(&xanchor));
649  ensure(_anchor->is_same_type(&xanchor));
650  ensure(is_done());
651 
652  // Exit
653 
654  return;
655 }
656 
657 template <typename T>
658 void
661 {
662  // Preconditions:
663 
664  require(xanchor.state_is_read_accessible());
665  require(is_done());
666 
667  // Body:
668 
669  is_abstract();
670 
671  // Postconditions:
672 
673  ensure(_has_visited != 0);
674  ensure(is_done());
675 
676  // Exit
677 
678  return;
679 
680 }
681 
682 template <typename T>
683 void
686 {
687  // Preconditions:
688 
689  require(_anchor != 0);
690  require(_anchor->state_is_read_accessible());
691  require(_client_filter.is_attached());
692  require(is_done());
693 
694  // Body:
695 
696  // First clean up any existing filter.
697 
698  // If this allocated the existing _filter, delete it.
699 
700  if(_new_filter)
701  delete _filter;
702 
703  _filter = 0;
704 
705  // Initialize the new filter.
706  // Iterator should traverse downset of the anchor, filtered by
707  // the intersection of _client_filter with the version filter associated
708  // with _anchor.version(). If _client_filter is the same as the version filter,
709  // or if the version filter is the same as the allocated filter (that is,
710  // the version is the coarsest common refinement and allocated members
711  // pass the filter) then we don't need to compute the intersection nor
712  // store the result, we can just use _client_filter._members().
713 
714  int lversion = _anchor->version();
715 
716  if(lversion == COARSEST_COMMON_REFINEMENT_VERSION)
717  {
718  // Version is CCR, use the client filter members as the traversal filter.
719 
720  _filter = _client_filter.members();
721  _new_filter = false;
722  }
723  else
724  {
725  poset_state_handle* lhost = _anchor->host();
726  pod_index_type lversion_index = lhost->version_index(lversion);
727  if(_client_filter.index() == lversion_index)
728  {
729  // Client filter is same as version filter;
730  // use the client filter members as the traversal filter.
731 
732  _filter = _client_filter.members();
733  _new_filter = false;
734  }
735  else
736  {
737  // Have to allocate a new traversal filter.
738 
739  _filter = new zn_to_bool(*(_client_filter.members()));
740  _new_filter = true;
741  _filter->b_and_sa(lhost->powerset().member(lversion_index).members());
742  }
743  }
744 
745  // Postconditions:
746 
747  ensure(_filter != 0);
748  ensure(is_done());
749 
750  // Exit
751 
752  return;
753 }
754 
755 template <typename T>
756 void
759 {
760  // Preconditions:
761 
762  require(_anchor != 0);
763  require(_anchor->state_is_read_accessible());
764  require(_anchor->host()->includes_subposet(&xfilter));
765  require(is_done());
766 
767  // Body:
768 
769  define_old_variable(bool old_descending = _descending);
770  define_old_variable(bool old_strict = _strict);
771 
772  _client_filter.attach_to_state(&xfilter);
773 
774  initialize_filter();
775 
776  // Postconditions:
777 
778  ensure(invariant());
779  ensure(_filter != 0);
780  ensure(_client_filter.is_same_state(&xfilter));
781  ensure(descending() == old_descending);
782  ensure(strict() == old_strict);
783  ensure(is_done());
784 
785 
786  // Exit
787 
788  return;
789 }
790 
791 template <typename T>
792 void
795 {
796  // Preconditions:
797 
798  require(_anchor != 0);
799  require(_anchor->state_is_read_accessible());
800  require(_anchor->host()->includes_subposet(xfilter_hub_id));
801  require(is_done());
802 
803  // Body:
804 
805  _client_filter.attach_to_state(_anchor->host(), xfilter_hub_id);
806 
807  initialize_filter();
808 
809  // Postconditions:
810 
811  ensure(_filter != 0);
812  ensure(_client_filter.index() == xfilter_hub_id);
813  ensure(is_done());
814 
815  // Exit
816 
817  return;
818 }
819 
820 template <typename T>
821 void
823 initialize_filter(const scoped_index& xfilter_id)
824 {
825  // Preconditions:
826 
827  require(_anchor != 0);
828  require(_anchor->state_is_read_accessible());
829  require(_anchor->host()->includes_subposet(xfilter_id));
830  require(is_done());
831 
832  // Body:
833 
834  initialize_filter(xfilter_id.hub_pod());
835 
836  // Postconditions:
837 
838  ensure(_filter != 0);
839  ensure(_client_filter.index() ==~ xfilter_id);
840  ensure(is_done());
841 
842  // Exit
843 
844  return;
845 }
846 
847 template <typename T>
848 void
850 initialize_filter(const std::string& xfilter_name)
851 {
852  // Preconditions:
853 
854  require(_anchor != 0);
855  require(_anchor->state_is_read_accessible());
856  require(!xfilter_name.empty() ?
857  _anchor->host()->includes_subposet(xfilter_name) :
858  true);
859  require(is_done());
860 
861  // Body:
862 
863  if(xfilter_name.empty())
864  {
865  _client_filter.attach_to_state(_anchor->host(), _anchor->version_name());
866  }
867  else
868  {
869  _client_filter.attach_to_state(_anchor->host(), xfilter_name);
870  }
871 
872  initialize_filter();
873 
874  // Postconditions:
875 
876  ensure(_filter != 0);
877  ensure(!xfilter_name.empty() ?
878  _client_filter.name() == xfilter_name :
879  _client_filter.name() == anchor().version_name());
880  ensure(is_done());
881 
882  // Exit
883 
884  return;
885 }
886 
887 template <typename T>
888 void
891 {
892  // Preconditions:
893 
894  // Body:
895 
896  if(_anchor != 0)
897  {
898  _anchor->host()->get_read_access();
899 
900  if(_path_head_lc != 0)
901  {
902  _anchor->host()->release_cover_id_space_iterator(*_path_head_lc);
903  _path_head_lc = 0;
904  }
905 
906  if(_path_head != 0)
907  {
908  _anchor->host()->release_cover_id_space_iterator(*_path_head);
909  _path_head = 0;
910  }
911 
912  while(!_path_tail.empty())
913  {
914  _anchor->host()->release_cover_id_space_iterator(*_path_tail.top());
915  _path_tail.pop();
916  }
917 
918  _anchor->host()->release_access();
919  }
920  else
921  {
923 
924  assertion(_path_head_lc == 0);
925  assertion(_path_head == 0);
926  assertion(_path_tail.empty());
927  }
928 
929  // Postconditions:
930 
931  ensure(_path_head_lc == 0);
932  ensure(_path_head == 0);
933  ensure(_path_tail.empty());
934 
935  // Exit:
936 
937  return;
938 }
939 
940 template <typename T>
941 const char*
943 iterator_state_names[NOT_A_STATE+1] =
944  {
945  "FIRST",
946  "INIT_COVER_ITERATOR",
947  "TEST_HAS_VISITED",
948  "INC_COVER_ITERATOR",
949  "ERASE_COVER_ITERATOR",
950  "DESCEND",
951  "TEST_PATH_TAIL",
952  "ASCEND",
953  "EXECUTE_PREVISIT_ACTION",
954  "EXECUTE_LINK_ACTION",
955  "EXECUTE_POSTVISIT_ACTION",
956  "FINISH",
957  "NOT_A_STATE"
958  };
959 
960 template <typename T>
963 PREORDER_TRANSITION_FCN[NOT_A_STATE-1][FAIL+1] =
964  {
965  // PASS, FAIL
966 
967  EXECUTE_PREVISIT_ACTION, EXECUTE_PREVISIT_ACTION, // FIRST
968  TEST_HAS_VISITED, TEST_PATH_TAIL, // INIT_COVER_ITERATOR
969  INC_COVER_ITERATOR, DESCEND, // TEST_HAS_VISITED
970  TEST_HAS_VISITED, TEST_PATH_TAIL, // INC_COVER_ITERATOR
971  NOT_A_STATE, NOT_A_STATE, // ERASE_COVER_ITERATOR
972  EXECUTE_PREVISIT_ACTION, EXECUTE_PREVISIT_ACTION, // DESCEND
973  FINISH, ASCEND, // TEST_PATH_TAIL
974  INC_COVER_ITERATOR, INC_COVER_ITERATOR, // ASCEND
975  INIT_COVER_ITERATOR, INIT_COVER_ITERATOR, // EXECUTE_PREVISIT_ACTION
976  NOT_A_STATE, NOT_A_STATE, // EXECUTE_LINK_ACTION,
977  NOT_A_STATE, NOT_A_STATE // EXECUTE_POSTVISIT_ACTION
978  };
979 
980 
981 template <typename T>
984 POSTORDER_TRANSITION_FCN[NOT_A_STATE-1][FAIL+1] =
985  {
986  // PASS, FAIL
987 
988  INIT_COVER_ITERATOR, INIT_COVER_ITERATOR, // FIRST
989  TEST_HAS_VISITED, EXECUTE_POSTVISIT_ACTION, // INIT_COVER_ITERATOR
990  INC_COVER_ITERATOR, DESCEND, // TEST_HAS_VISITED
991  TEST_HAS_VISITED, EXECUTE_POSTVISIT_ACTION, // INC_COVER_ITERATOR
992  NOT_A_STATE, NOT_A_STATE, // ERASE_COVER_ITERATOR
993  INIT_COVER_ITERATOR, INIT_COVER_ITERATOR, // DESCEND
994  FINISH, ASCEND, // TEST_PATH_TAIL
995  INC_COVER_ITERATOR, INC_COVER_ITERATOR, // ASCEND
996  NOT_A_STATE, NOT_A_STATE, // EXECUTE_PREVISIT_ACTION
997  NOT_A_STATE, NOT_A_STATE, // EXECUTE_LINK_ACTION,
998  TEST_PATH_TAIL, TEST_PATH_TAIL // EXECUTE_POSTVISIT_ACTION
999  };
1000 
1001 template <typename T>
1004 LINKORDER_TRANSITION_FCN[NOT_A_STATE-1][FAIL+1] =
1005  {
1006  // PASS, FAIL
1007 
1008  INIT_COVER_ITERATOR, INIT_COVER_ITERATOR, // FIRST
1009  TEST_HAS_VISITED, TEST_PATH_TAIL, // INIT_COVER_ITERATOR
1010  EXECUTE_LINK_ACTION, DESCEND, // TEST_HAS_VISITED
1011  TEST_HAS_VISITED, TEST_PATH_TAIL, // INC_COVER_ITERATOR
1012  TEST_HAS_VISITED, TEST_PATH_TAIL, // ERASE_COVER_ITERATOR
1013  INIT_COVER_ITERATOR, INIT_COVER_ITERATOR, // DESCEND
1014  FINISH, ASCEND, // TEST_PATH_TAIL
1015  EXECUTE_LINK_ACTION, EXECUTE_LINK_ACTION, // ASCEND
1016  NOT_A_STATE, NOT_A_STATE, // EXECUTE_PREVISIT_ACTION
1017  INC_COVER_ITERATOR, INC_COVER_ITERATOR, // EXECUTE_LINK_ACTION,
1018  NOT_A_STATE, NOT_A_STATE // EXECUTE_POSTVISIT_ACTION
1019  };
1020 
1021 template <typename T>
1024 BIORDER_TRANSITION_FCN[NOT_A_STATE-1][FAIL+1] =
1025  {
1026  // PASS, FAIL
1027 
1028  EXECUTE_PREVISIT_ACTION, EXECUTE_PREVISIT_ACTION, // FIRST
1029  TEST_HAS_VISITED, EXECUTE_POSTVISIT_ACTION, // INIT_COVER_ITERATOR
1030  INC_COVER_ITERATOR, DESCEND, // TEST_HAS_VISITED
1031  TEST_HAS_VISITED, EXECUTE_POSTVISIT_ACTION, // INC_COVER_ITERATOR
1032  NOT_A_STATE, NOT_A_STATE, // ERASE_COVER_ITERATOR
1033  EXECUTE_PREVISIT_ACTION, EXECUTE_PREVISIT_ACTION, // DESCEND
1034  FINISH, ASCEND, // TEST_PATH_TAIL
1035  INC_COVER_ITERATOR, INC_COVER_ITERATOR, // ASCEND
1036  INIT_COVER_ITERATOR, INIT_COVER_ITERATOR, // EXECUTE_PREVISIT_ACTION
1037  NOT_A_STATE, NOT_A_STATE, // EXECUTE_LINK_ACTION,
1038  TEST_PATH_TAIL, TEST_PATH_TAIL // EXECUTE_POSTVISIT_ACTION
1039  };
1040 
1041 template <typename T>
1044 TRIORDER_TRANSITION_FCN[NOT_A_STATE-1][FAIL+1] =
1045  {
1046  // PASS, FAIL
1047 
1048  EXECUTE_PREVISIT_ACTION, EXECUTE_PREVISIT_ACTION, // FIRST
1049  TEST_HAS_VISITED, EXECUTE_POSTVISIT_ACTION, // INIT_COVER_ITERATOR
1050  EXECUTE_LINK_ACTION, DESCEND, // TEST_HAS_VISITED
1051  TEST_HAS_VISITED, EXECUTE_POSTVISIT_ACTION, // INC_COVER_ITERATOR
1052  TEST_HAS_VISITED, EXECUTE_POSTVISIT_ACTION, // ERASE_COVER_ITERATOR
1053  EXECUTE_PREVISIT_ACTION, EXECUTE_PREVISIT_ACTION, // DESCEND
1054  FINISH, ASCEND, // TEST_PATH_TAIL
1055  EXECUTE_LINK_ACTION, EXECUTE_LINK_ACTION, // ASCEND
1056  INIT_COVER_ITERATOR, INIT_COVER_ITERATOR, // EXECUTE_PREVISIT_ACTION
1057  INC_COVER_ITERATOR, INC_COVER_ITERATOR, // EXECUTE_LINK_ACTION,
1058  TEST_PATH_TAIL, TEST_PATH_TAIL // EXECUTE_POSTVISIT_ACTION
1059  };
1060 
1061 // PRIVATE MEMBER FUNCTIONS
1062 
1063 
1064 // ===========================================================
1065 // ITERATOR FACET
1066 // ===========================================================
1067 
1068 // PUBLIC MEMBER FUNCTIONS
1069 
1070 template <typename T>
1073 order() const
1074 {
1075  order_type result;
1076 
1077  // Preconditions:
1078 
1079  // Body:
1080 
1081  result = _order;
1082 
1083  // Postconditions:
1084 
1085  // Exit
1086 
1087  return result;
1088 }
1089 
1090 template <typename T>
1091 bool
1094 {
1095  bool result;
1096 
1097  // Preconditions:
1098 
1099  // Body:
1100 
1101  result = (_anchor != 0) && (_has_visited != 0) && (_filter != 0);
1102 
1103  // Postconditions:
1104 
1105  // Exit
1106 
1107  return result;
1108 }
1109 
1110 template <typename T>
1114 {
1115  // Preconditions:
1116 
1117  require(is_initialized());
1118 
1119  // Body:
1120 
1121  abstract_poset_member& result = *_anchor;
1122 
1123  // Postconditions:
1124 
1125  // Exit
1126 
1127  return result;
1128 }
1129 
1130 template <typename T>
1131 const abstract_poset_member&
1133 anchor() const
1134 {
1135  // Preconditions:
1136 
1137  require(is_initialized());
1138 
1139  // Body:
1140 
1141  abstract_poset_member& result = *_anchor;
1142 
1143  // Postconditions:
1144 
1145  // Exit
1146 
1147  return result;
1148 }
1149 
1150 template <typename T>
1151 bool
1154 {
1155  bool result;
1156 
1157  // Preconditions:
1158 
1159  // Body:
1160 
1161  // Always true in this class;
1162  // intended to be redefined in descendants.
1163 
1164  result = true;
1165 
1166  // Postconditions:
1167 
1168  // Exit
1169 
1170  return result;
1171 }
1172 
1173 template <typename T>
1174 bool
1176 descending() const
1177 {
1178  bool result;
1179 
1180  // Preconditions:
1181 
1182  // Body:
1183 
1184  result = _descending;
1185 
1186  // Postconditions:
1187 
1188  // Exit
1189 
1190  return result;
1191 }
1192 
1193 template <typename T>
1194 bool
1196 strict() const
1197 {
1198  bool result;
1199 
1200  // Preconditions:
1201 
1202  // Body:
1203 
1204  result = _strict;
1205 
1206  // Postconditions:
1207 
1208  // Exit
1209 
1210  return result;
1211 }
1212 
1213 template <typename T>
1214 subposet&
1217 {
1218  // Preconditions:
1219 
1220  // The following precondition is stronger than necessary for
1221  // this routine alone, but is consistent with the preconditions for
1222  // anchor() and has_visited() and hence easier for the client to understand.
1223 
1224  require(is_initialized());
1225 
1226  // Body:
1227 
1228  subposet& result = _client_filter;
1229 
1230  // Postconditions:
1231 
1232  ensure(is_initialized() == result.is_attached());
1233 
1234  // Exit
1235 
1236  return result;
1237 }
1238 
1239 template <typename T>
1240 bool
1242 is_done() const
1243 {
1244  bool result;
1245 
1246  // Preconditions:
1247 
1248  // Body:
1249 
1250  result = (_state == NOT_A_STATE);
1251 
1252  // Postconditions:
1253 
1254  // Exit
1255 
1256  return result;
1257 }
1258 
1259 template <typename T>
1260 void
1263 {
1264  // Preconditions:
1265 
1266  // Body:
1267 
1268  _index.invalidate();
1269 
1270  _action = NOT_AN_ACTION;
1271  _state = NOT_A_STATE;
1272 
1273  // Clear the path
1274 
1275  release_cover_id_space_iterators();
1276 
1277  // Clear the filtered path
1278 
1279  while(!_filtered_path_tail.empty())
1280  {
1281  _filtered_path_tail.pop();
1282  }
1283 
1284  // Postconditions:
1285 
1286  ensure(invariant());
1287  ensure(is_done());
1288 
1289  // Exit:
1290 }
1291 
1292 template <typename T>
1293 void
1295 next(bool xtruncate)
1296 {
1297  // Preconditions:
1298 
1299  require(!is_done());
1300 
1301  // Body:
1302 
1303  pod_index_type lc_index;
1304 
1305  // The following while/switch construction is a finite state machine.
1306  // Each case in the switch corresponds to a state. In each state, an
1307  // action is performed and the result of the action determines the
1308  // "input token" of the finite state machine. The transition to the
1309  // next state is determined by the transitition function, implemented
1310  // as an array indexed by state and token.
1311  //
1312  // Control enters the while with _state set to some value. Each iteration
1313  // of the loop corresponds to a state transition. Iteration continues
1314  // until a state is reached which returns to the caller.
1315 
1323 
1324  while(true)
1325  {
1326 
1327 #ifdef DIAGNOSTIC_OUTPUT
1328  cout << "in depth_first_itr<T>::next: _state = " << iterator_state_names[_state];
1329  if(is_initialized())
1330  {
1331  cout << "\t\t_filtered_path_tail: " << _filtered_path_tail.top();
1332  cout << "\t _index: " << _index;
1333  }
1334  cout << endl;
1335 #endif
1336 
1337  switch(_state)
1338  {
1339  case INIT_COVER_ITERATOR:
1340 
1341  // Initialize the cover iterator, depending on truncation and direction.
1342 
1343  if(_path_head_lc != 0)
1344  {
1345  _anchor->host()->release_cover_id_space_iterator(*_path_head_lc);
1346  }
1347 
1348  _path_head_lc = &_anchor->host()->get_cover_id_space_iterator(_descending, _index);
1349 
1350  if(xtruncate)
1351  {
1352  // Truncation requested; initialize the iterator to end.
1353  // Cover of this will be skipped.
1354 
1355  _path_head_lc->force_is_done();
1356 
1357  // Client has only requested truncation for the current member.
1358  // If we pass thorugh this state again, we don't want to truncate.
1359 
1360  xtruncate = false;
1361  }
1362 
1363  // Test the cover iterator to see if there is a current member of the cover.
1364 
1365  if(!_path_head_lc->is_done())
1366  {
1367  // Cover iterator points to the current member of cover;
1368  // Now there is a link defined. _index and _path_head refer to
1369  // the greater member and _path_head_lc refers to the lesser member.
1370 
1371  // Check to see if lesser has already been visited.
1372 
1373  _state = _transition_fcn[INIT_COVER_ITERATOR][PASS];
1374  }
1375  else
1376  {
1377  // Cover iterator is finished; we've visited all the cover.
1378  // There is no current link, we're in the postvisit action position.
1379 
1380  _state = _transition_fcn[INIT_COVER_ITERATOR][FAIL];
1381  }
1382 
1383  break;
1384 
1385  case TEST_HAS_VISITED:
1386 
1387  // Check to see if we've already visited the
1388  // current member of the cover.
1389 
1390  lc_index = _path_head_lc->hub_pod();
1391 
1392  if(_visit_once && has_visited(lc_index))
1393  {
1394  // Current member of cover has been visited and we're only visiting once;
1395  // execute the link action then move on to the next member.
1396 
1397  _state = _transition_fcn[TEST_HAS_VISITED][PASS];
1398  }
1399  else
1400  {
1401  // Current member hasn't been visited or
1402  // we're visiting more than once; descend
1403 
1404  _state = _transition_fcn[TEST_HAS_VISITED][FAIL];
1405  }
1406  break;
1407 
1408  case INC_COVER_ITERATOR:
1409 
1410  // Move on to the next member of the cover.
1411 
1412  _path_head_lc->next();
1413 
1414  // Test the cover iterator to see if there is a current member of the cover.
1415 
1416  if(!_path_head_lc->is_done())
1417  {
1418  // Cover iterator points to the current member of cover;
1419  // check to see if it has already been visited.
1420 
1421  _state = _transition_fcn[INC_COVER_ITERATOR][PASS];
1422  }
1423  else
1424  {
1425  // Cover iterator is finished; we've visited all the cover;
1426  // the iterator is is in the postvisit action position.
1427 
1428  _state = _transition_fcn[INC_COVER_ITERATOR][FAIL];
1429  }
1430 
1431  break;
1432 
1433  case ERASE_COVER_ITERATOR:
1434 
1435  // Erase the current member of cover and move on,
1436  // without trashing the iterator.
1437 
1438  {
1439  // Local scope to avoid compiler complaint about
1440  // "jump to case label crosses initialization" of ltmp_itr.
1441 
1442 
1443 #ifdef DIAGNOSTIC_OUTPUT
1444  cout << "in depth_first_itr<T>::next::ERASE_COVER_ITERATOR "
1445  << "erasing " << _path_head_lc->hub_pod()
1446  << " in cover of " << _path_head
1447  << endl;
1448 #endif
1449 
1450  pod_index_type litem = _path_head_lc->hub_pod();
1451  _path_head_lc->next();
1452  _anchor->host()->clear_cover(_descending, litem);
1453  }
1454 
1455 
1456  // Test the cover iterator to see if there is a current member of the cover.
1457 
1458  if(!_path_head_lc->is_done())
1459  {
1460  // Cover iterator points to the current member of cover;
1461  // check to see if it has already been visited.
1462 
1463  _state = _transition_fcn[ERASE_COVER_ITERATOR][PASS];
1464  }
1465  else
1466  {
1467  // Cover iterator is finished; we've visited all the cover;
1468  // the iterator is is in the postvisit action position.
1469 
1470  _state = _transition_fcn[ERASE_COVER_ITERATOR][FAIL];
1471  }
1472 
1473  break;
1474 
1475  case DESCEND:
1476 
1477  // Mark the current member of cover.
1478 
1479  lc_index = _path_head_lc->hub_pod();
1480 
1481  put_has_visited(lc_index, true);
1482 
1483  // Descend.
1484 
1485  if(_index !=~ _anchor->index())
1486  {
1487  assertion(_index.pod() == _path_head->hub_pod());
1488 
1489  _path_tail.push(_path_head);
1490 
1491  // Update the greater end of the link.
1492 
1493  if(filter(_path_head->hub_pod()))
1494  {
1495  _filtered_path_tail.push(_path_head->hub_pod());
1496  }
1497  }
1498 
1499  _path_head = _path_head_lc;
1500  _path_head_lc = 0;
1501  _index = lc_index;
1502 
1503  // This is the first time we've seend this node and we're
1504  // about to begin iteration over its cover.
1505  // This is the previsit action position.
1506 
1507  _state = _transition_fcn[DESCEND][PASS];
1508 
1509  break;
1510 
1511  case TEST_PATH_TAIL:
1512 
1513  // Test the path tail to see whether we can ascend or
1514  // we're done.
1515 
1516  if(_index == _anchor->index())
1517  {
1518  // Tail of path is empty;
1519  // _path_head is anchor;
1520  // iteration is over.
1521 
1522  _state = _transition_fcn[TEST_PATH_TAIL][PASS];
1523  }
1524  else
1525  {
1526  // Tail of path is not empty; ascend.
1527 
1528  _state = _transition_fcn[TEST_PATH_TAIL][FAIL];
1529  }
1530 
1531  break;
1532 
1533  case ASCEND:
1534 
1535  // Release the path head lower cover.
1536 
1537  _anchor->host()->release_cover_id_space_iterator(*_path_head_lc);
1538 
1539  _path_head_lc = 0;
1540 
1541  if(_path_tail.empty())
1542  {
1543  // Assend to the anchor.
1544 
1545  _path_head_lc = _path_head;
1546  _path_head = 0;
1547 
1548  // Attach this to the anchor.
1549 
1550  _index = _anchor->index();
1551  }
1552  else
1553  {
1554  // Ascend to the previous link in the path
1555 
1556  _path_head_lc = _path_head;
1557 
1558  // Update the greater end of the link;
1559 
1560  if(!_filtered_path_tail.empty() &&
1561  (_filtered_path_tail.top() == _path_tail.top()->hub_pod()))
1562  {
1563  // Filtered path can not be empty at this point.
1564 
1565  assertion(!_filtered_path_tail.empty());
1566  _filtered_path_tail.pop();
1567  }
1568 
1569  _path_head = _path_tail.top();
1570  _path_tail.pop();
1571 
1572  // Attach this to the lesser member of the current link
1573 
1574  _index = _path_head->hub_pod();
1575  }
1576 
1577  // We have just ascended from visiting
1578  // the lesser member of the link.
1579  // This is the link action position;
1580 
1581  _state = _transition_fcn[ASCEND][PASS];
1582 
1583  break;
1584 
1585  case EXECUTE_PREVISIT_ACTION:
1586 
1587  // Only execute the action if the current member passes the filter.
1588 
1593 
1594  //cout << "_index: "<< _index << endl;
1595 
1596  if(filter(_index) && (!_strict || !(_index == _anchor->index())) )
1597  {
1598  // Current member passes the filter, attach and
1599  // return to client for previsit action. When client
1600  // returns control, initialize iteration over this members cover.
1601 
1602  attach_item();
1603 
1604  //cout << "PASS" << endl;
1605 
1606  _state = _transition_fcn[EXECUTE_PREVISIT_ACTION][PASS];
1607  _action = PREVISIT_ACTION;
1608 
1609  return;
1610  }
1611  else
1612  {
1613  // Current member doesn't pass the filter;
1614  // skip the previsit action and go directly to
1615  // initializing iteration over this members cover.
1616 
1617  //cout << "FAIL" << endl;
1618 
1619  _state = _transition_fcn[EXECUTE_PREVISIT_ACTION][FAIL];
1620  }
1621 
1622  break;
1623 
1624  case EXECUTE_LINK_ACTION:
1625 
1626 #ifdef DIAGNOSTIC_OUTPUT
1627 
1628  cout << "\t\t*_path_head_lc: " << _path_head_lc->hub_pod() << endl;
1629 #endif
1630 
1631  // Only execute the link action if the current member passes the filter.
1632 
1633  if( filter(_index) && (!_strict || !(_index == _anchor->index())) )
1634  {
1635  // Current member passes the filter, attach and
1636  // return to client for postvisit action. When client
1637  // returns control, increment the cover iterator.
1638 
1639  attach_item();
1640 
1641  _state = _transition_fcn[EXECUTE_LINK_ACTION][PASS];
1642  _action = LINK_ACTION;
1643 
1644  return;
1645  }
1646  else
1647  {
1648  // Current member doesn't pass the filter;
1649  // skip the link action and go directly to
1650  // incrementing the cover iterator.
1651 
1652  _state = _transition_fcn[EXECUTE_LINK_ACTION][FAIL];
1653  }
1654 
1655  break;
1656 
1657  case EXECUTE_POSTVISIT_ACTION:
1658 
1659  // Only execute the action if the current member passes the filter.
1660 
1662 
1663  if( filter(_index) && (!_strict || !(_index == _anchor->index())) )
1664  {
1665  // Current member passes the filter, attach and
1666  // return to client for postvisit action. When client
1667  // returns control, test the path to see if we can ascend.
1668 
1669  attach_item();
1670 
1671  _state = _transition_fcn[EXECUTE_POSTVISIT_ACTION][PASS];
1672  _action = POSTVISIT_ACTION;
1673 
1674  return;
1675  }
1676  else
1677  {
1678  // Current member doesn't pass the filter;
1679  // skip the postvisit action and go directly to
1680  // testing the path to see if we can ascend.
1681 
1682  _state = _transition_fcn[EXECUTE_POSTVISIT_ACTION][FAIL];
1683  }
1684 
1685  break;
1686 
1687  case FINISH:
1688 
1689  // Iteration is over.
1690 
1691  _index.invalidate();
1692 
1693  detach_item();
1694 
1695  _state = NOT_A_STATE;
1696  _action = NOT_AN_ACTION;
1697 
1698  return;
1699  }
1700  }
1701 
1702  // Postconditions:
1703 
1706 
1707  // ensure(invariant());
1708 
1709  // Exit
1710 
1711  // return;
1712 }
1713 
1714 template <typename T>
1715 void
1717 reset(bool xreset_markers)
1718 {
1719  // Preconditions:
1720 
1721  require(is_initialized());
1722  require(anchor().state_is_read_accessible());
1723 
1724  // Body:
1725 
1726  define_old_variable(bool old_descending = _descending);
1727  define_old_variable(bool old_strict = _strict);
1728 
1729  // Force the iteration into a clean state.
1730 
1731  force_is_done();
1732 
1733  // Reset the markers as requested.
1734 
1735  if(xreset_markers)
1736  clear_has_visited();
1737 
1738  // Advance to the first item in the iteration
1739 
1740  first();
1741 
1742  // Postconditions:
1743 
1744  ensure(invariant());
1745  ensure(descending() == old_descending);
1746  ensure(strict() == old_strict);
1747 
1753 
1754 
1755  // Exit
1756 
1757  return;
1758 }
1759 
1760 template <typename T>
1761 int
1763 ct(bool xreset)
1764 {
1765  int result = 0;
1766 
1767  // Preconditions:
1768 
1769  require(is_initialized());
1770  require(xreset ? anchor().state_is_read_accessible(): true);
1771 
1772  // Body:
1773 
1774  if(xreset)
1775  reset();
1776 
1777  while(!is_done())
1778  {
1779  result++;
1780  next();
1781  }
1782 
1783  // Postconditions:
1784 
1785  ensure(result >= 0);
1786  ensure(is_done());
1787 
1788  // Exit
1789 
1790  return result;
1791 }
1792 
1793 template <typename T>
1794 void
1797 {
1798 
1799  // Preconditions:
1800 
1801  // Body:
1802 
1803  is_abstract();
1804 
1805  // Postconditions:
1806 
1807  // Exit
1808 
1809  return;
1810 }
1811 
1812 template <typename T>
1813 void
1816 {
1817  // Preconditions:
1818 
1819  // Body:
1820 
1821  is_abstract();
1822 
1823  // Postconditions:
1824 
1825  // Exit
1826 
1827  return;
1828 }
1829 
1830 template <typename T>
1831 bool
1834 {
1835  bool result = false; // Just to silence the compiler.
1836 
1837  // Preconditions:
1838 
1839  require(is_initialized());
1840  require(anchor().state_is_read_accessible());
1841  require(anchor().host()->contains_member(xhub_id));
1842 
1843  // Body:
1844 
1845  is_abstract();
1846 
1847  // Postconditions:
1848 
1849  // Exit
1850 
1851  return result;
1852 }
1853 
1854 template <typename T>
1855 bool
1857 has_visited(const scoped_index& xid) const
1858 {
1859  // Preconditions:
1860 
1861  require(is_initialized());
1862  require(anchor().state_is_read_accessible());
1863  require(anchor().host()->contains_member(xid));
1864 
1865  // Body:
1866 
1867  return has_visited(xid.hub_pod());
1868 }
1869 
1870 template <typename T>
1871 bool
1874 {
1875  // Preconditions:
1876 
1877  require(is_initialized());
1878  require(anchor().state_is_read_accessible());
1879  require(xmbr != 0);
1880  require(xmbr->is_attached());
1881  require(anchor().host()->is_same_state(xmbr->host()));
1882 
1883  // Body:
1884 
1885  return has_visited(xmbr->index().hub_pod());
1886 }
1887 
1888 template <typename T>
1889 void
1891 put_has_visited(pod_index_type xhub_id, bool xvalue)
1892 {
1893  // Preconditions:
1894 
1895  require(is_initialized());
1896  require(anchor().state_is_read_accessible());
1897  require(anchor().host()->contains_member(xhub_id));
1898 
1899  // Body:
1900 
1901  not_implemented();
1902 
1903  // Postconditions:
1904 
1905  ensure(has_visited(xhub_id) == xvalue);
1906 
1907  // Exit
1908 
1909  return;
1910 }
1911 
1912 template <typename T>
1913 void
1915 put_has_visited(const scoped_index& xid, bool xvalue)
1916 {
1917  // Preconditions:
1918 
1919  require(is_initialized());
1920  require(anchor().state_is_read_accessible());
1921  require(anchor().host()->contains_member(xid));
1922 
1923  // Body:
1924 
1925  put_has_visited(xid.hub_pod(), xvalue);
1926 
1927  // Postconditions:
1928 
1929  ensure(has_visited(xid) == xvalue);
1930 
1931  // Exit
1932 
1933  return;
1934 }
1935 
1936 template <typename T>
1937 bool
1939 visit_once() const
1940 {
1941  return _visit_once;
1942 }
1943 
1944 template <typename T>
1945 void
1947 put_visit_once(bool xvisit_once)
1948 {
1949  // Preconditions:
1950 
1951  // Body:
1952 
1953  _visit_once = xvisit_once;
1954 
1955  // Postconditions:
1956 
1957  ensure(visit_once() == xvisit_once);
1958 
1959  // Exit:
1960 
1961  return;
1962 }
1963 
1964 template <typename T>
1965 bool
1968 {
1969  bool result;
1970 
1971  // Preconditions:
1972 
1973  require(is_initialized());
1974 
1975  // Body:
1976 
1977  result = !greater_index().is_valid();
1978 
1979  // Postconditions:
1980 
1981  ensure(result == !greater_index().is_valid());
1982 
1983  // Exit
1984 
1985  return result;
1986 }
1987 
1988 template <typename T>
1989 const scoped_index&
1992 {
1993  // Preconditions:
1994 
1995  require(is_initialized());
1996  require(!is_done());
1997 
1998  // Body:
1999 
2000  _greater_index =
2001  (_action == LINK_ACTION) ? _index.pod() :
2002  (_filtered_path_tail.empty() ? invalid_pod_index() : _filtered_path_tail.top());
2003 
2004  // Postconditions:
2005 
2006  // Exit
2007 
2008  return _greater_index;
2009 }
2010 
2011 template <typename T>
2012 const sheaf::scoped_index&
2015 {
2016  // Preconditions:
2017 
2018  require(is_initialized());
2019  require(!is_done());
2020 
2021  // Body:
2022 
2029 
2030  _lesser_index = (_action == LINK_ACTION) ? _path_head_lc->hub_pod() : _index.pod();
2031 
2032  // Postconditions:
2033 
2034  // Exit
2035 
2036  return _lesser_index;
2037 }
2038 
2039 template <typename T>
2042 action() const
2043 {
2044  action_type result;
2045 
2046  // Preconditions:
2047 
2048  // Body:
2049 
2050  result = _action;
2051 
2052  // Postconditions:
2053 
2054  // Exit
2055 
2056  return result;
2057 }
2058 
2059 template <typename T>
2060 void
2063 {
2064  // Preconditions:
2065 
2066  require(action() == LINK_ACTION);
2067 
2068  // Body:
2069 
2070  _state = ERASE_COVER_ITERATOR;
2071 
2072  // Postconditions:
2073 
2074  // Exit:
2075 
2076  return;
2077 }
2078 
2079 // PROTECTED MEMBER FUNCTIONS
2080 
2081 // PRIVATE MEMBER FUNCTIONS
2082 
2083 
2084 // ===========================================================
2085 // INDEX ITERATOR FACET
2086 // ===========================================================
2087 
2088 // PUBLIC MEMBER FUNCTIONS
2089 
2090 template <typename T>
2091 const sheaf::scoped_index&
2093 index() const
2094 {
2095  // Preconditions:
2096 
2097  require(!is_done());
2098 
2099  // Body:
2100 
2101  const scoped_index& result = _index;
2102 
2103  // Postconditions:
2104 
2105  ensure( (action() == LINK_ACTION) ? (result == greater_index()) : (result == lesser_index()) );
2106 
2107  // Exit
2108 
2109  return result;
2110 }
2111 
2112 template <typename T>
2113 size_t
2116 {
2117  int result;
2118 
2119  // Preconditions:
2120 
2121  require(!is_done());
2122 
2123  // Body:
2124 
2125  result = _path_tail.size();
2126 
2127  // Postconditions:
2128 
2129  // Exit:
2130 
2131  return result;
2132 }
2133 
2134 // PROTECTED MEMBER FUNCTIONS
2135 
2136 // PRIVATE MEMBER FUNCTIONS
2137 
2138 
2139 // ===========================================================
2140 // ANY FACET
2141 // ===========================================================
2142 
2143 // PUBLIC MEMBER FUNCTIONS
2144 
2145 template <typename T>
2146 bool
2148 is_ancestor_of(const any* xother) const
2149 {
2150  bool result;
2151 
2152  // Preconditions:
2153 
2154  // Body:
2155 
2156  result = dynamic_cast<const depth_first_itr*>(xother) != 0;
2157 
2158  // Postconditions:
2159 
2160  // Exit
2161 
2162  return result;
2163 }
2164 
2165 template <typename T>
2168 clone() const
2169 {
2170  depth_first_itr* result;
2171 
2172  // Preconditions:
2173 
2174  // Body:
2175 
2176  result = new depth_first_itr;
2177 
2178  // Postconditions:
2179 
2180  ensure(result != 0);
2181  ensure(!result->is_initialized());
2182 
2183  // Exit
2184 
2185  return result;
2186 }
2187 
2188 template <typename T>
2189 bool
2191 invariant() const
2192 {
2193  bool result = true;
2194 
2195  // Preconditions:
2196 
2197  // Body:
2198 
2199  invariance(any::invariant());
2200 
2201  if(invariant_check())
2202  {
2203  disable_invariant_check();
2204 
2205  invariance( is_initialized() ? order() != NOT_AN_ORDER : true);
2206  invariance( !is_initialized() ? is_done() : true);
2207  invariance( is_initialized() ? anchor().is_attached() == (_has_visited != 0) : true );
2208  invariance( is_initialized() == (_has_visited != 0));
2209 
2210  // The following apparent "invariance" is in fact not true when the graph
2211  // is being modified behind the current position of the iterator.
2212  // invariance( is_initialized() ? (_has_visited->ub() == anchor().host()->member_index_ub()) : true );
2213 
2216 
2217  //invariance( is_initialized() && !is_done() ? index() == _path_head.item() : true);
2218  invariance( (action() == NOT_AN_ACTION) == is_done() );
2219  invariance( (_state == NOT_A_STATE) == is_done() );
2220  invariance( _new_filter ? _filter != 0 : true );
2221  invariance( is_initialized() == (_anchor != 0) );
2222  invariance( !is_initialized() ? !_new_filter : true );
2223 
2224 
2225  // Finished, turn invariant checking back on.
2226 
2227  enable_invariant_check();
2228  }
2229 
2230  // Postconditions:
2231 
2232  // Exit
2233 
2234  return result;
2235 }
2236 
2237 // PROTECTED MEMBER FUNCTIONS
2238 
2239 // PRIVATE MEMBER FUNCTIONS
2240 
2241 
2242 // ===========================================================
2243 // NON-MEMBER FUNCTIONS FACET
2244 // ===========================================================
2245 
2246 } // namespace sheaf
2247 
action_type
The types of action a client should take when the iterator returns control to the client...
virtual bool invariant() const
Class invariant, intended to be redefined in each descendant. See below for template for invariant in...
Definition: any.cc:153
void clear_has_visited()
Makes has_visited(i) false for all i.
void put_has_visited(pod_index_type xhub_id, bool xvalue)
Set the visited marker for hub id xhub_id to xvalue. Intended for use reseting iterator without havin...
poset_state_handle * host() const
The poset which this is a handle to a component of.
virtual void initialize_has_visited(const abstract_poset_member &xanchor)
Initializes the has_visited markers.
A client handle for a subposet.
Definition: subposet.h:86
zn_to_bool * members() const
Get the members of the subposet.
virtual abstract_poset_member & anchor()
The poset member whose downset is being iterated over; the top member of the domain of iteration...
size_t depth()
The length of the path from anchor() to the current member.
virtual void detach_item()
Detaches the item handle to the current index. Empty in this class; intended for redefinition in desc...
virtual void reset(bool xreset_markers=true)
Restarts the iteration over the down set of anchor().
bool is_done() const
True if iteration finished.
order_type
The types of order in which the iterator will visit the members of the poset. Determines which action...
virtual bool is_ancestor_of(const any *other) const
True if other conforms to this.
int version(bool xunalias=true) const
The (possibly aliased) version of this component. The version of the host used when evaluating proper...
bool has_visited(pod_index_type xhub_id) const
True if this has already visited member with hub id xhub_id.
void initialize_order(order_type xorder)
Initializes _order and _transition_fcn.
void initialize_filter()
Initializes the filter subposet from the client filter.
bool state_is_read_accessible() const
True if this is attached and if the state is accessible for read or access control is disabled...
bool _descending
True if iterating over the up/down set of anchor.
order_type order() const
The order of the iteration. Determines which actions are exported to the client.
bool invariant() const
The class invariant.
A client handle for a general, abstract partially order set.
bool filter(pod_index_type xhub_id)
The value of the filter at hub id xhub_id.
int ct(bool xreset=false)
The number of members of the iteration set, from the current member to the end, inclusive. If xreset, reset before computing the count.
const scoped_index & greater_index() const
The index of the greater member of the current link.
const scoped_index & index() const
The index of the component state this handle is attached to.
iterator_state
The states for the finite state machine that controls iteration.
namespace_poset * host() const
The namespace this poset resides in. Obsolete; use name_space() instead.
depth_first_itr()
Default constructor; creates an unattached iterator,.
virtual depth_first_itr * clone() const
Make a new instance of the same type as this.
const scoped_index & index() const
The index of the current member of the iteration.
action_type action() const
The type of action the client should take when the iterator returns control to the client...
void reserve_has_visited(pod_index_type xub)
Ensures has_visited(i) is a legal call for 0 <= i < xub.
Abstract base class with useful features for all objects.
Definition: any.h:39
A map from Zn (the integers mod n) to bools. A characteristic function used to represent subsets of Z...
Definition: zn_to_bool.h:52
virtual void force_is_done()
Force the iterator to be done.
bool visit_once() const
True if traversal should only visit a member once; that is, it should not revisit members it has alre...
The general depth-first iterator over the intersection of a poset member anchor&#39;s whole with its down...
virtual pod_index_type version_index(int xversion) const
The subposet hub id of the whole() subposet for version xversion.
bool _visit_once
True if traversal should only visit a member once; that is, it should not revisit members it has alre...
void initialize_traversal(const abstract_poset_member &xanchor)
Initializes the anchor, has_visited markers and filter.
An index within the external ("client") scope of a given id space.
Definition: scoped_index.h:116
virtual bool is_attached() const
True if this handle is attached to a non-void state.
bool strict() const
True if iterating over xstrict up/down set of anchor.
void mark_not_visited(abstract_poset_member *xmbr)
Mark xmbr as not visited. Warning: this function can change the state of the iteration in unpredictab...
void initialize_anchor(const abstract_poset_member &xanchor)
Initializes the anchor.
void mark_visited(abstract_poset_member *xmbr)
Mark xmbr as visited. Warning: this function can change the state of the iteration in unpredictable w...
subposet & filter()
The subposet which is the filter; Defines what is passed, not what is blocked.
virtual bool anchor_is_ancestor_of(const abstract_poset_member &xmbr) const
True if xmbr conforms to the type of anchor of this.
depth_first_itr & operator=(const depth_first_itr &xother)
Assignment operator.
virtual void attach_item()
Attaches the item handle to the current index. Empty in this class; intended for redefinition in desc...
abstract_poset_member * clone(bool xnew_state, bool xauto_access=true) const
Virtual constructor; makes a new handle of the same type as this, attached to a new state (xnew_state...
const bool NO_RESET
Iteration marker reset control.
Definition: sheaf.h:92
void release_cover_id_space_iterators()
Release the cover iterators back to the pool of iterators.
void next()
Makes this the next member of the subset.
virtual ~depth_first_itr()
Destructor.
void put_visit_once(bool xvisit_once)
Set visit_once() to xvisit_once.
int_type pod_index_type
The plain old data index type.
Definition: pod_types.h:49
Namespace for the sheaves component of the sheaf system.
bool is_maximal()
True if the current member has no greater member within the subposet visited by this iterator...
subposet_state & member(pod_index_type xindex)
The subposet with index xindex (mutable version).
void attach_to_state(const namespace_poset *xns, const poset_path &xpath, bool xauto_access=true)
Attach to the state specified by path xpath in the namespace xns.
const scoped_index & lesser_index() const
The index of the lesser member of the current link.
void first()
Moves this to the first member of the iteration.
An abstract client handle for a member of a poset.
virtual bool is_initialized() const
True if this has been initialized for iteration with respect to a specific anchor.
SHEAF_DLL_SPEC bool is_valid(pod_index_type xpod_index)
True if an only if xpod_index is valid.
Definition: pod_types.cc:37
bool descending() const
True if iterating over down set of anchor.
SHEAF_DLL_SPEC pod_index_type invalid_pod_index()
The invalid pod index value.
Definition: pod_types.cc:31
order_type _order
The order of the iteration.
void erase_cover()
Schedules the lesser member entry in the cover of the greater member of the current link for deletion...
poset_powerset_state & powerset() const
The set of subposets of this poset.
bool _strict
True if iterating over the strict up/down set of anchor.
pod_type hub_pod() const
The pod value of this mapped to the unglued hub id space.
Definition: scoped_index.h:710