ceph/src/boost/libs/geometry/include/boost/geometry/algorithms/detail/is_valid/complement_graph.hpp

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