depth_first_itr.h

Go to the documentation of this file.

//
// 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.
//


#ifndef DEPTH_FIRST_ITR_H
#define DEPTH_FIRST_ITR_H

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

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

#ifndef STD_UNORDERED_SET_H
#include "SheafSystem/std_unordered_set.h"
#endif

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

#ifndef STD_SET_H
#include "SheafSystem/std_set.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;

template <typename T>
class SHEAF_DLL_SPEC depth_first_itr : public any
{
  // ===========================================================
  // ===========================================================

public:

  depth_first_itr& operator=(const depth_first_itr& xother);

  virtual ~depth_first_itr();

  // SOME USEFUL CONSTANTS

  static const char* NULL_FILTER;

  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
  };

protected:

  depth_first_itr();

  depth_first_itr(const depth_first_itr& 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);

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

  bool filter(const scoped_index& xid)
  {
    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];

  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:

  T* _has_visited;

  zn_to_bool* _filter;



  // ===========================================================
  // ===========================================================

public:

  order_type order() const;

  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);

  void clear_has_visited();

  void reserve_has_visited(pod_index_type xub);

  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 scoped_index& greater_index() const;

  const scoped_index& lesser_index() const;

  action_type action() const;

  void erase_cover();

protected:

private:



  // ===========================================================
  // ===========================================================

public:

  const scoped_index& index() const;

  size_t depth();

protected:

private:



  // ===========================================================
  // ===========================================================

public:

  virtual bool is_ancestor_of(const any* other) const;

  virtual depth_first_itr* clone() const;

  bool invariant() const;

protected:

private:

};

// =============================================================================
// MEMBER FUNCTION SPECIALIZATIONS
// =============================================================================

template <>
SHEAF_DLL_SPEC
void
depth_first_itr<zn_to_bool>::
clear_has_visited();

template <>
SHEAF_DLL_SPEC
void
depth_first_itr<zn_to_bool>::
reserve_has_visited(pod_index_type xub);

template <>
SHEAF_DLL_SPEC
bool
depth_first_itr<zn_to_bool>::
has_visited(pod_index_type xhub_id) const;

template <>
SHEAF_DLL_SPEC
void
depth_first_itr<zn_to_bool>::
initialize_has_visited(const abstract_poset_member& xanchor);

template <>
SHEAF_DLL_SPEC
void
depth_first_itr<zn_to_bool>::
put_has_visited(pod_index_type xhub_id, bool xvalue);

template <>
SHEAF_DLL_SPEC
void
depth_first_itr< std::set<pod_index_type> >::
clear_has_visited();


template <>
SHEAF_DLL_SPEC
void
depth_first_itr< std::set<pod_index_type> >::
reserve_has_visited(pod_index_type xub);

template <>
SHEAF_DLL_SPEC
bool
depth_first_itr< std::set<pod_index_type> >::
has_visited(pod_index_type xhub_id) const;


template <>
SHEAF_DLL_SPEC
void
depth_first_itr< std::set<pod_index_type> >::
initialize_has_visited(const abstract_poset_member& xanchor);

template <>
SHEAF_DLL_SPEC
void
depth_first_itr< std::set<pod_index_type> >::
put_has_visited(pod_index_type xhub_id, bool xvalue);

template <>
SHEAF_DLL_SPEC
void
depth_first_itr< unordered::unordered_set<pod_index_type> >::
clear_has_visited();

template <>
SHEAF_DLL_SPEC
void
depth_first_itr< unordered::unordered_set<pod_index_type> >::
reserve_has_visited(pod_index_type xub);

template <>
SHEAF_DLL_SPEC
bool
depth_first_itr< unordered::unordered_set<pod_index_type> >::
has_visited(pod_index_type xhub_id) const;

template <>
SHEAF_DLL_SPEC
void
depth_first_itr< unordered::unordered_set<pod_index_type> >::
initialize_has_visited(const abstract_poset_member& xanchor);

template <>
SHEAF_DLL_SPEC
void
depth_first_itr< unordered::unordered_set<pod_index_type> >::
put_has_visited(pod_index_type xhub_id, bool xvalue);
 
} // namespace sheaf

#endif // ifndef DEPTH_FIRST_ITR_H