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