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

namespace CGoGN
{

29
30
31
//**********************
// Marker for traversor
//**********************
Pierre Kraemer's avatar
Pierre Kraemer committed
32

Pierre Kraemer's avatar
Pierre Kraemer committed
33
34
template <typename MAP, unsigned int ORBIT>
MarkerForTraversor<MAP, ORBIT>::MarkerForTraversor(MAP& map, bool forceDartMarker, unsigned int thread) :
35
36
	m_map(map),
	m_dmark(NULL),
Pierre Kraemer's avatar
Pierre Kraemer committed
37
	m_cmark(NULL)
Pierre Kraemer's avatar
Pierre Kraemer committed
38
{
39
	if(!forceDartMarker && map.isOrbitEmbedded(ORBIT))
Pierre Kraemer's avatar
Pierre Kraemer committed
40
		m_cmark = new CellMarkerStore<ORBIT>(map, thread) ;
41
42
	else
		m_dmark = new DartMarkerStore(map, thread) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
43
44
}

Pierre Kraemer's avatar
Pierre Kraemer committed
45
46
template <typename MAP, unsigned int ORBIT>
MarkerForTraversor<MAP, ORBIT>::~MarkerForTraversor()
Pierre Kraemer's avatar
Pierre Kraemer committed
47
{
48
49
50
51
	if (m_cmark)
		delete m_cmark;
	if (m_dmark)
		delete m_dmark;
Pierre Kraemer's avatar
Pierre Kraemer committed
52
53
}

Pierre Kraemer's avatar
Pierre Kraemer committed
54
55
template <typename MAP, unsigned int ORBIT>
void MarkerForTraversor<MAP, ORBIT>::mark(Dart d)
Pierre Kraemer's avatar
Pierre Kraemer committed
56
{
57
58
59
	if (m_cmark)
		m_cmark->mark(d);
	else
Pierre Kraemer's avatar
Pierre Kraemer committed
60
		m_dmark->markOrbit<ORBIT>(d);
Pierre Kraemer's avatar
Pierre Kraemer committed
61
62
}

Pierre Kraemer's avatar
Pierre Kraemer committed
63
64
template <typename MAP, unsigned int ORBIT>
void MarkerForTraversor<MAP, ORBIT>::unmark(Dart d)
65
{
66
67
	if (m_cmark)
		m_cmark->unmark(d);
68
	else
Pierre Kraemer's avatar
Pierre Kraemer committed
69
		m_dmark->unmarkOrbit<ORBIT>(d);
70
71
}

Pierre Kraemer's avatar
Pierre Kraemer committed
72
73
template <typename MAP, unsigned int ORBIT>
bool MarkerForTraversor<MAP, ORBIT>::isMarked(Dart d)
74
{
75
76
77
	if (m_cmark)
		return m_cmark->isMarked(d);
	return m_dmark->isMarked(d);
78
79
}

Pierre Kraemer's avatar
Pierre Kraemer committed
80
81
template <typename MAP, unsigned int ORBIT>
CellMarkerStore<ORBIT>* MarkerForTraversor<MAP, ORBIT>::cmark()
82
{
83
	return m_cmark;
84
85
}

Pierre Kraemer's avatar
Pierre Kraemer committed
86
87
template <typename MAP, unsigned int ORBIT>
DartMarkerStore* MarkerForTraversor<MAP, ORBIT>::dmark()
88
89
90
91
92
93
94
95
{
	return m_dmark;
}

//**************************************
// Traversor cellX Y incident to cell X
//**************************************

Pierre Kraemer's avatar
Pierre Kraemer committed
96
97
template <typename MAP, unsigned int ORBX, unsigned int ORBY>
Traversor3XY<MAP, ORBX, ORBY>::Traversor3XY(MAP& map, Dart dart, bool forceDartMarker, unsigned int thread) :
98
99
100
	m_map(map),
	m_dmark(NULL),
	m_cmark(NULL),
Pierre Kraemer's avatar
Pierre Kraemer committed
101
	m_tradoo(map, dart, thread),
102
103
	m_allocated(true),
	m_first(true)
104
{
Pierre Kraemer's avatar
Pierre Kraemer committed
105
106
	if(!forceDartMarker && map.isOrbitEmbedded(ORBY))
		m_cmark = new CellMarkerStore<ORBY>(map, thread) ;
107
108
109
110
	else
		m_dmark = new DartMarkerStore(map, thread) ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
111
112
template <typename MAP, unsigned int ORBX, unsigned int ORBY>
Traversor3XY<MAP, ORBX, ORBY>::Traversor3XY(MAP& map, Dart dart, MarkerForTraversor<MAP, ORBY>& tmo, bool forceDartMarker, unsigned int thread) :
113
	m_map(map),
Pierre Kraemer's avatar
Pierre Kraemer committed
114
	m_tradoo(map, dart, thread),
115
116
	m_allocated(false),
	m_first(true)
117
118
119
120
121
{
	m_cmark = tmo.cmark();
	m_dmark = tmo.dmark();
}

Pierre Kraemer's avatar
Pierre Kraemer committed
122
123
template <typename MAP, unsigned int ORBX, unsigned int ORBY>
Traversor3XY<MAP, ORBX, ORBY>::~Traversor3XY()
124
125
126
127
128
129
130
131
132
133
{
	if (m_allocated)
	{
		if (m_cmark)
			delete m_cmark;
		if (m_dmark)
			delete m_dmark;
	}
}

Pierre Kraemer's avatar
Pierre Kraemer committed
134
135
template <typename MAP, unsigned int ORBX, unsigned int ORBY>
Dart Traversor3XY<MAP, ORBX, ORBY>::begin()
136
{
137
	if (!m_first)
138
	{
139
140
141
142
		if (m_cmark)
			m_cmark->unmarkAll();
		else
			m_dmark->unmarkAll();
143
	}
144
	m_first = false;
145
146
147
148

	m_current = m_tradoo.begin() ;
	// for the case of beginning with a given MarkerForTraversor
	if (!m_allocated)
149
	{
150
151
152
153
154
155
156
157
158
159
		if (m_cmark)
		{
			while ((m_current != NIL) && m_cmark->isMarked(m_current))
				m_current = m_tradoo.next();
		}
		else
		{
			while ((m_current != NIL) && m_dmark->isMarked(m_current))
				m_current = m_tradoo.next();
		}
160
	}
161

Sylvain Thery's avatar
Sylvain Thery committed
162
	if ((ORBY == VOLUME) && (m_current != NIL))
163
	{
Thery Sylvain's avatar
Thery Sylvain committed
164
		if(m_map.isBoundaryMarked3(m_current))
165
166
167
			m_current = next();
	}

168
169
170
	return m_current;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
171
172
template <typename MAP, unsigned int ORBX, unsigned int ORBY>
Dart Traversor3XY<MAP, ORBX, ORBY>::end()
173
174
175
176
{
	return NIL ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
177
178
template <typename MAP, unsigned int ORBX, unsigned int ORBY>
Dart Traversor3XY<MAP, ORBX, ORBY>::next()
179
{
180
	if(m_current != NIL)
181
	{
182
		if (m_cmark)
183
		{
184
185
			m_cmark->mark(m_current);
			m_current = m_tradoo.next();
186
187
			if(ORBY == VOLUME)
			{
Thery Sylvain's avatar
Thery Sylvain committed
188
				if(m_map.isBoundaryMarked3(m_current))
189
190
					m_cmark->mark(m_current);
			}
191
192
			while ((m_current != NIL) && m_cmark->isMarked(m_current))
				m_current = m_tradoo.next();
193
194
195
		}
		else
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
196
			if (ORBX == VOLUME)
197
198
199
			{
				// if allocated we are in a local traversal of volume so we can mark only darts of volume
				if (m_allocated)
Pierre Kraemer's avatar
Pierre Kraemer committed
200
					m_dmark->markOrbit<ORBY + MAP::IN_PARENT>(m_current);
201
				else
Pierre Kraemer's avatar
Pierre Kraemer committed
202
					m_dmark->markOrbit<ORBY>(m_current); // here we need to mark all the darts
203
204
			}
			else
Pierre Kraemer's avatar
Pierre Kraemer committed
205
				m_dmark->markOrbit<ORBY>(m_current);
206
			m_current = m_tradoo.next();
207
208
			if(ORBY == VOLUME)
			{
Thery Sylvain's avatar
Thery Sylvain committed
209
				if(m_map.isBoundaryMarked3(m_current))
210
211
212
213
214
215
216
217
218
219
220
221
222
				{
					if (ORBX == VOLUME)
					{
						// if allocated we are in a local traversal of volume so we can mark only darts of volume
						if (m_allocated)
							m_dmark->markOrbit<ORBY + MAP::IN_PARENT>(m_current);
						else
							m_dmark->markOrbit<ORBY>(m_current); // here we need to mark all the darts
					}
					else
						m_dmark->markOrbit<ORBY>(m_current);
				}
			}
223
224
			while ((m_current != NIL) && m_dmark->isMarked(m_current))
				m_current = m_tradoo.next();
225
226
		}
	}
227
228
229
230
231
232
233
	return m_current ;
}

//*********************************************
// Traversor cellX to cellX adjacent by cell Y
//*********************************************

Pierre Kraemer's avatar
Pierre Kraemer committed
234
235
template <typename MAP, unsigned int ORBX, unsigned int ORBY>
Traversor3XXaY<MAP, ORBX, ORBY>::Traversor3XXaY(MAP& map, Dart dart, bool forceDartMarker, unsigned int thread):
236
237
	m_map(map)
{
Pierre Kraemer's avatar
Pierre Kraemer committed
238
	MarkerForTraversor<MAP, ORBX> mk(map, forceDartMarker, thread);
239
240
	mk.mark(dart);

Pierre Kraemer's avatar
Pierre Kraemer committed
241
	Traversor3XY<MAP, ORBX, ORBY> traAdj(map, dart, forceDartMarker, thread);
Pierre Kraemer's avatar
Pierre Kraemer committed
242
	for (Dart d = traAdj.begin(); d != traAdj.end(); d = traAdj.next())
243
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
244
		Traversor3XY<MAP, ORBY, ORBX> traInci(map, d, mk, forceDartMarker, thread);
Pierre Kraemer's avatar
Pierre Kraemer committed
245
		for (Dart e = traInci.begin(); e != traInci.end(); e = traInci.next())
246
247
248
249
250
			m_vecDarts.push_back(e);
	}
	m_vecDarts.push_back(NIL);
}

Pierre Kraemer's avatar
Pierre Kraemer committed
251
252
template <typename MAP, unsigned int ORBX, unsigned int ORBY>
Dart Traversor3XXaY<MAP, ORBX, ORBY>::begin()
253
{
254
	m_iter = m_vecDarts.begin();
255
256
257
	return *m_iter;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
258
259
template <typename MAP, unsigned int ORBX, unsigned int ORBY>
Dart Traversor3XXaY<MAP, ORBX, ORBY>::end()
260
261
{
	return NIL;
262
263
}

Pierre Kraemer's avatar
Pierre Kraemer committed
264
265
template <typename MAP, unsigned int ORBX, unsigned int ORBY>
Dart Traversor3XXaY<MAP, ORBX, ORBY>::next()
266
267
268
269
270
271
{
	if (*m_iter != NIL)
		m_iter++;
	return *m_iter ;
}

272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381

//template<typename MAP>
//Traversor3<MAP>* Traversor3<MAP>::createXY(MAP& map, Dart dart, unsigned int orbX, unsigned int orbY)
//{
//	int code = 0x10*(orbX-VERTEX) + orbY-VERTEX;
//
//	switch(code)
//	{
//	case 0x01:
//		return new Traversor3XY<MAP, VERTEX, EDGE>(map,dart);
//		break;
//	case 0x02:
//		return new Traversor3XY<MAP, VERTEX, FACE>(map,dart);
//		break;
//	case 0x03:
//		return new Traversor3XY<MAP, VERTEX, VOLUME>(map,dart);
//		break;
//
//	case 0x10:
//		return new Traversor3XY<MAP, EDGE, VERTEX>(map,dart);
//		break;
//	case 0x12:
//		return new Traversor3XY<MAP, EDGE, FACE>(map,dart);
//		break;
//	case 0x13:
//		return new Traversor3XY<MAP, EDGE, VOLUME>(map,dart);
//		break;
//
//	case 0x20:
//		return new Traversor3XY<MAP, FACE, VERTEX>(map,dart);
//		break;
//	case 0x21:
//		return new Traversor3XY<MAP, FACE, EDGE>(map,dart);
//		break;
//	case 0x23:
//		return new Traversor3XY<MAP, FACE, VOLUME>(map,dart);
//		break;
//
//	case 0x30:
//		return new Traversor3XY<MAP, VOLUME, VERTEX>(map,dart);
//		break;
//	case 0x31:
//		return new Traversor3XY<MAP, VOLUME, EDGE>(map,dart);
//		break;
//	case 0x32:
//		return new Traversor3XY<MAP, VOLUME, FACE>(map,dart);
//		break;
//
//	default:
//		return NULL;
//		break;
//	}
//	return NULL;
//}
//
//
//template<typename MAP>
//Traversor3<MAP>* Traversor3<MAP>::createXXaY(MAP& map, Dart dart, unsigned int orbX, unsigned int orbY)
//{
//	int code = 0x10*(orbX-VERTEX) + orbY-VERTEX;
//
//	switch(code)
//	{
//	case 0x01:
//		return new Traversor3XXaY<MAP, VERTEX, EDGE>(map,dart);
//		break;
//	case 0x02:
//		return new Traversor3XXaY<MAP, VERTEX, FACE>(map,dart);
//		break;
//	case 0x03:
//		return new Traversor3XXaY<MAP, VERTEX, VOLUME>(map,dart);
//		break;
//
//	case 0x10:
//		return new Traversor3XXaY<MAP, EDGE, VERTEX>(map,dart);
//		break;
//	case 0x12:
//		return new Traversor3XXaY<MAP, EDGE, FACE>(map,dart);
//		break;
//	case 0x13:
//		return new Traversor3XXaY<MAP, EDGE, VOLUME>(map,dart);
//		break;
//
//	case 0x20:
//		return new Traversor3XXaY<MAP, FACE, VERTEX>(map,dart);
//		break;
//	case 0x21:
//		return new Traversor3XXaY<MAP, FACE, EDGE>(map,dart);
//		break;
//	case 0x23:
//		return new Traversor3XXaY<MAP, FACE, VOLUME>(map,dart);
//		break;
//
//	case 0x30:
//		return new Traversor3XXaY<MAP, VOLUME, VERTEX>(map,dart);
//		break;
//	case 0x31:
//		return new Traversor3XXaY<MAP, VOLUME, EDGE>(map,dart);
//		break;
//	case 0x32:
//		return new Traversor3XXaY<MAP, VOLUME, FACE>(map,dart);
//		break;
//
//	default:
//		return NULL;
//		break;
//	}
//	return NULL;
//}

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