#ifndef OSMIUM_AREA_DETAIL_BASIC_ASSEMBLER_HPP
#define OSMIUM_AREA_DETAIL_BASIC_ASSEMBLER_HPP

/*

This file is part of Osmium (https://osmcode.org/libosmium).

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

Boost Software License - Version 1.0 - August 17th, 2003

Permission is hereby granted, free of charge, to any person or organization
obtaining a copy of the software and accompanying documentation covered by
this license (the "Software") to use, reproduce, display, distribute,
execute, and transmit the Software, and to prepare derivative works of the
Software, and to permit third-parties to whom the Software is furnished to
do so, all subject to the following:

The copyright notices in the Software and this entire statement, including
the above license grant, this restriction and the following disclaimer,
must be included in all copies of the Software, in whole or in part, and
all derivative works of the Software, unless such copies or derivative
works are solely in the form of machine-executable object code generated by
a source language processor.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
DEALINGS IN THE SOFTWARE.

*/

#include <osmium/area/assembler_config.hpp>
#include <osmium/area/detail/node_ref_segment.hpp>
#include <osmium/area/detail/proto_ring.hpp>
#include <osmium/area/detail/segment_list.hpp>
#include <osmium/area/problem_reporter.hpp>
#include <osmium/area/stats.hpp>
#include <osmium/builder/osm_object_builder.hpp>
#include <osmium/osm/location.hpp>
#include <osmium/osm/node_ref.hpp>
#include <osmium/osm/types.hpp>
#include <osmium/osm/way.hpp>
#include <osmium/util/iterator.hpp>
#include <osmium/util/timer.hpp>

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <cstdlib>
#include <exception>
#include <iostream>
#include <iterator>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

namespace osmium {

    namespace area {

        namespace detail {

            using open_ring_its_type = std::list<std::list<ProtoRing>::iterator>;

            struct location_to_ring_map {
                osmium::Location location;
                open_ring_its_type::iterator ring_it{};
                bool start{false};

                location_to_ring_map(osmium::Location l, open_ring_its_type::iterator r, const bool s) noexcept :
                    location(l),
                    ring_it(r),
                    start(s) {
                }

                explicit location_to_ring_map(osmium::Location l) noexcept :
                    location(l) {
                }

                const ProtoRing& ring() const noexcept {
                    return **ring_it;
                }

            }; // struct location_to_ring_map

            inline bool operator==(const location_to_ring_map& lhs, const location_to_ring_map& rhs) noexcept {
                return lhs.location == rhs.location;
            }

            inline bool operator<(const location_to_ring_map& lhs, const location_to_ring_map& rhs) noexcept {
                return lhs.location < rhs.location;
            }

            /**
             * Class for assembling ways and relations into multipolygons
             * (areas). Contains the basic functionality needed but is not
             * used directly. Use the osmium::area::Assembler class instead.
             */
            class BasicAssembler {

                static constexpr const std::size_t max_split_locations = 100ULL;

                // Maximum recursion depth, stops complex multipolygons from
                // breaking everything.
                enum : unsigned {
                    max_depth = 20U
                };

                struct slocation {

                    enum {
                        invalid_item = 1U << 30U
                    };

                    uint32_t item : 31;
                    uint32_t reverse : 1;

                    slocation() noexcept :
                        item(invalid_item),
                        reverse(false) {
                    }

                    explicit slocation(uint32_t n, bool r = false) noexcept :
                        item(n),
                        reverse(r) {
                    }

                    osmium::Location location(const SegmentList& segment_list) const noexcept {
                        const auto& segment = segment_list[item];
                        return reverse ? segment.second().location() : segment.first().location();
                    }

                    const osmium::NodeRef& node_ref(const SegmentList& segment_list) const noexcept {
                        const auto& segment = segment_list[item];
                        return reverse ? segment.second() : segment.first();
                    }

                    osmium::Location location(const SegmentList& segment_list, const osmium::Location& default_location) const noexcept {
                        if (item == invalid_item) {
                            return default_location;
                        }
                        return location(segment_list);
                    }

                }; // struct slocation

                // Configuration settings for this Assembler
                const AssemblerConfig& m_config;

                // List of segments (connection between two nodes)
                SegmentList m_segment_list;

                // The rings we are building from the segments
                std::list<ProtoRing> m_rings;

                // All node locations
                std::vector<slocation> m_locations;

                // All locations where more than two segments start/end
                std::vector<Location> m_split_locations;

                // Statistics
                area_stats m_stats;

                // The number of members the multipolygon relation has
                std::size_t m_num_members = 0;

                template <typename TBuilder>
                static void build_ring_from_proto_ring(osmium::builder::AreaBuilder& builder, const ProtoRing& ring) {
                    TBuilder ring_builder{builder};
                    ring_builder.add_node_ref(ring.get_node_ref_start());
                    for (const auto& segment : ring.segments()) {
                        ring_builder.add_node_ref(segment->stop());
                    }
                }

                void check_inner_outer_roles() {
                    if (debug()) {
                        std::cerr << "    Checking inner/outer roles\n";
                    }

                    std::unordered_map<const osmium::Way*, const ProtoRing*> way_rings;
                    std::unordered_set<const osmium::Way*> ways_in_multiple_rings;

                    for (const ProtoRing& ring : m_rings) {
                        for (const auto& segment : ring.segments()) {
                            assert(segment->way());

                            if (!segment->role_empty() && (ring.is_outer() ? !segment->role_outer() : !segment->role_inner())) {
                                ++m_stats.wrong_role;
                                if (debug()) {
                                    std::cerr << "      Segment " << *segment << " from way " << segment->way()->id() << " has role '" << segment->role_name()
                                              << "', but should have role '" << (ring.is_outer() ? "outer" : "inner") << "'\n";
                                }
                                if (m_config.problem_reporter) {
                                    if (ring.is_outer()) {
                                        m_config.problem_reporter->report_role_should_be_outer(segment->way()->id(), segment->first().location(), segment->second().location());
                                    } else {
                                        m_config.problem_reporter->report_role_should_be_inner(segment->way()->id(), segment->first().location(), segment->second().location());
                                    }
                                }
                            }

                            auto& r = way_rings[segment->way()];
                            if (!r) {
                                r = &ring;
                            } else if (r != &ring) {
                                ways_in_multiple_rings.insert(segment->way());
                            }

                        }
                    }

                    for (const osmium::Way* way : ways_in_multiple_rings) {
                        ++m_stats.ways_in_multiple_rings;
                        if (debug()) {
                            std::cerr << "      Way " << way->id() << " is in multiple rings\n";
                        }
                        if (m_config.problem_reporter) {
                            m_config.problem_reporter->report_way_in_multiple_rings(*way);
                        }
                    }

                }

                NodeRefSegment* get_next_segment(const osmium::Location& location) {
                    auto it = std::lower_bound(m_locations.begin(), m_locations.end(), slocation{}, [this, &location](const slocation& lhs, const slocation& rhs) {
                        return lhs.location(m_segment_list, location) < rhs.location(m_segment_list, location);
                    });

                    assert(it != m_locations.end());
                    if (m_segment_list[it->item].is_done()) {
                        ++it;
                    }
                    assert(it != m_locations.end());

                    assert(!m_segment_list[it->item].is_done());
                    return &m_segment_list[it->item];
                }

                class rings_stack_element {

                    double m_y;
                    ProtoRing* m_ring_ptr;

                public:

                    rings_stack_element(double y, ProtoRing* ring_ptr) :
                        m_y(y),
                        m_ring_ptr(ring_ptr) {
                    }

                    double y() const noexcept {
                        return m_y;
                    }

                    const ProtoRing& ring() const noexcept {
                        return *m_ring_ptr;
                    }

                    ProtoRing* ring_ptr() noexcept {
                        return m_ring_ptr;
                    }

                    bool operator==(const rings_stack_element& rhs) const noexcept {
                        return m_ring_ptr == rhs.m_ring_ptr;
                    }

                    bool operator<(const rings_stack_element& rhs) const noexcept {
                        return m_y < rhs.m_y;
                    }

                }; // class rings_stack_element

                using rings_stack = std::vector<rings_stack_element>;

                static void remove_duplicates(rings_stack& outer_rings) {
                    while (true) {
                        const auto it = std::adjacent_find(outer_rings.begin(), outer_rings.end());
                        if (it == outer_rings.end()) {
                            return;
                        }
                        outer_rings.erase(it, std::next(it, 2));
                    }
                }

                ProtoRing* find_enclosing_ring(NodeRefSegment* segment) {
                    if (debug()) {
                        std::cerr << "    Looking for ring enclosing " << *segment << "\n";
                    }

                    const auto location = segment->first().location();
                    const auto end_location = segment->second().location();

                    while (segment->first().location() == location) {
                        if (segment == &m_segment_list.back()) {
                            break;
                        }
                        ++segment;
                    }

                    int nesting = 0;

                    rings_stack outer_rings;
                    while (segment >= &m_segment_list.front()) {
                        if (!segment->is_direction_done()) {
                            --segment;
                            continue;
                        }
                        if (debug()) {
                            std::cerr << "      Checking against " << *segment << "\n";
                        }
                        const osmium::Location& a = segment->first().location();
                        const osmium::Location& b = segment->second().location();

                        if (segment->first().location() == location) {
                            const int64_t ax = a.x();
                            const int64_t bx = b.x();
                            const int64_t lx = end_location.x();
                            const int64_t ay = a.y();
                            const int64_t by = b.y();
                            const int64_t ly = end_location.y();
                            const auto z = (bx - ax) * (ly - ay) - (by - ay) * (lx - ax);
                            if (debug()) {
                                std::cerr << "      Segment z=" << z << '\n';
                            }
                            if (z > 0) {
                                nesting += segment->is_reverse() ? -1 : 1;
                                if (debug()) {
                                    std::cerr << "        Segment is below (nesting=" << nesting << ")\n";
                                }
                                if (segment->ring()->is_outer()) {
                                    if (debug()) {
                                        std::cerr << "        Segment belongs to outer ring (y=" << a.y() << " ring=" << *segment->ring() << ")\n";
                                    }
                                    outer_rings.emplace_back(a.y(), segment->ring());
                                }
                            }
                        } else if (a.x() <= location.x() && location.x() < b.x()) {
                            if (debug()) {
                                std::cerr << "        Is in x range\n";
                            }

                            const int64_t ax = a.x();
                            const int64_t bx = b.x();
                            const int64_t lx = location.x();
                            const int64_t ay = a.y();
                            const int64_t by = b.y();
                            const int64_t ly = location.y();
                            const auto z = (bx - ax) * (ly - ay) - (by - ay) * (lx - ax);

                            if (z >= 0) {
                                nesting += segment->is_reverse() ? -1 : 1;
                                if (debug()) {
                                    std::cerr << "        Segment is below (nesting=" << nesting << ")\n";
                                }
                                if (segment->ring()->is_outer()) {
                                    const double y = static_cast<double>(ay) +
                                                     static_cast<double>((by - ay) * (lx - ax)) / static_cast<double>(bx - ax);
                                    if (debug()) {
                                        std::cerr << "        Segment belongs to outer ring (y=" << y << " ring=" << *segment->ring() << ")\n";
                                    }
                                    outer_rings.emplace_back(y, segment->ring());
                                }
                            }
                        }
                        --segment;
                    }

                    if (nesting % 2 == 0) {
                        if (debug()) {
                            std::cerr << "    Decided that this is an outer ring\n";
                        }
                        return nullptr;
                    }

                    if (debug()) {
                        std::cerr << "    Decided that this is an inner ring\n";
                    }
                    assert(!outer_rings.empty());

                    std::stable_sort(outer_rings.rbegin(), outer_rings.rend());
                    if (debug()) {
                        for (const auto& o : outer_rings) {
                            std::cerr << "        y=" << o.y() << " " << o.ring() << "\n";
                        }
                    }

                    remove_duplicates(outer_rings);
                    if (debug()) {
                        std::cerr << "      after remove duplicates:\n";
                        for (const auto& o : outer_rings) {
                            std::cerr << "        y=" << o.y() << " " << o.ring() << "\n";
                        }
                    }

                    assert(!outer_rings.empty());
                    return outer_rings.front().ring_ptr();
                }

                bool is_split_location(const osmium::Location& location) const noexcept {
                    return std::find(m_split_locations.cbegin(), m_split_locations.cend(), location) != m_split_locations.cend();
                }

                uint32_t add_new_ring(const slocation& node) {
                    NodeRefSegment* segment = &m_segment_list[node.item];
                    assert(!segment->is_done());

                    if (debug()) {
                        std::cerr << "  Starting new ring at location " << node.location(m_segment_list) << " with segment " << *segment << "\n";
                    }

                    if (node.reverse) {
                        segment->reverse();
                    }

                    ProtoRing* outer_ring = nullptr;

                    if (segment != &m_segment_list.front()) {
                        outer_ring = find_enclosing_ring(segment);
                    }
                    segment->mark_direction_done();

                    m_rings.emplace_back(segment);
                    ProtoRing* ring = &m_rings.back();
                    if (outer_ring) {
                        if (debug()) {
                            std::cerr << "    This is an inner ring. Outer ring is " << *outer_ring << "\n";
                        }
                        outer_ring->add_inner_ring(ring);
                        ring->set_outer_ring(outer_ring);
                    } else if (debug()) {
                        std::cerr << "    This is an outer ring\n";
                    }

                    const osmium::Location& first_location = node.location(m_segment_list);
                    osmium::Location last_location = segment->stop().location();

                    uint32_t nodes = 1;
                    while (first_location != last_location) {
                        ++nodes;
                        NodeRefSegment* next_segment = get_next_segment(last_location);
                        next_segment->mark_direction_done();
                        if (next_segment->start().location() != last_location) {
                            next_segment->reverse();
                        }
                        ring->add_segment_back(next_segment);
                        if (debug()) {
                            std::cerr << "    Next segment is " << *next_segment << "\n";
                        }
                        last_location = next_segment->stop().location();
                    }

                    ring->fix_direction();

                    if (debug()) {
                        std::cerr << "    Completed ring: " << *ring << "\n";
                    }

                    return nodes;
                }

                uint32_t add_new_ring_complex(const slocation& node) {
                    NodeRefSegment* segment = &m_segment_list[node.item];
                    assert(!segment->is_done());

                    if (debug()) {
                        std::cerr << "  Starting new ring at location " << node.location(m_segment_list) << " with segment " << *segment << "\n";
                    }

                    if (node.reverse) {
                        segment->reverse();
                    }

                    m_rings.emplace_back(segment);
                    ProtoRing* ring = &m_rings.back();

                    const osmium::Location& first_location = node.location(m_segment_list);
                    osmium::Location last_location = segment->stop().location();

                    uint32_t nodes = 1;
                    while (first_location != last_location && !is_split_location(last_location)) {
                        ++nodes;
                        NodeRefSegment* next_segment = get_next_segment(last_location);
                        if (next_segment->start().location() != last_location) {
                            next_segment->reverse();
                        }
                        ring->add_segment_back(next_segment);
                        if (debug()) {
                            std::cerr << "    Next segment is " << *next_segment << "\n";
                        }
                        last_location = next_segment->stop().location();
                    }

                    if (debug()) {
                        if (first_location == last_location) {
                            std::cerr << "    Completed ring: " << *ring << "\n";
                        } else {
                            std::cerr << "    Completed partial ring: " << *ring << "\n";
                        }
                    }

                    return nodes;
                }

                void create_locations_list() {
                    m_locations.reserve(m_segment_list.size() * 2);

                    // static_cast is okay here: The 32bit limit is way past
                    // anything that makes sense here and even if there are
                    // 2^32 segments here, it would simply not go through
                    // all of them not building the multipolygon correctly.
                    assert(m_segment_list.size() < std::numeric_limits<uint32_t>::max());
                    for (uint32_t n = 0; n < static_cast<uint32_t>(m_segment_list.size()); ++n) {
                        m_locations.emplace_back(n, false);
                        m_locations.emplace_back(n, true);
                    }

                    std::stable_sort(m_locations.begin(), m_locations.end(), [this](const slocation& lhs, const slocation& rhs) {
                        return lhs.location(m_segment_list) < rhs.location(m_segment_list);
                    });
                }

                void find_inner_outer_complex(ProtoRing* ring) {
                    ProtoRing* outer_ring = find_enclosing_ring(ring->min_segment());
                    if (outer_ring) {
                        outer_ring->add_inner_ring(ring);
                        ring->set_outer_ring(outer_ring);
                    }
                    ring->fix_direction();
                    ring->mark_direction_done();
                }

                void find_inner_outer_complex() {
                    if (debug()) {
                        std::cerr << "  Finding inner/outer rings\n";
                    }
                    std::vector<ProtoRing*> rings;
                    rings.reserve(m_rings.size());
                    for (auto& ring : m_rings) {
                        if (ring.closed()) {
                            rings.push_back(&ring);
                        }
                    }

                    if (rings.empty()) {
                        return;
                    }

                    std::stable_sort(rings.begin(), rings.end(), [](ProtoRing* a, ProtoRing* b) {
                        return a->min_segment() < b->min_segment();
                    });

                    rings.front()->fix_direction();
                    rings.front()->mark_direction_done();
                    if (debug()) {
                        std::cerr << "    First ring is outer: " << *rings.front() << "\n";
                    }
                    for (auto it = std::next(rings.begin()); it != rings.end(); ++it) {
                        if (debug()) {
                            std::cerr << "    Checking (at min segment " << *((*it)->min_segment()) << ") ring " << **it << "\n";
                        }
                        find_inner_outer_complex(*it);
                        if (debug()) {
                            std::cerr << "    Ring is " << ((*it)->is_outer() ? "OUTER: " : "INNER: ") << **it << "\n";
                        }
                    }
                }

                /**
                 * Finds all locations where more than two segments meet. If there
                 * are any open rings found along the way, they are reported
                 * and the function returns false.
                 */
                bool find_split_locations() {
                    osmium::Location previous_location;
                    for (auto it = m_locations.cbegin(); it != m_locations.cend(); ++it) {
                        const osmium::NodeRef& nr = it->node_ref(m_segment_list);
                        const osmium::Location& loc = nr.location();
                        if (std::next(it) == m_locations.cend() || loc != std::next(it)->location(m_segment_list)) {
                            if (debug()) {
                                std::cerr << "  Found open ring at " << nr << "\n";
                            }
                            if (m_config.problem_reporter) {
                                const auto& segment = m_segment_list[it->item];
                                m_config.problem_reporter->report_ring_not_closed(nr, segment.way());
                            }
                            ++m_stats.open_rings;
                        } else {
                            if (loc == previous_location && (m_split_locations.empty() || m_split_locations.back() != previous_location)) {
                                m_split_locations.push_back(previous_location);
                            }
                            ++it;
                            if (it == m_locations.end()) {
                                break;
                            }
                        }
                        previous_location = loc;
                    }
                    return m_stats.open_rings == 0;
                }

                void create_rings_simple_case() {
                    auto count_remaining = m_segment_list.size();
                    for (slocation& sl : m_locations) {
                        const NodeRefSegment& segment = m_segment_list[sl.item];
                        if (!segment.is_done()) {
                            count_remaining -= add_new_ring(sl);
                            if (count_remaining == 0) {
                                return;
                            }
                        }
                    }
                }

                std::vector<location_to_ring_map> create_location_to_ring_map(open_ring_its_type& open_ring_its) const {
                    std::vector<location_to_ring_map> xrings;
                    xrings.reserve(open_ring_its.size() * 2);

                    for (auto it = open_ring_its.begin(); it != open_ring_its.end(); ++it) {
                        if (debug()) {
                            std::cerr << "      " << **it << '\n';
                        }
                        xrings.emplace_back((*it)->get_node_ref_start().location(), it, true);
                        xrings.emplace_back((*it)->get_node_ref_stop().location(), it, false);
                    }

                    std::stable_sort(xrings.begin(), xrings.end());

                    return xrings;
                }

                void merge_two_rings(open_ring_its_type& open_ring_its, const location_to_ring_map& m1, const location_to_ring_map& m2) {
                    const auto r1 = *m1.ring_it;
                    const auto r2 = *m2.ring_it;

                    if (r1->get_node_ref_stop().location() == r2->get_node_ref_start().location()) {
                        r1->join_forward(*r2);
                    } else if (r1->get_node_ref_stop().location() == r2->get_node_ref_stop().location()) {
                        r1->join_backward(*r2);
                    } else if (r1->get_node_ref_start().location() == r2->get_node_ref_start().location()) {
                        r1->reverse();
                        r1->join_forward(*r2);
                    } else if (r1->get_node_ref_start().location() == r2->get_node_ref_stop().location()) {
                        r1->reverse();
                        r1->join_backward(*r2);
                    } else {
                        assert(false);
                    }

                    open_ring_its.erase(std::find(open_ring_its.begin(), open_ring_its.end(), r2));
                    m_rings.erase(r2);

                    if (r1->closed()) {
                        open_ring_its.erase(std::find(open_ring_its.begin(), open_ring_its.end(), r1));
                    }
                }

                bool try_to_merge(open_ring_its_type& open_ring_its) {
                    if (open_ring_its.empty()) {
                        return false;
                    }

                    if (debug()) {
                        std::cerr << "    Trying to merge " << open_ring_its.size() << " open rings (try_to_merge)\n";
                    }

                    std::vector<location_to_ring_map> xrings = create_location_to_ring_map(open_ring_its);

                    auto it = xrings.cbegin();
                    while (it != xrings.cend()) {
                        it = std::adjacent_find(it, xrings.cend());
                        if (it == xrings.cend()) {
                            return false;
                        }
                        auto after = std::next(it, 2);
                        if (after == xrings.cend() || after->location != it->location) {
                            if (debug()) {
                                std::cerr << "      Merging two rings\n";
                            }
                            merge_two_rings(open_ring_its, *it, *std::next(it));
                            return true;
                        }
                        while (it != xrings.cend() && it->location == after->location) {
                            ++it;
                        }
                    }

                    return false;
                }

                bool there_are_open_rings() const noexcept {
                    return std::any_of(m_rings.cbegin(), m_rings.cend(), [](const ProtoRing& ring) {
                        return !ring.closed();
                    });
                }

                struct candidate {
                    int64_t sum;
                    std::vector<std::pair<location_to_ring_map, bool>> rings{};
                    osmium::Location start_location;
                    osmium::Location stop_location;

                    explicit candidate(location_to_ring_map& ring, bool reverse) :
                        sum(ring.ring().sum()),
                        start_location(ring.ring().get_node_ref_start().location()),
                        stop_location(ring.ring().get_node_ref_stop().location()) {
                        rings.emplace_back(ring, reverse);
                    }

                    bool closed() const noexcept {
                        return start_location == stop_location;
                    }

                };

                struct exceeded_max_depth : public std::exception {};

                using location_set = std::vector<osmium::Location>;

                void find_candidates(std::vector<candidate>& candidates, location_set& loc_done, const std::vector<location_to_ring_map>& xrings, const candidate& cand, unsigned depth = 0) {
                    if (depth > max_depth) {
                        throw exceeded_max_depth{};
                    }

                    if (debug()) {
                        std::cerr << "      find_candidates sum=" << cand.sum << " start=" << cand.start_location << " stop=" << cand.stop_location << "\n";
                        for (const auto& ring : cand.rings) {
                            std::cerr << "        " << ring.first.ring() << (ring.second ? " reverse" : "") << "\n";
                        }
                    }

                    const auto connections = make_range(std::equal_range(xrings.cbegin(),
                                                                         xrings.cend(),
                                                                         location_to_ring_map{cand.stop_location}));

                    assert(connections.begin() != connections.end());

                    assert(!cand.rings.empty());
                    const ProtoRing* ring_leading_here = &cand.rings.back().first.ring();
                    for (const location_to_ring_map& m : connections) {
                        const ProtoRing& ring = m.ring();

                        if (&ring != ring_leading_here) {
                            if (debug()) {
                                std::cerr << "        next possible connection: " << ring << (m.start ? "" : " reverse") << "\n";
                            }

                            candidate c = cand;
                            if (m.start) {
                                c.rings.emplace_back(m, false);
                                c.stop_location = ring.get_node_ref_stop().location();
                                c.sum += ring.sum();
                            } else {
                                c.rings.emplace_back(m, true);
                                c.stop_location = ring.get_node_ref_start().location();
                                c.sum -= ring.sum();
                            }
                            if (c.closed()) {
                                if (debug()) {
                                    std::cerr << "          found candidate\n";
                                }

                                if (candidates.empty()) {
                                    candidates.push_back(c);
                                } else if (candidates.size() == 1) {
                                    // add new candidate to vector, keep sorted
                                    if (std::abs(c.sum) < std::abs(candidates.front().sum)) {
                                        candidates.insert(candidates.begin(), c);
                                    } else {
                                        candidates.push_back(c);
                                    }
                                } else {
                                    // add new candidate if it has either smallest or largest area
                                    if (std::abs(c.sum) < std::abs(candidates.front().sum)) {
                                        candidates.front() = c;
                                    } else if (std::abs(c.sum) > std::abs(candidates.back().sum)) {
                                        candidates.back() = c;
                                    }
                                }
                            } else if (std::find(loc_done.cbegin(), loc_done.cend(), c.stop_location) == loc_done.cend()) {
                                if (debug()) {
                                    std::cerr << "          recurse... (depth=" << depth << " candidates.size=" << candidates.size() << " loc_done.size=" << loc_done.size() << ")\n";
                                }
                                loc_done.push_back(c.stop_location);
                                find_candidates(candidates, loc_done, xrings, c, depth + 1);
                                assert(!loc_done.empty() && loc_done.back() == c.stop_location);
                                loc_done.pop_back();
                                if (debug()) {
                                    std::cerr << "          ...back\n";
                                }
                            } else if (debug()) {
                                std::cerr << "          loop found\n";
                            }
                        }
                    }
                }

                /**
                 * If there are multiple open rings and multiple ways to join them,
                 * this function is called. It will take the first open ring and
                 * try recursively all ways of closing it. Of all the candidates
                 * the one with the smallest area is chosen and closed. If it
                 * can't close this ring, an error is reported and the function
                 * returns false.
                 */
                bool join_connected_rings(open_ring_its_type& open_ring_its) {
                    assert(!open_ring_its.empty());

                    if (debug()) {
                        std::cerr << "    Trying to merge " << open_ring_its.size() << " open rings (join_connected_rings)\n";
                    }

                    std::vector<location_to_ring_map> xrings = create_location_to_ring_map(open_ring_its);

                    const auto ring_min = std::min_element(xrings.begin(), xrings.end(), [](const location_to_ring_map& lhs, const location_to_ring_map& rhs) {
                        return lhs.ring().min_segment() < rhs.ring().min_segment();
                    });

                    find_inner_outer_complex();
                    ProtoRing* outer_ring = find_enclosing_ring(ring_min->ring().min_segment());
                    bool ring_min_is_outer = !outer_ring;
                    if (debug()) {
                        std::cerr << "  Open ring is " << (ring_min_is_outer ? "outer" : "inner") << " ring\n";
                    }
                    for (auto& ring : m_rings) {
                        ring.reset();
                    }

                    const candidate cand{*ring_min, false};

                    // Locations we have visited while finding candidates, used
                    // to detect loops.
                    location_set loc_done;

                    loc_done.push_back(cand.stop_location);

                    std::vector<candidate> candidates;
                    try {
                        find_candidates(candidates, loc_done, xrings, cand);
                    } catch (const exceeded_max_depth&) {
                        if (m_config.debug_level > 0) {
                            std::cerr << "    Exceeded max depth (" << static_cast<unsigned>(max_depth) << ")\n";
                        }
                        return false;
                    }

                    if (candidates.empty()) {
                        if (debug()) {
                            std::cerr << "    Found no candidates\n";
                        }
                        if (!open_ring_its.empty()) {
                            ++m_stats.open_rings;
                            if (m_config.problem_reporter) {
                                for (auto& it : open_ring_its) {
                                    m_config.problem_reporter->report_ring_not_closed(it->get_node_ref_start(), nullptr);
                                    m_config.problem_reporter->report_ring_not_closed(it->get_node_ref_stop(), nullptr);
                                }
                            }
                        }
                        return false;
                    }

                    if (debug()) {
                        std::cerr << "    Found candidates:\n";
                        for (const auto& c : candidates) {
                            std::cerr << "      sum=" << c.sum << "\n";
                            for (const auto& ring : c.rings) {
                                std::cerr << "        " << ring.first.ring() << (ring.second ? " reverse" : "") << "\n";
                            }
                        }
                    }

                    // Find the candidate with the smallest/largest area
                    const auto chosen_cand = ring_min_is_outer ? candidates.front() : candidates.back();

                    if (debug()) {
                        std::cerr << "    Decided on: sum=" << chosen_cand.sum << "\n";
                        for (const auto& ring : chosen_cand.rings) {
                            std::cerr << "        " << ring.first.ring() << (ring.second ? " reverse" : "") << "\n";
                        }
                    }

                    // Join all (open) rings in the candidate to get one closed ring.
                    assert(chosen_cand.rings.size() > 1);
                    const auto& first_ring = chosen_cand.rings.front().first;
                    const ProtoRing& remaining_ring = first_ring.ring();
                    for (auto it = std::next(chosen_cand.rings.begin()); it != chosen_cand.rings.end(); ++it) {
                        merge_two_rings(open_ring_its, first_ring, it->first);
                    }

                    if (debug()) {
                        std::cerr << "    Merged to " << remaining_ring << '\n';
                    }

                    return true;
                }

                bool create_rings_complex_case() {
                    // First create all the (partial) rings starting at the split locations
                    auto count_remaining = m_segment_list.size();
                    for (const osmium::Location& location : m_split_locations) {
                        const auto locs = make_range(std::equal_range(m_locations.begin(),
                                                                      m_locations.end(),
                                                                      slocation{},
                                                                      [this, &location](const slocation& lhs, const slocation& rhs) {
                                                                          return lhs.location(m_segment_list, location) < rhs.location(m_segment_list, location);
                                                                      }));
                        for (auto& loc : locs) {
                            if (!m_segment_list[loc.item].is_done()) {
                                count_remaining -= add_new_ring_complex(loc);
                                if (count_remaining == 0) {
                                    break;
                                }
                            }
                        }
                    }

                    // Now find all the rest of the rings (ie not starting at split locations)
                    if (count_remaining > 0) {
                        for (slocation& sl : m_locations) {
                            const NodeRefSegment& segment = m_segment_list[sl.item];
                            if (!segment.is_done()) {
                                count_remaining -= add_new_ring_complex(sl);
                                if (count_remaining == 0) {
                                    break;
                                }
                            }
                        }
                    }

                    // Now all segments are in exactly one (partial) ring.

                    // If there are open rings, try to join them to create closed
                    // rings.
                    if (there_are_open_rings()) {
                        ++m_stats.area_really_complex_case;

                        open_ring_its_type open_ring_its;
                        for (auto it = m_rings.begin(); it != m_rings.end(); ++it) {
                            if (!it->closed()) {
                                open_ring_its.push_back(it);
                            }
                        }

                        while (!open_ring_its.empty()) {
                            if (debug()) {
                                std::cerr << "  There are " << open_ring_its.size() << " open rings\n";
                            }
                            while (try_to_merge(open_ring_its)) {
                                // intentionally left blank
                            }

                            if (!open_ring_its.empty()) {
                                if (debug()) {
                                    std::cerr << "  After joining obvious cases there are still " << open_ring_its.size() << " open rings\n";
                                }
                                if (!join_connected_rings(open_ring_its)) {
                                    return false;
                                }
                            }
                        }

                        if (debug()) {
                            std::cerr << "  Joined all open rings\n";
                        }
                    }

                    // Now all rings are complete.

                    find_inner_outer_complex();

                    return true;
                }

#ifdef OSMIUM_WITH_TIMER
                static bool print_header() {
                    std::cout << "nodes outer_rings inner_rings sort dupl intersection locations split simple_case complex_case roles_check\n";
                    return true;
                }

                static bool init_header() {
                    static bool printed_print_header = print_header();
                    return printed_print_header;
                }
#endif

            protected:

                const std::list<ProtoRing>& rings() const noexcept {
                    return m_rings;
                }

                void set_num_members(std::size_t size) noexcept {
                    m_num_members = size;
                }

                SegmentList& segment_list() noexcept {
                    return m_segment_list;
                }

                /**
                 * Append each outer ring together with its inner rings to the
                 * area in the buffer.
                 */
                void add_rings_to_area(osmium::builder::AreaBuilder& builder) const {
                    for (const ProtoRing& ring : m_rings) {
                        if (ring.is_outer()) {
                            build_ring_from_proto_ring<osmium::builder::OuterRingBuilder>(builder, ring);
                            for (const ProtoRing* inner : ring.inner_rings()) {
                                build_ring_from_proto_ring<osmium::builder::InnerRingBuilder>(builder, *inner);
                            }
                        }
                    }
                }

                /**
                 * Create rings from segments.
                 */
                bool create_rings() {
                    m_stats.nodes += m_segment_list.size();

                    // Sort the list of segments (from left to right and bottom
                    // to top).
                    osmium::Timer timer_sort;
                    m_segment_list.sort();
                    timer_sort.stop();

                    // Remove duplicate segments. Removal is in pairs, so if there
                    // are two identical segments, they will both be removed. If
                    // there are three, two will be removed and one remains.
                    osmium::Timer timer_dupl;
                    m_segment_list.erase_duplicate_segments(m_config.problem_reporter, m_stats.duplicate_segments, m_stats.overlapping_segments);
                    timer_dupl.stop();

                    // If there are no segments left at this point, this isn't
                    // a valid area.
                    if (m_segment_list.empty()) {
                        if (debug()) {
                            std::cerr << "  No segments left\n";
                        }
                        return false;
                    }

                    if (m_config.debug_level >= 3) {
                        std::cerr << "Sorted de-duplicated segment list:\n";
                        for (const auto& s : m_segment_list) {
                            std::cerr << "  " << s << "\n";
                        }
                    }

                    // Now we look for segments crossing each other. If there are
                    // any, the multipolygon is invalid.
                    // In the future this could be improved by trying to fix those
                    // cases.
                    osmium::Timer timer_intersection;
                    m_stats.intersections = m_segment_list.find_intersections(m_config.problem_reporter);
                    timer_intersection.stop();

                    if (m_stats.intersections) {
                        return false;
                    }

                    // This creates an ordered list of locations of both endpoints
                    // of all segments with pointers back to the segments. We will
                    // use this list later to quickly find which segment(s) fits
                    // onto a known segment.
                    osmium::Timer timer_locations_list;
                    create_locations_list();
                    timer_locations_list.stop();

                    // Find all locations where more than two segments start or
                    // end. We call those "split" locations. If there are any
                    // "spike" segments found while doing this, we know the area
                    // geometry isn't valid and return.
                    osmium::Timer timer_split;
                    if (!find_split_locations()) {
                        return false;
                    }
                    timer_split.stop();

                    // Now report all split locations to the problem reporter.
                    m_stats.touching_rings += m_split_locations.size();
                    if (!m_split_locations.empty()) {
                        if (debug()) {
                            std::cerr << "  Found split locations:\n";
                        }
                        for (const auto& location : m_split_locations) {
                            if (m_config.problem_reporter) {
                                auto it = std::lower_bound(m_locations.cbegin(), m_locations.cend(), slocation{}, [this, &location](const slocation& lhs, const slocation& rhs) {
                                    return lhs.location(m_segment_list, location) < rhs.location(m_segment_list, location);
                                });
                                assert(it != m_locations.cend());
                                const osmium::object_id_type id = it->node_ref(m_segment_list).ref();
                                m_config.problem_reporter->report_touching_ring(id, location);
                            }
                            if (debug()) {
                                std::cerr << "    " << location << "\n";
                            }
                        }
                    }

                    // From here on we use two different algorithms depending on
                    // whether there were any split locations or not. If there
                    // are no splits, we use the faster "simple algorithm", if
                    // there are, we use the slower "complex algorithm".
                    osmium::Timer timer;
                    if (m_split_locations.empty()) {
                        if (debug()) {
                            std::cerr << "  No split locations -> using simple algorithm\n";
                        }
                        ++m_stats.area_simple_case;

                        timer.start();
                        create_rings_simple_case();
                        timer.stop();
                    } else if (m_split_locations.size() > max_split_locations) {
                        if (m_config.debug_level > 0) {
                            std::cerr << "  Ignoring polygon with "
                                      << m_split_locations.size()
                                      << " split locations (>"
                                      << max_split_locations
                                      << ")\n";
                        }
                        return false;
                    } else {
                        if (m_config.debug_level > 0) {
                            std::cerr << "  Found "
                                      << m_split_locations.size()
                                      << " split locations -> using complex algorithm\n";
                        }
                        ++m_stats.area_touching_rings_case;

                        timer.start();
                        if (!create_rings_complex_case()) {
                            return false;
                        }
                        timer.stop();
                    }

                    // If the assembler was so configured, now check whether the
                    // member roles are correctly tagged.
                    if (m_config.check_roles && m_stats.from_relations) {
                        osmium::Timer timer_roles;
                        check_inner_outer_roles();
                        timer_roles.stop();
                    }

                    m_stats.outer_rings = std::count_if(m_rings.cbegin(), m_rings.cend(), [](const ProtoRing& ring) {
                        return ring.is_outer();
                    });
                    m_stats.inner_rings = m_rings.size() - m_stats.outer_rings;

#ifdef OSMIUM_WITH_TIMER
                    std::cout << m_stats.nodes << ' ' << m_stats.outer_rings << ' ' << m_stats.inner_rings <<
                                                ' ' << timer_sort.elapsed_microseconds() <<
                                                ' ' << timer_dupl.elapsed_microseconds() <<
                                                ' ' << timer_intersection.elapsed_microseconds() <<
                                                ' ' << timer_locations_list.elapsed_microseconds() <<
                                                ' ' << timer_split.elapsed_microseconds();

                    if (m_split_locations.empty()) {
                        std::cout << ' ' << timer.elapsed_microseconds() << " 0";
                    } else {
                        std::cout << " 0" << ' ' << timer.elapsed_microseconds();
                    }

                    std::cout <<
# ifdef OSMIUM_AREA_CHECK_INNER_OUTER_ROLES
                                ' ' << timer_roles.elapsed_microseconds() <<
# else
                                " 0" <<
# endif
                                '\n';
#endif

                    return true;
                }

            public:

                using config_type = osmium::area::AssemblerConfig;

                explicit BasicAssembler(const config_type& config) :
                    m_config(config),
                    m_segment_list(config.debug_level > 1) {
#ifdef OSMIUM_WITH_TIMER
                    init_header();
#endif
                }

                const AssemblerConfig& config() const noexcept {
                    return m_config;
                }

                bool debug() const noexcept {
                    return m_config.debug_level > 1;
                }

                /**
                 * Get statistics from assembler. Call this after running the
                 * assembler to get statistics and data about errors.
                 */
                const osmium::area::area_stats& stats() const noexcept {
                    return m_stats;
                }

                osmium::area::area_stats& stats() noexcept {
                    return m_stats;
                }

            }; // class BasicAssembler

        } // namespace detail

    } // namespace area

} // namespace osmium

#endif // OSMIUM_AREA_DETAIL_BASIC_ASSEMBLER_HPP