DGtal  1.3.beta
DigitalSetBySTLVector.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 DigitalSetBySTLVector.ih
19  * @author Jacques-Olivier Lachaud (\c jacques-olivier.lachaud@univ-savoie.fr )
20  * Laboratory of Mathematics (CNRS, UMR 5807), University of Savoie, France
21  *
22  * @date 2010/07/01
23  *
24  * Implementation of inline methods defined in DigitalSetBySTLVector.h
25  *
26  * This file is part of the DGtal library.
27  */
28 
29 
30 //////////////////////////////////////////////////////////////////////////////
31 #include <cstdlib>
32 #include <algorithm>
33 //////////////////////////////////////////////////////////////////////////////
34 
35 ///////////////////////////////////////////////////////////////////////////////
36 // IMPLEMENTATION of inline methods.
37 ///////////////////////////////////////////////////////////////////////////////
38 
39 ///////////////////////////////////////////////////////////////////////////////
40 // ----------------------- Standard services ------------------------------
41 
42 /**
43  * Destructor.
44  */
45 template <typename Domain>
46 inline
47 DGtal::DigitalSetBySTLVector<Domain>::~DigitalSetBySTLVector()
48 {
49 }
50 
51 /**
52  * Constructor.
53  * Creates the empty set in the domain [d].
54  *
55  * @param d any domain.
56  */
57 template <typename Domain>
58 inline
59 DGtal::DigitalSetBySTLVector<Domain>::DigitalSetBySTLVector
60 ( Clone<Domain> d )
61  : myDomain( d ), myVector()
62 {
63 }
64 
65 /**
66  * Copy constructor.
67  * @param other the object to clone.
68  */
69 template <typename Domain>
70 inline
71 DGtal::DigitalSetBySTLVector<Domain>::DigitalSetBySTLVector
72 ( const DigitalSetBySTLVector & other )
73  : myDomain( other.myDomain ), myVector( other.myVector )
74 {
75 }
76 
77 /**
78  * Assignment.
79  * @param other the object to copy.
80  * @return a reference on 'this'.
81  */
82 template <typename Domain>
83 inline
84 DGtal::DigitalSetBySTLVector<Domain> &
85 DGtal::DigitalSetBySTLVector<Domain>::operator=
86 ( const DigitalSetBySTLVector & other )
87 {
88  ASSERT( ( domain().lowerBound() <= other.domain().lowerBound() )
89  && ( domain().upperBound() >= other.domain().upperBound() )
90  && "This domain should include the domain of the other set in case of assignment." );
91  myVector = other.myVector;
92  return *this;
93 }
94 
95 
96 /**
97  * @return the embedding domain.
98  */
99 template <typename Domain>
100 inline
101 const Domain &
102 DGtal::DigitalSetBySTLVector<Domain>::domain() const
103 {
104  return *myDomain;
105 }
106 
107 template <typename Domain>
108 inline
109 DGtal::CowPtr<Domain>
110 DGtal::DigitalSetBySTLVector<Domain>::domainPointer() const
111 {
112  return myDomain;
113 }
114 
115 
116 
117 // ----------------------- Standard Set services --------------------------
118 
119 /**
120  * @return the number of elements in the set.
121  */
122 template <typename Domain>
123 inline
124 typename DGtal::DigitalSetBySTLVector<Domain>::Size
125 DGtal::DigitalSetBySTLVector<Domain>::size() const
126 {
127  return (unsigned int)myVector.size();
128 }
129 
130 /**
131  * @return 'true' iff the set is empty (no element).
132  */
133 template <typename Domain>
134 inline
135 bool
136 DGtal::DigitalSetBySTLVector<Domain>::empty() const
137 {
138  return myVector.empty();
139 }
140 
141 /**
142  * Adds point [p] to this set.
143  *
144  * @param p any digital point.
145  * @pre p should belong to the associated domain.
146  */
147 template <typename Domain>
148 inline
149 void
150 DGtal::DigitalSetBySTLVector<Domain>::insert( const Point & p )
151 {
152  // ASSERT( domain().isInside( p ) );
153  Iterator it = find( p );
154  if ( it == end() )
155  myVector.push_back( p );
156 }
157 
158 /**
159  * Adds the collection of points specified by the two iterators to
160  * this set.
161  *
162  * @param first the start point in the collection of Point.
163  * @param last the last point in the collection of Point.
164  * @pre all points should belong to the associated domain.
165  */
166 template <typename Domain>
167 template <typename PointInputIterator>
168 inline
169 void
170 DGtal::DigitalSetBySTLVector<Domain>::insert
171 ( PointInputIterator first, PointInputIterator last )
172 {
173  for ( ; first != last; ++first )
174  insert( *first );
175 }
176 
177 /**
178  * Adds point [p] to this set if the point is not already in the
179  * set. There is no defined behavior if the point is already in
180  * the set (for instance, may be present twice).
181  *
182  * @param p any digital point.
183  *
184  * @pre p should belong to the associated domain.
185  * @pre p should not belong to this.
186  */
187 template <typename Domain>
188 inline
189 void
190 DGtal::DigitalSetBySTLVector<Domain>::insertNew( const Point & p )
191 {
192  // ASSERT( domain().isInside( p ) );
193  ASSERT( find( p ) == end() );
194  myVector.push_back( p );
195 }
196 
197 /**
198  * Adds the collection of points specified by the two iterators to
199  * this set. The collection should contain distinct points. Each
200  * of these points should also not belong already to the set.
201  * set. There is no defined behavior if the preceding requisites
202  * are not satisfied (for instance, points may be present several
203  * times in the set).
204  *
205  * @param first the start point in the collection of Point.
206  * @param last the last point in the collection of Point.
207  *
208  * @pre all points should belong to the associated domain.
209  * @pre each point should not belong to this.
210  */
211 template <typename Domain>
212 template <typename PointInputIterator>
213 inline
214 void
215 DGtal::DigitalSetBySTLVector<Domain>::insertNew
216 ( PointInputIterator first, PointInputIterator last )
217 {
218  while ( first != last )
219  myVector.push_back( *first++ );
220  // std::copy( first, last, myVector.end() );
221 }
222 
223 
224 /**
225  * Removes point [p] from the set.
226  *
227  * @param p the point to remove.
228  * @return the number of removed elements (0 or 1).
229  */
230 template <typename Domain>
231 inline
232 typename DGtal::DigitalSetBySTLVector<Domain>::Size
233 DGtal::DigitalSetBySTLVector<Domain>::erase( const Point & p )
234 {
235  Iterator it = find( p );
236  if ( it != end() )
237  {
238  erase( it );
239  return 1;
240  }
241  return 0;
242 }
243 
244 /**
245  * Removes the point pointed by [it] from the set.
246  *
247  * @param it an iterator on this set.
248  * @pre it should point on a valid element ( it != end() ).
249  * Note: generally faster than giving just the point.
250  */
251 template <typename Domain>
252 inline
253 void
254 DGtal::DigitalSetBySTLVector<Domain>::erase( Iterator it )
255 {
256  //take a mutable iterator
257  typename std::iterator_traits<Iterator>::difference_type d = it - this->begin();
258  typename std::vector<Point>::iterator it2 = myVector.begin() + d;
259  //swap
260  *it2 = myVector.back();
261  myVector.pop_back();
262 }
263 
264 /**
265  * Removes the collection of points specified by the two iterators from
266  * this set.
267  *
268  * @param first the start point in this set.
269  * @param last the last point in this set.
270  */
271 template <typename Domain>
272 inline
273 void
274 DGtal::DigitalSetBySTLVector<Domain>::erase( Iterator first, Iterator last )
275 {
276  while ( ( last != end() )
277  && ( first != last ) )
278  {
279  //take a mutable iterator
280  typename std::iterator_traits<Iterator>::difference_type d = first - this->begin();
281  typename std::vector<Point>::iterator first2 = myVector.begin() + d;
282  //swap
283  *first2 = myVector.back();
284  myVector.pop_back();
285  //advance
286  first++;
287  }
288  if ( first != last )
289  while ( first != end() )
290  myVector.pop_back();
291 }
292 
293 /**
294  * Clears the set.
295  * @post this set is empty.
296  */
297 template <typename Domain>
298 inline
299 void
300 DGtal::DigitalSetBySTLVector<Domain>::clear()
301 {
302  myVector.clear();
303 }
304 
305 /**
306  * @param p any digital point.
307  * @return a const iterator pointing on [p] if found, otherwise end().
308  */
309 template <typename Domain>
310 inline
311 typename DGtal::DigitalSetBySTLVector<Domain>::ConstIterator
312 DGtal::DigitalSetBySTLVector<Domain>::find( const Point & p ) const
313 {
314  const ConstIterator it_end = end();
315  for ( ConstIterator it = begin(); it != it_end; ++it )
316  if ( p == *it ) return it;
317  return it_end;
318 }
319 
320 /**
321  * @param p any digital point.
322  * @return an iterator pointing on [p] if found, otherwise end().
323  */
324 template <typename Domain>
325 inline
326 typename DGtal::DigitalSetBySTLVector<Domain>::Iterator
327 DGtal::DigitalSetBySTLVector<Domain>::find( const Point & p )
328 {
329  const Iterator it_end = end();
330  for ( Iterator it = begin(); it != it_end; ++it )
331  if ( p == *it ) return it;
332  return it_end;
333 }
334 
335 
336 /**
337  * @return a const iterator on the first element in this set.
338  */
339 template <typename Domain>
340 inline
341 typename DGtal::DigitalSetBySTLVector<Domain>::ConstIterator
342 DGtal::DigitalSetBySTLVector<Domain>::begin() const
343 {
344  return myVector.begin();
345 }
346 
347 /**
348  * @return a const iterator on the element after the last in this set.
349  */
350 template <typename Domain>
351 inline
352 typename DGtal::DigitalSetBySTLVector<Domain>::ConstIterator
353 DGtal::DigitalSetBySTLVector<Domain>::end() const
354 {
355  return myVector.end();
356 }
357 
358 
359 /**
360  * @return an iterator on the first element in this set.
361  */
362 template <typename Domain>
363 inline
364 typename DGtal::DigitalSetBySTLVector<Domain>::Iterator
365 DGtal::DigitalSetBySTLVector<Domain>::begin()
366 {
367  return myVector.begin();
368 }
369 
370 
371 /**
372  * @return a iterator on the element after the last in this set.
373  */
374 template <typename Domain>
375 inline
376 typename DGtal::DigitalSetBySTLVector<Domain>::Iterator
377 DGtal::DigitalSetBySTLVector<Domain>::end()
378 {
379  return myVector.end();
380 }
381 
382 template <typename Domain>
383 inline
384 const typename DGtal::DigitalSetBySTLVector<Domain>::Container &
385 DGtal::DigitalSetBySTLVector<Domain>::container() const
386 {
387  return myVector;
388 }
389 
390 template <typename Domain>
391 inline
392 typename DGtal::DigitalSetBySTLVector<Domain>::Container &
393 DGtal::DigitalSetBySTLVector<Domain>::container()
394 {
395  return myVector;
396 }
397 
398 /**
399  * set union to left.
400  * @param aSet any other set.
401  */
402 template <typename Domain>
403 inline
404 DGtal::DigitalSetBySTLVector<Domain> &
405 DGtal::DigitalSetBySTLVector<Domain>
406 ::operator+=( const DigitalSetBySTLVector<Domain> & aSet )
407 {
408  if ( this != &aSet )
409  {
410  std::vector<Point> other( aSet.myVector );
411  std::stable_sort( other.begin(), other.end() );
412  std::stable_sort( myVector.begin(), myVector.end() );
413  std::vector<Point> new_vector;
414  new_vector.reserve( size() + other.size() );
415  std::set_union( begin(), end(), other.begin(), other.end(),
416  std::back_insert_iterator< std::vector<Point> >
417  ( new_vector ) );
418  myVector.swap( new_vector );
419  }
420  return *this;
421 }
422 
423 //-----------------------------------------------------------------------------
424 template <typename Domain>
425 inline
426 bool
427 DGtal::DigitalSetBySTLVector<Domain>
428 ::operator()( const Point & p ) const
429 {
430  return find( p ) != end();
431 }
432 
433 
434 ///////////////////////////////////////////////////////////////////////////////
435 // ----------------------- Other Set services -----------------------------
436 
437 
438 template <typename Domain>
439 template <typename TOutputIterator>
440 inline
441 void
442 DGtal::DigitalSetBySTLVector<Domain>::computeComplement(TOutputIterator& ito) const
443 {
444  typename Domain::ConstIterator itPoint = domain().begin();
445  typename Domain::ConstIterator itEnd = domain().end();
446  while ( itPoint != itEnd ) {
447  if ( std::find( begin(), end(), *itPoint ) == end() ) {
448  *ito++ = *itPoint;
449  }
450  ++itPoint;
451  }
452 }
453 
454 /**
455  * Builds the complement in the domain of the set [other_set] in
456  * this.
457  *
458  * @param other_set defines the set whose complement is assigned to 'this'.
459  */
460 template <typename Domain>
461 inline
462 void
463 DGtal::DigitalSetBySTLVector<Domain>::assignFromComplement
464 ( const DigitalSetBySTLVector<Domain> & other_set )
465 {
466  clear();
467  typename Domain::ConstIterator itPoint = domain().begin();
468  typename Domain::ConstIterator itEnd = domain().end();
469  while ( itPoint != itEnd ) {
470  if ( std::find( other_set.begin(),
471  other_set.end(),
472  *itPoint ) == other_set.end() ) {
473  insert( *itPoint );
474  }
475  ++itPoint;
476  }
477 }
478 
479 /**
480  * Computes the bounding box of this set.
481  *
482  * @param lower the first point of the bounding box (lowest in all
483  * directions).
484  * @param upper the last point of the bounding box (highest in all
485  * directions).
486  */
487 template <typename Domain>
488 inline
489 void
490 DGtal::DigitalSetBySTLVector<Domain>::computeBoundingBox
491 ( Point & lower, Point & upper ) const
492 {
493  if ( begin() != end() )
494  {
495  ConstIterator it = begin();
496  ConstIterator it_end = end();
497  upper = lower = *it;
498  for ( ; it != it_end; ++it )
499  if ( it->isLower( lower ) ) lower = *it;
500  else if ( it->isUpper( upper ) ) upper = *it;
501  }
502  else
503  {
504  lower = domain().upperBound();
505  upper = domain().lowerBound();
506  }
507 }
508 
509 
510 ///////////////////////////////////////////////////////////////////////////////
511 // Interface - public :
512 
513 /**
514  * Writes/Displays the object on an output stream.
515  * @param out the output stream where the object is written.
516  */
517 template <typename Domain>
518 inline
519 void
520 DGtal::DigitalSetBySTLVector<Domain>::selfDisplay ( std::ostream & out ) const
521 {
522  out << "[DigitalSetBySTLVector]" << " size=" << size();
523 }
524 
525 /**
526  * Checks the validity/consistency of the object.
527  * @return 'true' if the object is valid, 'false' otherwise.
528  */
529 template <typename Domain>
530 inline
531 bool
532 DGtal::DigitalSetBySTLVector<Domain>::isValid() const
533 {
534  return true;
535 }
536 
537 
538 
539 // --------------- CDrawableWithBoard2D realization -------------------------
540 
541 
542 /**
543  * @return the style name used for drawing this object.
544  */
545 template<typename Domain>
546 inline
547 std::string
548 DGtal::DigitalSetBySTLVector<Domain>::className() const
549 {
550  return "DigitalSetBySTLVector";
551 }
552 
553 ///////////////////////////////////////////////////////////////////////////////
554 // Implementation of inline function //
555 
556 template <typename Domain>
557 inline
558 std::ostream&
559 DGtal::operator<< ( std::ostream & out,
560  const DigitalSetBySTLVector<Domain> & object )
561 {
562  object.selfDisplay( out );
563  return out;
564 }
565 
566 // //
567 ///////////////////////////////////////////////////////////////////////////////
568 
569