traversor3.hpp 9.55 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(m_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
145
146
147
148
	m_first=false;

	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
162
163
	}
	return m_current;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
164
165
template <typename MAP, unsigned int ORBX, unsigned int ORBY>
Dart Traversor3XY<MAP, ORBX, ORBY>::end()
166
167
168
169
{
	return NIL ;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
170
171
template <typename MAP, unsigned int ORBX, unsigned int ORBY>
Dart Traversor3XY<MAP, ORBX, ORBY>::next()
172
{
173
	if(m_current != NIL)
174
	{
175
		if (m_cmark)
176
		{
177
178
179
180
			m_cmark->mark(m_current);
			m_current = m_tradoo.next();
			while ((m_current != NIL) && m_cmark->isMarked(m_current))
				m_current = m_tradoo.next();
181
182
183
		}
		else
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
184
			if (ORBX == VOLUME)
185
186
187
			{
				// 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
188
					m_dmark->markOrbit<ORBY + MAP::IN_PARENT>(m_current);
189
				else
Pierre Kraemer's avatar
Pierre Kraemer committed
190
					m_dmark->markOrbit<ORBY>(m_current); // here we need to mark all the darts
191
192
			}
			else
Pierre Kraemer's avatar
Pierre Kraemer committed
193
				m_dmark->markOrbit<ORBY>(m_current);
194
195
196
			m_current = m_tradoo.next();
			while ((m_current != NIL) && m_dmark->isMarked(m_current))
				m_current = m_tradoo.next();
197
198
		}
	}
199
200
201
202
203
204
205
	return m_current ;
}

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

Pierre Kraemer's avatar
Pierre Kraemer committed
206
207
template <typename MAP, unsigned int ORBX, unsigned int ORBY>
Traversor3XXaY<MAP, ORBX, ORBY>::Traversor3XXaY(MAP& map, Dart dart, bool forceDartMarker, unsigned int thread):
208
209
	m_map(map)
{
Pierre Kraemer's avatar
Pierre Kraemer committed
210
	MarkerForTraversor<MAP, ORBX> mk(map, forceDartMarker, thread);
211
212
	mk.mark(dart);

Pierre Kraemer's avatar
Pierre Kraemer committed
213
	Traversor3XY<MAP, ORBX, ORBY> traAdj(map, dart, forceDartMarker, thread);
Pierre Kraemer's avatar
Pierre Kraemer committed
214
	for (Dart d = traAdj.begin(); d != traAdj.end(); d = traAdj.next())
215
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
216
		Traversor3XY<MAP, ORBY, ORBX> traInci(map, d, mk, forceDartMarker, thread);
Pierre Kraemer's avatar
Pierre Kraemer committed
217
		for (Dart e = traInci.begin(); e != traInci.end(); e = traInci.next())
218
219
220
221
222
			m_vecDarts.push_back(e);
	}
	m_vecDarts.push_back(NIL);
}

Pierre Kraemer's avatar
Pierre Kraemer committed
223
224
template <typename MAP, unsigned int ORBX, unsigned int ORBY>
Dart Traversor3XXaY<MAP, ORBX, ORBY>::begin()
225
{
226
	m_iter = m_vecDarts.begin();
227
228
229
	return *m_iter;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
230
231
template <typename MAP, unsigned int ORBX, unsigned int ORBY>
Dart Traversor3XXaY<MAP, ORBX, ORBY>::end()
232
233
{
	return NIL;
234
235
}

Pierre Kraemer's avatar
Pierre Kraemer committed
236
237
template <typename MAP, unsigned int ORBX, unsigned int ORBY>
Dart Traversor3XXaY<MAP, ORBX, ORBY>::next()
238
239
240
241
242
243
{
	if (*m_iter != NIL)
		m_iter++;
	return *m_iter ;
}

244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
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

//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
354
} // namespace CGoGN