26001

Committed 22 May 2026 09:25AM UTC coverage: 93.203% (+0.003%) from 93.2%

Build # 26001

Build Type

push

circleci

Committed by

web-flow

Commit Message

Merge pull request #1459 from tinko92/refactor/reduce-misc-boost-dependencies

Refactor/reduce misc boost dependencies

Coverage Stats

33130 of 35546 relevant lines covered (93.2%)

1488955.17 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

98.57

include/boost/geometry/algorithms/detail/is_valid/complement_graph.hpp

// Boost.Geometry (aka GGL, Generic Geometry Library)

// Copyright (c) 2014-2023, Oracle and/or its affiliates.

// Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle

// Licensed under the Boost Software License version 1.0.
// http://www.boost.org/users/license.html

#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_COMPLEMENT_GRAPH_HPP
#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_COMPLEMENT_GRAPH_HPP

#include <cstddef>

#include <memory>
#include <set>
#include <stack>
#include <utility>
#include <vector>

#include <boost/geometry/algorithms/detail/signed_size_type.hpp>
#include <boost/geometry/core/assert.hpp>
#include <boost/geometry/policies/compare.hpp>


namespace boost { namespace geometry
{

namespace detail { namespace is_valid
{


template <typename TurnPoint, typename Strategy>
class complement_graph_vertex
{
public:
    complement_graph_vertex(std::size_t id)
        : m_id(id)
        , m_turn_point(NULL)
    {}

    complement_graph_vertex(TurnPoint const* turn_point,
                            std::size_t expected_id)
        : m_id(expected_id)
        , m_turn_point(turn_point)
    {}

    inline std::size_t id() const { return m_id; }

    inline bool operator<(complement_graph_vertex const& other) const
    {
        if ( m_turn_point != NULL && other.m_turn_point != NULL )
        {
            return geometry::less
                <
                    TurnPoint, -1, Strategy
                >()(*m_turn_point, *other.m_turn_point);
        }
        if ( m_turn_point == NULL && other.m_turn_point == NULL )
        {
            return m_id < other.m_id;
        }
        return m_turn_point == NULL;
    }

private:
    // the value of m_turn_point determines the type of the vertex
    // non-NULL: vertex corresponds to an IP
    // NULL    : vertex corresponds to a hole or outer space, and the id
    //           is the ring id of the corresponding ring of the polygon
    std::size_t m_id;
    TurnPoint const* m_turn_point;
};




template <typename TurnPoint, typename Strategy>
class complement_graph
{
private:
    typedef complement_graph_vertex<TurnPoint, Strategy> vertex;
    typedef std::set<vertex> vertex_container;

public:
    typedef typename vertex_container::const_iterator vertex_handle;

private:
    struct vertex_handle_less
    {
        inline bool operator()(vertex_handle v1, vertex_handle v2) const
        {
            return v1->id() < v2->id();
        }
    };

    typedef std::set<vertex_handle, vertex_handle_less> neighbor_container;

    class has_cycles_dfs_data
    {
    public:
        has_cycles_dfs_data(std::size_t num_nodes)
            : m_visited(num_nodes, false)
            , m_parent_id(num_nodes, -1)
        {}

        inline signed_size_type parent_id(vertex_handle v) const
        {
            return m_parent_id[v->id()];
        }

        inline void set_parent_id(vertex_handle v, signed_size_type id)
        {
            m_parent_id[v->id()] = id;
        }

        inline bool visited(vertex_handle v) const
        {
            return m_visited[v->id()];
        }

        inline void set_visited(vertex_handle v, bool value)
        {
            m_visited[v->id()] = value;
        }
    private:
        std::vector<bool> m_visited;
        std::vector<signed_size_type> m_parent_id;
    };


    inline bool has_cycles(vertex_handle start_vertex,
                           has_cycles_dfs_data& data) const
    {
        std::stack<vertex_handle> stack;
        stack.push(start_vertex);

        while ( !stack.empty() )
        {
            vertex_handle v = stack.top();
            stack.pop();

            data.set_visited(v, true);
            for (typename neighbor_container::const_iterator nit
                     = m_neighbors[v->id()].begin();
                 nit != m_neighbors[v->id()].end(); ++nit)
            {
                if ( static_cast<signed_size_type>((*nit)->id()) != data.parent_id(v) )
                {
                    if ( data.visited(*nit) )
                    {
                        return true;
                    }
                    else
                    {
                        data.set_parent_id(*nit, static_cast<signed_size_type>(v->id()));
                        stack.push(*nit);
                    }
                }
            }
        }
        return false;
    }

public:
    // num_rings: total number of rings, including the exterior ring
    complement_graph(std::size_t num_rings)
        : m_num_rings(num_rings)
        , m_num_turns(0)
        , m_vertices()
        , m_neighbors(num_rings)
    {}

    // inserts a ring vertex in the graph and returns its handle
    // ring id's are zero-based (so the first interior ring has id 1)
    inline vertex_handle add_vertex(signed_size_type id)
    {
        return m_vertices.insert(vertex(static_cast<std::size_t>(id))).first;
    }

    // inserts an IP in the graph and returns its id
    inline vertex_handle add_vertex(TurnPoint const& turn_point)
    {
        std::pair<vertex_handle, bool> res
            = m_vertices.insert(vertex(std::addressof(turn_point),
                                       m_num_rings + m_num_turns)
                                );

        if ( res.second )
        {
            // a new element is inserted
            m_neighbors.push_back(neighbor_container());
            ++m_num_turns;
        }
        return res.first;
    }

    inline void add_edge(vertex_handle v1, vertex_handle v2)
    {
        BOOST_GEOMETRY_ASSERT( v1 != m_vertices.end() );
        BOOST_GEOMETRY_ASSERT( v2 != m_vertices.end() );
        m_neighbors[v1->id()].insert(v2);
        m_neighbors[v2->id()].insert(v1);
    }

    inline bool has_cycles() const
    {
        // initialize all vertices as non-visited and with no parent set
        // this is done by the constructor of has_cycles_dfs_data
        has_cycles_dfs_data data(m_num_rings + m_num_turns);

        // for each non-visited vertex, start a DFS from that vertex
        for (vertex_handle it = m_vertices.begin();
             it != m_vertices.end(); ++it)
        {
            if ( !data.visited(it) && has_cycles(it, data) )
            {
                return true;
            }
        }
        return false;
    }

#ifdef BOOST_GEOMETRY_TEST_DEBUG
    template <typename OutputStream>
    friend inline
    void debug_print_complement_graph(OutputStream&,
                                      complement_graph<TurnPoint, Strategy> const&);
#endif // BOOST_GEOMETRY_TEST_DEBUG

private:
    std::size_t m_num_rings, m_num_turns;
    vertex_container m_vertices;
    std::vector<neighbor_container> m_neighbors;
};


}} // namespace detail::is_valid

}} // namespace boost::geometry

#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_COMPLEMENT_GRAPH_HPP

1	// Boost.Geometry (aka GGL, Generic Geometry Library)
2
3	// Copyright (c) 2014-2023, Oracle and/or its affiliates.
4
5	// Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
6	// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
7	// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
8
9	// Licensed under the Boost Software License version 1.0.
10	// http://www.boost.org/users/license.html
11
12	#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_COMPLEMENT_GRAPH_HPP
13	#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_COMPLEMENT_GRAPH_HPP
14
15	#include <cstddef>
16
17	#include <memory>
18	#include <set>
19	#include <stack>
20	#include <utility>
21	#include <vector>
22
23	#include <boost/geometry/algorithms/detail/signed_size_type.hpp>
24	#include <boost/geometry/core/assert.hpp>
25	#include <boost/geometry/policies/compare.hpp>
26
27
28	namespace boost { namespace geometry
29	{
30
31	namespace detail { namespace is_valid
32	{
33
34
35	template <typename TurnPoint, typename Strategy>
36	class complement_graph_vertex
37	{
38	public:
39	complement_graph_vertex(std::size_t id)	3,608✔
40	: m_id(id)
41	, m_turn_point(NULL)	3,608✔
42	{}	3,608✔
43
44	complement_graph_vertex(TurnPoint const* turn_point,	1,804✔
45	std::size_t expected_id)
46	: m_id(expected_id)
47	, m_turn_point(turn_point)	1,804✔
48	{}	1,804✔
49
50	inline std::size_t id() const { return m_id; }	67,632✔
51
52	inline bool operator<(complement_graph_vertex const& other) const	19,137✔
53	{
54	if ( m_turn_point != NULL && other.m_turn_point != NULL )	19,137✔
55	{
56	return geometry::less
57	<
58	TurnPoint, -1, Strategy
59	>()(m_turn_point, other.m_turn_point);	3,331✔
60	}
61	if ( m_turn_point == NULL && other.m_turn_point == NULL )	15,806✔
62	{
63	return m_id < other.m_id;	9,967✔
64	}
65	return m_turn_point == NULL;	5,839✔
66	}
67
68	private:
69	// the value of m_turn_point determines the type of the vertex
70	// non-NULL: vertex corresponds to an IP
71	// NULL : vertex corresponds to a hole or outer space, and the id
72	// is the ring id of the corresponding ring of the polygon
73	std::size_t m_id;
74	TurnPoint const* m_turn_point;
75	};
76
77
78
79
80	template <typename TurnPoint, typename Strategy>
81	class complement_graph
82	{
83	private:
84	typedef complement_graph_vertex<TurnPoint, Strategy> vertex;
85	typedef std::set<vertex> vertex_container;
86
87	public:
88	typedef typename vertex_container::const_iterator vertex_handle;
89
90	private:
91	struct vertex_handle_less
92	{
93	inline bool operator()(vertex_handle v1, vertex_handle v2) const	10,412✔
94	{
95	return v1->id() < v2->id();	10,412✔
96	}
97	};
98
99	typedef std::set<vertex_handle, vertex_handle_less> neighbor_container;
100
101	class has_cycles_dfs_data
102	{
103	public:
104	has_cycles_dfs_data(std::size_t num_nodes)	13,565✔
105	: m_visited(num_nodes, false)	×
106	, m_parent_id(num_nodes, -1)	13,565✔
107	{}	13,565✔
108
109	inline signed_size_type parent_id(vertex_handle v) const	5,696✔
110	{
111	return m_parent_id[v->id()];	5,696✔
112	}
113
114	inline void set_parent_id(vertex_handle v, signed_size_type id)	2,950✔
115	{
116	m_parent_id[v->id()] = id;	2,950✔
117	}	2,950✔
118
119	inline bool visited(vertex_handle v) const	6,073✔
120	{
121	return m_visited[v->id()];	6,073✔
122	}
123
124	inline void set_visited(vertex_handle v, bool value)	3,549✔
125	{
126	m_visited[v->id()] = value;	3,549✔
127	}	3,549✔
128	private:
129	std::vector<bool> m_visited;
130	std::vector<signed_size_type> m_parent_id;
131	};
132
133
134	inline bool has_cycles(vertex_handle start_vertex,	803✔
135	has_cycles_dfs_data& data) const
136	{
137	std::stack<vertex_handle> stack;	1,606✔
138	stack.push(start_vertex);	803✔
139
140	while ( !stack.empty() )	4,236✔
141	{
142	vertex_handle v = stack.top();	3,549✔
143	stack.pop();	3,549✔
144
145	data.set_visited(v, true);	3,549✔
146	for (typename neighbor_container::const_iterator nit	9,129✔
147	= m_neighbors[v->id()].begin();	3,549✔
148	nit != m_neighbors[v->id()].end(); ++nit)	14,709✔
149	{
150	if ( static_cast<signed_size_type>((*nit)->id()) != data.parent_id(v) )	5,696✔
151	{
152	if ( data.visited(*nit) )	3,066✔
153	{
154	return true;	116✔
155	}
156	else
157	{
158	data.set_parent_id(*nit, static_cast<signed_size_type>(v->id()));	2,950✔
159	stack.push(*nit);	2,950✔
160	}
161	}
162	}
163	}
164	return false;	687✔
165	}
166
167	public:
168	// num_rings: total number of rings, including the exterior ring
169	complement_graph(std::size_t num_rings)	13,565✔
170	: m_num_rings(num_rings)
171	, m_num_turns(0)
172	, m_vertices()
173	, m_neighbors(num_rings)	13,565✔
174	{}	13,565✔
175
176	// inserts a ring vertex in the graph and returns its handle
177	// ring id's are zero-based (so the first interior ring has id 1)
178	inline vertex_handle add_vertex(signed_size_type id)	3,608✔
179	{
180	return m_vertices.insert(vertex(static_cast<std::size_t>(id))).first;	3,608✔
181	}
182
183	// inserts an IP in the graph and returns its id
184	inline vertex_handle add_vertex(TurnPoint const& turn_point)	1,804✔
185	{
186	std::pair<vertex_handle, bool> res	1,804✔
187	= m_vertices.insert(vertex(std::addressof(turn_point),
188	m_num_rings + m_num_turns)	1,804✔
189	);
190
191	if ( res.second )	1,804✔
192	{
193	// a new element is inserted
194	m_neighbors.push_back(neighbor_container());	1,396✔
195	++m_num_turns;	1,396✔
196	}
197	return res.first;	1,804✔
198	}
199
200	inline void add_edge(vertex_handle v1, vertex_handle v2)	3,608✔
201	{
202	BOOST_GEOMETRY_ASSERT( v1 != m_vertices.end() );	3,608✔
203	BOOST_GEOMETRY_ASSERT( v2 != m_vertices.end() );	3,608✔
204	m_neighbors[v1->id()].insert(v2);	3,608✔
205	m_neighbors[v2->id()].insert(v1);	3,608✔
206	}	3,608✔
207
208	inline bool has_cycles() const	13,565✔
209	{
210	// initialize all vertices as non-visited and with no parent set
211	// this is done by the constructor of has_cycles_dfs_data
212	has_cycles_dfs_data data(m_num_rings + m_num_turns);	27,130✔
213
214	// for each non-visited vertex, start a DFS from that vertex
215	for (vertex_handle it = m_vertices.begin();	16,456✔
216	it != m_vertices.end(); ++it)	19,347✔
217	{
218	if ( !data.visited(it) && has_cycles(it, data) )	3,007✔
219	{
220	return true;	116✔
221	}
222	}
223	return false;	13,449✔
224	}
225
226	#ifdef BOOST_GEOMETRY_TEST_DEBUG
227	template <typename OutputStream>
228	friend inline
229	void debug_print_complement_graph(OutputStream&,
230	complement_graph<TurnPoint, Strategy> const&);
231	#endif // BOOST_GEOMETRY_TEST_DEBUG
232
233	private:
234	std::size_t m_num_rings, m_num_turns;
235	vertex_container m_vertices;
236	std::vector<neighbor_container> m_neighbors;
237	};
238
239
240	}} // namespace detail::is_valid
241
242	}} // namespace boost::geometry
243
244	#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_COMPLEMENT_GRAPH_HPP

boostorg / geometry / 26001

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous