mpadge.tngl.sh
R package for downloading OpenStreetMap data
1/***************************************************************************
2 * Project: osmdata
3 * File: convert_osm_rcpp.cpp
4 * Language: C++
5 *
6 * osmdata is free software: you can redistribute it and/or modify it under
7 * the terms of the GNU General Public License as published by the Free
8 * Software Foundation, either version 3 of the License, or (at your option)
9 * any later version.
10 *
11 * osmdata is distributed in the hope that it will be useful, but WITHOUT ANY
12 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
13 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
14 * details.
15 *
16 * You should have received a copy of the GNU General Public License along with
17 * osm-router. If not, see <http://www.gnu.org/licenses/>.
18 *
19 * Author: Mark Padgham
20 * E-Mail: mark.padgham@email.com
21 *
22 * Description: Functions to convert OSM data stored in C++ arrays to Rcpp
23 * structures.
24 *
25 * Limitations:
26 *
27 * Dependencies: none (rapidXML header included in osmdatar)
28 *
29 * Compiler Options: -std=c++11
30 ***************************************************************************/
31
32#include "convert-osm-rcpp.h"
33
34
35/************************************************************************
36 ************************************************************************
37 ** **
38 ** FUNCTIONS TO CONVERT C++ OBJECTS TO Rcpp::List OBJECTS **
39 ** **
40 ************************************************************************
41 ************************************************************************/
42
43/* Traces a single way and adds (lon,lat,rownames) to an Rcpp::NumericMatrix
44 *
45 * @param &ways pointer to Ways structure
46 * @param &nodes pointer to Nodes structure
47 * @param first_node Last node of previous way to find in current
48 * @param &wayi_id pointer to ID of current way
49 * @lons pointer to vector of longitudes
50 * @lats pointer to vector of latitutdes
51 * @rownames pointer to vector of rownames for each node.
52 * @nmat Rcpp::NumericMatrix to store lons, lats, and rownames
53 */
54void osm_convert::trace_way_nmat (const Ways &ways, const Nodes &nodes,
55 const osmid_t &wayi_id, Rcpp::NumericMatrix &nmat)
56{
57 auto wayi = ways.find (wayi_id);
58 std::vector <std::string> rownames;
59 rownames.clear ();
60 size_t n = wayi->second.nodes.size ();
61 rownames.reserve (n);
62 nmat = Rcpp::NumericMatrix (Rcpp::Dimension (n, 2));
63
64 size_t tempi = 0;
65 for (auto ni = wayi->second.nodes.begin ();
66 ni != wayi->second.nodes.end (); ++ni)
67 {
68 rownames.push_back (std::to_string (*ni));
69 //nmat (tempi, 0) = static_cast <double> (nodes.find (*ni)->second.lon);
70 //nmat (tempi++, 1) = static_cast <double> (nodes.find (*ni)->second.lat);
71 nmat (tempi, 0) = nodes.find (*ni)->second.lon;
72 nmat (tempi++, 1) = nodes.find (*ni)->second.lat;
73 }
74
75 std::vector <std::string> colnames = {"lon", "lat"};
76 Rcpp::List dimnames (0);
77 dimnames.push_back (rownames);
78 dimnames.push_back (colnames);
79 nmat.attr ("dimnames") = dimnames;
80 //dimnames.erase (0, static_cast <int> (dimnames.size ()));
81 dimnames.erase (0, 2);
82}
83
84/* get_value_mat_way
85 *
86 * Extract key-value pairs for a given way and fill Rcpp::CharacterMatrix
87 *
88 * @param wayi Constant iterator to one OSM way
89 * @param Ways Pointer to the std::vector of all ways
90 * @param unique_vals Pointer to the UniqueVals structure
91 * @param value_arr Pointer to the Rcpp::CharacterMatrix of values to be filled
92 * by tracing the key-val pairs of the way 'wayi'
93 * @param rowi Integer value for the key-val pairs for wayi
94 */
95// TODO: Is it faster to use a std::vector <std::string> instead of
96// Rcpp::CharacterMatrix and then simply
97// Rcpp::CharacterMatrix mat (nrow, ncol, value_vec.begin ()); ?
98void osm_convert::get_value_mat_way (Ways::const_iterator wayi,
99 const UniqueVals &unique_vals, Rcpp::CharacterMatrix &value_arr,
100 unsigned int rowi)
101{
102 for (auto kv_iter = wayi->second.key_val.begin ();
103 kv_iter != wayi->second.key_val.end (); ++kv_iter)
104 {
105 const std::string &key = kv_iter->first;
106 unsigned int coli = unique_vals.k_way_index.at (key);
107 value_arr (rowi, coli) = kv_iter->second;
108 }
109}
110
111/* get_value_mat_rel
112 *
113 * Extract key-value pairs for a given relation and fill Rcpp::CharacterMatrix
114 *
115 * @param reli Constant iterator to one OSM relation
116 * @param rels Pointer to the std::vector of all relations
117 * @param unique_vals Pointer to the UniqueVals structure
118 * @param value_arr Pointer to the Rcpp::CharacterMatrix of values to be filled
119 * by tracing the key-val pairs of the relation 'reli'
120 * @param rowi Integer value for the key-val pairs for reli
121 */
122void osm_convert::get_value_mat_rel (Relations::const_iterator &reli,
123 const UniqueVals &unique_vals, Rcpp::CharacterMatrix &value_arr,
124 unsigned int rowi)
125{
126 for (auto kv_iter = reli->key_val.begin (); kv_iter != reli->key_val.end ();
127 ++kv_iter)
128 {
129 const std::string &key = kv_iter->first;
130 unsigned int coli = unique_vals.k_rel_index.at (key);
131 value_arr (rowi, coli) = kv_iter->second;
132 }
133}
134
135
136/* restructure_kv_mat
137 *
138 * Restructures a key-value matrix to reflect typical GDAL output by
139 * inserting a first column containing "osm_id" and moving the "name" column to
140 * second position.
141 *
142 * @param kv Pointer to the key-value matrix to be restructured
143 * @param ls true only for multilinestrings, which have compound rownames which
144 * include roles
145 */
146Rcpp::CharacterMatrix osm_convert::restructure_kv_mat (Rcpp::CharacterMatrix &kv, bool ls=false)
147{
148 // The following has to be done in 2 lines:
149 std::vector <std::vector <std::string> > dims = kv.attr ("dimnames");
150 std::vector <std::string> ids = dims [0], varnames = dims [1], varnames_new;
151 Rcpp::CharacterMatrix kv_out;
152
153 int ni = static_cast <int> (std::distance (varnames.begin (),
154 std::find (varnames.begin (), varnames.end (), "name")));
155 unsigned int add_lines = 1;
156 if (ls)
157 add_lines++;
158
159 // This only processes entries that have key = "name". Those that don't do
160 // not get their osm_id values appended. It's then easier to post-append
161 // these, rather than modify this code
162 if (ni < static_cast <int> (varnames.size ()))
163 {
164 Rcpp::CharacterVector name_vals = kv.column (ni);
165 Rcpp::CharacterVector roles; // only for ls, but has to be defined here
166 // convert ids to CharacterVector - direct allocation doesn't work
167 Rcpp::CharacterVector ids_rcpp (ids.size ());
168 if (!ls)
169 for (unsigned int i=0; i<ids.size (); i++)
170 ids_rcpp (i) = ids [i];
171 else
172 { // extract way roles for multilinestring kev-val matrices
173 roles = Rcpp::CharacterVector (ids.size ());
174 for (unsigned int i=0; i<ids.size (); i++)
175 {
176 size_t ipos = ids [i].find ("-", 0);
177 ids_rcpp (i) = ids [i].substr (0, ipos).c_str ();
178 roles (i) = ids [i].substr (ipos + 1, ids[i].length () - ipos);
179 }
180 }
181
182 varnames_new.reserve (static_cast <unsigned int> (kv.ncol ()) +
183 add_lines);
184 varnames_new.push_back ("osm_id");
185 varnames_new.push_back ("name");
186 kv_out = Rcpp::CharacterMatrix (Rcpp::Dimension (
187 static_cast <unsigned int> (kv.nrow ()),
188 static_cast <unsigned int> (kv.ncol ()) + add_lines));
189 kv_out.column (0) = ids_rcpp;
190 kv_out.column (1) = name_vals;
191 if (ls)
192 {
193 varnames_new.push_back ("role");
194 kv_out.column (2) = roles;
195 }
196 int count = 1 + static_cast <int> (add_lines);
197 int i_int = 0;
198 for (unsigned int i=0; i<static_cast <unsigned int> (kv.ncol ()); i++)
199 {
200 if (i != static_cast <unsigned int> (ni))
201 {
202 varnames_new.push_back (varnames [i]);
203 kv_out.column (count++) = kv.column (i_int);
204 }
205 i_int++;
206 }
207 kv_out.attr ("dimnames") = Rcpp::List::create (ids, varnames_new);
208 } else
209 kv_out = kv;
210
211 return kv_out;
212}
213
214/* convert_poly_linestring_to_sf
215 *
216 * Converts the data contained in all the arguments into an Rcpp::List object
217 * to be used as the geometry column of a Simple Features Colletion
218 *
219 * @param lon_arr 3D array of longitudinal coordinates
220 * @param lat_arr 3D array of latgitudinal coordinates
221 * @param rowname_arr 3D array of <osmid_t> IDs for nodes of all (lon,lat)
222 * @param id_vec 2D array of either <std::string> or <osmid_t> IDs for all ways
223 * used in the geometry.
224 * @param rel_id Vector of <osmid_t> IDs for each relation.
225 *
226 * @return An Rcpp::List object of [relation][way][node/geom] data.
227 */
228// TODO: Replace return value with pointer to List as argument?
229template <typename T> Rcpp::List osm_convert::convert_poly_linestring_to_sf (
230 const double_arr3 &lon_arr, const double_arr3 &lat_arr,
231 const string_arr3 &rowname_arr,
232 const std::vector <std::vector <T> > &id_vec,
233 const std::vector <std::string> &rel_id, const std::string type)
234{
235 if (!(type == "MULTILINESTRING" || type == "MULTIPOLYGON"))
236 throw std::runtime_error ("type must be multilinestring/polygon"); // # nocov
237 Rcpp::List outList (lon_arr.size ());
238 Rcpp::NumericMatrix nmat (Rcpp::Dimension (0, 0));
239 Rcpp::List dimnames (0);
240 std::vector <std::string> colnames = {"lat", "lon"};
241 for (unsigned int i=0; i<lon_arr.size (); i++) // over all relations
242 {
243 Rcpp::List outList_i (lon_arr [i].size ());
244 for (unsigned int j=0; j<lon_arr [i].size (); j++) // over all ways
245 {
246 size_t n = lon_arr [i][j].size ();
247 nmat = Rcpp::NumericMatrix (Rcpp::Dimension (n, 2));
248 std::copy (lon_arr [i][j].begin (), lon_arr [i][j].end (),
249 nmat.begin ());
250 std::copy (lat_arr [i][j].begin (), lat_arr [i][j].end (),
251 nmat.begin () + n);
252 dimnames.push_back (rowname_arr [i][j]);
253 dimnames.push_back (colnames);
254 nmat.attr ("dimnames") = dimnames;
255 //dimnames.erase (0, static_cast <int> (dimnames.size ()));
256 dimnames.erase (0, 2);
257 outList_i [j] = nmat;
258 }
259 outList_i.attr ("names") = id_vec [i];
260 if (type == "MULTIPOLYGON")
261 {
262 Rcpp::List tempList (1);
263 tempList (0) = outList_i;
264 tempList.attr ("class") = Rcpp::CharacterVector::create ("XY", type, "sfg");
265 outList [i] = tempList;
266 } else
267 {
268 outList_i.attr ("class") = Rcpp::CharacterVector::create ("XY", type, "sfg");
269 outList [i] = outList_i;
270 }
271 }
272 outList.attr ("names") = rel_id;
273
274 return outList;
275}
276template Rcpp::List osm_convert::convert_poly_linestring_to_sf <osmid_t> (
277 const double_arr3 &lon_arr, const double_arr3 &lat_arr,
278 const string_arr3 &rowname_arr,
279 const std::vector <std::vector <osmid_t> > &id_vec,
280 const std::vector <std::string> &rel_id, const std::string type);
281template Rcpp::List osm_convert::convert_poly_linestring_to_sf <std::string> (
282 const double_arr3 &lon_arr, const double_arr3 &lat_arr,
283 const string_arr3 &rowname_arr,
284 const std::vector <std::vector <std::string> > &id_vec,
285 const std::vector <std::string> &rel_id, const std::string type);
286
287/* convert_multipoly_to_sp
288 *
289 * Converts the data contained in all the arguments into a
290 * SpatialPolygonsDataFrame
291 *
292 * @param lon_arr 3D array of longitudinal coordinates
293 * @param lat_arr 3D array of latgitudinal coordinates
294 * @param rowname_arr 3D array of <osmid_t> IDs for nodes of all (lon,lat)
295 * @param id_vec 2D array of either <std::string> or <osmid_t> IDs for all ways
296 * used in the geometry.
297 * @param rel_id Vector of <osmid_t> IDs for each relation.
298 *
299 * @return Object pointed to by 'multipolygons' is constructed.
300 */
301void osm_convert::convert_multipoly_to_sp (Rcpp::S4 &multipolygons, const Relations &rels,
302 const double_arr3 &lon_arr, const double_arr3 &lat_arr,
303 const string_arr3 &rowname_arr, const string_arr2 &id_vec,
304 const UniqueVals &unique_vals)
305{
306 Rcpp::Environment sp_env = Rcpp::Environment::namespace_env ("sp");
307 Rcpp::Function Polygon = sp_env ["Polygon"];
308 Rcpp::Language polygons_call ("new", "Polygons");
309
310 size_t nrow = lon_arr.size (), ncol = unique_vals.k_rel.size ();
311 Rcpp::CharacterMatrix kv_mat (Rcpp::Dimension (nrow, ncol));
312 std::fill (kv_mat.begin (), kv_mat.end (), NA_STRING);
313
314 Rcpp::List outList (lon_arr.size ());
315 Rcpp::NumericMatrix nmat (Rcpp::Dimension (0, 0));
316 Rcpp::List dimnames (0);
317 std::vector <std::string> colnames = {"lat", "lon"}, rel_id;
318
319 unsigned int npolys = 0;
320 for (auto itr = rels.begin (); itr != rels.end (); itr++)
321 if (itr->ispoly)
322 npolys++;
323 if (npolys != lon_arr.size ())
324 throw std::runtime_error ("polygons must be same size as geometries"); // # nocov
325 rel_id.reserve (npolys);
326
327 unsigned int i = 0;
328 for (auto itr = rels.begin (); itr != rels.end (); itr++)
329 if (itr->ispoly)
330 {
331 Rcpp::List outList_i (lon_arr [i].size ());
332 // j over all ways, with outer always first followed by inner
333 bool outer = true;
334 //std::vector <int> plotorder (lon_arr [i].size ());
335 Rcpp::IntegerVector plotorder (lon_arr [i].size ());
336 for (unsigned int j=0; j<lon_arr [i].size (); j++)
337 {
338 size_t n = lon_arr [i][j].size ();
339 nmat = Rcpp::NumericMatrix (Rcpp::Dimension (n, 2));
340 std::copy (lon_arr [i][j].begin (), lon_arr [i][j].end (),
341 nmat.begin ());
342 std::copy (lat_arr [i][j].begin (), lat_arr [i][j].end (),
343 nmat.begin () + n);
344 dimnames.push_back (rowname_arr [i][j]);
345 dimnames.push_back (colnames);
346 nmat.attr ("dimnames") = dimnames;
347 //dimnames.erase (0, static_cast <int> (dimnames.size ()));
348 dimnames.erase (0, 2);
349
350 Rcpp::S4 poly = Polygon (nmat);
351 poly.slot ("hole") = !outer;
352 poly.slot ("ringDir") = static_cast <int> (1);
353 if (outer)
354 outer = false;
355 else
356 poly.slot ("ringDir") = static_cast <int> (-1);
357 outList_i [j] = poly;
358 plotorder [j] = static_cast <int> (j) + 1; // 1-based R values
359 }
360 outList_i.attr ("names") = id_vec [i];
361
362 Rcpp::S4 polygons = polygons_call.eval ();
363 polygons.slot ("Polygons") = outList_i;
364 // Issue #36 caused by data with one item having no actual data for
365 // one item, so id_vec[i].size = lon_vec[i].size = ... = 0
366 if (id_vec [i].size () > 0)
367 {
368 // convert id_vec to single string
369 std::string id_vec_str = id_vec [i] [0];
370 for (unsigned int j = 1;
371 j < static_cast <unsigned int> (id_vec [i].size ()); j++)
372 id_vec_str += "." + id_vec [i] [j];
373 polygons.slot ("ID") = id_vec_str;
374 }
375 //polygons.slot ("ID") = id_vec [i]; // sp expects char not vec!
376 polygons.slot ("plotOrder") = plotorder;
377 //polygons.slot ("labpt") = poly.slot ("labpt");
378 //polygons.slot ("area") = poly.slot ("area");
379 outList [i] = polygons;
380 rel_id.push_back (std::to_string (itr->id));
381
382 osm_convert::get_value_mat_rel (itr, unique_vals, kv_mat, i++);
383 } // end if ispoly & for i
384 outList.attr ("names") = rel_id;
385
386 Rcpp::Language sp_polys_call ("new", "SpatialPolygonsDataFrame");
387 multipolygons = sp_polys_call.eval ();
388 multipolygons.slot ("polygons") = outList;
389
390 // Fill plotOrder slot with int vector - this has to be int, not
391 // unsigned int!
392 std::vector <int> plotord (rels.size ());
393 for (size_t j = 0; j < rels.size (); j++)
394 plotord [j] = static_cast <int> (j + 1);
395 multipolygons.slot ("plotOrder") = plotord;
396 plotord.clear ();
397
398 Rcpp::DataFrame kv_df = R_NilValue;
399 if (rel_id.size () > 0)
400 {
401 kv_mat.attr ("names") = unique_vals.k_rel;
402 kv_mat.attr ("dimnames") = Rcpp::List::create (rel_id, unique_vals.k_rel);
403 kv_mat.attr ("names") = unique_vals.k_rel;
404 if (kv_mat.nrow () > 0 && kv_mat.ncol () > 0)
405 kv_df = osm_convert::restructure_kv_mat (kv_mat, false);
406 multipolygons.slot ("data") = kv_df;
407 }
408 rel_id.clear ();
409}
410
411
412/* convert_multiline_to_sp
413 *
414 * Converts the data contained in all the arguments into a SpatialLinesDataFrame
415 *
416 * @param lon_arr 3D array of longitudinal coordinates
417 * @param lat_arr 3D array of latgitudinal coordinates
418 * @param rowname_arr 3D array of <osmid_t> IDs for nodes of all (lon,lat)
419 * @param id_vec 2D array of either <std::string> or <osmid_t> IDs for all ways
420 * used in the geometry.
421 * @param rel_id Vector of <osmid_t> IDs for each relation.
422 *
423 * @return Object pointed to by 'multilines' is constructed.
424 */
425void osm_convert::convert_multiline_to_sp (Rcpp::S4 &multilines, const Relations &rels,
426 const double_arr3 &lon_arr, const double_arr3 &lat_arr,
427 const string_arr3 &rowname_arr, const osmt_arr2 &id_vec,
428 const UniqueVals &unique_vals)
429{
430
431 Rcpp::Language line_call ("new", "Line");
432 Rcpp::Language lines_call ("new", "Lines");
433
434 Rcpp::NumericMatrix nmat (Rcpp::Dimension (0, 0));
435 Rcpp::List dimnames (0);
436 std::vector <std::string> colnames = {"lat", "lon"}, rel_id;
437
438 unsigned int nlines = 0;
439 for (auto itr = rels.begin (); itr != rels.end (); itr++)
440 if (!itr->ispoly)
441 nlines++;
442 rel_id.reserve (nlines);
443
444 Rcpp::List outList (nlines);
445 size_t ncol = unique_vals.k_rel.size ();
446 Rcpp::CharacterMatrix kv_mat (Rcpp::Dimension (nlines, ncol));
447 std::fill (kv_mat.begin (), kv_mat.end (), NA_STRING);
448
449 unsigned int i = 0;
450 for (auto itr = rels.begin (); itr != rels.end (); itr++)
451 if (!itr->ispoly)
452 {
453 Rcpp::List outList_i (lon_arr [i].size ());
454 // j over all ways
455 for (unsigned int j=0; j<lon_arr [i].size (); j++)
456 {
457 size_t n = lon_arr [i][j].size ();
458 nmat = Rcpp::NumericMatrix (Rcpp::Dimension (n, 2));
459 std::copy (lon_arr [i][j].begin (), lon_arr [i][j].end (),
460 nmat.begin ());
461 std::copy (lat_arr [i][j].begin (), lat_arr [i][j].end (),
462 nmat.begin () + n);
463 dimnames.push_back (rowname_arr [i][j]);
464 dimnames.push_back (colnames);
465 nmat.attr ("dimnames") = dimnames;
466 //dimnames.erase (0, static_cast <int> (dimnames.size ()));
467 dimnames.erase (0, 2);
468
469 Rcpp::S4 line = line_call.eval ();
470 line.slot ("coords") = nmat;
471
472 outList_i [j] = line;
473 }
474 outList_i.attr ("names") = id_vec [i]; // implicit type conversion
475 Rcpp::S4 lines = lines_call.eval ();
476 lines.slot ("Lines") = outList_i;
477 lines.slot ("ID") = itr->id;
478
479 outList [i] = lines;
480 rel_id.push_back (std::to_string (itr->id));
481
482 osm_convert::get_value_mat_rel (itr, unique_vals, kv_mat, i++);
483 } // end if ispoly & for i
484 outList.attr ("names") = rel_id;
485
486 Rcpp::Language sp_lines_call ("new", "SpatialLinesDataFrame");
487 multilines = sp_lines_call.eval ();
488 multilines.slot ("lines") = outList;
489
490 Rcpp::DataFrame kv_df = R_NilValue;
491 if (rel_id.size () > 0)
492 {
493 kv_mat.attr ("names") = unique_vals.k_rel;
494 kv_mat.attr ("dimnames") = Rcpp::List::create (rel_id, unique_vals.k_rel);
495 kv_mat.attr ("names") = unique_vals.k_rel;
496 if (kv_mat.nrow () > 0 && kv_mat.ncol () > 0)
497 kv_df = osm_convert::restructure_kv_mat (kv_mat, true);
498 multilines.slot ("data") = kv_df;
499 }
500 rel_id.clear ();
501}
502
503/* convert_relation_to_sc
504 *
505 * Converts the data contained in all the arguments into an SC object
506 *
507 * @param id_vec 2D array of either <std::string> or <osmid_t> IDs for all ways
508 * used in the geometry.
509 *
510 * @return Objects pointed to by 'members_out' and 'kv_out' are constructed.
511 */
512void osm_convert::convert_relation_to_sc (string_arr2 &members_out,
513 string_arr2 &kv_out, const Relations &rels,
514 const UniqueVals &unique_vals)
515{
516 size_t nmembers = 0;
517 for (auto itr = rels.begin (); itr != rels.end (); itr++)
518 nmembers += itr->relations.size ();
519
520 members_out.resize (nmembers);
521 for (auto m: members_out)
522 m.resize (3);
523
524 size_t ncol = unique_vals.k_rel.size ();
525 kv_out.resize (ncol);
526 for (auto k: kv_out)
527 k.resize (rels.size ());
528
529 unsigned int rowi = 0; // explicit loop index - see note at top of osmdata-sf
530 for (auto itr = rels.begin (); itr != rels.end (); itr++)
531 {
532 //const unsigned int rowi = static_cast <unsigned int> (
533 // std::distance (rels.begin (), itr));
534
535 // Get all members of that relation and their roles:
536 unsigned int rowj = rowi;
537 for (auto ritr = itr->relations.begin ();
538 ritr != itr->relations.end (); ++ritr)
539 {
540 //const unsigned int rowj = rowi + static_cast <unsigned int> (
541 // std::distance (itr->relations.begin (), ritr));
542 members_out [rowj] [0] = std::to_string (itr->id);
543 members_out [rowj] [1] = std::to_string (ritr->first); // OSM id
544 members_out [rowj++] [2] = ritr->second; // role
545 }
546
547 // And then key-value pairs
548 for (auto kv_iter = itr->key_val.begin ();
549 kv_iter != itr->key_val.end (); ++kv_iter)
550 {
551 const std::string &key = kv_iter->first;
552 //long int coli = static_cast <long int> (
553 // unique_vals.k_rel_index.at (key));
554 unsigned int coli = unique_vals.k_rel_index.at (key);
555 kv_out [coli] [rowi] = kv_iter->second;
556 }
557 rowi++;
558 } // end for itr
559}