ceph/src/boost/boost/geometry/algorithms/detail/relate/result.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
   4 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
   5
   6 // This file was modified by Oracle on 2013-2016.
   7 // Modifications copyright (c) 2013-2016 Oracle and/or its affiliates.
   8
   9 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
  10
  11 // Use, modification and distribution is subject to the Boost Software License,
  12 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  13 // http://www.boost.org/LICENSE_1_0.txt)
  14
  15 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_RESULT_HPP
  16 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_RESULT_HPP
  17
  18 #include <cstddef>
  19
  20 #include <boost/mpl/assert.hpp>
  21 #include <boost/mpl/at.hpp>
  22 #include <boost/mpl/begin.hpp>
  23 #include <boost/mpl/deref.hpp>
  24 #include <boost/mpl/end.hpp>
  25 #include <boost/mpl/is_sequence.hpp>
  26 #include <boost/mpl/next.hpp>
  27 #include <boost/static_assert.hpp>
  28 #include <boost/throw_exception.hpp>
  29 #include <boost/tuple/tuple.hpp>
  30 #include <boost/type_traits/integral_constant.hpp>
  31
  32 #include <boost/geometry/core/assert.hpp>
  33 #include <boost/geometry/core/coordinate_dimension.hpp>
  34 #include <boost/geometry/core/exception.hpp>
  35 #include <boost/geometry/util/condition.hpp>
  36
  37 namespace boost { namespace geometry {
  38
  39 #ifndef DOXYGEN_NO_DETAIL
  40 namespace detail { namespace relate {
  41
  42 enum field { interior = 0, boundary = 1, exterior = 2 };
  43
  44 // TODO: IF THE RESULT IS UPDATED WITH THE MAX POSSIBLE VALUE FOR SOME PAIR OF GEOEMTRIES
  45 // THE VALUE ALREADY STORED MUSN'T BE CHECKED
  46 // update() calls chould be replaced with set() in those cases
  47 // but for safety reasons (STATIC_ASSERT) we should check if parameter D is valid and set() doesn't do that
  48 // so some additional function could be added, e.g. set_dim()
  49
  50 // --------------- MATRIX ----------------
  51
  52 // matrix
  53
  54 template <std::size_t Height, std::size_t Width = Height>
  55 class matrix
  56 {
  57 public:
  58     typedef char value_type;
  59     typedef std::size_t size_type;
  60     typedef const char * const_iterator;
  61     typedef const_iterator iterator;
  62
  63     static const std::size_t static_width = Width;
  64     static const std::size_t static_height = Height;
  65     static const std::size_t static_size = Width * Height;
  66
  67     inline matrix()
  68     {
  69         ::memset(m_array, 'F', static_size);
  70     }
  71
  72     template <field F1, field F2>
  73     inline char get() const
  74     {
  75         BOOST_STATIC_ASSERT(F1 < Height && F2 < Width);
  76         static const std::size_t index = F1 * Width + F2;
  77         BOOST_STATIC_ASSERT(index < static_size);
  78         return m_array[index];
  79     }
  80
  81     template <field F1, field F2, char V>
  82     inline void set()
  83     {
  84         BOOST_STATIC_ASSERT(F1 < Height && F2 < Width);
  85         static const std::size_t index = F1 * Width + F2;
  86         BOOST_STATIC_ASSERT(index < static_size);
  87         m_array[index] = V;
  88     }
  89
  90     inline char operator[](std::size_t index) const
  91     {
  92         BOOST_GEOMETRY_ASSERT(index < static_size);
  93         return m_array[index];
  94     }
  95
  96     inline const_iterator begin() const
  97     {
  98         return m_array;
  99     }
 100
 101     inline const_iterator end() const
 102     {
 103         return m_array + static_size;
 104     }
 105
 106     inline static std::size_t size()
 107     {
 108         return static_size;
 109     }
 110
 111     inline const char * data() const
 112     {
 113         return m_array;
 114     }
 115
 116     inline std::string str() const
 117     {
 118         return std::string(m_array, static_size);
 119     }
 120
 121 private:
 122     char m_array[static_size];
 123 };
 124
 125 // matrix_handler
 126
 127 template <typename Matrix>
 128 class matrix_handler
 129 {
 130 public:
 131     typedef Matrix result_type;
 132
 133     static const bool interrupt = false;
 134
 135     matrix_handler()
 136     {}
 137
 138     result_type const& result() const
 139     {
 140         return m_matrix;
 141     }
 142
 143     result_type const& matrix() const
 144     {
 145         return m_matrix;
 146     }
 147
 148     result_type & matrix()
 149     {
 150         return m_matrix;
 151     }
 152
 153     template <field F1, field F2, char D>
 154     inline bool may_update() const
 155     {
 156         BOOST_STATIC_ASSERT('0' <= D && D <= '9');
 157
 158         char const c = m_matrix.template get<F1, F2>();
 159         return D > c || c > '9';
 160     }
 161
 162     template <field F1, field F2, char V>
 163     inline void set()
 164     {
 165         static const bool in_bounds = F1 < Matrix::static_height
 166                                    && F2 < Matrix::static_width;
 167         typedef boost::integral_constant<bool, in_bounds> in_bounds_t;
 168         set_dispatch<F1, F2, V>(in_bounds_t());
 169     }
 170
 171     template <field F1, field F2, char D>
 172     inline void update()
 173     {
 174         static const bool in_bounds = F1 < Matrix::static_height
 175                                    && F2 < Matrix::static_width;
 176         typedef boost::integral_constant<bool, in_bounds> in_bounds_t;
 177         update_dispatch<F1, F2, D>(in_bounds_t());
 178     }
 179
 180 private:
 181     template <field F1, field F2, char V>
 182     inline void set_dispatch(integral_constant<bool, true>)
 183     {
 184         static const std::size_t index = F1 * Matrix::static_width + F2;
 185         BOOST_STATIC_ASSERT(index < Matrix::static_size);
 186         BOOST_STATIC_ASSERT(('0' <= V && V <= '9') || V == 'T' || V == 'F');
 187         m_matrix.template set<F1, F2, V>();
 188     }
 189     template <field F1, field F2, char V>
 190     inline void set_dispatch(integral_constant<bool, false>)
 191     {}
 192
 193     template <field F1, field F2, char D>
 194     inline void update_dispatch(integral_constant<bool, true>)
 195     {
 196         static const std::size_t index = F1 * Matrix::static_width + F2;
 197         BOOST_STATIC_ASSERT(index < Matrix::static_size);
 198         BOOST_STATIC_ASSERT('0' <= D && D <= '9');
 199         char const c = m_matrix.template get<F1, F2>();
 200         if ( D > c || c > '9')
 201             m_matrix.template set<F1, F2, D>();
 202     }
 203     template <field F1, field F2, char D>
 204     inline void update_dispatch(integral_constant<bool, false>)
 205     {}
 206
 207     Matrix m_matrix;
 208 };
 209
 210 // --------------- RUN-TIME MASK ----------------
 211
 212 // run-time mask
 213
 214 template <std::size_t Height, std::size_t Width = Height>
 215 class mask
 216 {
 217 public:
 218     static const std::size_t static_width = Width;
 219     static const std::size_t static_height = Height;
 220     static const std::size_t static_size = Width * Height;
 221
 222     inline mask(const char * s)
 223     {
 224         char * it = m_array;
 225         char * const last = m_array + static_size;
 226         for ( ; it != last && *s != '\0' ; ++it, ++s )
 227         {
 228             char c = *s;
 229             check_char(c);
 230             *it = c;
 231         }
 232         if ( it != last )
 233         {
 234             ::memset(it, '*', last - it);
 235         }
 236     }
 237
 238     inline mask(const char * s, std::size_t count)
 239     {
 240         if ( count > static_size )
 241         {
 242             count = static_size;
 243         }
 244         if ( count > 0 )
 245         {
 246             std::for_each(s, s + count, check_char);
 247             ::memcpy(m_array, s, count);
 248         }
 249         if ( count < static_size )
 250         {
 251             ::memset(m_array + count, '*', static_size - count);
 252         }
 253     }
 254
 255     template <field F1, field F2>
 256     inline char get() const
 257     {
 258         BOOST_STATIC_ASSERT(F1 < Height && F2 < Width);
 259         static const std::size_t index = F1 * Width + F2;
 260         BOOST_STATIC_ASSERT(index < static_size);
 261         return m_array[index];
 262     }
 263
 264 private:
 265     static inline void check_char(char c)
 266     {
 267         bool const is_valid = c == '*' || c == 'T' || c == 'F'
 268                          || ( c >= '0' && c <= '9' );
 269         if ( !is_valid )
 270         {
 271             BOOST_THROW_EXCEPTION(geometry::invalid_input_exception());
 272         }
 273     }
 274
 275     char m_array[static_size];
 276 };
 277
 278 // interrupt()
 279
 280 template <typename Mask, bool InterruptEnabled>
 281 struct interrupt_dispatch
 282 {
 283     template <field F1, field F2, char V>
 284     static inline bool apply(Mask const&)
 285     {
 286         return false;
 287     }
 288 };
 289
 290 template <typename Mask>
 291 struct interrupt_dispatch<Mask, true>
 292 {
 293     template <field F1, field F2, char V>
 294     static inline bool apply(Mask const& mask)
 295     {
 296         char m = mask.template get<F1, F2>();
 297         return check_element<V>(m);
 298     }
 299
 300     template <char V>
 301     static inline bool check_element(char m)
 302     {
 303         if ( BOOST_GEOMETRY_CONDITION(V >= '0' && V <= '9') )
 304         {
 305             return m == 'F' || ( m < V && m >= '0' && m <= '9' );
 306         }
 307         else if ( BOOST_GEOMETRY_CONDITION(V == 'T') )
 308         {
 309             return m == 'F';
 310         }
 311         return false;
 312     }
 313 };
 314
 315 template <typename Masks, int I = 0, int N = boost::tuples::length<Masks>::value>
 316 struct interrupt_dispatch_tuple
 317 {
 318     template <field F1, field F2, char V>
 319     static inline bool apply(Masks const& masks)
 320     {
 321         typedef typename boost::tuples::element<I, Masks>::type mask_type;
 322         mask_type const& mask = boost::get<I>(masks);
 323         return interrupt_dispatch<mask_type, true>::template apply<F1, F2, V>(mask)
 324             && interrupt_dispatch_tuple<Masks, I+1>::template apply<F1, F2, V>(masks);
 325     }
 326 };
 327
 328 template <typename Masks, int N>
 329 struct interrupt_dispatch_tuple<Masks, N, N>
 330 {
 331     template <field F1, field F2, char V>
 332     static inline bool apply(Masks const& )
 333     {
 334         return true;
 335     }
 336 };
 337
 338 //template <typename T0, typename T1, typename T2, typename T3, typename T4,
 339 //          typename T5, typename T6, typename T7, typename T8, typename T9>
 340 //struct interrupt_dispatch<boost::tuple<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9>, true>
 341 //{
 342 //    typedef boost::tuple<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9> mask_type;
 343
 344 //    template <field F1, field F2, char V>
 345 //    static inline bool apply(mask_type const& mask)
 346 //    {
 347 //        return interrupt_dispatch_tuple<mask_type>::template apply<F1, F2, V>(mask);
 348 //    }
 349 //};
 350
 351 template <typename Head, typename Tail>
 352 struct interrupt_dispatch<boost::tuples::cons<Head, Tail>, true>
 353 {
 354     typedef boost::tuples::cons<Head, Tail> mask_type;
 355
 356     template <field F1, field F2, char V>
 357     static inline bool apply(mask_type const& mask)
 358     {
 359         return interrupt_dispatch_tuple<mask_type>::template apply<F1, F2, V>(mask);
 360     }
 361 };
 362
 363 template <field F1, field F2, char V, bool InterruptEnabled, typename Mask>
 364 inline bool interrupt(Mask const& mask)
 365 {
 366     return interrupt_dispatch<Mask, InterruptEnabled>
 367                 ::template apply<F1, F2, V>(mask);
 368 }
 369
 370 // may_update()
 371
 372 template <typename Mask>
 373 struct may_update_dispatch
 374 {
 375     template <field F1, field F2, char D, typename Matrix>
 376     static inline bool apply(Mask const& mask, Matrix const& matrix)
 377     {
 378         BOOST_STATIC_ASSERT('0' <= D && D <= '9');
 379
 380         char const m = mask.template get<F1, F2>();
 381
 382         if ( m == 'F' )
 383         {
 384             return true;
 385         }
 386         else if ( m == 'T' )
 387         {
 388             char const c = matrix.template get<F1, F2>();
 389             return c == 'F'; // if it's T or between 0 and 9, the result will be the same
 390         }
 391         else if ( m >= '0' && m <= '9' )
 392         {
 393             char const c = matrix.template get<F1, F2>();
 394             return D > c || c > '9';
 395         }
 396
 397         return false;
 398     }
 399 };
 400
 401 template <typename Masks, int I = 0, int N = boost::tuples::length<Masks>::value>
 402 struct may_update_dispatch_tuple
 403 {
 404     template <field F1, field F2, char D, typename Matrix>
 405     static inline bool apply(Masks const& masks, Matrix const& matrix)
 406     {
 407         typedef typename boost::tuples::element<I, Masks>::type mask_type;
 408         mask_type const& mask = boost::get<I>(masks);
 409         return may_update_dispatch<mask_type>::template apply<F1, F2, D>(mask, matrix)
 410             || may_update_dispatch_tuple<Masks, I+1>::template apply<F1, F2, D>(masks, matrix);
 411     }
 412 };
 413
 414 template <typename Masks, int N>
 415 struct may_update_dispatch_tuple<Masks, N, N>
 416 {
 417     template <field F1, field F2, char D, typename Matrix>
 418     static inline bool apply(Masks const& , Matrix const& )
 419     {
 420         return false;
 421     }
 422 };
 423
 424 //template <typename T0, typename T1, typename T2, typename T3, typename T4,
 425 //          typename T5, typename T6, typename T7, typename T8, typename T9>
 426 //struct may_update_dispatch< boost::tuple<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9> >
 427 //{
 428 //    typedef boost::tuple<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9> mask_type;
 429
 430 //    template <field F1, field F2, char D, typename Matrix>
 431 //    static inline bool apply(mask_type const& mask, Matrix const& matrix)
 432 //    {
 433 //        return may_update_dispatch_tuple<mask_type>::template apply<F1, F2, D>(mask, matrix);
 434 //    }
 435 //};
 436
 437 template <typename Head, typename Tail>
 438 struct may_update_dispatch< boost::tuples::cons<Head, Tail> >
 439 {
 440     typedef boost::tuples::cons<Head, Tail> mask_type;
 441
 442     template <field F1, field F2, char D, typename Matrix>
 443     static inline bool apply(mask_type const& mask, Matrix const& matrix)
 444     {
 445         return may_update_dispatch_tuple<mask_type>::template apply<F1, F2, D>(mask, matrix);
 446     }
 447 };
 448
 449 template <field F1, field F2, char D, typename Mask, typename Matrix>
 450 inline bool may_update(Mask const& mask, Matrix const& matrix)
 451 {
 452     return may_update_dispatch<Mask>
 453                 ::template apply<F1, F2, D>(mask, matrix);
 454 }
 455
 456 // check_matrix()
 457
 458 template <typename Mask>
 459 struct check_dispatch
 460 {
 461     template <typename Matrix>
 462     static inline bool apply(Mask const& mask, Matrix const& matrix)
 463     {
 464         return per_one<interior, interior>(mask, matrix)
 465             && per_one<interior, boundary>(mask, matrix)
 466             && per_one<interior, exterior>(mask, matrix)
 467             && per_one<boundary, interior>(mask, matrix)
 468             && per_one<boundary, boundary>(mask, matrix)
 469             && per_one<boundary, exterior>(mask, matrix)
 470             && per_one<exterior, interior>(mask, matrix)
 471             && per_one<exterior, boundary>(mask, matrix)
 472             && per_one<exterior, exterior>(mask, matrix);
 473     }
 474
 475     template <field F1, field F2, typename Matrix>
 476     static inline bool per_one(Mask const& mask, Matrix const& matrix)
 477     {
 478         const char mask_el = mask.template get<F1, F2>();
 479         const char el = matrix.template get<F1, F2>();
 480
 481         if ( mask_el == 'F' )
 482         {
 483             return el == 'F';
 484         }
 485         else if ( mask_el == 'T' )
 486         {
 487             return el == 'T' || ( el >= '0' && el <= '9' );
 488         }
 489         else if ( mask_el >= '0' && mask_el <= '9' )
 490         {
 491             return el == mask_el;
 492         }
 493
 494         return true;
 495     }
 496 };
 497
 498 template <typename Masks, int I = 0, int N = boost::tuples::length<Masks>::value>
 499 struct check_dispatch_tuple
 500 {
 501     template <typename Matrix>
 502     static inline bool apply(Masks const& masks, Matrix const& matrix)
 503     {
 504         typedef typename boost::tuples::element<I, Masks>::type mask_type;
 505         mask_type const& mask = boost::get<I>(masks);
 506         return check_dispatch<mask_type>::apply(mask, matrix)
 507             || check_dispatch_tuple<Masks, I+1>::apply(masks, matrix);
 508     }
 509 };
 510
 511 template <typename Masks, int N>
 512 struct check_dispatch_tuple<Masks, N, N>
 513 {
 514     template <typename Matrix>
 515     static inline bool apply(Masks const&, Matrix const&)
 516     {
 517         return false;
 518     }
 519 };
 520
 521 //template <typename T0, typename T1, typename T2, typename T3, typename T4,
 522 //          typename T5, typename T6, typename T7, typename T8, typename T9>
 523 //struct check_dispatch< boost::tuple<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9> >
 524 //{
 525 //    typedef boost::tuple<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9> mask_type;
 526
 527 //    template <typename Matrix>
 528 //    static inline bool apply(mask_type const& mask, Matrix const& matrix)
 529 //    {
 530 //        return check_dispatch_tuple<mask_type>::apply(mask, matrix);
 531 //    }
 532 //};
 533
 534 template <typename Head, typename Tail>
 535 struct check_dispatch< boost::tuples::cons<Head, Tail> >
 536 {
 537     typedef boost::tuples::cons<Head, Tail> mask_type;
 538
 539     template <typename Matrix>
 540     static inline bool apply(mask_type const& mask, Matrix const& matrix)
 541     {
 542         return check_dispatch_tuple<mask_type>::apply(mask, matrix);
 543     }
 544 };
 545
 546 template <typename Mask, typename Matrix>
 547 inline bool check_matrix(Mask const& mask, Matrix const& matrix)
 548 {
 549     return check_dispatch<Mask>::apply(mask, matrix);
 550 }
 551
 552 // matrix_width
 553
 554 template <typename MatrixOrMask>
 555 struct matrix_width
 556 {
 557     static const std::size_t value = MatrixOrMask::static_width;
 558 };
 559
 560 template <typename Tuple,
 561           int I = 0,
 562           int N = boost::tuples::length<Tuple>::value>
 563 struct matrix_width_tuple
 564 {
 565     static const std::size_t
 566         current = matrix_width<typename boost::tuples::element<I, Tuple>::type>::value;
 567     static const std::size_t
 568         next = matrix_width_tuple<Tuple, I+1>::value;
 569
 570     static const std::size_t
 571         value = current > next ? current : next;
 572 };
 573
 574 template <typename Tuple, int N>
 575 struct matrix_width_tuple<Tuple, N, N>
 576 {
 577     static const std::size_t value = 0;
 578 };
 579
 580 template <typename Head, typename Tail>
 581 struct matrix_width< boost::tuples::cons<Head, Tail> >
 582 {
 583     static const std::size_t
 584         value = matrix_width_tuple< boost::tuples::cons<Head, Tail> >::value;
 585 };
 586
 587 // mask_handler
 588
 589 template <typename Mask, bool Interrupt>
 590 class mask_handler
 591     : private matrix_handler
 592         <
 593             relate::matrix<matrix_width<Mask>::value>
 594         >
 595 {
 596     typedef matrix_handler
 597         <
 598             relate::matrix<matrix_width<Mask>::value>
 599         > base_t;
 600
 601 public:
 602     typedef bool result_type;
 603
 604     bool interrupt;
 605
 606     inline explicit mask_handler(Mask const& m)
 607         : interrupt(false)
 608         , m_mask(m)
 609     {}
 610
 611     result_type result() const
 612     {
 613         return !interrupt
 614             && check_matrix(m_mask, base_t::matrix());
 615     }
 616
 617     template <field F1, field F2, char D>
 618     inline bool may_update() const
 619     {
 620         return detail::relate::may_update<F1, F2, D>(
 621                     m_mask, base_t::matrix()
 622                );
 623     }
 624
 625     template <field F1, field F2, char V>
 626     inline void set()
 627     {
 628         if ( relate::interrupt<F1, F2, V, Interrupt>(m_mask) )
 629         {
 630             interrupt = true;
 631         }
 632         else
 633         {
 634             base_t::template set<F1, F2, V>();
 635         }
 636     }
 637
 638     template <field F1, field F2, char V>
 639     inline void update()
 640     {
 641         if ( relate::interrupt<F1, F2, V, Interrupt>(m_mask) )
 642         {
 643             interrupt = true;
 644         }
 645         else
 646         {
 647             base_t::template update<F1, F2, V>();
 648         }
 649     }
 650
 651 private:
 652     Mask const& m_mask;
 653 };
 654
 655 // --------------- COMPILE-TIME MASK ----------------
 656
 657 // static_check_characters
 658 template
 659 <
 660     typename Seq,
 661     typename First = typename boost::mpl::begin<Seq>::type,
 662     typename Last = typename boost::mpl::end<Seq>::type
 663 >
 664 struct static_check_characters
 665     : static_check_characters
 666         <
 667             Seq,
 668             typename boost::mpl::next<First>::type
 669         >
 670 {
 671     typedef typename boost::mpl::deref<First>::type type;
 672     static const char value = type::value;
 673     static const bool is_valid = (value >= '0' && value <= '9')
 674                                || value == 'T' || value == 'F' || value == '*';
 675     BOOST_MPL_ASSERT_MSG((is_valid),
 676                          INVALID_STATIC_MASK_CHARACTER,
 677                          (type));
 678 };
 679
 680 template <typename Seq, typename Last>
 681 struct static_check_characters<Seq, Last, Last>
 682 {};
 683
 684 // static_mask
 685
 686 template
 687 <
 688     typename Seq,
 689     std::size_t Height,
 690     std::size_t Width = Height
 691 >
 692 struct static_mask
 693 {
 694     static const std::size_t static_width = Width;
 695     static const std::size_t static_height = Height;
 696     static const std::size_t static_size = Width * Height;
 697
 698     BOOST_STATIC_ASSERT(
 699         std::size_t(boost::mpl::size<Seq>::type::value) == static_size);
 700
 701     template <detail::relate::field F1, detail::relate::field F2>
 702     struct static_get
 703     {
 704         BOOST_STATIC_ASSERT(std::size_t(F1) < static_height);
 705         BOOST_STATIC_ASSERT(std::size_t(F2) < static_width);
 706
 707         static const char value
 708             = boost::mpl::at_c<Seq, F1 * static_width + F2>::type::value;
 709     };
 710
 711 private:
 712     // check static_mask characters
 713     enum { mask_check = sizeof(static_check_characters<Seq>) };
 714 };
 715
 716 // static_should_handle_element
 717
 718 template <typename StaticMask, field F1, field F2, bool IsSequence>
 719 struct static_should_handle_element_dispatch
 720 {
 721     static const char mask_el = StaticMask::template static_get<F1, F2>::value;
 722     static const bool value = mask_el == 'F'
 723                            || mask_el == 'T'
 724                            || ( mask_el >= '0' && mask_el <= '9' );
 725 };
 726
 727 template <typename First, typename Last, field F1, field F2>
 728 struct static_should_handle_element_sequence
 729 {
 730     typedef typename boost::mpl::deref<First>::type StaticMask;
 731
 732     static const bool value
 733         = static_should_handle_element_dispatch
 734             <
 735                 StaticMask,
 736                 F1, F2,
 737                 boost::mpl::is_sequence<StaticMask>::value
 738             >::value
 739        || static_should_handle_element_sequence
 740             <
 741                 typename boost::mpl::next<First>::type,
 742                 Last,
 743                 F1, F2
 744             >::value;
 745 };
 746
 747 template <typename Last, field F1, field F2>
 748 struct static_should_handle_element_sequence<Last, Last, F1, F2>
 749 {
 750     static const bool value = false;
 751 };
 752
 753 template <typename StaticMask, field F1, field F2>
 754 struct static_should_handle_element_dispatch<StaticMask, F1, F2, true>
 755 {
 756     static const bool value
 757         = static_should_handle_element_sequence
 758             <
 759                 typename boost::mpl::begin<StaticMask>::type,
 760                 typename boost::mpl::end<StaticMask>::type,
 761                 F1, F2
 762             >::value;
 763 };
 764
 765 template <typename StaticMask, field F1, field F2>
 766 struct static_should_handle_element
 767 {
 768     static const bool value
 769         = static_should_handle_element_dispatch
 770             <
 771                 StaticMask,
 772                 F1, F2,
 773                 boost::mpl::is_sequence<StaticMask>::value
 774             >::value;
 775 };
 776
 777 // static_interrupt
 778
 779 template <typename StaticMask, char V, field F1, field F2, bool InterruptEnabled, bool IsSequence>
 780 struct static_interrupt_dispatch
 781 {
 782     static const bool value = false;
 783 };
 784
 785 template <typename StaticMask, char V, field F1, field F2, bool IsSequence>
 786 struct static_interrupt_dispatch<StaticMask, V, F1, F2, true, IsSequence>
 787 {
 788     static const char mask_el = StaticMask::template static_get<F1, F2>::value;
 789
 790     static const bool value
 791         = ( V >= '0' && V <= '9' ) ?
 792           ( mask_el == 'F' || ( mask_el < V && mask_el >= '0' && mask_el <= '9' ) ) :
 793           ( ( V == 'T' ) ? mask_el == 'F' : false );
 794 };
 795
 796 template <typename First, typename Last, char V, field F1, field F2>
 797 struct static_interrupt_sequence
 798 {
 799     typedef typename boost::mpl::deref<First>::type StaticMask;
 800
 801     static const bool value
 802         = static_interrupt_dispatch
 803             <
 804                 StaticMask,
 805                 V, F1, F2,
 806                 true,
 807                 boost::mpl::is_sequence<StaticMask>::value
 808             >::value
 809        && static_interrupt_sequence
 810             <
 811                 typename boost::mpl::next<First>::type,
 812                 Last,
 813                 V, F1, F2
 814             >::value;
 815 };
 816
 817 template <typename Last, char V, field F1, field F2>
 818 struct static_interrupt_sequence<Last, Last, V, F1, F2>
 819 {
 820     static const bool value = true;
 821 };
 822
 823 template <typename StaticMask, char V, field F1, field F2>
 824 struct static_interrupt_dispatch<StaticMask, V, F1, F2, true, true>
 825 {
 826     static const bool value
 827         = static_interrupt_sequence
 828             <
 829                 typename boost::mpl::begin<StaticMask>::type,
 830                 typename boost::mpl::end<StaticMask>::type,
 831                 V, F1, F2
 832             >::value;
 833 };
 834
 835 template <typename StaticMask, char V, field F1, field F2, bool EnableInterrupt>
 836 struct static_interrupt
 837 {
 838     static const bool value
 839         = static_interrupt_dispatch
 840             <
 841                 StaticMask,
 842                 V, F1, F2,
 843                 EnableInterrupt,
 844                 boost::mpl::is_sequence<StaticMask>::value
 845             >::value;
 846 };
 847
 848 // static_may_update
 849
 850 template <typename StaticMask, char D, field F1, field F2, bool IsSequence>
 851 struct static_may_update_dispatch
 852 {
 853     static const char mask_el = StaticMask::template static_get<F1, F2>::value;
 854     static const int version
 855                         = mask_el == 'F' ? 0
 856                         : mask_el == 'T' ? 1
 857                         : mask_el >= '0' && mask_el <= '9' ? 2
 858                         : 3;
 859
 860     template <typename Matrix>
 861     static inline bool apply(Matrix const& matrix)
 862     {
 863         return apply_dispatch(matrix, integral_constant<int, version>());
 864     }
 865
 866     // mask_el == 'F'
 867     template <typename Matrix>
 868     static inline bool apply_dispatch(Matrix const& , integral_constant<int, 0>)
 869     {
 870         return true;
 871     }
 872     // mask_el == 'T'
 873     template <typename Matrix>
 874     static inline bool apply_dispatch(Matrix const& matrix, integral_constant<int, 1>)
 875     {
 876         char const c = matrix.template get<F1, F2>();
 877         return c == 'F'; // if it's T or between 0 and 9, the result will be the same
 878     }
 879     // mask_el >= '0' && mask_el <= '9'
 880     template <typename Matrix>
 881     static inline bool apply_dispatch(Matrix const& matrix, integral_constant<int, 2>)
 882     {
 883         char const c = matrix.template get<F1, F2>();
 884         return D > c || c > '9';
 885     }
 886     // else
 887     template <typename Matrix>
 888     static inline bool apply_dispatch(Matrix const&, integral_constant<int, 3>)
 889     {
 890         return false;
 891     }
 892 };
 893
 894 template <typename First, typename Last, char D, field F1, field F2>
 895 struct static_may_update_sequence
 896 {
 897     typedef typename boost::mpl::deref<First>::type StaticMask;
 898
 899     template <typename Matrix>
 900     static inline bool apply(Matrix const& matrix)
 901     {
 902         return static_may_update_dispatch
 903                 <
 904                     StaticMask,
 905                     D, F1, F2,
 906                     boost::mpl::is_sequence<StaticMask>::value
 907                 >::apply(matrix)
 908             || static_may_update_sequence
 909                 <
 910                     typename boost::mpl::next<First>::type,
 911                     Last,
 912                     D, F1, F2
 913                 >::apply(matrix);
 914     }
 915 };
 916
 917 template <typename Last, char D, field F1, field F2>
 918 struct static_may_update_sequence<Last, Last, D, F1, F2>
 919 {
 920     template <typename Matrix>
 921     static inline bool apply(Matrix const& /*matrix*/)
 922     {
 923         return false;
 924     }
 925 };
 926
 927 template <typename StaticMask, char D, field F1, field F2>
 928 struct static_may_update_dispatch<StaticMask, D, F1, F2, true>
 929 {
 930     template <typename Matrix>
 931     static inline bool apply(Matrix const& matrix)
 932     {
 933         return static_may_update_sequence
 934                 <
 935                     typename boost::mpl::begin<StaticMask>::type,
 936                     typename boost::mpl::end<StaticMask>::type,
 937                     D, F1, F2
 938                 >::apply(matrix);
 939     }
 940 };
 941
 942 template <typename StaticMask, char D, field F1, field F2>
 943 struct static_may_update
 944 {
 945     template <typename Matrix>
 946     static inline bool apply(Matrix const& matrix)
 947     {
 948         return static_may_update_dispatch
 949                 <
 950                     StaticMask,
 951                     D, F1, F2,
 952                     boost::mpl::is_sequence<StaticMask>::value
 953                 >::apply(matrix);
 954     }
 955 };
 956
 957 // static_check_matrix
 958
 959 template <typename StaticMask, bool IsSequence>
 960 struct static_check_dispatch
 961 {
 962     template <typename Matrix>
 963     static inline bool apply(Matrix const& matrix)
 964     {
 965         return per_one<interior, interior>::apply(matrix)
 966             && per_one<interior, boundary>::apply(matrix)
 967             && per_one<interior, exterior>::apply(matrix)
 968             && per_one<boundary, interior>::apply(matrix)
 969             && per_one<boundary, boundary>::apply(matrix)
 970             && per_one<boundary, exterior>::apply(matrix)
 971             && per_one<exterior, interior>::apply(matrix)
 972             && per_one<exterior, boundary>::apply(matrix)
 973             && per_one<exterior, exterior>::apply(matrix);
 974     }
 975
 976     template <field F1, field F2>
 977     struct per_one
 978     {
 979         static const char mask_el = StaticMask::template static_get<F1, F2>::value;
 980         static const int version
 981                             = mask_el == 'F' ? 0
 982                             : mask_el == 'T' ? 1
 983                             : mask_el >= '0' && mask_el <= '9' ? 2
 984                             : 3;
 985
 986         template <typename Matrix>
 987         static inline bool apply(Matrix const& matrix)
 988         {
 989             const char el = matrix.template get<F1, F2>();
 990             return apply_dispatch(el, integral_constant<int, version>());
 991         }
 992
 993         // mask_el == 'F'
 994         static inline bool apply_dispatch(char el, integral_constant<int, 0>)
 995         {
 996             return el == 'F';
 997         }
 998         // mask_el == 'T'
 999         static inline bool apply_dispatch(char el, integral_constant<int, 1>)
1000         {
1001             return el == 'T' || ( el >= '0' && el <= '9' );
1002         }
1003         // mask_el >= '0' && mask_el <= '9'
1004         static inline bool apply_dispatch(char el, integral_constant<int, 2>)
1005         {
1006             return el == mask_el;
1007         }
1008         // else
1009         static inline bool apply_dispatch(char /*el*/, integral_constant<int, 3>)
1010         {
1011             return true;
1012         }
1013     };
1014 };
1015
1016 template <typename First, typename Last>
1017 struct static_check_sequence
1018 {
1019     typedef typename boost::mpl::deref<First>::type StaticMask;
1020
1021     template <typename Matrix>
1022     static inline bool apply(Matrix const& matrix)
1023     {
1024         return static_check_dispatch
1025                 <
1026                     StaticMask,
1027                     boost::mpl::is_sequence<StaticMask>::value
1028                 >::apply(matrix)
1029             || static_check_sequence
1030                 <
1031                     typename boost::mpl::next<First>::type,
1032                     Last
1033                 >::apply(matrix);
1034     }
1035 };
1036
1037 template <typename Last>
1038 struct static_check_sequence<Last, Last>
1039 {
1040     template <typename Matrix>
1041     static inline bool apply(Matrix const& /*matrix*/)
1042     {
1043         return false;
1044     }
1045 };
1046
1047 template <typename StaticMask>
1048 struct static_check_dispatch<StaticMask, true>
1049 {
1050     template <typename Matrix>
1051     static inline bool apply(Matrix const& matrix)
1052     {
1053         return static_check_sequence
1054                 <
1055                     typename boost::mpl::begin<StaticMask>::type,
1056                     typename boost::mpl::end<StaticMask>::type
1057                 >::apply(matrix);
1058     }
1059 };
1060
1061 template <typename StaticMask>
1062 struct static_check_matrix
1063 {
1064     template <typename Matrix>
1065     static inline bool apply(Matrix const& matrix)
1066     {
1067         return static_check_dispatch
1068                 <
1069                     StaticMask,
1070                     boost::mpl::is_sequence<StaticMask>::value
1071                 >::apply(matrix);
1072     }
1073 };
1074
1075 // static_mask_handler
1076
1077 template <typename StaticMask, bool Interrupt>
1078 class static_mask_handler
1079     : private matrix_handler< matrix<3> >
1080 {
1081     typedef matrix_handler< relate::matrix<3> > base_type;
1082
1083 public:
1084     typedef bool result_type;
1085
1086     bool interrupt;
1087
1088     inline static_mask_handler()
1089         : interrupt(false)
1090     {}
1091
1092     inline explicit static_mask_handler(StaticMask const& /*dummy*/)
1093         : interrupt(false)
1094     {}
1095
1096     result_type result() const
1097     {
1098         return (!Interrupt || !interrupt)
1099             && static_check_matrix<StaticMask>::apply(base_type::matrix());
1100     }
1101
1102     template <field F1, field F2, char D>
1103     inline bool may_update() const
1104     {
1105         return static_may_update<StaticMask, D, F1, F2>::
1106                     apply(base_type::matrix());
1107     }
1108
1109     template <field F1, field F2>
1110     static inline bool expects()
1111     {
1112         return static_should_handle_element<StaticMask, F1, F2>::value;
1113     }
1114
1115     template <field F1, field F2, char V>
1116     inline void set()
1117     {
1118         static const bool interrupt_c = static_interrupt<StaticMask, V, F1, F2, Interrupt>::value;
1119         static const bool should_handle = static_should_handle_element<StaticMask, F1, F2>::value;
1120         static const int version = interrupt_c ? 0
1121                                  : should_handle ? 1
1122                                  : 2;
1123
1124         set_dispatch<F1, F2, V>(integral_constant<int, version>());
1125     }
1126
1127     template <field F1, field F2, char V>
1128     inline void update()
1129     {
1130         static const bool interrupt_c = static_interrupt<StaticMask, V, F1, F2, Interrupt>::value;
1131         static const bool should_handle = static_should_handle_element<StaticMask, F1, F2>::value;
1132         static const int version = interrupt_c ? 0
1133                                  : should_handle ? 1
1134                                  : 2;
1135
1136         update_dispatch<F1, F2, V>(integral_constant<int, version>());
1137     }
1138
1139 private:
1140     // Interrupt && interrupt
1141     template <field F1, field F2, char V>
1142     inline void set_dispatch(integral_constant<int, 0>)
1143     {
1144         interrupt = true;
1145     }
1146     // else should_handle
1147     template <field F1, field F2, char V>
1148     inline void set_dispatch(integral_constant<int, 1>)
1149     {
1150         base_type::template set<F1, F2, V>();
1151     }
1152     // else
1153     template <field F1, field F2, char V>
1154     inline void set_dispatch(integral_constant<int, 2>)
1155     {}
1156
1157     // Interrupt && interrupt
1158     template <field F1, field F2, char V>
1159     inline void update_dispatch(integral_constant<int, 0>)
1160     {
1161         interrupt = true;
1162     }
1163     // else should_handle
1164     template <field F1, field F2, char V>
1165     inline void update_dispatch(integral_constant<int, 1>)
1166     {
1167         base_type::template update<F1, F2, V>();
1168     }
1169     // else
1170     template <field F1, field F2, char V>
1171     inline void update_dispatch(integral_constant<int, 2>)
1172     {}
1173 };
1174
1175 // --------------- UTIL FUNCTIONS ----------------
1176
1177 // set
1178
1179 template <field F1, field F2, char V, typename Result>
1180 inline void set(Result & res)
1181 {
1182     res.template set<F1, F2, V>();
1183 }
1184
1185 template <field F1, field F2, char V, bool Transpose>
1186 struct set_dispatch
1187 {
1188     template <typename Result>
1189     static inline void apply(Result & res)
1190     {
1191         res.template set<F1, F2, V>();
1192     }
1193 };
1194
1195 template <field F1, field F2, char V>
1196 struct set_dispatch<F1, F2, V, true>
1197 {
1198     template <typename Result>
1199     static inline void apply(Result & res)
1200     {
1201         res.template set<F2, F1, V>();
1202     }
1203 };
1204
1205 template <field F1, field F2, char V, bool Transpose, typename Result>
1206 inline void set(Result & res)
1207 {
1208     set_dispatch<F1, F2, V, Transpose>::apply(res);
1209 }
1210
1211 // update
1212
1213 template <field F1, field F2, char D, typename Result>
1214 inline void update(Result & res)
1215 {
1216     res.template update<F1, F2, D>();
1217 }
1218
1219 template <field F1, field F2, char D, bool Transpose>
1220 struct update_result_dispatch
1221 {
1222     template <typename Result>
1223     static inline void apply(Result & res)
1224     {
1225         update<F1, F2, D>(res);
1226     }
1227 };
1228
1229 template <field F1, field F2, char D>
1230 struct update_result_dispatch<F1, F2, D, true>
1231 {
1232     template <typename Result>
1233     static inline void apply(Result & res)
1234     {
1235         update<F2, F1, D>(res);
1236     }
1237 };
1238
1239 template <field F1, field F2, char D, bool Transpose, typename Result>
1240 inline void update(Result & res)
1241 {
1242     update_result_dispatch<F1, F2, D, Transpose>::apply(res);
1243 }
1244
1245 // may_update
1246
1247 template <field F1, field F2, char D, typename Result>
1248 inline bool may_update(Result const& res)
1249 {
1250     return res.template may_update<F1, F2, D>();
1251 }
1252
1253 template <field F1, field F2, char D, bool Transpose>
1254 struct may_update_result_dispatch
1255 {
1256     template <typename Result>
1257     static inline bool apply(Result const& res)
1258     {
1259         return may_update<F1, F2, D>(res);
1260     }
1261 };
1262
1263 template <field F1, field F2, char D>
1264 struct may_update_result_dispatch<F1, F2, D, true>
1265 {
1266     template <typename Result>
1267     static inline bool apply(Result const& res)
1268     {
1269         return may_update<F2, F1, D>(res);
1270     }
1271 };
1272
1273 template <field F1, field F2, char D, bool Transpose, typename Result>
1274 inline bool may_update(Result const& res)
1275 {
1276     return may_update_result_dispatch<F1, F2, D, Transpose>::apply(res);
1277 }
1278
1279 // result_dimension
1280
1281 template <typename Geometry>
1282 struct result_dimension
1283 {
1284     BOOST_STATIC_ASSERT(geometry::dimension<Geometry>::value >= 0);
1285     static const char value
1286         = ( geometry::dimension<Geometry>::value <= 9 ) ?
1287             ( '0' + geometry::dimension<Geometry>::value ) :
1288               'T';
1289 };
1290
1291 }} // namespace detail::relate
1292 #endif // DOXYGEN_NO_DETAIL
1293
1294 }} // namespace boost::geometry
1295
1296 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_RESULT_HPP