DGtal  0.9.2
Labels.ih
1 /**
2  * This program is free software: you can redistribute it and/or modify
3  * it under the terms of the GNU Lesser General Public License as
4  * published by the Free Software Foundation, either version 3 of the
5  * License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program. If not, see <http://www.gnu.org/licenses/>.
14  *
15  **/
16 
17 /**
18  * @file Labels.ih
19  * @author Jacques-Olivier Lachaud (\c jacques-olivier.lachaud@univ-savoie.fr )
20  * Laboratory of Mathematics (CNRS, UMR 5127), University of Savoie, France
21  *
22  * @date 2012/07/07
23  *
24  * Implementation of inline methods defined in Labels.h
25  *
26  * This file is part of the DGtal library.
27  */
28 
29 
30 //////////////////////////////////////////////////////////////////////////////
31 #include <cstdlib>
32 #include <algorithm>
33 #include <limits>
34 #include "DGtal/base/Bits.h"
35 //////////////////////////////////////////////////////////////////////////////
36 
37 ///////////////////////////////////////////////////////////////////////////////
38 // IMPLEMENTATION of inline methods.
39 ///////////////////////////////////////////////////////////////////////////////
40 
41 ///////////////////////////////////////////////////////////////////////////////
42 // class DGtal::Labels<L, TWord>::ConstEnumerator
43 
44 ///////////////////////////////////////////////////////////////////////////////
45 // ----------------------- Standard services ------------------------------
46 //-----------------------------------------------------------------------------
47 template <unsigned int L, typename TWord>
48 inline
49 DGtal::Labels<L, TWord>::ConstEnumerator::
50 ~ConstEnumerator()
51 {}
52 //-----------------------------------------------------------------------------
53 template <unsigned int L, typename TWord>
54 inline
55 DGtal::Labels<L, TWord>::ConstEnumerator::
56 ConstEnumerator()
57  : myWordAddress( 0 ), myLabel( 0 )
58 {}
59 //-----------------------------------------------------------------------------
60 template <unsigned int L, typename TWord>
61 inline
62 DGtal::Labels<L, TWord>::ConstEnumerator::
63 ConstEnumerator( const Word* address, SizeType firstWord )
64  : myWordAddress( address + firstWord ),
65  myWordLabel( firstWord * __DGTAL_WORD_NBDIGITS )
66 {
67  ASSERT( firstWord <= __DGTAL_LABELS_NBWORDS );
68  if ( firstWord != __DGTAL_LABELS_NBWORDS )
69  {
70  myWord = *myWordAddress++;
71  this->operator++(); // find first bit
72  }
73  else
74  {
75  myWord = 0;
76  myLabel = std::numeric_limits<Label>::max();
77  }
78 }
79 //-----------------------------------------------------------------------------
80 template <unsigned int L, typename TWord>
81 inline
82 DGtal::Labels<L, TWord>::ConstEnumerator::
83 ConstEnumerator( const ConstEnumerator & other )
84  : myWordAddress( other.myWordAddress ), myWordLabel( other.myWordLabel ),
85  myLabel( other.myLabel ), myWord( other.myWord )
86 {}
87 //-----------------------------------------------------------------------------
88 template <unsigned int L, typename TWord>
89 inline
90 typename DGtal::Labels<L, TWord>::ConstEnumerator::Self &
91 DGtal::Labels<L, TWord>::ConstEnumerator::
92 operator= ( const Self & other )
93 {
94  if ( this != &other )
95  {
96  myWordAddress = other.myWordAddress;
97  myWordLabel = other.myWordLabel;
98  myLabel = other.myLabel;
99  myWord = other.myWord;
100  }
101  return *this;
102 }
103 //-----------------------------------------------------------------------------
104 template <unsigned int L, typename TWord>
105 inline
106 typename DGtal::Labels<L, TWord>::ConstEnumerator::Reference
107 DGtal::Labels<L, TWord>::ConstEnumerator::
108 operator*() const
109 {
110  return myLabel;
111 }
112 //-----------------------------------------------------------------------------
113 template <unsigned int L, typename TWord>
114 inline
115 typename DGtal::Labels<L, TWord>::ConstEnumerator::Pointer
116 DGtal::Labels<L, TWord>::ConstEnumerator::
117 operator->() const
118 {
119  return &myLabel;
120 }
121 //-----------------------------------------------------------------------------
122 template <unsigned int L, typename TWord>
123 inline
124 typename DGtal::Labels<L, TWord>::ConstEnumerator::Self&
125 DGtal::Labels<L, TWord>::ConstEnumerator::
126 operator++()
127 {
128  ASSERT( ( myWordLabel < ( __DGTAL_LABELS_NBWORDS
129  * __DGTAL_WORD_NBDIGITS ) ) );
130  while ( myWord == 0 )
131  {
132  myWordLabel += __DGTAL_WORD_NBDIGITS;
133  if ( myWordLabel == ( __DGTAL_LABELS_NBWORDS
134  * __DGTAL_WORD_NBDIGITS ) )
135  {
136  myLabel = std::numeric_limits<Label>::max();
137  return *this;
138  }
139  myWord = *myWordAddress++;
140  }
141  ASSERT( myWord != 0 );
142  Word fsb = Bits::firstSetBit( myWord );
143  myLabel = myWordLabel + Bits::leastSignificantBit( fsb );
144  myWord -= fsb;
145  return *this;
146 }
147 //-----------------------------------------------------------------------------
148 template <unsigned int L, typename TWord>
149 inline
150 typename DGtal::Labels<L, TWord>::ConstEnumerator::Self
151 DGtal::Labels<L, TWord>::ConstEnumerator::
152 operator++( int )
153 {
154  ConstEnumerator tmp( *this );
155  this->operator++();
156  return tmp;
157 }
158 //-----------------------------------------------------------------------------
159 template <unsigned int L, typename TWord>
160 inline
161 bool
162 DGtal::Labels<L, TWord>::ConstEnumerator::
163 operator==( const Self & other ) const
164 {
165  return ( myWordAddress == other.myWordAddress )
166  && ( myLabel == other.myLabel );
167 }
168 //-----------------------------------------------------------------------------
169 template <unsigned int L, typename TWord>
170 inline
171 bool
172 DGtal::Labels<L, TWord>::ConstEnumerator::
173 operator!=( const Self & other ) const
174 {
175  return ( myWordAddress != other.myWordAddress )
176  || ( myLabel != other.myLabel );
177 }
178 
179 
180 
181 //-----------------------------------------------------------------------------
182 template <unsigned int L, typename TWord>
183 inline
184 typename DGtal::Labels<L, TWord>::SizeType
185 DGtal::Labels<L, TWord>::_word( Label l )
186 {
187  return __DGTAL_LABEL_WORD_INDEX( l );
188 }
189 //-----------------------------------------------------------------------------
190 template <unsigned int L, typename TWord>
191 inline
192 typename DGtal::Labels<L, TWord>::SizeType
193 DGtal::Labels<L, TWord>::_digit( Label l )
194 {
195  return __DGTAL_LABEL_DIGIT_INDEX( l );
196 }
197 //-----------------------------------------------------------------------------
198 template <unsigned int L, typename TWord>
199 inline
200 typename DGtal::Labels<L, TWord>::Word
201 DGtal::Labels<L, TWord>::_mask( Label l )
202 {
203  return ( (Word) 1 ) << _digit( l );
204 }
205 //-----------------------------------------------------------------------------
206 template <unsigned int L, typename TWord>
207 inline
208 DGtal::Labels<L, TWord>::~Labels()
209 {
210 }
211 //-----------------------------------------------------------------------------
212 template <unsigned int L, typename TWord>
213 inline
214 DGtal::Labels<L, TWord>::Labels()
215 {
216  reset();
217 }
218 //-----------------------------------------------------------------------------
219 template <unsigned int L, typename TWord>
220 inline
221 DGtal::Labels<L, TWord>::Labels( const Self & other )
222 {
223  std::copy( other.myLabels, other.myLabels + __DGTAL_LABELS_NBWORDS,
224  myLabels );
225 }
226 //-----------------------------------------------------------------------------
227 template <unsigned int L, typename TWord>
228 inline
229 typename DGtal::Labels<L, TWord>::Self &
230 DGtal::Labels<L, TWord>::operator=( const Self & other )
231 {
232  if ( this != &other )
233  std::copy( other.myLabels, other.myLabels + __DGTAL_LABELS_NBWORDS,
234  myLabels );
235  return *this;
236 }
237 //-----------------------------------------------------------------------------
238 template <unsigned int L, typename TWord>
239 inline
240 typename DGtal::Labels<L, TWord>::Self &
241 DGtal::Labels<L, TWord>::reset()
242 {
243  Word* p1 = myLabels;
244  Word* p2 = myLabels + __DGTAL_LABELS_NBWORDS;
245  while ( p1 != p2 )
246  *p1++ = (Word) 0;
247  return *this;
248 }
249 //-----------------------------------------------------------------------------
250 template <unsigned int L, typename TWord>
251 inline
252 bool
253 DGtal::Labels<L, TWord>::test( Label l ) const
254 {
255  return _mask( l ) & myLabels[ _word( l ) ];
256 }
257 //-----------------------------------------------------------------------------
258 template <unsigned int L, typename TWord>
259 inline
260 typename DGtal::Labels<L, TWord>::Self &
261 DGtal::Labels<L, TWord>::set( Label l, bool val )
262 {
263  if ( val )
264  myLabels[ _word( l ) ] |= _mask( l );
265  else
266  myLabels[ _word( l ) ] &= ~_mask( l );
267  return *this;
268 }
269 //-----------------------------------------------------------------------------
270 template <unsigned int L, typename TWord>
271 inline
272 typename DGtal::Labels<L, TWord>::Self &
273 DGtal::Labels<L, TWord>::reset( Label l )
274 {
275  myLabels[ _word( l ) ] &= ~_mask( l );
276  return *this;
277 }
278 //-----------------------------------------------------------------------------
279 template <unsigned int L, typename TWord>
280 inline
281 typename DGtal::Labels<L, TWord>::Self &
282 DGtal::Labels<L, TWord>::flip( Label l )
283 {
284  myLabels[ _word( l ) ] ^= _mask( l );
285  return *this;
286 }
287 //-----------------------------------------------------------------------------
288 template <unsigned int L, typename TWord>
289 inline
290 typename DGtal::Labels<L, TWord>::SizeType
291 DGtal::Labels<L, TWord>::
292 count() const
293 {
294  SizeType n = 0;
295  const Word* p1 = myLabels;
296  const Word* p2 = myLabels + __DGTAL_LABELS_NBWORDS;
297  while ( p1 != p2 )
298  n += Bits::nbSetBits( *p1++ );
299  return n;
300 }
301 //-----------------------------------------------------------------------------
302 template <unsigned int L, typename TWord>
303 inline
304 typename DGtal::Labels<L, TWord>::SizeType
305 DGtal::Labels<L, TWord>::
306 size()
307 {
308  return L;
309 }
310 //-----------------------------------------------------------------------------
311 template <unsigned int L, typename TWord>
312 inline
313 void
314 DGtal::Labels<L, TWord>::
315 getLabels( std::vector<Label> & labels ) const
316 {
317  labels.clear();
318  Word w;
319  Word fsb;
320  const Word* p1 = myLabels;
321  const Word* p2 = myLabels + __DGTAL_LABELS_NBWORDS;
322  Label l = 0;
323  while ( p1 != p2 )
324  {
325  w = *p1++;
326  while ( w ) // extract labels within word
327  {
328  fsb = Bits::firstSetBit( w );
329  labels.push_back( l + Bits::leastSignificantBit( fsb ) );
330  w -= fsb;
331  ASSERT( index( labels.back() ) == ( labels.size() - 1 ) );
332  }
333  l += __DGTAL_WORD_NBDIGITS;
334  }
335 }
336 //-----------------------------------------------------------------------------
337 template <unsigned int L, typename TWord>
338 inline
339 typename DGtal::Labels<L, TWord>::SizeType
340 DGtal::Labels<L, TWord>::
341 index( Label l ) const
342 {
343  ASSERT( l < L );
344  const Word* p1 = myLabels;
345  const Word* p2 = myLabels + _word( l );
346  SizeType i = 0;
347  while ( p1 != p2 )
348  i += Bits::nbSetBits( *p1++ );
349  return ( _mask( l ) & *p1 )
350  ? i + Bits::indexInSetBits( *p1, _digit( l ) ) - 1
351  : L;
352 }
353 //-----------------------------------------------------------------------------
354 template <unsigned int L, typename TWord>
355 inline
356 typename DGtal::Labels<L, TWord>::ConstIterator
357 DGtal::Labels<L, TWord>::
358 begin() const
359 {
360  return ConstIterator( myLabels, 0 );
361 }
362 //-----------------------------------------------------------------------------
363 template <unsigned int L, typename TWord>
364 inline
365 typename DGtal::Labels<L, TWord>::ConstIterator
366 DGtal::Labels<L, TWord>::
367 end() const
368 {
369  return ConstIterator( myLabels, __DGTAL_LABELS_NBWORDS );
370 }
371 
372 
373 ///////////////////////////////////////////////////////////////////////////////
374 // Interface - public :
375 
376 /**
377  * Writes/Displays the object on an output stream.
378  * @param out the output stream where the object is written.
379  */
380 template <unsigned int L, typename TWord>
381 inline
382 void
383 DGtal::Labels<L, TWord>::selfDisplay ( std::ostream & out ) const
384 {
385  std::vector<Label> v;
386  this->getLabels( v );
387  if ( v.empty() )
388  out << "()";
389  else
390  {
391  out << "(" << v[ 0 ];
392  for ( SizeType i = 1; i < v.size(); ++i )
393  out << "," << v[ i ];
394  out << ")";
395  }
396 }
397 
398 /**
399  * Checks the validity/consistency of the object.
400  * @return 'true' if the object is valid, 'false' otherwise.
401  */
402 template <unsigned int L, typename TWord>
403 inline
404 bool
405 DGtal::Labels<L, TWord>::isValid() const
406 {
407  return true;
408 }
409 
410 
411 
412 ///////////////////////////////////////////////////////////////////////////////
413 // Implementation of inline functions //
414 
415 template <unsigned int L, typename TWord>
416 inline
417 std::ostream&
418 DGtal::operator<< ( std::ostream & out,
419  const Labels<L, TWord> & object )
420 {
421  object.selfDisplay( out );
422  return out;
423 }
424 
425 // //
426 ///////////////////////////////////////////////////////////////////////////////