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/constexpr.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_CONSTEXPR (V >= '0' && V <= '9')
0296         {
0297             return m == 'F' || ( m < V && m >= '0' && m <= '9' );
0298         }
0299         else if BOOST_GEOMETRY_CONSTEXPR (V == 'T')
0300         {
0301             return m == 'F';
0302         }
0303         else
0304         {
0305             return false;
0306         }
0307     }
0308 };
0309
0310 template <typename Masks, int I = 0, int N = std::tuple_size<Masks>::value>
0311 struct interrupt_dispatch_tuple
0312 {
0313     template <field F1, field F2, char V>
0314     static inline bool apply(Masks const& masks)
0315     {
0316         typedef typename std::tuple_element<I, Masks>::type mask_type;
0317         mask_type const& mask = std::get<I>(masks);
0318         return interrupt_dispatch<mask_type, true>::template apply<F1, F2, V>(mask)
0319             && interrupt_dispatch_tuple<Masks, I+1>::template apply<F1, F2, V>(masks);
0320     }
0321 };
0322
0323 template <typename Masks, int N>
0324 struct interrupt_dispatch_tuple<Masks, N, N>
0325 {
0326     template <field F1, field F2, char V>
0327     static inline bool apply(Masks const& )
0328     {
0329         return true;
0330     }
0331 };
0332
0333 template <typename ...Masks>
0334 struct interrupt_dispatch<std::tuple<Masks...>, true>
0335 {
0336     typedef std::tuple<Masks...> mask_type;
0337
0338     template <field F1, field F2, char V>
0339     static inline bool apply(mask_type const& mask)
0340     {
0341         return interrupt_dispatch_tuple<mask_type>::template apply<F1, F2, V>(mask);
0342     }
0343 };
0344
0345 template <field F1, field F2, char V, bool InterruptEnabled, typename Mask>
0346 inline bool interrupt(Mask const& mask)
0347 {
0348     return interrupt_dispatch<Mask, InterruptEnabled>
0349                 ::template apply<F1, F2, V>(mask);
0350 }
0351
0352 // may_update()
0353
0354 template <typename Mask>
0355 struct may_update_dispatch
0356 {
0357     template <field F1, field F2, char D, typename Matrix>
0358     static inline bool apply(Mask const& mask, Matrix const& matrix)
0359     {
0360         BOOST_STATIC_ASSERT('0' <= D && D <= '9');
0361
0362         char const m = mask.template get<F1, F2>();
0363
0364         if ( m == 'F' )
0365         {
0366             return true;
0367         }
0368         else if ( m == 'T' )
0369         {
0370             char const c = matrix.template get<F1, F2>();
0371             return c == 'F'; // if it's T or between 0 and 9, the result will be the same
0372         }
0373         else if ( m >= '0' && m <= '9' )
0374         {
0375             char const c = matrix.template get<F1, F2>();
0376             return D > c || c > '9';
0377         }
0378
0379         return false;
0380     }
0381 };
0382
0383 template <typename Masks, int I = 0, int N = std::tuple_size<Masks>::value>
0384 struct may_update_dispatch_tuple
0385 {
0386     template <field F1, field F2, char D, typename Matrix>
0387     static inline bool apply(Masks const& masks, Matrix const& matrix)
0388     {
0389         typedef typename std::tuple_element<I, Masks>::type mask_type;
0390         mask_type const& mask = std::get<I>(masks);
0391         return may_update_dispatch<mask_type>::template apply<F1, F2, D>(mask, matrix)
0392             || may_update_dispatch_tuple<Masks, I+1>::template apply<F1, F2, D>(masks, matrix);
0393     }
0394 };
0395
0396 template <typename Masks, int N>
0397 struct may_update_dispatch_tuple<Masks, N, N>
0398 {
0399     template <field F1, field F2, char D, typename Matrix>
0400     static inline bool apply(Masks const& , Matrix const& )
0401     {
0402         return false;
0403     }
0404 };
0405
0406 template <typename ...Masks>
0407 struct may_update_dispatch<std::tuple<Masks...>>
0408 {
0409     typedef std::tuple<Masks...> mask_type;
0410
0411     template <field F1, field F2, char D, typename Matrix>
0412     static inline bool apply(mask_type const& mask, Matrix const& matrix)
0413     {
0414         return may_update_dispatch_tuple<mask_type>::template apply<F1, F2, D>(mask, matrix);
0415     }
0416 };
0417
0418 template <field F1, field F2, char D, typename Mask, typename Matrix>
0419 inline bool may_update(Mask const& mask, Matrix const& matrix)
0420 {
0421     return may_update_dispatch<Mask>
0422                 ::template apply<F1, F2, D>(mask, matrix);
0423 }
0424
0425 // check_matrix()
0426
0427 template <typename Mask>
0428 struct check_dispatch
0429 {
0430     template <typename Matrix>
0431     static inline bool apply(Mask const& mask, Matrix const& matrix)
0432     {
0433         return per_one<interior, interior>(mask, matrix)
0434             && per_one<interior, boundary>(mask, matrix)
0435             && per_one<interior, exterior>(mask, matrix)
0436             && per_one<boundary, interior>(mask, matrix)
0437             && per_one<boundary, boundary>(mask, matrix)
0438             && per_one<boundary, exterior>(mask, matrix)
0439             && per_one<exterior, interior>(mask, matrix)
0440             && per_one<exterior, boundary>(mask, matrix)
0441             && per_one<exterior, exterior>(mask, matrix);
0442     }
0443
0444     template <field F1, field F2, typename Matrix>
0445     static inline bool per_one(Mask const& mask, Matrix const& matrix)
0446     {
0447         const char mask_el = mask.template get<F1, F2>();
0448         const char el = matrix.template get<F1, F2>();
0449
0450         if ( mask_el == 'F' )
0451         {
0452             return el == 'F';
0453         }
0454         else if ( mask_el == 'T' )
0455         {
0456             return el == 'T' || ( el >= '0' && el <= '9' );
0457         }
0458         else if ( mask_el >= '0' && mask_el <= '9' )
0459         {
0460             return el == mask_el;
0461         }
0462
0463         return true;
0464     }
0465 };
0466
0467 template <typename Masks, int I = 0, int N = std::tuple_size<Masks>::value>
0468 struct check_dispatch_tuple
0469 {
0470     template <typename Matrix>
0471     static inline bool apply(Masks const& masks, Matrix const& matrix)
0472     {
0473         typedef typename std::tuple_element<I, Masks>::type mask_type;
0474         mask_type const& mask = std::get<I>(masks);
0475         return check_dispatch<mask_type>::apply(mask, matrix)
0476             || check_dispatch_tuple<Masks, I+1>::apply(masks, matrix);
0477     }
0478 };
0479
0480 template <typename Masks, int N>
0481 struct check_dispatch_tuple<Masks, N, N>
0482 {
0483     template <typename Matrix>
0484     static inline bool apply(Masks const&, Matrix const&)
0485     {
0486         return false;
0487     }
0488 };
0489
0490 template <typename ...Masks>
0491 struct check_dispatch<std::tuple<Masks...>>
0492 {
0493     typedef std::tuple<Masks...> mask_type;
0494
0495     template <typename Matrix>
0496     static inline bool apply(mask_type const& mask, Matrix const& matrix)
0497     {
0498         return check_dispatch_tuple<mask_type>::apply(mask, matrix);
0499     }
0500 };
0501
0502 template <typename Mask, typename Matrix>
0503 inline bool check_matrix(Mask const& mask, Matrix const& matrix)
0504 {
0505     return check_dispatch<Mask>::apply(mask, matrix);
0506 }
0507
0508 // matrix_width
0509
0510 template <typename MatrixOrMask>
0511 struct matrix_width
0512 {
0513     static const std::size_t value = MatrixOrMask::static_width;
0514 };
0515
0516 template <typename Tuple,
0517           int I = 0,
0518           int N = std::tuple_size<Tuple>::value>
0519 struct matrix_width_tuple
0520 {
0521     static const std::size_t
0522         current = matrix_width<typename std::tuple_element<I, Tuple>::type>::value;
0523     static const std::size_t
0524         next = matrix_width_tuple<Tuple, I+1>::value;
0525
0526     static const std::size_t
0527         value = current > next ? current : next;
0528 };
0529
0530 template <typename Tuple, int N>
0531 struct matrix_width_tuple<Tuple, N, N>
0532 {
0533     static const std::size_t value = 0;
0534 };
0535
0536 template <typename ...Masks>
0537 struct matrix_width<std::tuple<Masks...>>
0538 {
0539     static const std::size_t
0540         value = matrix_width_tuple<std::tuple<Masks...>>::value;
0541 };
0542
0543 // mask_handler
0544
0545 template <typename Mask, bool Interrupt>
0546 class mask_handler
0547     : private matrix_handler
0548         <
0549             relate::matrix<matrix_width<Mask>::value>
0550         >
0551 {
0552     typedef matrix_handler
0553         <
0554             relate::matrix<matrix_width<Mask>::value>
0555         > base_t;
0556
0557 public:
0558     typedef bool result_type;
0559
0560     bool interrupt;
0561
0562     inline explicit mask_handler(Mask const& m)
0563         : interrupt(false)
0564         , m_mask(m)
0565     {}
0566
0567     result_type result() const
0568     {
0569         return !interrupt
0570             && check_matrix(m_mask, base_t::matrix());
0571     }
0572
0573     template <field F1, field F2, char D>
0574     inline bool may_update() const
0575     {
0576         return detail::relate::may_update<F1, F2, D>(m_mask, base_t::matrix());
0577     }
0578
0579     template <field F1, field F2, char V>
0580     inline void update()
0581     {
0582         if (relate::interrupt<F1, F2, V, Interrupt>(m_mask))
0583         {
0584             interrupt = true;
0585         }
0586         else
0587         {
0588             base_t::template update<F1, F2, V>();
0589         }
0590     }
0591
0592     template <field F1, field F2, char V>
0593     inline void set()
0594     {
0595         if (relate::interrupt<F1, F2, V, Interrupt>(m_mask))
0596         {
0597             interrupt = true;
0598         }
0599         else
0600         {
0601             base_t::template set<F1, F2, V>();
0602         }
0603     }
0604
0605     template <field F1, field F2>
0606     inline char get() const
0607     {
0608         return base_t::template get<F1, F2>();
0609     }
0610
0611 private:
0612     Mask const& m_mask;
0613 };
0614
0615 // --------------- FALSE MASK ----------------
0616
0617 struct false_mask {};
0618
0619 // --------------- COMPILE-TIME MASK ----------------
0620
0621 // static_check_characters
0622 template <typename Seq>
0623 struct static_check_characters {};
0624
0625 template <char C, char ...Cs>
0626 struct static_check_characters<std::integer_sequence<char, C, Cs...>>
0627     : static_check_characters<std::integer_sequence<char, Cs...>>
0628 {
0629     typedef std::integer_sequence<char, C, Cs...> type;
0630     static const bool is_valid = (C >= '0' && C <= '9')
0631                                || C == 'T' || C == 'F' || C == '*';
0632     BOOST_GEOMETRY_STATIC_ASSERT((is_valid),
0633                                  "Invalid static mask character",
0634                                  type);
0635 };
0636
0637 template <char ...Cs>
0638 struct static_check_characters<std::integral_constant<char, Cs...>>
0639 {};
0640
0641 // static_mask
0642
0643 template <typename Seq, std::size_t Height, std::size_t Width = Height>
0644 struct static_mask
0645 {
0646     static const std::size_t static_width = Width;
0647     static const std::size_t static_height = Height;
0648     static const std::size_t static_size = Width * Height;
0649
0650     BOOST_STATIC_ASSERT(
0651         std::size_t(util::sequence_size<Seq>::value) == static_size);
0652
0653     template <detail::relate::field F1, detail::relate::field F2>
0654     struct static_get
0655     {
0656         BOOST_STATIC_ASSERT(std::size_t(F1) < static_height);
0657         BOOST_STATIC_ASSERT(std::size_t(F2) < static_width);
0658
0659         static const char value
0660             = util::sequence_element<F1 * static_width + F2, Seq>::value;
0661     };
0662
0663 private:
0664     // check static_mask characters
0665     enum { mask_check = sizeof(static_check_characters<Seq>) };
0666 };
0667
0668 // static_should_handle_element
0669
0670 template
0671 <
0672     typename StaticMask, field F1, field F2,
0673     bool IsSequence = util::is_sequence<StaticMask>::value
0674 >
0675 struct static_should_handle_element_dispatch
0676 {
0677     static const char mask_el = StaticMask::template static_get<F1, F2>::value;
0678     static const bool value = mask_el == 'F'
0679                            || mask_el == 'T'
0680                            || ( mask_el >= '0' && mask_el <= '9' );
0681 };
0682
0683 template
0684 <
0685     typename Seq, field F1, field F2,
0686     std::size_t I = 0,
0687     std::size_t N = util::sequence_size<Seq>::value
0688 >
0689 struct static_should_handle_element_sequence
0690 {
0691     typedef typename util::sequence_element<I, Seq>::type StaticMask;
0692
0693     static const bool value
0694         = static_should_handle_element_dispatch
0695             <
0696                 StaticMask, F1, F2
0697             >::value
0698        || static_should_handle_element_sequence
0699             <
0700                 Seq, F1, F2, I + 1
0701             >::value;
0702 };
0703
0704 template <typename Seq, field F1, field F2, std::size_t N>
0705 struct static_should_handle_element_sequence<Seq, F1, F2, N, N>
0706 {
0707     static const bool value = false;
0708 };
0709
0710 template <typename StaticMask, field F1, field F2>
0711 struct static_should_handle_element_dispatch<StaticMask, F1, F2, true>
0712 {
0713     static const bool value
0714         = static_should_handle_element_sequence
0715             <
0716                 StaticMask, F1, F2
0717             >::value;
0718 };
0719
0720 template <typename StaticMask, field F1, field F2>
0721 struct static_should_handle_element
0722 {
0723     static const bool value
0724         = static_should_handle_element_dispatch
0725             <
0726                 StaticMask, F1, F2
0727             >::value;
0728 };
0729
0730 // static_interrupt
0731
0732 template
0733 <
0734     typename StaticMask, char V, field F1, field F2,
0735     bool InterruptEnabled,
0736     bool IsSequence = util::is_sequence<StaticMask>::value
0737 >
0738 struct static_interrupt_dispatch
0739 {
0740     static const bool value = false;
0741 };
0742
0743 template <typename StaticMask, char V, field F1, field F2, bool IsSequence>
0744 struct static_interrupt_dispatch<StaticMask, V, F1, F2, true, IsSequence>
0745 {
0746     static const char mask_el = StaticMask::template static_get<F1, F2>::value;
0747
0748     static const bool value
0749         = ( V >= '0' && V <= '9' ) ?
0750           ( mask_el == 'F' || ( mask_el < V && mask_el >= '0' && mask_el <= '9' ) ) :
0751           ( ( V == 'T' ) ? mask_el == 'F' : false );
0752 };
0753
0754 template
0755 <
0756     typename Seq, char V, field F1, field F2,
0757     std::size_t I = 0,
0758     std::size_t N = util::sequence_size<Seq>::value
0759 >
0760 struct static_interrupt_sequence
0761 {
0762     typedef typename util::sequence_element<I, Seq>::type StaticMask;
0763
0764     static const bool value
0765         = static_interrupt_dispatch
0766             <
0767                 StaticMask, V, F1, F2, true
0768             >::value
0769        && static_interrupt_sequence
0770             <
0771                 Seq, V, F1, F2, I + 1
0772             >::value;
0773 };
0774
0775 template <typename Seq, char V, field F1, field F2, std::size_t N>
0776 struct static_interrupt_sequence<Seq, V, F1, F2, N, N>
0777 {
0778     static const bool value = true;
0779 };
0780
0781 template <typename StaticMask, char V, field F1, field F2>
0782 struct static_interrupt_dispatch<StaticMask, V, F1, F2, true, true>
0783 {
0784     static const bool value
0785         = static_interrupt_sequence
0786             <
0787                 StaticMask, V, F1, F2
0788             >::value;
0789 };
0790
0791 template <typename StaticMask, char V, field F1, field F2, bool EnableInterrupt>
0792 struct static_interrupt
0793 {
0794     static const bool value
0795         = static_interrupt_dispatch
0796             <
0797                 StaticMask, V, F1, F2, EnableInterrupt
0798             >::value;
0799 };
0800
0801 // static_may_update
0802
0803 template
0804 <
0805     typename StaticMask, char D, field F1, field F2,
0806     bool IsSequence = util::is_sequence<StaticMask>::value
0807 >
0808 struct static_may_update_dispatch
0809 {
0810     static const char mask_el = StaticMask::template static_get<F1, F2>::value;
0811     static const int version
0812                         = mask_el == 'F' ? 0
0813                         : mask_el == 'T' ? 1
0814                         : mask_el >= '0' && mask_el <= '9' ? 2
0815                         : 3;
0816
0817     // TODO: use std::enable_if_t instead of std::integral_constant
0818
0819     template <typename Matrix>
0820     static inline bool apply(Matrix const& matrix)
0821     {
0822         return apply_dispatch(matrix, std::integral_constant<int, version>());
0823     }
0824
0825     // mask_el == 'F'
0826     template <typename Matrix>
0827     static inline bool apply_dispatch(Matrix const& , std::integral_constant<int, 0>)
0828     {
0829         return true;
0830     }
0831     // mask_el == 'T'
0832     template <typename Matrix>
0833     static inline bool apply_dispatch(Matrix const& matrix, std::integral_constant<int, 1>)
0834     {
0835         char const c = matrix.template get<F1, F2>();
0836         return c == 'F'; // if it's T or between 0 and 9, the result will be the same
0837     }
0838     // mask_el >= '0' && mask_el <= '9'
0839     template <typename Matrix>
0840     static inline bool apply_dispatch(Matrix const& matrix, std::integral_constant<int, 2>)
0841     {
0842         char const c = matrix.template get<F1, F2>();
0843         return D > c || c > '9';
0844     }
0845     // else
0846     template <typename Matrix>
0847     static inline bool apply_dispatch(Matrix const&, std::integral_constant<int, 3>)
0848     {
0849         return false;
0850     }
0851 };
0852
0853 template
0854 <
0855     typename Seq, char D, field F1, field F2,
0856     std::size_t I = 0,
0857     std::size_t N = util::sequence_size<Seq>::value
0858 >
0859 struct static_may_update_sequence
0860 {
0861     typedef typename util::sequence_element<I, Seq>::type StaticMask;
0862
0863     template <typename Matrix>
0864     static inline bool apply(Matrix const& matrix)
0865     {
0866         return static_may_update_dispatch
0867                 <
0868                     StaticMask, D, F1, F2
0869                 >::apply(matrix)
0870             || static_may_update_sequence
0871                 <
0872                     Seq, D, F1, F2, I + 1
0873                 >::apply(matrix);
0874     }
0875 };
0876
0877 template <typename Seq, char D, field F1, field F2, std::size_t N>
0878 struct static_may_update_sequence<Seq, D, F1, F2, N, N>
0879 {
0880     template <typename Matrix>
0881     static inline bool apply(Matrix const& /*matrix*/)
0882     {
0883         return false;
0884     }
0885 };
0886
0887 template <typename StaticMask, char D, field F1, field F2>
0888 struct static_may_update_dispatch<StaticMask, D, F1, F2, true>
0889 {
0890     template <typename Matrix>
0891     static inline bool apply(Matrix const& matrix)
0892     {
0893         return static_may_update_sequence
0894                 <
0895                     StaticMask, D, F1, F2
0896                 >::apply(matrix);
0897     }
0898 };
0899
0900 template <typename StaticMask, char D, field F1, field F2>
0901 struct static_may_update
0902 {
0903     template <typename Matrix>
0904     static inline bool apply(Matrix const& matrix)
0905     {
0906         return static_may_update_dispatch
0907                 <
0908                     StaticMask, D, F1, F2
0909                 >::apply(matrix);
0910     }
0911 };
0912
0913 // static_check_matrix
0914
0915 template
0916 <
0917     typename StaticMask,
0918     bool IsSequence = util::is_sequence<StaticMask>::value
0919 >
0920 struct static_check_dispatch
0921 {
0922     template <typename Matrix>
0923     static inline bool apply(Matrix const& matrix)
0924     {
0925         return per_one<interior, interior>::apply(matrix)
0926             && per_one<interior, boundary>::apply(matrix)
0927             && per_one<interior, exterior>::apply(matrix)
0928             && per_one<boundary, interior>::apply(matrix)
0929             && per_one<boundary, boundary>::apply(matrix)
0930             && per_one<boundary, exterior>::apply(matrix)
0931             && per_one<exterior, interior>::apply(matrix)
0932             && per_one<exterior, boundary>::apply(matrix)
0933             && per_one<exterior, exterior>::apply(matrix);
0934     }
0935
0936     template <field F1, field F2>
0937     struct per_one
0938     {
0939         static const char mask_el = StaticMask::template static_get<F1, F2>::value;
0940         static const int version
0941                             = mask_el == 'F' ? 0
0942                             : mask_el == 'T' ? 1
0943                             : mask_el >= '0' && mask_el <= '9' ? 2
0944                             : 3;
0945
0946         // TODO: use std::enable_if_t instead of std::integral_constant
0947
0948         template <typename Matrix>
0949         static inline bool apply(Matrix const& matrix)
0950         {
0951             const char el = matrix.template get<F1, F2>();
0952             return apply_dispatch(el, std::integral_constant<int, version>());
0953         }
0954
0955         // mask_el == 'F'
0956         static inline bool apply_dispatch(char el, std::integral_constant<int, 0>)
0957         {
0958             return el == 'F';
0959         }
0960         // mask_el == 'T'
0961         static inline bool apply_dispatch(char el, std::integral_constant<int, 1>)
0962         {
0963             return el == 'T' || ( el >= '0' && el <= '9' );
0964         }
0965         // mask_el >= '0' && mask_el <= '9'
0966         static inline bool apply_dispatch(char el, std::integral_constant<int, 2>)
0967         {
0968             return el == mask_el;
0969         }
0970         // else
0971         static inline bool apply_dispatch(char /*el*/, std::integral_constant<int, 3>)
0972         {
0973             return true;
0974         }
0975     };
0976 };
0977
0978 template
0979 <
0980     typename Seq,
0981     std::size_t I = 0,
0982     std::size_t N = util::sequence_size<Seq>::value
0983 >
0984 struct static_check_sequence
0985 {
0986     typedef typename util::sequence_element<I, Seq>::type StaticMask;
0987
0988     template <typename Matrix>
0989     static inline bool apply(Matrix const& matrix)
0990     {
0991         return static_check_dispatch
0992                 <
0993                     StaticMask
0994                 >::apply(matrix)
0995             || static_check_sequence
0996                 <
0997                     Seq, I + 1
0998                 >::apply(matrix);
0999     }
1000 };
1001
1002 template <typename Seq, std::size_t N>
1003 struct static_check_sequence<Seq, N, N>
1004 {
1005     template <typename Matrix>
1006     static inline bool apply(Matrix const& /*matrix*/)
1007     {
1008         return false;
1009     }
1010 };
1011
1012 template <typename StaticMask>
1013 struct static_check_dispatch<StaticMask, true>
1014 {
1015     template <typename Matrix>
1016     static inline bool apply(Matrix const& matrix)
1017     {
1018         return static_check_sequence
1019                 <
1020                     StaticMask
1021                 >::apply(matrix);
1022     }
1023 };
1024
1025 template <typename StaticMask>
1026 struct static_check_matrix
1027 {
1028     template <typename Matrix>
1029     static inline bool apply(Matrix const& matrix)
1030     {
1031         return static_check_dispatch
1032                 <
1033                     StaticMask
1034                 >::apply(matrix);
1035     }
1036 };
1037
1038 // static_mask_handler
1039
1040 template <typename StaticMask, bool Interrupt>
1041 class static_mask_handler
1042     : private matrix_handler< matrix<3> >
1043 {
1044     typedef matrix_handler< relate::matrix<3> > base_type;
1045
1046 public:
1047     typedef bool result_type;
1048
1049     bool interrupt;
1050
1051     inline static_mask_handler()
1052         : interrupt(false)
1053     {}
1054
1055     inline explicit static_mask_handler(StaticMask const& /*dummy*/)
1056         : interrupt(false)
1057     {}
1058
1059     result_type result() const
1060     {
1061         return (!Interrupt || !interrupt)
1062             && static_check_matrix<StaticMask>::apply(base_type::matrix());
1063     }
1064
1065     template <field F1, field F2, char D>
1066     inline bool may_update() const
1067     {
1068         return static_may_update<StaticMask, D, F1, F2>::
1069                     apply(base_type::matrix());
1070     }
1071
1072     template <field F1, field F2, char V>
1073     inline void update()
1074     {
1075         static const bool interrupt_c = static_interrupt<StaticMask, V, F1, F2, Interrupt>::value;
1076         static const bool should_handle = static_should_handle_element<StaticMask, F1, F2>::value;
1077         static const int version = interrupt_c ? 0
1078                                  : should_handle ? 1
1079                                  : 2;
1080
1081         update_dispatch<F1, F2, V>(integral_constant<int, version>());
1082     }
1083
1084     template
1085     <
1086         field F1, field F2, char V,
1087         std::enable_if_t<static_interrupt<StaticMask, V, F1, F2, Interrupt>::value, int> = 0
1088     >
1089     inline void set()
1090     {
1091         interrupt = true;
1092     }
1093
1094     template
1095     <
1096         field F1, field F2, char V,
1097         std::enable_if_t<! static_interrupt<StaticMask, V, F1, F2, Interrupt>::value, int> = 0
1098     >
1099     inline void set()
1100     {
1101         base_type::template set<F1, F2, V>();
1102     }
1103
1104     template <field F1, field F2>
1105     inline char get() const
1106     {
1107         return base_type::template get<F1, F2>();
1108     }
1109
1110 private:
1111     // Interrupt && interrupt
1112     template <field F1, field F2, char V>
1113     inline void update_dispatch(integral_constant<int, 0>)
1114     {
1115         interrupt = true;
1116     }
1117     // else should_handle
1118     template <field F1, field F2, char V>
1119     inline void update_dispatch(integral_constant<int, 1>)
1120     {
1121         base_type::template update<F1, F2, V>();
1122     }
1123     // else
1124     template <field F1, field F2, char V>
1125     inline void update_dispatch(integral_constant<int, 2>)
1126     {}
1127 };
1128
1129 // --------------- UTIL FUNCTIONS ----------------
1130
1131 // update
1132
1133 template <field F1, field F2, char D, typename Result>
1134 inline void update(Result & res)
1135 {
1136     res.template update<F1, F2, D>();
1137 }
1138
1139 template
1140 <
1141     field F1, field F2, char D, bool Transpose, typename Result,
1142     std::enable_if_t<! Transpose, int> = 0
1143 >
1144 inline void update(Result & res)
1145 {
1146     res.template update<F1, F2, D>();
1147 }
1148
1149 template
1150 <
1151     field F1, field F2, char D, bool Transpose, typename Result,
1152     std::enable_if_t<Transpose, int> = 0
1153 >
1154 inline void update(Result & res)
1155 {
1156     res.template update<F2, F1, D>();
1157 }
1158
1159 // may_update
1160
1161 template <field F1, field F2, char D, typename Result>
1162 inline bool may_update(Result const& res)
1163 {
1164     return res.template may_update<F1, F2, D>();
1165 }
1166
1167 template
1168 <
1169     field F1, field F2, char D, bool Transpose, typename Result,
1170     std::enable_if_t<! Transpose, int> = 0
1171 >
1172 inline bool may_update(Result const& res)
1173 {
1174     return res.template may_update<F1, F2, D>();
1175 }
1176
1177 template
1178 <
1179     field F1, field F2, char D, bool Transpose, typename Result,
1180     std::enable_if_t<Transpose, int> = 0
1181 >
1182 inline bool may_update(Result const& res)
1183 {
1184     return res.template may_update<F2, F1, D>();
1185 }
1186
1187 // result_dimension
1188
1189 template <typename Geometry>
1190 struct result_dimension
1191 {
1192     static const std::size_t dim = geometry::dimension<Geometry>::value;
1193     BOOST_STATIC_ASSERT(dim >= 0);
1194     static const char value = (dim <= 9) ? ('0' + dim) : 'T';
1195 };
1196
1197 }} // namespace detail::relate
1198 #endif // DOXYGEN_NO_DETAIL
1199
1200 }} // namespace boost::geometry
1201
1202 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_RESULT_HPP