ceph/src/boost/boost/geometry/algorithms/detail/overlay/check_enrich.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
   4
   5 // Use, modification and distribution is subject to the Boost Software License,
   6 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   7 // http://www.boost.org/LICENSE_1_0.txt)
   8
   9 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_CHECK_ENRICH_HPP
  10 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_CHECK_ENRICH_HPP
  11
  12
  13 #include <cstddef>
  14
  15 #include <boost/range.hpp>
  16
  17 #include <boost/geometry/algorithms/detail/ring_identifier.hpp>
  18
  19
  20 namespace boost { namespace geometry
  21 {
  22
  23 #ifndef DOXYGEN_NO_DETAIL
  24 namespace detail { namespace overlay
  25 {
  26
  27
  28 template<typename Turn>
  29 struct meta_turn
  30 {
  31     int index;
  32     Turn const* turn;
  33     bool handled[2];
  34
  35     inline meta_turn(int i, Turn const& t)
  36         : index(i), turn(&t)
  37     {
  38         handled[0] = false;
  39         handled[1] = false;
  40     }
  41 };
  42
  43
  44 template <typename MetaTurn>
  45 inline void display(MetaTurn const& meta_turn, std::string const& reason = "")
  46 {
  47 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
  48     std::cout << meta_turn.index
  49         << "\tMethods: " << method_char(meta_turn.turn->method)
  50         << " operations: "  << operation_char(meta_turn.turn->operations[0].operation)
  51                 << operation_char(meta_turn.turn->operations[1].operation)
  52         << " travels to " << meta_turn.turn->operations[0].enriched.travels_to_ip_index
  53         << " and " << meta_turn.turn->operations[1].enriched.travels_to_ip_index
  54         //<< " -> " << op_index
  55         << " " << reason
  56         << std::endl;
  57 #endif
  58 }
  59
  60
  61 template <typename MetaTurns, typename MetaTurn>
  62 inline void check_detailed(MetaTurns& meta_turns, MetaTurn const& meta_turn,
  63             int op_index, int cycle, int start, operation_type for_operation,
  64             bool& error)
  65 {
  66     display(meta_turn);
  67     int const ip_index = meta_turn.turn->operations[op_index].enriched.travels_to_ip_index;
  68     if (ip_index >= 0)
  69     {
  70         bool found = false;
  71
  72         if (ip_index == start)
  73         {
  74             display(meta_turns[ip_index], " FINISH");
  75             return;
  76         }
  77
  78         // check on continuing, or on same-operation-on-same-geometry
  79         if (! meta_turns[ip_index].handled[op_index]
  80             && (meta_turns[ip_index].turn->operations[op_index].operation == operation_continue
  81                 || meta_turns[ip_index].turn->operations[op_index].operation == for_operation)
  82             )
  83         {
  84             meta_turns[ip_index].handled[op_index] = true;
  85             check_detailed(meta_turns, meta_turns[ip_index], op_index, cycle, start, for_operation, error);
  86             found = true;
  87         }
  88         // check on other geometry
  89         if (! found)
  90         {
  91             int const other_index = 1 - op_index;
  92             if (! meta_turns[ip_index].handled[other_index]
  93                 && meta_turns[ip_index].turn->operations[other_index].operation == for_operation)
  94             {
  95                 meta_turns[ip_index].handled[other_index] = true;
  96                 check_detailed(meta_turns, meta_turns[ip_index], other_index, cycle, start, for_operation, error);
  97                 found = true;
  98             }
  99         }
 100
 101         if (! found)
 102         {
 103             display(meta_turns[ip_index], " STOP");
 104             error = true;
 105 #ifndef BOOST_GEOMETRY_DEBUG_ENRICH
 106             //std::cout << " STOP";
 107 #endif
 108         }
 109     }
 110 }
 111
 112
 113 template <typename TurnPoints>
 114 inline bool check_graph(TurnPoints& turn_points, operation_type for_operation)
 115 {
 116     typedef typename boost::range_value<TurnPoints>::type turn_point_type;
 117
 118     bool error = false;
 119     int index = 0;
 120
 121     std::vector<meta_turn<turn_point_type> > meta_turns;
 122     for (typename boost::range_iterator<TurnPoints const>::type
 123             it = boost::begin(turn_points);
 124          it != boost::end(turn_points);
 125          ++it, ++index)
 126     {
 127         meta_turns.push_back(meta_turn<turn_point_type>(index, *it));
 128     }
 129
 130     int cycle = 0;
 131     for (typename boost::range_iterator<std::vector<meta_turn<turn_point_type> > > ::type
 132             it = boost::begin(meta_turns);
 133          it != boost::end(meta_turns);
 134          ++it)
 135     {
 136         if (! (it->turn->blocked() || it->turn->discarded))
 137         {
 138             for (int i = 0 ; i < 2; i++)
 139             {
 140                 if (! it->handled[i]
 141                     && it->turn->operations[i].operation == for_operation)
 142                 {
 143 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
 144                     std::cout << "CYCLE " << cycle << std::endl;
 145 #endif
 146                     it->handled[i] = true;
 147                     check_detailed(meta_turns, *it, i, cycle++, it->index, for_operation, error);
 148 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
 149                     std::cout <<" END CYCLE " << it->index << std::endl;
 150 #endif
 151                 }
 152             }
 153         }
 154     }
 155     return error;
 156 }
 157
 158
 159
 160 }} // namespace detail::overlay
 161 #endif //DOXYGEN_NO_DETAIL
 162
 163
 164
 165 }} // namespace boost::geometry
 166
 167
 168 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_CHECK_ENRICH_HPP