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-2018.
   7 // Modifications copyright (c) 2013-2018 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 // --------------- COMPILE-TIME MASK ----------------
 658
 659 // static_check_characters
 660 template
 661 <
 662     typename Seq,
 663     typename First = typename boost::mpl::begin<Seq>::type,
 664     typename Last = typename boost::mpl::end<Seq>::type
 665 >
 666 struct static_check_characters
 667     : static_check_characters
 668         <
 669             Seq,
 670             typename boost::mpl::next<First>::type
 671         >
 672 {
 673     typedef typename boost::mpl::deref<First>::type type;
 674     static const char value = type::value;
 675     static const bool is_valid = (value >= '0' && value <= '9')
 676                                || value == 'T' || value == 'F' || value == '*';
 677     BOOST_MPL_ASSERT_MSG((is_valid),
 678                          INVALID_STATIC_MASK_CHARACTER,
 679                          (type));
 680 };
 681
 682 template <typename Seq, typename Last>
 683 struct static_check_characters<Seq, Last, Last>
 684 {};
 685
 686 // static_mask
 687
 688 template
 689 <
 690     typename Seq,
 691     std::size_t Height,
 692     std::size_t Width = Height
 693 >
 694 struct static_mask
 695 {
 696     static const std::size_t static_width = Width;
 697     static const std::size_t static_height = Height;
 698     static const std::size_t static_size = Width * Height;
 699
 700     BOOST_STATIC_ASSERT(
 701         std::size_t(boost::mpl::size<Seq>::type::value) == static_size);
 702
 703     template <detail::relate::field F1, detail::relate::field F2>
 704     struct static_get
 705     {
 706         BOOST_STATIC_ASSERT(std::size_t(F1) < static_height);
 707         BOOST_STATIC_ASSERT(std::size_t(F2) < static_width);
 708
 709         static const char value
 710             = boost::mpl::at_c<Seq, F1 * static_width + F2>::type::value;
 711     };
 712
 713 private:
 714     // check static_mask characters
 715     enum { mask_check = sizeof(static_check_characters<Seq>) };
 716 };
 717
 718 // static_should_handle_element
 719
 720 template <typename StaticMask, field F1, field F2, bool IsSequence>
 721 struct static_should_handle_element_dispatch
 722 {
 723     static const char mask_el = StaticMask::template static_get<F1, F2>::value;
 724     static const bool value = mask_el == 'F'
 725                            || mask_el == 'T'
 726                            || ( mask_el >= '0' && mask_el <= '9' );
 727 };
 728
 729 template <typename First, typename Last, field F1, field F2>
 730 struct static_should_handle_element_sequence
 731 {
 732     typedef typename boost::mpl::deref<First>::type StaticMask;
 733
 734     static const bool value
 735         = static_should_handle_element_dispatch
 736             <
 737                 StaticMask,
 738                 F1, F2,
 739                 boost::mpl::is_sequence<StaticMask>::value
 740             >::value
 741        || static_should_handle_element_sequence
 742             <
 743                 typename boost::mpl::next<First>::type,
 744                 Last,
 745                 F1, F2
 746             >::value;
 747 };
 748
 749 template <typename Last, field F1, field F2>
 750 struct static_should_handle_element_sequence<Last, Last, F1, F2>
 751 {
 752     static const bool value = false;
 753 };
 754
 755 template <typename StaticMask, field F1, field F2>
 756 struct static_should_handle_element_dispatch<StaticMask, F1, F2, true>
 757 {
 758     static const bool value
 759         = static_should_handle_element_sequence
 760             <
 761                 typename boost::mpl::begin<StaticMask>::type,
 762                 typename boost::mpl::end<StaticMask>::type,
 763                 F1, F2
 764             >::value;
 765 };
 766
 767 template <typename StaticMask, field F1, field F2>
 768 struct static_should_handle_element
 769 {
 770     static const bool value
 771         = static_should_handle_element_dispatch
 772             <
 773                 StaticMask,
 774                 F1, F2,
 775                 boost::mpl::is_sequence<StaticMask>::value
 776             >::value;
 777 };
 778
 779 // static_interrupt
 780
 781 template <typename StaticMask, char V, field F1, field F2, bool InterruptEnabled, bool IsSequence>
 782 struct static_interrupt_dispatch
 783 {
 784     static const bool value = false;
 785 };
 786
 787 template <typename StaticMask, char V, field F1, field F2, bool IsSequence>
 788 struct static_interrupt_dispatch<StaticMask, V, F1, F2, true, IsSequence>
 789 {
 790     static const char mask_el = StaticMask::template static_get<F1, F2>::value;
 791
 792     static const bool value
 793         = ( V >= '0' && V <= '9' ) ?
 794           ( mask_el == 'F' || ( mask_el < V && mask_el >= '0' && mask_el <= '9' ) ) :
 795           ( ( V == 'T' ) ? mask_el == 'F' : false );
 796 };
 797
 798 template <typename First, typename Last, char V, field F1, field F2>
 799 struct static_interrupt_sequence
 800 {
 801     typedef typename boost::mpl::deref<First>::type StaticMask;
 802
 803     static const bool value
 804         = static_interrupt_dispatch
 805             <
 806                 StaticMask,
 807                 V, F1, F2,
 808                 true,
 809                 boost::mpl::is_sequence<StaticMask>::value
 810             >::value
 811        && static_interrupt_sequence
 812             <
 813                 typename boost::mpl::next<First>::type,
 814                 Last,
 815                 V, F1, F2
 816             >::value;
 817 };
 818
 819 template <typename Last, char V, field F1, field F2>
 820 struct static_interrupt_sequence<Last, Last, V, F1, F2>
 821 {
 822     static const bool value = true;
 823 };
 824
 825 template <typename StaticMask, char V, field F1, field F2>
 826 struct static_interrupt_dispatch<StaticMask, V, F1, F2, true, true>
 827 {
 828     static const bool value
 829         = static_interrupt_sequence
 830             <
 831                 typename boost::mpl::begin<StaticMask>::type,
 832                 typename boost::mpl::end<StaticMask>::type,
 833                 V, F1, F2
 834             >::value;
 835 };
 836
 837 template <typename StaticMask, char V, field F1, field F2, bool EnableInterrupt>
 838 struct static_interrupt
 839 {
 840     static const bool value
 841         = static_interrupt_dispatch
 842             <
 843                 StaticMask,
 844                 V, F1, F2,
 845                 EnableInterrupt,
 846                 boost::mpl::is_sequence<StaticMask>::value
 847             >::value;
 848 };
 849
 850 // static_may_update
 851
 852 template <typename StaticMask, char D, field F1, field F2, bool IsSequence>
 853 struct static_may_update_dispatch
 854 {
 855     static const char mask_el = StaticMask::template static_get<F1, F2>::value;
 856     static const int version
 857                         = mask_el == 'F' ? 0
 858                         : mask_el == 'T' ? 1
 859                         : mask_el >= '0' && mask_el <= '9' ? 2
 860                         : 3;
 861
 862     template <typename Matrix>
 863     static inline bool apply(Matrix const& matrix)
 864     {
 865         return apply_dispatch(matrix, integral_constant<int, version>());
 866     }
 867
 868     // mask_el == 'F'
 869     template <typename Matrix>
 870     static inline bool apply_dispatch(Matrix const& , integral_constant<int, 0>)
 871     {
 872         return true;
 873     }
 874     // mask_el == 'T'
 875     template <typename Matrix>
 876     static inline bool apply_dispatch(Matrix const& matrix, integral_constant<int, 1>)
 877     {
 878         char const c = matrix.template get<F1, F2>();
 879         return c == 'F'; // if it's T or between 0 and 9, the result will be the same
 880     }
 881     // mask_el >= '0' && mask_el <= '9'
 882     template <typename Matrix>
 883     static inline bool apply_dispatch(Matrix const& matrix, integral_constant<int, 2>)
 884     {
 885         char const c = matrix.template get<F1, F2>();
 886         return D > c || c > '9';
 887     }
 888     // else
 889     template <typename Matrix>
 890     static inline bool apply_dispatch(Matrix const&, integral_constant<int, 3>)
 891     {
 892         return false;
 893     }
 894 };
 895
 896 template <typename First, typename Last, char D, field F1, field F2>
 897 struct static_may_update_sequence
 898 {
 899     typedef typename boost::mpl::deref<First>::type StaticMask;
 900
 901     template <typename Matrix>
 902     static inline bool apply(Matrix const& matrix)
 903     {
 904         return static_may_update_dispatch
 905                 <
 906                     StaticMask,
 907                     D, F1, F2,
 908                     boost::mpl::is_sequence<StaticMask>::value
 909                 >::apply(matrix)
 910             || static_may_update_sequence
 911                 <
 912                     typename boost::mpl::next<First>::type,
 913                     Last,
 914                     D, F1, F2
 915                 >::apply(matrix);
 916     }
 917 };
 918
 919 template <typename Last, char D, field F1, field F2>
 920 struct static_may_update_sequence<Last, Last, D, F1, F2>
 921 {
 922     template <typename Matrix>
 923     static inline bool apply(Matrix const& /*matrix*/)
 924     {
 925         return false;
 926     }
 927 };
 928
 929 template <typename StaticMask, char D, field F1, field F2>
 930 struct static_may_update_dispatch<StaticMask, D, F1, F2, true>
 931 {
 932     template <typename Matrix>
 933     static inline bool apply(Matrix const& matrix)
 934     {
 935         return static_may_update_sequence
 936                 <
 937                     typename boost::mpl::begin<StaticMask>::type,
 938                     typename boost::mpl::end<StaticMask>::type,
 939                     D, F1, F2
 940                 >::apply(matrix);
 941     }
 942 };
 943
 944 template <typename StaticMask, char D, field F1, field F2>
 945 struct static_may_update
 946 {
 947     template <typename Matrix>
 948     static inline bool apply(Matrix const& matrix)
 949     {
 950         return static_may_update_dispatch
 951                 <
 952                     StaticMask,
 953                     D, F1, F2,
 954                     boost::mpl::is_sequence<StaticMask>::value
 955                 >::apply(matrix);
 956     }
 957 };
 958
 959 // static_check_matrix
 960
 961 template <typename StaticMask, bool IsSequence>
 962 struct static_check_dispatch
 963 {
 964     template <typename Matrix>
 965     static inline bool apply(Matrix const& matrix)
 966     {
 967         return per_one<interior, interior>::apply(matrix)
 968             && per_one<interior, boundary>::apply(matrix)
 969             && per_one<interior, exterior>::apply(matrix)
 970             && per_one<boundary, interior>::apply(matrix)
 971             && per_one<boundary, boundary>::apply(matrix)
 972             && per_one<boundary, exterior>::apply(matrix)
 973             && per_one<exterior, interior>::apply(matrix)
 974             && per_one<exterior, boundary>::apply(matrix)
 975             && per_one<exterior, exterior>::apply(matrix);
 976     }
 977
 978     template <field F1, field F2>
 979     struct per_one
 980     {
 981         static const char mask_el = StaticMask::template static_get<F1, F2>::value;
 982         static const int version
 983                             = mask_el == 'F' ? 0
 984                             : mask_el == 'T' ? 1
 985                             : mask_el >= '0' && mask_el <= '9' ? 2
 986                             : 3;
 987
 988         template <typename Matrix>
 989         static inline bool apply(Matrix const& matrix)
 990         {
 991             const char el = matrix.template get<F1, F2>();
 992             return apply_dispatch(el, integral_constant<int, version>());
 993         }
 994
 995         // mask_el == 'F'
 996         static inline bool apply_dispatch(char el, integral_constant<int, 0>)
 997         {
 998             return el == 'F';
 999         }
1000         // mask_el == 'T'
1001         static inline bool apply_dispatch(char el, integral_constant<int, 1>)
1002         {
1003             return el == 'T' || ( el >= '0' && el <= '9' );
1004         }
1005         // mask_el >= '0' && mask_el <= '9'
1006         static inline bool apply_dispatch(char el, integral_constant<int, 2>)
1007         {
1008             return el == mask_el;
1009         }
1010         // else
1011         static inline bool apply_dispatch(char /*el*/, integral_constant<int, 3>)
1012         {
1013             return true;
1014         }
1015     };
1016 };
1017
1018 template <typename First, typename Last>
1019 struct static_check_sequence
1020 {
1021     typedef typename boost::mpl::deref<First>::type StaticMask;
1022
1023     template <typename Matrix>
1024     static inline bool apply(Matrix const& matrix)
1025     {
1026         return static_check_dispatch
1027                 <
1028                     StaticMask,
1029                     boost::mpl::is_sequence<StaticMask>::value
1030                 >::apply(matrix)
1031             || static_check_sequence
1032                 <
1033                     typename boost::mpl::next<First>::type,
1034                     Last
1035                 >::apply(matrix);
1036     }
1037 };
1038
1039 template <typename Last>
1040 struct static_check_sequence<Last, Last>
1041 {
1042     template <typename Matrix>
1043     static inline bool apply(Matrix const& /*matrix*/)
1044     {
1045         return false;
1046     }
1047 };
1048
1049 template <typename StaticMask>
1050 struct static_check_dispatch<StaticMask, true>
1051 {
1052     template <typename Matrix>
1053     static inline bool apply(Matrix const& matrix)
1054     {
1055         return static_check_sequence
1056                 <
1057                     typename boost::mpl::begin<StaticMask>::type,
1058                     typename boost::mpl::end<StaticMask>::type
1059                 >::apply(matrix);
1060     }
1061 };
1062
1063 template <typename StaticMask>
1064 struct static_check_matrix
1065 {
1066     template <typename Matrix>
1067     static inline bool apply(Matrix const& matrix)
1068     {
1069         return static_check_dispatch
1070                 <
1071                     StaticMask,
1072                     boost::mpl::is_sequence<StaticMask>::value
1073                 >::apply(matrix);
1074     }
1075 };
1076
1077 // static_mask_handler
1078
1079 template <typename StaticMask, bool Interrupt>
1080 class static_mask_handler
1081     : private matrix_handler< matrix<3> >
1082 {
1083     typedef matrix_handler< relate::matrix<3> > base_type;
1084
1085 public:
1086     typedef bool result_type;
1087
1088     bool interrupt;
1089
1090     inline static_mask_handler()
1091         : interrupt(false)
1092     {}
1093
1094     inline explicit static_mask_handler(StaticMask const& /*dummy*/)
1095         : interrupt(false)
1096     {}
1097
1098     result_type result() const
1099     {
1100         return (!Interrupt || !interrupt)
1101             && static_check_matrix<StaticMask>::apply(base_type::matrix());
1102     }
1103
1104     template <field F1, field F2, char D>
1105     inline bool may_update() const
1106     {
1107         return static_may_update<StaticMask, D, F1, F2>::
1108                     apply(base_type::matrix());
1109     }
1110
1111     template <field F1, field F2>
1112     static inline bool expects()
1113     {
1114         return static_should_handle_element<StaticMask, F1, F2>::value;
1115     }
1116
1117     template <field F1, field F2, char V>
1118     inline void set()
1119     {
1120         static const bool interrupt_c = static_interrupt<StaticMask, V, F1, F2, Interrupt>::value;
1121         static const bool should_handle = static_should_handle_element<StaticMask, F1, F2>::value;
1122         static const int version = interrupt_c ? 0
1123                                  : should_handle ? 1
1124                                  : 2;
1125
1126         set_dispatch<F1, F2, V>(integral_constant<int, version>());
1127     }
1128
1129     template <field F1, field F2, char V>
1130     inline void update()
1131     {
1132         static const bool interrupt_c = static_interrupt<StaticMask, V, F1, F2, Interrupt>::value;
1133         static const bool should_handle = static_should_handle_element<StaticMask, F1, F2>::value;
1134         static const int version = interrupt_c ? 0
1135                                  : should_handle ? 1
1136                                  : 2;
1137
1138         update_dispatch<F1, F2, V>(integral_constant<int, version>());
1139     }
1140
1141 private:
1142     // Interrupt && interrupt
1143     template <field F1, field F2, char V>
1144     inline void set_dispatch(integral_constant<int, 0>)
1145     {
1146         interrupt = true;
1147     }
1148     // else should_handle
1149     template <field F1, field F2, char V>
1150     inline void set_dispatch(integral_constant<int, 1>)
1151     {
1152         base_type::template set<F1, F2, V>();
1153     }
1154     // else
1155     template <field F1, field F2, char V>
1156     inline void set_dispatch(integral_constant<int, 2>)
1157     {}
1158
1159     // Interrupt && interrupt
1160     template <field F1, field F2, char V>
1161     inline void update_dispatch(integral_constant<int, 0>)
1162     {
1163         interrupt = true;
1164     }
1165     // else should_handle
1166     template <field F1, field F2, char V>
1167     inline void update_dispatch(integral_constant<int, 1>)
1168     {
1169         base_type::template update<F1, F2, V>();
1170     }
1171     // else
1172     template <field F1, field F2, char V>
1173     inline void update_dispatch(integral_constant<int, 2>)
1174     {}
1175 };
1176
1177 // --------------- UTIL FUNCTIONS ----------------
1178
1179 // set
1180
1181 template <field F1, field F2, char V, typename Result>
1182 inline void set(Result & res)
1183 {
1184     res.template set<F1, F2, V>();
1185 }
1186
1187 template <field F1, field F2, char V, bool Transpose>
1188 struct set_dispatch
1189 {
1190     template <typename Result>
1191     static inline void apply(Result & res)
1192     {
1193         res.template set<F1, F2, V>();
1194     }
1195 };
1196
1197 template <field F1, field F2, char V>
1198 struct set_dispatch<F1, F2, V, true>
1199 {
1200     template <typename Result>
1201     static inline void apply(Result & res)
1202     {
1203         res.template set<F2, F1, V>();
1204     }
1205 };
1206
1207 template <field F1, field F2, char V, bool Transpose, typename Result>
1208 inline void set(Result & res)
1209 {
1210     set_dispatch<F1, F2, V, Transpose>::apply(res);
1211 }
1212
1213 // update
1214
1215 template <field F1, field F2, char D, typename Result>
1216 inline void update(Result & res)
1217 {
1218     res.template update<F1, F2, D>();
1219 }
1220
1221 template <field F1, field F2, char D, bool Transpose>
1222 struct update_result_dispatch
1223 {
1224     template <typename Result>
1225     static inline void apply(Result & res)
1226     {
1227         update<F1, F2, D>(res);
1228     }
1229 };
1230
1231 template <field F1, field F2, char D>
1232 struct update_result_dispatch<F1, F2, D, true>
1233 {
1234     template <typename Result>
1235     static inline void apply(Result & res)
1236     {
1237         update<F2, F1, D>(res);
1238     }
1239 };
1240
1241 template <field F1, field F2, char D, bool Transpose, typename Result>
1242 inline void update(Result & res)
1243 {
1244     update_result_dispatch<F1, F2, D, Transpose>::apply(res);
1245 }
1246
1247 // may_update
1248
1249 template <field F1, field F2, char D, typename Result>
1250 inline bool may_update(Result const& res)
1251 {
1252     return res.template may_update<F1, F2, D>();
1253 }
1254
1255 template <field F1, field F2, char D, bool Transpose>
1256 struct may_update_result_dispatch
1257 {
1258     template <typename Result>
1259     static inline bool apply(Result const& res)
1260     {
1261         return may_update<F1, F2, D>(res);
1262     }
1263 };
1264
1265 template <field F1, field F2, char D>
1266 struct may_update_result_dispatch<F1, F2, D, true>
1267 {
1268     template <typename Result>
1269     static inline bool apply(Result const& res)
1270     {
1271         return may_update<F2, F1, D>(res);
1272     }
1273 };
1274
1275 template <field F1, field F2, char D, bool Transpose, typename Result>
1276 inline bool may_update(Result const& res)
1277 {
1278     return may_update_result_dispatch<F1, F2, D, Transpose>::apply(res);
1279 }
1280
1281 // result_dimension
1282
1283 template <typename Geometry>
1284 struct result_dimension
1285 {
1286     BOOST_STATIC_ASSERT(geometry::dimension<Geometry>::value >= 0);
1287     static const char value
1288         = ( geometry::dimension<Geometry>::value <= 9 ) ?
1289             ( '0' + geometry::dimension<Geometry>::value ) :
1290               'T';
1291 };
1292
1293 }} // namespace detail::relate
1294 #endif // DOXYGEN_NO_DETAIL
1295
1296 }} // namespace boost::geometry
1297
1298 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_RESULT_HPP