|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r49668 - in sandbox/itl: boost/itl libs/itl/test libs/itl/test/test_interval_map_mixed libs/itl/test/test_interval_set_mixed
From: afojgo_at_[hidden]
Date: 2008-11-09 16:54:44
Author: jofaber
Date: 2008-11-09 16:54:41 EST (Sun, 09 Nov 2008)
New Revision: 49668
URL: http://svn.boost.org/trac/boost/changeset/49668
Log:
Refactored contained_in(). Prepared interval for generic Compare order. Stable {msvc-9.0}
Text files modified:
sandbox/itl/boost/itl/interval.hpp | 177 ++++++++++++++++++---------------
sandbox/itl/boost/itl/interval_base_set.hpp | 2
sandbox/itl/boost/itl/interval_map.hpp | 15 -
sandbox/itl/boost/itl/interval_map_algo.hpp | 32 ++++++
sandbox/itl/boost/itl/interval_maps.hpp | 19 +++
sandbox/itl/boost/itl/interval_set_algo.hpp | 210 +++++++++++++++++++++++++++++++--------
sandbox/itl/boost/itl/interval_sets.hpp | 17 +++
sandbox/itl/boost/itl/separate_interval_set.hpp | 2
sandbox/itl/boost/itl/set_algo.hpp | 3
sandbox/itl/boost/itl/split_interval_map.hpp | 10 -
sandbox/itl/boost/itl/split_interval_set.hpp | 20 ---
sandbox/itl/libs/itl/test/test_interval_map_mixed/test_interval_map_mixed.cpp | 4
sandbox/itl/libs/itl/test/test_interval_set_mixed/test_interval_set_mixed.cpp | 1
sandbox/itl/libs/itl/test/test_interval_set_shared.hpp | 1
sandbox/itl/libs/itl/test/test_type_lists.hpp | 6 +
15 files changed, 348 insertions(+), 171 deletions(-)
Modified: sandbox/itl/boost/itl/interval.hpp
==============================================================================
--- sandbox/itl/boost/itl/interval.hpp (original)
+++ sandbox/itl/boost/itl/interval.hpp 2008-11-09 16:54:41 EST (Sun, 09 Nov 2008)
@@ -495,7 +495,7 @@
{
if(empty())
return itl::neutron<size_type>::value();
- else if(is_closed() && _lwb == _upb)
+ else if(is_closed() && data_equal(_lwb, _upb))
return itl::unon<size_type>::value();
else
return std::numeric_limits<size_type>::infinity();
@@ -558,6 +558,12 @@
bool lower_equal(const interval& x2)const;
bool upper_equal(const interval& x2)const;
+public:
+ typedef typename boost::call_traits<DataT>::param_type DataP;
+ inline static bool data_less(DataP left, DataP right) {return left < right ;}
+ inline static bool data_less_equal(DataP left, DataP right) {return !(right < left );}
+ inline static bool data_equal(DataP left, DataP right) {return !(left < right) && !(right < left);}
+
private:
// public?
typedef std::pair<DataT, bound_types> BoundT;
@@ -622,22 +628,28 @@
}
-template<class DataT>
+template<class IntervalT>
struct continuous_type
{
- typedef typename boost::call_traits<DataT>::param_type DataP;
+ typedef typename IntervalT::data_type data_type;
+ typedef typename boost::call_traits<data_type>::param_type DataP;
- static bool open_bound_less_equal(DataP x, DataP y) { return x <= y; }
- static bool open_bound_less (DataP x, DataP y) { return x < y; }
+ static bool open_bound_less_equal(DataP x, DataP y)
+ { return IntervalT::data_less_equal(x,y); } //{ return x <= y; }
+ static bool open_bound_less (DataP x, DataP y)
+ { return IntervalT::data_less(x,y); } //{ return x < y; }
};
-template<class DataT>
+template<class IntervalT>
struct discrete_type
{
- typedef typename boost::call_traits<DataT>::param_type DataP;
+ typedef typename IntervalT::data_type data_type;
+ typedef typename boost::call_traits<data_type>::param_type DataP;
- static bool open_bound_less_equal(DataP x, DataP y) { return x <= succ(y); }
- static bool open_bound_less (DataP x, DataP y) { return succ(x) < y ; }
+ static bool open_bound_less_equal(DataP x, DataP y)
+ { return IntervalT::data_less_equal(x, succ(y)); } //{ return x <= succ(y); }
+ static bool open_bound_less (DataP x, DataP y)
+ { return IntervalT::data_less(succ(x),y); } //{ return succ(x) < y ; }
};
template <class DataT>
@@ -645,72 +657,74 @@
{
using namespace boost::mpl;
- if(rightbound_closed() && leftbound_closed()) return _upb < _lwb;
- if(rightbound_open() && leftbound_closed()) return _upb <= _lwb;
- if(rightbound_closed() && leftbound_open()) return _upb <= _lwb;
+ if(rightbound_closed() && leftbound_closed()) return data_less(_upb, _lwb); //_upb < _lwb;
+ if(rightbound_open() && leftbound_closed()) return data_less_equal(_upb, _lwb); //_upb <= _lwb;
+ if(rightbound_closed() && leftbound_open()) return data_less_equal(_upb, _lwb); //_upb <= _lwb;
// OTHERWISE (rightbound_open() && leftbound_open())
return
if_<
bool_<is_continuous<DataT>::value>,
- continuous_type<DataT>,
- discrete_type<DataT>
+ continuous_type<interval<DataT> >,
+ discrete_type<interval<DataT> >
>
::type::open_bound_less_equal(_upb, _lwb);
}
-template<class DataT>
+template<class IntervalT>
struct continuous_interval
{
- static typename itl::interval<DataT>::size_type
- cardinality(const interval<DataT>& x)
+ static typename IntervalT::size_type
+ cardinality(const IntervalT& x)
{ return x.continuous_cardinality(); }
- static typename itl::interval<DataT>::difference_type
- length(const interval<DataT>& x)
+ static typename IntervalT::difference_type
+ length(const IntervalT& x)
{ return x.continuous_length(); }
- static bool unaligned_lwb_equal(const interval<DataT>& x1, const interval<DataT>& x2)
+ static bool unaligned_lwb_equal(const IntervalT& x1, const IntervalT& x2)
{ return false; }
- static bool unaligned_upb_equal(const interval<DataT>& x1, const interval<DataT>& x2)
+ static bool unaligned_upb_equal(const IntervalT& x1, const IntervalT& x2)
{ return false; }
- static bool has_equal_border_touch(const interval<DataT>& x1, const interval<DataT>& x2)
+ static bool has_equal_border_touch(const IntervalT& x1, const IntervalT& x2)
{ return false; }
};
-template<class DataT>
+template<class IntervalT>
struct discrete_interval
{
- static typename itl::interval<DataT>::size_type
- cardinality(const interval<DataT>& x)
+ typedef typename IntervalT::data_type data_type;
+
+ static typename IntervalT::size_type
+ cardinality(const IntervalT& x)
{ return x.discrete_cardinality(); }
- static typename interval<DataT>::difference_type
- length(const interval<DataT>& x)
+ static typename IntervalT::difference_type
+ length(const IntervalT& x)
{ return x.discrete_length(); }
- static bool unaligned_lwb_equal(const interval<DataT>& x1, const interval<DataT>& x2)
+ static bool unaligned_lwb_equal(const IntervalT& x1, const IntervalT& x2)
{
if(x1.leftbound_open() && x2.leftbound_closed())
- return succ(x1.lower()) == x2.lower();
- else return x1.lower() == succ(x2.lower());
+ return IntervalT::data_equal(succ(x1.lower()), x2.lower() );
+ else return IntervalT::data_equal( x1.lower(), succ(x2.lower()));
}
- static bool unaligned_upb_equal(const interval<DataT>& x1, const interval<DataT>& x2)
+ static bool unaligned_upb_equal(const IntervalT& x1, const IntervalT& x2)
{
if(x1.rightbound_closed() && x2.rightbound_open())
- return succ(x1.upper()) == x2.upper();
- else return x1.upper() == succ(x2.upper());
+ return IntervalT::data_equal(succ(x1.upper()), x2.upper() );
+ else return IntervalT::data_equal( x1.upper(), succ(x2.upper()));
}
- static bool has_equal_border_touch(const interval<DataT>& x1, const interval<DataT>& x2)
+ static bool has_equal_border_touch(const IntervalT& x1, const IntervalT& x2)
{
if(x1.rightbound_closed() && x2.leftbound_closed())
- return succ(x1.upper()) == x2.lower();
+ return IntervalT::data_equal(succ(x1.upper()), x2.lower());
if(x1.rightbound_open() && x2.leftbound_open() )
- return x1.upper() == succ(x2.lower());
+ return IntervalT::data_equal(x1.upper(), succ(x2.lower()));
return false;
}
@@ -722,16 +736,15 @@
bool interval<DataT>::exclusive_less(const interval& x2)const
{
using namespace boost::mpl;
- if(rightbound_closed() && x2.leftbound_closed()) return _upb < x2._lwb;
- if(rightbound_open() && x2.leftbound_closed()) return _upb <= x2._lwb;
- if(rightbound_closed() && x2.leftbound_open() ) return _upb <= x2._lwb;
+ if(rightbound_closed() && x2.leftbound_closed()) return data_less(_upb, x2._lwb); //_upb < x2._lwb
+ if(rightbound_open() && x2.leftbound_closed()) return data_less_equal(_upb, x2._lwb); //_upb <= x2._lwb;
+ if(rightbound_closed() && x2.leftbound_open() ) return data_less_equal(_upb, x2._lwb); //_upb <= x2._lwb;
- // OTHERWISE (rightbound_open() && leftbound_open())
return
if_<
bool_<is_continuous<DataT>::value>,
- continuous_type<DataT>,
- discrete_type<DataT>
+ continuous_type<interval<DataT> >,
+ discrete_type<interval<DataT> >
>
::type::open_bound_less_equal(_upb, x2._lwb);
}
@@ -741,16 +754,16 @@
bool interval<DataT>::lower_less(const interval& x2)const
{
using namespace boost::mpl;
- if(leftbound_closed() && x2.leftbound_closed()) return _lwb < x2._lwb;
- if(leftbound_open() && x2.leftbound_open()) return _lwb < x2._lwb;
- if(leftbound_closed() && x2.leftbound_open()) return _lwb <= x2._lwb;
+ if(leftbound_closed() && x2.leftbound_closed()) return data_less(_lwb, x2._lwb);
+ if(leftbound_open() && x2.leftbound_open()) return data_less(_lwb, x2._lwb);
+ if(leftbound_closed() && x2.leftbound_open()) return data_less_equal(_lwb, x2._lwb);//data_less_equal(_lwb, x2._lwb);
// OTHERWISE (leftbound_open() && x2.leftbound_closed())
return
if_<
bool_<is_continuous<DataT>::value>,
- continuous_type<DataT>,
- discrete_type<DataT>
+ continuous_type<interval<DataT> >,
+ discrete_type<interval<DataT> >
>
::type::open_bound_less(_lwb, x2._lwb);
}
@@ -759,16 +772,16 @@
bool interval<DataT>::upper_less(const interval& x2)const
{
using namespace boost::mpl;
- if(rightbound_closed() && x2.rightbound_closed()) return _upb < x2._upb;
- if(rightbound_open() && x2.rightbound_open()) return _upb < x2._upb;
- if(rightbound_open() && x2.rightbound_closed()) return _upb <= x2._upb;
+ if(rightbound_closed() && x2.rightbound_closed()) return data_less(_upb, x2._upb);
+ if(rightbound_open() && x2.rightbound_open()) return data_less(_upb, x2._upb);
+ if(rightbound_open() && x2.rightbound_closed()) return data_less_equal(_upb, x2._upb);//data_less_equal(_upb, x2._upb);
// OTHERWISE (rightbound_closed() && x2.rightbound_open())
return
if_<
bool_<is_continuous<DataT>::value>,
- continuous_type<DataT>,
- discrete_type<DataT>
+ continuous_type<interval<DataT> >,
+ discrete_type<interval<DataT> >
>
::type::open_bound_less(_upb, x2._upb);
}
@@ -778,16 +791,16 @@
bool interval<DataT>::lower_less_equal(const interval& x2)const
{
using namespace boost::mpl;
- if(leftbound_closed() && x2.leftbound_closed()) return _lwb <= x2._lwb;
- if(leftbound_open() && x2.leftbound_open()) return _lwb <= x2._lwb;
- if(leftbound_open() && x2.leftbound_closed()) return _lwb < x2._lwb;
+ if(leftbound_closed() && x2.leftbound_closed()) return data_less_equal(_lwb, x2._lwb);
+ if(leftbound_open() && x2.leftbound_open()) return data_less_equal(_lwb, x2._lwb);
+ if(leftbound_open() && x2.leftbound_closed()) return data_less(_lwb, x2._lwb);
// OTHERWISE (leftbound_closed() && x2.leftbound_open())
return
if_<
bool_<is_continuous<DataT>::value>,
- continuous_type<DataT>,
- discrete_type<DataT>
+ continuous_type<interval<DataT> >,
+ discrete_type<interval<DataT> >
>
::type::open_bound_less_equal(_lwb, x2._lwb);
}
@@ -797,16 +810,16 @@
bool interval<DataT>::upper_less_equal(const interval& x2)const
{
using namespace boost::mpl;
- if(rightbound_closed() && x2.rightbound_closed()) return _upb <= x2._upb;
- if(rightbound_open() && x2.rightbound_open()) return _upb <= x2._upb;
- if(rightbound_closed() && x2.rightbound_open()) return _upb < x2._upb;
+ if(rightbound_closed() && x2.rightbound_closed()) return data_less_equal(_upb, x2._upb);
+ if(rightbound_open() && x2.rightbound_open()) return data_less_equal(_upb, x2._upb);
+ if(rightbound_closed() && x2.rightbound_open()) return data_less(_upb, x2._upb);
// OTHERWISE (rightbound_open() && x2.rightbound_closed())
return
if_<
bool_<is_continuous<DataT>::value>,
- continuous_type<DataT>,
- discrete_type<DataT>
+ continuous_type<interval<DataT> >,
+ discrete_type<interval<DataT> >
>
::type::open_bound_less_equal(_upb, x2._upb);
}
@@ -818,14 +831,14 @@
bool interval<DataT>::lower_equal(const interval& x2)const
{
using namespace boost::mpl;
- if(leftbound_closed() && x2.leftbound_closed()) return _lwb == x2._lwb;
- if(leftbound_open() && x2.leftbound_open() ) return _lwb == x2._lwb;
+ if(leftbound_closed() && x2.leftbound_closed()) return data_equal(_lwb, x2._lwb);
+ if(leftbound_open() && x2.leftbound_open() ) return data_equal(_lwb, x2._lwb);
return
if_<
bool_<is_continuous<DataT>::value>,
- continuous_interval<DataT>,
- discrete_interval<DataT>
+ continuous_interval<interval<DataT> >,
+ discrete_interval<interval<DataT> >
>
::type::unaligned_lwb_equal(*this, x2);
}
@@ -836,14 +849,14 @@
bool interval<DataT>::upper_equal(const interval& x2)const
{
using namespace boost::mpl;
- if(rightbound_closed() && x2.rightbound_closed()) return _upb == x2._upb;
- if(rightbound_open() && x2.rightbound_open() ) return _upb == x2._upb;
+ if(rightbound_closed() && x2.rightbound_closed()) return data_equal(_upb, x2._upb);
+ if(rightbound_open() && x2.rightbound_open() ) return data_equal(_upb, x2._upb);
return
if_<
bool_<is_continuous<DataT>::value>,
- continuous_interval<DataT>,
- discrete_interval<DataT>
+ continuous_interval<interval<DataT> >,
+ discrete_interval<interval<DataT> >
>
::type::unaligned_upb_equal(*this, x2);
}
@@ -907,14 +920,14 @@
bool interval<DataT>::touches(const interval& x2)const
{
using namespace boost::mpl;
- if(rightbound_open() && x2.leftbound_closed()) return _upb == x2._lwb;
- if(rightbound_closed() && x2.leftbound_open()) return _upb == x2._lwb;
+ if(rightbound_open() && x2.leftbound_closed()) return data_equal(_upb, x2._lwb);
+ if(rightbound_closed() && x2.leftbound_open()) return data_equal(_upb, x2._lwb);
return
if_<
bool_<is_continuous<DataT>::value>,
- continuous_interval<DataT>,
- discrete_interval<DataT>
+ continuous_interval<interval<DataT> >,
+ discrete_interval<interval<DataT> >
>
::type::has_equal_border_touch(*this, x2);
}
@@ -922,10 +935,10 @@
template <class DataT>
bool interval<DataT>::contains(const DataT& x)const
{
- if(rightbound_closed() && leftbound_closed()) return _lwb <= x && x <= _upb;
- if(rightbound_closed() && leftbound_open() ) return _lwb < x && x <= _upb;
- if(rightbound_open() && leftbound_closed()) return _lwb <= x && x < _upb;
- return _lwb < x && x < _upb;
+ if(rightbound_closed() && leftbound_closed()) return data_less_equal(_lwb, x) && data_less_equal(x, _upb);
+ if(rightbound_closed() && leftbound_open() ) return data_less(_lwb, x) && data_less_equal(x, _upb);
+ if(rightbound_open() && leftbound_closed()) return data_less_equal(_lwb, x) && data_less(x, _upb);
+ return data_less(_lwb, x) && data_less(x, _upb);
}
template <class DataT>
@@ -1037,8 +1050,8 @@
using namespace boost::mpl;
return if_<
bool_<is_continuous<DataT>::value>,
- continuous_interval<DataT>,
- discrete_interval<DataT>
+ continuous_interval<interval<DataT> >,
+ discrete_interval<interval<DataT> >
>
::type::cardinality(*this);
}
@@ -1049,8 +1062,8 @@
using namespace boost::mpl;
return if_<
bool_<is_continuous<DataT>::value>,
- continuous_interval<DataT>,
- discrete_interval<DataT>
+ continuous_interval<interval<DataT> >,
+ discrete_interval<interval<DataT> >
>
::type::length(*this);
}
Modified: sandbox/itl/boost/itl/interval_base_set.hpp
==============================================================================
--- sandbox/itl/boost/itl/interval_base_set.hpp (original)
+++ sandbox/itl/boost/itl/interval_base_set.hpp 2008-11-09 16:54:41 EST (Sun, 09 Nov 2008)
@@ -417,7 +417,7 @@
template<typename IteratorT>
static codomain_type codomain_value(IteratorT& value_)
- { return (*value_).empty()? codomain_type() : (*value_).first(); }
+ { return (*value_).empty()? codomain_type() : (*value_).lower(); }
template<typename LeftIterT, typename RightIterT>
static bool key_less(LeftIterT& lhs_, RightIterT& rhs_)
Modified: sandbox/itl/boost/itl/interval_map.hpp
==============================================================================
--- sandbox/itl/boost/itl/interval_map.hpp (original)
+++ sandbox/itl/boost/itl/interval_map.hpp 2008-11-09 16:54:41 EST (Sun, 09 Nov 2008)
@@ -13,6 +13,7 @@
#define __interval_map_h_JOFA_080705__
#include <boost/assert.hpp>
+#include <boost/itl/type_traits/is_map.hpp>
#include <boost/itl/interval_set.hpp>
#include <boost/itl/interval_base_map.hpp>
#include <boost/itl/interval_maps.hpp>
@@ -413,7 +414,6 @@
interval_map<DomainT,CodomainT,Traits,Interval,Compare,Alloc>
::fill_gap_join_left(const value_type& value, const Combiner& combine)
{
- //CL static Combiner combine;
//collision free insert is asserted
if(value.KEY_VALUE.empty())
return this->_map.end();
@@ -442,7 +442,6 @@
interval_map<DomainT,CodomainT,Traits,Interval,Compare,Alloc>
::fill_gap_join_both(const value_type& value, const Combiner& combine)
{
- //CL static Combiner combine;
//collision free insert is asserted
if(value.KEY_VALUE.empty())
return this->_map.end();
@@ -473,8 +472,6 @@
void interval_map<DomainT,CodomainT,Traits,Interval,Compare,Alloc>
::add_(const value_type& x, const Combiner& combine)
{
- //CL static Combiner combine;
-
const interval_type& x_itv = x.KEY_VALUE;
if(x_itv.empty())
return;
@@ -574,8 +571,6 @@
void interval_map<DomainT,CodomainT,Traits,Interval,Compare,Alloc>
::add_rest(const interval_type& x_itv, const CodomainT& x_val, iterator& it, iterator& end_it, const Combiner& combine)
{
- //CL static Combiner combine;
-
iterator nxt_it = it; nxt_it++;
interval_type x_rest = x_itv, left_gap, common, cur_itv;
@@ -609,8 +604,6 @@
void interval_map<DomainT,CodomainT,Traits,Interval,Compare,Alloc>
::add_rear(const interval_type& x_rest, const CodomainT& x_val, iterator& it, const Combiner& combine)
{
- //CL static Combiner combine;
-
interval_type cur_itv = (*it).KEY_VALUE ;
CodomainT cur_val = (*it).CONT_VALUE ;
@@ -653,7 +646,6 @@
void interval_map<DomainT,CodomainT,Traits,Interval,Compare,Alloc>
::subtract_(const value_type& x, const Combiner& combine)
{
- //CL static Combiner combine;
const interval_type& x_itv = x.KEY_VALUE;
if(x_itv.empty())
@@ -723,7 +715,6 @@
void interval_map<DomainT,CodomainT,Traits,Interval,Compare,Alloc>
::subtract_rest(const interval_type& x_itv, const CodomainT& x_val, iterator& it, iterator& end_it, const Combiner& combine)
{
- //CL static Combiner combine;
iterator nxt_it=it; nxt_it++;
while(nxt_it!=end_it)
@@ -1027,6 +1018,10 @@
{ enum{value = true}; };
template <class KeyT, class DataT, class Traits>
+struct is_map<itl::interval_map<KeyT,DataT,Traits> >
+{ enum{value = true}; };
+
+template <class KeyT, class DataT, class Traits>
struct is_interval_container<itl::interval_map<KeyT,DataT,Traits> >
{ enum{value = true}; };
Modified: sandbox/itl/boost/itl/interval_map_algo.hpp
==============================================================================
--- sandbox/itl/boost/itl/interval_map_algo.hpp (original)
+++ sandbox/itl/boost/itl/interval_map_algo.hpp 2008-11-09 16:54:41 EST (Sun, 09 Nov 2008)
@@ -81,6 +81,7 @@
{
if(left == _left.end())
return stop;
+
if(!LeftT::key_value(_prior_left).touches(LeftT::key_value(left)))
return stop; //_result = false;
@@ -94,6 +95,7 @@
{
if(right == _right.end())
return stop;
+
if(!RightT::key_value(_prior_right).touches(RightT::key_value(right)))
return stop; //_result = false;
@@ -138,6 +140,36 @@
return step.result();
}
+/*CL
+template<class LeftT, class RightT>
+int lexicographical_compare(LeftT::const_iterator left_begin, LeftT::const_iterator left_end,
+ RightT::const_iterator right_begin, RightT::const_iterator right_end)
+{
+ if(left.empty())
+ return right.empty();
+ else if(right.empty())
+ return false;
+
+ typedef interval_map_sequence_tracker<LeftT,RightT> Step;
+ Step step(left_end, right_end);
+
+ typename LeftT::const_iterator left_ = left.begin();
+ typename RightT::const_iterator right_ = right.begin();
+
+ int state = Step::nextboth;
+ while(state != Step::stop)
+ {
+ switch(state){
+ case Step::nextboth: state = step.next_both(left_, right_); break;
+ case Step::nextleft: state = step.next_left(left_, right_); break;
+ case Step::nextright: state = step.next_right(left_, right_); break;
+ case Step::leftaligned: state = step.proceed(left_, right_); break;
+ }
+ }
+ return step.result();
+}
+*/
+
} //Map
}} // namespace itl boost
Modified: sandbox/itl/boost/itl/interval_maps.hpp
==============================================================================
--- sandbox/itl/boost/itl/interval_maps.hpp (original)
+++ sandbox/itl/boost/itl/interval_maps.hpp 2008-11-09 16:54:41 EST (Sun, 09 Nov 2008)
@@ -376,7 +376,7 @@
Traits,Interval,Compare,Alloc>& right
)
{
- return Map::is_element_equal(left, right);
+ return Interval_Set::is_element_equal(left, right);
}
@@ -505,6 +505,23 @@
.span(object.rbegin()->KEY_VALUE);
}
+template
+<
+ class SubType, class DomainT, class CodomainT,
+ class Traits, template<class>class Interval,
+ template<class>class Compare, template<class>class Alloc
+>
+typename interval_base_map<SubType,DomainT,CodomainT,Traits,Interval,Compare,Alloc>::interval_type
+enclosure(const interval_base_map<SubType,DomainT,CodomainT,Traits,Interval,Compare,Alloc>& object)
+{
+ typedef interval_base_map<SubType,DomainT,CodomainT,Traits,Interval,Compare,Alloc> IntervalMapT;
+ typedef typename IntervalMapT::interval_type interval_type;
+ return
+ object.empty() ? neutron<interval_type>::value()
+ : (object.begin()->KEY_VALUE)
+ .span(object.rbegin()->KEY_VALUE);
+}
+
}} // namespace itl boost
#endif
Modified: sandbox/itl/boost/itl/interval_set_algo.hpp
==============================================================================
--- sandbox/itl/boost/itl/interval_set_algo.hpp (original)
+++ sandbox/itl/boost/itl/interval_set_algo.hpp 2008-11-09 16:54:41 EST (Sun, 09 Nov 2008)
@@ -8,6 +8,7 @@
#ifndef __itl_interval_set_algo_JOFA_081005_H__
#define __itl_interval_set_algo_JOFA_081005_H__
+#include <boost/itl/type_traits/is_map.hpp>
#include <boost/itl/notate.hpp>
#include <boost/itl/type_traits/neutron.hpp>
@@ -60,34 +61,55 @@
};
-namespace Set
+namespace Interval_Set
{
-template<class LeftIntervalSetT, class RightIntervalSetT>
-class interval_set_sequence_tracker
+template<class LeftT, class RightT>
+class interval_sequence_tracker
{
public:
- typedef typename LeftIntervalSetT::const_iterator LeftIterT;
- typedef typename RightIntervalSetT::const_iterator RightIterT;
+ typedef typename LeftT::const_iterator LeftIterT;
+ typedef typename RightT::const_iterator RightIterT;
+
+ interval_sequence_tracker(const LeftT& left,
+ const RightT& right,
+ const LeftIterT& left_end,
+ const RightIterT& right_end)
+ : _left(left), _right(right),
+ _left_end(left_end), _right_end(right_end),
+ _compare_codomain(false), _result(result_is_equal)
+ {
+ _scope = enclosure(_left).intersect(enclosure(_right));
+ }
- interval_set_sequence_tracker(const LeftIntervalSetT& left,
- const RightIntervalSetT& right)
- : _left(left), _right(right), _result(false)
- {}
+ enum{firstboth, nextboth, nextleft, nextright, leftaligned, stop};
+ enum{result_is_less = -1, result_is_equal = 0, result_is_greater = 1};
- enum{nextboth, nextleft, nextright, leftaligned, stop};
+ void set_compare_codomain(bool truth=true)
+ { _compare_codomain = truth; }
- bool result()const{ return _result; }
+ bool compare_codomain()const { return _compare_codomain; }
+
+ int result()const{ return _result; }
+
+ bool covalues_are_equal(LeftIterT& left, RightIterT& right)
+ {
+ if(LeftT::codomain_value(left) < RightT::codomain_value(right))
+ _result = result_is_less;
+ if(RightT::codomain_value(right) < LeftT::codomain_value(left))
+ _result = result_is_greater;
+ return _result == result_is_equal;
+ }
int proceed(LeftIterT& left, RightIterT& right)
{
- if((*left).upper_equal(*right))
+ if(LeftT::key_value(left).upper_equal(RightT::key_value(right)))
{
++left;
++right;
return nextboth;
}
- else if((*left).upper_less(*right))
+ else if(LeftT::key_value(left).upper_less(RightT::key_value(right)))
{
_prior_left = left;
++left;
@@ -98,69 +120,145 @@
_prior_right = right;
++right;
return nextright;
- }
+ }
}
int next_both(LeftIterT& left, RightIterT& right)
{
- if(left == _left.end())
+ if(left == _left_end)
{
- _result = (right == _right.end()) ? true : false;
+ _result = (right == _right_end) ? result_is_equal : result_is_less;
return stop;
}
- // left != _left.end()
- if(right == _right.end())
- return stop; //_result = false;
-
- // The starting intervals have to begin equally
- if(!(*left).lower_equal(*right))
- return stop; //_result = false;
+ // left != _left_end
+ if(right == _right_end)
+ {
+ _result = result_is_greater;
+ return stop;
+ }
+
+ // Two matching intervals for left and right
+ // if they both start at or before the _scope, they are
+ // assumed to be leftaligned.
+ if(!( LeftT::key_value(left).lower_less_equal(_scope)
+ && RightT::key_value(right).lower_less_equal(_scope)))
+ {
+ // The starting intervals have to begin equally
+ if(LeftT::key_value(left).lower_less(RightT::key_value(right)))
+ { // left: same A... = sameA...
+ // right:same B.. = sameB...
+ _result = result_is_less;
+ return stop;
+ }
+
+ if(LeftT::key_value(right).lower_less(RightT::key_value(left)))
+ { // left: same B.. = sameB...
+ // right:same A... = sameA...
+ _result = result_is_greater;
+ return stop;
+ }
+
+ if(compare_codomain() && covalues_are_equal(left, right))
+ return stop;
+ }
+
+ // If left and right intervals reach to or beyond the _scope's end
+ // the result is equality
+ if( _scope.upper_less_equal(LeftT::key_value(left))
+ && _scope.upper_less_equal(RightT::key_value(right)))
+ return stop;
return leftaligned;
}
int next_left(LeftIterT& left, RightIterT& right)
{
- if(left == _left.end())
+ if(left == _left_end)
+ { // left: same
+ // right:sameA...
+ _result = result_is_less;
return stop;
- if(!(*_prior_left).touches(*left))
- return stop; //_result = false;
+ }
+
+ if(!LeftT::key_value(_prior_left).touches(LeftT::key_value(left)))
+ { // left: same B = sameB...
+ // right:sameA = sameA...
+ _result = result_is_greater;
+ return stop;
+ }
+
+ if(compare_codomain() && covalues_are_equal(left, right))
+ return stop;
+
+ // If left and right intervals reach to or beyond the _scope's end
+ // the result is equality
+ if( _scope.upper_less_equal(LeftT::key_value(left))
+ && _scope.upper_less_equal(RightT::key_value(right)))
+ return stop;
return proceed(left, right);
}
int next_right(LeftIterT& left, RightIterT& right)
{
- if(right == _right.end())
+ if(right == _right_end)
+ { // left: sameA...
+ // right:same
+ _result = result_is_greater;
return stop;
- if(!(*_prior_right).touches(*right))
- return stop; //_result = false;
+ }
+
+ if(!RightT::key_value(_prior_right).touches(RightT::key_value(right)))
+ {
+ // left: sameA... = sameA...
+ // right:same B.. = sameB...
+ _result = result_is_less;
+ return stop;
+ }
+
+ if(compare_codomain() && covalues_are_equal(left, right))
+ return stop;
+
+ // If left and right intervals reach to or beyond the _scope's end
+ // the result is equality
+ if( _scope.upper_less_equal(LeftT::key_value(left))
+ && _scope.upper_less_equal(RightT::key_value(right)))
+ return stop;
return proceed(left, right);
}
private:
- const LeftIntervalSetT& _left;
- const RightIntervalSetT& _right;
- LeftIterT _prior_left;
- RightIterT _prior_right;
- bool _result;
+ const LeftT& _left;
+ const RightT& _right;
+ LeftIterT _left_end;
+ RightIterT _right_end;
+ bool _compare_codomain;
+ LeftIterT _prior_left;
+ RightIterT _prior_right;
+ int _result;
+ typename LeftT::interval_type _scope;
};
+/* Lexicographical comparison on ranges of two interval container */
template<class LeftT, class RightT>
-bool is_element_equal(const LeftT& left, const RightT& right)
+int lexicographical_compare_3way
+(
+ const LeftT& left, //sub
+ const RightT& right, //super
+ typename LeftT::const_iterator left_begin,
+ typename LeftT::const_iterator left_end,
+ typename RightT::const_iterator right_begin,
+ typename RightT::const_iterator right_end
+)
{
- if(left.empty())
- return right.empty();
- else if(right.empty())
- return false;
-
- typedef interval_set_sequence_tracker<LeftT,RightT> Step;
- Step step(left, right);
+ typedef interval_sequence_tracker<LeftT,RightT> Step;
+ Step step(left, right, left_end, right_end);
+ step.set_compare_codomain(is_map<LeftT>::value && is_map<RightT>::value);
- typename LeftT::const_iterator left_ = left.begin();
- typename RightT::const_iterator right_ = right.begin();
+ typename LeftT::const_iterator left_ = left_begin;
+ typename RightT::const_iterator right_ = right_begin;
int state = Step::nextboth;
while(state != Step::stop)
@@ -175,7 +273,29 @@
return step.result();
}
-} //Set
+template<class LeftT, class RightT>
+bool is_element_equal(const LeftT& left, const RightT& right)
+{
+ return lexicographical_compare_3way
+ (
+ left, right,
+ left.begin(), left.end(),
+ right.begin(), right.end()
+ ) == 0;
+}
+
+template<class LeftT, class RightT>
+bool is_element_less(const LeftT& left, const RightT& right)
+{
+ return lexicographical_compare_3way
+ (
+ left, right,
+ left.begin(), left.end(),
+ right.begin(), right.end()
+ ) == -1;
+}
+
+} // namespace Interval_Set
}} // namespace itl boost
Modified: sandbox/itl/boost/itl/interval_sets.hpp
==============================================================================
--- sandbox/itl/boost/itl/interval_sets.hpp (original)
+++ sandbox/itl/boost/itl/interval_sets.hpp 2008-11-09 16:54:41 EST (Sun, 09 Nov 2008)
@@ -290,7 +290,7 @@
const IntervalSet <DomainT,Interval,Compare,Alloc>& operand
)
{
- return Set::is_element_equal(object, operand);
+ return Interval_Set::is_element_equal(object, operand);
}
@@ -459,6 +459,21 @@
: (*object.begin()).span(*object.rbegin());
}
+template
+<
+ class SubType, class DomainT, template<class>class Interval,
+ template<class>class Compare, template<class>class Alloc
+>
+typename interval_base_set<SubType,DomainT,Interval,Compare,Alloc>::interval_type
+enclosure(const interval_base_set<SubType,DomainT,Interval,Compare,Alloc>& object)
+{
+ typedef interval_base_set<SubType,DomainT,Interval,Compare,Alloc> IntervalSetT;
+ typedef typename IntervalSetT::interval_type interval_type;
+ return
+ object.empty() ? neutron<interval_type>::value()
+ : (*object.begin()).span(*object.rbegin());
+}
+
}} // namespace itl boost
Modified: sandbox/itl/boost/itl/separate_interval_set.hpp
==============================================================================
--- sandbox/itl/boost/itl/separate_interval_set.hpp (original)
+++ sandbox/itl/boost/itl/separate_interval_set.hpp 2008-11-09 16:54:41 EST (Sun, 09 Nov 2008)
@@ -251,6 +251,7 @@
//-----------------------------------------------------------------------------
// equality of elements
//-----------------------------------------------------------------------------
+/*CL
template
<
class DomainT, template<class>class Interval,
@@ -271,6 +272,7 @@
joined_type joined_rhs(rhs);
return Set::lexicographical_equal(joined_lhs, joined_rhs);
}
+*/
template <class Type>
struct is_set<itl::separate_interval_set<Type> >
Modified: sandbox/itl/boost/itl/set_algo.hpp
==============================================================================
--- sandbox/itl/boost/itl/set_algo.hpp (original)
+++ sandbox/itl/boost/itl/set_algo.hpp 2008-11-09 16:54:41 EST (Sun, 09 Nov 2008)
@@ -79,9 +79,6 @@
return true;
}
- //JODO where to put common algorithms? namespace Collector, Ordered, Sorted, SortedObject
-
-
template<class ObjectT>
ObjectT& add(ObjectT& result, const ObjectT& x2)
{
Modified: sandbox/itl/boost/itl/split_interval_map.hpp
==============================================================================
--- sandbox/itl/boost/itl/split_interval_map.hpp (original)
+++ sandbox/itl/boost/itl/split_interval_map.hpp 2008-11-09 16:54:41 EST (Sun, 09 Nov 2008)
@@ -307,7 +307,6 @@
void split_interval_map<DomainT,CodomainT,Traits,Interval,Compare,Alloc>
::fill_gap(const value_type& value, const Combiner& combine)
{
- //CL static Combiner combine;
//collision free insert is asserted
if(value.KEY_VALUE.empty())
return;
@@ -332,7 +331,6 @@
void split_interval_map<DomainT,CodomainT,Traits,Interval,Compare,Alloc>
::add_(const value_type& x, const Combiner& combine)
{
- //CL static Combiner combine;
const interval_type& x_itv = x.KEY_VALUE;
if(x_itv.empty())
@@ -419,7 +417,6 @@
iterator& it, iterator& end_it,
const Combiner& combine)
{
- //CL static Combiner combine;
iterator nxt_it = it; nxt_it++;
interval_type x_rest = x_itv, gap, common, cur_itv;
@@ -449,7 +446,6 @@
::add_rear(const interval_type& x_rest, const CodomainT& x_val, iterator& it,
const Combiner& combine)
{
- //CL static Combiner combine;
interval_type cur_itv = (*it).KEY_VALUE ;
CodomainT cur_val = (*it).CONT_VALUE ;
@@ -485,7 +481,6 @@
void split_interval_map<DomainT,CodomainT,Traits,Interval,Compare,Alloc>
::subtract_(const value_type& x, const Combiner& combine)
{
- //CL static Combiner combine;
const interval_type& x_itv = x.KEY_VALUE;
if(x_itv.empty())
@@ -547,7 +542,6 @@
iterator& it, iterator& end_it,
const Combiner& combine)
{
- //CL static Combiner combine;
iterator nxt_it=it; nxt_it++;
while(nxt_it!=end_it)
@@ -809,6 +803,10 @@
{ enum{value = true}; };
template <class KeyT, class DataT, class Traits>
+struct is_map<itl::split_interval_map<KeyT,DataT,Traits> >
+{ enum{value = true}; };
+
+template <class KeyT, class DataT, class Traits>
struct is_interval_container<itl::split_interval_map<KeyT,DataT,Traits> >
{ enum{value = true}; };
Modified: sandbox/itl/boost/itl/split_interval_set.hpp
==============================================================================
--- sandbox/itl/boost/itl/split_interval_set.hpp (original)
+++ sandbox/itl/boost/itl/split_interval_set.hpp 2008-11-09 16:54:41 EST (Sun, 09 Nov 2008)
@@ -199,26 +199,6 @@
void subtract_rest(const interval_type& x_itv, iterator& it, iterator& end_it);
} ;
- /*
- template <typename DomainT, template<class>class Interval, template<class>class Compare, template<class>class Alloc>
- bool split_interval_set<DomainT,Interval,Compare,Alloc>::contains_(const interval_type& x)const
- {
- if(x.empty()) return true;
-
- typename ImplSetT::const_iterator fst_it = this->_set.lower_bound(x);
- typename ImplSetT::const_iterator end_it = this->_set.upper_bound(x);
-
- interval_set<DomainT,Interval,Compare,Alloc> matchSet;
- for(typename ImplSetT::const_iterator it=fst_it; it!=end_it; it++)
- matchSet.add(*it);
-
- interval_set<DomainT,Interval,Compare,Alloc> x_asSet;
- x_asSet.add(x);
- return x_asSet.contained_in(matchSet);
- }
- */
-
-
template <typename DomainT, template<class>class Interval, template<class>class Compare, template<class>class Alloc>
bool split_interval_set<DomainT,Interval,Compare,Alloc>::contains_(const interval_type& interv)const
{
Modified: sandbox/itl/libs/itl/test/test_interval_map_mixed/test_interval_map_mixed.cpp
==============================================================================
--- sandbox/itl/libs/itl/test/test_interval_map_mixed/test_interval_map_mixed.cpp (original)
+++ sandbox/itl/libs/itl/test/test_interval_map_mixed/test_interval_map_mixed.cpp 2008-11-09 16:54:41 EST (Sun, 09 Nov 2008)
@@ -907,9 +907,9 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(test_itl_interval_map_mixed_intersect_4_bicremental_types, T, bicremental_types)
{
typedef int U;
- typedef interval_map<T,U> IntervalMapT;
+ typedef interval_map<T,U> IntervalMapT;
typedef split_interval_map<T,U> SplitIntervalMapT;
- typedef interval_set<T> IntervalSetT;
+ typedef interval_set<T> IntervalSetT;
typedef split_interval_set<T> SplitIntervalSetT;
U u1 = make<U>(1);
U u2 = make<U>(2);
Modified: sandbox/itl/libs/itl/test/test_interval_set_mixed/test_interval_set_mixed.cpp
==============================================================================
--- sandbox/itl/libs/itl/test/test_interval_set_mixed/test_interval_set_mixed.cpp (original)
+++ sandbox/itl/libs/itl/test/test_interval_set_mixed/test_interval_set_mixed.cpp 2008-11-09 16:54:41 EST (Sun, 09 Nov 2008)
@@ -750,3 +750,4 @@
BOOST_CHECK_EQUAL( is_disjoint(join_A, sep_B), true );
BOOST_CHECK_EQUAL( is_disjoint(join_A, join_B), true );
}
+
Modified: sandbox/itl/libs/itl/test/test_interval_set_shared.hpp
==============================================================================
--- sandbox/itl/libs/itl/test/test_interval_set_shared.hpp (original)
+++ sandbox/itl/libs/itl/test/test_interval_set_shared.hpp 2008-11-09 16:54:41 EST (Sun, 09 Nov 2008)
@@ -413,6 +413,7 @@
BOOST_CHECK_EQUAL( all.contains(left), true );
BOOST_CHECK_EQUAL( all.contains(right), true );
BOOST_CHECK_EQUAL( all.contains(complement), true );
+
BOOST_CHECK_EQUAL( left.contains(section), true );
BOOST_CHECK_EQUAL( right.contains(section), true );
Modified: sandbox/itl/libs/itl/test/test_type_lists.hpp
==============================================================================
--- sandbox/itl/libs/itl/test/test_type_lists.hpp (original)
+++ sandbox/itl/libs/itl/test/test_type_lists.hpp 2008-11-09 16:54:41 EST (Sun, 09 Nov 2008)
@@ -17,6 +17,7 @@
#include <boost/itl/interval.hpp>
+
typedef ::boost::mpl::list<
unsigned short, unsigned int, unsigned long
,short, int, long
@@ -26,6 +27,11 @@
// ,boost::gregorian::date
> bicremental_types;
+//DBG short list for debugging
+//typedef ::boost::mpl::list<
+// int
+//> bicremental_types;
+
typedef ::boost::mpl::list<
float, double
,boost::rational<int>
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk