]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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> | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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> | |
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> | |
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> | |
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 |