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

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