traversor2.h 13.8 KB
Newer Older
Pierre Kraemer's avatar
Pierre Kraemer committed
1 2 3
/*******************************************************************************
* CGoGN: Combinatorial and Geometric modeling with Generic N-dimensional Maps  *
* version 0.1                                                                  *
4
* Copyright (C) 2009-2012, IGG Team, LSIIT, University of Strasbourg           *
Pierre Kraemer's avatar
Pierre Kraemer committed
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
*                                                                              *
* This library is free software; you can redistribute it and/or modify it      *
* under the terms of the GNU Lesser General Public License as published by the *
* Free Software Foundation; either version 2.1 of the License, or (at your     *
* option) any later version.                                                   *
*                                                                              *
* This library is distributed in the hope that it will be useful, but WITHOUT  *
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or        *
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License  *
* for more details.                                                            *
*                                                                              *
* You should have received a copy of the GNU Lesser General Public License     *
* along with this library; if not, write to the Free Software Foundation,      *
* Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301 USA.           *
*                                                                              *
20
* Web site: http://cgogn.unistra.fr/                                           *
Pierre Kraemer's avatar
Pierre Kraemer committed
21 22 23 24 25 26 27 28
* Contact information: cgogn@unistra.fr                                        *
*                                                                              *
*******************************************************************************/

#ifndef __TRAVERSOR2_H__
#define __TRAVERSOR2_H__

#include "Topology/generic/dart.h"
29
#include "Topology/generic/cells.h"
Pierre Kraemer's avatar
Pierre Kraemer committed
30 31 32

namespace CGoGN
{
33

Pierre Kraemer's avatar
Pierre Kraemer committed
34 35 36 37
/*******************************************************************************
					VERTEX CENTERED TRAVERSALS
*******************************************************************************/

Pierre Kraemer's avatar
Pierre Kraemer committed
38 39
// Traverse the edges incident to a given vertex
template <typename MAP>
40
class Traversor2VE
Pierre Kraemer's avatar
Pierre Kraemer committed
41 42
{
private:
Sylvain Thery's avatar
Sylvain Thery committed
43
	const MAP& m ;
44 45
	Edge start ;
	Edge current ;
Sylvain Thery's avatar
Sylvain Thery committed
46 47
	const std::vector<Dart>* m_QLT;
	std::vector<Dart>::const_iterator m_ItDarts;
Pierre Kraemer's avatar
Pierre Kraemer committed
48
public:
49
	Traversor2VE(const MAP& map, Vertex dart) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
50

51 52 53
	inline Edge begin() ;
	inline Edge end() ;
	inline Edge next() ;
54 55 56 57

	typedef Edge IterType;
	typedef Vertex ParamType;
	typedef MAP MapType;
Pierre Kraemer's avatar
Pierre Kraemer committed
58 59 60 61
} ;

// Traverse the faces incident to a given vertex
template <typename MAP>
62
class Traversor2VF
Pierre Kraemer's avatar
Pierre Kraemer committed
63 64
{
private:
Sylvain Thery's avatar
Sylvain Thery committed
65
	const MAP& m ;
66 67
	Face start ;
	Face current ;
Sylvain Thery's avatar
Sylvain Thery committed
68 69
	const std::vector<Dart>* m_QLT;
	std::vector<Dart>::const_iterator m_ItDarts;
Pierre Kraemer's avatar
Pierre Kraemer committed
70
public:
71
	Traversor2VF(const MAP& map, Vertex dart) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
72

73 74 75
	inline Face begin() ;
	inline Face end() ;
	inline Face next() ;
76 77 78 79

	typedef Face IterType;
	typedef Vertex ParamType;
	typedef MAP MapType;
Pierre Kraemer's avatar
Pierre Kraemer committed
80 81 82 83
} ;

// Traverse the vertices adjacent to a given vertex through sharing a common edge
template <typename MAP>
84
class Traversor2VVaE
Pierre Kraemer's avatar
Pierre Kraemer committed
85 86
{
private:
Sylvain Thery's avatar
Sylvain Thery committed
87
	const MAP& m ;
88 89
	Vertex start ;
	Vertex current ;
Sylvain Thery's avatar
Sylvain Thery committed
90 91
	const std::vector<Dart>* m_QLT;
	std::vector<Dart>::const_iterator m_ItDarts;
Pierre Kraemer's avatar
Pierre Kraemer committed
92
public:
93
	Traversor2VVaE(const MAP& map, Vertex dart) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
94

95 96 97
	inline Vertex begin() ;
	inline Vertex end() ;
	inline Vertex next() ;
98 99 100 101

	typedef Vertex IterType;
	typedef Vertex ParamType;
	typedef MAP MapType;
Pierre Kraemer's avatar
Pierre Kraemer committed
102 103 104 105
} ;

// Traverse the vertices adjacent to a given vertex through sharing a common face
template <typename MAP>
106
class Traversor2VVaF
Pierre Kraemer's avatar
Pierre Kraemer committed
107 108
{
private:
Sylvain Thery's avatar
Sylvain Thery committed
109
	const MAP& m ;
110 111
	Vertex start ;
	Vertex current ;
Pierre Kraemer's avatar
Pierre Kraemer committed
112

113
	Vertex stop ;
Sylvain Thery's avatar
Sylvain Thery committed
114 115
	const std::vector<Dart>* m_QLT;
	std::vector<Dart>::const_iterator m_ItDarts;
Pierre Kraemer's avatar
Pierre Kraemer committed
116
public:
117
	Traversor2VVaF(const MAP& map, Vertex dart) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
118

119 120 121
	inline Vertex begin() ;
	inline Vertex end() ;
	inline Vertex next() ;
122 123 124 125

	typedef Vertex IterType;
	typedef Vertex ParamType;
	typedef MAP MapType;
Pierre Kraemer's avatar
Pierre Kraemer committed
126 127 128 129 130 131 132 133
} ;

/*******************************************************************************
					EDGE CENTERED TRAVERSALS
*******************************************************************************/

// Traverse the vertices incident to a given edge
template <typename MAP>
134
class Traversor2EV
Pierre Kraemer's avatar
Pierre Kraemer committed
135 136
{
private:
Sylvain Thery's avatar
Sylvain Thery committed
137
	const MAP& m ;
138 139
	Vertex start ;
	Vertex current ;
Sylvain Thery's avatar
Sylvain Thery committed
140 141
	const std::vector<Dart>* m_QLT;
	std::vector<Dart>::const_iterator m_ItDarts;
Pierre Kraemer's avatar
Pierre Kraemer committed
142
public:
143
	Traversor2EV(const MAP& map, Edge dart) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
144

145 146 147
	inline Vertex begin() ;
	inline Vertex end() ;
	inline Vertex next() ;
148 149 150 151

	typedef Vertex IterType;
	typedef Edge ParamType;
	typedef MAP MapType;
Pierre Kraemer's avatar
Pierre Kraemer committed
152 153 154 155
} ;

// Traverse the faces incident to a given edge
template <typename MAP>
156
class Traversor2EF
Pierre Kraemer's avatar
Pierre Kraemer committed
157 158
{
private:
Sylvain Thery's avatar
Sylvain Thery committed
159
	const MAP& m ;
160 161
	Face start ;
	Face current ;
Sylvain Thery's avatar
Sylvain Thery committed
162 163
	const std::vector<Dart>* m_QLT;
	std::vector<Dart>::const_iterator m_ItDarts;
Pierre Kraemer's avatar
Pierre Kraemer committed
164
public:
165
	Traversor2EF(const MAP& map, Edge dart) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
166

167 168 169
	inline Face begin() ;
	inline Face end() ;
	inline Face next() ;
170 171 172 173

	typedef Face IterType;
	typedef Edge ParamType;
	typedef MAP MapType;
Pierre Kraemer's avatar
Pierre Kraemer committed
174 175 176 177
} ;

// Traverse the edges adjacent to a given edge through sharing a common vertex
template <typename MAP>
178
class Traversor2EEaV
Pierre Kraemer's avatar
Pierre Kraemer committed
179 180
{
private:
Sylvain Thery's avatar
Sylvain Thery committed
181
	const MAP& m ;
182 183
	Edge start ;
	Edge current ;
Pierre Kraemer's avatar
Pierre Kraemer committed
184

185
	Edge stop1, stop2 ;
Sylvain Thery's avatar
Sylvain Thery committed
186 187
	const std::vector<Dart>* m_QLT;
	std::vector<Dart>::const_iterator m_ItDarts;
Pierre Kraemer's avatar
Pierre Kraemer committed
188
public:
189
	Traversor2EEaV(const MAP& map, Edge dart) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
190

191 192 193
	inline Edge begin() ;
	inline Edge end() ;
	inline Edge next() ;
194 195 196 197

	typedef Edge IterType;
	typedef Edge ParamType;
	typedef MAP MapType;
Pierre Kraemer's avatar
Pierre Kraemer committed
198 199 200 201
} ;

// Traverse the edges adjacent to a given edge through sharing a common face
template <typename MAP>
202
class Traversor2EEaF
Pierre Kraemer's avatar
Pierre Kraemer committed
203 204
{
private:
Sylvain Thery's avatar
Sylvain Thery committed
205
	const MAP& m ;
206 207
	Edge start ;
	Edge current ;
Pierre Kraemer's avatar
Pierre Kraemer committed
208

209
	Edge stop1, stop2 ;
Sylvain Thery's avatar
Sylvain Thery committed
210 211
	const std::vector<Dart>* m_QLT;
	std::vector<Dart>::const_iterator m_ItDarts;
Pierre Kraemer's avatar
Pierre Kraemer committed
212
public:
213
	Traversor2EEaF(const MAP& map, Edge dart) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
214

215 216 217
	inline Edge begin() ;
	inline Edge end() ;
	inline Edge next() ;
218 219 220 221

	typedef Edge IterType;
	typedef Edge ParamType;
	typedef MAP MapType;
Pierre Kraemer's avatar
Pierre Kraemer committed
222 223 224 225 226 227 228 229
} ;

/*******************************************************************************
					FACE CENTERED TRAVERSALS
*******************************************************************************/

// Traverse the vertices incident to a given face
template <typename MAP>
230
class Traversor2FV
Pierre Kraemer's avatar
Pierre Kraemer committed
231 232
{
private:
Sylvain Thery's avatar
Sylvain Thery committed
233
	const MAP& m ;
234 235
	Vertex start ;
	Vertex current ;
Sylvain Thery's avatar
Sylvain Thery committed
236 237
	const std::vector<Dart>* m_QLT;
	std::vector<Dart>::const_iterator m_ItDarts;
Pierre Kraemer's avatar
Pierre Kraemer committed
238
public:
239
	Traversor2FV(const MAP& map, Face dart) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
240

241 242 243
	inline Vertex begin() ;
	inline Vertex end() ;
	inline Vertex next() ;
244 245 246 247

	typedef Vertex IterType;
	typedef Face ParamType;
	typedef MAP MapType;
Pierre Kraemer's avatar
Pierre Kraemer committed
248 249
} ;

250

251 252 253 254 255 256 257 258 259
//// Traverse the edges incident to a given face (equivalent to vertices)
//template <typename MAP>
//class Traversor2FE: public Traversor2FV<MAP>
//{
//public:
//	Traversor2FE(const MAP& map, Dart dart):Traversor2FV<MAP>(map,dart){}
//} ;

// Traverse the vertices incident to a given face
Pierre Kraemer's avatar
Pierre Kraemer committed
260
template <typename MAP>
261
class Traversor2FE
Pierre Kraemer's avatar
Pierre Kraemer committed
262
{
263 264 265 266 267 268
private:
	const MAP& m ;
	Edge start ;
	Edge current ;
	const std::vector<Dart>* m_QLT;
	std::vector<Dart>::const_iterator m_ItDarts;
Pierre Kraemer's avatar
Pierre Kraemer committed
269
public:
270 271 272 273 274
	Traversor2FE(const MAP& map, Face dart) ;

	inline Edge begin() ;
	inline Edge end() ;
	inline Edge next() ;
275 276 277 278

	typedef Edge IterType;
	typedef Face ParamType;
	typedef MAP MapType;
Pierre Kraemer's avatar
Pierre Kraemer committed
279 280
} ;

281

Pierre Kraemer's avatar
Pierre Kraemer committed
282 283
// Traverse the faces adjacent to a given face through sharing a common vertex
template <typename MAP>
284
class Traversor2FFaV
Pierre Kraemer's avatar
Pierre Kraemer committed
285 286
{
private:
Sylvain Thery's avatar
Sylvain Thery committed
287
	const MAP& m ;
288 289
	Face start ;
	Face current ;
Pierre Kraemer's avatar
Pierre Kraemer committed
290

291
	Face stop ;
Sylvain Thery's avatar
Sylvain Thery committed
292 293
	const std::vector<Dart>* m_QLT;
	std::vector<Dart>::const_iterator m_ItDarts;
Pierre Kraemer's avatar
Pierre Kraemer committed
294
public:
295
	Traversor2FFaV(const MAP& map, Face dart) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
296

297 298 299
	inline Face begin() ;
	inline Face end() ;
	inline Face next() ;
300 301 302 303

	typedef Face IterType;
	typedef Face ParamType;
	typedef MAP MapType;
Pierre Kraemer's avatar
Pierre Kraemer committed
304 305
} ;

Pierre Kraemer's avatar
Pierre Kraemer committed
306
// Traverse the faces adjacent to a given face through sharing a common edge
thery's avatar
thery committed
307
// Warning mult-incidence is not managed (some faces can be send several times)
Pierre Kraemer's avatar
Pierre Kraemer committed
308
template <typename MAP>
309
class Traversor2FFaE
Pierre Kraemer's avatar
Pierre Kraemer committed
310 311
{
private:
Sylvain Thery's avatar
Sylvain Thery committed
312
	const MAP& m ;
313 314
	Face start ;
	Face current ;
Sylvain Thery's avatar
Sylvain Thery committed
315 316
	const std::vector<Dart>* m_QLT;
	std::vector<Dart>::const_iterator m_ItDarts;
Pierre Kraemer's avatar
Pierre Kraemer committed
317
public:
318
	Traversor2FFaE(const MAP& map, Face dart) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
319

320 321 322
	inline Face begin() ;
	inline Face end() ;
	inline Face next() ;
323 324 325 326

	typedef Face IterType;
	typedef Face ParamType;
	typedef MAP MapType;
Pierre Kraemer's avatar
Pierre Kraemer committed
327 328
} ;

329 330 331 332 333

template <typename MAP, unsigned int F, unsigned int T>
class IncidentTrav2
{
public:
334 335
	IncidentTrav2(const MAP&, Cell<F>) {}

336 337 338 339 340 341 342 343
};


template <typename MAP>
class IncidentTrav2<MAP,VERTEX,EDGE>
{
public:
	Traversor2VE<MAP> t;
344
	IncidentTrav2(const MAP& m, Vertex d):t(m,d) {}
345 346 347 348 349 350 351
};

template <typename MAP>
class IncidentTrav2<MAP,VERTEX,FACE>
{
public:
	Traversor2VF<MAP> t;
352
	IncidentTrav2(const MAP& m, Vertex d):t(m,d) {}
353 354 355 356 357 358 359
};

template <typename MAP>
class IncidentTrav2<MAP,EDGE,VERTEX>
{
public:
	Traversor2EV<MAP> t;
360
	IncidentTrav2(const MAP& m, Edge d):t(m,d) {}
361 362 363 364 365 366 367
};

template <typename MAP>
class IncidentTrav2<MAP,EDGE,FACE>
{
public:
	Traversor2EF<MAP> t;
368
	IncidentTrav2(const MAP& m, Edge d):t(m,d) {}
369 370 371 372 373 374 375
};

template <typename MAP>
class IncidentTrav2<MAP,FACE,VERTEX>
{
public:
	Traversor2FV<MAP> t;
376
	IncidentTrav2(const MAP& m, Face d):t(m,d) {}
377 378 379 380 381 382 383
};

template <typename MAP>
class IncidentTrav2<MAP,FACE,EDGE>
{
public:
	Traversor2FE<MAP> t;
384
	IncidentTrav2(const MAP& m, Face d):t(m,d) {}
385 386 387 388 389 390 391 392
};



template <typename MAP, unsigned int F, unsigned int T>
class AdjacentTrav2
{
public:
393
	AdjacentTrav2(const MAP&, Cell<F>) {}
394 395 396 397 398 399 400 401
};


template <typename MAP>
class AdjacentTrav2<MAP,VERTEX,EDGE>
{
public:
	Traversor2VVaE<MAP> t;
402
	AdjacentTrav2(const MAP& m, Vertex d):t(m,d) {}
403 404 405 406 407 408 409
};

template <typename MAP>
class AdjacentTrav2<MAP,VERTEX,FACE>
{
public:
	Traversor2VVaF<MAP> t;
410
	AdjacentTrav2(const MAP& m, Vertex d):t(m,d) {}
411 412 413 414 415 416 417
};

template <typename MAP>
class AdjacentTrav2<MAP,EDGE,VERTEX>
{
public:
	Traversor2EEaV<MAP> t;
418
	AdjacentTrav2(const MAP& m, Edge d):t(m,d) {}
419 420 421 422 423 424 425
};

template <typename MAP>
class AdjacentTrav2<MAP,EDGE,FACE>
{
public:
	Traversor2EEaF<MAP> t;
426
	AdjacentTrav2(const MAP& m, Edge d):t(m,d) {}
427 428 429 430 431 432 433
};

template <typename MAP>
class AdjacentTrav2<MAP,FACE,VERTEX>
{
public:
	Traversor2FFaV<MAP> t;
434
	AdjacentTrav2(const MAP& m, Face d):t(m,d) {}
435 436 437 438 439 440 441
};

template <typename MAP>
class AdjacentTrav2<MAP,FACE,EDGE>
{
public:
	Traversor2FFaE<MAP> t;
442
	AdjacentTrav2(const MAP& m, Face d):t(m,d) {}
443 444
};

445
// foreach traversal function
446

Pierre Kraemer's avatar
Pierre Kraemer committed
447
template <unsigned int ORBIT_TO, unsigned int ORBIT_FROM, typename MAP, typename FUNC>
Pierre Kraemer's avatar
Pierre Kraemer committed
448
inline void foreach_incident2(MAP& map, Cell<ORBIT_FROM> c, FUNC f)
449 450 451 452 453 454
{
	IncidentTrav2<MAP,ORBIT_FROM,ORBIT_TO> trav(const_cast<const MAP&>(map),c);
	for (Cell<ORBIT_TO> c = trav.t.begin(), e = trav.t.end(); c.dart != e.dart; c = trav.t.next())
		f(c);
}

455
template <unsigned int THRU, unsigned int ORBIT, typename MAP, typename FUNC>
Pierre Kraemer's avatar
Pierre Kraemer committed
456
inline void foreach_adjacent2(MAP& map, Cell<ORBIT> c, FUNC f)
457 458 459 460 461 462
{
	AdjacentTrav2<MAP,ORBIT,THRU> trav(const_cast<const MAP&>(map),c);
	for (Cell<ORBIT> c = trav.t.begin(), e = trav.t.end(); c.dart != e.dart; c = trav.t.next())
		f(c);
}

463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597


/**
 * template classs that add iterator to Traversor
 * to allow the use of c++11 syntax for (auto d : v)
 */
template <typename TRAV>
class Iteratorize: public TRAV
{
public:
	typedef typename TRAV::MapType MAP;
	typedef typename TRAV::IterType ITER;
	typedef typename TRAV::ParamType PARAM;

	Iteratorize(const MAP& map, PARAM p):
		TRAV(map,p){}

	class iterator
	{
		Iteratorize<TRAV>* m_ptr;
		ITER m_index;

	public:

		inline iterator(Iteratorize<TRAV>* p, ITER i): m_ptr(p),m_index(i){}

		inline iterator& operator++()
		{
			m_index = m_ptr->next();
			return *this;
		}

		inline ITER& operator*()
		{
			return m_index;
		}

		inline bool operator!=(const iterator& it)
		{
			return m_index.dart != it.m_index.dart;
		}

	};

	inline iterator begin()
	{
		return iterator(this,TRAV::begin());
	}

	inline iterator end()
	{
		return iterator(this,TRAV::end());
	}

};

// functions that return the traversor+iterator
// functions instead of typedef because function
// allows the compiler to deduce template param

template <typename MAP>
inline Iteratorize< Traversor2VE<MAP> > edgesIncidentToVertex2(const MAP& m, Vertex c)
{
	return Iteratorize< Traversor2VE<MAP> >(m, c);
}

template <typename MAP>
inline Iteratorize< Traversor2VF<MAP> > facesIncidentToVertex2(const MAP& m, Vertex c)
{
	return Iteratorize< Traversor2VF<MAP> >(m, c);
}

template <typename MAP>
inline Iteratorize< Traversor2EV<MAP> > verticesIncidentToEdge2(const MAP& m, Edge c)
{
	return Iteratorize< Traversor2EV<MAP> >(m, c);
}

template <typename MAP>
inline Iteratorize< Traversor2EF<MAP> > facesIncidentToEdge2(const MAP& m, Edge c)
{
	return Iteratorize< Traversor2EF<MAP> >(m, c);
}

template <typename MAP>
inline Iteratorize< Traversor2FV<MAP> > verticesIncidentToFace2(const MAP& m, Face c)
{
	return Iteratorize< Traversor2FV<MAP> >(m, c);
}

template <typename MAP>
inline Iteratorize< Traversor2FE<MAP> > edgesIncidentToFace2(const MAP& m, Face c)
{
	return Iteratorize< Traversor2FE<MAP> >(m, c);
}


template <typename MAP>
inline Iteratorize< Traversor2VVaE<MAP> > verticesAdjacentByEdge2(const MAP& m, Vertex c)
{
	return Iteratorize< Traversor2VVaE<MAP> >(m, c);
}

template <typename MAP>
inline Iteratorize< Traversor2VVaF<MAP> > verticesAdjacentByFace2(const MAP& m, Vertex c)
{
	return Iteratorize< Traversor2VVaF<MAP> >(m, c);
}

template <typename MAP>
inline Iteratorize< Traversor2EEaV<MAP> > edgesAdjacentByVertex2(const MAP& m, Edge c)
{
	return Iteratorize< Traversor2EEaV<MAP> >(m, c);
}

template <typename MAP>
inline Iteratorize< Traversor2EEaF<MAP> > edgesAdjacentByFace2(const MAP& m, Edge c)
{
	return Iteratorize< Traversor2EEaF<MAP> >(m, c);
}

template <typename MAP>
inline Iteratorize< Traversor2FFaV<MAP> > facesAdjacentByVertex2(const MAP& m, Face c)
{
	return Iteratorize< Traversor2FFaV<MAP> >(m, c);
}

template <typename MAP>
inline Iteratorize< Traversor2FFaE<MAP> > facesAdjacentByEdge2(const MAP& m, Face c)
{
	return Iteratorize< Traversor2FFaE<MAP> >(m, c);
}



Pierre Kraemer's avatar
Pierre Kraemer committed
598 599
} // namespace CGoGN

600
#include "Topology/generic/traversor/traversor2.hpp"
Pierre Kraemer's avatar
Pierre Kraemer committed
601

Pierre Kraemer's avatar
Pierre Kraemer committed
602
#endif