1 /*-----------------------------------------------------------------------------+
2 Copyright (c) 2007-2012: Joachim Faulhaber
3 Copyright (c) 1999-2006: Cortex Software GmbH, Kantstrasse 57, Berlin
4 +------------------------------------------------------------------------------+
5 Distributed under the Boost Software License, Version 1.0.
6 (See accompanying file LICENCE.txt or copy at
7 http://www.boost.org/LICENSE_1_0.txt)
8 +-----------------------------------------------------------------------------*/
9 #ifndef BOOST_ICL_INTERVAL_BASE_MAP_HPP_JOFA_990223
10 #define BOOST_ICL_INTERVAL_BASE_MAP_HPP_JOFA_990223
13 #include <boost/mpl/and.hpp>
14 #include <boost/mpl/or.hpp>
15 #include <boost/mpl/not.hpp>
17 #include <boost/icl/detail/notate.hpp>
18 #include <boost/icl/detail/design_config.hpp>
19 #include <boost/icl/detail/on_absorbtion.hpp>
20 #include <boost/icl/detail/interval_map_algo.hpp>
22 #include <boost/icl/associative_interval_container.hpp>
24 #include <boost/icl/type_traits/is_interval_splitter.hpp>
25 #include <boost/icl/map.hpp>
27 namespace boost{namespace icl
30 template<class DomainT, class CodomainT>
36 mapping_pair():key(), data(){}
38 mapping_pair(const DomainT& key_value, const CodomainT& data_value)
39 :key(key_value), data(data_value){}
41 mapping_pair(const std::pair<DomainT,CodomainT>& std_pair)
42 :key(std_pair.first), data(std_pair.second){}
45 /** \brief Implements a map as a map of intervals (base class) */
51 class Traits = icl::partial_absorber,
52 ICL_COMPARE Compare = ICL_COMPARE_INSTANCE(ICL_COMPARE_DEFAULT, DomainT),
53 ICL_COMBINE Combine = ICL_COMBINE_INSTANCE(icl::inplace_plus, CodomainT),
54 ICL_SECTION Section = ICL_SECTION_INSTANCE(icl::inter_section, CodomainT),
55 ICL_INTERVAL(ICL_COMPARE) Interval = ICL_INTERVAL_INSTANCE(ICL_INTERVAL_DEFAULT, DomainT, Compare),
56 ICL_ALLOC Alloc = std::allocator
58 class interval_base_map
61 //==========================================================================
63 //==========================================================================
64 typedef interval_base_map<SubType,DomainT,CodomainT,
65 Traits,Compare,Combine,Section,Interval,Alloc>
68 /// The designated \e derived or \e sub_type of this base class
69 typedef SubType sub_type;
71 /// Auxilliary type for overloadresolution
72 typedef type overloadable_type;
74 /// Traits of an itl map
75 typedef Traits traits;
77 //--------------------------------------------------------------------------
78 //- Associated types: Related types
79 //--------------------------------------------------------------------------
80 /// The atomized type representing the corresponding container of elements
81 typedef typename icl::map<DomainT,CodomainT,
82 Traits,Compare,Combine,Section,Alloc> atomized_type;
84 //--------------------------------------------------------------------------
85 //- Associated types: Data
86 //--------------------------------------------------------------------------
87 /// Domain type (type of the keys) of the map
88 typedef DomainT domain_type;
89 typedef typename boost::call_traits<DomainT>::param_type domain_param;
90 /// Domain type (type of the keys) of the map
91 typedef CodomainT codomain_type;
92 /// Auxiliary type to help the compiler resolve ambiguities when using std::make_pair
93 typedef mapping_pair<domain_type,codomain_type> domain_mapping_type;
94 /// Conceptual is a map a set of elements of type \c element_type
95 typedef domain_mapping_type element_type;
96 /// The interval type of the map
97 typedef ICL_INTERVAL_TYPE(Interval,DomainT,Compare) interval_type;
98 /// Auxiliary type for overload resolution
99 typedef std::pair<interval_type,CodomainT> interval_mapping_type;
100 /// Type of an interval containers segment, that is spanned by an interval
101 typedef std::pair<interval_type,CodomainT> segment_type;
103 //--------------------------------------------------------------------------
104 //- Associated types: Size
105 //--------------------------------------------------------------------------
106 /// The difference type of an interval which is sometimes different form the domain_type
107 typedef typename difference_type_of<domain_type>::type difference_type;
108 /// The size type of an interval which is mostly std::size_t
109 typedef typename size_type_of<domain_type>::type size_type;
111 //--------------------------------------------------------------------------
112 //- Associated types: Functors
113 //--------------------------------------------------------------------------
114 /// Comparison functor for domain values
115 typedef ICL_COMPARE_DOMAIN(Compare,DomainT) domain_compare;
116 typedef ICL_COMPARE_DOMAIN(Compare,segment_type) segment_compare;
117 /// Combine functor for codomain value aggregation
118 typedef ICL_COMBINE_CODOMAIN(Combine,CodomainT) codomain_combine;
119 /// Inverse Combine functor for codomain value aggregation
120 typedef typename inverse<codomain_combine>::type inverse_codomain_combine;
121 /// Intersection functor for codomain values
123 typedef typename mpl::if_
124 <has_set_semantics<codomain_type>
125 , ICL_SECTION_CODOMAIN(Section,CodomainT)
127 >::type codomain_intersect;
130 /// Inverse Combine functor for codomain value intersection
131 typedef typename inverse<codomain_intersect>::type inverse_codomain_intersect;
133 /// Comparison functor for intervals which are keys as well
134 typedef exclusive_less_than<interval_type> interval_compare;
136 /// Comparison functor for keys
137 typedef exclusive_less_than<interval_type> key_compare;
139 //--------------------------------------------------------------------------
140 //- Associated types: Implementation and stl related
141 //--------------------------------------------------------------------------
142 /// The allocator type of the set
143 typedef Alloc<std::pair<const interval_type, codomain_type> >
146 /// Container type for the implementation
147 typedef ICL_IMPL_SPACE::map<interval_type,codomain_type,
148 key_compare,allocator_type> ImplMapT;
150 /// key type of the implementing container
151 typedef typename ImplMapT::key_type key_type;
152 /// value type of the implementing container
153 typedef typename ImplMapT::value_type value_type;
154 /// data type of the implementing container
155 typedef typename ImplMapT::value_type::second_type data_type;
158 typedef typename ImplMapT::pointer pointer;
159 /// const pointer type
160 typedef typename ImplMapT::const_pointer const_pointer;
162 typedef typename ImplMapT::reference reference;
163 /// const reference type
164 typedef typename ImplMapT::const_reference const_reference;
166 /// iterator for iteration over intervals
167 typedef typename ImplMapT::iterator iterator;
168 /// const_iterator for iteration over intervals
169 typedef typename ImplMapT::const_iterator const_iterator;
170 /// iterator for reverse iteration over intervals
171 typedef typename ImplMapT::reverse_iterator reverse_iterator;
172 /// const_iterator for iteration over intervals
173 typedef typename ImplMapT::const_reverse_iterator const_reverse_iterator;
175 /// element iterator: Depreciated, see documentation.
176 typedef boost::icl::element_iterator<iterator> element_iterator;
177 /// const element iterator: Depreciated, see documentation.
178 typedef boost::icl::element_iterator<const_iterator> element_const_iterator;
179 /// element reverse iterator: Depreciated, see documentation.
180 typedef boost::icl::element_iterator<reverse_iterator> element_reverse_iterator;
181 /// element const reverse iterator: Depreciated, see documentation.
182 typedef boost::icl::element_iterator<const_reverse_iterator> element_const_reverse_iterator;
184 typedef typename on_absorbtion<type, codomain_combine,
185 Traits::absorbs_identities>::type on_codomain_absorbtion;
188 BOOST_STATIC_CONSTANT(bool,
189 is_total_invertible = ( Traits::is_total
190 && has_inverse<codomain_type>::value));
192 BOOST_STATIC_CONSTANT(int, fineness = 0);
196 //==========================================================================
197 //= Construct, copy, destruct
198 //==========================================================================
199 /** Default constructor for the empty object */
202 BOOST_CONCEPT_ASSERT((DefaultConstructibleConcept<DomainT>));
203 BOOST_CONCEPT_ASSERT((LessThanComparableConcept<DomainT>));
204 BOOST_CONCEPT_ASSERT((DefaultConstructibleConcept<CodomainT>));
205 BOOST_CONCEPT_ASSERT((EqualComparableConcept<CodomainT>));
208 /** Copy constructor */
209 interval_base_map(const interval_base_map& src): _map(src._map)
211 BOOST_CONCEPT_ASSERT((DefaultConstructibleConcept<DomainT>));
212 BOOST_CONCEPT_ASSERT((LessThanComparableConcept<DomainT>));
213 BOOST_CONCEPT_ASSERT((DefaultConstructibleConcept<CodomainT>));
214 BOOST_CONCEPT_ASSERT((EqualComparableConcept<CodomainT>));
217 # ifndef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
218 //==========================================================================
220 //==========================================================================
222 /** Move constructor */
223 interval_base_map(interval_base_map&& src): _map(boost::move(src._map))
225 BOOST_CONCEPT_ASSERT((DefaultConstructibleConcept<DomainT>));
226 BOOST_CONCEPT_ASSERT((LessThanComparableConcept<DomainT>));
227 BOOST_CONCEPT_ASSERT((DefaultConstructibleConcept<CodomainT>));
228 BOOST_CONCEPT_ASSERT((EqualComparableConcept<CodomainT>));
231 /** Move assignment operator */
232 interval_base_map& operator = (interval_base_map src)
233 { //call by value sice 'src' is a "sink value"
234 this->_map = boost::move(src._map);
238 //==========================================================================
241 /** Copy assignment operator */
242 interval_base_map& operator = (const interval_base_map& src)
244 this->_map = src._map;
248 # endif // BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
250 /** swap the content of containers */
251 void swap(interval_base_map& object) { _map.swap(object._map); }
253 //==========================================================================
255 //==========================================================================
257 void clear() { icl::clear(*that()); }
259 /** is the map empty? */
260 bool empty()const { return icl::is_empty(*that()); }
262 //==========================================================================
264 //==========================================================================
265 /** An interval map's size is it's cardinality */
266 size_type size()const
268 return icl::cardinality(*that());
271 /** Size of the iteration over this container */
272 std::size_t iterative_size()const
277 //==========================================================================
279 //==========================================================================
281 /** Find the interval value pair, that contains \c key */
282 const_iterator find(const domain_type& key_value)const
284 return icl::find(*this, key_value);
287 /** Find the first interval value pair, that collides with interval
289 const_iterator find(const interval_type& key_interval)const
291 return _map.find(key_interval);
294 /** Total select function. */
295 codomain_type operator()(const domain_type& key_value)const
297 const_iterator it_ = icl::find(*this, key_value);
298 return it_==end() ? identity_element<codomain_type>::value()
302 //==========================================================================
304 //==========================================================================
306 /** Addition of a key value pair to the map */
307 SubType& add(const element_type& key_value_pair)
309 return icl::add(*that(), key_value_pair);
312 /** Addition of an interval value pair to the map. */
313 SubType& add(const segment_type& interval_value_pair)
315 this->template _add<codomain_combine>(interval_value_pair);
319 /** Addition of an interval value pair \c interval_value_pair to the map.
320 Iterator \c prior_ is a hint to the position \c interval_value_pair can be
322 iterator add(iterator prior_, const segment_type& interval_value_pair)
324 return this->template _add<codomain_combine>(prior_, interval_value_pair);
327 //==========================================================================
329 //==========================================================================
330 /** Subtraction of a key value pair from the map */
331 SubType& subtract(const element_type& key_value_pair)
333 return icl::subtract(*that(), key_value_pair);
336 /** Subtraction of an interval value pair from the map. */
337 SubType& subtract(const segment_type& interval_value_pair)
339 on_invertible<type, is_total_invertible>
340 ::subtract(*that(), interval_value_pair);
344 //==========================================================================
346 //==========================================================================
347 /** Insertion of a \c key_value_pair into the map. */
348 SubType& insert(const element_type& key_value_pair)
350 return icl::insert(*that(), key_value_pair);
353 /** Insertion of an \c interval_value_pair into the map. */
354 SubType& insert(const segment_type& interval_value_pair)
356 _insert(interval_value_pair);
360 /** Insertion of an \c interval_value_pair into the map. Iterator \c prior_.
361 serves as a hint to insert after the element \c prior point to. */
362 iterator insert(iterator prior, const segment_type& interval_value_pair)
364 return _insert(prior, interval_value_pair);
367 /** With <tt>key_value_pair = (k,v)</tt> set value \c v for key \c k */
368 SubType& set(const element_type& key_value_pair)
370 return icl::set_at(*that(), key_value_pair);
373 /** With <tt>interval_value_pair = (I,v)</tt> set value \c v
374 for all keys in interval \c I in the map. */
375 SubType& set(const segment_type& interval_value_pair)
377 return icl::set_at(*that(), interval_value_pair);
380 //==========================================================================
382 //==========================================================================
383 /** Erase a \c key_value_pair from the map. */
384 SubType& erase(const element_type& key_value_pair)
386 icl::erase(*that(), key_value_pair);
390 /** Erase an \c interval_value_pair from the map. */
391 SubType& erase(const segment_type& interval_value_pair);
393 /** Erase a key value pair for \c key. */
394 SubType& erase(const domain_type& key)
396 return icl::erase(*that(), key);
399 /** Erase all value pairs within the range of the
400 interval <tt>inter_val</tt> from the map. */
401 SubType& erase(const interval_type& inter_val);
404 /** Erase all value pairs within the range of the interval that iterator
405 \c position points to. */
406 void erase(iterator position){ this->_map.erase(position); }
408 /** Erase all value pairs for a range of iterators <tt>[first,past)</tt>. */
409 void erase(iterator first, iterator past){ this->_map.erase(first, past); }
411 //==========================================================================
413 //==========================================================================
414 /** The intersection of \c interval_value_pair and \c *this map is added to \c section. */
415 void add_intersection(SubType& section, const segment_type& interval_value_pair)const
417 on_definedness<SubType, Traits::is_total>
418 ::add_intersection(section, *that(), interval_value_pair);
421 //==========================================================================
422 //= Symmetric difference
423 //==========================================================================
424 /** If \c *this map contains \c key_value_pair it is erased, otherwise it is added. */
425 SubType& flip(const element_type& key_value_pair)
427 return icl::flip(*that(), key_value_pair);
430 /** If \c *this map contains \c interval_value_pair it is erased, otherwise it is added. */
431 SubType& flip(const segment_type& interval_value_pair)
433 on_total_absorbable<SubType, Traits::is_total, Traits::absorbs_identities>
434 ::flip(*that(), interval_value_pair);
438 //==========================================================================
440 //==========================================================================
442 iterator lower_bound(const key_type& interval)
443 { return _map.lower_bound(interval); }
445 iterator upper_bound(const key_type& interval)
446 { return _map.upper_bound(interval); }
448 const_iterator lower_bound(const key_type& interval)const
449 { return _map.lower_bound(interval); }
451 const_iterator upper_bound(const key_type& interval)const
452 { return _map.upper_bound(interval); }
454 std::pair<iterator,iterator> equal_range(const key_type& interval)
456 return std::pair<iterator,iterator>
457 (lower_bound(interval), upper_bound(interval));
460 std::pair<const_iterator,const_iterator>
461 equal_range(const key_type& interval)const
463 return std::pair<const_iterator,const_iterator>
464 (lower_bound(interval), upper_bound(interval));
467 iterator begin() { return _map.begin(); }
468 iterator end() { return _map.end(); }
469 const_iterator begin()const { return _map.begin(); }
470 const_iterator end()const { return _map.end(); }
471 reverse_iterator rbegin() { return _map.rbegin(); }
472 reverse_iterator rend() { return _map.rend(); }
473 const_reverse_iterator rbegin()const { return _map.rbegin(); }
474 const_reverse_iterator rend()const { return _map.rend(); }
477 template<class Combiner>
478 iterator _add(const segment_type& interval_value_pair);
480 template<class Combiner>
481 iterator _add(iterator prior_, const segment_type& interval_value_pair);
483 template<class Combiner>
484 void _subtract(const segment_type& interval_value_pair);
486 iterator _insert(const segment_type& interval_value_pair);
487 iterator _insert(iterator prior_, const segment_type& interval_value_pair);
490 template<class Combiner>
491 void add_segment(const interval_type& inter_val, const CodomainT& co_val, iterator& it_);
493 template<class Combiner>
494 void add_main(interval_type& inter_val, const CodomainT& co_val,
495 iterator& it_, const iterator& last_);
497 template<class Combiner>
498 void add_rear(const interval_type& inter_val, const CodomainT& co_val, iterator& it_);
500 void add_front(const interval_type& inter_val, iterator& first_);
503 void subtract_front(const interval_type& inter_val, iterator& first_);
505 template<class Combiner>
506 void subtract_main(const CodomainT& co_val, iterator& it_, const iterator& last_);
508 template<class Combiner>
509 void subtract_rear(interval_type& inter_val, const CodomainT& co_val, iterator& it_);
512 void insert_main(const interval_type&, const CodomainT&, iterator&, const iterator&);
513 void erase_rest ( interval_type&, const CodomainT&, iterator&, const iterator&);
515 template<class FragmentT>
516 void total_add_intersection(SubType& section, const FragmentT& fragment)const
519 section.add(fragment);
522 void partial_add_intersection(SubType& section, const segment_type& operand)const
524 interval_type inter_val = operand.first;
525 if(icl::is_empty(inter_val))
528 std::pair<const_iterator, const_iterator> exterior = equal_range(inter_val);
529 if(exterior.first == exterior.second)
532 for(const_iterator it_=exterior.first; it_ != exterior.second; it_++)
534 interval_type common_interval = (*it_).first & inter_val;
535 if(!icl::is_empty(common_interval))
537 section.template _add<codomain_combine> (value_type(common_interval, (*it_).second) );
538 section.template _add<codomain_intersect>(value_type(common_interval, operand.second));
543 void partial_add_intersection(SubType& section, const element_type& operand)const
545 partial_add_intersection(section, make_segment<type>(operand));
551 template <class Combiner>
552 iterator gap_insert(iterator prior_, const interval_type& inter_val,
553 const codomain_type& co_val )
555 // inter_val is not conained in this map. Insertion will be successful
556 BOOST_ASSERT(this->_map.find(inter_val) == this->_map.end());
557 BOOST_ASSERT((!on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable(co_val)));
558 return this->_map.insert(prior_, value_type(inter_val, version<Combiner>()(co_val)));
561 template <class Combiner>
562 std::pair<iterator, bool>
563 add_at(const iterator& prior_, const interval_type& inter_val,
564 const codomain_type& co_val )
566 // Never try to insert an identity element into an identity element absorber here:
567 BOOST_ASSERT((!(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable(co_val))));
570 = this->_map.insert(prior_, value_type(inter_val, Combiner::identity_element()));
572 if((*inserted_).first == inter_val && (*inserted_).second == Combiner::identity_element())
574 Combiner()((*inserted_).second, co_val);
575 return std::pair<iterator,bool>(inserted_, true);
578 return std::pair<iterator,bool>(inserted_, false);
581 std::pair<iterator, bool>
582 insert_at(const iterator& prior_, const interval_type& inter_val,
583 const codomain_type& co_val )
586 = this->_map.insert(prior_, value_type(inter_val, co_val));
588 if(inserted_ == prior_)
589 return std::pair<iterator,bool>(inserted_, false);
590 else if((*inserted_).first == inter_val)
591 return std::pair<iterator,bool>(inserted_, true);
593 return std::pair<iterator,bool>(inserted_, false);
598 sub_type* that() { return static_cast<sub_type*>(this); }
599 const sub_type* that()const { return static_cast<const sub_type*>(this); }
606 //--------------------------------------------------------------------------
607 template<class Type, bool is_total_invertible>
608 struct on_invertible;
611 struct on_invertible<Type, true>
613 typedef typename Type::segment_type segment_type;
614 typedef typename Type::inverse_codomain_combine inverse_codomain_combine;
616 static void subtract(Type& object, const segment_type& operand)
617 { object.template _add<inverse_codomain_combine>(operand); }
621 struct on_invertible<Type, false>
623 typedef typename Type::segment_type segment_type;
624 typedef typename Type::inverse_codomain_combine inverse_codomain_combine;
626 static void subtract(Type& object, const segment_type& operand)
627 { object.template _subtract<inverse_codomain_combine>(operand); }
630 friend struct on_invertible<type, true>;
631 friend struct on_invertible<type, false>;
632 //--------------------------------------------------------------------------
634 //--------------------------------------------------------------------------
635 template<class Type, bool is_total>
636 struct on_definedness;
639 struct on_definedness<Type, true>
641 static void add_intersection(Type& section, const Type& object,
642 const segment_type& operand)
643 { object.total_add_intersection(section, operand); }
647 struct on_definedness<Type, false>
649 static void add_intersection(Type& section, const Type& object,
650 const segment_type& operand)
651 { object.partial_add_intersection(section, operand); }
654 friend struct on_definedness<type, true>;
655 friend struct on_definedness<type, false>;
656 //--------------------------------------------------------------------------
658 //--------------------------------------------------------------------------
659 template<class Type, bool has_set_semantics>
660 struct on_codomain_model;
663 struct on_codomain_model<Type, true>
665 typedef typename Type::interval_type interval_type;
666 typedef typename Type::codomain_type codomain_type;
667 typedef typename Type::segment_type segment_type;
668 typedef typename Type::codomain_combine codomain_combine;
669 typedef typename Type::inverse_codomain_intersect inverse_codomain_intersect;
671 static void add(Type& intersection, interval_type& common_interval,
672 const codomain_type& flip_value, const codomain_type& co_value)
674 codomain_type common_value = flip_value;
675 inverse_codomain_intersect()(common_value, co_value);
676 intersection.template
677 _add<codomain_combine>(segment_type(common_interval, common_value));
682 struct on_codomain_model<Type, false>
684 typedef typename Type::interval_type interval_type;
685 typedef typename Type::codomain_type codomain_type;
686 typedef typename Type::segment_type segment_type;
687 typedef typename Type::codomain_combine codomain_combine;
689 static void add(Type& intersection, interval_type& common_interval,
690 const codomain_type&, const codomain_type&)
692 intersection.template
693 _add<codomain_combine>(segment_type(common_interval,
694 identity_element<codomain_type>::value()));
698 friend struct on_codomain_model<type, true>;
699 friend struct on_codomain_model<type, false>;
700 //--------------------------------------------------------------------------
703 //--------------------------------------------------------------------------
704 template<class Type, bool is_total, bool absorbs_identities>
705 struct on_total_absorbable;
708 struct on_total_absorbable<Type, true, true>
710 static void flip(Type& object, const typename Type::segment_type&)
711 { icl::clear(object); }
715 #pragma warning(push)
716 #pragma warning(disable:4127) // conditional expression is constant
720 struct on_total_absorbable<Type, true, false>
722 typedef typename Type::segment_type segment_type;
723 typedef typename Type::codomain_type codomain_type;
725 static void flip(Type& object, const segment_type& operand)
728 ICL_FORALL(typename Type, it_, object)
729 (*it_).second = identity_element<codomain_type>::value();
731 if(mpl::not_<is_interval_splitter<Type> >::value)
740 template<class Type, bool absorbs_identities>
741 struct on_total_absorbable<Type, false, absorbs_identities>
743 typedef typename Type::segment_type segment_type;
744 typedef typename Type::codomain_type codomain_type;
745 typedef typename Type::interval_type interval_type;
746 typedef typename Type::value_type value_type;
747 typedef typename Type::const_iterator const_iterator;
748 typedef typename Type::set_type set_type;
749 typedef typename Type::inverse_codomain_intersect inverse_codomain_intersect;
751 static void flip(Type& object, const segment_type& interval_value_pair)
753 // That which is common shall be subtracted
754 // That which is not shall be added
755 // So interval_value_pair has to be 'complementary added' or flipped
756 interval_type span = interval_value_pair.first;
757 std::pair<const_iterator, const_iterator> exterior
758 = object.equal_range(span);
760 const_iterator first_ = exterior.first;
761 const_iterator end_ = exterior.second;
763 interval_type covered, left_over, common_interval;
764 const codomain_type& x_value = interval_value_pair.second;
765 const_iterator it_ = first_;
772 const codomain_type& co_value = (*it_).second;
773 covered = (*it_++).first;
777 left_over = right_subtract(span, covered);
779 //That which is common ...
780 common_interval = span & covered;
781 if(!icl::is_empty(common_interval))
783 // ... shall be subtracted
784 icl::add(eraser, common_interval);
786 on_codomain_model<Type, has_set_semantics<codomain_type>::value>
787 ::add(intersection, common_interval, x_value, co_value);
790 icl::add(object, value_type(left_over, x_value)); //That which is not shall be added
791 // Because this is a collision free addition I don't have to distinguish codomain_types.
796 span = left_subtract(span, covered);
799 //If span is not empty here, it is not in the set so it shall be added
800 icl::add(object, value_type(span, x_value));
802 //finally rewrite the common segments
803 icl::erase(object, eraser);
804 object += intersection;
807 //--------------------------------------------------------------------------
811 //==============================================================================
813 //==============================================================================
814 template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
815 inline void interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
816 ::add_front(const interval_type& inter_val, iterator& first_)
818 // If the collision sequence has a left residual 'left_resid' it will
819 // be split, to provide a standardized start of algorithms:
820 // The addend interval 'inter_val' covers the beginning of the collision sequence.
822 // only for the first there can be a left_resid: a part of *first_ left of inter_val
823 interval_type left_resid = right_subtract((*first_).first, inter_val);
825 if(!icl::is_empty(left_resid))
826 { // [------------ . . .
827 // [left_resid---first_ --- . . .
828 iterator prior_ = cyclic_prior(*this, first_);
829 const_cast<interval_type&>((*first_).first)
830 = left_subtract((*first_).first, left_resid);
831 //NOTE: Only splitting
832 this->_map.insert(prior_, segment_type(left_resid, (*first_).second));
835 // [----- inter_val ---- . . .
836 // ...[-- first_ --...
839 template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
840 template<class Combiner>
841 inline void interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
842 ::add_segment(const interval_type& inter_val, const CodomainT& co_val, iterator& it_)
844 interval_type lead_gap = right_subtract(inter_val, (*it_).first);
845 if(!icl::is_empty(lead_gap))
847 // [lead_gap--- . . .
849 iterator prior_ = it_==this->_map.begin()? it_ : prior(it_);
850 iterator inserted_ = this->template gap_insert<Combiner>(prior_, lead_gap, co_val);
851 that()->handle_inserted(prior_, inserted_);
854 // . . . --------- . . . addend interval
855 // [-- it_ --) has a common part with the first overval
856 Combiner()((*it_).second, co_val);
857 that()->template handle_left_combined<Combiner>(it_++);
861 template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
862 template<class Combiner>
863 inline void interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
864 ::add_main(interval_type& inter_val, const CodomainT& co_val,
865 iterator& it_, const iterator& last_)
867 interval_type cur_interval;
870 cur_interval = (*it_).first ;
871 add_segment<Combiner>(inter_val, co_val, it_);
873 inter_val = left_subtract(inter_val, cur_interval);
877 template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
878 template<class Combiner>
879 inline void interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
880 ::add_rear(const interval_type& inter_val, const CodomainT& co_val, iterator& it_)
882 iterator prior_ = cyclic_prior(*that(), it_);
883 interval_type cur_itv = (*it_).first ;
885 interval_type lead_gap = right_subtract(inter_val, cur_itv);
886 if(!icl::is_empty(lead_gap))
887 { // [lead_gap--- . . .
888 // [prior) [-- it_ ...
889 iterator inserted_ = this->template gap_insert<Combiner>(prior_, lead_gap, co_val);
890 that()->handle_inserted(prior_, inserted_);
893 interval_type end_gap = left_subtract(inter_val, cur_itv);
894 if(!icl::is_empty(end_gap))
896 // [----------------end_gap)
898 Combiner()((*it_).second, co_val);
899 that()->template gap_insert_at<Combiner>(it_, prior_, end_gap, co_val);
903 // only for the last there can be a right_resid: a part of *it_ right of x
904 interval_type right_resid = left_subtract(cur_itv, inter_val);
906 if(icl::is_empty(right_resid))
910 Combiner()((*it_).second, co_val);
911 that()->template handle_preceeded_combined<Combiner>(prior_, it_);
916 // [-- it_ --right_resid)
917 const_cast<interval_type&>((*it_).first) = right_subtract((*it_).first, right_resid);
919 //NOTE: This is NOT an insertion that has to take care for correct application of
920 // the Combiner functor. It only reestablished that state after splitting the
921 // 'it_' interval value pair. Using _map_insert<Combiner> does not work here.
922 iterator insertion_ = this->_map.insert(it_, value_type(right_resid, (*it_).second));
923 that()->handle_reinserted(insertion_);
925 Combiner()((*it_).second, co_val);
926 that()->template handle_preceeded_combined<Combiner>(insertion_, it_);
932 //==============================================================================
934 //==============================================================================
935 template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
936 template<class Combiner>
937 inline typename interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>::iterator
938 interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
939 ::_add(const segment_type& addend)
941 typedef typename on_absorbtion<type,Combiner,
942 absorbs_identities<type>::value>::type on_absorbtion_;
944 const interval_type& inter_val = addend.first;
945 if(icl::is_empty(inter_val))
946 return this->_map.end();
948 const codomain_type& co_val = addend.second;
949 if(on_absorbtion_::is_absorbable(co_val))
950 return this->_map.end();
952 std::pair<iterator,bool> insertion
953 = this->_map.insert(value_type(inter_val, version<Combiner>()(co_val)));
956 return that()->handle_inserted(insertion.first);
959 // Detect the first and the end iterator of the collision sequence
960 iterator first_ = this->_map.lower_bound(inter_val),
961 last_ = prior(this->_map.upper_bound(inter_val));
962 //assert(end_ == this->_map.upper_bound(inter_val));
963 iterator it_ = first_;
964 interval_type rest_interval = inter_val;
966 add_front (rest_interval, it_ );
967 add_main<Combiner>(rest_interval, co_val, it_, last_);
968 add_rear<Combiner>(rest_interval, co_val, it_ );
973 template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
974 template<class Combiner>
975 inline typename interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>::iterator
976 interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
977 ::_add(iterator prior_, const segment_type& addend)
979 typedef typename on_absorbtion<type,Combiner,
980 absorbs_identities<type>::value>::type on_absorbtion_;
982 const interval_type& inter_val = addend.first;
983 if(icl::is_empty(inter_val))
986 const codomain_type& co_val = addend.second;
987 if(on_absorbtion_::is_absorbable(co_val))
990 std::pair<iterator,bool> insertion
991 = add_at<Combiner>(prior_, inter_val, co_val);
994 return that()->handle_inserted(insertion.first);
997 // Detect the first and the end iterator of the collision sequence
998 std::pair<iterator,iterator> overlap = equal_range(inter_val);
999 iterator it_ = overlap.first,
1000 last_ = prior(overlap.second);
1001 interval_type rest_interval = inter_val;
1003 add_front (rest_interval, it_ );
1004 add_main<Combiner>(rest_interval, co_val, it_, last_);
1005 add_rear<Combiner>(rest_interval, co_val, it_ );
1010 //==============================================================================
1011 //= Subtraction detail
1012 //==============================================================================
1014 template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
1015 inline void interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
1016 ::subtract_front(const interval_type& inter_val, iterator& it_)
1018 interval_type left_resid = right_subtract((*it_).first, inter_val);
1020 if(!icl::is_empty(left_resid)) // [--- inter_val ---)
1021 { //[prior_) [left_resid)[--- it_ . . .
1022 iterator prior_ = cyclic_prior(*this, it_);
1023 const_cast<interval_type&>((*it_).first) = left_subtract((*it_).first, left_resid);
1024 this->_map.insert(prior_, value_type(left_resid, (*it_).second));
1025 // The segemnt *it_ is split at inter_val.first(), so as an invariant
1026 // segment *it_ is always "under" inter_val and a left_resid is empty.
1031 template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
1032 template<class Combiner>
1033 inline void interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
1034 ::subtract_main(const CodomainT& co_val, iterator& it_, const iterator& last_)
1038 Combiner()((*it_).second, co_val);
1039 that()->template handle_left_combined<Combiner>(it_++);
1043 template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
1044 template<class Combiner>
1045 inline void interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
1046 ::subtract_rear(interval_type& inter_val, const CodomainT& co_val, iterator& it_)
1048 interval_type right_resid = left_subtract((*it_).first, inter_val);
1050 if(icl::is_empty(right_resid))
1052 Combiner()((*it_).second, co_val);
1053 that()->template handle_combined<Combiner>(it_);
1057 const_cast<interval_type&>((*it_).first) = right_subtract((*it_).first, right_resid);
1058 iterator next_ = this->_map.insert(it_, value_type(right_resid, (*it_).second));
1059 Combiner()((*it_).second, co_val);
1060 that()->template handle_succeeded_combined<Combiner>(it_, next_);
1064 //==============================================================================
1066 //==============================================================================
1067 template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
1068 template<class Combiner>
1069 inline void interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
1070 ::_subtract(const segment_type& minuend)
1072 interval_type inter_val = minuend.first;
1073 if(icl::is_empty(inter_val))
1076 const codomain_type& co_val = minuend.second;
1077 if(on_absorbtion<type,Combiner,Traits::absorbs_identities>::is_absorbable(co_val))
1080 std::pair<iterator, iterator> exterior = equal_range(inter_val);
1081 if(exterior.first == exterior.second)
1084 iterator last_ = prior(exterior.second);
1085 iterator it_ = exterior.first;
1086 subtract_front (inter_val, it_ );
1087 subtract_main <Combiner>( co_val, it_, last_);
1088 subtract_rear <Combiner>(inter_val, co_val, it_ );
1091 //==============================================================================
1093 //==============================================================================
1094 template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
1095 inline void interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
1096 ::insert_main(const interval_type& inter_val, const CodomainT& co_val,
1097 iterator& it_, const iterator& last_)
1099 iterator end_ = boost::next(last_);
1100 iterator prior_ = cyclic_prior(*this,it_), inserted_;
1101 interval_type rest_interval = inter_val, left_gap, cur_itv;
1102 interval_type last_interval = last_ ->first;
1106 cur_itv = (*it_).first ;
1107 left_gap = right_subtract(rest_interval, cur_itv);
1109 if(!icl::is_empty(left_gap))
1111 inserted_ = this->_map.insert(prior_, value_type(left_gap, co_val));
1112 it_ = that()->handle_inserted(inserted_);
1116 rest_interval = left_subtract(rest_interval, cur_itv);
1121 //insert_rear(rest_interval, co_val, last_):
1122 interval_type end_gap = left_subtract(rest_interval, last_interval);
1123 if(!icl::is_empty(end_gap))
1125 inserted_ = this->_map.insert(prior_, value_type(end_gap, co_val));
1126 it_ = that()->handle_inserted(inserted_);
1133 template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
1134 inline typename interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>::iterator
1135 interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
1136 ::_insert(const segment_type& addend)
1138 interval_type inter_val = addend.first;
1139 if(icl::is_empty(inter_val))
1140 return this->_map.end();
1142 const codomain_type& co_val = addend.second;
1143 if(on_codomain_absorbtion::is_absorbable(co_val))
1144 return this->_map.end();
1146 std::pair<iterator,bool> insertion = this->_map.insert(addend);
1148 if(insertion.second)
1149 return that()->handle_inserted(insertion.first);
1152 // Detect the first and the end iterator of the collision sequence
1153 iterator first_ = this->_map.lower_bound(inter_val),
1154 last_ = prior(this->_map.upper_bound(inter_val));
1155 //assert((++last_) == this->_map.upper_bound(inter_val));
1156 iterator it_ = first_;
1157 insert_main(inter_val, co_val, it_, last_);
1163 template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
1164 inline typename interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>::iterator
1165 interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
1166 ::_insert(iterator prior_, const segment_type& addend)
1168 interval_type inter_val = addend.first;
1169 if(icl::is_empty(inter_val))
1172 const codomain_type& co_val = addend.second;
1173 if(on_codomain_absorbtion::is_absorbable(co_val))
1176 std::pair<iterator,bool> insertion = insert_at(prior_, inter_val, co_val);
1178 if(insertion.second)
1179 return that()->handle_inserted(insertion.first);
1181 // Detect the first and the end iterator of the collision sequence
1182 std::pair<iterator,iterator> overlap = equal_range(inter_val);
1183 iterator it_ = overlap.first,
1184 last_ = prior(overlap.second);
1185 insert_main(inter_val, co_val, it_, last_);
1190 //==============================================================================
1191 //= Erasure segment_type
1192 //==============================================================================
1193 template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
1194 inline void interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
1195 ::erase_rest(interval_type& inter_val, const CodomainT& co_val,
1196 iterator& it_, const iterator& last_)
1198 // For all intervals within loop: (*it_).first are contained_in inter_val
1200 if((*it_).second == co_val)
1201 this->_map.erase(it_++);
1205 if((*it_).second == co_val)
1207 interval_type right_resid = left_subtract((*it_).first, inter_val);
1208 if(icl::is_empty(right_resid))
1209 this->_map.erase(it_);
1211 const_cast<interval_type&>((*it_).first) = right_resid;
1215 template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
1216 inline SubType& interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
1217 ::erase(const segment_type& minuend)
1219 interval_type inter_val = minuend.first;
1220 if(icl::is_empty(inter_val))
1223 const codomain_type& co_val = minuend.second;
1224 if(on_codomain_absorbtion::is_absorbable(co_val))
1227 std::pair<iterator,iterator> exterior = equal_range(inter_val);
1228 if(exterior.first == exterior.second)
1231 iterator first_ = exterior.first, end_ = exterior.second,
1232 last_ = cyclic_prior(*this, end_);
1233 iterator second_= first_; ++second_;
1236 { // [----inter_val----)
1237 // .....first_==last_.....
1238 // only for the last there can be a right_resid: a part of *it_ right of minuend
1239 interval_type right_resid = left_subtract((*first_).first, inter_val);
1241 if((*first_).second == co_val)
1243 interval_type left_resid = right_subtract((*first_).first, inter_val);
1244 if(!icl::is_empty(left_resid)) // [----inter_val----)
1245 { // [left_resid)..first_==last_......
1246 const_cast<interval_type&>((*first_).first) = left_resid;
1247 if(!icl::is_empty(right_resid))
1248 this->_map.insert(first_, value_type(right_resid, co_val));
1250 else if(!icl::is_empty(right_resid))
1251 const_cast<interval_type&>((*first_).first) = right_resid;
1253 this->_map.erase(first_);
1258 // first AND NOT last
1259 if((*first_).second == co_val)
1261 interval_type left_resid = right_subtract((*first_).first, inter_val);
1262 if(icl::is_empty(left_resid))
1263 this->_map.erase(first_);
1265 const_cast<interval_type&>((*first_).first) = left_resid;
1268 erase_rest(inter_val, co_val, second_, last_);
1274 //==============================================================================
1275 //= Erasure key_type
1276 //==============================================================================
1277 template <class SubType, class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
1278 inline SubType& interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>
1279 ::erase(const interval_type& minuend)
1281 if(icl::is_empty(minuend))
1284 std::pair<iterator, iterator> exterior = equal_range(minuend);
1285 if(exterior.first == exterior.second)
1288 iterator first_ = exterior.first,
1289 end_ = exterior.second,
1290 last_ = prior(end_);
1292 interval_type left_resid = right_subtract((*first_).first, minuend);
1293 interval_type right_resid = left_subtract(last_ ->first, minuend);
1295 if(first_ == last_ )
1296 if(!icl::is_empty(left_resid))
1298 const_cast<interval_type&>((*first_).first) = left_resid;
1299 if(!icl::is_empty(right_resid))
1300 this->_map.insert(first_, value_type(right_resid, (*first_).second));
1302 else if(!icl::is_empty(right_resid))
1303 const_cast<interval_type&>((*first_).first) = left_subtract((*first_).first, minuend);
1305 this->_map.erase(first_);
1307 { // [-------- minuend ---------)
1308 // [left_resid fst) . . . . [lst right_resid)
1309 iterator second_= first_; ++second_;
1311 iterator start_ = icl::is_empty(left_resid)? first_: second_;
1312 iterator stop_ = icl::is_empty(right_resid)? end_ : last_ ;
1313 this->_map.erase(start_, stop_); //erase [start_, stop_)
1315 if(!icl::is_empty(left_resid))
1316 const_cast<interval_type&>((*first_).first) = left_resid;
1318 if(!icl::is_empty(right_resid))
1319 const_cast<interval_type&>(last_ ->first) = right_resid;
1325 //-----------------------------------------------------------------------------
1327 //-----------------------------------------------------------------------------
1331 class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc
1333 struct is_map<icl::interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
1335 typedef is_map<icl::interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type;
1336 BOOST_STATIC_CONSTANT(bool, value = true);
1342 class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc
1344 struct has_inverse<icl::interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
1346 typedef has_inverse<icl::interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type;
1347 BOOST_STATIC_CONSTANT(bool, value = (has_inverse<CodomainT>::value));
1353 class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc
1355 struct is_interval_container<icl::interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
1357 typedef is_interval_container<icl::interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type;
1358 BOOST_STATIC_CONSTANT(bool, value = true);
1364 class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc
1366 struct absorbs_identities<icl::interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
1368 typedef absorbs_identities<icl::interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type;
1369 BOOST_STATIC_CONSTANT(bool, value = (Traits::absorbs_identities));
1375 class DomainT, class CodomainT, class Traits, ICL_COMPARE Compare, ICL_COMBINE Combine, ICL_SECTION Section, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc
1377 struct is_total<icl::interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> >
1379 typedef is_total<icl::interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc> > type;
1380 BOOST_STATIC_CONSTANT(bool, value = (Traits::is_total));
1385 }} // namespace icl boost