depth_first_iterator.h

//
// Copyright (c) 2014 Limit Point Systems, Inc.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//   http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//

// Interface for class depth_first_iterator


#ifndef DEPTH_FIRST_ITERATOR_H
#define DEPTH_FIRST_ITERATOR_H

#ifndef SHEAF_DLL_SPEC_H
#include "SheafSystem/sheaf_dll_spec.h"
#endif

#ifndef ANY_H
#include "SheafSystem/any.h"
#endif

#ifndef POSET_STATE_HANDLE_H
#include "SheafSystem/poset_state_handle.h"
#endif

#ifndef STD_STACK_H
#include "SheafSystem/std_stack.h"
#endif

#ifndef SUBPOSET_H
#include "SheafSystem/subposet.h"
#endif

#ifndef TOTAL_POSET_MEMBER_H
#include "SheafSystem/total_poset_member.h"
#endif

namespace sheaf
{

class zn_to_bool;  

class SHEAF_DLL_SPEC depth_first_iterator : public any
{


public:

  // CANONICAL MEMBERS

  depth_first_iterator& operator=(const depth_first_iterator& xother);

  virtual ~depth_first_iterator();

  virtual bool is_ancestor_of(const any* other) const;

  virtual depth_first_iterator* clone() const;

  bool invariant() const;

  // SOME USEFUL CONSTANTS

  static const char* NULL_FILTER;

/*   /// */
/*   /// Iteration directions */
/*   /// */
/*   static const bool DOWN; */

/*   /// */
/*   /// Iteration directions */
/*   /// */
/*   static const bool UP; */

/*   /// */
/*   /// Iteration marker reset control */
/*   /// */
/*   static const bool RESET; */

/*   /// */
/*   /// Iteration marker reset control */
/*   /// */
/*   static const bool NO_RESET; */

/*   /// */
/*   /// Iteration strictness control */
/*   /// */
/*   static const bool STRICT; */

/*   /// */
/*   /// Iteration strictness control */
/*   /// */
/*   static const bool NOT_STRICT; */

  enum order_type
  {
    PREORDER,  // Member is visited before its inferiors, exports PREVISIT_ACTION.
    POSTORDER, // Member is visited after its inferiors, exports POSTVISIT_ACTION.
    LINKORDER, // Visits links; exports LINK_ACTION.
    BIORDER,  // Exports PREVISIT_ACTION and POSTVISIT_ACTION.
    TRIORDER,  // Exports PREVISIT_ACTION, POSTVISIT_ACTION, and LINK_ACTION.
    NOT_AN_ORDER
  };

  enum action_type
  {
    PREVISIT_ACTION,
    LINK_ACTION,
    POSTVISIT_ACTION,
    NOT_AN_ACTION
  };

  // ITERATOR FACET

  order_type order() const;

  //$$SCRIBBLE jebutler const correctness

  virtual bool is_initialized() const;

  virtual abstract_poset_member& anchor();

  virtual const abstract_poset_member& anchor() const;

  virtual bool anchor_is_ancestor_of(const abstract_poset_member& xmbr) const;

  bool descending() const;

  bool strict() const;

  subposet& filter();

  bool is_done() const;

  virtual void force_is_done();

  inline void next()
  {
    next(false);
  };

  inline void truncate()
  {
    next(true);
  };

  virtual void next(bool xtruncate);

  virtual void reset(bool xreset_markers = true);

  int ct(bool xreset = false);

  bool has_visited(pod_index_type xhub_id) const;

  bool has_visited(const scoped_index& xid) const;

  bool has_visited(const abstract_poset_member* xmbr) const;

  void put_has_visited(pod_index_type xhub_id, bool xvalue);

  void put_has_visited(const scoped_index& xid, bool xvalue);

  bool visit_once() const;

  void put_visit_once(bool xvisit_once);

  bool is_maximal() const;

  const scoped_index& greater_index() const;

  const scoped_index& lesser_index() const;

  action_type action() const;

  void erase_cover();

  // INDEX ITERATOR FACET

  const scoped_index& index() const;

  size_t depth() const;

protected:

  depth_first_iterator();

  depth_first_iterator(const depth_first_iterator& xother);

  void first();

  void mark_visited(abstract_poset_member* xmbr);

  void mark_not_visited(abstract_poset_member* xmbr);

  virtual void attach_item();

  virtual void detach_item();

  void initialize_order(order_type xorder);

  void initialize_traversal(const abstract_poset_member& xanchor);

  void initialize_traversal(pod_index_type xanchor_hub_id);

  void initialize_traversal(const scoped_index& xanchor_id);

  void initialize_anchor(const abstract_poset_member& xanchor);

  virtual void initialize_has_visited(const abstract_poset_member& xanchor);

  zn_to_bool* has_visited() const;

  void put_has_visited(zn_to_bool* xhas_visited);
  

  bool filter(pod_index_type xhub_id) const
  {
    return (*_filter)[xhub_id];
  };

  bool filter(const scoped_index& xid) const
  {
    return (*_filter)[xid.hub_pod()];
  };

  void initialize_filter();

  void initialize_filter(const subposet& xfilter);

  void initialize_filter(pod_index_type xfilter_hub_id);

  void initialize_filter(const scoped_index& xfilter_id);

  void initialize_filter(const std::string& xfilter_name);

  void release_cover_id_space_iterators();

  abstract_poset_member* _anchor;

  action_type _action;

  scoped_index _index;

  mutable scoped_index _greater_index;

  mutable scoped_index _lesser_index;

  subposet _client_filter;

  bool _new_filter;

  bool _descending;

  bool _strict;

  order_type _order;

  enum iterator_state
  {
    FIRST,
    INIT_COVER_ITERATOR,
    TEST_HAS_VISITED,
    INC_COVER_ITERATOR,
    ERASE_COVER_ITERATOR,
    DESCEND,
    TEST_PATH_TAIL,
    ASCEND,
    EXECUTE_PREVISIT_ACTION,
    EXECUTE_LINK_ACTION,
    EXECUTE_POSTVISIT_ACTION,
    FINISH,
    NOT_A_STATE // Must be last; used for array bounds.
  };

  enum iterator_token
  {
    PASS,
    FAIL
  };

  static const char* iterator_state_names[NOT_A_STATE+1];

  const iterator_state (*_transition_fcn)[FAIL+1];

  static const iterator_state PREORDER_TRANSITION_FCN[NOT_A_STATE-1][FAIL+1];

  static const iterator_state POSTORDER_TRANSITION_FCN[NOT_A_STATE-1][FAIL+1];

  static const iterator_state LINKORDER_TRANSITION_FCN[NOT_A_STATE-1][FAIL+1];

  static const iterator_state BIORDER_TRANSITION_FCN[NOT_A_STATE-1][FAIL+1];

  static const iterator_state TRIORDER_TRANSITION_FCN[NOT_A_STATE-1][FAIL+1];

  typedef const iterator_state (*transition_fcn_type)[FAIL+1];

  static const transition_fcn_type STD_TRANSITION_FCNS[NOT_AN_ORDER+1];

  iterator_state _state;

  index_space_iterator* _path_head_lc;

  index_space_iterator* _path_head;

  std::stack<index_space_iterator*> _path_tail;

  std::stack<pod_index_type> _filtered_path_tail;

  bool _visit_once;

private:

  zn_to_bool* _has_visited;

  zn_to_bool* _filter;

};

} // namespace sheaf

#endif // ifndef DEPTH_FIRST_ITERATOR_H