Subject: [Boost-commit] svn:boost r76725 - in sandbox/gtl: boost/polygon/detail libs/polygon/test
From: sydorchuk.andriy_at_[hidden]
Date: 2012-01-27 16:53:17
Author: asydorchuk
Date: 2012-01-27 16:53:17 EST (Fri, 27 Jan 2012)
New Revision: 76725
URL: http://svn.boost.org/trac/boost/changeset/76725
Log:
Updating voronoi_ctypes tests.
Text files modified:
sandbox/gtl/boost/polygon/detail/voronoi_ctypes.hpp | 93 ++++++++++++++++-----------------------
sandbox/gtl/libs/polygon/test/voronoi_ctypes_test.cpp | 86 ++++++++++++++++++++++++++----------
2 files changed, 100 insertions(+), 79 deletions(-)
Modified: sandbox/gtl/boost/polygon/detail/voronoi_ctypes.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/detail/voronoi_ctypes.hpp (original)
+++ sandbox/gtl/boost/polygon/detail/voronoi_ctypes.hpp 2012-01-27 16:53:17 EST (Fri, 27 Jan 2012)
@@ -26,7 +26,7 @@
// If two floating-point numbers in the same format are ordered (x < y),
// then they are ordered the same way when their bits are reinterpreted as
// sign-magnitude integers. Values are considered to be almost equal if
-// their integer bit reinterpretations differ in not more than maxUlps units.
+// their integer bits reinterpretations differ in not more than maxUlps units.
template <typename _fpt>
struct ulp_comparison;
@@ -95,8 +95,8 @@
const int64 fpt_exponent_accessor<fpt64>::kMaxExponent = 1024LL;
const int64 fpt_exponent_accessor<fpt64>::kMaxSignificantExpDif = 54;
-// Allows to extend floating-point type exponent boundaries to the 64 bit
-// integer range. This class does not handle division by zero, subnormal
+// Floating point type wrapper. Allows to extend exponent boundaries to the
+// 64 bit integer range. This class does not handle division by zero, subnormal
// numbers or NaNs.
template <typename _fpt>
class extended_exponent_fpt {
@@ -270,6 +270,8 @@
return that.is_zero();
}
+// Very efficient stack allocated big integer class.
+// Supports next set of arithmetic operations: +, -, *.
template<size_t N>
class extended_int {
public:
@@ -286,38 +288,28 @@
this->chunks_[0] = -that;
this->count_ = -1;
} else {
- this->chunks_[0] = this->count_ = 0;
+ this->count_ = 0;
}
}
extended_int(int64 that) {
if (that > 0) {
this->chunks_[0] = static_cast<uint32>(that & kUInt64LowMask);
- uint32 high = (that & kUInt64HighMask) >> 32;
- if (high) {
- this->chunks_[1] = high;
- this->count_ = 2;
- } else {
- this->count_ = 1;
- }
+ this->chunks_[1] = that >> 32;
+ this->count_ = this->chunks_[1] ? 2 : 1;
} else if (that < 0) {
that = -that;
this->chunks_[0] = static_cast<uint32>(that & kUInt64LowMask);
- uint32 high = (that & kUInt64HighMask) >> 32;
- if (high) {
- this->chunks_[1] = high;
- this->count_ = -2;
- } else {
- this->count_ = -1;
- }
+ this->chunks_[1] = that >> 32;
+ this->count_ = this->chunks_[1] ? -2 : -1;
} else {
- this->chunks_[0] = this->count_ = 0;
+ this->count_ = 0;
}
}
extended_int(const std::vector<uint32>& chunks, bool plus = true) {
- this->count_ = static_cast<int32>(chunks.size());
- for (size_t i = 0; i < chunks.size(); ++i) {
+ this->count_ = static_cast<int32>((std::min)(N, chunks.size()));
+ for (int i = 0; i < this->count_; ++i) {
this->chunks_[i] = chunks[chunks.size() - i - 1];
}
if (!plus) {
@@ -327,11 +319,12 @@
template <size_t M>
extended_int(const extended_int<M>& that) {
+ if (that.size() > N) return;
this->count_ = that.count();
memcpy(this->chunks_, that.chunks(), that.size() * sizeof(uint32));
}
- extended_int<N>& operator=(int32 that) {
+ extended_int& operator=(int32 that) {
if (that > 0) {
this->chunks_[0] = that;
this->count_ = 1;
@@ -339,42 +332,32 @@
this->chunks_[0] = -that;
this->count_ = -1;
} else {
- this->chunks_[0] = this->count_ = 0;
+ this->count_ = 0;
}
return *this;
}
- extended_int<N>& operator=(int64 that) {
+ extended_int& operator=(int64 that) {
if (that > 0) {
this->chunks_[0] = static_cast<uint32>(that & kUInt64LowMask);
- uint32 high = (that & kUInt64HighMask) >> 32;
- if (high) {
- this->chunks_[1] = high;
- this->count_ = 2;
- } else {
- this->count_ = 1;
- }
+ this->chunks_[1] = that >> 32;
+ this->count_ = this->chunks_[1] ? 2 : 1;
} else if (that < 0) {
that = -that;
this->chunks_[0] = static_cast<uint32>(that & kUInt64LowMask);
- uint32 high = (that & kUInt64HighMask) >> 32;
- if (high) {
- this->chunks_[1] = high;
- this->count_ = -2;
- } else {
- this->count_ = -1;
- }
+ this->chunks_[1] = that >> 32;
+ this->count_ = this->chunks_[1] ? -2 : -1;
} else {
- this->chunks_[0] = this->count_ = 0;
+ this->count_ = 0;
}
return *this;
}
template <size_t M>
- extended_int<N>& operator=(const extended_int<M>& that) {
+ extended_int& operator=(const extended_int<M>& that) {
+ if (that.size() > N) return;
this->count_ = that.count();
- size_t sz = (std::min)(N, that.size());
- memcpy(this->chunks_, that.chunks(), sz * sizeof(uint32));
+ memcpy(this->chunks_, that.chunks(), that.size() * sizeof(uint32));
return *this;
}
@@ -441,8 +424,8 @@
return !(*this < that);
}
- extended_int<N> operator-() const {
- extended_int<N> ret_val = *this;
+ extended_int operator-() const {
+ extended_int ret_val = *this;
ret_val.neg();
return ret_val;
}
@@ -526,7 +509,7 @@
template <size_t N1, size_t N2>
void mul(const extended_int<N1>& e1, const extended_int<N2>& e2) {
if (!e1.count() || !e2.count()) {
- this->chunks_[0] = this->count_ = 0;
+ this->count_ = 0;
return;
}
mul(e1.chunks(), e1.size(), e2.chunks(), e2.size());
@@ -555,12 +538,10 @@
} else {
if (sz == 1) {
ret_val.first = static_cast<fpt64>(this->chunks_[0]);
- ret_val.second = 0;
} else if (sz == 2) {
ret_val.first = static_cast<fpt64>(this->chunks_[1]) *
static_cast<fpt64>(0x100000000LL) +
static_cast<fpt64>(this->chunks_[0]);
- ret_val.second = 0;
} else {
for (size_t i = 1; i <= 3; ++i) {
ret_val.first *= static_cast<fpt64>(0x100000000LL);
@@ -593,12 +574,12 @@
temp += static_cast<uint64>(c1[i]) +
static_cast<uint64>(c2[i]);
this->chunks_[i] = static_cast<uint32>(temp & kUInt64LowMask);
- temp = (temp & kUInt64HighMask) >> 32;
+ temp >>= 32;
}
for (size_t i = sz2; i < sz1; ++i) {
temp += static_cast<uint64>(c1[i]);
this->chunks_[i] = static_cast<uint32>(temp & kUInt64LowMask);
- temp = (temp & kUInt64HighMask) >> 32;
+ temp >>= 32;
}
if (temp && (this->count_ != N)) {
this->chunks_[this->count_] = static_cast<uint32>(temp & kUInt64LowMask);
@@ -622,11 +603,12 @@
} else if (c1[sz1] > c2[sz1]) {
++sz1;
break;
- } else if (!sz1) {
- this->chunks_[0] = this->count_ = 0;
- return;
}
} while (sz1);
+ if (!sz1) {
+ this->count_ = 0;
+ return;
+ }
sz2 = sz1;
}
this->count_ = sz1-1;
@@ -660,10 +642,10 @@
tmp = static_cast<uint64>(c1[first]) *
static_cast<uint64>(c2[second]);
cur += tmp & kUInt64LowMask;
- nxt += (tmp & kUInt64HighMask) >> 32;
+ nxt += tmp >> 32;
}
this->chunks_[shift] = static_cast<uint32>(cur & kUInt64LowMask);
- cur = nxt + ((cur & kUInt64HighMask) >> 32);
+ cur = nxt + (cur >> 32);
}
if (cur && (this->count_ != N)) {
this->chunks_[this->count_] = static_cast<uint32>(cur & kUInt64LowMask);
@@ -720,6 +702,9 @@
}
};
+// Voronoi coordinate type traits make it possible to extend algorithm
+// input coordinate range to any user provided integer and algorithm
+// output coordinate range to any ieee-754 like floating point type.
template <typename T>
struct voronoi_ctype_traits;
Modified: sandbox/gtl/libs/polygon/test/voronoi_ctypes_test.cpp
==============================================================================
--- sandbox/gtl/libs/polygon/test/voronoi_ctypes_test.cpp (original)
+++ sandbox/gtl/libs/polygon/test/voronoi_ctypes_test.cpp 2012-01-27 16:53:17 EST (Fri, 27 Jan 2012)
@@ -19,6 +19,31 @@
type_converter_fpt to_fpt;
+BOOST_AUTO_TEST_CASE(ulp_comparison_test1) {
+ ulp_comparison<double> ulp_cmp;
+ uint64 a = 22;
+ uint64 b = 27;
+ fpt64 da = *reinterpret_cast<fpt64*>(&a);
+ fpt64 db = *reinterpret_cast<fpt64*>(&b);
+ BOOST_CHECK_EQUAL(ulp_cmp(da, db, 1), ulp_cmp.LESS);
+ BOOST_CHECK_EQUAL(ulp_cmp(db, da, 1), ulp_cmp.MORE);
+ BOOST_CHECK_EQUAL(ulp_cmp(da, db, 4), ulp_cmp.LESS);
+ BOOST_CHECK_EQUAL(ulp_cmp(da, db, 5), ulp_cmp.EQUAL);
+ BOOST_CHECK_EQUAL(ulp_cmp(da, db, 6), ulp_cmp.EQUAL);
+}
+
+BOOST_AUTO_TEST_CASE(ulp_comparison_test2) {
+ ulp_comparison<fpt64> ulp_cmp;
+ uint64 a = 0ULL;
+ uint64 b = 0x8000000000000002ULL;
+ fpt64 da = *reinterpret_cast<fpt64*>(&a);
+ fpt64 db = *reinterpret_cast<fpt64*>(&b);
+ BOOST_CHECK_EQUAL(ulp_cmp(da, db, 1), ulp_cmp.MORE);
+ BOOST_CHECK_EQUAL(ulp_cmp(db, da, 1), ulp_cmp.LESS);
+ BOOST_CHECK_EQUAL(ulp_cmp(da, db, 2), ulp_cmp.EQUAL);
+ BOOST_CHECK_EQUAL(ulp_cmp(da, db, 3), ulp_cmp.EQUAL);
+}
+
BOOST_AUTO_TEST_CASE(fpt_exponent_accessor_test) {
typedef fpt_exponent_accessor<fpt64> fpt_ea;
fpt64 value = 15;
@@ -43,7 +68,7 @@
fpt64 b = 0.0;
efpt64 eeb(b);
for (int i = 0; i < 1000; ++i) {
- fpt64 a = static_cast<fpt64>(static_cast<int64>(gen()));
+ fpt64 a = to_fpt(static_cast<int64>(gen()));
efpt64 eea(a);
efpt64 neg = -eea;
efpt64 sum = eea + eeb;
@@ -61,7 +86,7 @@
fpt64 a = 0.0;
efpt64 eea(a);
for (int i = 0; i < 1000; ++i) {
- fpt64 b = static_cast<fpt64>(static_cast<int64>(gen()));
+ fpt64 b = to_fpt(static_cast<int64>(gen()));
if (b == 0.0) {
continue;
}
@@ -82,8 +107,8 @@
BOOST_AUTO_TEST_CASE(extended_exponent_fpt_test3) {
boost::mt19937_64 gen(static_cast<uint32>(time(NULL)));
for (int i = 0; i < 1000; ++i) {
- fpt64 a = static_cast<fpt64>(static_cast<int64>(gen()));
- fpt64 b = static_cast<fpt64>(static_cast<int64>(gen()));
+ fpt64 a = to_fpt(static_cast<int64>(gen()));
+ fpt64 b = to_fpt(static_cast<int64>(gen()));
if (b == 0.0) {
continue;
}
@@ -106,7 +131,7 @@
for (int exp = 0; exp < 64; ++exp)
for (int i = 1; i < 100; ++i) {
fpt64 a = i;
- fpt64 b = static_cast<fpt64>(1LL << exp);
+ fpt64 b = to_fpt(1LL << exp);
efpt64 eea(a);
efpt64 eeb(b);
efpt64 neg = -eea;
@@ -124,9 +149,18 @@
BOOST_AUTO_TEST_CASE(extended_exponent_fpt_test5) {
for (int i = 0; i < 100; ++i) {
- efpt64 a(static_cast<fpt64>(i * i));
+ efpt64 a(to_fpt(i * i));
efpt64 b = a.sqrt();
- BOOST_CHECK_EQUAL(to_fpt(b), static_cast<fpt64>(i));
+ BOOST_CHECK_EQUAL(to_fpt(b), to_fpt(i));
+ }
+}
+
+BOOST_AUTO_TEST_CASE(extended_exponent_fpt_test6) {
+ for (int i = -10; i <= 10; ++i) {
+ efpt64 a(to_fpt(i));
+ BOOST_CHECK_EQUAL(is_pos(a), i > 0);
+ BOOST_CHECK_EQUAL(is_neg(a), i < 0);
+ BOOST_CHECK_EQUAL(is_zero(a), !i);
}
}
@@ -134,14 +168,13 @@
typedef extended_int<1> eint32;
eint32 e1(0), e2(32), e3(-32);
BOOST_CHECK_EQUAL(e1.count(), 0);
- BOOST_CHECK_EQUAL(e1.chunks()[0], 0u);
- BOOST_CHECK_EQUAL(e1.size(), 0u);
+ BOOST_CHECK_EQUAL(e1.size(), 0U);
BOOST_CHECK_EQUAL(e2.count(), 1);
- BOOST_CHECK_EQUAL(e2.chunks()[0], 32u);
- BOOST_CHECK_EQUAL(e2.size(), 1u);
+ BOOST_CHECK_EQUAL(e2.chunks()[0], 32U);
+ BOOST_CHECK_EQUAL(e2.size(), 1U);
BOOST_CHECK_EQUAL(e3.count(), -1);
- BOOST_CHECK_EQUAL(e3.chunks()[0], 32u);
- BOOST_CHECK_EQUAL(e3.size(), 1u);
+ BOOST_CHECK_EQUAL(e3.chunks()[0], 32U);
+ BOOST_CHECK_EQUAL(e3.size(), 1U);
}
BOOST_AUTO_TEST_CASE(extended_int_test2) {
@@ -149,11 +182,10 @@
int64 val64 = 0x7fffffffffffffffLL;
eint64 e1(0LL), e2(32LL), e3(-32LL), e4(val64), e5(-val64);
BOOST_CHECK_EQUAL(e1.count(), 0);
- BOOST_CHECK_EQUAL(e1.chunks()[0], 0u);
BOOST_CHECK_EQUAL(e2.count(), 1);
- BOOST_CHECK_EQUAL(e2.chunks()[0], 32u);
+ BOOST_CHECK_EQUAL(e2.chunks()[0], 32U);
BOOST_CHECK_EQUAL(e3.count(), -1);
- BOOST_CHECK_EQUAL(e3.chunks()[0], 32u);
+ BOOST_CHECK_EQUAL(e3.chunks()[0], 32U);
BOOST_CHECK_EQUAL(e4.count(), 2);
BOOST_CHECK_EQUAL(e4.chunks()[0], 0xffffffff);
BOOST_CHECK_EQUAL(e4.chunks()[1], val64 >> 32);
@@ -169,11 +201,11 @@
chunks.push_back(2);
eint64 e1(chunks, true), e2(chunks, false);
BOOST_CHECK_EQUAL(e1.count(), 2);
- BOOST_CHECK_EQUAL(e1.chunks()[0], 2u);
- BOOST_CHECK_EQUAL(e1.chunks()[1], 1u);
+ BOOST_CHECK_EQUAL(e1.chunks()[0], 2U);
+ BOOST_CHECK_EQUAL(e1.chunks()[1], 1U);
BOOST_CHECK_EQUAL(e2.count(), -2);
- BOOST_CHECK_EQUAL(e2.chunks()[0], 2u);
- BOOST_CHECK_EQUAL(e2.chunks()[1], 1u);
+ BOOST_CHECK_EQUAL(e2.chunks()[0], 2U);
+ BOOST_CHECK_EQUAL(e2.chunks()[1], 1U);
}
BOOST_AUTO_TEST_CASE(extended_int_test4) {
@@ -199,7 +231,7 @@
BOOST_AUTO_TEST_CASE(extended_int_test5) {
typedef extended_int<2> eint64;
boost::mt19937_64 gen(static_cast<uint32>(time(NULL)));
- for (int i = 0; i < 100; ++i) {
+ for (int i = 0; i < 1000; ++i) {
int64 i1 = static_cast<int64>(gen());
int64 i2 = static_cast<int64>(gen());
eint64 e1(i1), e2(i2);
@@ -217,14 +249,14 @@
eint32 e1(32);
eint32 e2 = -e1;
BOOST_CHECK_EQUAL(e2.count(), -1);
- BOOST_CHECK_EQUAL(e2.size(), 1u);
- BOOST_CHECK_EQUAL(e2.chunks()[0], 32u);
+ BOOST_CHECK_EQUAL(e2.size(), 1U);
+ BOOST_CHECK_EQUAL(e2.chunks()[0], 32U);
}
BOOST_AUTO_TEST_CASE(extended_int_test7) {
typedef extended_int<2> eint64;
boost::mt19937_64 gen(static_cast<uint32>(time(NULL)));
- for (int i = 0; i < 100; ++i) {
+ for (int i = 0; i < 1000; ++i) {
int64 i1 = static_cast<int64>(gen()) >> 2;
int64 i2 = static_cast<int64>(gen()) >> 2;
eint64 e1(i1), e2(i2), e3(i1 + i2), e4(i1 - i2);
@@ -236,7 +268,7 @@
BOOST_AUTO_TEST_CASE(extended_int_test8) {
typedef extended_int<2> eint64;
boost::mt19937 gen(static_cast<uint32>(time(NULL)));
- for (int i = 0; i < 100; ++i) {
+ for (int i = 0; i < 1000; ++i) {
int64 i1 = static_cast<int32>(gen());
int64 i2 = static_cast<int32>(gen());
eint64 e1(i1), e2(i2), e3(i1 * i2);
@@ -277,4 +309,8 @@
value = value * two;
}
BOOST_CHECK_EQUAL(value.count(), 33);
+ for (size_t i = 1; i < value.size(); ++i) {
+ BOOST_CHECK_EQUAL(value.chunks()[i-1], 0U);
+ }
+ BOOST_CHECK_EQUAL(value.chunks()[32], 1U);
}