traversorCell.hpp 20.9 KB
Newer Older
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           *
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/                                           *
21 22 23
* Contact information: cgogn@unistra.fr                                        *
*                                                                              *
*******************************************************************************/
24

Sylvain Thery's avatar
Sylvain Thery committed
25
#include "Utils/threadbarrier.h"
Sylvain Thery's avatar
Sylvain Thery committed
26
#include <vector>
27 28 29 30

namespace CGoGN
{

31
template <typename MAP, unsigned int ORBIT, TraversalOptim OPT>
Sylvain Thery's avatar
Sylvain Thery committed
32
TraversorCell<MAP, ORBIT, OPT>::TraversorCell(const MAP& map, bool forceDartMarker) :
33 34 35 36 37 38
	m(map),
	dmark(NULL),
	cmark(NULL),
	quickTraversal(NULL),
	current(NIL),
	firstTraversal(true)
39
{
Pierre Kraemer's avatar
Pierre Kraemer committed
40 41
	dimension = map.dimension();

42
	switch(OPT)
Pierre Kraemer's avatar
Pierre Kraemer committed
43
	{
44
		case FORCE_DART_MARKING:
Sylvain Thery's avatar
Sylvain Thery committed
45
			dmark = new DartMarker<MAP>(map) ;
46 47
			break;
		case FORCE_CELL_MARKING:
Sylvain Thery's avatar
Sylvain Thery committed
48
			cmark = new CellMarker<MAP, ORBIT>(map) ;
49 50
			break;
		case FORCE_QUICK_TRAVERSAL:
51
			quickTraversal = map.template getQuickTraversal<ORBIT>() ;
52 53 54 55 56
			assert(quickTraversal != NULL);
			cont = &(map.template getAttributeContainer<ORBIT>()) ;
			break;
		case AUTO:
			if(forceDartMarker)
Sylvain Thery's avatar
Sylvain Thery committed
57
				dmark = new DartMarker<MAP>(map) ;
58
			else
59
			{
60 61 62 63 64 65
				quickTraversal = map.template getQuickTraversal<ORBIT>() ;
				if(quickTraversal != NULL)
				{
					cont = &(map.template getAttributeContainer<ORBIT>()) ;

				}
66
				else
67 68
				{
					if(map.template isOrbitEmbedded<ORBIT>())
Sylvain Thery's avatar
Sylvain Thery committed
69
						cmark = new CellMarker<MAP, ORBIT>(map) ;
70
					else
Sylvain Thery's avatar
Sylvain Thery committed
71
						dmark = new DartMarker<MAP>(map) ;
72
				}
73
			}
74 75 76
			break;
		default:
			break;
Pierre Kraemer's avatar
Pierre Kraemer committed
77
	}
78 79
}

80
template <typename MAP, unsigned int ORBIT, TraversalOptim OPT>
81 82 83 84 85 86 87 88 89 90 91
TraversorCell<MAP, ORBIT, OPT>::TraversorCell(const TraversorCell<MAP, ORBIT, OPT>& tc) :
	m(tc.m),
	dimension(tc.dimension),
	cont(tc.cont),
	qCurrent(tc.qCurrent),
	dmark(tc.dmark),
	cmark(tc.cmark),
	quickTraversal(tc.quickTraversal),
	current(tc.current),
	firstTraversal(tc.firstTraversal)
{}
Sylvain Thery's avatar
Sylvain Thery committed
92

93 94
template <typename MAP, unsigned int ORBIT, TraversalOptim OPT>
TraversorCell<MAP, ORBIT,OPT>::~TraversorCell()
95
{
96 97
	switch(OPT)
	{
98
		case FORCE_DART_MARKING:
99
			delete dmark ;
100 101
			break;
		case FORCE_CELL_MARKING:
102
			delete cmark ;
103 104 105 106 107 108 109 110 111
			break;
		case AUTO:
			if(dmark)
				delete dmark ;
			else if(cmark)
				delete cmark ;
			break;
		default:
			break;
112
	}
113 114
}

115
template <typename MAP, unsigned int ORBIT, TraversalOptim OPT>
116
Cell<ORBIT> TraversorCell<MAP, ORBIT, OPT>::begin()
117
{
118
	switch(OPT)
119
	{
120 121 122 123
		case FORCE_DART_MARKING:
		{
			if(!firstTraversal)
				dmark->unmarkAll() ;
Pierre Kraemer's avatar
Pierre Kraemer committed
124

125 126 127
			current.dart = m.begin() ;
			while(current.dart != m.end() && (m.isBoundaryMarked(dimension, current.dart)))
				m.next(current.dart) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
128

129 130 131 132
			if(current.dart == m.end())
				current.dart = NIL ;
			else
				dmark->markOrbit(current) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
133
		}
134 135
			break;
		case FORCE_CELL_MARKING:
136 137
		{
			if(!firstTraversal)
138
				cmark->unmarkAll() ;
Pierre Kraemer's avatar
Pierre Kraemer committed
139

140
			current.dart = m.begin() ;
141
			while(current.dart != m.end() && (m.isBoundaryMarked(dimension, current.dart)))
142
				m.next(current.dart) ;
143

144 145
			if(current.dart == m.end())
				current.dart = NIL ;
146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162
			else
				cmark->mark(current) ;
		}
			break;
		case FORCE_QUICK_TRAVERSAL:
		{
			qCurrent = cont->begin() ;
			current.dart = (*quickTraversal)[qCurrent] ;
		}
			break;
		case AUTO:
		{
			if(quickTraversal != NULL)
			{
				qCurrent = cont->begin() ;
				current.dart = (*quickTraversal)[qCurrent] ;
			}
163 164
			else
			{
165 166 167 168 169 170 171 172 173 174 175 176 177 178
				if(!firstTraversal)
				{
					if(dmark)
						dmark->unmarkAll() ;
					else
						cmark->unmarkAll() ;
				}

				current.dart = m.begin() ;
				while(current.dart != m.end() && (m.isBoundaryMarked(dimension, current.dart)))
					m.next(current.dart) ;

				if(current.dart == m.end())
					current.dart = NIL ;
179
				else
180 181 182 183 184 185
				{
					if(dmark)
						dmark->markOrbit(current) ;
					else
						cmark->mark(current) ;
				}
186 187
			}
		}
188 189 190
			break;
		default:
			break;
191
	}
192

193
	firstTraversal = false ;
194 195 196
	return current ;
}

197
template <typename MAP, unsigned int ORBIT, TraversalOptim OPT>
198
Cell<ORBIT> TraversorCell<MAP, ORBIT, OPT>::end()
Pierre Kraemer's avatar
Pierre Kraemer committed
199
{
Pierre Kraemer's avatar
Pierre Kraemer committed
200
	return Cell<ORBIT>(NIL) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
201
}
202

203
template <typename MAP, unsigned int ORBIT, TraversalOptim OPT>
204
Cell<ORBIT> TraversorCell<MAP, ORBIT, OPT>::next()
205
{
Pierre Kraemer's avatar
Pierre Kraemer committed
206
	assert(current.dart != NIL);
207 208 209

	switch(OPT)
	{
210
		case FORCE_DART_MARKING:
211
		{
212 213 214 215 216 217 218 219 220 221 222
			bool ismarked = dmark->isMarked(current.dart) ;
			while(current.dart != NIL && (ismarked || m.isBoundaryMarked(dimension, current.dart)))
			{
				m.next(current.dart) ;
				if(current.dart == m.end())
					current.dart = NIL ;
				else
					ismarked = dmark->isMarked(current.dart) ;
			}
			if(current.dart != NIL)
				dmark->markOrbit(current) ;
223
		}
224 225
			break;
		case FORCE_CELL_MARKING:
226
		{
227 228 229 230 231 232 233 234 235 236 237
			bool ismarked = cmark->isMarked(current) ;
			while(current.dart != NIL && (ismarked || m.isBoundaryMarked(dimension, current.dart)))
			{
				m.next(current.dart) ;
				if(current.dart == m.end())
					current.dart = NIL ;
				else
					ismarked = cmark->isMarked(current) ;
			}
			if(current.dart != NIL)
				cmark->mark(current) ;
238
		}
239 240
			break;
		case FORCE_QUICK_TRAVERSAL:
241
		{
242 243 244 245
			cont->next(qCurrent) ;
			if (qCurrent != cont->end())
				current.dart = (*quickTraversal)[qCurrent] ;
			else current.dart = NIL;
246
		}
247 248
			break;
		case AUTO:
249
		{
250
			if(quickTraversal != NULL)
Pierre Kraemer's avatar
Pierre Kraemer committed
251
			{
252 253 254 255
				cont->next(qCurrent) ;
				if (qCurrent != cont->end())
					current.dart = (*quickTraversal)[qCurrent] ;
				else current.dart = NIL;
256 257 258
			}
			else
			{
259
				if(dmark)
260
				{
261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285
					bool ismarked = dmark->isMarked(current.dart) ;
					while(current.dart != NIL && (ismarked || m.isBoundaryMarked(dimension, current.dart)))
					{
						m.next(current.dart) ;
						if(current.dart == m.end())
							current.dart = NIL ;
						else
							ismarked = dmark->isMarked(current.dart) ;
					}
					if(current.dart != NIL)
						dmark->markOrbit(current) ;
				}
				else
				{
					bool ismarked = cmark->isMarked(current) ;
					while(current.dart != NIL && (ismarked || m.isBoundaryMarked(dimension, current.dart) ))
					{
						m.next(current.dart) ;
						if(current.dart == m.end())
							current.dart = NIL ;
						else
							ismarked = cmark->isMarked(current) ;
					}
					if(current.dart != NIL)
						cmark->mark(current) ;
286
				}
Pierre Kraemer's avatar
Pierre Kraemer committed
287
			}
288
		}
289 290 291
			break;
		default:
			break;
292 293 294 295
	}
	return current ;
}

296
template <typename MAP, unsigned int ORBIT, TraversalOptim OPT>
297
void TraversorCell<MAP, ORBIT, OPT>::skip(Cell<ORBIT> c)
298
{
299 300
	switch(OPT)
	{
301 302 303 304
		case FORCE_DART_MARKING:
			dmark->markOrbit(c) ;
			break;
		case FORCE_CELL_MARKING:
305
			cmark->mark(c) ;
306 307 308 309 310 311 312 313 314 315 316
			break;
		case FORCE_QUICK_TRAVERSAL:
			break;
		case AUTO:
			if(dmark)
				dmark->markOrbit(c) ;
			else
				cmark->mark(c) ;
			break;
		default:
			break;
317
	}
318 319
}

Sylvain Thery's avatar
Sylvain Thery committed
320 321


Sylvain Thery's avatar
Sylvain Thery committed
322

323
template <typename MAP, unsigned int ORBIT, TraversalOptim OPT>
324
Cell<ORBIT> TraversorCellEven<MAP, ORBIT, OPT>::begin()
Sylvain Thery's avatar
Sylvain Thery committed
325
{
326
	Cell<ORBIT> c = TraversorCell<MAP, ORBIT, OPT>::begin();
Sylvain Thery's avatar
Sylvain Thery committed
327 328 329 330 331 332
	this->firstTraversal = true;
	return c;
}



333
template <typename MAP, unsigned int ORBIT, TraversalOptim OPT>
334
Cell<ORBIT> TraversorCellOdd<MAP, ORBIT, OPT>::begin()
Sylvain Thery's avatar
Sylvain Thery committed
335
{
336
	switch(OPT)
Sylvain Thery's avatar
Sylvain Thery committed
337
	{
338
		case FORCE_DART_MARKING:
339
		{
340 341 342 343 344 345 346 347
			this->current.dart = this->m.begin() ;
			while(this->current.dart != this->m.end() && (this->m.isBoundaryMarked(this->dimension, this->current.dart) ))
				this->m.next(this->current.dart) ;

			if(this->current.dart == this->m.end())
				this->current.dart = NIL ;
			else
				this->dmark->unmarkOrbit(this->current) ;
348
		}
349 350
			break;
		case FORCE_CELL_MARKING:
Sylvain Thery's avatar
Sylvain Thery committed
351
		{
352 353 354 355 356 357
			this->current.dart = this->m.begin() ;
			while(this->current.dart != this->m.end() && (this->m.isBoundaryMarked(this->dimension, this->current.dart) ))
				this->m.next(this->current.dart) ;

			if(this->current.dart == this->m.end())
				this->current.dart = NIL ;
358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374
			else
				this->cmark->unmark(this->current) ;
		}
			break;
		case FORCE_QUICK_TRAVERSAL:
		{
			this->qCurrent = this->cont->begin() ;
			this->current.dart = this->quickTraversal->operator[](this->qCurrent);
		}
			break;
		case AUTO:
		{
			if(this->quickTraversal != NULL)
			{
				this->qCurrent = this->cont->begin() ;
				this->current.dart = this->quickTraversal->operator[](this->qCurrent);
			}
Sylvain Thery's avatar
Sylvain Thery committed
375
			else
376
			{
377 378 379 380 381 382
				this->current.dart = this->m.begin() ;
				while(this->current.dart != this->m.end() && (this->m.isBoundaryMarked(this->dimension, this->current.dart) ))
					this->m.next(this->current.dart) ;

				if(this->current.dart == this->m.end())
					this->current.dart = NIL ;
383
				else
384 385 386 387 388 389
				{
					if(this->dmark)
						this->dmark->unmarkOrbit(this->current) ;
					else
						this->cmark->unmark(this->current) ;
				}
390
			}
Sylvain Thery's avatar
Sylvain Thery committed
391
		}
392 393 394
			break;
		default:
			break;
Sylvain Thery's avatar
Sylvain Thery committed
395 396 397 398
	}
	return this->current ;
}

399
template <typename MAP, unsigned int ORBIT, TraversalOptim OPT>
400
Cell<ORBIT> TraversorCellOdd<MAP, ORBIT, OPT>::next()
Sylvain Thery's avatar
Sylvain Thery committed
401 402 403
{
	assert(this->current.dart != NIL);

404
	switch(OPT)
Sylvain Thery's avatar
Sylvain Thery committed
405
	{
406
		case FORCE_DART_MARKING:
407
		{
408 409 410 411 412 413 414 415 416 417 418
			bool ismarked = this->dmark->isMarked(this->current.dart) ;
			while(this->current.dart != NIL && (!ismarked || this->m.isBoundaryMarked(this->dimension,this->current.dart)))
			{
				this->m.next(this->current.dart) ;
				if(this->current.dart == this->m.end())
					this->current.dart = NIL ;
				else
					ismarked = this->dmark->isMarked(this->current.dart) ;
			}
			if(this->current.dart != NIL)
				this->dmark->unmarkOrbit(this->current) ;
419
		}
420 421
			break;
		case FORCE_CELL_MARKING:
422
		{
423 424 425 426 427 428 429 430 431 432 433
			bool ismarked = this->cmark->isMarked(this->current) ;
			while(this->current.dart != NIL && (!ismarked || this->m.isBoundaryMarked(this->dimension, this->current.dart) ))
			{
				this->m.next(this->current.dart) ;
				if(this->current.dart == this->m.end())
					this->current.dart = NIL ;
				else
					ismarked = this->cmark->isMarked(this->current) ;
			}
			if(this->current.dart != NIL)
				this->cmark->unmark(this->current) ;
434
		}
435 436
			break;
		case FORCE_QUICK_TRAVERSAL:
Sylvain Thery's avatar
Sylvain Thery committed
437
		{
438 439 440 441
			this->cont->next(this->qCurrent) ;
			if (this->qCurrent != this->cont->end())
				this->current.dart = this->quickTraversal->operator[](this->qCurrent) ;
			else this->current.dart = NIL;
Sylvain Thery's avatar
Sylvain Thery committed
442
		}
443 444
			break;
		case AUTO:
Sylvain Thery's avatar
Sylvain Thery committed
445
		{
446
			if(this->quickTraversal != NULL)
Sylvain Thery's avatar
Sylvain Thery committed
447
			{
448 449 450 451
				this->cont->next(this->qCurrent) ;
				if (this->qCurrent != this->cont->end())
					this->current.dart = this->quickTraversal->operator[](this->qCurrent) ;
				else this->current.dart = NIL;
452 453 454
			}
			else
			{
455
				if(this->dmark)
456
				{
457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481
					bool ismarked = this->dmark->isMarked(this->current.dart) ;
					while(this->current.dart != NIL && (!ismarked || this->m.isBoundaryMarked(this->dimension,this->current.dart)))
					{
						this->m.next(this->current.dart) ;
						if(this->current.dart == this->m.end())
							this->current.dart = NIL ;
						else
							ismarked = this->dmark->isMarked(this->current.dart) ;
					}
					if(this->current.dart != NIL)
						this->dmark->unmarkOrbit(this->current) ;
				}
				else
				{
					bool ismarked = this->cmark->isMarked(this->current) ;
					while(this->current.dart != NIL && (!ismarked || this->m.isBoundaryMarked(this->dimension, this->current.dart) ))
					{
						this->m.next(this->current.dart) ;
						if(this->current.dart == this->m.end())
							this->current.dart = NIL ;
						else
							ismarked = this->cmark->isMarked(this->current) ;
					}
					if(this->current.dart != NIL)
						this->cmark->unmark(this->current) ;
482
				}
Sylvain Thery's avatar
Sylvain Thery committed
483 484
			}
		}
485 486 487
			break;
		default:
			break;
Sylvain Thery's avatar
Sylvain Thery committed
488
	}
489

Sylvain Thery's avatar
Sylvain Thery committed
490 491 492 493 494 495
	return this->current ;
}




Sylvain Thery's avatar
Sylvain Thery committed
496
template <unsigned int ORBIT, typename MAP, typename FUNC>
Sylvain Thery's avatar
Sylvain Thery committed
497
inline void foreach_cell(const MAP& map, FUNC f, TraversalOptim opt)
Sylvain Thery's avatar
Sylvain Thery committed
498 499 500
{
	switch(opt)
	{
501 502
		case FORCE_DART_MARKING:
		{
Sylvain Thery's avatar
Sylvain Thery committed
503
			TraversorCell<MAP, ORBIT,FORCE_DART_MARKING> trav(map, false);
504 505 506 507 508 509
			for (Cell<ORBIT> c = trav.begin(), e = trav.end(); c.dart != e.dart; c = trav.next())
				f(c);
		}
			break;
		case FORCE_CELL_MARKING:
		{
Sylvain Thery's avatar
Sylvain Thery committed
510
			TraversorCell<MAP, ORBIT,FORCE_CELL_MARKING> trav(map, false);
511 512 513 514 515 516
			for (Cell<ORBIT> c = trav.begin(), e = trav.end(); c.dart != e.dart; c = trav.next())
				f(c);
		}
			break;
		case FORCE_QUICK_TRAVERSAL:
		{
Sylvain Thery's avatar
Sylvain Thery committed
517
			TraversorCell<MAP, ORBIT,FORCE_QUICK_TRAVERSAL> trav(map, false);
518 519 520 521 522 523 524
			for (Cell<ORBIT> c = trav.begin(), e = trav.end(); c.dart != e.dart; c = trav.next())
				f(c);
		}
			break;
		case AUTO:
		default:
		{
Sylvain Thery's avatar
Sylvain Thery committed
525
			TraversorCell<MAP, ORBIT,AUTO> trav(map, false);
526 527 528 529
			for (Cell<ORBIT> c = trav.begin(), e = trav.end(); c.dart != e.dart; c = trav.next())
				f(c);
		}
			break;
Sylvain Thery's avatar
Sylvain Thery committed
530 531 532 533
	}
}

template <unsigned int ORBIT, typename MAP, typename FUNC>
Sylvain Thery's avatar
Sylvain Thery committed
534
inline void foreach_cell_until(const MAP& map, FUNC f, TraversalOptim opt)
Sylvain Thery's avatar
Sylvain Thery committed
535 536 537
{
	switch(opt)
	{
538 539
		case FORCE_DART_MARKING:
		{
Sylvain Thery's avatar
Sylvain Thery committed
540
			TraversorCell<MAP, ORBIT,FORCE_DART_MARKING> trav(map, false);
541 542 543 544 545 546 547
			for (Cell<ORBIT> c = trav.begin(), e = trav.end(); c.dart != e.dart; c = trav.next())
				if (!f(c))
					break;
		}
			break;
		case FORCE_CELL_MARKING:
		{
Sylvain Thery's avatar
Sylvain Thery committed
548
			TraversorCell<MAP, ORBIT,FORCE_CELL_MARKING> trav(map, false);
549 550 551 552 553 554 555
			for (Cell<ORBIT> c = trav.begin(), e = trav.end(); c.dart != e.dart; c = trav.next())
				if (!f(c))
					break;
		}
			break;
		case FORCE_QUICK_TRAVERSAL:
		{
Sylvain Thery's avatar
Sylvain Thery committed
556
			TraversorCell<MAP, ORBIT,FORCE_QUICK_TRAVERSAL> trav(map, false);
557 558 559 560 561 562 563 564
			for (Cell<ORBIT> c = trav.begin(), e = trav.end(); c.dart != e.dart; c = trav.next())
				if (!f(c))
					break;
		}
			break;
		case AUTO:
		default:
		{
Sylvain Thery's avatar
Sylvain Thery committed
565
			TraversorCell<MAP, ORBIT,AUTO> trav(map, false);
566 567 568 569 570
			for (Cell<ORBIT> c = trav.begin(), e = trav.end(); c.dart != e.dart; c = trav.next())
				if (!f(c))
					break;
		}
			break;
Sylvain Thery's avatar
Sylvain Thery committed
571 572 573 574 575
	}
}


//template <unsigned int ORBIT, typename MAP, typename FUNC, typename FUNC2>
Sylvain Thery's avatar
Sylvain Thery committed
576
//inline void foreach_cell_EvenOdd(const MAP& map, FUNC f, FUNC2 g, unsigned int nbpasses, TraversalOptim opt)
Sylvain Thery's avatar
Sylvain Thery committed
577 578 579 580 581
//{
//	switch(opt)
//	{
//	case FORCE_DART_MARKING:
//	{
Sylvain Thery's avatar
Sylvain Thery committed
582
//		TraversorCell<MAP,ORBIT,FORCE_DART_MARKING> trav(map, false);
Sylvain Thery's avatar
Sylvain Thery committed
583 584 585 586 587 588 589 590 591 592 593 594 595 596
//		TraversorCellEven<MAP,ORBIT,FORCE_DART_MARKING> tr1(trav);
//		TraversorCellOdd<MAP,ORBIT,FORCE_DART_MARKING> tr2(trav);

//		for (unsigned int i=0; i<nbpasses; ++i)
//		{
//			for (Cell<ORBIT> c = trav.begin(), e = trav.end(); c.dart != e.dart; c = trav.next())
//				f(c);
//			for (Cell<ORBIT> c = trav.begin(), e = trav.end(); c.dart != e.dart; c = trav.next())
//				g(c);
//		}
//	}
//	break;
//	case FORCE_CELL_MARKING:
//	{
Sylvain Thery's avatar
Sylvain Thery committed
597
//		TraversorCell<MAP,ORBIT,FORCE_CELL_MARKING> trav(map, false);
Sylvain Thery's avatar
Sylvain Thery committed
598 599 600 601 602 603 604 605 606 607 608 609 610 611
//		TraversorCellEven<MAP,ORBIT,FORCE_CELL_MARKING> tr1(trav);
//		TraversorCellOdd<MAP,ORBIT, FORCE_CELL_MARKING> tr2(trav);

//		for (unsigned int i=0; i<nbpasses; ++i)
//		{
//			for (Cell<ORBIT> c = trav.begin(), e = trav.end(); c.dart != e.dart; c = trav.next())
//				f(c);
//			for (Cell<ORBIT> c = trav.begin(), e = trav.end(); c.dart != e.dart; c = trav.next())
//				g(c);
//		}
//	}
//	break;
//	case FORCE_QUICK_TRAVERSAL:
//	{
Sylvain Thery's avatar
Sylvain Thery committed
612
//		TraversorCell<MAP,ORBIT,FORCE_QUICK_TRAVERSAL> trav(map, false);
Sylvain Thery's avatar
Sylvain Thery committed
613 614 615 616 617 618 619 620 621 622 623 624 625 626 627
//		TraversorCellEven<MAP,ORBIT,FORCE_QUICK_TRAVERSAL> tr1(trav);
//		TraversorCellOdd<MAP,ORBIT,FORCE_QUICK_TRAVERSAL> tr2(trav);

//		for (unsigned int i=0; i<nbpasses; ++i)
//		{
//			for (Cell<ORBIT> c = trav.begin(), e = trav.end(); c.dart != e.dart; c = trav.next())
//				f(c);
//			for (Cell<ORBIT> c = trav.begin(), e = trav.end(); c.dart != e.dart; c = trav.next())
//				g(c);
//		}
//	}
//	break;
//	case AUTO:
//	default:
//	{
Sylvain Thery's avatar
Sylvain Thery committed
628
//		TraversorCell<MAP,ORBIT,AUTO> trav(map, false);
Sylvain Thery's avatar
Sylvain Thery committed
629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647
//		TraversorCellEven<MAP,ORBIT,AUTO> tr1(trav);
//		TraversorCellOdd<MAP,ORBIT,AUTO> tr2(trav);

//		for (unsigned int i=0; i<nbpasses; ++i)
//		{
//			for (Cell<ORBIT> c = trav.begin(), e = trav.end(); c.dart != e.dart; c = trav.next())
//				f(c);
//			for (Cell<ORBIT> c = trav.begin(), e = trav.end(); c.dart != e.dart; c = trav.next())
//				g(c);
//		}
//	}
//	break;
//	}
//}





Sylvain Thery's avatar
Sylvain Thery committed
648 649 650 651 652 653 654 655 656 657
namespace Parallel
{

/// internal functor for boost call
template <unsigned int ORBIT, typename FUNC>
class ThreadFunction
{
protected:
	typedef Cell<ORBIT> CELL;
	std::vector<CELL>& m_cells;
Sylvain Thery's avatar
Sylvain Thery committed
658 659
	Utils::Barrier& m_sync1;
	Utils::Barrier& m_sync2;
Sylvain Thery's avatar
Sylvain Thery committed
660 661 662
	bool& m_finished;
	unsigned int m_id;
	FUNC m_lambda;
663 664
	std::thread::id& m_threadId; // ref on thread::id in table of threads in genericMap for init at operator()

Sylvain Thery's avatar
Sylvain Thery committed
665
public:
Sylvain Thery's avatar
Sylvain Thery committed
666 667
	ThreadFunction(FUNC func, std::vector<CELL>& vd, Utils::Barrier& s1, Utils::Barrier& s2, bool& finished, unsigned int id, std::thread::id& threadId) :
		m_cells(vd), m_sync1(s1), m_sync2(s2), m_finished(finished), m_id(id), m_lambda(func), m_threadId(threadId)
Sylvain Thery's avatar
Sylvain Thery committed
668 669 670 671 672 673
	{
	}

	ThreadFunction(const ThreadFunction<ORBIT, FUNC>& tf):
		m_cells(tf.m_cells), m_sync1(tf.m_sync1), m_sync2(tf.m_sync2), m_finished(tf.m_finished), m_id(tf.m_id), m_lambda(tf.m_lambda){}

674 675
	std::thread::id& getThreadId() { return m_threadId; }

Sylvain Thery's avatar
Sylvain Thery committed
676 677
	void operator()()
	{
Sylvain Thery's avatar
Sylvain Thery committed
678 679 680
		// first thing to do set the thread id in genericMap
		m_threadId = std::this_thread::get_id();

Sylvain Thery's avatar
Sylvain Thery committed
681 682 683
		while (!m_finished)
		{
			for (typename std::vector<CELL>::const_iterator it = m_cells.begin(); it != m_cells.end(); ++it)
684
				m_lambda(*it, m_id);
Sylvain Thery's avatar
Sylvain Thery committed
685
			m_cells.clear();
Sylvain Thery's avatar
Sylvain Thery committed
686 687 688 689 690 691 692
			m_sync1.wait(); // wait every body has finished
			m_sync2.wait(); // wait vectors has been refilled
		}
	}
};


693
template <TraversalOptim OPT, unsigned int ORBIT, typename MAP, typename FUNC>
Sylvain Thery's avatar
Sylvain Thery committed
694
void foreach_cell_tmpl(MAP& map, FUNC func, unsigned int nbth)
Sylvain Thery's avatar
Sylvain Thery committed
695
{
696
	// buffer for cell traversing
Sylvain Thery's avatar
Sylvain Thery committed
697 698 699 700 701
	std::vector< Cell<ORBIT> >* vd = new std::vector< Cell<ORBIT> >[nbth];
	for (unsigned int i = 0; i < nbth; ++i)
		vd[i].reserve(SIZE_BUFFER_THREAD);

	unsigned int nb = 0;
702
	TraversorCell<MAP, ORBIT, OPT> trav(map);
Sylvain Thery's avatar
Sylvain Thery committed
703 704 705 706 707 708 709 710
	Cell<ORBIT> cell = trav.begin();
	Cell<ORBIT> c_end = trav.end();
	while ((cell.dart != c_end.dart) && (nb < nbth*SIZE_BUFFER_THREAD) )
	{
		vd[nb%nbth].push_back(cell);
		nb++;
		cell = trav.next();
	}
Sylvain Thery's avatar
Sylvain Thery committed
711 712
	Utils::Barrier sync1(nbth+1);
	Utils::Barrier sync2(nbth+1);
Sylvain Thery's avatar
Sylvain Thery committed
713 714
	bool finished=false;

Sylvain Thery's avatar
Sylvain Thery committed
715
	// launch threads
Sylvain Thery's avatar
Sylvain Thery committed
716
	std::thread** threads = new std::thread*[nbth];
Sylvain Thery's avatar
Sylvain Thery committed
717 718
	ThreadFunction<ORBIT,FUNC>** tfs = new ThreadFunction<ORBIT,FUNC>*[nbth];

Sylvain Thery's avatar
Sylvain Thery committed
719
	// add place for nbth new threads in the table of threadId in genericmap
720 721
//	unsigned int firstThread = map.addEmptyThreadIds(nbth);

Sylvain Thery's avatar
Sylvain Thery committed
722 723
	for (unsigned int i = 0; i < nbth; ++i)
	{
724 725
		std::thread::id& threadId = map.addEmptyThreadId();
		tfs[i] = new ThreadFunction<ORBIT,FUNC>(func, vd[i], sync1, sync2, finished, 1+i, threadId);
Sylvain Thery's avatar
Sylvain Thery committed
726
		threads[i] = new std::thread( std::ref( *(tfs[i]) ) );
Sylvain Thery's avatar
Sylvain Thery committed
727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751
	}

	// and continue to traverse the map
	std::vector< Cell<ORBIT> >* tempo = new std::vector< Cell<ORBIT> >[nbth];
	for (unsigned int i = 0; i < nbth; ++i)
		tempo[i].reserve(SIZE_BUFFER_THREAD);

	while (cell.dart != c_end.dart)
	{
		for (unsigned int i = 0; i < nbth; ++i)
			tempo[i].clear();
		unsigned int nb = 0;

		while ((cell.dart != c_end.dart) && (nb < nbth*SIZE_BUFFER_THREAD) )
		{
			tempo[nb%nbth].push_back(cell);
			nb++;
			cell = trav.next();
		}
		sync1.wait();// wait for all thread to finish its vector
		for (unsigned int i = 0; i < nbth; ++i)
			vd[i].swap(tempo[i]);
		sync2.wait();// everybody refilled then go
	}

752 753
	sync1.wait(); // wait for all thread to finish its vector
	finished = true; // say finsih to everyone
Sylvain Thery's avatar
Sylvain Thery committed
754 755
	sync2.wait(); // just wait for last barrier wait !

756
	// wait for all theads to be finished
Sylvain Thery's avatar
Sylvain Thery committed
757 758 759 760
	for (unsigned int i = 0; i < nbth; ++i)
	{
		threads[i]->join();
		delete threads[i];
761
		map.removeThreadId(tfs[i]->getThreadId());
Sylvain Thery's avatar
Sylvain Thery committed
762 763
		delete tfs[i];
	}
Sylvain Thery's avatar
Sylvain Thery committed
764

Sylvain Thery's avatar
Sylvain Thery committed
765 766 767 768 769 770
	delete[] tfs;
	delete[] threads;
	delete[] vd;
	delete[] tempo;
}

771
template <unsigned int ORBIT, typename MAP, typename FUNC>
Sylvain Thery's avatar
Sylvain Thery committed
772
void foreach_cell(MAP& map, FUNC func, TraversalOptim opt, unsigned int nbth)
773
{
774 775 776
	if (nbth < 2)
	{
		CGoGNerr << "Warning number of threads must be > 1 for //" << CGoGNendl;
777
		nbth = 2;
778
	}
779 780
	switch(opt)
	{
781
		case FORCE_DART_MARKING:
Sylvain Thery's avatar
Sylvain Thery committed
782
			foreach_cell_tmpl<FORCE_DART_MARKING,ORBIT,MAP,FUNC>(map,func,nbth-1);
783 784
			break;
		case FORCE_CELL_MARKING:
Sylvain Thery's avatar
Sylvain Thery committed
785
			foreach_cell_tmpl<FORCE_CELL_MARKING,ORBIT,MAP,FUNC>(map,func,nbth-1);
786 787
			break;
		case FORCE_QUICK_TRAVERSAL:
Sylvain Thery's avatar
Sylvain Thery committed
788
			foreach_cell_tmpl<FORCE_QUICK_TRAVERSAL,ORBIT,MAP,FUNC>(map,func,nbth-1);
789 790 791
			break;
		case AUTO:
		default:
Sylvain Thery's avatar
Sylvain Thery committed
792
			foreach_cell_tmpl<AUTO,ORBIT,MAP,FUNC>(map,func,nbth-1);
793
			break;
794
	}
Sylvain Thery's avatar
Sylvain Thery committed
795 796
}

797
} // namespace Parallel
Sylvain Thery's avatar
Sylvain Thery committed
798

Pierre Kraemer's avatar
Pierre Kraemer committed
799
} // namespace CGoGN