ceph/src/boost/libs/graph/include/boost/graph/planar_detail/face_iterators.hpp

   1 //=======================================================================
   2 // Copyright (c) Aaron Windsor 2007
   3 //
   4 // Distributed under the Boost Software License, Version 1.0. (See
   5 // accompanying file LICENSE_1_0.txt or copy at
   6 // http://www.boost.org/LICENSE_1_0.txt)
   7 //=======================================================================
   8
   9 #ifndef __FACE_ITERATORS_HPP__
  10 #define __FACE_ITERATORS_HPP__
  11
  12 #include <boost/iterator/iterator_facade.hpp>
  13 #include <boost/mpl/bool.hpp>
  14 #include <boost/graph/graph_traits.hpp>
  15
  16 namespace boost
  17 {
  18
  19   //tags for defining traversal properties
  20
  21   //VisitorType
  22   struct lead_visitor {};
  23   struct follow_visitor {};
  24
  25   //TraversalType
  26   struct single_side {};
  27   struct both_sides {};
  28
  29   //TraversalSubType
  30   struct first_side {}; //for single_side
  31   struct second_side {}; //for single_side
  32   struct alternating {}; //for both_sides
  33
  34   //Time
  35   struct current_iteration {};
  36   struct previous_iteration {};
  37
  38   // Why TraversalType AND TraversalSubType? TraversalSubType is a function
  39   // template parameter passed in to the constructor of the face iterator,
  40   // whereas TraversalType is a class template parameter. This lets us decide
  41   // at runtime whether to move along the first or second side of a bicomp (by
  42   // assigning a face_iterator that has been constructed with TraversalSubType
  43   // = first_side or second_side to a face_iterator variable) without any of
  44   // the virtual function overhead that comes with implementing this
  45   // functionality as a more structured form of type erasure. It also allows
  46   // a single face_iterator to be the end iterator of two iterators traversing
  47   // both sides of a bicomp.
  48
  49   //ValueType is either graph_traits<Graph>::vertex_descriptor
  50   //or graph_traits<Graph>::edge_descriptor
  51
  52
  53   //forward declaration (defining defaults)
  54   template <typename Graph,
  55             typename FaceHandlesMap,
  56             typename ValueType,
  57             typename BicompSideToTraverse = single_side,
  58             typename VisitorType = lead_visitor,
  59             typename Time = current_iteration
  60             >
  61   class face_iterator;
  62
  63
  64
  65   template <typename Graph, bool StoreEdge>
  66   struct edge_storage
  67   {};
  68
  69   template <typename Graph>
  70   struct edge_storage <Graph, true>
  71   {
  72     typename graph_traits<Graph>::edge_descriptor value;
  73   };
  74
  75
  76
  77
  78   //specialization for TraversalType = traverse_vertices
  79   template <typename Graph,
  80             typename FaceHandlesMap,
  81             typename ValueType,
  82             typename TraversalType,
  83             typename VisitorType,
  84             typename Time
  85             >
  86
  87   class face_iterator
  88       : public boost::iterator_facade < face_iterator<Graph,
  89                                                       FaceHandlesMap,
  90                                                       ValueType,
  91                                                       TraversalType,
  92                                                       VisitorType,
  93                                                       Time
  94                                                       >,
  95                                         ValueType,
  96                                         boost::forward_traversal_tag,
  97                                         ValueType
  98                                       >
  99   {
 100   public:
 101
 102     typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
 103     typedef typename graph_traits<Graph>::edge_descriptor edge_t;
 104     typedef face_iterator
 105       <Graph,FaceHandlesMap,ValueType,TraversalType,VisitorType,Time> self;
 106     typedef typename FaceHandlesMap::value_type face_handle_t;
 107
 108     face_iterator() :
 109       m_lead(graph_traits<Graph>::null_vertex()),
 110       m_follow(graph_traits<Graph>::null_vertex())
 111     {}
 112
 113     template <typename TraversalSubType>
 114     face_iterator(face_handle_t anchor_handle,
 115                   FaceHandlesMap face_handles,
 116                   TraversalSubType traversal_type):
 117       m_follow(anchor_handle.get_anchor()),
 118       m_face_handles(face_handles)
 119     {
 120       set_lead_dispatch(anchor_handle, traversal_type);
 121     }
 122
 123     template <typename TraversalSubType>
 124     face_iterator(vertex_t anchor,
 125                   FaceHandlesMap face_handles,
 126                   TraversalSubType traversal_type):
 127       m_follow(anchor),
 128       m_face_handles(face_handles)
 129     {
 130       set_lead_dispatch(m_face_handles[anchor], traversal_type);
 131     }
 132
 133   private:
 134
 135     friend class boost::iterator_core_access;
 136
 137
 138
 139
 140     inline vertex_t get_first_vertex(face_handle_t anchor_handle,
 141                                      current_iteration
 142                                      )
 143     {
 144       return anchor_handle.first_vertex();
 145     }
 146
 147     inline vertex_t get_second_vertex(face_handle_t anchor_handle,
 148                                       current_iteration
 149                                       )
 150     {
 151       return anchor_handle.second_vertex();
 152     }
 153
 154     inline vertex_t get_first_vertex(face_handle_t anchor_handle,
 155                                      previous_iteration
 156                                      )
 157     {
 158       return anchor_handle.old_first_vertex();
 159     }
 160
 161     inline vertex_t get_second_vertex(face_handle_t anchor_handle,
 162                                       previous_iteration
 163                                       )
 164     {
 165       return anchor_handle.old_second_vertex();
 166     }
 167
 168
 169
 170
 171
 172     inline void set_lead_dispatch(face_handle_t anchor_handle, first_side)
 173     {
 174       m_lead = get_first_vertex(anchor_handle, Time());
 175       set_edge_to_first_dispatch(anchor_handle, ValueType(), Time());
 176     }
 177
 178     inline void set_lead_dispatch(face_handle_t anchor_handle, second_side)
 179     {
 180       m_lead = get_second_vertex(anchor_handle, Time());
 181       set_edge_to_second_dispatch(anchor_handle, ValueType(), Time());
 182     }
 183
 184
 185
 186
 187
 188     inline void set_edge_to_first_dispatch(face_handle_t anchor_handle,
 189                                            edge_t,
 190                                            current_iteration
 191                                            )
 192     {
 193       m_edge.value = anchor_handle.first_edge();
 194     }
 195
 196     inline void set_edge_to_second_dispatch(face_handle_t anchor_handle,
 197                                             edge_t,
 198                                             current_iteration
 199                                             )
 200     {
 201       m_edge.value = anchor_handle.second_edge();
 202     }
 203
 204     inline void set_edge_to_first_dispatch(face_handle_t anchor_handle,
 205                                            edge_t,
 206                                            previous_iteration
 207                                            )
 208     {
 209       m_edge.value = anchor_handle.old_first_edge();
 210     }
 211
 212     inline void set_edge_to_second_dispatch(face_handle_t anchor_handle,
 213                                             edge_t,
 214                                             previous_iteration
 215                                             )
 216     {
 217       m_edge.value = anchor_handle.old_second_edge();
 218     }
 219
 220     template<typename T>
 221     inline void set_edge_to_first_dispatch(face_handle_t, vertex_t, T)
 222     {}
 223
 224     template<typename T>
 225     inline void set_edge_to_second_dispatch(face_handle_t, vertex_t, T)
 226     {}
 227
 228     void increment()
 229     {
 230       face_handle_t curr_face_handle(m_face_handles[m_lead]);
 231       vertex_t first = get_first_vertex(curr_face_handle, Time());
 232       vertex_t second = get_second_vertex(curr_face_handle, Time());
 233       if (first == m_follow)
 234         {
 235           m_follow = m_lead;
 236           set_edge_to_second_dispatch(curr_face_handle, ValueType(), Time());
 237           m_lead = second;
 238         }
 239       else if (second == m_follow)
 240         {
 241           m_follow = m_lead;
 242           set_edge_to_first_dispatch(curr_face_handle, ValueType(), Time());
 243           m_lead = first;
 244         }
 245       else
 246         m_lead = m_follow = graph_traits<Graph>::null_vertex();
 247     }
 248
 249     bool equal(self const& other) const
 250     {
 251       return m_lead == other.m_lead && m_follow == other.m_follow;
 252     }
 253
 254     ValueType dereference() const
 255     {
 256       return dereference_dispatch(VisitorType(), ValueType());
 257     }
 258
 259     inline ValueType dereference_dispatch(lead_visitor, vertex_t) const
 260     { return m_lead; }
 261
 262     inline ValueType dereference_dispatch(follow_visitor, vertex_t) const
 263     { return m_follow; }
 264
 265     inline ValueType dereference_dispatch(lead_visitor, edge_t) const
 266     { return m_edge.value; }
 267
 268     inline ValueType dereference_dispatch(follow_visitor, edge_t) const
 269     { return m_edge.value; }
 270
 271     vertex_t m_lead;
 272     vertex_t m_follow;
 273     edge_storage<Graph, boost::is_same<ValueType, edge_t>::value > m_edge;
 274     FaceHandlesMap m_face_handles;
 275   };
 276
 277
 278
 279
 280
 281
 282
 283
 284
 285   template <typename Graph,
 286             typename FaceHandlesMap,
 287             typename ValueType,
 288             typename VisitorType,
 289             typename Time
 290             >
 291   class face_iterator
 292     <Graph, FaceHandlesMap, ValueType, both_sides, VisitorType, Time>
 293     : public boost::iterator_facade< face_iterator<Graph,
 294                                                    FaceHandlesMap,
 295                                                    ValueType,
 296                                                    both_sides,
 297                                                    VisitorType,
 298                                                    Time>,
 299                                      ValueType,
 300                                      boost::forward_traversal_tag,
 301                                      ValueType >
 302   {
 303   public:
 304
 305     typedef face_iterator
 306       <Graph,FaceHandlesMap,ValueType,both_sides,VisitorType,Time> self;
 307     typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
 308     typedef typename FaceHandlesMap::value_type face_handle_t;
 309
 310     face_iterator() {}
 311
 312     face_iterator(face_handle_t anchor_handle, FaceHandlesMap face_handles):
 313       first_itr(anchor_handle, face_handles, first_side()),
 314       second_itr(anchor_handle, face_handles, second_side()),
 315       first_is_active(true),
 316       first_increment(true)
 317     {}
 318
 319     face_iterator(vertex_t anchor, FaceHandlesMap face_handles):
 320       first_itr(face_handles[anchor], face_handles, first_side()),
 321       second_itr(face_handles[anchor], face_handles, second_side()),
 322       first_is_active(true),
 323       first_increment(true)
 324     {}
 325
 326   private:
 327
 328     friend class boost::iterator_core_access;
 329
 330     typedef face_iterator
 331       <Graph, FaceHandlesMap, ValueType, single_side, follow_visitor, Time>
 332       inner_itr_t;
 333
 334     void increment()
 335     {
 336       if (first_increment)
 337         {
 338           ++first_itr;
 339           ++second_itr;
 340           first_increment = false;
 341         }
 342       else if (first_is_active)
 343         ++first_itr;
 344       else
 345         ++second_itr;
 346       first_is_active = !first_is_active;
 347     }
 348
 349     bool equal(self const& other) const
 350     {
 351       //Want this iterator to be equal to the "end" iterator when at least
 352       //one of the iterators has reached the root of the current bicomp.
 353       //This isn't ideal, but it works.
 354
 355       return (first_itr == other.first_itr || second_itr == other.second_itr);
 356     }
 357
 358     ValueType dereference() const
 359     {
 360       return first_is_active ? *first_itr : *second_itr;
 361     }
 362
 363     inner_itr_t first_itr;
 364     inner_itr_t second_itr;
 365     inner_itr_t face_end;
 366     bool first_is_active;
 367     bool first_increment;
 368
 369   };
 370
 371
 372 } /* namespace boost */
 373
 374
 375 #endif //__FACE_ITERATORS_HPP__