1 /*-----------------------------------------------------------------------------+
2 Copyright (c) 2008-2012: 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_HPP_JOFA_080705
9 #define BOOST_ICL_INTERVAL_MAP_HPP_JOFA_080705
10 
11 #include <boost/assert.hpp>
12 #include <boost/icl/type_traits/is_map.hpp>
13 #include <boost/icl/interval_set.hpp>
14 #include <boost/icl/interval_base_map.hpp>
15 
16 namespace boost{namespace icl
17 {
18 
19 template<class DomainT, class CodomainT, class Traits,
20          ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section,
21          ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
22 class split_interval_map;
23 
24 /** \brief implements a map as a map of intervals - on insertion
25     overlapping intervals are split and associated values are combined.*/
26 template
27 <
28     typename DomainT,
29     typename CodomainT,
30     class Traits = icl::partial_absorber,
31     ICL_COMPARE Compare  = ICL_COMPARE_INSTANCE(ICL_COMPARE_DEFAULT, DomainT),
32     ICL_COMBINE Combine  = ICL_COMBINE_INSTANCE(icl::inplace_plus, CodomainT),
33     ICL_SECTION Section  = ICL_SECTION_INSTANCE(icl::inter_section, CodomainT),
34     ICL_INTERVAL(ICL_COMPARE) Interval = ICL_INTERVAL_INSTANCE(ICL_INTERVAL_DEFAULT, DomainT, Compare),
35     ICL_ALLOC   Alloc    = std::allocator
36 >
37 class interval_map:
38 
39     public interval_base_map<interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>,
40                              DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
41 {
42 public:
43     typedef Traits traits;
44     typedef       interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> type;
45     typedef split_interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> split_type;
46     typedef type overloadable_type;
47     typedef type joint_type;
48     typedef interval_base_map<type,
49                               DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> base_type;
50 
51     typedef ICL_INTERVAL_TYPE(Interval,DomainT,Compare) interval_type;
52     typedef typename base_type::iterator      iterator;
53     typedef typename base_type::value_type    value_type;
54     typedef typename base_type::element_type  element_type;
55     typedef typename base_type::segment_type  segment_type;
56     typedef typename base_type::domain_type   domain_type;
57     typedef typename base_type::codomain_type codomain_type;
58     typedef typename base_type::domain_mapping_type domain_mapping_type;
59     typedef typename base_type::interval_mapping_type interval_mapping_type;
60     typedef typename base_type::ImplMapT ImplMapT;
61 
62     typedef typename base_type::size_type     size_type;
63     typedef typename base_type::codomain_combine codomain_combine;
64 
65     typedef interval_set<DomainT,Compare,Interval,Alloc> interval_set_type;
66     typedef interval_set_type set_type;
67     typedef set_type          key_object_type;
68 
69     enum { fineness = 1 };
70 
71 public:
72     //==========================================================================
73     //= Construct, copy, destruct
74     //==========================================================================
75 
76     /// Default constructor for the empty object
interval_map()77     interval_map(): base_type() {}
78 
79     /// Copy constructor
interval_map(const interval_map & src)80     interval_map(const interval_map& src): base_type(src) {}
81 
82     /// Copy constructor for base_type
83     template<class SubType>
interval_map(const interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> & src)84     explicit interval_map
85         (const interval_base_map<SubType,DomainT,CodomainT,
86                                  Traits,Compare,Combine,Section,Interval,Alloc>& src)
87     { this->assign(src); }
88 
interval_map(const domain_mapping_type & base_pair)89     explicit interval_map(const domain_mapping_type& base_pair): base_type()
90     { this->add(base_pair); }
91 
interval_map(const value_type & value_pair)92     explicit interval_map(const value_type& value_pair): base_type()
93     { this->add(value_pair); }
94 
95 
96     /// Assignment from a base interval_map.
97     template<class SubType>
assign(const interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> & src)98     void assign(const interval_base_map<SubType,DomainT,CodomainT,
99                                         Traits,Compare,Combine,Section,Interval,Alloc>& src)
100     {
101         typedef interval_base_map<SubType,DomainT,CodomainT,
102                                   Traits,Compare,Combine,Section,Interval,Alloc> base_map_type;
103         this->clear();
104         iterator prior_ = this->_map.end();
105         ICL_const_FORALL(typename base_map_type, it_, src)
106             prior_ = this->add(prior_, *it_);
107     }
108 
109     /// Assignment operator for base type
110     template<class SubType>
operator =(const interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> & src)111     interval_map& operator =
112         (const interval_base_map<SubType,DomainT,CodomainT,
113                                  Traits,Compare,Combine,Section,Interval,Alloc>& src)
114     {
115         this->assign(src);
116         return *this;
117     }
118 
119 #   ifndef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
120     //==========================================================================
121     //= Move semantics
122     //==========================================================================
123 
124     /// Move constructor
interval_map(interval_map && src)125     interval_map(interval_map&& src)
126         : base_type(boost::move(src))
127     {}
128 
129     /// Move assignment operator
operator =(interval_map src)130     interval_map& operator = (interval_map src)
131     {
132         base_type::operator=(boost::move(src));
133         return *this;
134     }
135 
136     //==========================================================================
137 #   else
138 
139     /// Assignment operator
operator =(const interval_map & src)140     interval_map& operator = (const interval_map& src)
141     {
142         base_type::operator=(src);
143         return *this;
144     }
145 
146 #   endif // BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
147 
148 private:
149     // Private functions that shall be accessible by the baseclass:
150     friend class
151         interval_base_map <interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>,
152                                         DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>;
153 
handle_inserted(iterator it_)154     iterator handle_inserted(iterator it_)
155     {
156         return segmental::join_neighbours(*this, it_);
157     }
158 
handle_inserted(iterator prior_,iterator it_)159     void handle_inserted(iterator prior_, iterator it_)
160     {
161         if(prior_ != this->_map.end() && segmental::joinable(*this, prior_, it_))
162             segmental::join_on_right(*this, prior_, it_);
163     }
164 
165     template<class Combiner>
handle_left_combined(iterator it_)166     void handle_left_combined(iterator it_)
167     {
168         if(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable((*it_).second))
169             this->_map.erase(it_);
170         else
171             segmental::join_left(*this, it_);
172     }
173 
174     template<class Combiner>
handle_combined(iterator it_)175     void handle_combined(iterator it_)
176     {
177         if(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable((*it_).second))
178             this->_map.erase(it_);
179         else
180             segmental::join_neighbours(*this, it_);
181     }
182 
183     template<class Combiner>
handle_preceeded_combined(iterator prior_,iterator & it_)184     void handle_preceeded_combined(iterator prior_, iterator& it_)
185     {
186         if(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable((*it_).second))
187         {
188             this->_map.erase(it_);
189             it_ = prior_;
190         }
191         else // After a new combination (e.g. combiner=max) joining neighbours may be possible
192             segmental::join_neighbours(*this, it_);
193     }
194 
195     template<class Combiner>
handle_succeeded_combined(iterator it_,iterator next_)196     void handle_succeeded_combined(iterator it_, iterator next_)
197     {
198         if(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable((*it_).second))
199         {
200             this->_map.erase(it_);
201             segmental::join_right(*this, next_);
202         }
203         else
204         {
205             segmental::join_left(*this, it_);
206             segmental::join_neighbours(*this, next_);
207         }
208     }
209 
210 
211 
handle_reinserted(iterator insertion_)212     void handle_reinserted(iterator insertion_)
213     {
214         segmental::join_right(*this, insertion_);
215     }
216 
217 
218     template<class Combiner>
gap_insert_at(iterator & it_,iterator prior_,const interval_type & end_gap,const codomain_type & co_val)219     void gap_insert_at(iterator& it_, iterator prior_,
220                        const interval_type& end_gap, const codomain_type& co_val)
221     {
222         if(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable((*it_).second))
223         {
224             this->_map.erase(it_);
225             it_ = this->template gap_insert<Combiner>(prior_, end_gap, co_val);
226             segmental::join_right(*this, it_);
227         }
228         else
229         {
230             segmental::join_left(*this, it_);
231             iterator inserted_ = this->template gap_insert<Combiner>(it_, end_gap, co_val);
232             it_ = segmental::join_neighbours(*this, inserted_);
233         }
234     }
235 
236 } ;
237 
238 
239 //-----------------------------------------------------------------------------
240 // type traits
241 //-----------------------------------------------------------------------------
242 template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
243 struct is_map<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
244 {
245     typedef is_map<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type;
246     BOOST_STATIC_CONSTANT(bool, value = true);
247 };
248 
249 template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
250 struct has_inverse<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
251 {
252     typedef has_inverse<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type;
253     BOOST_STATIC_CONSTANT(bool, value = (has_inverse<CodomainT>::value));
254 };
255 
256 
257 template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
258 struct is_interval_container<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
259 {
260     typedef is_interval_container<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type;
261     BOOST_STATIC_CONSTANT(bool, value = true);
262 };
263 
264 template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
265 struct absorbs_identities<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
266 {
267     typedef absorbs_identities<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type;
268     BOOST_STATIC_CONSTANT(bool, value = (Traits::absorbs_identities));
269 };
270 
271 template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
272 struct is_total<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
273 {
274     typedef is_total<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type;
275     BOOST_STATIC_CONSTANT(bool, value = (Traits::is_total));
276 };
277 
278 
279 //-----------------------------------------------------------------------------
280 // type representation
281 //-----------------------------------------------------------------------------
282 template <class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
283 struct type_to_string<icl::interval_map<DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
284 {
applyboost::icl::type_to_string285     static std::string apply()
286     {
287         return "itv_map<"+ type_to_string<DomainT>::apply()   + ","
288                          + type_to_string<CodomainT>::apply() + ","
289                          + type_to_string<Traits>::apply()    + ">";
290     }
291 };
292 
293 }} // namespace icl boost
294 
295 #endif
296 
297 
298