Subject: [Boost-commit] svn:boost r58050 - in sandbox/itl/boost: itl itl/detail itl_xt itl_xt/detail validate/driver validate/gentor validate/laws validate/validater
From: afojgo_at_[hidden]
Date: 2009-11-30 05:18:54
Author: jofaber
Date: 2009-11-30 05:18:48 EST (Mon, 30 Nov 2009)
New Revision: 58050
URL: http://svn.boost.org/trac/boost/changeset/58050
Log:
Added law based tests for element_iterators. Bugfixed bit_element_iterators for interval_bitset.
Added documentation on element_iterators. Stable {msvc-9.0}
Added:
sandbox/itl/boost/validate/driver/sorted_associative_bitset_driver.hpp (contents, props changed)
sandbox/itl/boost/validate/driver/sorted_associative_map_driver.hpp (contents, props changed)
sandbox/itl/boost/validate/driver/sorted_associative_set_driver.hpp (contents, props changed)
sandbox/itl/boost/validate/laws/atomic_equivalence.hpp (contents, props changed)
sandbox/itl/boost/validate/validater/sorted_associative_validater.hpp (contents, props changed)
Text files modified:
sandbox/itl/boost/itl/detail/mapped_reference.hpp | 13 +
sandbox/itl/boost/itl/interval_base_map.hpp | 8
sandbox/itl/boost/itl/interval_base_set.hpp | 8
sandbox/itl/boost/itl_xt/bits.hpp | 48 +++-
sandbox/itl/boost/itl_xt/detail/bit_element_iterator.hpp | 364 +++++++++++++++++++++++++++++----------
sandbox/itl/boost/itl_xt/interval_bitset.hpp | 80 +++++++-
sandbox/itl/boost/validate/gentor/randomgentor.hpp | 13
sandbox/itl/boost/validate/laws/function_equality.hpp | 2
sandbox/itl/boost/validate/validater/law_validater.hpp | 11
9 files changed, 395 insertions(+), 152 deletions(-)
Modified: sandbox/itl/boost/itl/detail/mapped_reference.hpp
==============================================================================
--- sandbox/itl/boost/itl/detail/mapped_reference.hpp (original)
+++ sandbox/itl/boost/itl/detail/mapped_reference.hpp 2009-11-30 05:18:48 EST (Mon, 30 Nov 2009)
@@ -8,6 +8,9 @@
#ifndef BOOST_ITL_DETAIL_MAPPED_REFERENCE_HPP_JOFA_091108
#define BOOST_ITL_DETAIL_MAPPED_REFERENCE_HPP_JOFA_091108
+#include <boost/type_traits/is_const.hpp>
+#include <boost/mpl/if.hpp>
+
namespace boost{namespace itl
{
@@ -17,11 +20,15 @@
typedef FirstT first_type;
typedef SecondT second_type;
typedef mapped_reference type;
+ typedef typename
+ mpl::if_<is_const<second_type>,
+ second_type&,
+ const second_type&>::type second_reference_type;
- const FirstT& first;
- SecondT& second;
+ const FirstT& first;
+ second_reference_type second;
- mapped_reference(const FirstT& fst, SecondT& snd) : first(fst), second(snd){}
+ mapped_reference(const FirstT& fst, second_reference_type snd) : first(fst), second(snd){}
template<class FstT, class SndT>
mapped_reference(const mapped_reference<FstT, SndT>& source):
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-30 05:18:48 EST (Mon, 30 Nov 2009)
@@ -669,13 +669,13 @@
//==========================================================================
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_const_iterator elements_begin()const{ return element_const_iterator(this->begin()); }
+ element_const_iterator elements_end() const{ return element_const_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()); }
+ element_const_reverse_iterator elements_rbegin()const{ return element_const_reverse_iterator(this->rbegin()); }
+ element_const_reverse_iterator elements_rend() const{ return element_const_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-30 05:18:48 EST (Mon, 30 Nov 2009)
@@ -417,13 +417,13 @@
//==========================================================================
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_const_iterator elements_begin()const{ return element_const_iterator(this->begin()); }
+ element_const_iterator elements_end() const{ return element_const_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()); }
+ element_const_reverse_iterator elements_rbegin()const{ return element_const_reverse_iterator(this->rbegin()); }
+ element_const_reverse_iterator elements_rend() const{ return element_const_reverse_iterator(this->rend()); }
//==========================================================================
//= Morphisms
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-30 05:18:48 EST (Mon, 30 Nov 2009)
@@ -64,7 +64,8 @@
typedef bit_range_type bit_type;
typedef bit_type element_type; // pretty short: 0 <= max < digits
typedef bit_type size_type;
- BOOST_STATIC_CONSTANT(bit_type, digits = std::numeric_limits<NaturalT>::digits);
+ BOOST_STATIC_CONSTANT(bit_type, digits = std::numeric_limits<NaturalT>::digits);
+ BOOST_STATIC_CONSTANT(word_type, w1 = static_cast<word_type>(1) );
bits():_bits(){}
explicit bits(word_type value):_bits(value){}
@@ -91,11 +92,13 @@
bool operator == (const bits& value)const{return _bits == value._bits;}
bool empty()const { return _bits == 0; }
- bool contains(element_type element)const { return 0 != ((1 << element) & _bits); }
+ bool contains(element_type element)const { return 0 != ((w1 << element) & _bits); }
bool contains(const bits& sub)const { return inclusion::subset==inclusion_compare(sub,*this); }
size_type cardinality()const{ return bitcount::count<word_type, digits>::apply(_bits); }
size_type size()const { return cardinality(); }
+ std::string as_string(const char off_on[2] = " 1")const;
+
private:
word_type _bits;
};
@@ -120,6 +123,15 @@
else return inclusion::equal;
}
+template<class NaturalT>
+std::string bits<NaturalT>::as_string(const char off_on[2])const
+{
+ std::string sequence;
+ for(int bit=0; bit < digits; bit++)
+ sequence += contains(bit) ? off_on[1] : off_on[0];
+ return sequence;
+}
+
template<class CharType, class CharTraits, class NaturalT>
std::basic_ostream<CharType, CharTraits>& operator <<
@@ -183,21 +195,21 @@
};
-//template<>
-//struct count<unsigned int, 32>
-//{
-// typedef unsigned int word_type;
-// typedef count<word_type,32> type;
-//
-// static bit_range_type apply(word_type value)
-// {
-// return table[ value & 0xfful]
-// + table[(value >> 8) & 0xfful]
-// + table[(value >> 16) & 0xfful]
-// + table[(value >> 24) & 0xfful];
-// }
-//
-//};
+template<>
+struct count<unsigned int, 32>
+{
+ typedef unsigned int word_type;
+ typedef count<word_type,32> type;
+
+ static bit_range_type apply(word_type value)
+ {
+ return table[ value & 0xfful]
+ + table[(value >> 8) & 0xfful]
+ + table[(value >> 16) & 0xfful]
+ + table[(value >> 24) & 0xfful];
+ }
+
+};
template<>
struct count<nat64, 64>
@@ -205,7 +217,7 @@
typedef nat64 word_type;
typedef count<word_type,64> type;
- static bit_range_type compute(word_type value)
+ static bit_range_type apply(word_type value)
{
return table[ value & 0xffull]
+ table[(value >> 8) & 0xffull]
Modified: sandbox/itl/boost/itl_xt/detail/bit_element_iterator.hpp
==============================================================================
--- sandbox/itl/boost/itl_xt/detail/bit_element_iterator.hpp (original)
+++ sandbox/itl/boost/itl_xt/detail/bit_element_iterator.hpp 2009-11-30 05:18:48 EST (Mon, 30 Nov 2009)
@@ -1,5 +1,8 @@
/*-----------------------------------------------------------------------------+
Copyright (c) 2009-2009: Joachim Faulhaber
+Copyright (c) 1998: Charles E. Leiserson, Harald Prokop, Keith H. Randall
+ (Bit sequencing using DeBruin sequence
+ http://supertech.csail.mit.edu/papers/debruijn.pdf)
+------------------------------------------------------------------------------+
Distributed under the Boost Software License, Version 1.0.
(See accompanying file LICENCE.txt or copy at
@@ -9,15 +12,11 @@
#define BOOST_ITL_XT_DETAIL_BIT_ELEMENT_ITERATOR_HPP_JOFA_091109
#include <boost/itl_xt/bits.hpp>
+#include <boost/mpl/not.hpp>
namespace boost{namespace itl
{
-namespace iterator_state
-{
- enum { dereferencable, end };
-}
-
//------------------------------------------------------------------------------
template<class SegmentT> struct bitwise;
@@ -28,11 +27,15 @@
typedef DomainT domain_type;
typedef DomainT codomain_type;
typedef DomainT element_type;
+ typedef BitSetT bitset_type;
typedef typename BitSetT::word_type word_type;
BOOST_STATIC_CONSTANT(bit_range_type, digits = BitSetT::digits);
};
+namespace biterate
+{ template<class IteratorT, bool Forward> struct proceed; }
+
template <class SegmentIteratorT>
class bit_element_iterator
: public boost::iterator_facade<
@@ -47,9 +50,24 @@
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>::bitset_type bitset_type;
+ typedef typename bitwise<segment_type>::word_type word_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;
+ typedef element_type value_type;
+ typedef element_type key_type;
+ typedef element_type data_type;
+
+ BOOST_STATIC_CONSTANT(bit_range_type, digits = bitwise<segment_type>::digits );
+ BOOST_STATIC_CONSTANT(bool, is_forward = mpl::not_<is_reverse<SegmentIteratorT> >::value );
+
+ typedef typename biterate::proceed<segment_iterator,is_forward> Proceed;
+
+ BOOST_STATIC_CONSTANT(bit_range_type, before = Proceed::before );
+ BOOST_STATIC_CONSTANT(bit_range_type, ante = Proceed::ante );
+ BOOST_STATIC_CONSTANT(bit_range_type, past = Proceed::past );
+ BOOST_STATIC_CONSTANT(bit_range_type, beyond = Proceed::beyond );
private:
struct enabler{};
@@ -59,16 +77,14 @@
bit_element_iterator()
: _saltator(neutron<segment_iterator>::value())
, _reptator(neutron<domain_difference_type>::value())
- , _on_bit(ante)
+ , _on_bit(before)
{}
- explicit bit_element_iterator(segment_iterator jumper, int state = iterator_state::dereferencable)
+ bit_element_iterator(segment_iterator jumper, bit_range_type start_pos)
: _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);
- }
+ , _on_bit(start_pos)
+ {}
template <class SaltatorT>
bit_element_iterator
@@ -80,11 +96,7 @@
{}
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 );
+ BOOST_STATIC_CONSTANT(bit_range_type, shift = log2_<digits>::value );
friend class boost::iterator_core_access;
template <class> friend class bit_element_iterator;
@@ -92,72 +104,128 @@
template <class SaltatorT>
bool equal(bit_element_iterator<SaltatorT> const& other) const
{
- return this->_saltator == other._saltator
- && this->_reptator == other._reptator;
+ if( _saltator != other._saltator)
+ return false;
+ else if(_reptator != other._reptator)
+ return false;
+ else if(this->_on_bit == ante)
+ return other._on_bit == beyond || other.is_segment_begin();
+ else
+ return _on_bit == other._on_bit;
}
void increment()
{
- if(!next_bit()) // find and update the next on bit.
- {
+ if(_on_bit == ante)
+ first_bit();
+
+ next_bit();
+ if(_on_bit == past)
+ { // The current bitset passed the end
if(_reptator < pred(_saltator->first.length()))
- {
+ {
++_reptator;
- _on_bit = ante;
- }
+ _on_bit = ante;
+ }
else
{
++_saltator;
+ // NOTE: increment and dereference are unsecure now, because
+ // _saltator can (finally) be end here. decrement is secure.
_reptator = neutron<domain_difference_type>::value();
- _on_bit = ante;
+ _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.
- {
+ prev_bit();
+ if(_on_bit == ante)
+ { // The current bitset passed the beginning
if(neutron<domain_difference_type>::value() < _reptator)
- --_reptator;
+ {
+ --_reptator;
+ _on_bit = past;
+ }
else
{
+ //assert: _saltator is not at begin here.
--_saltator;
- _reptator = _saltator->first.length();
- --_reptator;
+ // NOW: decrement insecure, because _saltator can (finally) be
+ // begin here. increment and dereference are secure.
+ _reptator = _saltator->first.length();
+ --_reptator;
+ _on_bit = past;
}
- // 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;
+ if(_on_bit == ante)
+ first_bit();
+ else if(_on_bit == past)
+ last_bit();
+
+ return (Proceed::inter_value(_reptator, _saltator->first) << shift) + _on_bit;
+ }
+
+ void first_bit()const
+ {
+ // Because interval_bitsets are neutron absorbers, _saltator->second.word() is not a neutron
+ _on_bit = Proceed::first_bit(_saltator->second.word());
+ }
+
+ void last_bit()const
+ {
+ // Because interval_bitsets are neutron absorbers, _saltator->second.word() is not a neutron
+ _on_bit = Proceed::last_bit(_saltator->second.word());
}
bool next_bit()
{
- BOOST_ASSERT(ante <= _on_bit && _on_bit < past);
- _on_bit = biterate::proceed<word_type,digits>::next(_saltator->second.word(), _on_bit);
+ if(_on_bit == before)
+ {
+ ++_saltator;
+ _reptator = neutron<domain_difference_type>::value();
+ _on_bit = Proceed::first_bit(_saltator->second.word());
+ }
+ else
+ _on_bit = Proceed::next_bit(_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);
+ if(_on_bit == beyond)
+ {
+ --_saltator;
+ _reptator = _saltator->first.length();
+ --_reptator;
+ _on_bit = Proceed::last_bit(_saltator->second.word());
+ }
+ else
+ _on_bit = Proceed::prev_bit(_saltator->second.word(), _on_bit);
+
return _on_bit != ante;
}
+ bool is_segment_begin()const
+ {
+ return _reptator == neutron<domain_difference_type>::value()
+ && 0 <= _on_bit && _on_bit < digits
+ && _on_bit == Proceed::first_bit(_saltator->second.word());
+ }
+
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()
+ // rend() end()
+
};
namespace biterate
@@ -169,7 +237,15 @@
# pragma warning( disable : 4146 )
#endif
+/* Bit-iteration is coded on the bases of the work of
+Charles E. Leiserson, Harald Prokop, Keith H. Randall
+ http://supertech.csail.mit.edu/papers/debruijn.pdf
+
+and also Sean Eron Anderson:
+http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogDeBruijn
+*/
+//DeBruin sequence
static unsigned char index32[] =
{
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
@@ -187,28 +263,29 @@
}
template<typename WordT, bit_range_type Digits>
-struct proceed
+struct forward
{
typedef nat32 word_type;
- typedef proceed<WordT, Digits> type;
+ typedef forward<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 );
+ 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)
+ static bit_range_type first_bit(word_type value)
{
- BOOST_ASSERT( ante <= cur_pos && cur_pos < past );
+ return index32[(((value & -value) * factor)) >> shift];
+ }
+ static bit_range_type next_bit(word_type value, bit_range_type cur_pos)
+ {
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
@@ -220,14 +297,15 @@
}
}
- static bit_range_type prev(word_type value, bit_range_type cur_pos)
+ static bit_range_type last_bit(word_type value)
{
- BOOST_ASSERT(ante < cur_pos && cur_pos <= past);
+ return index32[((high_bit(value) * factor)) >> shift];
+ }
+ static bit_range_type prev_bit(word_type value, bit_range_type cur_pos)
+ {
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
@@ -241,22 +319,21 @@
};
-template<> struct proceed<nat64, 64>
+template<> struct forward<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 );
+ typedef forward<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 );
@@ -270,23 +347,22 @@
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)
+ static bit_range_type first_bit(word_type value)
{
- BOOST_ASSERT(cur_pos < past );
+ 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];
+ }
+ }
+ static bit_range_type next_bit(word_type value, bit_range_type cur_pos)
+ {
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;
@@ -298,11 +374,10 @@
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);
+ else if(half_type up_next = upper_next(value, cur_pos))
return half + index32[(((up_next & -up_next) * factor)) >> shift];
- }
+ else
+ return past;
}
}
@@ -317,23 +392,22 @@
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)
+ static bit_range_type last_bit(word_type value)
{
- BOOST_ASSERT(ante < cur_pos);
+ 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];
+ }
+ }
+ static bit_range_type prev_bit(word_type value, bit_range_type 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;
@@ -351,9 +425,101 @@
return half + index32[((high_bit(up_prev) * factor)) >> shift];
}
}
+};
+
+template<class IteratorT, bool Forward>
+struct proceed{};
+
+template<class IteratorT>
+struct proceed<IteratorT,true>
+{
+ typedef IteratorT iterator;
+ typedef typename iterator::value_type segment_type;
+ typedef typename first_element<segment_type>::type interval_type;
+ typedef typename interval_type::difference_type difference_type;
+ 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, before = -2 );
+ BOOST_STATIC_CONSTANT(bit_range_type, ante = -1 );
+ BOOST_STATIC_CONSTANT(bit_range_type, past = digits );
+ BOOST_STATIC_CONSTANT(bit_range_type, beyond = digits+1 );
+
+ static bit_range_type first_bit(word_type value)
+ {
+ unsigned int dbg_word_value = value; //CL
+ return forward<word_type,digits>::first_bit(value);
+ }
+
+ static bit_range_type last_bit(word_type value)
+ { return forward<word_type,digits>::last_bit(value); }
+
+ static bit_range_type next_bit(word_type value, bit_range_type cur_pos)
+ { return forward<word_type,digits>::next_bit(value, cur_pos); }
+
+ static bit_range_type prev_bit(word_type value, bit_range_type cur_pos)
+ { return forward<word_type,digits>::prev_bit(value, cur_pos); }
+
+ static difference_type inter_value(difference_type reptator, const interval_type inter_val)
+ {
+ return inter_val.first() + reptator;
+ }
+
+ static difference_type inter_base(const iterator& iter)
+ {
+ return neutron<difference_type>::value();
+ }
+
+ static difference_type inter_ceil(const iterator& iter)
+ {
+ return iter->first.length();
+ }
+};
+template<class IteratorT>
+struct proceed<IteratorT,false>
+{
+ typedef IteratorT iterator;
+ typedef typename iterator::value_type segment_type;
+ typedef typename first_element<segment_type>::type interval_type;
+ typedef typename interval_type::difference_type difference_type;
+ 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, beyond = -2 );
+ BOOST_STATIC_CONSTANT(bit_range_type, past = -1 );
+ BOOST_STATIC_CONSTANT(bit_range_type, ante = digits );
+ BOOST_STATIC_CONSTANT(bit_range_type, before = digits+1 );
+
+ static bit_range_type first_bit(word_type value)
+ { return forward<word_type,digits>::last_bit(value); }
+
+ static bit_range_type last_bit(word_type value)
+ { return forward<word_type,digits>::first_bit(value); }
+
+ static bit_range_type next_bit(word_type value, bit_range_type cur_pos)
+ { return forward<word_type,digits>::prev_bit(value, cur_pos); }
+
+ static bit_range_type prev_bit(word_type value, bit_range_type cur_pos)
+ { return forward<word_type,digits>::next_bit(value, cur_pos); }
+
+ static difference_type inter_value(difference_type reptator, const interval_type inter_val)
+ {
+ return inter_val.last() - reptator;
+ }
+
+ static difference_type inter_base(const iterator& iter)//CL . . .
+ {
+ return iter->first.length();
+ }
+
+ static difference_type inter_ceil(const iterator& iter)
+ {
+ return neutron<difference_type>::value();
+ }
};
+
#if (defined _MSC_VER)
# pragma warning( pop ) // C4146: unary minus operator applied to unsigned type,
// result still unsigned
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-30 05:18:48 EST (Mon, 30 Nov 2009)
@@ -16,7 +16,9 @@
#include <boost/itl_xt/meta_log.hpp> // a meta logarithm
#include <boost/itl_xt/bits.hpp> // a bitset implementation
#include <boost/itl_xt/detail/bit_element_iterator.hpp>
-//CL itl\boost\itl_xt\detail\bit_element_iterator.hpp
+
+#include <boost/itl/interval_morphism.hpp> //JODO Separate aspects and concerns
+
namespace boost{namespace itl
{
@@ -163,21 +165,56 @@
//==========================================================================
//= 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); }
+ element_iterator elements_begin()
+ {
+ if(this->begin()==this->end())
+ return element_iterator(this->begin(), element_iterator::beyond);
+ else
+ return element_iterator(this->begin(), element_iterator::ante );
+ }
+
+ element_iterator elements_end()
+ { return element_iterator(this->end(), element_iterator::beyond); }
+
+ element_const_iterator elements_begin()const
+ {
+ if(this->begin()==this->end())
+ return element_const_iterator(this->begin(), element_iterator::beyond);
+ else
+ return element_const_iterator(this->begin(), element_iterator::ante );
+ }
+
+ element_const_iterator elements_end()const
+ { return element_const_iterator(this->end(), element_iterator::beyond); }
+
+ element_reverse_iterator elements_rbegin()
+ {
+ if(this->rbegin()==this->rend())
+ return element_reverse_iterator(this->rbegin(), element_iterator::before);
+ else
+ return element_reverse_iterator(this->rbegin(), element_iterator::past );
+ }
+
+ element_reverse_iterator elements_rend()
+ { return element_reverse_iterator(this->rend(), element_iterator::before); }
+
+ element_const_reverse_iterator elements_rbegin()const
+ {
+ if(this->rbegin()==this->rend())
+ return element_const_reverse_iterator(this->rbegin(), element_iterator::before);
+ else
+ return element_const_reverse_iterator(this->rbegin(), element_iterator::past );
+ }
+
+ element_const_reverse_iterator elements_rend()const
+ { return element_const_reverse_iterator(this->rend(), element_iterator::before); }
private:
typedef typename interval_bitmap_type::segment_type seg_type;
BOOST_STATIC_CONSTANT( word_type, digits = bitset_type::digits );
BOOST_STATIC_CONSTANT( word_type, divisor = digits );
+ BOOST_STATIC_CONSTANT( word_type, last = digits-1 );
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 );
@@ -189,11 +226,11 @@
typedef void (interval_bitset::*segment_combiner)(element_type, element_type, bitset_type);
- 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); }
+ static word_type from_lower_to(word_type bit){return bit==last ? all : (w1<<(bit+w1))-w1;}
+ static word_type to_upper_from(word_type bit){return bit==last ? top : ~((w1<<bit)-w1); }
interval_bitset& segment_apply(segment_combiner combine, const interval_type& operand)
- { // same as
+ { // same as
condensed_type base = operand.first() >> shift, // operand.first()/ divisor
ceil = operand.last() >> shift; // operand.last() / divisor
word_type base_rest = operand.first() & mask , // operand.first()% divisor
@@ -383,6 +420,23 @@
}
};
+namespace Interval
+{
+ template <typename DomainT, typename BitSetT>
+ struct Atomize<itl::set<DomainT>, interval_bitset<DomainT, BitSetT> >
+ {
+ void operator()( itl::set<DomainT>& atomized,
+ const interval_bitset<DomainT, BitSetT>& clustered)
+ {
+ typedef interval_bitset<DomainT, BitSetT> InterBitsetT;
+ InterBitsetT::element_const_iterator bit_ = clustered.elements_begin();
+ while(bit_ != clustered.elements_end())
+ atomized.insert(*bit_++);
+ }
+ };
+
+} // namespace Interval
+
}} // namespace itl boost
Added: sandbox/itl/boost/validate/driver/sorted_associative_bitset_driver.hpp
==============================================================================
--- (empty file)
+++ sandbox/itl/boost/validate/driver/sorted_associative_bitset_driver.hpp 2009-11-30 05:18:48 EST (Mon, 30 Nov 2009)
@@ -0,0 +1,72 @@
+/*-----------------------------------------------------------------------------+
+A Law Based Test Automaton 'LaBatea'
+Author: Joachim Faulhaber
+Copyright (c) 2007-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_VALIDATE_DRIVER_SORTED_ASSOCIATIVE_BITSET_DRIVER_HPP_JOFA_091126
+#define BOOST_VALIDATE_DRIVER_SORTED_ASSOCIATIVE_BITSET_DRIVER_HPP_JOFA_091126
+
+#include <iostream>
+#include <stdio.h>
+#include <boost/validate/validater/sorted_associative_validater.hpp>
+#include <boost/validate/driver/itl_driver.hpp>
+#include <boost/validate/utility.hpp>
+
+namespace boost{namespace itl
+{
+
+ class sorted_associative_bitset_driver : public itl_driver
+ {
+ public:
+ sorted_associative_bitset_driver() { setProfile(); }
+
+ void setProfile()
+ {
+ setValid(true);
+ _freeChoice.setSize(FreeChoice::FreeChoice_size);
+ _freeChoice.setMaxWeights(100);
+ _freeChoice[FreeChoice::_1] = 20;
+ _freeChoice[FreeChoice::_2] = 20;
+ _freeChoice[FreeChoice::_3] = 20;
+ _freeChoice[FreeChoice::_4] = 20;
+ _freeChoice[FreeChoice::_5] = 20;
+ setRootTypeNames();
+ _freeChoice.init();
+
+ if(!_freeChoice.is_consistent())
+ {
+ setValid(false);
+ std::cout << _freeChoice.inconsitencyMessage("interval_bitset_driver::setProfile()") << std::endl;
+ }
+ }
+
+ algebra_validater* chooseValidater()
+ {
+ int freeChoice = _freeChoice.some();
+
+ switch(freeChoice)
+ {
+ case FreeChoice::_1:
+ return new sorted_associative_validater< interval_bitset<int, bits<unsigned char> >, itl::list<int> >;
+ case FreeChoice::_2:
+ return new sorted_associative_validater< interval_bitset<int, bits<unsigned short> >, itl::list<int> >;
+ case FreeChoice::_3:
+ return new sorted_associative_validater< interval_bitset<int, bits<unsigned int> >, itl::list<int> >;
+ case FreeChoice::_4:
+ return new sorted_associative_validater< interval_bitset<int, bits<unsigned long> >, itl::list<int> >;
+ case FreeChoice::_5:
+ return new sorted_associative_validater< interval_bitset<int, bits<unsigned long long> >, itl::list<int> >;
+ default: return choiceError(ITL_LOCATION("freeChoice:\n"), freeChoice, _freeChoice);
+ } //switch()
+
+ return NULL; //just to please the compiler ;)
+ }
+ };
+
+}} // namespace itl boost
+
+#endif // BOOST_VALIDATE_DRIVER_SORTED_ASSOCIATIVE_BITSET_DRIVER_HPP_JOFA_091126
Added: sandbox/itl/boost/validate/driver/sorted_associative_map_driver.hpp
==============================================================================
--- (empty file)
+++ sandbox/itl/boost/validate/driver/sorted_associative_map_driver.hpp 2009-11-30 05:18:48 EST (Mon, 30 Nov 2009)
@@ -0,0 +1,135 @@
+/*-----------------------------------------------------------------------------+
+A Law Based Test Automaton 'LaBatea'
+Author: Joachim Faulhaber
+Copyright (c) 2007-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_VALIDATE_DRIVER_SORTED_ASSOCIATIVE_MAP_DRIVER_HPP_JOFA_091126
+#define BOOST_VALIDATE_DRIVER_SORTED_ASSOCIATIVE_MAP_DRIVER_HPP_JOFA_091126
+
+#include <iostream>
+#include <stdio.h>
+#include <boost/validate/validater/sorted_associative_validater.hpp>
+#include <boost/validate/driver/itl_driver.hpp>
+#include <boost/validate/utility.hpp>
+
+namespace boost{namespace itl
+{
+
+ class sorted_associative_map_driver : public itl_driver
+ {
+ public:
+ sorted_associative_map_driver() { setProfile(); }
+
+ void setProfile()
+ {
+ setValid(true);
+ _rootChoice.setSize(RootType::Types_size);
+ _rootChoice.setMaxWeights(100);
+ _rootChoice[RootType::itl_set] = 0;
+ _rootChoice[RootType::interval_set] = 0;
+ _rootChoice[RootType::separate_interval_set] = 0;
+ _rootChoice[RootType::split_interval_set] = 0;
+ _rootChoice[RootType::itl_map] = 0;
+ _rootChoice[RootType::interval_map] = 50;
+ _rootChoice[RootType::split_interval_map] = 50;
+ setRootTypeNames();
+ _rootChoice.init();
+
+ _domainChoice.setSize(DomainType::DomainTypes_size);
+ _domainChoice.setMaxWeights(100);
+ _domainChoice[DomainType::Int] = 100;
+ _domainChoice[DomainType::Double] = 0;
+ setDomainTypeNames();
+ _domainChoice.init();
+
+ _codomainChoice.setSize(CodomainType::CodomainTypes_size);
+ _codomainChoice.setMaxWeights(100);
+ _codomainChoice[CodomainType::Nat] = 100;
+ _codomainChoice[CodomainType::Int] = 0;
+ _codomainChoice[CodomainType::Double] = 0;
+ _codomainChoice[CodomainType::set_int] = 0;
+ setCodomainTypeNames();
+ _codomainChoice.init();
+
+ _neutronizerChoice.setSize(NeutronHandlerType::NeutronHandlerTypes_size);
+ _neutronizerChoice.setMaxWeights(100);
+ _neutronizerChoice[NeutronHandlerType::partial_absorber] = 25;
+ _neutronizerChoice[NeutronHandlerType::partial_enricher] = 25;
+ _neutronizerChoice[NeutronHandlerType::total_absorber] = 25;
+ _neutronizerChoice[NeutronHandlerType::total_enricher] = 25;
+ setNeutronHandlerTypeNames();
+ _neutronizerChoice.init();
+
+ if(!_rootChoice.is_consistent())
+ {
+ setValid(false);
+ std::cout << _rootChoice.inconsitencyMessage("sorted_associative_map_driver::setProfile()") << std::endl;
+ }
+
+ if(!_domainChoice.is_consistent())
+ {
+ setValid(false);
+ std::cout << _domainChoice.inconsitencyMessage("sorted_associative_map_driver::setProfile()") << std::endl;
+ }
+
+ if(!_codomainChoice.is_consistent())
+ {
+ setValid(false);
+ std::cout << _codomainChoice.inconsitencyMessage("sorted_associative_map_driver::setProfile()") << std::endl;
+ }
+
+ if(!_neutronizerChoice.is_consistent())
+ {
+ setValid(false);
+ std::cout << _neutronizerChoice.inconsitencyMessage("sorted_associative_map_driver::setProfile()") << std::endl;
+ }
+
+ }
+
+
+ algebra_validater* chooseValidater()
+ {
+ int rootChoice = _rootChoice.some();
+ int domainChoice = _domainChoice.some();
+ int codomainChoice = _codomainChoice.some();
+ int neutronizerChoice = _neutronizerChoice.some();
+
+ switch(rootChoice)
+ {
+ //-----------------------------------------------------------------
+ case RootType::interval_map: {
+ switch(neutronizerChoice) {
+ case NeutronHandlerType::partial_absorber: return new sorted_associative_validater<interval_map<int,int,partial_absorber>, itl::list<std::pair<int,int> > >;
+ case NeutronHandlerType::partial_enricher: return new sorted_associative_validater<interval_map<int,int,partial_enricher>, itl::list<std::pair<int,int> > >;
+ case NeutronHandlerType::total_absorber: return new sorted_associative_validater<interval_map<int,int,total_absorber >, itl::list<std::pair<int,int> > >;
+ case NeutronHandlerType::total_enricher: return new sorted_associative_validater<interval_map<int,int,total_enricher >, itl::list<std::pair<int,int> > >;
+ default: return choiceError(ITL_LOCATION("\nRootType::interval_map: neutronizerChoice:\n"), neutronizerChoice, _neutronizerChoice);
+ }//switch neutronizerChoice
+ }//case interval_map
+ //-----------------------------------------------------------------
+ case RootType::split_interval_map: {
+ switch(neutronizerChoice) {
+ case NeutronHandlerType::partial_absorber: return new sorted_associative_validater<split_interval_map<int,int,partial_absorber>, itl::list<std::pair<int,int> > >;
+ case NeutronHandlerType::partial_enricher: return new sorted_associative_validater<split_interval_map<int,int,partial_enricher>, itl::list<std::pair<int,int> > >;
+ case NeutronHandlerType::total_absorber: return new sorted_associative_validater<split_interval_map<int,int,total_absorber >, itl::list<std::pair<int,int> > >;
+ case NeutronHandlerType::total_enricher: return new sorted_associative_validater<split_interval_map<int,int,total_enricher >, itl::list<std::pair<int,int> > >;
+ default: return choiceError(ITL_LOCATION("\nRootType::split_interval_map: neutronizerChoice:\n"), neutronizerChoice, _neutronizerChoice);
+ }//switch neutronizerChoice
+ }//case split_interval_map
+ //-----------------------------------------------------------------
+
+ default: return choiceError(ITL_LOCATION("rootChoice:\n"), rootChoice, _rootChoice);
+ } //switch()
+
+ return NULL; //just to please the compiler ;)
+ }
+ };
+
+
+}} // namespace itl boost
+
+#endif // BOOST_VALIDATE_DRIVER_SORTED_ASSOCIATIVE_MAP_DRIVER_HPP_JOFA_091126
Added: sandbox/itl/boost/validate/driver/sorted_associative_set_driver.hpp
==============================================================================
--- (empty file)
+++ sandbox/itl/boost/validate/driver/sorted_associative_set_driver.hpp 2009-11-30 05:18:48 EST (Mon, 30 Nov 2009)
@@ -0,0 +1,116 @@
+/*-----------------------------------------------------------------------------+
+A Law Based Test Automaton 'LaBatea'
+Author: Joachim Faulhaber
+Copyright (c) 2007-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_VALIDATE_DRIVER_SORTED_ASSOCIATIVE_SET_DRIVER_HPP_JOFA_091126
+#define BOOST_VALIDATE_DRIVER_SORTED_ASSOCIATIVE_SET_DRIVER_HPP_JOFA_091126
+
+#include <iostream>
+#include <stdio.h>
+#include <boost/validate/validater/sorted_associative_validater.hpp>
+#include <boost/validate/driver/itl_driver.hpp>
+#include <boost/validate/utility.hpp>
+
+namespace boost{namespace itl
+{
+
+ class sorted_associative_set_driver : public itl_driver
+ {
+ public:
+ sorted_associative_set_driver() { setProfile(); }
+
+ void setProfile()
+ {
+ setValid(true);
+ _rootChoice.setSize(RootType::Types_size);
+ _rootChoice.setMaxWeights(100);
+ _rootChoice[RootType::itl_set] = 0;
+ _rootChoice[RootType::interval_set] = 33;
+ _rootChoice[RootType::separate_interval_set] = 33;
+ _rootChoice[RootType::split_interval_set] = 34;
+ _rootChoice[RootType::itl_map] = 0;
+ _rootChoice[RootType::interval_map] = 0;
+ _rootChoice[RootType::split_interval_map] = 0;
+ setRootTypeNames();
+ _rootChoice.init();
+
+ _domainChoice.setSize(DomainType::DomainTypes_size);
+ _domainChoice.setMaxWeights(100);
+ _domainChoice[DomainType::Int] = 100;
+ _domainChoice[DomainType::Double] = 0;
+ setDomainTypeNames();
+ _domainChoice.init();
+
+ _codomainChoice.setSize(CodomainType::CodomainTypes_size);
+ _codomainChoice.setMaxWeights(100);
+ _codomainChoice[CodomainType::Nat] = 100;
+ _codomainChoice[CodomainType::Int] = 0;
+ _codomainChoice[CodomainType::Double] = 0;
+ _codomainChoice[CodomainType::set_int] = 0;
+ setCodomainTypeNames();
+ _codomainChoice.init();
+
+ _neutronizerChoice.setSize(NeutronHandlerType::NeutronHandlerTypes_size);
+ _neutronizerChoice.setMaxWeights(100);
+ _neutronizerChoice[NeutronHandlerType::partial_absorber] = 25;
+ _neutronizerChoice[NeutronHandlerType::partial_enricher] = 25;
+ _neutronizerChoice[NeutronHandlerType::total_absorber] = 25;
+ _neutronizerChoice[NeutronHandlerType::total_enricher] = 25;
+ setNeutronHandlerTypeNames();
+ _neutronizerChoice.init();
+
+ if(!_rootChoice.is_consistent())
+ {
+ setValid(false);
+ std::cout << _rootChoice.inconsitencyMessage("sorted_associative_set_driver::setProfile()") << std::endl;
+ }
+
+ if(!_domainChoice.is_consistent())
+ {
+ setValid(false);
+ std::cout << _domainChoice.inconsitencyMessage("sorted_associative_set_driver::setProfile()") << std::endl;
+ }
+
+ if(!_codomainChoice.is_consistent())
+ {
+ setValid(false);
+ std::cout << _codomainChoice.inconsitencyMessage("sorted_associative_set_driver::setProfile()") << std::endl;
+ }
+
+ if(!_neutronizerChoice.is_consistent())
+ {
+ setValid(false);
+ std::cout << _neutronizerChoice.inconsitencyMessage("sorted_associative_set_driver::setProfile()") << std::endl;
+ }
+
+ }
+
+
+ algebra_validater* chooseValidater()
+ {
+ int rootChoice = _rootChoice.some();
+ int domainChoice = _domainChoice.some();
+ int codomainChoice = _codomainChoice.some();
+ int neutronizerChoice = _neutronizerChoice.some();
+
+ switch(rootChoice)
+ {
+ case RootType:: interval_set: return new sorted_associative_validater< interval_set<int>, itl::list<int> >;
+ case RootType::separate_interval_set: return new sorted_associative_validater<separate_interval_set<int>, itl::list<int> >;
+ case RootType:: split_interval_set: return new sorted_associative_validater< split_interval_set<int>, itl::list<int> >;
+ default: return choiceError(ITL_LOCATION("rootChoice:\n"), rootChoice, _rootChoice);
+ } //switch()
+
+ return NULL; //just to please the compiler ;)
+ }
+ };
+
+
+}} // namespace itl boost
+
+#endif // BOOST_VALIDATE_DRIVER_SORTED_ASSOCIATIVE_SET_DRIVER_HPP_JOFA_091126
Modified: sandbox/itl/boost/validate/gentor/randomgentor.hpp
==============================================================================
--- sandbox/itl/boost/validate/gentor/randomgentor.hpp (original)
+++ sandbox/itl/boost/validate/gentor/randomgentor.hpp 2009-11-30 05:18:48 EST (Mon, 30 Nov 2009)
@@ -62,6 +62,11 @@
class RandomGentor< std::pair<DomainT,CodomainT> > :
public std_pair_gentor<DomainT,CodomainT> {};
+
+ template <class DomainT>
+ class RandomGentor<itl::list<DomainT> > :
+ public SeqGentorT<itl::list<DomainT> > {};
+
#ifdef LAW_BASED_TEST_BOOST_POLYGON
// -------------------------------------------------------------------------
template <class DomainT>
@@ -69,10 +74,6 @@
public point_gentor<DomainT> {};
template <class PointT>
- class RandomGentor<itl::list<PointT> > :
- public polygon_gentor<itl::list<PointT> > {};
-
- template <class PointT>
class RandomGentor<itl::list<itl::list<PointT> > > :
public polygon_set_gentor<itl::list<itl::list<PointT> > > {};
#endif //LAW_BASED_TEST_BOOST_POLYGON
@@ -94,10 +95,6 @@
class RandomGentor<itl::list<itl::interval<DomainT> > > :
public SeqGentorT<itl::list<itl::interval<DomainT> > > {};
- template <class DomainT>
- class RandomGentor<itl::list<DomainT> > :
- public SeqGentorT<itl::list<DomainT> > {};
-
// ----- sets --------------------------------------------------------------
//template <class DomainT, template<class>class Set>
//class RandomGentor<Set<DomainT> > :
Added: sandbox/itl/boost/validate/laws/atomic_equivalence.hpp
==============================================================================
--- (empty file)
+++ sandbox/itl/boost/validate/laws/atomic_equivalence.hpp 2009-11-30 05:18:48 EST (Mon, 30 Nov 2009)
@@ -0,0 +1,199 @@
+/*-----------------------------------------------------------------------------+
+A Law Based Test Automaton 'LaBatea'
+Author: Joachim Faulhaber
+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_VALIDATE_LAWS_ATOMIC_EQUIVALENCE_HPP_JOFA_091124
+#define BOOST_VALIDATE_LAWS_ATOMIC_EQUIVALENCE_HPP_JOFA_091124
+
+#include <boost/itl/type_traits/value_size.hpp>
+#include <boost/itl/functors.hpp>
+#include <boost/itl/predicates.hpp>
+#include <boost/itl/interval_morphism.hpp>
+#include <boost/validate/laws/law.hpp>
+#include <boost/validate/std/algorithm/copy.hpp>
+#include <boost/validate/std/algorithm/set_algo.hpp>
+
+namespace boost{namespace itl
+{
+
+// -----------------------------------------------------------------------------
+// S: Segment container
+// f: Atomize function transforming an interval container into an element container
+// E: Element container
+// g: A function (specifically std::algorithm) applicable to S and E
+// T: Target container
+//
+// S
+// / \
+// f / \ g
+// / = \
+// V V
+// E ------> T
+// g
+// -----------------------------------------------------------------------------
+template <typename SegmentsT,
+ typename TargetsT = typename SegmentsT::atomized_type,
+ template<class,class,template<class>class>class Algorithm = itl::std_copy_forward,
+ template<class>class TargetIterator = std::insert_iterator,
+ template<class,class>class Atomizer = itl::Interval::Atomize,
+ template<class>class Equality = itl::std_equal >
+class UnaryAtomicEquivalence :
+ public Law<UnaryAtomicEquivalence<SegmentsT, TargetsT,
+ Algorithm, TargetIterator,
+ Atomizer, Equality>,
+ LOKI_TYPELIST_1(SegmentsT),
+ LOKI_TYPELIST_2(TargetsT,TargetsT) >
+{
+ /** S: SegmentsT, T: TargetsT, I: InputIterator
+ Alg<S,T,I>: an algortihm on interval containers S
+ that results in a container T via iterator I.
+ For all S a: Alg<E,T,I>(atomize(a)) == Alg<S,T,I>(a)
+ Input = (a := inVal1)
+ Output = (lhs_result, rhs_result)
+ */
+public:
+ typedef typename SegmentsT::atomized_type ElementsT;
+
+ std::string name()const { return "UnnaryAtomicEquivalence"; }
+ std::string formula()const { return "For all S a: Alg<E,T,I>(atomize(a)) == Alg<S,T,I>(a)"; }
+
+ std::string typeString()const
+ {
+ return
+ "EleEq<"
+ + type_to_string<SegmentsT>::apply()+","
+ + type_to_string<TargetsT>::apply() +","
+ + Algorithm<ElementsT,TargetsT,TargetIterator>::struct_abbreviation() +">";
+ }
+
+public:
+
+ bool holds()
+ {
+ // For all S a: Alg<E,T,I>(atomize(a)) == Alg<S,T,I>(a)
+ // --- left hand side --------------------------------------------------
+ TargetsT lhs;
+ SegmentsT segmental_a = this->template getInputValue<operand_a>();
+ ElementsT elemental_a;
+ Atomizer<ElementsT,SegmentsT>()(elemental_a, segmental_a);
+ Algorithm<ElementsT,TargetsT,TargetIterator>::apply(elemental_a, lhs);
+
+ // --- right hand side -------------------------------------------------
+ TargetsT rhs;
+ Algorithm<SegmentsT,TargetsT,TargetIterator>::apply_elemental(segmental_a, rhs);
+
+ this->template setOutputValue<lhs_result>(lhs);
+ this->template setOutputValue<rhs_result>(rhs);
+
+ return Equality<TargetsT>()(lhs, rhs);
+ }
+
+ bool debug_holds()
+ {
+ return holds();
+ }
+
+ size_t size()const
+ {
+ return value_size<SegmentsT>::apply(this->template getInputValue<operand_a>());
+ }
+};
+
+
+
+// -----------------------------------------------------------------------------
+// S: Segment container
+// f: Atomize function transforming an interval container into an element container
+// E: Element container
+// .o.: U x U -> T A binary function (specifically std::algorithm) applicable to S or E
+// T: Target container
+//
+// S
+// / \
+// f / \ o
+// / = \
+// V V
+// E ------> T
+// o
+// -----------------------------------------------------------------------------
+template <typename SegmentsT,
+ typename TargetsT = typename SegmentsT::atomized_type,
+ template<class,class,template<class>class>class Algorithm = itl::std_set_union_forward,
+ template<class>class TargetIterator = std::insert_iterator,
+ template<class,class>class Atomizer = itl::Interval::Atomize,
+ template<class>class Equality = itl::std_equal >
+class BinaryAtomicEquivalence :
+ public Law<BinaryAtomicEquivalence<SegmentsT, TargetsT,
+ Algorithm, TargetIterator,
+ Atomizer, Equality>,
+ LOKI_TYPELIST_2(SegmentsT,SegmentsT),
+ LOKI_TYPELIST_2(TargetsT,TargetsT) >
+{
+ /** S: SegmentsT, T: TargetsT, I: InputIterator
+ Alg<S,T,I>: an algortihm on interval containers S
+ that results in a container T via iterator I.
+ For all S a,b: Alg<S,T,I>(atomize(a), atomize(b)) == Alg<S,T,I>(a,b)
+ Input = (a := inVal1)
+ Output = (lhs_result, rhs_result)
+ */
+public:
+ typedef typename SegmentsT::atomized_type ElementsT;
+
+ std::string name()const { return "BinaryAtomicEquivalence"; }
+ std::string formula()const
+ { return "For all S a: Alg<E,T,I>(f(a),f(b)) == Alg<S,T,I>(a,b)"; }
+
+ std::string typeString()const
+ {
+ return
+ "EleEq<"
+ + type_to_string<SegmentsT>::apply()+","
+ + type_to_string<TargetsT>::apply() +","
+ + Algorithm<ElementsT,TargetsT,TargetIterator>::struct_abbreviation() +">";
+ }
+
+public:
+
+ bool holds()
+ {
+ // For all S a: Alg<E,T,I>(atomize(a)) == Alg<S,T,I>(a)
+ // --- left hand side --------------------------------------------------
+ TargetsT lhs;
+ SegmentsT segmental_a = this->template getInputValue<operand_a>();
+ SegmentsT segmental_b = this->template getInputValue<operand_b>();
+ ElementsT elemental_a, elemental_b;
+ Atomizer<ElementsT,SegmentsT>()(elemental_a, segmental_a);
+ Atomizer<ElementsT,SegmentsT>()(elemental_b, segmental_b);
+ Algorithm<ElementsT,TargetsT,TargetIterator>::apply(elemental_a, elemental_b, lhs);
+
+ // --- right hand side -------------------------------------------------
+ TargetsT rhs;
+ Algorithm<SegmentsT,TargetsT,TargetIterator>::apply_elemental(segmental_a, segmental_b, rhs);
+
+ this->template setOutputValue<lhs_result>(lhs);
+ this->template setOutputValue<rhs_result>(rhs);
+
+ return Equality<TargetsT>()(lhs, rhs);
+ }
+
+ bool debug_holds()
+ {
+ return holds();
+ }
+
+ size_t size()const
+ {
+ return value_size<SegmentsT>::apply(this->template getInputValue<operand_a>())
+ + value_size<SegmentsT>::apply(this->template getInputValue<operand_b>());
+ }
+};
+
+}} // namespace itl boost
+
+#endif BOOST_VALIDATE_LAWS_ATOMIC_EQUIVALENCE_HPP_JOFA_091124
+
Modified: sandbox/itl/boost/validate/laws/function_equality.hpp
==============================================================================
--- sandbox/itl/boost/validate/laws/function_equality.hpp (original)
+++ sandbox/itl/boost/validate/laws/function_equality.hpp 2009-11-30 05:18:48 EST (Mon, 30 Nov 2009)
@@ -102,5 +102,5 @@
}} // namespace itl boost
-#endif // BOOST_ITL_MINOR_SET_LAWS_HPP_JOFA_070411
+#endif // BOOST_ITL_FUNCTION_EQUALITY_HPP_JOFA_091005
Modified: sandbox/itl/boost/validate/validater/law_validater.hpp
==============================================================================
--- sandbox/itl/boost/validate/validater/law_validater.hpp (original)
+++ sandbox/itl/boost/validate/validater/law_validater.hpp 2009-11-30 05:18:48 EST (Mon, 30 Nov 2009)
@@ -146,8 +146,15 @@
bool law_is_violated = false;
start = posix_time::ptime(posix_time::microsec_clock::local_time());
// In order to measure small time intervals, evaluation must be repeated.
- for(int repeat=0; repeat<_repeat_count; repeat++)
- law_is_violated = !_law.holds();
+
+ //std::cout << idx << " "; //CL..
+ //if(idx==0)
+ //{
+ // int dbg_ = 1;
+ //}
+
+ for(int repeat=0; repeat<_repeat_count; repeat++)
+ law_is_violated = !_law.holds();
stop = posix_time::ptime(posix_time::microsec_clock::local_time());
validation_time += static_cast<double>((stop - start).total_microseconds());
Added: sandbox/itl/boost/validate/validater/sorted_associative_validater.hpp
==============================================================================
--- (empty file)
+++ sandbox/itl/boost/validate/validater/sorted_associative_validater.hpp 2009-11-30 05:18:48 EST (Mon, 30 Nov 2009)
@@ -0,0 +1,128 @@
+/*-----------------------------------------------------------------------------+
+A Law Based Test Automaton 'LaBatea'
+Author: Joachim Faulhaber
+Copyright (c) 2007-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_VALIDATE_VALIDATER_SORTED_ASSOCIATIVE_VALIDATER_HPP_JOFA_091125
+#define BOOST_VALIDATE_VALIDATER_SORTED_ASSOCIATIVE_VALIDATER_HPP_JOFA_091125
+
+#include <boost/validate/laws/atomic_equivalence.hpp>
+#include <boost/validate/validater/law_validater.hpp>
+#include <boost/validate/validater/algebra_validater.hpp>
+
+namespace boost{namespace itl
+{
+
+typedef WeightedNumberGentor<int> ChoiceT;
+
+template <typename Type, typename TargetT = itl::list<typename Type::value_type> >
+class sorted_associative_validater : public algebra_validater
+{
+public:
+
+ enum Laws
+ {
+ copy_fore ,
+ copy_back ,
+ reverse_copy_fore ,
+ reverse_copy_back ,
+ includes_fore ,
+ includes_back ,
+ set_union_fore ,
+ set_union_back ,
+ set_difference_fore,
+ set_difference_back,
+ set_intersection_fore,
+ set_intersection_back,
+ set_symmetric_difference_fore,
+ set_symmetric_difference_back,
+ Laws_size
+ };
+
+ sorted_associative_validater() {setProfile();}
+
+ void setProfile()
+ {
+ const int sum_of_shares = 100;
+
+ _lawChoice.setSize(Laws_size);
+ _lawChoice.setMaxWeights(sum_of_shares);
+
+ int rest_shares = sum_of_shares, item_index = 0;
+ _lawChoice[copy_fore ] = share(Laws_size, item_index, rest_shares);
+ _lawChoice[copy_back ] = share(Laws_size, item_index, rest_shares);
+ _lawChoice[reverse_copy_fore ] = share(Laws_size, item_index, rest_shares);
+ _lawChoice[reverse_copy_back ] = share(Laws_size, item_index, rest_shares);
+ _lawChoice[includes_fore ] = share(Laws_size, item_index, rest_shares);
+ _lawChoice[includes_back ] = share(Laws_size, item_index, rest_shares);
+ _lawChoice[set_union_fore ] = share(Laws_size, item_index, rest_shares);
+ _lawChoice[set_union_back ] = share(Laws_size, item_index, rest_shares);
+ _lawChoice[set_difference_fore ] = share(Laws_size, item_index, rest_shares);
+ _lawChoice[set_difference_back ] = share(Laws_size, item_index, rest_shares);
+ _lawChoice[set_intersection_fore ] = share(Laws_size, item_index, rest_shares);
+ _lawChoice[set_intersection_back ] = share(Laws_size, item_index, rest_shares);
+ _lawChoice[set_symmetric_difference_fore] = share(Laws_size, item_index, rest_shares);
+ _lawChoice[set_symmetric_difference_back] = share(Laws_size, item_index, rest_shares);
+
+ _lawChoice.init();
+ }
+
+
+ LawValidaterI* chooseValidater()
+ {
+ switch(_lawChoice.some())
+ {
+ case copy_fore : return new LawValidater< UnaryAtomicEquivalence<Type, TargetT, std_copy_forward >, RandomGentor>;
+ case copy_back : return new LawValidater< UnaryAtomicEquivalence<Type, TargetT, std_copy_backward >, RandomGentor>;
+ case reverse_copy_fore : return new LawValidater< UnaryAtomicEquivalence<Type, TargetT, std_reverse_copy_forward >, RandomGentor>;
+ case reverse_copy_back : return new LawValidater< UnaryAtomicEquivalence<Type, TargetT, std_reverse_copy_backward >, RandomGentor>;
+ case includes_fore : return new LawValidater<BinaryAtomicEquivalence<Type, TargetT, std_includes_forward >, RandomGentor>;
+ case includes_back : return new LawValidater<BinaryAtomicEquivalence<Type, TargetT, std_includes_backward >, RandomGentor>;
+ case set_union_fore : return new LawValidater<BinaryAtomicEquivalence<Type, TargetT, std_set_union_forward >, RandomGentor>;
+ case set_union_back : return new LawValidater<BinaryAtomicEquivalence<Type, TargetT, std_set_union_backward >, RandomGentor>;
+ case set_difference_fore: return new LawValidater<BinaryAtomicEquivalence<Type, TargetT, std_set_difference_forward >, RandomGentor>;
+ case set_difference_back: return new LawValidater<BinaryAtomicEquivalence<Type, TargetT, std_set_difference_backward>, RandomGentor>;
+ case set_intersection_fore: return new LawValidater<BinaryAtomicEquivalence<Type, TargetT, std_set_intersection_forward >, RandomGentor>;
+ case set_intersection_back: return new LawValidater<BinaryAtomicEquivalence<Type, TargetT, std_set_intersection_backward>, RandomGentor>;
+ case set_symmetric_difference_fore: return new LawValidater<BinaryAtomicEquivalence<Type, TargetT, std_set_symmetric_difference_forward >, RandomGentor>;
+ case set_symmetric_difference_back: return new LawValidater<BinaryAtomicEquivalence<Type, TargetT, std_set_symmetric_difference_backward>, RandomGentor>;
+ default: return NULL;
+ }
+ }
+
+ void validate()
+ {
+ _validater = chooseValidater();
+ if(_validater)
+ {
+ _validater->run();
+ _validater->addFrequencies(_frequencies);
+ _validater->addViolations(_violationsCount, _violations);
+ delete _validater;
+ }
+ }
+
+ void addFrequencies(ValidationCounterT& summary) { summary += _frequencies; }
+ void addViolations(ViolationCounterT& summary, ViolationMapT& collector)
+ {
+ summary += _violationsCount;
+ collector += _violations;
+ }
+
+
+private:
+ ChoiceT _lawChoice;
+ LawValidaterI* _validater;
+ ValidationCounterT _frequencies;
+ ViolationCounterT _violationsCount;
+ ViolationMapT _violations;
+};
+
+
+}} // namespace itl boost
+
+#endif // BOOST_VALIDATE_VALIDATER_SORTED_ASSOCIATIVE_VALIDATER_HPP_JOFA_091125