SheafSystem  0.0.0.0
filtered_depth_first_iterator.cc
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 
18 // Implementation for class filtered_depth_first_iterator
19 
20 #include "SheafSystem/filtered_depth_first_iterator.h"
21 #include "SheafSystem/poset_state_handle.h"
22 #include "SheafSystem/assert_contract.h"
23 #include "SheafSystem/subposet.h"
24 #include "SheafSystem/zn_to_bool.h"
25 
26 //#define DIAGNOSTIC_OUTPUT
27 //#undef DIAGNOSTIC_OUTPUT
28 
32 {
33  // Preconditions:
34 
35  // Body:
36 
37  // Postconditions:
38 
39  ensure(invariant());
40  ensure(order() == NOT_AN_ORDER);
41  ensure(!is_initialized());
42  ensure(descending());
43  ensure(!strict());
44  ensure(visit_once());
45 
46  // Exit
47 
48  return;
49 }
50 
53  : depth_first_iterator(xother)
54 {
55 
56  // Preconditions:
57 
58  // Body:
59 
60  // Nothing left to do; base ctor does it all.
61 
62  // Postconditions:
63 
64  ensure(invariant());
65  ensure(order() == xother.order());
66  ensure(is_initialized() == xother.is_initialized());
67  ensure(is_initialized() ? anchor().is_same_state(&xother.anchor()) : true);
68  ensure(is_initialized() ? anchor().version() == xother.anchor().version() : true);
69  ensure(is_initialized() ? filter().is_same_state(&(const_cast<filtered_depth_first_iterator&>(xother).filter())) : true);
70  ensure(is_initialized() ? descending() == xother.descending() : true);
71  ensure(is_initialized() ? strict() == xother.strict() : true);
72  ensure(visit_once() == xother.visit_once());
73  ensure(unexecutable(this is first member of iteration or is_done()));
74 
75  // Exit
76 
77  return;
78 }
79 
83 {
84 
85  // Preconditions:
86 
87  // Body:
88 
90 
91  // Postconditions:
92 
93  ensure(invariant());
94  ensure(order() == xother.order());
95  ensure(is_initialized() == xother.is_initialized());
96  ensure(is_initialized() ? anchor().is_same_state(&xother.anchor()) : true);
97  ensure(is_initialized() ? anchor().version() == xother.anchor().version() : true);
98  ensure(is_initialized() ? filter().is_same_state(&(const_cast<filtered_depth_first_iterator&>(xother).filter())) : true);
99  ensure(is_initialized() ? descending() == xother.descending() : true);
100  ensure(is_initialized() ? strict() == xother.strict() : true);
101  ensure(visit_once() == xother.visit_once());
102  ensure(unexecutable(this is first member of iteration or is_done()));
103 
104  // Exit
105 
106  return *this;
107 }
108 
109 
112 {
113  // Preconditions:
114 
115  // Body:
116 
117  // Postconditions:
118 
119  // Exit:
120 
121  return;
122 }
123 
124 bool
126 is_ancestor_of(const any* xother) const
127 {
128  bool result;
129 
130  // Preconditions:
131 
132  // Body:
133 
134  result = dynamic_cast<const filtered_depth_first_iterator*>(xother) != 0;
135 
136  // Postconditions:
137 
138  // Exit
139 
140  return result;
141 }
142 
145 clone() const
146 {
148 
149  // Preconditions:
150 
151  // Body:
152 
153  result = new filtered_depth_first_iterator;
154 
155  // Postconditions:
156 
157  ensure(result != 0);
158  ensure(!result->is_initialized());
159 
160  // Exit
161 
162  return result;
163 }
164 
165 bool
167 invariant() const
168 {
169  bool result = true;
170 
171  // Preconditions:
172 
173  // Body:
174 
175  invariance(depth_first_iterator::invariant());
176 
177  if(invariant_check())
178  {
180 
182 
183  // Finished, turn invariant checking back on.
184 
186  }
187 
188  // Postconditions:
189 
190  // Exit
191 
192  return result;
193 }
194 
195 
196 // OTHER CONSTRUCTORS
197 
198 
199 
200 
203  bool xdown,
204  bool xstrict,
205  order_type xorder)
206 {
207 
208  // Preconditions:
209 
210  require(xanchor.state_is_read_accessible());
211  require(xorder != NOT_AN_ORDER);
212 
213 
214  // Body:
215 
216  // Initialize the order, dir, and strictness
217 
218  initialize_order(xorder);
219  _descending = xdown;
220  _strict = xstrict;
221 
222  // Initialize the anchor and filter. Then, reset.
223 
224  _anchor = 0;
225  _new_filter = false;
226  put_anchor(&xanchor);
227  put_filter(xanchor.version_index());
228  reset();
229 
230  // Postconditions:
231 
232  ensure(invariant());
233  ensure(is_initialized());
234  ensure(anchor().is_same_state(&xanchor));
235  ensure(anchor().is_same_type(&xanchor));
236  ensure(anchor().version() == xanchor.version());
237  ensure(filter().is_attached());
238  ensure(descending() == xdown);
239  ensure(strict() == xstrict);
240  ensure(strict() && !is_done() ? index() !=~ anchor().index() : true);
241  ensure(visit_once());
242  ensure(unexecutable(!is_done() implies this is first member));
243 
244  return;
245 }
246 
249  const subposet& xfilter,
250  bool xdown,
251  bool xstrict,
252  order_type xorder)
253 {
254 
255  // Preconditions:
256 
257  require(xanchor.state_is_read_accessible());
258  require(xanchor.host()->includes_subposet(&xfilter));
259  require(xorder != NOT_AN_ORDER);
260 
261 
262  // Body:
263 
264  // Initialize the order, dir, and strictness
265 
266  initialize_order(xorder);
267  _descending = xdown;
268  _strict = xstrict;
269 
270  // Initialize the anchor and filter. Then, reset.
271 
272  _anchor = 0;
273  _new_filter = false;
274  put_anchor(&xanchor);
275  put_filter(xfilter);
276  reset();
277 
278  // Postconditions:
279 
280  ensure(invariant());
281  ensure(is_initialized());
282  ensure(anchor().is_same_state(&xanchor));
283  ensure(anchor().is_same_type(&xanchor));
284  ensure(anchor().version() == xanchor.version());
285  ensure(filter().is_attached());
286  ensure(descending() == xdown);
287  ensure(strict() == xstrict);
288  ensure(strict() && !is_done() ? index() !=~ anchor().index() : true);
289  ensure(visit_once());
290  ensure(unexecutable(!is_done() implies this is first member));
291 
292  return;
293 }
294 
297  pod_index_type xfilter_index,
298  bool xdown,
299  bool xstrict,
300  order_type xorder)
301 {
302 
303  // Preconditions:
304 
305  require(xanchor.state_is_read_accessible());
306  require(xanchor.host()->includes_subposet(xfilter_index));
307  require(xorder != NOT_AN_ORDER);
308 
309 
310  // Body:
311 
312  // Initialize the order, dir, and strictness
313 
314  initialize_order(xorder);
315  _descending = xdown;
316  _strict = xstrict;
317 
318  // Initialize the anchor and filter. Then, reset.
319 
320  _anchor = 0;
321  _new_filter = false;
322  put_anchor(&xanchor);
323  put_filter(xfilter_index);
324  reset();
325 
326  // Postconditions:
327 
328  ensure(invariant());
329  ensure(is_initialized());
330  ensure(anchor().is_same_state(&xanchor));
331  ensure(anchor().is_same_type(&xanchor));
332  ensure(anchor().version() == xanchor.version());
333  ensure(filter().is_attached());
334  ensure(strict() == xstrict);
335  ensure(strict() && !is_done() ? index() !=~ anchor().index() : true);
336  ensure(visit_once());
337  ensure(unexecutable(!is_done() implies this is first member));
338 
339  return;
340 }
341 
344  const scoped_index& xfilter_index,
345  bool xdown,
346  bool xstrict,
347  order_type xorder)
348 {
349 
350  // Preconditions:
351 
352  require(xanchor.state_is_read_accessible());
353  require(xanchor.host()->includes_subposet(xfilter_index));
354  require(xorder != NOT_AN_ORDER);
355 
356 
357  // Body:
358 
359  // Initialize the order, dir, and strictness
360 
361  initialize_order(xorder);
362  _descending = xdown;
363  _strict = xstrict;
364 
365  // Initialize the anchor and filter. Then, reset.
366 
367  _anchor = 0;
368  _new_filter = false;
369  put_anchor(&xanchor);
370  put_filter(xfilter_index.hub_pod());
371  reset();
372 
373  // Postconditions:
374 
375  ensure(invariant());
376  ensure(is_initialized());
377  ensure(anchor().is_same_state(&xanchor));
378  ensure(anchor().is_same_type(&xanchor));
379  ensure(anchor().version() == xanchor.version());
380  ensure(filter().is_attached());
381  ensure(strict() == xstrict);
382  ensure(strict() && !is_done() ? index() !=~ anchor().index() : true);
383  ensure(visit_once());
384  ensure(unexecutable(!is_done() implies this is first member));
385 
386  return;
387 }
388 
389 
392  const std::string& xfilter_name,
393  bool xdown,
394  bool xstrict,
395  order_type xorder)
396 {
397 
398  // Preconditions:
399 
400  require(xanchor.state_is_read_accessible());
401  require(!xfilter_name.empty() ? xanchor.host()->includes_subposet(xfilter_name) : true);
402  require(xorder != NOT_AN_ORDER);
403 
404 
405  // Body:
406 
407  // Initialize the order, dir, and strictness
408 
409  initialize_order(xorder);
410  _descending = xdown;
411  _strict = xstrict;
412 
413  // Initialize the anchor and filter. Then, reset.
414 
415  _anchor = 0;
416  _new_filter = false;
417  put_anchor(&xanchor);
418  put_filter(xfilter_name);
419  reset();
420 
421  // Postconditions:
422 
423  ensure(invariant());
424  ensure(is_initialized());
425  ensure(anchor().is_same_state(&xanchor));
426  ensure(anchor().is_same_type(&xanchor));
427  ensure(anchor().version() == xanchor.version());
428  ensure(filter().is_attached());
429  // If _client_filter has multiple names, ensure that at least
430  // one of them matches.
431  ensure(!xfilter_name.empty() ?
432  _client_filter.has_name(xfilter_name) :
433  _client_filter.has_name(anchor().version_name()));
434  ensure(descending() == xdown);
435  ensure(strict() == xstrict);
436  ensure(strict() && !is_done() ? index() !=~ anchor().index() : true);
437  ensure(visit_once());
438  ensure(unexecutable(!is_done() implies this is first member));
439 
440  return;
441 }
442 
443 
444 // ITERATOR FACET
445 
446 
447 
448 void
451 {
452  // Preconditions:
453 
454  require(xanchor != 0);
455  require(anchor_is_ancestor_of(*xanchor));
456  require(xanchor->state_is_read_accessible());
457 
458  // Body:
459 
460  define_old_variable(bool old_descending = _descending);
461  define_old_variable(bool old_strict = _strict);
462 
463  // Force iterator into a known clean state;
464  // also forces client to reset before using this.
465 
466  force_is_done();
467 
468  // Now (re)initialize.
469 
470  initialize_traversal(*xanchor);
471 
472  // Postconditions:
473 
474  ensure(invariant());
475  ensure(is_initialized());
476  ensure(is_done());
477  ensure(anchor().is_same_state(xanchor));
478  ensure(anchor().is_same_type(xanchor));
479  ensure(anchor().version() == xanchor->version());
480  ensure(filter().index() == anchor().version_index());
481  ensure(descending() == old_descending);
482  ensure(strict() == old_strict);
483 
484  // Exit:
485 
486 }
487 
488 void
491 {
492  // Preconditions:
493 
494  require(is_initialized());
495  require(anchor().state_is_read_accessible());
496  require(anchor().host()->contains_member(xanchor_index));
497 
498  // Body:
499 
500  define_old_variable(bool old_descending = _descending);
501  define_old_variable(bool old_strict = _strict);
502  define_old_variable(scoped_index old_filter_index = filter().index());
503  define_old_variable(int old_anchor_version = anchor().version());
504 
505  // Force iterator into a known clean state;
506  // also forces client to reset before using this.
507 
508  force_is_done();
509 
510  // Now reinitialize.
511 
512  initialize_traversal(xanchor_index);
513 
514  // Postconditions:
515 
516  ensure(invariant());
517  ensure(is_initialized());
518  ensure(is_done());
519  ensure(anchor().index() == xanchor_index);
520  ensure(anchor().version() == old_anchor_version);
521  ensure(filter().index() == old_filter_index);
522  ensure(descending() == old_descending);
523  ensure(strict() == old_strict);
524 
525  // Exit:
526 
527 }
528 
529 void
531 put_anchor(const scoped_index& xanchor_index)
532 {
533  // Preconditions:
534 
535  require(is_initialized());
536  require(anchor().state_is_read_accessible());
537  require(anchor().host()->contains_member(xanchor_index));
538 
539  // Body:
540 
541  define_old_variable(bool old_descending = _descending);
542  define_old_variable(bool old_strict = _strict);
543  define_old_variable(scoped_index old_filter_index = filter().index());
544  define_old_variable(int old_anchor_version = anchor().version());
545 
546  put_anchor(xanchor_index.hub_pod());
547 
548  // Postconditions:
549 
550  ensure(invariant());
551  ensure(is_initialized());
552  ensure(is_done());
553  ensure(anchor().index() ==~ xanchor_index);
554  ensure(anchor().version() == old_anchor_version);
555  ensure(filter().index() == old_filter_index);
556  ensure(descending() == old_descending);
557  ensure(strict() == old_strict);
558 
559  // Exit:
560 
561 }
562 
563 void
565 put_descending(bool xdescending)
566 {
567  // Preconditions:
568 
569  // Body:
570 
571  _descending = xdescending;
572 
573  // Postconditions:
574 
575  ensure(descending() == xdescending);
576 
577  // Exit
578 
579  return;
580 }
581 
582 void
584 put_strict(bool xstrict)
585 {
586  // Preconditions:
587 
588  // Body:
589 
590  _strict = xstrict;
591 
592  // Postconditions:
593 
594  ensure(strict() == xstrict);
595 
596  // Exit
597 
598  return;
599 }
600 
601 void
603 put_filter(const subposet& xfilter)
604 {
605 
606  // Preconditions:
607 
608  require(is_initialized());
609  require(anchor().state_is_read_accessible());
610  require(anchor().host()->includes_subposet(&xfilter));
611 
612  // Body:
613 
614  define_old_variable(bool old_descending = _descending);
615  define_old_variable(bool old_strict = _strict);
616 
617  // Force iterator into a known clean state;
618  // also forces client to reset before using this.
619 
620  force_is_done();
621 
622  // Now reinitialize.
623 
624  initialize_filter(xfilter);
625 
626  // Postconditions:
627 
628  ensure(invariant());
629  ensure(is_initialized());
630  ensure(filter().is_same_state(&xfilter));
631  ensure(descending() == old_descending);
632  ensure(strict() == old_strict);
633  ensure(is_done());
634 
635  return;
636 }
637 
638 void
640 put_filter(const std::string& xfilter_name)
641 {
642 
643  // Preconditions:
644 
645  require(is_initialized());
646  require(anchor().state_is_read_accessible());
647  require(!xfilter_name.empty() ? anchor().host()->includes_subposet(xfilter_name) : true);
648 
649  // Body:
650 
651  define_old_variable(bool old_descending = _descending);
652  define_old_variable(bool old_strict = _strict);
653 
654  // Force iterator into a known clean state;
655  // also forces client to reset before using this.
656 
657  force_is_done();
658 
659  // Now reinitialize.
660 
661  initialize_filter(xfilter_name);
662 
663  // Postconditions:
664 
665  ensure(invariant());
666  ensure(is_initialized());
667  ensure(is_done());
668 
669  // If _client_filter has multiple names, ensure that at least
670  // one of them matches.
671  ensure(!xfilter_name.empty() ?
672  _client_filter.has_name(xfilter_name) :
673  _client_filter.has_name(anchor().version_name()));
674  ensure(descending() == old_descending);
675  ensure(strict() == old_strict);
676 
677  return;
678 }
679 
680 void
683 {
684 
685  // Preconditions:
686 
687  require(is_initialized());
688  require(anchor().state_is_read_accessible());
689  require(anchor().host()->includes_subposet(xfilter_index));
690 
691  // Body:
692 
693  define_old_variable(bool old_descending = _descending);
694  define_old_variable(bool old_strict = _strict);
695 
696  // Force iterator into a known clean state;
697  // also forces client to reset before using this.
698 
699  force_is_done();
700 
701  // Now reinitialize.
702 
703  initialize_filter(xfilter_index);
704 
705  // Postconditions:
706 
707  ensure(invariant());
708  ensure(is_initialized());
709  ensure(is_done());
710  ensure(filter().index() == xfilter_index);
711  ensure(descending() == old_descending);
712  ensure(strict() == old_strict);
713 
714  return;
715 }
716 
717 void
719 put_filter(const scoped_index& xfilter_index)
720 {
721 
722  // Preconditions:
723 
724  require(is_initialized());
725  require(anchor().state_is_read_accessible());
726  require(anchor().host()->includes_subposet(xfilter_index));
727 
728  // Body:
729 
730  define_old_variable(bool old_descending = _descending);
731  define_old_variable(bool old_strict = _strict);
732 
733  put_filter(xfilter_index.hub_pod());
734 
735  // Postconditions:
736 
737  ensure(invariant());
738  ensure(is_initialized());
739  ensure(is_done());
740  ensure(filter().index() ==~ xfilter_index);
741  ensure(descending() == old_descending);
742  ensure(strict() == old_strict);
743 
744  return;
745 }
virtual bool has_name(const std::string &xname, bool xauto_access=false) const
True if xname is a name for this.
Definition: subposet.cc:2762
poset_state_handle * host() const
The poset which this is a handle to a component of.
virtual void force_is_done()
Force the iterator to be done.
A client handle for a subposet.
Definition: subposet.h:86
int version(bool xunalias=true) const
The (possibly aliased) version of this component. The version of the host used when evaluating proper...
virtual bool is_initialized() const
True if this has been initialized for iteration with respect to a specific anchor.
void put_filter(const subposet &xfilter)
Sets the subposet which is the filter.
bool visit_once() const
True if traversal should only visit a member once; that is, it should not revisit members it has alre...
void initialize_order(order_type xorder)
Initializes _order and _transition_fcn.
pod_index_type version_index() const
The subposet index for the filter associated with version().
void initialize_filter()
Initializes the filter subposet from the client filter.
abstract_poset_member * _anchor
The top member of the down set being iterated over.
bool state_is_read_accessible() const
True if this is attached and if the state is accessible for read or access control is disabled...
virtual bool includes_subposet(pod_index_type xsubposet_hub_id, bool xauto_access=true) const
True if this poset includes subposet with hub id xsubposet_hub_id.
virtual bool anchor_is_ancestor_of(const abstract_poset_member &xmbr) const
True if xmbr conforms to the type of anchor of this.
order_type
The types of order in which the iterator will visit the members of the poset. Determines which action...
subposet _client_filter
The filter specified by the client.
void put_descending(bool xdescending)
Set descending() to xdescending.
virtual bool is_ancestor_of(const any *other) const
True if other conforms to this.
Abstract base class with useful features for all objects.
Definition: any.h:39
virtual abstract_poset_member & anchor()
The poset member whose downset is being iterated over; the top member of the domain of iteration (mut...
order_type order() const
The order of the iteration. Determines which actions are exported to the client.
An index within the external ("client") scope of a given id space.
Definition: scoped_index.h:116
bool descending() const
True if iterating over down set of anchor.
bool _new_filter
True if this allocated a new filter;.
depth_first_iterator & operator=(const depth_first_iterator &xother)
Assignment operator.
filtered_depth_first_iterator & operator=(const filtered_depth_first_iterator &xother)
Assignment operator.
void disable_invariant_check() const
Disable invariant check. Intended for preventing recursive calls to invariant and for suppressing inv...
Definition: any.h:97
bool is_done() const
True if iteration finished.
void first()
Moves this to the first member of the iteration.
bool _descending
True if iterating over the up/down set of anchor.
virtual void reset(bool xreset_markers=true)
Restarts the iteration over the down set of anchor().
bool invariant_check() const
True if invariant checking is enabled.
Definition: any.h:79
void initialize_traversal(const abstract_poset_member &xanchor)
Initializes the anchor, has_visited markers and filter.
int_type pod_index_type
The plain old data index type.
Definition: pod_types.h:49
bool invariant() const
The class invariant.
bool _strict
True if iterating over the strict up/down set of anchor.
virtual void put_anchor(const abstract_poset_member *xanchor)
Set anchor() to xanchor.
An abstract client handle for a member of a poset.
virtual filtered_depth_first_iterator * clone() const
Make a new instance of the same type as this.
subposet & filter()
The subposet which is the filter; Defines what is passed, not what is blocked.
bool is_same_type(const any *other) const
True if other is the same type as this.
Definition: any.cc:79
void enable_invariant_check() const
Enable invariant checking.
Definition: any.h:87
void put_strict(bool xstrict)
Set strict() to xstrict.
bool strict() const
True if iterating over xstrict up/down set of anchor.
filtered_depth_first_iterator()
Default constructor; creates an unattached iterator, with and all-pass filter.
pod_type hub_pod() const
The pod value of this mapped to the unglued hub id space.
Definition: scoped_index.h:710
const scoped_index & index() const
The index of the current member of the iteration.