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