detail/relate/result.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
0004 // Copyright (c) 2017-2023 Adam Wulkiewicz, Lodz, Poland.
0005
0006 // This file was modified by Oracle on 2013-2022.
0007 // Modifications copyright (c) 2013-2022 Oracle and/or its affiliates.
0008 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0009
0010 // Use, modification and distribution is subject to the Boost Software License,
0011 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0012 // http://www.boost.org/LICENSE_1_0.txt)
0013
0014 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_RESULT_HPP
0015 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_RESULT_HPP
0016
0017 #include <algorithm>
0018 #include <cstddef>
0019 #include <cstring>
0020 #include <string>
0021 #include <tuple>
0022 #include <type_traits>
0023
0024 #include <boost/throw_exception.hpp>
0025
0026 #include <boost/geometry/core/assert.hpp>
0027 #include <boost/geometry/core/coordinate_dimension.hpp>
0028 #include <boost/geometry/core/exception.hpp>
0029 #include <boost/geometry/core/static_assert.hpp>
0030 #include <boost/geometry/util/condition.hpp>
0031 #include <boost/geometry/util/sequence.hpp>
0032
0033 namespace boost { namespace geometry {
0034
0035 #ifndef DOXYGEN_NO_DETAIL
0036 namespace detail { namespace relate {
0037
0038 enum field { interior = 0, boundary = 1, exterior = 2 };
0039
0040 // TODO: IF THE RESULT IS UPDATED WITH THE MAX POSSIBLE VALUE FOR SOME PAIR OF GEOEMTRIES
0041 // THE VALUE ALREADY STORED MUSN'T BE CHECKED
0042 // update() calls chould be replaced with set() in those cases
0043 // but for safety reasons (STATIC_ASSERT) we should check if parameter D is valid and set() doesn't do that
0044 // so some additional function could be added, e.g. set_dim()
0045
0046
0047 template <typename MatrixOrMask, field F1, field F2>
0048 using fields_in_bounds = util::bool_constant
0049     <
0050         (F1 < MatrixOrMask::static_height && F2 < MatrixOrMask::static_width)
0051     >;
0052
0053 // --------------- MATRIX ----------------
0054
0055 // matrix
0056
0057 template <std::size_t Height, std::size_t Width = Height>
0058 class matrix
0059 {
0060 public:
0061     typedef char value_type;
0062     typedef std::size_t size_type;
0063     typedef const char * const_iterator;
0064     typedef const_iterator iterator;
0065
0066     static const std::size_t static_width = Width;
0067     static const std::size_t static_height = Height;
0068     static const std::size_t static_size = Width * Height;
0069
0070     inline matrix()
0071     {
0072         std::fill_n(m_array, static_size, 'F');
0073     }
0074
0075     template
0076     <
0077         field F1, field F2,
0078         std::enable_if_t<fields_in_bounds<matrix, F1, F2>::value, int> = 0
0079     >
0080     inline char get() const
0081     {
0082         static const std::size_t index = F1 * Width + F2;
0083         BOOST_STATIC_ASSERT(index < static_size);
0084         return m_array[index];
0085     }
0086
0087     template
0088     <
0089         field F1, field F2, char V,
0090         std::enable_if_t<fields_in_bounds<matrix, F1, F2>::value, int> = 0
0091     >
0092     inline void set()
0093     {
0094         static const std::size_t index = F1 * Width + F2;
0095         BOOST_STATIC_ASSERT(index < static_size);
0096         m_array[index] = V;
0097     }
0098
0099     inline char operator[](std::size_t index) const
0100     {
0101         BOOST_GEOMETRY_ASSERT(index < static_size);
0102         return m_array[index];
0103     }
0104
0105     inline const_iterator begin() const
0106     {
0107         return m_array;
0108     }
0109
0110     inline const_iterator end() const
0111     {
0112         return m_array + static_size;
0113     }
0114
0115     inline static std::size_t size()
0116     {
0117         return static_size;
0118     }
0119
0120     inline const char * data() const
0121     {
0122         return m_array;
0123     }
0124
0125     inline std::string str() const
0126     {
0127         return std::string(m_array, static_size);
0128     }
0129
0130 private:
0131     char m_array[static_size];
0132 };
0133
0134 // matrix_handler
0135
0136 template <typename Matrix>
0137 class matrix_handler
0138 {
0139 public:
0140     typedef Matrix result_type;
0141
0142     static const bool interrupt = false;
0143
0144     matrix_handler()
0145     {}
0146
0147     result_type const& result() const
0148     {
0149         return m_matrix;
0150     }
0151
0152     result_type const& matrix() const
0153     {
0154         return m_matrix;
0155     }
0156
0157     result_type & matrix()
0158     {
0159         return m_matrix;
0160     }
0161
0162     template <field F1, field F2, char D>
0163     inline bool may_update() const
0164     {
0165         BOOST_STATIC_ASSERT('0' <= D && D <= '9');
0166         char const c = m_matrix.template get<F1, F2>();
0167         return D > c || c > '9';
0168     }
0169
0170     template <field F1, field F2, char V>
0171     inline void update()
0172     {
0173         BOOST_STATIC_ASSERT(('0' <= V && V <= '9') || V == 'T');
0174         char const c = m_matrix.template get<F1, F2>();
0175         // If c == T and V == T it will be set anyway but that's fine
0176         if (V > c || c > '9')
0177         {
0178             m_matrix.template set<F1, F2, V>();
0179         }
0180     }
0181
0182     template <field F1, field F2, char V>
0183     inline void set()
0184     {
0185         BOOST_STATIC_ASSERT(('0' <= V && V <= '9') || V == 'T');
0186         m_matrix.template set<F1, F2, V>();
0187     }
0188
0189     template <field F1, field F2>
0190     inline char get() const
0191     {
0192         return m_matrix.template get<F1, F2>();
0193     }
0194
0195 private:
0196     Matrix m_matrix;
0197 };
0198
0199 // --------------- RUN-TIME MASK ----------------
0200
0201 // run-time mask
0202
0203 template <std::size_t Height, std::size_t Width = Height>
0204 class mask
0205 {
0206 public:
0207     static const std::size_t static_width = Width;
0208     static const std::size_t static_height = Height;
0209     static const std::size_t static_size = Width * Height;
0210
0211     inline mask(const char * s)
0212     {
0213         char * it = m_array;
0214         char * const last = m_array + static_size;
0215         for ( ; it != last && *s != '\0' ; ++it, ++s )
0216         {
0217             char c = *s;
0218             check_char(c);
0219             *it = c;
0220         }
0221         if ( it != last )
0222         {
0223             std::fill(it, last, '*');
0224         }
0225     }
0226
0227     inline mask(const char * s, std::size_t count)
0228     {
0229         if ( count > static_size )
0230         {
0231             count = static_size;
0232         }
0233         if ( count > 0 )
0234         {
0235             std::for_each(s, s + count, check_char);
0236             std::copy_n(s, count, m_array);
0237         }
0238         if ( count < static_size )
0239         {
0240             std::fill_n(m_array + count, static_size - count, '*');
0241         }
0242     }
0243
0244     template
0245     <
0246         field F1, field F2,
0247         std::enable_if_t<fields_in_bounds<mask, F1, F2>::value, int> = 0
0248     >
0249     inline char get() const
0250     {
0251         static const std::size_t index = F1 * Width + F2;
0252         BOOST_STATIC_ASSERT(index < static_size);
0253         return m_array[index];
0254     }
0255
0256 private:
0257     static inline void check_char(char c)
0258     {
0259         bool const is_valid = c == '*' || c == 'T' || c == 'F'
0260                          || ( c >= '0' && c <= '9' );
0261         if ( !is_valid )
0262         {
0263             BOOST_THROW_EXCEPTION(geometry::invalid_input_exception());
0264         }
0265     }
0266
0267     char m_array[static_size];
0268 };
0269
0270 // interrupt()
0271
0272 template <typename Mask, bool InterruptEnabled>
0273 struct interrupt_dispatch
0274 {
0275     template <field F1, field F2, char V>
0276     static inline bool apply(Mask const&)
0277     {
0278         return false;
0279     }
0280 };
0281
0282 template <typename Mask>
0283 struct interrupt_dispatch<Mask, true>
0284 {
0285     template <field F1, field F2, char V>
0286     static inline bool apply(Mask const& mask)
0287     {
0288         char m = mask.template get<F1, F2>();
0289         return check_element<V>(m);
0290     }
0291
0292     template <char V>
0293     static inline bool check_element(char m)
0294     {
0295         if ( BOOST_GEOMETRY_CONDITION(V >= '0' && V <= '9') )
0296         {
0297             return m == 'F' || ( m < V && m >= '0' && m <= '9' );
0298         }
0299         else if ( BOOST_GEOMETRY_CONDITION(V == 'T') )
0300         {
0301             return m == 'F';
0302         }
0303         return false;
0304     }
0305 };
0306
0307 template <typename Masks, int I = 0, int N = std::tuple_size<Masks>::value>
0308 struct interrupt_dispatch_tuple
0309 {
0310     template <field F1, field F2, char V>
0311     static inline bool apply(Masks const& masks)
0312     {
0313         typedef typename std::tuple_element<I, Masks>::type mask_type;
0314         mask_type const& mask = std::get<I>(masks);
0315         return interrupt_dispatch<mask_type, true>::template apply<F1, F2, V>(mask)
0316             && interrupt_dispatch_tuple<Masks, I+1>::template apply<F1, F2, V>(masks);
0317     }
0318 };
0319
0320 template <typename Masks, int N>
0321 struct interrupt_dispatch_tuple<Masks, N, N>
0322 {
0323     template <field F1, field F2, char V>
0324     static inline bool apply(Masks const& )
0325     {
0326         return true;
0327     }
0328 };
0329
0330 template <typename ...Masks>
0331 struct interrupt_dispatch<std::tuple<Masks...>, true>
0332 {
0333     typedef std::tuple<Masks...> mask_type;
0334
0335     template <field F1, field F2, char V>
0336     static inline bool apply(mask_type const& mask)
0337     {
0338         return interrupt_dispatch_tuple<mask_type>::template apply<F1, F2, V>(mask);
0339     }
0340 };
0341
0342 template <field F1, field F2, char V, bool InterruptEnabled, typename Mask>
0343 inline bool interrupt(Mask const& mask)
0344 {
0345     return interrupt_dispatch<Mask, InterruptEnabled>
0346                 ::template apply<F1, F2, V>(mask);
0347 }
0348
0349 // may_update()
0350
0351 template <typename Mask>
0352 struct may_update_dispatch
0353 {
0354     template <field F1, field F2, char D, typename Matrix>
0355     static inline bool apply(Mask const& mask, Matrix const& matrix)
0356     {
0357         BOOST_STATIC_ASSERT('0' <= D && D <= '9');
0358
0359         char const m = mask.template get<F1, F2>();
0360
0361         if ( m == 'F' )
0362         {
0363             return true;
0364         }
0365         else if ( m == 'T' )
0366         {
0367             char const c = matrix.template get<F1, F2>();
0368             return c == 'F'; // if it's T or between 0 and 9, the result will be the same
0369         }
0370         else if ( m >= '0' && m <= '9' )
0371         {
0372             char const c = matrix.template get<F1, F2>();
0373             return D > c || c > '9';
0374         }
0375
0376         return false;
0377     }
0378 };
0379
0380 template <typename Masks, int I = 0, int N = std::tuple_size<Masks>::value>
0381 struct may_update_dispatch_tuple
0382 {
0383     template <field F1, field F2, char D, typename Matrix>
0384     static inline bool apply(Masks const& masks, Matrix const& matrix)
0385     {
0386         typedef typename std::tuple_element<I, Masks>::type mask_type;
0387         mask_type const& mask = std::get<I>(masks);
0388         return may_update_dispatch<mask_type>::template apply<F1, F2, D>(mask, matrix)
0389             || may_update_dispatch_tuple<Masks, I+1>::template apply<F1, F2, D>(masks, matrix);
0390     }
0391 };
0392
0393 template <typename Masks, int N>
0394 struct may_update_dispatch_tuple<Masks, N, N>
0395 {
0396     template <field F1, field F2, char D, typename Matrix>
0397     static inline bool apply(Masks const& , Matrix const& )
0398     {
0399         return false;
0400     }
0401 };
0402
0403 template <typename ...Masks>
0404 struct may_update_dispatch<std::tuple<Masks...>>
0405 {
0406     typedef std::tuple<Masks...> mask_type;
0407
0408     template <field F1, field F2, char D, typename Matrix>
0409     static inline bool apply(mask_type const& mask, Matrix const& matrix)
0410     {
0411         return may_update_dispatch_tuple<mask_type>::template apply<F1, F2, D>(mask, matrix);
0412     }
0413 };
0414
0415 template <field F1, field F2, char D, typename Mask, typename Matrix>
0416 inline bool may_update(Mask const& mask, Matrix const& matrix)
0417 {
0418     return may_update_dispatch<Mask>
0419                 ::template apply<F1, F2, D>(mask, matrix);
0420 }
0421
0422 // check_matrix()
0423
0424 template <typename Mask>
0425 struct check_dispatch
0426 {
0427     template <typename Matrix>
0428     static inline bool apply(Mask const& mask, Matrix const& matrix)
0429     {
0430         return per_one<interior, interior>(mask, matrix)
0431             && per_one<interior, boundary>(mask, matrix)
0432             && per_one<interior, exterior>(mask, matrix)
0433             && per_one<boundary, interior>(mask, matrix)
0434             && per_one<boundary, boundary>(mask, matrix)
0435             && per_one<boundary, exterior>(mask, matrix)
0436             && per_one<exterior, interior>(mask, matrix)
0437             && per_one<exterior, boundary>(mask, matrix)
0438             && per_one<exterior, exterior>(mask, matrix);
0439     }
0440
0441     template <field F1, field F2, typename Matrix>
0442     static inline bool per_one(Mask const& mask, Matrix const& matrix)
0443     {
0444         const char mask_el = mask.template get<F1, F2>();
0445         const char el = matrix.template get<F1, F2>();
0446
0447         if ( mask_el == 'F' )
0448         {
0449             return el == 'F';
0450         }
0451         else if ( mask_el == 'T' )
0452         {
0453             return el == 'T' || ( el >= '0' && el <= '9' );
0454         }
0455         else if ( mask_el >= '0' && mask_el <= '9' )
0456         {
0457             return el == mask_el;
0458         }
0459
0460         return true;
0461     }
0462 };
0463
0464 template <typename Masks, int I = 0, int N = std::tuple_size<Masks>::value>
0465 struct check_dispatch_tuple
0466 {
0467     template <typename Matrix>
0468     static inline bool apply(Masks const& masks, Matrix const& matrix)
0469     {
0470         typedef typename std::tuple_element<I, Masks>::type mask_type;
0471         mask_type const& mask = std::get<I>(masks);
0472         return check_dispatch<mask_type>::apply(mask, matrix)
0473             || check_dispatch_tuple<Masks, I+1>::apply(masks, matrix);
0474     }
0475 };
0476
0477 template <typename Masks, int N>
0478 struct check_dispatch_tuple<Masks, N, N>
0479 {
0480     template <typename Matrix>
0481     static inline bool apply(Masks const&, Matrix const&)
0482     {
0483         return false;
0484     }
0485 };
0486
0487 template <typename ...Masks>
0488 struct check_dispatch<std::tuple<Masks...>>
0489 {
0490     typedef std::tuple<Masks...> mask_type;
0491
0492     template <typename Matrix>
0493     static inline bool apply(mask_type const& mask, Matrix const& matrix)
0494     {
0495         return check_dispatch_tuple<mask_type>::apply(mask, matrix);
0496     }
0497 };
0498
0499 template <typename Mask, typename Matrix>
0500 inline bool check_matrix(Mask const& mask, Matrix const& matrix)
0501 {
0502     return check_dispatch<Mask>::apply(mask, matrix);
0503 }
0504
0505 // matrix_width
0506
0507 template <typename MatrixOrMask>
0508 struct matrix_width
0509 {
0510     static const std::size_t value = MatrixOrMask::static_width;
0511 };
0512
0513 template <typename Tuple,
0514           int I = 0,
0515           int N = std::tuple_size<Tuple>::value>
0516 struct matrix_width_tuple
0517 {
0518     static const std::size_t
0519         current = matrix_width<typename std::tuple_element<I, Tuple>::type>::value;
0520     static const std::size_t
0521         next = matrix_width_tuple<Tuple, I+1>::value;
0522
0523     static const std::size_t
0524         value = current > next ? current : next;
0525 };
0526
0527 template <typename Tuple, int N>
0528 struct matrix_width_tuple<Tuple, N, N>
0529 {
0530     static const std::size_t value = 0;
0531 };
0532
0533 template <typename ...Masks>
0534 struct matrix_width<std::tuple<Masks...>>
0535 {
0536     static const std::size_t
0537         value = matrix_width_tuple<std::tuple<Masks...>>::value;
0538 };
0539
0540 // mask_handler
0541
0542 template <typename Mask, bool Interrupt>
0543 class mask_handler
0544     : private matrix_handler
0545         <
0546             relate::matrix<matrix_width<Mask>::value>
0547         >
0548 {
0549     typedef matrix_handler
0550         <
0551             relate::matrix<matrix_width<Mask>::value>
0552         > base_t;
0553
0554 public:
0555     typedef bool result_type;
0556
0557     bool interrupt;
0558
0559     inline explicit mask_handler(Mask const& m)
0560         : interrupt(false)
0561         , m_mask(m)
0562     {}
0563
0564     result_type result() const
0565     {
0566         return !interrupt
0567             && check_matrix(m_mask, base_t::matrix());
0568     }
0569
0570     template <field F1, field F2, char D>
0571     inline bool may_update() const
0572     {
0573         return detail::relate::may_update<F1, F2, D>(m_mask, base_t::matrix());
0574     }
0575
0576     template <field F1, field F2, char V>
0577     inline void update()
0578     {
0579         if (relate::interrupt<F1, F2, V, Interrupt>(m_mask))
0580         {
0581             interrupt = true;
0582         }
0583         else
0584         {
0585             base_t::template update<F1, F2, V>();
0586         }
0587     }
0588
0589     template <field F1, field F2, char V>
0590     inline void set()
0591     {
0592         if (relate::interrupt<F1, F2, V, Interrupt>(m_mask))
0593         {
0594             interrupt = true;
0595         }
0596         else
0597         {
0598             base_t::template set<F1, F2, V>();
0599         }
0600     }
0601
0602     template <field F1, field F2>
0603     inline char get() const
0604     {
0605         return base_t::template get<F1, F2>();
0606     }
0607
0608 private:
0609     Mask const& m_mask;
0610 };
0611
0612 // --------------- FALSE MASK ----------------
0613
0614 struct false_mask {};
0615
0616 // --------------- COMPILE-TIME MASK ----------------
0617
0618 // static_check_characters
0619 template <typename Seq>
0620 struct static_check_characters {};
0621
0622 template <char C, char ...Cs>
0623 struct static_check_characters<std::integer_sequence<char, C, Cs...>>
0624     : static_check_characters<std::integer_sequence<char, Cs...>>
0625 {
0626     typedef std::integer_sequence<char, C, Cs...> type;
0627     static const bool is_valid = (C >= '0' && C <= '9')
0628                                || C == 'T' || C == 'F' || C == '*';
0629     BOOST_GEOMETRY_STATIC_ASSERT((is_valid),
0630                                  "Invalid static mask character",
0631                                  type);
0632 };
0633
0634 template <char ...Cs>
0635 struct static_check_characters<std::integral_constant<char, Cs...>>
0636 {};
0637
0638 // static_mask
0639
0640 template <typename Seq, std::size_t Height, std::size_t Width = Height>
0641 struct static_mask
0642 {
0643     static const std::size_t static_width = Width;
0644     static const std::size_t static_height = Height;
0645     static const std::size_t static_size = Width * Height;
0646
0647     BOOST_STATIC_ASSERT(
0648         std::size_t(util::sequence_size<Seq>::value) == static_size);
0649
0650     template <detail::relate::field F1, detail::relate::field F2>
0651     struct static_get
0652     {
0653         BOOST_STATIC_ASSERT(std::size_t(F1) < static_height);
0654         BOOST_STATIC_ASSERT(std::size_t(F2) < static_width);
0655
0656         static const char value
0657             = util::sequence_element<F1 * static_width + F2, Seq>::value;
0658     };
0659
0660 private:
0661     // check static_mask characters
0662     enum { mask_check = sizeof(static_check_characters<Seq>) };
0663 };
0664
0665 // static_should_handle_element
0666
0667 template
0668 <
0669     typename StaticMask, field F1, field F2,
0670     bool IsSequence = util::is_sequence<StaticMask>::value
0671 >
0672 struct static_should_handle_element_dispatch
0673 {
0674     static const char mask_el = StaticMask::template static_get<F1, F2>::value;
0675     static const bool value = mask_el == 'F'
0676                            || mask_el == 'T'
0677                            || ( mask_el >= '0' && mask_el <= '9' );
0678 };
0679
0680 template
0681 <
0682     typename Seq, field F1, field F2,
0683     std::size_t I = 0,
0684     std::size_t N = util::sequence_size<Seq>::value
0685 >
0686 struct static_should_handle_element_sequence
0687 {
0688     typedef typename util::sequence_element<I, Seq>::type StaticMask;
0689
0690     static const bool value
0691         = static_should_handle_element_dispatch
0692             <
0693                 StaticMask, F1, F2
0694             >::value
0695        || static_should_handle_element_sequence
0696             <
0697                 Seq, F1, F2, I + 1
0698             >::value;
0699 };
0700
0701 template <typename Seq, field F1, field F2, std::size_t N>
0702 struct static_should_handle_element_sequence<Seq, F1, F2, N, N>
0703 {
0704     static const bool value = false;
0705 };
0706
0707 template <typename StaticMask, field F1, field F2>
0708 struct static_should_handle_element_dispatch<StaticMask, F1, F2, true>
0709 {
0710     static const bool value
0711         = static_should_handle_element_sequence
0712             <
0713                 StaticMask, F1, F2
0714             >::value;
0715 };
0716
0717 template <typename StaticMask, field F1, field F2>
0718 struct static_should_handle_element
0719 {
0720     static const bool value
0721         = static_should_handle_element_dispatch
0722             <
0723                 StaticMask, F1, F2
0724             >::value;
0725 };
0726
0727 // static_interrupt
0728
0729 template
0730 <
0731     typename StaticMask, char V, field F1, field F2,
0732     bool InterruptEnabled,
0733     bool IsSequence = util::is_sequence<StaticMask>::value
0734 >
0735 struct static_interrupt_dispatch
0736 {
0737     static const bool value = false;
0738 };
0739
0740 template <typename StaticMask, char V, field F1, field F2, bool IsSequence>
0741 struct static_interrupt_dispatch<StaticMask, V, F1, F2, true, IsSequence>
0742 {
0743     static const char mask_el = StaticMask::template static_get<F1, F2>::value;
0744
0745     static const bool value
0746         = ( V >= '0' && V <= '9' ) ?
0747           ( mask_el == 'F' || ( mask_el < V && mask_el >= '0' && mask_el <= '9' ) ) :
0748           ( ( V == 'T' ) ? mask_el == 'F' : false );
0749 };
0750
0751 template
0752 <
0753     typename Seq, char V, field F1, field F2,
0754     std::size_t I = 0,
0755     std::size_t N = util::sequence_size<Seq>::value
0756 >
0757 struct static_interrupt_sequence
0758 {
0759     typedef typename util::sequence_element<I, Seq>::type StaticMask;
0760
0761     static const bool value
0762         = static_interrupt_dispatch
0763             <
0764                 StaticMask, V, F1, F2, true
0765             >::value
0766        && static_interrupt_sequence
0767             <
0768                 Seq, V, F1, F2, I + 1
0769             >::value;
0770 };
0771
0772 template <typename Seq, char V, field F1, field F2, std::size_t N>
0773 struct static_interrupt_sequence<Seq, V, F1, F2, N, N>
0774 {
0775     static const bool value = true;
0776 };
0777
0778 template <typename StaticMask, char V, field F1, field F2>
0779 struct static_interrupt_dispatch<StaticMask, V, F1, F2, true, true>
0780 {
0781     static const bool value
0782         = static_interrupt_sequence
0783             <
0784                 StaticMask, V, F1, F2
0785             >::value;
0786 };
0787
0788 template <typename StaticMask, char V, field F1, field F2, bool EnableInterrupt>
0789 struct static_interrupt
0790 {
0791     static const bool value
0792         = static_interrupt_dispatch
0793             <
0794                 StaticMask, V, F1, F2, EnableInterrupt
0795             >::value;
0796 };
0797
0798 // static_may_update
0799
0800 template
0801 <
0802     typename StaticMask, char D, field F1, field F2,
0803     bool IsSequence = util::is_sequence<StaticMask>::value
0804 >
0805 struct static_may_update_dispatch
0806 {
0807     static const char mask_el = StaticMask::template static_get<F1, F2>::value;
0808     static const int version
0809                         = mask_el == 'F' ? 0
0810                         : mask_el == 'T' ? 1
0811                         : mask_el >= '0' && mask_el <= '9' ? 2
0812                         : 3;
0813
0814     // TODO: use std::enable_if_t instead of std::integral_constant
0815
0816     template <typename Matrix>
0817     static inline bool apply(Matrix const& matrix)
0818     {
0819         return apply_dispatch(matrix, std::integral_constant<int, version>());
0820     }
0821
0822     // mask_el == 'F'
0823     template <typename Matrix>
0824     static inline bool apply_dispatch(Matrix const& , std::integral_constant<int, 0>)
0825     {
0826         return true;
0827     }
0828     // mask_el == 'T'
0829     template <typename Matrix>
0830     static inline bool apply_dispatch(Matrix const& matrix, std::integral_constant<int, 1>)
0831     {
0832         char const c = matrix.template get<F1, F2>();
0833         return c == 'F'; // if it's T or between 0 and 9, the result will be the same
0834     }
0835     // mask_el >= '0' && mask_el <= '9'
0836     template <typename Matrix>
0837     static inline bool apply_dispatch(Matrix const& matrix, std::integral_constant<int, 2>)
0838     {
0839         char const c = matrix.template get<F1, F2>();
0840         return D > c || c > '9';
0841     }
0842     // else
0843     template <typename Matrix>
0844     static inline bool apply_dispatch(Matrix const&, std::integral_constant<int, 3>)
0845     {
0846         return false;
0847     }
0848 };
0849
0850 template
0851 <
0852     typename Seq, char D, field F1, field F2,
0853     std::size_t I = 0,
0854     std::size_t N = util::sequence_size<Seq>::value
0855 >
0856 struct static_may_update_sequence
0857 {
0858     typedef typename util::sequence_element<I, Seq>::type StaticMask;
0859
0860     template <typename Matrix>
0861     static inline bool apply(Matrix const& matrix)
0862     {
0863         return static_may_update_dispatch
0864                 <
0865                     StaticMask, D, F1, F2
0866                 >::apply(matrix)
0867             || static_may_update_sequence
0868                 <
0869                     Seq, D, F1, F2, I + 1
0870                 >::apply(matrix);
0871     }
0872 };
0873
0874 template <typename Seq, char D, field F1, field F2, std::size_t N>
0875 struct static_may_update_sequence<Seq, D, F1, F2, N, N>
0876 {
0877     template <typename Matrix>
0878     static inline bool apply(Matrix const& /*matrix*/)
0879     {
0880         return false;
0881     }
0882 };
0883
0884 template <typename StaticMask, char D, field F1, field F2>
0885 struct static_may_update_dispatch<StaticMask, D, F1, F2, true>
0886 {
0887     template <typename Matrix>
0888     static inline bool apply(Matrix const& matrix)
0889     {
0890         return static_may_update_sequence
0891                 <
0892                     StaticMask, D, F1, F2
0893                 >::apply(matrix);
0894     }
0895 };
0896
0897 template <typename StaticMask, char D, field F1, field F2>
0898 struct static_may_update
0899 {
0900     template <typename Matrix>
0901     static inline bool apply(Matrix const& matrix)
0902     {
0903         return static_may_update_dispatch
0904                 <
0905                     StaticMask, D, F1, F2
0906                 >::apply(matrix);
0907     }
0908 };
0909
0910 // static_check_matrix
0911
0912 template
0913 <
0914     typename StaticMask,
0915     bool IsSequence = util::is_sequence<StaticMask>::value
0916 >
0917 struct static_check_dispatch
0918 {
0919     template <typename Matrix>
0920     static inline bool apply(Matrix const& matrix)
0921     {
0922         return per_one<interior, interior>::apply(matrix)
0923             && per_one<interior, boundary>::apply(matrix)
0924             && per_one<interior, exterior>::apply(matrix)
0925             && per_one<boundary, interior>::apply(matrix)
0926             && per_one<boundary, boundary>::apply(matrix)
0927             && per_one<boundary, exterior>::apply(matrix)
0928             && per_one<exterior, interior>::apply(matrix)
0929             && per_one<exterior, boundary>::apply(matrix)
0930             && per_one<exterior, exterior>::apply(matrix);
0931     }
0932
0933     template <field F1, field F2>
0934     struct per_one
0935     {
0936         static const char mask_el = StaticMask::template static_get<F1, F2>::value;
0937         static const int version
0938                             = mask_el == 'F' ? 0
0939                             : mask_el == 'T' ? 1
0940                             : mask_el >= '0' && mask_el <= '9' ? 2
0941                             : 3;
0942
0943         // TODO: use std::enable_if_t instead of std::integral_constant
0944
0945         template <typename Matrix>
0946         static inline bool apply(Matrix const& matrix)
0947         {
0948             const char el = matrix.template get<F1, F2>();
0949             return apply_dispatch(el, std::integral_constant<int, version>());
0950         }
0951
0952         // mask_el == 'F'
0953         static inline bool apply_dispatch(char el, std::integral_constant<int, 0>)
0954         {
0955             return el == 'F';
0956         }
0957         // mask_el == 'T'
0958         static inline bool apply_dispatch(char el, std::integral_constant<int, 1>)
0959         {
0960             return el == 'T' || ( el >= '0' && el <= '9' );
0961         }
0962         // mask_el >= '0' && mask_el <= '9'
0963         static inline bool apply_dispatch(char el, std::integral_constant<int, 2>)
0964         {
0965             return el == mask_el;
0966         }
0967         // else
0968         static inline bool apply_dispatch(char /*el*/, std::integral_constant<int, 3>)
0969         {
0970             return true;
0971         }
0972     };
0973 };
0974
0975 template
0976 <
0977     typename Seq,
0978     std::size_t I = 0,
0979     std::size_t N = util::sequence_size<Seq>::value
0980 >
0981 struct static_check_sequence
0982 {
0983     typedef typename util::sequence_element<I, Seq>::type StaticMask;
0984
0985     template <typename Matrix>
0986     static inline bool apply(Matrix const& matrix)
0987     {
0988         return static_check_dispatch
0989                 <
0990                     StaticMask
0991                 >::apply(matrix)
0992             || static_check_sequence
0993                 <
0994                     Seq, I + 1
0995                 >::apply(matrix);
0996     }
0997 };
0998
0999 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, char V>
1070     inline void update()
1071     {
1072         static const bool interrupt_c = static_interrupt<StaticMask, V, F1, F2, Interrupt>::value;
1073         static const bool should_handle = static_should_handle_element<StaticMask, F1, F2>::value;
1074         static const int version = interrupt_c ? 0
1075                                  : should_handle ? 1
1076                                  : 2;
1077
1078         update_dispatch<F1, F2, V>(integral_constant<int, version>());
1079     }
1080
1081     template
1082     <
1083         field F1, field F2, char V,
1084         std::enable_if_t<static_interrupt<StaticMask, V, F1, F2, Interrupt>::value, int> = 0
1085     >
1086     inline void set()
1087     {
1088         interrupt = true;
1089     }
1090
1091     template
1092     <
1093         field F1, field F2, char V,
1094         std::enable_if_t<! static_interrupt<StaticMask, V, F1, F2, Interrupt>::value, int> = 0
1095     >
1096     inline void set()
1097     {
1098         base_type::template set<F1, F2, V>();
1099     }
1100
1101     template <field F1, field F2>
1102     inline char get() const
1103     {
1104         return base_type::template get<F1, F2>();
1105     }
1106
1107 private:
1108     // Interrupt && interrupt
1109     template <field F1, field F2, char V>
1110     inline void update_dispatch(integral_constant<int, 0>)
1111     {
1112         interrupt = true;
1113     }
1114     // else should_handle
1115     template <field F1, field F2, char V>
1116     inline void update_dispatch(integral_constant<int, 1>)
1117     {
1118         base_type::template update<F1, F2, V>();
1119     }
1120     // else
1121     template <field F1, field F2, char V>
1122     inline void update_dispatch(integral_constant<int, 2>)
1123     {}
1124 };
1125
1126 // --------------- UTIL FUNCTIONS ----------------
1127
1128 // update
1129
1130 template <field F1, field F2, char D, typename Result>
1131 inline void update(Result & res)
1132 {
1133     res.template update<F1, F2, D>();
1134 }
1135
1136 template
1137 <
1138     field F1, field F2, char D, bool Transpose, typename Result,
1139     std::enable_if_t<! Transpose, int> = 0
1140 >
1141 inline void update(Result & res)
1142 {
1143     res.template update<F1, F2, D>();
1144 }
1145
1146 template
1147 <
1148     field F1, field F2, char D, bool Transpose, typename Result,
1149     std::enable_if_t<Transpose, int> = 0
1150 >
1151 inline void update(Result & res)
1152 {
1153     res.template update<F2, F1, D>();
1154 }
1155
1156 // may_update
1157
1158 template <field F1, field F2, char D, typename Result>
1159 inline bool may_update(Result const& res)
1160 {
1161     return res.template may_update<F1, F2, D>();
1162 }
1163
1164 template
1165 <
1166     field F1, field F2, char D, bool Transpose, typename Result,
1167     std::enable_if_t<! Transpose, int> = 0
1168 >
1169 inline bool may_update(Result const& res)
1170 {
1171     return res.template may_update<F1, F2, D>();
1172 }
1173
1174 template
1175 <
1176     field F1, field F2, char D, bool Transpose, typename Result,
1177     std::enable_if_t<Transpose, int> = 0
1178 >
1179 inline bool may_update(Result const& res)
1180 {
1181     return res.template may_update<F2, F1, D>();
1182 }
1183
1184 // result_dimension
1185
1186 template <typename Geometry>
1187 struct result_dimension
1188 {
1189     static const std::size_t dim = geometry::dimension<Geometry>::value;
1190     BOOST_STATIC_ASSERT(dim >= 0);
1191     static const char value = (dim <= 9) ? ('0' + dim) : 'T';
1192 };
1193
1194 }} // namespace detail::relate
1195 #endif // DOXYGEN_NO_DETAIL
1196
1197 }} // namespace boost::geometry
1198
1199 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_RESULT_HPP