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