123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375 |
- //=======================================================================
- // Copyright (c) Aaron Windsor 2007
- //
- // Distributed under the Boost Software License, Version 1.0. (See
- // accompanying file LICENSE_1_0.txt or copy at
- // http://www.boost.org/LICENSE_1_0.txt)
- //=======================================================================
- #ifndef __FACE_ITERATORS_HPP__
- #define __FACE_ITERATORS_HPP__
- #include <boost/iterator/iterator_facade.hpp>
- #include <boost/mpl/bool.hpp>
- #include <boost/graph/graph_traits.hpp>
- namespace boost
- {
- //tags for defining traversal properties
- //VisitorType
- struct lead_visitor {};
- struct follow_visitor {};
- //TraversalType
- struct single_side {};
- struct both_sides {};
- //TraversalSubType
- struct first_side {}; //for single_side
- struct second_side {}; //for single_side
- struct alternating {}; //for both_sides
- //Time
- struct current_iteration {};
- struct previous_iteration {};
- // Why TraversalType AND TraversalSubType? TraversalSubType is a function
- // template parameter passed in to the constructor of the face iterator,
- // whereas TraversalType is a class template parameter. This lets us decide
- // at runtime whether to move along the first or second side of a bicomp (by
- // assigning a face_iterator that has been constructed with TraversalSubType
- // = first_side or second_side to a face_iterator variable) without any of
- // the virtual function overhead that comes with implementing this
- // functionality as a more structured form of type erasure. It also allows
- // a single face_iterator to be the end iterator of two iterators traversing
- // both sides of a bicomp.
- //ValueType is either graph_traits<Graph>::vertex_descriptor
- //or graph_traits<Graph>::edge_descriptor
-
- //forward declaration (defining defaults)
- template <typename Graph,
- typename FaceHandlesMap,
- typename ValueType,
- typename BicompSideToTraverse = single_side,
- typename VisitorType = lead_visitor,
- typename Time = current_iteration
- >
- class face_iterator;
-
- template <typename Graph, bool StoreEdge>
- struct edge_storage
- {};
- template <typename Graph>
- struct edge_storage <Graph, true>
- {
- typename graph_traits<Graph>::edge_descriptor value;
- };
- //specialization for TraversalType = traverse_vertices
- template <typename Graph,
- typename FaceHandlesMap,
- typename ValueType,
- typename TraversalType,
- typename VisitorType,
- typename Time
- >
- class face_iterator
- : public boost::iterator_facade < face_iterator<Graph,
- FaceHandlesMap,
- ValueType,
- TraversalType,
- VisitorType,
- Time
- >,
- ValueType,
- boost::forward_traversal_tag,
- ValueType
- >
- {
- public:
- typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
- typedef typename graph_traits<Graph>::edge_descriptor edge_t;
- typedef face_iterator
- <Graph,FaceHandlesMap,ValueType,TraversalType,VisitorType,Time> self;
- typedef typename FaceHandlesMap::value_type face_handle_t;
- face_iterator() :
- m_lead(graph_traits<Graph>::null_vertex()),
- m_follow(graph_traits<Graph>::null_vertex())
- {}
- template <typename TraversalSubType>
- face_iterator(face_handle_t anchor_handle,
- FaceHandlesMap face_handles,
- TraversalSubType traversal_type):
- m_follow(anchor_handle.get_anchor()),
- m_face_handles(face_handles)
- {
- set_lead_dispatch(anchor_handle, traversal_type);
- }
- template <typename TraversalSubType>
- face_iterator(vertex_t anchor,
- FaceHandlesMap face_handles,
- TraversalSubType traversal_type):
- m_follow(anchor),
- m_face_handles(face_handles)
- {
- set_lead_dispatch(m_face_handles[anchor], traversal_type);
- }
- private:
-
- friend class boost::iterator_core_access;
-
- inline vertex_t get_first_vertex(face_handle_t anchor_handle,
- current_iteration
- )
- {
- return anchor_handle.first_vertex();
- }
- inline vertex_t get_second_vertex(face_handle_t anchor_handle,
- current_iteration
- )
- {
- return anchor_handle.second_vertex();
- }
- inline vertex_t get_first_vertex(face_handle_t anchor_handle,
- previous_iteration
- )
- {
- return anchor_handle.old_first_vertex();
- }
- inline vertex_t get_second_vertex(face_handle_t anchor_handle,
- previous_iteration
- )
- {
- return anchor_handle.old_second_vertex();
- }
- inline void set_lead_dispatch(face_handle_t anchor_handle, first_side)
- {
- m_lead = get_first_vertex(anchor_handle, Time());
- set_edge_to_first_dispatch(anchor_handle, ValueType(), Time());
- }
-
- inline void set_lead_dispatch(face_handle_t anchor_handle, second_side)
- {
- m_lead = get_second_vertex(anchor_handle, Time());
- set_edge_to_second_dispatch(anchor_handle, ValueType(), Time());
- }
- inline void set_edge_to_first_dispatch(face_handle_t anchor_handle,
- edge_t,
- current_iteration
- )
- {
- m_edge.value = anchor_handle.first_edge();
- }
- inline void set_edge_to_second_dispatch(face_handle_t anchor_handle,
- edge_t,
- current_iteration
- )
- {
- m_edge.value = anchor_handle.second_edge();
- }
- inline void set_edge_to_first_dispatch(face_handle_t anchor_handle,
- edge_t,
- previous_iteration
- )
- {
- m_edge.value = anchor_handle.old_first_edge();
- }
- inline void set_edge_to_second_dispatch(face_handle_t anchor_handle,
- edge_t,
- previous_iteration
- )
- {
- m_edge.value = anchor_handle.old_second_edge();
- }
-
- template<typename T>
- inline void set_edge_to_first_dispatch(face_handle_t, vertex_t, T)
- {}
- template<typename T>
- inline void set_edge_to_second_dispatch(face_handle_t, vertex_t, T)
- {}
- void increment()
- {
- face_handle_t curr_face_handle(m_face_handles[m_lead]);
- vertex_t first = get_first_vertex(curr_face_handle, Time());
- vertex_t second = get_second_vertex(curr_face_handle, Time());
- if (first == m_follow)
- {
- m_follow = m_lead;
- set_edge_to_second_dispatch(curr_face_handle, ValueType(), Time());
- m_lead = second;
- }
- else if (second == m_follow)
- {
- m_follow = m_lead;
- set_edge_to_first_dispatch(curr_face_handle, ValueType(), Time());
- m_lead = first;
- }
- else
- m_lead = m_follow = graph_traits<Graph>::null_vertex();
- }
-
- bool equal(self const& other) const
- {
- return m_lead == other.m_lead && m_follow == other.m_follow;
- }
-
- ValueType dereference() const
- {
- return dereference_dispatch(VisitorType(), ValueType());
- }
-
- inline ValueType dereference_dispatch(lead_visitor, vertex_t) const
- { return m_lead; }
-
- inline ValueType dereference_dispatch(follow_visitor, vertex_t) const
- { return m_follow; }
- inline ValueType dereference_dispatch(lead_visitor, edge_t) const
- { return m_edge.value; }
- inline ValueType dereference_dispatch(follow_visitor, edge_t) const
- { return m_edge.value; }
- vertex_t m_lead;
- vertex_t m_follow;
- edge_storage<Graph, boost::is_same<ValueType, edge_t>::value > m_edge;
- FaceHandlesMap m_face_handles;
- };
-
- template <typename Graph,
- typename FaceHandlesMap,
- typename ValueType,
- typename VisitorType,
- typename Time
- >
- class face_iterator
- <Graph, FaceHandlesMap, ValueType, both_sides, VisitorType, Time>
- : public boost::iterator_facade< face_iterator<Graph,
- FaceHandlesMap,
- ValueType,
- both_sides,
- VisitorType,
- Time>,
- ValueType,
- boost::forward_traversal_tag,
- ValueType >
- {
- public:
- typedef face_iterator
- <Graph,FaceHandlesMap,ValueType,both_sides,VisitorType,Time> self;
- typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
- typedef typename FaceHandlesMap::value_type face_handle_t;
- face_iterator() {}
- face_iterator(face_handle_t anchor_handle, FaceHandlesMap face_handles):
- first_itr(anchor_handle, face_handles, first_side()),
- second_itr(anchor_handle, face_handles, second_side()),
- first_is_active(true),
- first_increment(true)
- {}
- face_iterator(vertex_t anchor, FaceHandlesMap face_handles):
- first_itr(face_handles[anchor], face_handles, first_side()),
- second_itr(face_handles[anchor], face_handles, second_side()),
- first_is_active(true),
- first_increment(true)
- {}
-
- private:
-
- friend class boost::iterator_core_access;
- typedef face_iterator
- <Graph, FaceHandlesMap, ValueType, single_side, follow_visitor, Time>
- inner_itr_t;
-
- void increment()
- {
- if (first_increment)
- {
- ++first_itr;
- ++second_itr;
- first_increment = false;
- }
- else if (first_is_active)
- ++first_itr;
- else
- ++second_itr;
- first_is_active = !first_is_active;
- }
-
- bool equal(self const& other) const
- {
- //Want this iterator to be equal to the "end" iterator when at least
- //one of the iterators has reached the root of the current bicomp.
- //This isn't ideal, but it works.
- return (first_itr == other.first_itr || second_itr == other.second_itr);
- }
-
- ValueType dereference() const
- {
- return first_is_active ? *first_itr : *second_itr;
- }
- inner_itr_t first_itr;
- inner_itr_t second_itr;
- inner_itr_t face_end;
- bool first_is_active;
- bool first_increment;
- };
-
-
- } /* namespace boost */
- #endif //__FACE_ITERATORS_HPP__
|