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 face_iterator()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> face_iterator(face_handle_t anchor_handle,FaceHandlesMap face_handles,TraversalSubType traversal_type)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> face_iterator(vertex_t anchor,FaceHandlesMap face_handles,TraversalSubType traversal_type)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 get_first_vertex(face_handle_t anchor_handle,current_iteration)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 get_second_vertex(face_handle_t anchor_handle,current_iteration)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 get_first_vertex(face_handle_t anchor_handle,previous_iteration)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 get_second_vertex(face_handle_t anchor_handle,previous_iteration)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 set_lead_dispatch(face_handle_t anchor_handle,first_side)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 set_lead_dispatch(face_handle_t anchor_handle,second_side)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 set_edge_to_first_dispatch(face_handle_t anchor_handle,edge_t,current_iteration)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 set_edge_to_second_dispatch(face_handle_t anchor_handle,edge_t,current_iteration)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 set_edge_to_first_dispatch(face_handle_t anchor_handle,edge_t,previous_iteration)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 set_edge_to_second_dispatch(face_handle_t anchor_handle,edge_t,previous_iteration)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> set_edge_to_first_dispatch(face_handle_t,vertex_t,T)221 inline void set_edge_to_first_dispatch(face_handle_t, vertex_t, T) 222 {} 223 224 template<typename T> set_edge_to_second_dispatch(face_handle_t,vertex_t,T)225 inline void set_edge_to_second_dispatch(face_handle_t, vertex_t, T) 226 {} 227 increment()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 equal(self const & other) const249 bool equal(self const& other) const 250 { 251 return m_lead == other.m_lead && m_follow == other.m_follow; 252 } 253 dereference() const254 ValueType dereference() const 255 { 256 return dereference_dispatch(VisitorType(), ValueType()); 257 } 258 dereference_dispatch(lead_visitor,vertex_t) const259 inline ValueType dereference_dispatch(lead_visitor, vertex_t) const 260 { return m_lead; } 261 dereference_dispatch(follow_visitor,vertex_t) const262 inline ValueType dereference_dispatch(follow_visitor, vertex_t) const 263 { return m_follow; } 264 dereference_dispatch(lead_visitor,edge_t) const265 inline ValueType dereference_dispatch(lead_visitor, edge_t) const 266 { return m_edge.value; } 267 dereference_dispatch(follow_visitor,edge_t) const268 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 face_iterator()310 face_iterator() {} 311 face_iterator(face_handle_t anchor_handle,FaceHandlesMap face_handles)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 face_iterator(vertex_t anchor,FaceHandlesMap face_handles)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 increment()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 equal(self const & other) const349 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 dereference() const358 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__ 376