DGtal  1.5.beta
Expander.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 Expander.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/10
23  *
24  * Implementation of inline methods defined in Expander.h
25  *
26  * This file is part of the DGtal library.
27  */
28 
29 
30 //////////////////////////////////////////////////////////////////////////////
31 #include <cstdlib>
32 //////////////////////////////////////////////////////////////////////////////
33 
34 ///////////////////////////////////////////////////////////////////////////////
35 // IMPLEMENTATION of inline methods.
36 ///////////////////////////////////////////////////////////////////////////////
37 
38 ///////////////////////////////////////////////////////////////////////////////
39 // ----------------------- Standard services ------------------------------
40 
41 /**
42  * Destructor.
43  */
44 template <typename TObject>
45 inline
46 DGtal::Expander<TObject>::~Expander()
47 {
48 }
49 
50 /**
51  * Constructor from a point. This point provides the initial core
52  * of the expander.
53  *
54  * @param object the digital object in which the expander expands.
55  * @param p any point in the given object.
56  */
57 template <typename TObject>
58 inline
59 DGtal::Expander<TObject>
60 ::Expander( ConstAlias<Object> object, const Point & p )
61  : myEmbeddingDomain( (&object)->pointSet().domain() ),
62  myObject( object ),
63  myObjectDomain( myObject.pointSet() ),
64  myObjectAdjacency( myObjectDomain, myObject.adjacency() ),
65  myCore( myEmbeddingDomain ),
66  myLayer( myEmbeddingDomain ),
67  myDistance( 0 ), myFinished( false ),
68  myNotInCorePred( myCore )
69 {
70  ASSERT( myObjectDomain.isInside( p ) );
71  myCore.insertNew( p );
72  computeNextLayer( myCore );
73 }
74 
75 /**
76  * Constructor from iterators. All points visited between the
77  * iterators should be distinct two by two. The so specified set
78  * of points provides the initial core of the expander.
79  *
80  * @tparam PointInputIterator the type of an InputIterator pointing on a Point.
81  *
82  * @param object the digital object in which the expander expands.
83  * @param b the begin point in a set.
84  * @param e the end point in a set.
85  */
86 template <typename TObject>
87 template <typename PointInputIterator>
88 inline
89 DGtal::Expander<TObject>
90 ::Expander( ConstAlias<Object> object,
91  PointInputIterator b, PointInputIterator e )
92  : myEmbeddingDomain( (&object)->pointSet().domain() ),
93  myObject( object ),
94  myObjectDomain( myObject.pointSet() ),
95  myObjectAdjacency( myObjectDomain, myObject.adjacency() ),
96  myCore( myEmbeddingDomain ),
97  myLayer( myEmbeddingDomain ),
98  myDistance( 0 ), myFinished( false ),
99  myNotInCorePred( myCore )
100 {
101  myCore.insertNew( b, e );
102  computeNextLayer( myCore );
103 }
104 
105 
106 /**
107  * @return 'true' if all possible elements have been visited.
108  */
109 template <typename TObject>
110 inline
111 bool
112 DGtal::Expander<TObject>::finished() const
113 {
114  return myFinished;
115 }
116 
117 /**
118  * @return the current distance to the initial core, or
119  * equivalently the index of the current layer.
120  */
121 template <typename TObject>
122 inline
123 typename DGtal::Expander<TObject>::Size
124 DGtal::Expander<TObject>::distance() const
125 {
126  return myDistance;
127 }
128 
129 
130 /**
131  * Extract next layer. You might used begin() and end() to access
132  * all the elements of the new layer.
133  *
134  * @return 'true' if there was another layer, or 'false' if it was the
135  * last (ie. reverse of finished() ).
136  */
137 template <typename TObject>
138 inline
139 bool
140 DGtal::Expander<TObject>
141 ::nextLayer()
142 {
143  endLayer();
144  computeNextLayer( myLayer );
145  return ! finished();
146 }
147 
148 /**
149  * Push the layer into the current core. Must be called before
150  * computeNextLayer.
151  */
152 template <typename TObject>
153 inline
154 void
155 DGtal::Expander<TObject>
156 ::endLayer()
157 {
158  myCore.insertNew( myLayer.begin(), myLayer.end() );
159 }
160 
161 /**
162  * Computes the next layer just around [src]. The member 'm_core' must
163  * be up to date (i.e, [src] is a subset of 'm_core'). 'm_layer' is
164  * cleared in this method. At first call, [src] should be 'm_core',
165  * then [src] should be 'm_layer'.
166  *
167  * @param src the set around which the new layer is computed.
168  */
169 template <typename TObject>
170 inline
171 void
172 DGtal::Expander<TObject>
173 ::computeNextLayer( const DigitalSet & src )
174 {
175  if ( finished() ) return;
176 
177  ConstIterator p = src.begin();
178  ConstIterator pEnd = src.end();
179  typedef std::set<Point> SetContainer;
180  typedef std::insert_iterator< SetContainer > Inserter;
181  SetContainer newLayer;
182  Inserter inserter( newLayer, newLayer.begin() );
183 
184  // const ObjectDomainPredicate & objectPred = myObjectDomain.predicate();
185  typedef typename ObjectDomain::Predicate ObjectDomainPredicate;
186  typedef functors::BinaryPointPredicate< ObjectDomainPredicate,
187  NotInCoreDomainPredicate > Predicate;
188 
189  Predicate cPred( myObjectDomain.predicate(),
190  myNotInCorePred,
191  functors::andBF2 );
192  // Computes the 1-neighborhood of the core.
193  for ( ; p != pEnd; ++p )
194  {
195  myObjectAdjacency.writeNeighbors
196  ( inserter, *p, cPred );
197  // std::cerr << *p;
198  // for ( unsigned int i = 0; i < v.size(); ++i )
199  // {
200  // std::cerr << " " << v[ i ];
201  // newLayer.insert( v[ i ] );
202  // }
203  // std::cerr << std::endl;
204  // v.clear();
205  }
206  // std::cerr << "Core.size=" << myCore.size()
207  // << " prevLayer.size=" << src.size()
208  // << " nextLayer.size=" << newLayer.size()
209  // << std::endl;
210  // Termination test.
211  if ( newLayer.empty() )
212  myFinished = true;
213  else
214  {
215  myDistance++;
216  myLayer.clear();
217  myLayer.insertNew( newLayer.begin(), newLayer.end() );
218  }
219 }
220 
221 
222 /**
223  * @return the iterator on the first element of the layer.
224  */
225 template <typename TObject>
226 inline
227 const typename DGtal::Expander<TObject>::DigitalSet &
228 DGtal::Expander<TObject>
229 ::core() const
230 {
231  return myCore;
232 }
233 
234 /**
235  * @return a const reference on the (current) layer set of points.
236  */
237 template <typename TObject>
238 inline
239 const typename DGtal::Expander<TObject>::DigitalSet &
240 DGtal::Expander<TObject>
241 ::layer() const
242 {
243  return myLayer;
244 }
245 
246 /**
247  * @return the iterator on the first element of the layer.
248  */
249 template <typename TObject>
250 inline
251 typename DGtal::Expander<TObject>::ConstIterator
252 DGtal::Expander<TObject>
253 ::begin() const
254 {
255  return myLayer.begin();
256 }
257 
258 /**
259  * @return the iterator after the last element of the layer.
260  */
261 template <typename TObject>
262 inline
263 typename DGtal::Expander<TObject>::ConstIterator
264 DGtal::Expander<TObject>
265 ::end() const
266 {
267  return myLayer.end();
268 }
269 
270 
271 ///////////////////////////////////////////////////////////////////////////////
272 // Interface - public :
273 
274 /**
275  * Writes/Displays the object on an output stream.
276  * @param out the output stream where the object is written.
277  */
278 template <typename TObject>
279 inline
280 void
281 DGtal::Expander<TObject>::selfDisplay ( std::ostream & out ) const
282 {
283  out << "[Expander layer=" << myDistance
284  << " layer.size=" << myLayer.size()
285  << " finished=" << myFinished
286  << " ]";
287 }
288 
289 /**
290  * Checks the validity/consistency of the object.
291  * @return 'true' if the object is valid, 'false' otherwise.
292  */
293 template <typename TObject>
294 inline
295 bool
296 DGtal::Expander<TObject>::isValid() const
297 {
298  return true;
299 }
300 
301 
302 
303 ///////////////////////////////////////////////////////////////////////////////
304 // Implementation of inline functions //
305 
306 template <typename TObject>
307 inline
308 std::ostream&
309 DGtal::operator<< ( std::ostream & out,
310  const Expander<TObject> & object )
311 {
312  object.selfDisplay( out );
313  return out;
314 }
315 
316 // //
317 ///////////////////////////////////////////////////////////////////////////////
318 
319