Subject: [Boost-commit] svn:boost r57599 - in sandbox/itl: boost/itl boost/itl/detail boost/itl_xt boost/itl_xt/detail libs/itl/example/large_bitset_ libs/itl/test libs/itl/test/test_casual_ libs/itl/test/test_interval_set_ libs/itl/test/test_split_interval_set_
From: afojgo_at_[hidden]
Date: 2009-11-12 11:33:28
Author: jofaber
Date: 2009-11-12 11:33:24 EST (Thu, 12 Nov 2009)
New Revision: 57599
URL: http://svn.boost.org/trac/boost/changeset/57599
Log:
Added element_iterators. Stable {msvc-9.0}
Added:
sandbox/itl/boost/itl/detail/element_iterator.hpp (contents, props changed)
sandbox/itl/boost/itl/detail/mapped_reference.hpp (contents, props changed)
sandbox/itl/boost/itl_xt/detail/
sandbox/itl/boost/itl_xt/detail/bit_element_iterator.hpp (contents, props changed)
Text files modified:
sandbox/itl/boost/itl/interval.hpp | 7
sandbox/itl/boost/itl/interval_base_map.hpp | 22 +++
sandbox/itl/boost/itl/interval_base_set.hpp | 26 +++
sandbox/itl/boost/itl/iterator.hpp | 2
sandbox/itl/boost/itl_xt/bits.hpp | 4
sandbox/itl/boost/itl_xt/interval_bitset.hpp | 79 ++++++++--
sandbox/itl/libs/itl/example/large_bitset_/large_bitset.hpp | 4
sandbox/itl/libs/itl/test/fastest_interval_map_cases.hpp | 4
sandbox/itl/libs/itl/test/fastest_interval_set_cases.hpp | 4
sandbox/itl/libs/itl/test/test_casual_/test_casual.cpp | 268 ++++++++++++++++++++++++++++++++++++++-
sandbox/itl/libs/itl/test/test_interval_map_cases.hpp | 4
sandbox/itl/libs/itl/test/test_interval_map_shared.hpp | 44 ++++++
sandbox/itl/libs/itl/test/test_interval_set_/test_interval_set.cpp | 1
sandbox/itl/libs/itl/test/test_interval_set_cases.hpp | 4
sandbox/itl/libs/itl/test/test_interval_set_shared.hpp | 35 +++++
sandbox/itl/libs/itl/test/test_split_interval_set_/test_split_interval_set_shared.cpp | 4
sandbox/itl/libs/itl/test/vc9_fast_tests.sln | 12 +
17 files changed, 485 insertions(+), 39 deletions(-)
Added: sandbox/itl/boost/itl/detail/element_iterator.hpp
==============================================================================
--- (empty file)
+++ sandbox/itl/boost/itl/detail/element_iterator.hpp 2009-11-12 11:33:24 EST (Thu, 12 Nov 2009)
@@ -0,0 +1,247 @@
+/*-----------------------------------------------------------------------------+
+Copyright (c) 2009-2009: Joachim Faulhaber
++------------------------------------------------------------------------------+
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENCE.txt or copy at
+ http://www.boost.org/LICENSE_1_0.txt)
++-----------------------------------------------------------------------------*/
+#ifndef BOOST_ITL_DETAIL_ELEMENT_ITERATOR_HPP_JOFA_091104
+#define BOOST_ITL_DETAIL_ELEMENT_ITERATOR_HPP_JOFA_091104
+
+#include <boost/mpl/if.hpp>
+#include <boost/iterator/iterator_facade.hpp>
+#include <boost/config/warning_disable.hpp>
+#include <boost/itl/detail/mapped_reference.hpp>
+
+namespace boost{namespace itl
+{
+
+//------------------------------------------------------------------------------
+template<class Type>
+struct is_std_pair
+{
+ typedef is_std_pair<Type> type;
+ BOOST_STATIC_CONSTANT(bool, value = false);
+};
+
+template<class FirstT, class SecondT>
+struct is_std_pair<std::pair<FirstT, SecondT> >
+{
+ typedef is_std_pair<std::pair<FirstT, SecondT> > type;
+ BOOST_STATIC_CONSTANT(bool, value = true);
+};
+
+
+//------------------------------------------------------------------------------
+template<class Type>
+struct first_element
+{
+ typedef Type type;
+};
+
+template<class FirstT, class SecondT>
+struct first_element<std::pair<FirstT, SecondT> >
+{
+ typedef FirstT type;
+};
+
+//------------------------------------------------------------------------------
+template <class SegmentIteratorT> class element_iterator;
+
+template<class IteratorT>
+struct is_reverse
+{
+ typedef is_reverse type;
+ BOOST_STATIC_CONSTANT(bool, value = false);
+};
+
+template<class BaseIteratorT>
+struct is_reverse<std::reverse_iterator<BaseIteratorT> >
+{
+ typedef is_reverse<std::reverse_iterator<BaseIteratorT> > type;
+ BOOST_STATIC_CONSTANT(bool, value = true);
+};
+
+template<class BaseIteratorT>
+struct is_reverse<itl::element_iterator<BaseIteratorT> >
+{
+ typedef is_reverse<itl::element_iterator<BaseIteratorT> > type;
+ BOOST_STATIC_CONSTANT(bool, value = is_reverse<BaseIteratorT>::value);
+};
+
+//------------------------------------------------------------------------------
+template<class SegmentT>
+struct elemental;
+
+template<class DomainT, ITL_COMPARE Compare, template<class, ITL_COMPARE>class Interval>
+struct elemental<Interval<DomainT,Compare> >
+{
+ typedef Interval<DomainT,Compare> segment_type;
+ typedef segment_type interval_type;
+ typedef DomainT type;
+ typedef DomainT domain_type;
+ typedef DomainT codomain_type;
+ typedef DomainT transit_type;
+};
+
+template< class DomainT, class CodomainT,
+ ITL_COMPARE Compare, template<class, ITL_COMPARE>class Interval >
+struct elemental<std::pair<Interval<DomainT,Compare>const, CodomainT> >
+{
+ typedef std::pair<Interval<DomainT,Compare>, CodomainT> segment_type;
+ typedef Interval<DomainT,Compare> interval_type;
+ typedef std::pair<DomainT, CodomainT> type;
+ typedef DomainT domain_type;
+ typedef CodomainT codomain_type;
+ typedef mapped_reference<DomainT, CodomainT> transit_type;
+};
+
+
+//------------------------------------------------------------------------------
+//- struct segment_adapter
+//------------------------------------------------------------------------------
+template<class SegmentIteratorT, class SegmentT>
+struct segment_adapter;
+
+template<class SegmentIteratorT, class DomainT, ITL_COMPARE Compare, template<class, ITL_COMPARE>class Interval>
+struct segment_adapter<SegmentIteratorT, Interval<DomainT,Compare> >
+{
+ typedef segment_adapter type;
+ typedef Interval<DomainT,Compare> segment_type;
+ typedef segment_type interval_type;
+ typedef typename interval_type::difference_type domain_difference_type;
+ typedef DomainT domain_type;
+ typedef DomainT codomain_type;
+ typedef domain_type element_type;
+ typedef domain_type& transit_type;
+
+ static domain_type first (const SegmentIteratorT& leaper){ return leaper->first(); }
+ static domain_type last (const SegmentIteratorT& leaper){ return leaper->last(); }
+ static domain_difference_type length(const SegmentIteratorT& leaper){ return leaper->length();}
+
+ static transit_type transient_element(domain_type& inter_pos, const SegmentIteratorT& leaper,
+ const domain_difference_type& sneaker)
+ {
+ inter_pos = is_reverse<SegmentIteratorT>::value ? leaper->last() - sneaker
+ : leaper->first() + sneaker;
+ return inter_pos;
+ }
+};
+
+template < class SegmentIteratorT, class DomainT, class CodomainT,
+ ITL_COMPARE Compare, template<class, ITL_COMPARE>class Interval >
+struct segment_adapter<SegmentIteratorT, std::pair<Interval<DomainT,Compare>const, CodomainT> >
+{
+ typedef segment_adapter type;
+ typedef Interval<DomainT,Compare> interval_type;
+ typedef typename interval_type::difference_type domain_difference_type;
+ typedef DomainT domain_type;
+ typedef std::pair<DomainT, CodomainT> element_type;
+ typedef CodomainT codomain_type;
+ typedef mapped_reference<DomainT, CodomainT> transit_type;
+
+ static domain_type first (const SegmentIteratorT& leaper){ return leaper->first.first(); }
+ static domain_type last (const SegmentIteratorT& leaper){ return leaper->first.last(); }
+ static domain_difference_type length(const SegmentIteratorT& leaper){ return leaper->first.length();}
+
+ static transit_type transient_element(domain_type& inter_pos, const SegmentIteratorT& leaper,
+ const domain_difference_type& sneaker)
+ {
+ inter_pos = is_reverse<SegmentIteratorT>::value ? leaper->first.last() - sneaker
+ : leaper->first.first() + sneaker;
+ return transit_type(inter_pos, leaper->second);
+ }
+};
+
+
+template <class SegmentIteratorT>
+class element_iterator
+ : public boost::iterator_facade<
+ element_iterator<SegmentIteratorT>
+ , typename elemental<typename SegmentIteratorT::value_type>::transit_type
+ , boost::bidirectional_traversal_tag
+ , typename elemental<typename SegmentIteratorT::value_type>::transit_type
+ >
+{
+public:
+ typedef SegmentIteratorT segment_iterator;
+ typedef typename SegmentIteratorT::value_type segment_type;
+ typedef typename first_element<segment_type>::type interval_type;
+ typedef typename interval_type::difference_type domain_difference_type;
+ typedef typename elemental<segment_type>::type element_type;
+ typedef typename elemental<segment_type>::domain_type domain_type;
+ typedef typename elemental<segment_type>::codomain_type codomain_type;
+ typedef typename elemental<segment_type>::transit_type transit_type;
+ typedef transit_type value_type;
+
+private:
+ typedef typename segment_adapter<segment_iterator,segment_type>::type adapt;
+
+ struct enabler{};
+
+public:
+ element_iterator()
+ : _saltator(neutron<segment_iterator>::value())
+ , _reptator(neutron<domain_difference_type>::value()){}
+
+ explicit element_iterator(segment_iterator jumper)
+ : _saltator(jumper), _reptator(neutron<domain_difference_type>::value()) {}
+
+ template <class SaltatorT>
+ element_iterator
+ ( element_iterator<SaltatorT> const& other
+ , typename enable_if<boost::is_convertible<SaltatorT*,SegmentIteratorT*>, enabler>::type = enabler())
+ : _saltator(other._saltator), _reptator(other._reptator) {}
+
+private:
+ friend class boost::iterator_core_access;
+ template <class> friend class element_iterator;
+
+ template <class SaltatorT>
+ bool equal(element_iterator<SaltatorT> const& other) const
+ {
+ return this->_saltator == other._saltator
+ && this->_reptator == other._reptator;
+ }
+
+ void increment()
+ {
+ if(_reptator < pred(adapt::length(_saltator)))
+ ++_reptator;
+ else
+ {
+ ++_saltator;
+ _reptator = neutron<domain_difference_type>::value();
+ }
+ }
+
+ void decrement()
+ {
+ if(neutron<domain_difference_type>::value() < _reptator)
+ --_reptator;
+ else
+ {
+ --_saltator;
+ _reptator = adapt::length(_saltator);
+ --_reptator;
+ }
+ }
+
+ value_type& dereference()const
+ {
+ return adapt::transient_element(_inter_pos, _saltator, _reptator);
+ }
+
+private:
+ segment_iterator _saltator; // satltare: to jump : the fast moving iterator
+ mutable domain_difference_type _reptator; // reptare: to sneak : the slow moving iterator 0 based
+ mutable domain_type _inter_pos; // inter position : Position within the current segment
+ // _saltator->first.first() <= _inter_pos <= _saltator->first.last()
+};
+
+}} // namespace itl boost
+
+#endif // BOOST_ITL_DETAIL_ELEMENT_ITERATOR_HPP_JOFA_091104
+
+
+
Added: sandbox/itl/boost/itl/detail/mapped_reference.hpp
==============================================================================
--- (empty file)
+++ sandbox/itl/boost/itl/detail/mapped_reference.hpp 2009-11-12 11:33:24 EST (Thu, 12 Nov 2009)
@@ -0,0 +1,65 @@
+/*-----------------------------------------------------------------------------+
+Copyright (c) 2009-2009: Joachim Faulhaber
++------------------------------------------------------------------------------+
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENCE.txt or copy at
+ http://www.boost.org/LICENSE_1_0.txt)
++-----------------------------------------------------------------------------*/
+#ifndef BOOST_ITL_DETAIL_MAPPED_REFERENCE_HPP_JOFA_091108
+#define BOOST_ITL_DETAIL_MAPPED_REFERENCE_HPP_JOFA_091108
+
+namespace boost{namespace itl
+{
+
+template<class FirstT, class SecondT>
+struct mapped_reference
+{
+ typedef FirstT first_type;
+ typedef SecondT second_type;
+ typedef mapped_reference type;
+
+ const FirstT& first;
+ SecondT& second;
+
+ mapped_reference(const FirstT& fst, SecondT& snd) : first(fst), second(snd){}
+
+ template<class FstT, class SndT>
+ mapped_reference(const mapped_reference<FstT, SndT>& source):
+ first(source.first), second(source.second){}
+
+ template<class FstT, class SndT>
+ operator std::pair<FstT,SndT>(){ return std::pair<FstT,SndT>(first, second); }
+};
+
+
+template<class FirstT, class SecondT>
+inline bool operator == (const mapped_reference<FirstT, SecondT>& left, const mapped_reference<FirstT, SecondT>& right)
+{ return left.first == right.first && left.second == right.second; }
+
+template<class FirstT, class SecondT>
+inline bool operator < (const mapped_reference<FirstT, SecondT>& left, const mapped_reference<FirstT, SecondT>& right)
+{ return left.first < right.first || (!(right.first < left.first) && left.second < right.second); }
+
+template<class FirstT, class SecondT>
+inline bool operator != (const mapped_reference<FirstT, SecondT>& left, const mapped_reference<FirstT, SecondT>& right)
+{ return !(left == right); }
+
+template<class FirstT, class SecondT>
+inline bool operator > (const mapped_reference<FirstT, SecondT>& left, const mapped_reference<FirstT, SecondT>& right)
+{ return right < left; }
+
+template<class FirstT, class SecondT>
+inline bool operator <= (const mapped_reference<FirstT, SecondT>& left, const mapped_reference<FirstT, SecondT>& right)
+{ return !(right < left); }
+
+template<class FirstT, class SecondT>
+inline bool operator >= (const mapped_reference<FirstT, SecondT>& left, const mapped_reference<FirstT, SecondT>& right)
+{ return !(left < right); }
+
+template<class FirstT, class SecondT>
+inline mapped_reference<FirstT, SecondT> make_mapped_reference(const FirstT& left, SecondT& right)
+{ return mapped_reference<FirstT, SecondT>(left, right); }
+
+}} // namespace itl boost
+
+#endif // BOOST_ITL_DETAIL_MAPPED_REFERENCE_HPP_JOFA_091108
Modified: sandbox/itl/boost/itl/interval.hpp
==============================================================================
--- sandbox/itl/boost/itl/interval.hpp (original)
+++ sandbox/itl/boost/itl/interval.hpp 2009-11-12 11:33:24 EST (Thu, 12 Nov 2009)
@@ -509,14 +509,13 @@
cardinality(const IntervalT& x)
{
return x.empty()? itl::neutron<typename IntervalT::size_type>::value()
- : succ(x.last()-x.first());
+ : static_cast<typename IntervalT::size_type>(succ(x.last()-x.first()));
}
static typename IntervalT::difference_type length(const IntervalT& x)
{
- return x.empty() ?
- itl::neutron<typename IntervalT::difference_type>::value() :
- succ(x.last() - x.first());
+ return x.empty() ? itl::neutron<typename IntervalT::difference_type>::value()
+ : succ(x.last() - x.first());
}
static bool unaligned_lwb_equal(const IntervalT& x1, const IntervalT& x2)
Modified: sandbox/itl/boost/itl/interval_base_map.hpp
==============================================================================
--- sandbox/itl/boost/itl/interval_base_map.hpp (original)
+++ sandbox/itl/boost/itl/interval_base_map.hpp 2009-11-12 11:33:24 EST (Thu, 12 Nov 2009)
@@ -153,6 +153,15 @@
/// const_iterator for iteration over intervals
typedef typename ImplMapT::const_reverse_iterator const_reverse_iterator;
+ /// element iterator: Depreciated, see documentation.
+ typedef boost::itl::element_iterator<iterator> element_iterator;
+ /// const element iterator: Depreciated, see documentation.
+ typedef boost::itl::element_iterator<const_iterator> element_const_iterator;
+ /// element reverse iterator: Depreciated, see documentation.
+ typedef boost::itl::element_iterator<reverse_iterator> element_reverse_iterator;
+ /// element const reverse iterator: Depreciated, see documentation.
+ typedef boost::itl::element_iterator<const_reverse_iterator> element_const_reverse_iterator;
+
typedef typename ImplMapT::pointer pointer;
typedef typename ImplMapT::const_pointer const_pointer;
typedef typename ImplMapT::reference reference;
@@ -656,6 +665,19 @@
const_reverse_iterator rend()const { return _map.rend(); }
//==========================================================================
+ //= Element iterator related
+ //==========================================================================
+ element_iterator elements_begin(){ return element_iterator(this->begin()); }
+ element_iterator elements_end() { return element_iterator(this->end()); }
+ element_const_iterator elements_begin()const{ return element_iterator(this->begin()); }
+ element_const_iterator elements_end() const{ return element_iterator(this->end()); }
+
+ element_reverse_iterator elements_rbegin(){ return element_reverse_iterator(this->rbegin()); }
+ element_reverse_iterator elements_rend() { return element_reverse_iterator(this->rend()); }
+ element_const_reverse_iterator elements_rbegin()const{ return element_reverse_iterator(this->rbegin()); }
+ element_const_reverse_iterator elements_rend() const{ return element_reverse_iterator(this->rend()); }
+
+ //==========================================================================
//= Representation
//==========================================================================
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 2009-11-12 11:33:24 EST (Thu, 12 Nov 2009)
@@ -14,6 +14,7 @@
#include <boost/itl/set.hpp>
#include <boost/itl/interval.hpp>
#include <boost/itl/detail/notate.hpp>
+#include <boost/itl/detail/element_iterator.hpp>
#define const_FOR_IMPL(iter) for(typename ImplSetT::const_iterator iter=_set.begin(); (iter)!=_set.end(); (iter)++)
#define FOR_IMPL(iter) for(typename ImplSetT::iterator iter=_set.begin(); (iter)!=_set.end(); (iter)++)
@@ -116,12 +117,21 @@
/// const_iterator for iteration over intervals
typedef typename ImplSetT::const_reverse_iterator const_reverse_iterator;
+ /// element iterator: Depreciated, see documentation.
+ typedef boost::itl::element_iterator<iterator> element_iterator;
+ /// element const iterator: Depreciated, see documentation.
+ typedef boost::itl::element_iterator<const_iterator> element_const_iterator;
+ /// element reverse iterator: Depreciated, see documentation.
+ typedef boost::itl::element_iterator<reverse_iterator> element_reverse_iterator;
+ /// element const reverse iterator: Depreciated, see documentation.
+ typedef boost::itl::element_iterator<const_reverse_iterator> element_const_reverse_iterator;
+
typedef typename ImplSetT::pointer pointer;
typedef typename ImplSetT::const_pointer const_pointer;
typedef typename ImplSetT::reference reference;
typedef typename ImplSetT::const_reference const_reference;
- enum { fineness = 4 }; //SubType::fineness };
+ enum { fineness = 4 };
public:
//==========================================================================
@@ -401,6 +411,20 @@
std::pair<const_iterator,const_iterator> equal_range(const key_type& interval)const
{ return _set.equal_range(interval); }
+
+ //==========================================================================
+ //= Element iterator related
+ //==========================================================================
+ element_iterator elements_begin(){ return element_iterator(this->begin()); }
+ element_iterator elements_end() { return element_iterator(this->end()); }
+ element_const_iterator elements_begin()const{ return element_iterator(this->begin()); }
+ element_const_iterator elements_end() const{ return element_iterator(this->end()); }
+
+ element_reverse_iterator elements_rbegin(){ return element_reverse_iterator(this->rbegin()); }
+ element_reverse_iterator elements_rend() { return element_reverse_iterator(this->rend()); }
+ element_const_reverse_iterator elements_rbegin()const{ return element_reverse_iterator(this->rbegin()); }
+ element_const_reverse_iterator elements_rend() const{ return element_reverse_iterator(this->rend()); }
+
//==========================================================================
//= Morphisms
//==========================================================================
Modified: sandbox/itl/boost/itl/iterator.hpp
==============================================================================
--- sandbox/itl/boost/itl/iterator.hpp (original)
+++ sandbox/itl/boost/itl/iterator.hpp 2009-11-12 11:33:24 EST (Thu, 12 Nov 2009)
@@ -21,6 +21,7 @@
public:
/// The container's type.
typedef ContainerT container_type;
+ typedef std::output_iterator_tag iterator_category;
/** An add_iterator is constructed with a container and a position
that has to be maintained. */
@@ -61,6 +62,7 @@
public:
/// The container's type.
typedef ContainerT container_type;
+ typedef std::output_iterator_tag iterator_category;
/** An insert_iterator is constructed with a container and a position
that has to be maintained. */
Modified: sandbox/itl/boost/itl_xt/bits.hpp
==============================================================================
--- sandbox/itl/boost/itl_xt/bits.hpp (original)
+++ sandbox/itl/boost/itl_xt/bits.hpp 2009-11-12 11:33:24 EST (Thu, 12 Nov 2009)
@@ -21,6 +21,9 @@
namespace boost{namespace itl
{
+// A bit_range_type is supposed to cover the range of bits including endings.
+// rend() end()
+// -1 <= b <= BitsT::digits
typedef short bit_range_type;
namespace bitcount
@@ -140,6 +143,7 @@
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
};
+
template<>
struct count<nat8, 8>
{
Added: sandbox/itl/boost/itl_xt/detail/bit_element_iterator.hpp
==============================================================================
--- (empty file)
+++ sandbox/itl/boost/itl_xt/detail/bit_element_iterator.hpp 2009-11-12 11:33:24 EST (Thu, 12 Nov 2009)
@@ -0,0 +1,369 @@
+/*-----------------------------------------------------------------------------+
+Copyright (c) 2009-2009: Joachim Faulhaber
++------------------------------------------------------------------------------+
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENCE.txt or copy at
+ http://www.boost.org/LICENSE_1_0.txt)
++-----------------------------------------------------------------------------*/
+#ifndef BOOST_ITL_XT_DETAIL_BIT_ELEMENT_ITERATOR_HPP_JOFA_091109
+#define BOOST_ITL_XT_DETAIL_BIT_ELEMENT_ITERATOR_HPP_JOFA_091109
+
+#include <boost/itl_xt/bits.hpp>
+
+namespace boost{namespace itl
+{
+
+namespace iterator_state
+{
+ enum { dereferencable, end };
+}
+
+//------------------------------------------------------------------------------
+template<class SegmentT> struct bitwise;
+
+template<class DomainT, ITL_COMPARE Compare, template<class, ITL_COMPARE>class Interval, class BitSetT>
+struct bitwise<std::pair<Interval<DomainT,Compare>const, BitSetT> >
+{
+ typedef bitwise type;
+ typedef DomainT domain_type;
+ typedef DomainT codomain_type;
+ typedef DomainT element_type;
+ typedef typename BitSetT::word_type word_type;
+
+ BOOST_STATIC_CONSTANT(bit_range_type, digits = BitSetT::digits);
+};
+
+template <class SegmentIteratorT>
+class bit_element_iterator
+ : public boost::iterator_facade<
+ bit_element_iterator<SegmentIteratorT>
+ , typename bitwise<typename SegmentIteratorT::value_type>::element_type
+ , boost::bidirectional_traversal_tag
+ , typename bitwise<typename SegmentIteratorT::value_type>::element_type
+ >
+{
+public:
+ typedef SegmentIteratorT segment_iterator;
+ typedef typename SegmentIteratorT::value_type segment_type;
+ typedef typename first_element<segment_type>::type interval_type;
+ typedef typename interval_type::difference_type domain_difference_type;
+ typedef typename bitwise<segment_type>::domain_type domain_type;
+ typedef typename bitwise<segment_type>::codomain_type codomain_type;
+ typedef typename bitwise<segment_type>::element_type element_type;
+
+private:
+ struct enabler{};
+
+public:
+
+ bit_element_iterator()
+ : _saltator(neutron<segment_iterator>::value())
+ , _reptator(neutron<domain_difference_type>::value())
+ , _on_bit(ante)
+ {}
+
+ explicit bit_element_iterator(segment_iterator jumper, int state = iterator_state::dereferencable)
+ : _saltator(jumper)
+ , _reptator(neutron<domain_difference_type>::value())
+ {
+ if(state == iterator_state::dereferencable)
+ _on_bit = biterate::proceed<word_type,digits>::next(jumper->second.word(), ante);
+ }
+
+ template <class SaltatorT>
+ bit_element_iterator
+ ( bit_element_iterator<SaltatorT> const& other
+ , typename enable_if<boost::is_convertible<SaltatorT*,SegmentIteratorT*>, enabler>::type = enabler())
+ : _saltator(other._saltator)
+ , _reptator(other._reptator)
+ , _on_bit(other._on_bit)
+ {}
+
+private:
+ typedef typename bitwise<segment_type>::word_type word_type;
+ BOOST_STATIC_CONSTANT(bit_range_type, digits = bitwise<segment_type>::digits );
+ BOOST_STATIC_CONSTANT(bit_range_type, shift = log2_<digits>::value );
+ BOOST_STATIC_CONSTANT(bit_range_type, past = digits );
+ BOOST_STATIC_CONSTANT(bit_range_type, ante = -1 );
+
+ friend class boost::iterator_core_access;
+ template <class> friend class bit_element_iterator;
+
+ template <class SaltatorT>
+ bool equal(bit_element_iterator<SaltatorT> const& other) const
+ {
+ return this->_saltator == other._saltator
+ && this->_reptator == other._reptator;
+ }
+
+ void increment()
+ {
+ if(!next_bit()) // find and update the next on bit.
+ {
+ if(_reptator < pred(_saltator->first.length()))
+ {
+ ++_reptator;
+ _on_bit = ante;
+ }
+ else
+ {
+ ++_saltator;
+ _reptator = neutron<domain_difference_type>::value();
+ _on_bit = ante;
+ }
+ // The existence of at least one bit is asserted (absorber trait)
+ }
+ }
+
+ void decrement()
+ {
+ if(!prev_bit()) // find and update the previous on bit.
+ {
+ if(neutron<domain_difference_type>::value() < _reptator)
+ --_reptator;
+ else
+ {
+ --_saltator;
+ _reptator = _saltator->first.length();
+ --_reptator;
+ }
+ // The existence of at least one bit is asserted (absorber trait)
+ _on_bit = past;
+ next_bit();
+ }
+ }
+
+ element_type dereference()const
+ {
+ return (_saltator->first.first() << shift) + _reptator + _on_bit;
+ }
+
+ bool next_bit()
+ {
+ BOOST_ASSERT(ante <= _on_bit && _on_bit < past);
+ _on_bit = biterate::proceed<word_type,digits>::next(_saltator->second.word(), _on_bit);
+ return _on_bit != past;
+ }
+
+ bool prev_bit()
+ {
+ BOOST_ASSERT(ante < _on_bit && _on_bit <= past);
+ _on_bit = biterate::proceed<word_type,digits>::prev(_saltator->second.word(), _on_bit);
+ return _on_bit != ante;
+ }
+
+private:
+ segment_iterator _saltator; // satltare: to jump : the fast moving iterator
+ mutable domain_difference_type _reptator; // reptare: to sneak : the slow moving iterator 0 based
+ mutable bit_range_type _on_bit; // position of the current on bit.
+ // -1 <= _on_bit <= digits
+ // rend() end()
+};
+
+namespace biterate
+{
+
+#if (defined _MSC_VER)
+# pragma warning( push )
+// C4146: unary minus operator applied to unsigned type, result still unsigned
+# pragma warning( disable : 4146 )
+#endif
+
+
+static unsigned char index32[] =
+{
+ 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
+ 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
+};
+
+inline static nat32 high_bit(nat32 v)
+{
+ v |= v >> 1;
+ v |= v >> 2;
+ v |= v >> 4;
+ v |= v >> 8;
+ v |= v >> 16;
+ return (v >> 1) + 1;
+}
+
+template<typename WordT, bit_range_type Digits>
+struct proceed
+{
+ typedef nat32 word_type;
+ typedef proceed<WordT, Digits> type;
+
+ BOOST_STATIC_CONSTANT( word_type, digits = Digits );
+ BOOST_STATIC_CONSTANT( word_type, w1 = static_cast<word_type>(1) );
+ BOOST_STATIC_CONSTANT( word_type, top = w1 << (digits-w1) );
+ BOOST_STATIC_CONSTANT( word_type, factor = 0x077CB531U );
+ BOOST_STATIC_CONSTANT( word_type, shift = 27 );
+ BOOST_STATIC_CONSTANT( bit_range_type, ante = -1 );
+ BOOST_STATIC_CONSTANT( bit_range_type, past = digits );
+ BOOST_STATIC_CONSTANT( bit_range_type, last = past-1 );
+
+ static bit_range_type next(word_type value, bit_range_type cur_pos)
+ {
+ BOOST_ASSERT( ante <= cur_pos && cur_pos < past );
+
+ if(cur_pos == last)
+ return past;
+ else if(cur_pos == ante)
+ return index32[(((value & -value) * factor)) >> shift];
+ else
+ {
+ // next contains all bits of value above cur_pos
+ word_type next = value & ~((1<<(cur_pos+1))-1);
+ if(!next)
+ return past;
+ else
+ return index32[(((next & -next) * factor)) >> shift];
+ }
+ }
+
+ static bit_range_type prev(word_type value, bit_range_type cur_pos)
+ {
+ BOOST_ASSERT(ante < cur_pos && cur_pos <= past);
+
+ if(cur_pos == 0)
+ return ante;
+ else if(cur_pos == past)
+ return index32[((high_bit(value) * factor)) >> shift];
+ else
+ {
+ // next contains all bits of value above cur_pos
+ word_type prev = value & ((1<<cur_pos)-1);
+ if(!prev)
+ return ante;
+ else
+ return index32[((high_bit(prev) * factor)) >> shift];
+ }
+ }
+};
+
+
+template<> struct proceed<nat64, 64>
+{
+ typedef nat64 word_type;
+ typedef nat32 half_type;
+ typedef proceed<word_type,64> type;
+
+ BOOST_STATIC_CONSTANT( word_type, digits = 64 );
+ BOOST_STATIC_CONSTANT( word_type, w1 = static_cast<word_type>(1) );
+ BOOST_STATIC_CONSTANT( word_type, top = w1 << (digits-w1) );
+ BOOST_STATIC_CONSTANT( half_type, factor = 0x077CB531U );
+ BOOST_STATIC_CONSTANT( half_type, shift = 27 );
+ BOOST_STATIC_CONSTANT( bit_range_type, ante = -1 );
+ BOOST_STATIC_CONSTANT( bit_range_type, past = digits );
+ BOOST_STATIC_CONSTANT( bit_range_type, last = past-1 );
+ BOOST_STATIC_CONSTANT( bit_range_type, half = 32 );
+
+ BOOST_STATIC_CONSTANT( word_type, lower_mask = (w1 << 32)-w1 );
+
+
+ static half_type lower_next(word_type value, bit_range_type cur_pos)
+ {
+ return static_cast<half_type>(lower_mask & (value & ~((1<<(cur_pos+1))-1)));
+ }
+
+ static half_type upper_next(word_type value, bit_range_type cur_pos)
+ {
+ return static_cast<half_type>(value >> half) & ~((1<<(cur_pos-half+1))-1);
+ }
+
+ static bit_range_type next(word_type value, bit_range_type cur_pos)
+ {
+ BOOST_ASSERT(cur_pos < past );
+
+ if(cur_pos == last)
+ return past;
+ else if(cur_pos == ante)
+ {
+ half_type lower = static_cast<half_type>(lower_mask & value);
+ if(lower)
+ return index32[(((lower & -lower) * factor)) >> shift];
+ else
+ {
+ half_type upper = static_cast<half_type>(value >> half);
+ return half + index32[(((upper & -upper) * factor)) >> shift];
+ }
+ }
+ else
+ {
+ half_type low_next, up_next;
+ if(half-1 <= cur_pos)
+ if(up_next = upper_next(value, cur_pos))
+ return half + index32[(((up_next & -up_next) * factor)) >> shift];
+ else
+ return past;
+ else
+ if(low_next = lower_next(value, cur_pos))
+ return index32[(((low_next & -low_next) * factor)) >> shift];
+ else
+ {
+ half_type up_next = upper_next(value, cur_pos);
+ return half + index32[(((up_next & -up_next) * factor)) >> shift];
+ }
+ }
+ }
+
+
+ static half_type lower_previous(word_type value, bit_range_type cur_pos)
+ {
+ return static_cast<half_type>(lower_mask & (value & ((1<<(cur_pos))-1)));
+ }
+
+ static half_type upper_previous(word_type value, bit_range_type cur_pos)
+ {
+ return static_cast<half_type>(value >> half) & ((1<<(cur_pos-half))-1);
+ }
+
+ static bit_range_type prev(word_type value, bit_range_type cur_pos)
+ {
+ BOOST_ASSERT(ante < cur_pos);
+
+ if(cur_pos == 0)
+ return ante;
+ else if(cur_pos == past)
+ {
+ half_type upper = static_cast<half_type>(value >> half);
+ if(upper)
+ return half + index32[((high_bit(upper) * factor)) >> shift];
+ else
+ {
+ half_type lower = static_cast<half_type>(value & lower_mask);
+ return index32[((high_bit(lower) * factor)) >> shift];
+ }
+ }
+ else
+ {
+ half_type up_prev, low_prev;
+ if(half == cur_pos)
+ if(low_prev = static_cast<half_type>(lower_mask & value))
+ return index32[((high_bit(low_prev) * factor)) >> shift];
+ else
+ return ante;
+ else if(cur_pos < half || !(up_prev = upper_previous(value, cur_pos)))
+ if(low_prev = lower_previous(value,cur_pos))
+ return index32[((high_bit(low_prev) * factor)) >> shift];
+ else
+ return ante;
+ else
+ return half + index32[((high_bit(up_prev) * factor)) >> shift];
+ }
+ }
+
+};
+
+#if (defined _MSC_VER)
+# pragma warning( pop ) // C4146: unary minus operator applied to unsigned type,
+ // result still unsigned
+#endif
+
+} //namespace biterate
+
+}} // namespace itl boost
+
+#endif // BOOST_ITL_XT_DETAIL_BIT_ELEMENT_ITERATOR_HPP_JOFA_091109
+
+
+
Modified: sandbox/itl/boost/itl_xt/interval_bitset.hpp
==============================================================================
--- sandbox/itl/boost/itl_xt/interval_bitset.hpp (original)
+++ sandbox/itl/boost/itl_xt/interval_bitset.hpp 2009-11-12 11:33:24 EST (Thu, 12 Nov 2009)
@@ -12,9 +12,11 @@
#include <iostream> // to organize output
#include <boost/cstdint.hpp> // portable boost integers
#include <boost/operators.hpp> // to define operators with minimal effort
+#include <boost/itl/interval_map.hpp> // base of large bitsets
#include <boost/itl_xt/meta_log.hpp> // a meta logarithm
#include <boost/itl_xt/bits.hpp> // a bitset implementation
-#include <boost/itl/interval_map.hpp> // base of large bitsets
+#include <boost/itl_xt/detail/bit_element_iterator.hpp>
+//CL itl\boost\itl_xt\detail\bit_element_iterator.hpp
namespace boost{namespace itl
{
@@ -61,7 +63,8 @@
typedef DomainT element_type; // 0 .. 2^digits(element_type)-1
typedef DomainT condensed_type; // 0 .. (2^digits(element_type)-1)/digits(word_type)
typedef typename BitSetT::word_type word_type; // 0 .. 2^digits(word_type)-1
- typedef typename BitSetT::bit_type bit_type; // 0 .. digits(word_type)
+ typedef typename BitSetT::bit_type bit_type; // 0 .. digits(word_type)
+ typedef short narrow_type; // small signed type that includes bit_type
typedef BitSetT bitset_type;
typedef BitSetT data_type;
typedef typename std::size_t size_type;
@@ -71,11 +74,28 @@
typedef typename interval_bitmap_type::key_type key_type;
typedef typename interval_bitmap_type::value_type value_type;
- typedef typename interval_bitmap_type::iterator iterator;
- typedef typename interval_bitmap_type::const_iterator const_iterator;
-
typedef typename itl::set<DomainT,Compare,Alloc> atomized_type;
+ typedef typename interval_bitmap_type::iterator iterator;
+ typedef typename interval_bitmap_type::const_iterator const_iterator;
+ typedef typename interval_bitmap_type::reverse_iterator reverse_iterator;
+ typedef typename interval_bitmap_type::const_reverse_iterator const_reverse_iterator;
+
+ /// element iterator: Depreciated, see documentation.
+ typedef boost::itl::bit_element_iterator<iterator> element_iterator;
+ /// element const iterator: Depreciated, see documentation.
+ typedef boost::itl::bit_element_iterator<const_iterator> element_const_iterator;
+ /// element reverse iterator: Depreciated, see documentation.
+ typedef boost::itl::bit_element_iterator<reverse_iterator> element_reverse_iterator;
+ /// element const reverse iterator: Depreciated, see documentation.
+ typedef boost::itl::bit_element_iterator<const_reverse_iterator> element_const_reverse_iterator;
+
+ typedef typename interval_bitmap_type::pointer pointer;
+ typedef typename interval_bitmap_type::const_pointer const_pointer;
+ typedef typename interval_bitmap_type::reference reference;
+ typedef typename interval_bitmap_type::const_reference const_reference;
+
+
public:
bool operator ==(const interval_bitset& rhs)const{ return _map == rhs._map; }
bool operator < (const interval_bitset& rhs)const{ return _map < rhs._map; }
@@ -126,30 +146,51 @@
void show_matrix(const char off_on[2] = " 1")const;
std::string as_string()const{ return _map.as_string(); }
- iterator begin() { return _map.begin(); }
- const_iterator begin()const{ return _map.begin(); }
- iterator end() { return _map.end(); }
- const_iterator end()const { return _map.end(); }
+ //==========================================================================
+ //= Iterator related
+ //==========================================================================
+
+ iterator begin() { return _map.begin(); }
+ const_iterator begin()const { return _map.begin(); }
+ iterator end() { return _map.end(); }
+ const_iterator end()const { return _map.end(); }
+
+ reverse_iterator rbegin() { return _map.rbegin(); }
+ reverse_iterator rend() { return _map.rend(); }
+ const_reverse_iterator rbegin()const { return _map.rbegin(); }
+ const_reverse_iterator rend()const { return _map.rend(); }
+
+ //==========================================================================
+ //= Element iterator related
+ //==========================================================================
+ element_iterator elements_begin(){ return element_iterator(this->begin()); }
+ element_iterator elements_end() { return element_iterator(this->end(), iterator_state::end); }
+ element_const_iterator elements_begin()const{ return element_iterator(this->begin()); }
+ element_const_iterator elements_end() const{ return element_iterator(this->end(), iterator_state::end); }
+
+ element_reverse_iterator elements_rbegin(){ return element_reverse_iterator(this->rbegin()); }
+ element_reverse_iterator elements_rend() { return element_reverse_iterator(this->rend(), iterator_state::end); }
+ element_const_reverse_iterator elements_rbegin()const{ return element_reverse_iterator(this->rbegin()); }
+ element_const_reverse_iterator elements_rend() const{ return element_reverse_iterator(this->rend(), iterator_state::end); }
private:
typedef typename interval_bitmap_type::segment_type seg_type;
- static const word_type
- digits = bitset_type::digits,
- divisor = digits,
- shift = log2_<divisor>::value,
- w1 = static_cast<word_type>(1),
- mask = divisor - w1,
- all = ~static_cast<word_type>(0),
- top = w1 << (digits-w1);
+ BOOST_STATIC_CONSTANT( word_type, digits = bitset_type::digits );
+ BOOST_STATIC_CONSTANT( word_type, divisor = digits );
+ BOOST_STATIC_CONSTANT( word_type, shift = log2_<divisor>::value );
+ BOOST_STATIC_CONSTANT( word_type, w1 = static_cast<word_type>(1) );
+ BOOST_STATIC_CONSTANT( word_type, mask = divisor - w1 );
+ BOOST_STATIC_CONSTANT( word_type, all = ~static_cast<word_type>(0));
+ BOOST_STATIC_CONSTANT( word_type, top = w1 << (digits-w1) );
typedef itl::bits<unsigned char> PartsT;
enum { inner_part = 0, sub_part = 1, super_part = 2, inter_part = 4 };
typedef void (interval_bitset::*segment_combiner)(element_type, element_type, bitset_type);
- word_type from_lower_to(word_type bit)const{return bit==digits-w1 ? all : (1<<(bit+1))-1;}
- word_type to_upper_from(word_type bit)const{return bit==digits-w1 ? top : ~((1<<bit)-1); }
+ static word_type from_lower_to(word_type bit){return bit==top ? all : (1<<(bit+1))-1;}
+ static word_type to_upper_from(word_type bit){return bit==top ? top : ~((1<<bit)-1); }
interval_bitset& segment_apply(segment_combiner combine, const interval_type& operand)
{ // same as
Modified: sandbox/itl/libs/itl/example/large_bitset_/large_bitset.hpp
==============================================================================
--- sandbox/itl/libs/itl/example/large_bitset_/large_bitset.hpp (original)
+++ sandbox/itl/libs/itl/example/large_bitset_/large_bitset.hpp 2009-11-12 11:33:24 EST (Thu, 12 Nov 2009)
@@ -155,8 +155,8 @@
//]
//[large_bitset_bitset_filler
- word_type from_lower_to(word_type bit){return bit==digits-w1 ? all : (1<<(bit+1))-1;}
- word_type to_upper_from(word_type bit){return bit==digits-w1 ? top : ~((1<<bit)-1); }
+ static word_type from_lower_to(word_type bit){return bit==top ? all : (1<<(bit+1))-1;}
+ static word_type to_upper_from(word_type bit){return bit==top ? top : ~((1<<bit)-1); }
//]
//[large_bitset_segment_apply
Modified: sandbox/itl/libs/itl/test/fastest_interval_map_cases.hpp
==============================================================================
--- sandbox/itl/libs/itl/test/fastest_interval_map_cases.hpp (original)
+++ sandbox/itl/libs/itl/test/fastest_interval_map_cases.hpp 2009-11-12 11:33:24 EST (Thu, 12 Nov 2009)
@@ -75,6 +75,10 @@
(fastest_itl_interval_map_std_copy_via_inserter_4_bicremental_types)
{ interval_map_std_copy_via_inserter_4_bicremental_types<bicremental_type_4, int, partial_absorber, INTERVAL_MAP>();}
+BOOST_AUTO_TEST_CASE
+(fastest_itl_interval_map_element_iter_4_discrete_types)
+{ interval_map_element_iter_4_discrete_types<discrete_type_2, int, partial_absorber, INTERVAL_MAP>();}
+
#endif // BOOST_ITL_FASTEST_INTERVAL_MAP_CASES_HPP_JOFA_090702
Modified: sandbox/itl/libs/itl/test/fastest_interval_set_cases.hpp
==============================================================================
--- sandbox/itl/libs/itl/test/fastest_interval_set_cases.hpp (original)
+++ sandbox/itl/libs/itl/test/fastest_interval_set_cases.hpp 2009-11-12 11:33:24 EST (Thu, 12 Nov 2009)
@@ -56,6 +56,10 @@
(fastest_itl_interval_set_find_4_bicremental_types)
{ interval_set_find_4_bicremental_types<INTERVAL_SET, bicremental_type_1>();}
+BOOST_AUTO_TEST_CASE
+(fastest_itl_interval_set_element_iter_4_discrete_types)
+{ interval_set_element_iter_4_discrete_types<INTERVAL_SET, discrete_type_2>();}
+
#endif // BOOST_ITL_FASTEST_INTERVAL_SET_CASES_HPP_JOFA_090702
Modified: sandbox/itl/libs/itl/test/test_casual_/test_casual.cpp
==============================================================================
--- sandbox/itl/libs/itl/test/test_casual_/test_casual.cpp (original)
+++ sandbox/itl/libs/itl/test/test_casual_/test_casual.cpp 2009-11-12 11:33:24 EST (Thu, 12 Nov 2009)
@@ -24,7 +24,10 @@
#include <boost/itl/split_interval_set.hpp>
#include <boost/itl/interval_map.hpp>
#include <boost/itl/split_interval_map.hpp>
+#include <boost/itl/detail/element_iterator.hpp>
+#include <boost/itl_xt/detail/bit_element_iterator.hpp>
#include <boost/itl_xt/interval_bitset.hpp>
+#include <boost/itl_xt/list.hpp>
#include <limits>
#include <bitset>
@@ -35,21 +38,260 @@
using namespace unit_test;
using namespace boost::itl;
+
+
BOOST_AUTO_TEST_CASE(casual_test)
{
- typedef int T;
- typedef int U;
- typedef interval_map<int,int> IntervalMapT;
- typedef split_interval_map<int,int> SplitIntervalMapT;
- typedef interval_map<int,int> IntervalMapT;
-
- interval_bitset<nat> ibs;
-
- ibs += interval<nat>::rightopen(0,64);
- int sz = ibs.size();
- cout << ibs.size() << endl;
+ typedef interval_bitset<nat, bits8> InterBits8T;
+ InterBits8T lbs;
+
+ lbs.add(1).add(4).add(7).add(8);
+
+ InterBits8T::element_iterator it = lbs.elements_begin();
+ cout << "{";
+ while(it != lbs.elements_end())
+ {
+ int ele = *it;
+ cout << *it << " ";
+ if(ele == 8)
+ {
+ int dbg = 1;
+ }
+ ++it;
+ }
+ cout << "}";
+}
+
+
+/*
+BOOST_AUTO_TEST_CASE(biter64_test)
+{
+ typedef nat64 worT ;
+ const bit_range_type wdth = 64;
+
+ worT val = 1;
+ short pos = -1;
+ short nxt, prv;
+
+ cout << "------- bitter 64 ---------\n";
+
+ val = 0;
+ val |= 1ull << 63ull;
+ val |= 1ull << 62ull;
+ val |= 1ull << 55ull;
+ val |= 1ull << 44ull;
+ val |= 1ull << 33ull;
+ val |= 1ull << 32ull;
+ val |= 1ull << 31ull;
+ val |= 1ull << 30ull;
+ val |= 1ull << 22ull;
+ val |= 1ull << 11ull;
+ val |= 1ull << 3ull;
+ val |= 1ull << 2ull;
+ val |= 1ull << 1ull;
+ val |= 1ull << 0ull;
+ pos = -1;
+
+ while(pos < wdth)
+ {
+ nxt = biterate::proceed<worT,wdth>::next(val,pos);
+ cout << "next(" << val <<","<< pos << ")" << "=" << nxt << endl;
+ pos = nxt;
+ }
+ cout << "- - - - - - - - - -\n";
+ while(pos > -1)
+ {
+ if(pos == 31)
+ {
+ int dbg = 42;
+ }
+ prv = biterate::proceed<worT,wdth>::prev(val,pos);
+ cout << "prev(" << val <<","<< pos << ")" << "=" << prv << endl;
+ pos = prv;
+ }
+}
+
+BOOST_AUTO_TEST_CASE(biter64_up_test)
+{
+ typedef nat64 worT ;
+ const bit_range_type wdth = 64;
+
+ worT val = 1;
+ short pos = -1;
+ short nxt, prv;
+
+ cout << "------- bitter 64 up ---------\n";
+
+ val = 0;
+ val |= 1ull << 63ull;
+ val |= 1ull << 62ull;
+ val |= 1ull << 55ull;
+ val |= 1ull << 44ull;
+ val |= 1ull << 33ull;
+ val |= 1ull << 32ull;
+ pos = -1;
+
+ while(pos < wdth)
+ {
+ nxt = biterate::proceed<worT,wdth>::next(val,pos);
+ cout << "next(" << val <<","<< pos << ")" << "=" << nxt << endl;
+ pos = nxt;
+ }
+ cout << "- - - - - - - - - -\n";
+ while(pos > -1)
+ {
+ if(pos == 31)
+ {
+ int dbg = 42;
+ }
+ prv = biterate::proceed<worT,wdth>::prev(val,pos);
+ cout << "prev(" << val <<","<< pos << ")" << "=" << prv << endl;
+ pos = prv;
+ }
+}
+
+BOOST_AUTO_TEST_CASE(biter64_low_test)
+{
+ typedef nat64 worT ;
+ const bit_range_type wdth = 64;
+
+ worT val = 1;
+ short pos = -1;
+ short nxt, prv;
+
+ cout << "------- bitter 64 low ---------\n";
+
+ val = 0;
+ val |= 1ull << 31ull;
+ val |= 1ull << 30ull;
+ val |= 1ull << 22ull;
+ val |= 1ull << 11ull;
+ val |= 1ull << 3ull;
+ val |= 1ull << 2ull;
+ val |= 1ull << 1ull;
+ val |= 1ull << 0ull;
+ pos = -1;
+
+ while(pos < wdth)
+ {
+ nxt = biterate::proceed<worT,wdth>::next(val,pos);
+ cout << "next(" << val <<","<< pos << ")" << "=" << nxt << endl;
+ pos = nxt;
+ }
+ cout << "- - - - - - - - - -\n";
+ while(pos > -1)
+ {
+ if(pos == 64)
+ {
+ int dbg = 42;
+ }
+ prv = biterate::proceed<worT,wdth>::prev(val,pos);
+ cout << "prev(" << val <<","<< pos << ")" << "=" << prv << endl;
+ pos = prv;
+ }
+}
+
+BOOST_AUTO_TEST_CASE(biter32_test)
+{
+ typedef nat32 worT ;
+ const bit_range_type wdth = 32;
+
+ worT val = 1;
+ short pos = -1;
+ short nxt, prv;
- bool contains = ibs.contains(interval<nat>(11,63));
- cout << "contains=" << contains << endl;
+ cout << "------- bitter 32 ---------\n";
+
+ val = 0;
+ val |= 1ul << 31ul;
+ val |= 1ul << 30ul;
+ val |= 1ul << 22ul;
+ val |= 1ul << 11ul;
+ val |= 1ul << 3ul;
+ val |= 1ul << 2ul;
+ val |= 1ul << 1ul;
+ val |= 1ul << 0ul;
+ pos = -1;
+
+ while(pos < wdth)
+ {
+ if(pos == wdth)
+ {
+ int dbg = 42;
+ }
+ nxt = biterate::proceed<worT,wdth>::next(val,pos);
+ cout << "next(" << val <<","<< pos << ")" << "=" << nxt << endl;
+ pos = nxt;
+ }
+
+ cout << "- - - - - - - - - -\n";
+ while(pos > -1)
+ {
+ if(pos == 31)
+ {
+ int dbg = 42;
+ }
+ prv = biterate::proceed<worT,wdth>::prev(val,pos);
+ cout << "prev(" << val <<","<< pos << ")" << "=" << prv << endl;
+ pos = prv;
+ }
}
+
+BOOST_AUTO_TEST_CASE(biter16_test)
+{
+ typedef nat16 worT ;
+ const bit_range_type wdth = 16;
+
+ worT val = 1;
+ short pos = -1;
+ short nxt;
+
+ cout << "------- bitter 16 ---------\n";
+
+ val = 0;
+ val |= 1 << 15;
+ val |= 1 << 14;
+ val |= 1 << 12;
+ val |= 1 << 11;
+ val |= 1 << 3;
+ val |= 1 << 2;
+ val |= 1 << 1;
+ val |= 1 << 0;
+ pos = -1;
+
+ while(pos < wdth)
+ {
+ nxt = biterate::proceed<worT,wdth>::next(val,pos);
+ cout << "next(" << val <<","<< pos << ")" << "=" << nxt << endl;
+ pos = nxt;
+ }
+}
+
+BOOST_AUTO_TEST_CASE(biter8_test)
+{
+ typedef nat8 worT ;
+ const bit_range_type wdth = 8;
+
+ worT val = 1;
+ short pos = -1;
+ short nxt;
+
+ cout << "------- bitter 8 ---------\n";
+
+ val = 0;
+ val |= 1 << 7;
+ val |= 1 << 4;
+ val |= 1 << 2;
+ val |= 1 << 1;
+ val |= 1 << 0;
+ pos = -1;
+
+ while(pos < wdth)
+ {
+ nxt = biterate::proceed<worT,wdth>::next(val,pos);
+ cout << "next(" << static_cast<short>(val) <<","<< pos << ")" << "=" << nxt << endl;
+ pos = nxt;
+ }
+}
+*/
Modified: sandbox/itl/libs/itl/test/test_interval_map_cases.hpp
==============================================================================
--- sandbox/itl/libs/itl/test/test_interval_map_cases.hpp (original)
+++ sandbox/itl/libs/itl/test/test_interval_map_cases.hpp 2009-11-12 11:33:24 EST (Thu, 12 Nov 2009)
@@ -75,5 +75,9 @@
(test_itl_interval_map_std_copy_via_inserter_4_bicremental_types, T, bicremental_types)
{ interval_map_std_copy_via_inserter_4_bicremental_types<T, int, partial_absorber, INTERVAL_MAP>();}
+BOOST_AUTO_TEST_CASE_TEMPLATE
+(test_itl_interval_map_element_iter_4_discrete_types, T, discrete_types)
+{ interval_map_element_iter_4_discrete_types<T, int, partial_absorber, INTERVAL_MAP>();}
+
#endif // BOOST_ITL_TEST_INTERVAL_MAP_CASES_HPP_JOFA_090701
Modified: sandbox/itl/libs/itl/test/test_interval_map_shared.hpp
==============================================================================
--- sandbox/itl/libs/itl/test/test_interval_map_shared.hpp (original)
+++ sandbox/itl/libs/itl/test/test_interval_map_shared.hpp 2009-11-12 11:33:24 EST (Thu, 12 Nov 2009)
@@ -1234,5 +1234,49 @@
}
+template <class T, class U, class Trt,
+ template<class T, class U,
+ class Traits = Trt,
+ ITL_COMPARE Compare = ITL_COMPARE_INSTANCE(std::less, U),
+ ITL_COMBINE Combine = ITL_COMBINE_INSTANCE(itl::inplace_plus, U),
+ ITL_SECTION Section = ITL_SECTION_INSTANCE(itl::inplace_et, U),
+ template<class,ITL_COMPARE>class Interval = interval,
+ ITL_ALLOC Alloc = std::allocator
+ >class IntervalMap
+ >
+void interval_map_element_iter_4_discrete_types()
+{
+ typedef IntervalMap<T,U,Trt> IntervalMapT;
+ typedef typename IntervalMapT::element_iterator ReptatorT;
+ typedef std::vector<std::pair<T,U> > VectorT;
+
+ IntervalMapT map_a;
+ map_a.insert(IIv(1,3,1)).insert(IIv(6,7,2));
+
+ IntervalMapT::atomized_type ato_map_a;
+ ReptatorT el_it = map_a.elements_begin();
+
+ VectorT vec(5), cev(5);
+ vec[0]=sK_v(1,1);vec[1]=sK_v(2,1);vec[2]=sK_v(3,1);vec[3]=sK_v(6,2);vec[4]=sK_v(7,2);
+ cev[0]=sK_v(7,2);cev[1]=sK_v(6,2);cev[2]=sK_v(3,1);cev[3]=sK_v(2,1);cev[4]=sK_v(1,1);
+
+ VectorT dest;
+ std::copy(map_a.elements_begin(), map_a.elements_end(), std::back_inserter(dest));
+ BOOST_CHECK_EQUAL( vec == dest, true );
+
+ dest.clear();
+ std::copy(map_a.elements_rbegin(), map_a.elements_rend(), std::back_inserter(dest));
+ BOOST_CHECK_EQUAL( cev == dest, true );
+
+ dest.clear();
+ std::reverse_copy(map_a.elements_rbegin(), map_a.elements_rend(), std::back_inserter(dest));
+ BOOST_CHECK_EQUAL( vec == dest, true );
+
+ dest.clear();
+ std::reverse_copy(map_a.elements_begin(), map_a.elements_end(), std::back_inserter(dest));
+ BOOST_CHECK_EQUAL( cev == dest, true );
+
+}
+
#endif // __test_itl_interval_map_shared_h_JOFA_080920__
Modified: sandbox/itl/libs/itl/test/test_interval_set_/test_interval_set.cpp
==============================================================================
--- sandbox/itl/libs/itl/test/test_interval_set_/test_interval_set.cpp (original)
+++ sandbox/itl/libs/itl/test/test_interval_set_/test_interval_set.cpp 2009-11-12 11:33:24 EST (Thu, 12 Nov 2009)
@@ -7,6 +7,7 @@
+-----------------------------------------------------------------------------*/
#define BOOST_TEST_MODULE itl::interval_set unit test
#include <string>
+#include <vector>
#include <boost/mpl/list.hpp>
#include <boost/test/unit_test.hpp>
#include <boost/test/test_case_template.hpp>
Modified: sandbox/itl/libs/itl/test/test_interval_set_cases.hpp
==============================================================================
--- sandbox/itl/libs/itl/test/test_interval_set_cases.hpp (original)
+++ sandbox/itl/libs/itl/test/test_interval_set_cases.hpp 2009-11-12 11:33:24 EST (Thu, 12 Nov 2009)
@@ -56,6 +56,10 @@
(test_itl_interval_set_find_4_bicremental_types, T, bicremental_types)
{ interval_set_find_4_bicremental_types<INTERVAL_SET, T>();}
+BOOST_AUTO_TEST_CASE_TEMPLATE
+(test_itl_interval_set_element_iter_4_discrete_types, T, discrete_types)
+{ interval_set_element_iter_4_discrete_types<INTERVAL_SET, T>();}
+
#endif // BOOST_ITL_TEST_INTERVAL_SET_CASES_HPP_JOFA_090701
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 2009-11-12 11:33:24 EST (Thu, 12 Nov 2009)
@@ -719,5 +719,40 @@
BOOST_CHECK_EQUAL( found == set_a.end(), true );
}
+template <template< class T,
+ ITL_COMPARE Compare = ITL_COMPARE_INSTANCE(std::less, T),
+ template<class,ITL_COMPARE>class Interval = interval,
+ ITL_ALLOC Alloc = std::allocator
+ >class IntervalSet,
+ class T>
+void interval_set_element_iter_4_discrete_types()
+{
+ typedef IntervalSet<T> IntervalSetT;
+ typedef std::vector<T> VectorT;
+
+ IntervalSetT set_a;
+ set_a.add(I_I(1,3)).add(I_I(6,7));
+
+ VectorT vec(5), cev(5);
+ vec[0]=MK_v(1);vec[1]=MK_v(2);vec[2]=MK_v(3);vec[3]=MK_v(6);vec[4]=MK_v(7);
+ cev[0]=MK_v(7);cev[1]=MK_v(6);cev[2]=MK_v(3);cev[3]=MK_v(2);cev[4]=MK_v(1);
+
+ VectorT dest;
+ std::copy(set_a.elements_begin(), set_a.elements_end(), std::back_inserter(dest));
+ BOOST_CHECK_EQUAL( vec == dest, true );
+
+ dest.clear();
+ std::copy(set_a.elements_rbegin(), set_a.elements_rend(), std::back_inserter(dest));
+ BOOST_CHECK_EQUAL( cev == dest, true );
+
+ dest.clear();
+ std::reverse_copy(set_a.elements_begin(), set_a.elements_end(), std::back_inserter(dest));
+ BOOST_CHECK_EQUAL( cev == dest, true );
+
+ dest.clear();
+ std::reverse_copy(set_a.elements_rbegin(), set_a.elements_rend(), std::back_inserter(dest));
+ BOOST_CHECK_EQUAL( vec == dest, true );
+}
+
#endif // __test_itl_interval_set_shared_h_JOFA_080920__
Modified: sandbox/itl/libs/itl/test/test_split_interval_set_/test_split_interval_set_shared.cpp
==============================================================================
--- sandbox/itl/libs/itl/test/test_split_interval_set_/test_split_interval_set_shared.cpp (original)
+++ sandbox/itl/libs/itl/test/test_split_interval_set_/test_split_interval_set_shared.cpp 2009-11-12 11:33:24 EST (Thu, 12 Nov 2009)
@@ -53,4 +53,8 @@
(test_itl_interval_set_find_4_bicremental_types, T, bicremental_types)
{ interval_set_find_4_bicremental_types<INTERVAL_SET, T>();}
+BOOST_AUTO_TEST_CASE_TEMPLATE
+(test_itl_interval_set_find_4_bicremental_types, T, bicremental_types)
+{ interval_set_find_4_bicremental_types<INTERVAL_SET, T>();}
+
Modified: sandbox/itl/libs/itl/test/vc9_fast_tests.sln
==============================================================================
--- sandbox/itl/libs/itl/test/vc9_fast_tests.sln (original)
+++ sandbox/itl/libs/itl/test/vc9_fast_tests.sln 2009-11-12 11:33:24 EST (Thu, 12 Nov 2009)
@@ -33,6 +33,10 @@
EndProject
Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "vc9_fastest_set_itl_set", "fastest_set_itl_set_\vc9_fastest_set_itl_set.vcproj", "{33577D13-D562-4E3F-89F2-A8885151D13F}"
EndProject
+Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "vc9_fastest_split_interval_map", "fastest_split_interval_map_\vc9_fastest_split_interval_map.vcproj", "{EE61B7EF-EC45-4165-8B49-FD5B7D2A913E}"
+EndProject
+Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "vc9_fastest_split_interval_set", "fastest_split_interval_set_\vc9_fastest_split_interval_set.vcproj", "{EE61B7EF-EC45-4165-8B49-FD5B7D4A915C}"
+EndProject
Global
GlobalSection(SolutionConfigurationPlatforms) = preSolution
Debug|Win32 = Debug|Win32
@@ -103,6 +107,14 @@
{33577D13-D562-4E3F-89F2-A8885151D13F}.Debug|Win32.Build.0 = Debug|Win32
{33577D13-D562-4E3F-89F2-A8885151D13F}.Release|Win32.ActiveCfg = Release|Win32
{33577D13-D562-4E3F-89F2-A8885151D13F}.Release|Win32.Build.0 = Release|Win32
+ {EE61B7EF-EC45-4165-8B49-FD5B7D2A913E}.Debug|Win32.ActiveCfg = Debug|Win32
+ {EE61B7EF-EC45-4165-8B49-FD5B7D2A913E}.Debug|Win32.Build.0 = Debug|Win32
+ {EE61B7EF-EC45-4165-8B49-FD5B7D2A913E}.Release|Win32.ActiveCfg = Release|Win32
+ {EE61B7EF-EC45-4165-8B49-FD5B7D2A913E}.Release|Win32.Build.0 = Release|Win32
+ {EE61B7EF-EC45-4165-8B49-FD5B7D4A915C}.Debug|Win32.ActiveCfg = Debug|Win32
+ {EE61B7EF-EC45-4165-8B49-FD5B7D4A915C}.Debug|Win32.Build.0 = Debug|Win32
+ {EE61B7EF-EC45-4165-8B49-FD5B7D4A915C}.Release|Win32.ActiveCfg = Release|Win32
+ {EE61B7EF-EC45-4165-8B49-FD5B7D4A915C}.Release|Win32.Build.0 = Release|Win32
EndGlobalSection
GlobalSection(SolutionProperties) = preSolution
HideSolutionNode = FALSE