Création d'un compte pour un collaborateur extérieur au laboratoire depuis l'intranet ICube : https://intranet.icube.unistra.fr/fr/labs/member/profile

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