traversorCell.hpp 20.8 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 <vector>
28 29 30 31

namespace CGoGN
{

32
template <typename MAP, unsigned int ORBIT, TraversalOptim OPT>
33 34 35 36 37 38 39
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)
40
{
Pierre Kraemer's avatar
Pierre Kraemer committed
41 42
	dimension = map.dimension();

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Sylvain Thery's avatar
Sylvain Thery committed
321 322


Sylvain Thery's avatar
Sylvain Thery committed
323

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



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

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

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

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




Sylvain Thery's avatar
Sylvain Thery committed
497 498 499 500 501
template <unsigned int ORBIT, typename MAP, typename FUNC>
inline void foreach_cell(const MAP& map, FUNC f, TraversalOptim opt, unsigned int thread)
{
	switch(opt)
	{
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
		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
531 532 533 534 535 536 537 538
	}
}

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


//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
649 650 651 652 653 654 655 656 657 658 659 660 661 662 663
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;
	boost::barrier& m_sync1;
	boost::barrier& m_sync2;
	bool& m_finished;
	unsigned int m_id;
	FUNC m_lambda;
664

Sylvain Thery's avatar
Sylvain Thery committed
665 666 667 668 669 670 671 672 673 674 675 676 677 678
public:
	ThreadFunction(FUNC func, std::vector<CELL>& vd, boost::barrier& s1, boost::barrier& s2, bool& finished, unsigned int id):
		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)
679
				m_lambda(*it, m_id);
Sylvain Thery's avatar
Sylvain Thery committed
680
			m_cells.clear();
Sylvain Thery's avatar
Sylvain Thery committed
681 682 683 684 685 686 687
			m_sync1.wait(); // wait every body has finished
			m_sync2.wait(); // wait vectors has been refilled
		}
	}
};


688
template <TraversalOptim OPT, unsigned int ORBIT, typename MAP, typename FUNC>
Sylvain Thery's avatar
Sylvain Thery committed
689
void foreach_cell_tmpl(MAP& map, FUNC func, bool needMarkers, unsigned int nbth)
Sylvain Thery's avatar
Sylvain Thery committed
690
{
Sylvain Thery's avatar
Sylvain Thery committed
691
	// buffer for cell traversing
Sylvain Thery's avatar
Sylvain Thery committed
692 693 694 695 696
	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;
697
	TraversorCell<MAP, ORBIT, OPT> trav(map);
Sylvain Thery's avatar
Sylvain Thery committed
698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 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 762 763 764 765 766
	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();
	}
	boost::barrier sync1(nbth+1);
	boost::barrier sync2(nbth+1);
	bool finished=false;
	// lauch threads
	if (needMarkers)
	{
		unsigned int nbth_prec = map.getNbThreadMarkers();
		if (nbth_prec < nbth+1)
			map.addThreadMarker(nbth+1-nbth_prec);
	}

	boost::thread** threads = new boost::thread*[nbth];
	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);
		threads[i] = new boost::thread( boost::ref( *(tfs[i]) ) );
	}

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

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

793
} // namespace Parallel
Sylvain Thery's avatar
Sylvain Thery committed
794

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