traversorCell.hpp 20.6 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 26 27
//#include <boost/thread.hpp>
//#include <boost/thread/barrier.hpp>
#include "Utils/threadbarrier.h"
Sylvain Thery's avatar
Sylvain Thery committed
28
#include <vector>
29 30 31 32

namespace CGoGN
{

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

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

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

82
template <typename MAP, unsigned int ORBIT, TraversalOptim OPT>
83 84 85 86 87 88 89 90 91 92 93
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
94

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

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

127 128 129
			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
130

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

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

146 147
			if(current.dart == m.end())
				current.dart = NIL ;
148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164
			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] ;
			}
165 166
			else
			{
167 168 169 170 171 172 173 174 175 176 177 178 179 180
				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 ;
181
				else
182 183 184 185 186 187
				{
					if(dmark)
						dmark->markOrbit(current) ;
					else
						cmark->mark(current) ;
				}
188 189
			}
		}
190 191 192
			break;
		default:
			break;
193
	}
194

195
	firstTraversal = false ;
196 197 198
	return current ;
}

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

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

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

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

Sylvain Thery's avatar
Sylvain Thery committed
322 323


Sylvain Thery's avatar
Sylvain Thery committed
324

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



335
template <typename MAP, unsigned int ORBIT, TraversalOptim OPT>
336
Cell<ORBIT> TraversorCellOdd<MAP, ORBIT, OPT>::begin()
Sylvain Thery's avatar
Sylvain Thery committed
337
{
338
	switch(OPT)
Sylvain Thery's avatar
Sylvain Thery committed
339
	{
340
		case FORCE_DART_MARKING:
341
		{
342 343 344 345 346 347 348 349
			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) ;
350
		}
351 352
			break;
		case FORCE_CELL_MARKING:
Sylvain Thery's avatar
Sylvain Thery committed
353
		{
354 355 356 357 358 359
			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 ;
360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376
			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
377
			else
378
			{
379 380 381 382 383 384
				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 ;
385
				else
386 387 388 389 390 391
				{
					if(this->dmark)
						this->dmark->unmarkOrbit(this->current) ;
					else
						this->cmark->unmark(this->current) ;
				}
392
			}
Sylvain Thery's avatar
Sylvain Thery committed
393
		}
394 395 396
			break;
		default:
			break;
Sylvain Thery's avatar
Sylvain Thery committed
397 398 399 400
	}
	return this->current ;
}

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

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

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




Sylvain Thery's avatar
Sylvain Thery committed
498 499 500 501 502
template <unsigned int ORBIT, typename MAP, typename FUNC>
inline void foreach_cell(const MAP& map, FUNC f, TraversalOptim opt, unsigned int thread)
{
	switch(opt)
	{
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
		case FORCE_DART_MARKING:
		{
			TraversorCell<MAP, ORBIT,FORCE_DART_MARKING> trav(map, false, thread);
			for (Cell<ORBIT> c = trav.begin(), e = trav.end(); c.dart != e.dart; c = trav.next())
				f(c);
		}
			break;
		case FORCE_CELL_MARKING:
		{
			TraversorCell<MAP, ORBIT,FORCE_CELL_MARKING> trav(map, false, thread);
			for (Cell<ORBIT> c = trav.begin(), e = trav.end(); c.dart != e.dart; c = trav.next())
				f(c);
		}
			break;
		case FORCE_QUICK_TRAVERSAL:
		{
			TraversorCell<MAP, ORBIT,FORCE_QUICK_TRAVERSAL> trav(map, false, thread);
			for (Cell<ORBIT> c = trav.begin(), e = trav.end(); c.dart != e.dart; c = trav.next())
				f(c);
		}
			break;
		case AUTO:
		default:
		{
			TraversorCell<MAP, ORBIT,AUTO> trav(map, false, thread);
			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
532 533 534 535 536 537 538 539
	}
}

template <unsigned int ORBIT, typename MAP, typename FUNC>
inline void foreach_cell_until(const MAP& map, FUNC f, TraversalOptim opt, unsigned int thread)
{
	switch(opt)
	{
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
		case FORCE_DART_MARKING:
		{
			TraversorCell<MAP, ORBIT,FORCE_DART_MARKING> trav(map, false, thread);
			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:
		{
			TraversorCell<MAP, ORBIT,FORCE_CELL_MARKING> trav(map, false, thread);
			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:
		{
			TraversorCell<MAP, ORBIT,FORCE_QUICK_TRAVERSAL> trav(map, false, thread);
			for (Cell<ORBIT> c = trav.begin(), e = trav.end(); c.dart != e.dart; c = trav.next())
				if (!f(c))
					break;
		}
			break;
		case AUTO:
		default:
		{
			TraversorCell<MAP, ORBIT,AUTO> trav(map, false, thread);
			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
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 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649
	}
}


//template <unsigned int ORBIT, typename MAP, typename FUNC, typename FUNC2>
//inline void foreach_cell_EvenOdd(const MAP& map, FUNC f, FUNC2 g, unsigned int nbpasses, TraversalOptim opt, unsigned int thread)
//{
//	switch(opt)
//	{
//	case FORCE_DART_MARKING:
//	{
//		TraversorCell<MAP,ORBIT,FORCE_DART_MARKING> trav(map, false, thread);
//		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:
//	{
//		TraversorCell<MAP,ORBIT,FORCE_CELL_MARKING> trav(map, false, thread);
//		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:
//	{
//		TraversorCell<MAP,ORBIT,FORCE_QUICK_TRAVERSAL> trav(map, false, thread);
//		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:
//	{
//		TraversorCell<MAP,ORBIT,AUTO> trav(map, false, thread);
//		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
650 651 652 653 654 655 656 657 658 659
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
660 661
	Utils::Barrier& m_sync1;
	Utils::Barrier& m_sync2;
Sylvain Thery's avatar
Sylvain Thery committed
662 663 664
	bool& m_finished;
	unsigned int m_id;
	FUNC m_lambda;
665

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

	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){}

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


689
template <TraversalOptim OPT, unsigned int ORBIT, typename MAP, typename FUNC>
Sylvain Thery's avatar
Sylvain Thery committed
690
void foreach_cell_tmpl(MAP& map, FUNC func, unsigned int nbth)
Sylvain Thery's avatar
Sylvain Thery committed
691
{
Sylvain Thery's avatar
Sylvain Thery committed
692
	// buffer for cell traversing
Sylvain Thery's avatar
Sylvain Thery committed
693 694 695 696 697
	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;
698
	TraversorCell<MAP, ORBIT, OPT> trav(map);
Sylvain Thery's avatar
Sylvain Thery committed
699 700 701 702 703 704 705 706
	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
707 708
	Utils::Barrier sync1(nbth+1);
	Utils::Barrier sync2(nbth+1);
Sylvain Thery's avatar
Sylvain Thery committed
709 710
	bool finished=false;

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

	for (unsigned int i = 0; i < nbth; ++i)
	{
		tfs[i] = new ThreadFunction<ORBIT,FUNC>(func, vd[i],sync1,sync2, finished,1+i);
Sylvain Thery's avatar
Sylvain Thery committed
718
		threads[i] = new std::thread( std::ref( *(tfs[i]) ) );
Sylvain Thery's avatar
Sylvain Thery committed
719 720 721 722 723 724 725 726 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 752 753 754 755 756 757 758 759 760 761
	}

	// 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
	}

	sync1.wait();// wait for all thread to finish its vector
	finished = true;// say finsih to everyone
	sync2.wait(); // just wait for last barrier wait !


	//wait for all theads to be finished
	for (unsigned int i = 0; i < nbth; ++i)
	{
		threads[i]->join();
		delete threads[i];
		delete tfs[i];
	}
	delete[] tfs;
	delete[] threads;
	delete[] vd;
	delete[] tempo;
}

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

788
} // namespace Parallel
Sylvain Thery's avatar
Sylvain Thery committed
789

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