1 /*-----------------------------------------------------------------------------+
2 Copyright (c) 2008-2010: Joachim Faulhaber
3 +------------------------------------------------------------------------------+
4 Distributed under the Boost Software License, Version 1.0.
5 (See accompanying file LICENCE.txt or copy at
6 http://www.boost.org/LICENSE_1_0.txt)
7 +-----------------------------------------------------------------------------*/
8 #ifndef BOOST_ICL_INTERVAL_MAP_ALGO_HPP_JOFA_100730
9 #define BOOST_ICL_INTERVAL_MAP_ALGO_HPP_JOFA_100730
10
11 #include <boost/utility/enable_if.hpp>
12 #include <boost/mpl/not.hpp>
13
14 #include <boost/icl/type_traits/is_total.hpp>
15 #include <boost/icl/type_traits/is_map.hpp>
16 #include <boost/icl/detail/notate.hpp>
17 #include <boost/icl/detail/relation_state.hpp>
18 #include <boost/icl/type_traits/identity_element.hpp>
19 #include <boost/icl/interval_combining_style.hpp>
20 #include <boost/icl/detail/element_comparer.hpp>
21 #include <boost/icl/detail/interval_subset_comparer.hpp>
22
23 namespace boost{namespace icl
24 {
25
26
27 namespace Interval_Map
28 {
29 using namespace segmental;
30
31 template<class IntervalMapT>
is_joinable(const IntervalMapT & container,typename IntervalMapT::const_iterator first,typename IntervalMapT::const_iterator past)32 bool is_joinable(const IntervalMapT& container,
33 typename IntervalMapT::const_iterator first,
34 typename IntervalMapT::const_iterator past)
35 {
36 if(first == container.end())
37 return true;
38
39 typename IntervalMapT::const_iterator it_ = first, next_ = first;
40 ++next_;
41
42 const typename IntervalMapT::codomain_type& co_value
43 = icl::co_value<IntervalMapT>(first);
44 while(it_ != past)
45 {
46 if(icl::co_value<IntervalMapT>(next_) != co_value)
47 return false;
48 if(!icl::touches(key_value<IntervalMapT>(it_++),
49 key_value<IntervalMapT>(next_++)))
50 return false;
51 }
52
53 return true;
54 }
55
56 //------------------------------------------------------------------------------
57 //- Containedness of key objects
58 //------------------------------------------------------------------------------
59
60 //- domain_type ----------------------------------------------------------------
61 template<class IntervalMapT>
62 typename enable_if<mpl::not_<is_total<IntervalMapT> >, bool>::type
contains(const IntervalMapT & container,const typename IntervalMapT::domain_type & key)63 contains(const IntervalMapT& container,
64 const typename IntervalMapT::domain_type& key)
65 {
66 return container.find(key) != container.end();
67 }
68
69 template<class IntervalMapT>
70 typename enable_if<is_total<IntervalMapT>, bool>::type
contains(const IntervalMapT &,const typename IntervalMapT::domain_type &)71 contains(const IntervalMapT&,
72 const typename IntervalMapT::domain_type&)
73 {
74 return true;
75 }
76
77 //- interval_type --------------------------------------------------------------
78 template<class IntervalMapT>
79 typename enable_if<mpl::not_<is_total<IntervalMapT> >, bool>::type
contains(const IntervalMapT & container,const typename IntervalMapT::interval_type & sub_interval)80 contains(const IntervalMapT& container,
81 const typename IntervalMapT::interval_type& sub_interval)
82 {
83 typedef typename IntervalMapT::const_iterator const_iterator;
84 if(icl::is_empty(sub_interval))
85 return true;
86
87 std::pair<const_iterator, const_iterator> exterior = container.equal_range(sub_interval);
88 if(exterior.first == exterior.second)
89 return false;
90
91 const_iterator last_overlap = prior(exterior.second);
92
93 return
94 icl::contains(hull(exterior.first->first, last_overlap->first), sub_interval)
95 && Interval_Set::is_joinable(container, exterior.first, last_overlap);
96 }
97
98 template<class IntervalMapT>
99 typename enable_if<is_total<IntervalMapT>, bool>::type
contains(const IntervalMapT &,const typename IntervalMapT::interval_type &)100 contains(const IntervalMapT&,
101 const typename IntervalMapT::interval_type&)
102 {
103 return true;
104 }
105
106 //- set_type -------------------------------------------------------------------
107 template<class IntervalMapT, class IntervalSetT>
108 typename enable_if<mpl::and_<mpl::not_<is_total<IntervalMapT> >
109 ,is_interval_set<IntervalSetT> >, bool>::type
contains(const IntervalMapT & super_map,const IntervalSetT & sub_set)110 contains(const IntervalMapT& super_map, const IntervalSetT& sub_set)
111 {
112 return Interval_Set::within(sub_set, super_map);
113 }
114
115 template<class IntervalMapT, class IntervalSetT>
116 typename enable_if<mpl::and_<is_total<IntervalMapT>
117 ,is_interval_set<IntervalSetT> >, bool>::type
contains(const IntervalMapT &,const IntervalSetT &)118 contains(const IntervalMapT&, const IntervalSetT&)
119 {
120 return true;
121 }
122
123
124 //------------------------------------------------------------------------------
125 //- Containedness of sub objects
126 //------------------------------------------------------------------------------
127
128 template<class IntervalMapT>
contains(const IntervalMapT & container,const typename IntervalMapT::element_type & key_value_pair)129 bool contains(const IntervalMapT& container,
130 const typename IntervalMapT::element_type& key_value_pair)
131 {
132 typename IntervalMapT::const_iterator it_ = container.find(key_value_pair.key);
133 return it_ != container.end() && (*it_).second == key_value_pair.data;
134 }
135
136 template<class IntervalMapT>
contains(const IntervalMapT & container,const typename IntervalMapT::segment_type sub_segment)137 bool contains(const IntervalMapT& container,
138 const typename IntervalMapT::segment_type sub_segment)
139 {
140 typedef typename IntervalMapT::const_iterator const_iterator;
141 typename IntervalMapT::interval_type sub_interval = sub_segment.first;
142 if(icl::is_empty(sub_interval))
143 return true;
144
145 std::pair<const_iterator, const_iterator> exterior = container.equal_range(sub_interval);
146 if(exterior.first == exterior.second)
147 return false;
148
149 const_iterator last_overlap = prior(exterior.second);
150
151 if(!(sub_segment.second == exterior.first->second) )
152 return false;
153
154 return
155 icl::contains(hull(exterior.first->first, last_overlap->first), sub_interval)
156 && Interval_Map::is_joinable(container, exterior.first, last_overlap);
157 }
158
159
160 template<class IntervalMapT>
contains(const IntervalMapT & super,const IntervalMapT & sub)161 bool contains(const IntervalMapT& super, const IntervalMapT& sub)
162 {
163 return Interval_Set::within(sub, super);
164 }
165
166 } // namespace Interval_Map
167
168 }} // namespace icl boost
169
170 #endif
171
172