This file is indexed.

/usr/include/osmium/relations/assembler.hpp is in libosmium-dev 0.0~20160124-b30afd3-1.

This file is owned by root:root, with mode 0o644.

The actual contents of the file can be viewed below.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
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
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
#ifndef OSMIUM_RELATIONS_ASSEMBLER_HPP
#define OSMIUM_RELATIONS_ASSEMBLER_HPP

/*

Copyright 2012 Jochen Topf <jochen@topf.org> and others (see README).

This file is part of Osmium (https://github.com/joto/osmium).

Osmium is free software: you can redistribute it and/or modify it under the
terms of the GNU Lesser General Public License or (at your option) the GNU
General Public License as published by the Free Software Foundation, either
version 3 of the Licenses, or (at your option) any later version.

Osmium 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 and the GNU
General Public License for more details.

You should have received a copy of the Licenses along with Osmium. If not, see
<http://www.gnu.org/licenses/>.

*/

#include <algorithm>
#include <cassert>
#include <iostream>
#include <utility>
#include <vector>
#include <boost/foreach.hpp>
#include <boost/utility.hpp>

#include <osmium/handler.hpp>
#include <osmium/relations/relation_info.hpp>

namespace Osmium {

    /**
     * @brief Namespace for code related to OSM relations
     */
    namespace Relations {

        /**
         * Helper class for the Assembler class.
         *
         * Stores an object ID and information where the object should be
         * stored.
         */
        struct MemberInfo {

            /**
             * Object ID of this relation member. Can be a node, way, or relation ID.
             * It depends on the vector in which this object is stored which kind of
             * object is referenced here.
             */
            osm_object_id_t m_member_id;

            /**
             * Position of the relation this member is a part of in the
             * m_relations vector.
             */
            unsigned int m_relation_pos;

            /**
             * Position of this member in the list of members of the
             * relation this member if a part of.
             */
            osm_sequence_id_t m_member_pos;

            /**
             * Create new MemberInfo. The variant with zeros for relation_pos and
             * member_pos is used to create dummy MemberInfo that can be compared
             * to the MemberInfo in the vectors using the equal_range algorithm.
             */
            MemberInfo(osm_object_id_t member_id, int relation_pos=0, osm_sequence_id_t member_pos=0) :
                m_member_id(member_id),
                m_relation_pos(relation_pos),
                m_member_pos(member_pos) {
            }

        };

        /**
         * Compares two MemberInfo objects by only looking at the member id.
         * Used to sort a vector of MemberInfo objects and to later find
         * them using binary search.
         */
        bool operator<(const MemberInfo& a, const MemberInfo& b) {
            return a.m_member_id < b.m_member_id;
        }

        typedef std::vector<MemberInfo> member_info_vector_t;

        /**
         * The Assembler class assembles relations and their members. This is a generic
         * base class that can be used to assemble all kinds of relations. It has numerous
         * hooks you can implement in child classes to customize its behaviour.
         *
         * The assembler provides two handlers (HandlerPass1 and HandlerPass2) for a first
         * and second pass through an input file, respectively. In the first pass all
         * relations we are interested in are stored in TRelationInfo objects in the
         * m_relations vector. All members we are interested in are stored in MemberInfo
         * objects in the m_member_nodes, m_member_ways, and m_member_relations vectors.
         * The MemberInfo objects also store the information where the relations containing
         * those members are to be found.
         *
         * Later the m_member_(nodes|ways|relations) vectors are sorted according to the
         * member ids so that a binary search (with equal_range) can be used in the second
         * pass to find the relations for each node, way, or relation coming along. The
         * member objects are stored together with their relation and once a relation is
         * complete the complete_relation() method is called which you can overwrite in
         * a child class of Assembler.
         *
         * @tparam TAssembler Child class of this class.
         *
         * @tparam TRelationInfo RelationInfo or a child class of it.
         *
         * @tparam N Are we interested in member nodes?
         *
         * @tparam W Are we interested in member ways?
         *
         * @tparam R Are we interested in member relations?
         *
         * @tparam THandler Nested handler that is called at the end of each method in
         *         HandlerPass2. Defaults to Osmium::Handler::Base which does nothing.
         */
        template <class TAssembler, class TRelationInfo, bool N, bool W, bool R, class THandler=Osmium::Handler::Base>
        class Assembler {

            /// Vector of RelationInfo objects used to store relations we are interested in.
            typedef std::vector<TRelationInfo> relation_info_vector_t;

            /// This is the type used for results of the equal_range algorithm.
            typedef std::pair<typename member_info_vector_t::iterator, typename member_info_vector_t::iterator> member_info_range_t;

        public:

            /**
             * Create an Assembler without nested handler.
             */
            Assembler() :
                m_base_handler(),
                m_next_handler(m_base_handler),
                m_handler_pass1(*static_cast<TAssembler*>(this)),
                m_handler_pass2(*static_cast<TAssembler*>(this)),
                m_relations(),
                m_member_infos() {
            }

            /**
             * Create an Assembler with nested handler.
             */
            Assembler(THandler& handler) :
                m_base_handler(),
                m_next_handler(handler),
                m_handler_pass1(*static_cast<TAssembler*>(this)),
                m_handler_pass2(*static_cast<TAssembler*>(this)),
                m_relations(),
                m_member_infos() {
            }

        protected:

            const relation_info_vector_t& relations() const {
                return m_relations;
            }

            /**
             * This method is called from the first pass handler for every
             * relation in the input. It calls add_relation() to add this
             * relation to the list of relations we are interested in.
             *
             * Overwrite this method in a child class to only call add_relation
             * on the relations you are interested in, for instance depending
             * on the type tag. Storing relations takes a lot of memory, so
             * it makes sense to filter this as much as possible.
             */
            void relation(const shared_ptr<Osmium::OSM::Relation const>& relation) {
                add_relation(TRelationInfo(relation));
            }

            /**
             * This method is called for every member of every relation that
             * is added with add_relation(). It should decide if the member
             * is interesting or not and return true or false to signal that.
             * Only interesting members are later added to the relation.
             *
             * Overwrite this method in a child class. In the MultiPolygonAssembler
             * this is for instance used to only keep members of type way and
             * ignore all others.
             */
            bool keep_member(Osmium::Relations::RelationInfo& /*relation_info*/, const Osmium::OSM::RelationMember& /*member*/) {
                return true;
            }

            /**
             * This method is called for all nodes that are not a member of
             * any relation.
             *
             * Overwrite this method in a child class if you are interested
             * in this.
             */
            void node_not_in_any_relation(const shared_ptr<Osmium::OSM::Node const>& /*node*/) {
            }

            /**
             * This method is called for all ways that are not a member of
             * any relation.
             *
             * Overwrite this method in a child class if you are interested
             * in this.
             */
            void way_not_in_any_relation(const shared_ptr<Osmium::OSM::Way const>& /*way*/) {
            }

            /**
             * This method is called for all relations that are not a member of
             * any relation.
             *
             * Overwrite this method in a child class if you are interested
             * in this.
             */
            void relation_not_in_any_relation(const shared_ptr<Osmium::OSM::Relation const>& /*relation*/) {
            }

            /**
             * This method is called from the handler when all objects that are
             * wanted as relation members are available.
             *
             * Overwrite this method in a child class if you are interested
             * in this.
             *
             * Note that even after this call members might be missing if they
             * were not in the input file!
             */
            void all_members_available() {
            }

            /**
             * This removes all relations that have already been assembled
             * from the m_relations vector.
             */
            void clean_assembled_relations() {
                m_relations.erase(std::remove_if(m_relations.begin(), m_relations.end(), has_all_members()), m_relations.end());
            }

            /**
             * Tell the Assembler that you are interested in this relation
             * and want it kept until all members have been assembled and
             * it is handed back to you.
             */
            void add_relation(TRelationInfo relation_info) {
                osm_sequence_id_t n=0;
                BOOST_FOREACH(const Osmium::OSM::RelationMember& member, relation_info.relation()->members()) {
                    bool add = static_cast<TAssembler*>(this)->keep_member(relation_info, member);
                    if (add) {
                        MemberInfo member_info(member.ref(), m_relations.size(), n);
                        switch (member.type()) {
                            case 'n':
                                m_member_infos[NODE].push_back(member_info);
                                break;
                            case 'w':
                                m_member_infos[WAY].push_back(member_info);
                                break;
                            case 'r':
                                m_member_infos[RELATION].push_back(member_info);
                                break;
                        }
                        relation_info.need_member();
                    }
                    n++;
                }
                m_relations.push_back(relation_info);
            }

            /**
             * Return a reference to the nested handler that is called
             * in the second pass after the Assembler's own handler.
             */
            THandler& nested_handler() {
                return m_next_handler;
            }

            /**
             * Sort the vectors with the member infos so that we can do binary
             * search on them.
             */
            void sort_member_infos() {
                std::sort(m_member_infos[NODE].begin(),     m_member_infos[NODE].end());
                std::sort(m_member_infos[WAY].begin(),      m_member_infos[WAY].end());
                std::sort(m_member_infos[RELATION].begin(), m_member_infos[RELATION].end());
            }

        public:

            uint64_t used_memory() const {
                uint64_t nmembers = m_member_infos[NODE].size() + m_member_infos[WAY].size() + m_member_infos[RELATION].size();
                uint64_t relations = m_relations.size() * (sizeof(TRelationInfo) + sizeof(Osmium::OSM::Relation)) + nmembers * sizeof(Osmium::OSM::RelationMember); // plus tags
                uint64_t members = nmembers * sizeof(MemberInfo);

                std::cout << "nR  = m_relations.size()             = " << m_relations.size() << "\n";
                std::cout << "nMN = m_member_info[NODE].size()     = " << m_member_infos[NODE].size() << "\n";
                std::cout << "nMW = m_member_info[WAY].size()      = " << m_member_infos[WAY].size() << "\n";
                std::cout << "nMR = m_member_info[RELATION].size() = " << m_member_infos[RELATION].size() << "\n";
                std::cout << "nM  = m_member_info[*].size()        = " << nmembers << "\n";

                std::cout << "sRI = sizeof(TRelationInfo)  = " << sizeof(TRelationInfo) << "\n";
                std::cout << "sR  = sizeof(Relation)       = " << sizeof(Osmium::OSM::Relation) << "\n";
                std::cout << "sRM = sizeof(RelationMember) = " << sizeof(Osmium::OSM::RelationMember) << "\n";
                std::cout << "sMI = sizeof(MemberInfo)     = " << sizeof(MemberInfo) << "\n";

                std::cout << "nR * (sRI + sR) = " << m_relations.size() * (sizeof(TRelationInfo) + sizeof(Osmium::OSM::Relation)) << "\n";
                std::cout << "nM * sRM        = " << nmembers * sizeof(Osmium::OSM::RelationMember) << "\n";
                std::cout << "nM * sMI        = " << nmembers * sizeof(MemberInfo) << "\n";

                return relations + members;
            }

            /**
             * This is the handler class for the first pass of the Assembler.
             */
            class HandlerPass1 : public Osmium::Handler::Base {

                TAssembler& m_assembler;

            public:

                HandlerPass1(TAssembler& assembler) :
                    Osmium::Handler::Base(),
                    m_assembler(assembler) {
                }

                void relation(const shared_ptr<Osmium::OSM::Relation const>& relation) {
                    m_assembler.relation(relation);
                }

                void after_relations() const {
                    m_assembler.sort_member_infos();
                    throw Osmium::Handler::StopReading();
                }

            }; // class HandlerPass1

            /**
             * This is the handler class for the second pass of the Assembler.
             */
            class HandlerPass2 {

                TAssembler& m_assembler;

                /**
                 * This variable is initialized with the number of different
                 * kinds of OSM objects we are interested in. If we only need
                 * way members (for instance for the multipolygon assembler)
                 * it is intialized with 1 for instance. If node and way
                 * members are needed, it is initialized with 2.
                 *
                 * In the after_* methods of this handler, it is decremented
                 * and once it reaches 0, we know we have all members available
                 * that we are ever going to get.
                 */
                int m_want_types;

                /**
                 * Find this object in the member vectors and add it to all
                 * relations that need it.
                 *
                 * @returns true if the member was added to at least one
                 *          relation and false otherwise
                 */
                bool find_and_add_object(const shared_ptr<Osmium::OSM::Object const>& object) const {
                    member_info_vector_t& miv = m_assembler.m_member_infos[object->type()];
                    const member_info_range_t range = std::equal_range(miv.begin(), miv.end(), MemberInfo(object->id()));

                    if (range.first == range.second) {
                        // nothing found
                        return false;
                    }

                    BOOST_FOREACH(const MemberInfo& member_info, range) {
                        assert(member_info.m_member_id == object->id());
                        assert(member_info.m_relation_pos < m_assembler.m_relations.size());
                        TRelationInfo& relation_info = m_assembler.m_relations[member_info.m_relation_pos];
                        assert(member_info.m_member_pos < relation_info.relation()->members().size());
                        if (relation_info.add_member(object, member_info.m_member_pos)) {
                            m_assembler.complete_relation(relation_info);
                            m_assembler.m_relations[member_info.m_relation_pos] = TRelationInfo();
                        }
                    }

                    return true;
                }

                /**
                 * This method is called from the after_* methods. It reclaimes
                 * memory that's not needed any more and calls
                 * all_members_available() if they are.
                 */
                void after(osm_object_type_t type) {
                    // clear all memory used by m_member_info of this type
                    member_info_vector_t().swap(m_assembler.m_member_infos[type]);
                    if (--m_want_types == 0) {
                        m_assembler.all_members_available();
                    }
                }

            public:

                HandlerPass2(TAssembler& assembler) :
                    m_assembler(assembler),
                    m_want_types((N?1:0) + (W?1:0) + (R?1:0)) {
                }

                void init(Osmium::OSM::Meta& meta) const {
                    m_assembler.m_next_handler.init(meta);
                }

                void before_nodes() const {
                    m_assembler.m_next_handler.before_nodes();
                }

                void node(const shared_ptr<Osmium::OSM::Node const>& node) const {
                    if (N) {
                        if (! find_and_add_object(node)) {
                            m_assembler.node_not_in_any_relation(node);
                        }
                    }
                    m_assembler.m_next_handler.node(node);
                }

                void after_nodes() {
                    if (N) {
                        after(NODE);
                    }
                    m_assembler.m_next_handler.after_nodes();
                }

                void before_ways() const {
                    m_assembler.m_next_handler.before_ways();
                }

                void way(const shared_ptr<Osmium::OSM::Way const>& way) const {
                    if (W) {
                        if (! find_and_add_object(way)) {
                            m_assembler.way_not_in_any_relation(way);
                        }
                    }
                    m_assembler.m_next_handler.way(way);
                }

                void after_ways() {
                    if (W) {
                        after(WAY);
                    }
                    m_assembler.m_next_handler.after_ways();
                }

                void before_relations() const {
                    m_assembler.m_next_handler.before_relations();
                }

                void relation(const shared_ptr<Osmium::OSM::Relation const>& relation) const {
                    if (R) {
                        if (! find_and_add_object(relation)) {
                            m_assembler.relation_not_in_any_relation(relation);
                        }
                    }
                    m_assembler.m_next_handler.relation(relation);
                }

                void after_relations() {
                    if (R) {
                        after(RELATION);
                    }
                    m_assembler.m_next_handler.after_relations();
                }

                void final() const {
                    m_assembler.m_next_handler.final();
                }

            }; // class HandlerPass2

            /**
             * Return reference to first pass handler.
             */
            HandlerPass1& handler_pass1() {
                return m_handler_pass1;
            }

            /**
             * Return reference to second pass handler.
             */
            HandlerPass2& handler_pass2() {
                return m_handler_pass2;
            }

        private:

            /**
             * This base handler is used as default if no chained handler was
             * given to the Assembler.
             */
            Osmium::Handler::Base m_base_handler;

            /// Reference to chained handler
            THandler& m_next_handler;

            HandlerPass1 m_handler_pass1;
            HandlerPass2 m_handler_pass2;

            /// Vector with all relations we are interested in
            relation_info_vector_t m_relations;

            /**
             * One vector each for nodes, ways, and relations containing all
             * mappings from member ids to their relations.
             */
            member_info_vector_t m_member_infos[3];

        }; // class Assembler

    } // namespace Relations

} // namespace Osmium

#endif // OSMIUM_RELATIONS_ASSEMBLER_HPP