[test] testing for strict weak ordering
Hi, I couldn't find a way to do this. Maybe I have overlooked something. Anyway, making sure that operator<, operator== does the right thing is pretty important. I had in mind that I could say for( each i ) for( each i2 ) BOOST_CHECK_STRICT_WEAK_ORDERING( *i, *i2 ); which would check something like the following: if( !(*i < *i2) && !(*i2 < *i) ) { BOOST_CHECK( *i == *i2 ); } else if( *i < *i2 ) { BOOST_CHECK( *i != *i2 ); BOOST_CHECK( !(*i2 < *i) ); } else { BOOST_CHECK( *i2 < *i ); BOOST_CHECK( !(*i2 < *i) ); } -Thorsten
Thorsten Ottosen <thorsten.ottosen@dezide.com> writes:
Hi,
I couldn't find a way to do this. Maybe I have overlooked something. Anyway, making sure that operator<, operator== does the right thing is pretty important.
Strict weak ordering uses a single operations and does not relate two operations. Thus you can test that < imposes a strict weak ordering, but it can have nothing to do with ==. What you're testing below would need some other name.
I had in mind that I could say
for( each i ) for( each i2 ) BOOST_CHECK_STRICT_WEAK_ORDERING( *i, *i2 );
which would check something like the following:
if( !(*i < *i2) && !(*i2 < *i) ) { BOOST_CHECK( *i == *i2 ); } else if( *i < *i2 ) { BOOST_CHECK( *i != *i2 ); BOOST_CHECK( !(*i2 < *i) ); } else { BOOST_CHECK( *i2 < *i ); BOOST_CHECK( !(*i2 < *i) ); }
-- Dave Abrahams Boost Consulting www.boost-consulting.com
David Abrahams wrote:
Thorsten Ottosen <thorsten.ottosen@dezide.com> writes:
Hi,
I couldn't find a way to do this. Maybe I have overlooked something. Anyway, making sure that operator<, operator== does the right thing is pretty important.
Strict weak ordering uses a single operations and does not relate two operations. Thus you can test that < imposes a strict weak ordering, but it can have nothing to do with ==. What you're testing below would need some other name.
Right. I guess both could be useful. -Thorsten
On Feb 2, 2007, at 10:36 AM, Thorsten Ottosen wrote:
David Abrahams wrote:
Thorsten Ottosen <thorsten.ottosen@dezide.com> writes:
Hi,
I couldn't find a way to do this. Maybe I have overlooked something. Anyway, making sure that operator<, operator== does the right thing is pretty important.
Strict weak ordering uses a single operations and does not relate two operations. Thus you can test that < imposes a strict weak ordering, but it can have nothing to do with ==. What you're testing below would need some other name.
Right. I guess both could be useful.
One approach is to use a debugging compare predicate which adapts another predicate and adds a test. Something like: template <class Compare> struct debug_comp { Compare comp_; debug_comp() {} explicit debug_comp(const Compare& c) : comp_(c) {} template <class Tp, class Up> bool operator()(const Tp& x, const Up& y) { bool r = comp_(x, y); if (r) assert(!comp_(y, x)); return r; } }; Demo: std::sort(v.begin(), v.end(), debug_comp<std::less<A> >()); It isn't an exhaustive test, but does tend to catch such bugs in the wild. A disadvantage of this approach is that it may upset some algorithms which only require comp(x,y) but not comp(y,x) to be valid.
"Howard Hinnant" <howard.hinnant@gmail.com> wrote in message news:D9D92951-17A4-4A29-9A0D-AD0B9E13FA64@twcny.rr.com...
On Feb 2, 2007, at 10:36 AM, Thorsten Ottosen wrote:
David Abrahams wrote:
Thorsten Ottosen <thorsten.ottosen@dezide.com> writes:
Hi,
I couldn't find a way to do this. Maybe I have overlooked something. Anyway, making sure that operator<, operator== does the right thing is pretty important.
Strict weak ordering uses a single operations and does not relate two operations. Thus you can test that < imposes a strict weak ordering, but it can have nothing to do with ==. What you're testing below would need some other name.
Right. I guess both could be useful.
One approach is to use a debugging compare predicate which adapts another predicate and adds a test. Something like:
template <class Compare> struct debug_comp { Compare comp_; debug_comp() {} explicit debug_comp(const Compare& c) : comp_(c) {}
template <class Tp, class Up> bool operator()(const Tp& x, const Up& y) { bool r = comp_(x, y); if (r) assert(!comp_(y, x)); return r; } };
Demo:
std::sort(v.begin(), v.end(), debug_comp<std::less<A> >());
SWO implies not only anti-symmetry. Did you take a look on test_strict_weak_ordering in my post? Gennadiy
Howard Hinnant <howard.hinnant@gmail.com> writes:
It isn't an exhaustive test, but does tend to catch such bugs in the wild. A disadvantage of this approach is that it may upset some algorithms which only require comp(x,y) but not comp(y,x) to be valid.
Seems to me that either means you should have known not to use this test on that algorithm, or it reveals a bug in the algorithm's documentation. What am I missing? -- Dave Abrahams Boost Consulting www.boost-consulting.com
"Thorsten Ottosen" <thorsten.ottosen@dezide.com> wrote in message news:45C3529C.6040804@dezide.com...
Hi,
I couldn't find a way to do this. Maybe I have overlooked something. Anyway, making sure that operator<, operator== does the right thing is pretty important.
I had in mind that I could say
for( each i ) for( each i2 ) BOOST_CHECK_STRICT_WEAK_ORDERING( *i, *i2 );
which would check something like the following:
if( !(*i < *i2) && !(*i2 < *i) ) { BOOST_CHECK( *i == *i2 ); } else if( *i < *i2 ) { BOOST_CHECK( *i != *i2 ); BOOST_CHECK( !(*i2 < *i) ); } else { BOOST_CHECK( *i2 < *i ); BOOST_CHECK( !(*i2 < *i) ); }
While ago there was an idea to have test_strict_weak_ordering. I had a prototype implemented. It never got into "production". Let me know how does it match with what you need (see attachment) Gennadiy begin 666 runtime_concept_check.hpp M(VEF;F1E9B!254Y424U%7T-/3D-%4%1?0TA%0TM?2%!0"B-D969I;F4@4E5. M5$E-15]#3TY#15!47T-(14-+7TA04 H*+R\@("A#*2!#;W!Y<FEG:'0@2F]H M;B!086YZ97(L($=E;FYA9&EY(%)O>F5N=&%L(#(P,#(N"B\O("!097)M:7-S M:6]N('1O(&-O<'DL('5S92P@;6]D:69Y+"!S96QL(&%N9"!D:7-T<FEB=71E M('1H:7,@<V]F='=A<F4*+R\@(&ES(&=R86YT960@<')O=FED960@=&AI<R!C M;W!Y<FEG:'0@;F]T:6-E(&%P<&5A<G,@:6X@86QL(&-O<&EE<RX*+R\@(%1H M:7,@<V]F='=A<F4@:7,@<')O=FED960@(F%S(&ES(B!W:71H;W5T(&5X<')E M<W,@;W(@:6UP;&EE9"!W87)R86YT>2P*+R\@(&%N9"!W:71H(&YO(&-L86EM M(&%S('1O(&ET<R!S=6ET86)I;&ET>2!F;W(@86YY('!U<G!O<V4N"B\O"B\O M("!3964@:'1T<#HO+W=W=RYB;V]S="YO<F<@9F]R(&UO<W0@<F5C96YT('9E M<G-I;VX@:6YC;'5D:6YG(&1O8W5M96YT871I;VXN"@HO+R!"3T]35 HC:6YC M;'5D92 \8F]O<W0O8V]N9FEG+FAP<#X*"B\O($)43 HC:6YC;'5D92 \8F]O M<W0O=&5S="]T97-T7W1O;VQS+FAP<#X*"B\O(%-43 HC:6YC;'5D92 \=F5C M=&]R/@H*+R\@*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ M*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BH@+R\*+R\@ M*BHJ*BHJ*BHJ*BHJ*BH@(" @(" @(" @('1E<W1?<W1R:6-T7W=E86M?;W)D M97)I;F<@(" @(" @(" @*BHJ*BHJ*BHJ*BHJ*BH@+R\*+R\@*BHJ*BHJ*BHJ M*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ M*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BH@+R\*"B\O(%1E<W1S('=H971H97(@82!P M<F5D:6-A=&4@9G5N8W1O<B!C;7 @:7,@82 H;6]D96P@;V8I(&$*+R\@4W1R M:6-T(%=E86L@3W)D97)I;F<L('-U:71A8FQE(&9O<B!U<V4@=VET:"!O<F1E M<FEN9PHO+R!A;&=O<FET:&US(&%N9"!A<W-O8VEA=&EV92!C;VYT86EN97)S M+@HO+R *+R\@4F5Q=6ER97,Z"B\O( HO+R!#;7 @8VUP(#H@02!B:6YA<GD@ M9G5N8W1O<B!S871I<V9Y:6YG('1H92!I;G1E<F9A8V4*+R\@("!R97%U:7)E M;65N=',@9F]R(&$@4W1R:6-T(%=E86L@3W)D97)I;F<N"B\O( HO+R!);G!U M=$ET97)A=&]R(&)E9VEN+"!E;F0@.B!!;B!I=&5R871O<B!R86YG92!D969I M;FEN9PHO+R @(&$@=&5S="!D871A('-E="X@(%1H92!V86QU95]T>7!E(&UU M<W0@8F4@8V]P>2 *+R\@("!C;VYS=')U8W1I8FQE+"!B92!C;VUP871I8FQE M('=I=&@@=&AE('1W;R!I;G!U= HO+R @(&%R9W5M96YT<R!T;R!C;7 L(&%N M9"!H879E(&%N(&%P<')O<')I871E(&]P97)A=&]R/#P*+R\@("!D969I;F5D M(&9O<B!R97!O<G1I;F<@<'5R<&]S97,N"B\O( HO+R!$971A:6QS.@HO+R * M+R\@5&AI<R!A;&=O<FET:&T@<G5N<R!A('-E<FEE<R!O9B!T97-T<R!U<VEN M9R!T:&4@<W5P<&QI960*+R\@=&5S="!D871A(&%G86EN<W0@=&AE(&9U;F-T M;W(@8VUP+B @5&AI<R!C:&5C:W,@=VAE=&AE<@HO+R!C;7 @:7,@82 H;6]D M96P@;V8@82D@4W1R:6-T(%=E86L@3W)D97)I;F<L(&%S(&1E9FEN960@8GDZ M"B\O( HO+R!3=&%B:6QI='DZ"B\O(" @8VUP*&$L8BD@;75S="!R971U<FX@ M=&AE('-A;64@86YS=V5R(&9O<B!T:&4@<V%M92 *+R\@("!V86QU97,@82QB M(')E9V%R9&QE<W,@;V8@;G5M8F5R(&]F('1I;65S(&ET(&ES"B\O(" @<75E M<FEE9" H8F%S:6,@4')E9&EC871E(')E<75I<F5M96YT*2X*+R\@27)R969L M97AI=FET>3H*+R\@("!C;7 H82QA*2!I<R!F86QS92!F;W(@86YY('9A;'5E M(&$N"B\O($%N=&ES>6UM971R>3H*+R\@("!C;7 H82QB*2 M/B A8VUP*&(L M82D*+R\@5')A;G-I=&EV:71Y.@HO+R @(&-M<"AA+&(I(&%N9"!C;7 H8BQC M*2!I;7!L:65S(&-M<"AA+&,I(&9O<B!A;&P*+R\@("!A+&(L8RX*+R\@5')A M;G-I=&EV:71Y(&]F($5Q=6EV86QE;F-E.@HO+R @(&%^/6(@86YD(&)^/6,@ M:6UP;&EE<R!A?CUC(&9O<B!A;&P@82QB+&,L('=H97)E"B\O(" @>'X]>2!I M<R!D969I;F5D(&)Y("%C;7 H>"QY*2X*+R\@"B\O($YO=&4Z($EF('1H92!V M86QU95]T>7!E(&1O97,@;F]T(&%L<F5A9'D@:&%V92!A(')E87-O;F%B;&4* M+R\@;W!E<F%T;W(\/"P@861D:6YG('1H92!F;VQL;W=I;F<@=&\@=6YI="!T M97-T(&-O9&4@=VEL;" *+R\@86QL;W<@=&AI<R!F=6YC=&EO;B!T;R!L:6YK M.@HO+R *+R\@;W-T<F5A;2 F;W!E<F%T;W(@/#P@*&]S=')E86T@)F]S+%0@ M8V]N<W0@)BD@>PHO+R @(" @<F5T=7)N(&]S(#P\("<J)SL*+R\@?0HO+R * M+R\@4V5E(&%L<V\Z"B\O(&AT=' Z+R]W=W<N<V=I+F-O;2]T96-H+W-T;"]3 M=')I8W1796%K3W)D97)I;F<N:'1M; HO+R *"@IT96UP;&%T92 \8VQA<W,@ M4')E9&EC871E+"!T>7!E;F%M92!);G!U=$ET97)A=&]R/@IV;VED"G1E<W1? M<W1R:6-T7W=E86M?;W)D97)I;F<H('-T9#HZ<W1R:6YG('!R961I8V%T92P@ M4')E9&EC871E(&-M<"P@26YP=71)=&5R871O<B!B96=I;BP@26YP=71)=&5R M871O<B!E;F0@*0I["B @(" O+R!4>7!E(&]F(&5L96UE;G1S(&1E86QT('=I M=&@@*&UU<W0@8F4@8V]P>6%B;&4I.@H@(" @='EP961E9B!T>7!E;F%M92!S M=&0Z.FET97)A=&]R7W1R86ET<SQ);G!U=$ET97)A=&]R/CHZ=F%L=65?='EP M92!V86QU95]T>7!E.R O+TU35D,V4U U(&-A;B=T(&-O;7!I;&4@=&AI<SH* M"B @(" O+R!!<G)A>2!O9B!V86QU97,@=&\@=&5S="!A9V%I;G-T+"!C;W!I M960*(" @("\O(&9R;VT@=7-E<BUS=7!P;&EE9"!I;G!U="!V86QU97,Z"B @ M("!S=&0Z.G9E8W1O<CQV86QU95]T>7!E/B!V86QU97,H8F5G:6XL96YD*3L* M"B @(" O+R!!(&UA=')I>"!R96-O<F1I;F<@9G5N8W1O<B!C;VUP87)I<V]N M(&%N<W=E<G,Z"B @("!S=&0Z.G9E8W1O<CQS=&0Z.G9E8W1O<CQB;V]L/B ^ M(&QT7V%N<W=E<CL*(" @(&EN="!D871A7W-E=%]S:7IE/79A;'5E<RYS:7IE M*"D["B @("!I;G0@:2P@:CL*"B @(" O+R!&:6QL(&]U="!L=%]A;G-W97(@ M;6%T<FEX('5S:6YG(&-M<#H*(" @(&QT7V%N<W=E<BYR97-I>F4H9&%T85]S M971?<VEZ92D["@H@(" @9F]R*"!I/3 [(&D@/"!D871A7W-E=%]S:7IE.R K M*VD@*2!["B @(" @(" @;'1?86YS=V5R6VE=+G)E<VEZ92@@9&%T85]S971? M<VEZ92 I.PH*(" @(" @("!F;W(@*&H],#L@:B \(&1A=&%?<V5T7W-I>F4[ M("LK:BD@>PH@(" @(" @(" @(" O+R!296-O<F0@<F5S=6QT(&]F(&-O;7!A M<FES;VXZ"B @(" @(" @(" @(&QT7V%N<W=E<EMI75MJ72 ](&-M<"AV86QU M97-;:5TL('9A;'5E<UMJ72D["@H@(" @(" @(" @(" O+R!497-T(&9O<B!S M=&%B:6QI='DZ"B @(" @(" @(" @($)/3U-47T-(14-+7TU%4U-!1T4H(&QT M7V%N<W=E<EMI75MJ72 ]/2!C;7 H=F%L=65S6VE=+"!V86QU97-;:ETI+ H@ M(" @(" @(" @(" @(" @(E!R961I8V%T92!0*&$L8BD](B \/"!P<F5D:6-A M=&4@"B @(" @(" @(" @(" @(" \/" B(&9A:6QS('-T86)I;&ET>2!T97-T M.R!R971U<FYS(&)O=&@@=')U92!A;F0@9F%L<V4@=VAE;B!C86QL960@;75L M=&EP;&4@=&EM97,@9F]R.B!A/2 B( H@(" @(" @(" @(" @(" @/#P@=F%L M=65S6VE=(#P\("(@86YD(&(]("(@/#P@=F%L=65S6VI=("D["B @(" @(" @ M?0H*(" @(" @(" O+R!497-T(&9O<B!I<G)E9FQE>&EV:71Y.@H@(" @(" @ M($)/3U-47T-(14-+7TU%4U-!1T4H("%C;7 H=F%L=65S6VE=+'9A;'5E<UMI M72DL( H@(" @(" @(" @(" B4')E9&EC871E(% H82QB*3TB(#P\('!R961I M8V%T92 *(" @(" @(" @(" @/#P@(B!F86EL<R!I<G)E9FQE>&EV:71Y('1E M<W0[(% H82QA*2!R971U<FYS('1R=64@9F]R(&$]("(@/#P@=F%L=65S6VE= M("D["B @("!]"@H@(" @9F]R*&D],#MI/&1A=&%?<V5T7W-I>F4[*RMI*2![ M"B @(" @(" @9F]R*&H],#MJ/&1A=&%?<V5T7W-I>F4[*RMJ*2!["B @(" @ M(" @(" @("\O($-H96-K(&9O<B!A;G1I<WEM;65T<GDZ(&-M<"AA+&(I("T^ M("%C;7 H8BQA*0H@(" @(" @(" @("!"3T]35%]#2$5#2U]-15-304=%*" A M*&QT7V%N<W=E<EMI75MJ72 F)B!L=%]A;G-W97);:EU;:5TI+ H@(" @(" @ M(" @(" @(" @(E!R961I8V%T92!0*&$L8BD](B \/"!P<F5D:6-A=&4@"B @ M(" @(" @(" @(" @(" \/" B(&9A:6QS(&%N=&ES>6UM971R>2!T97-T.R!B M;W1H(% H82QB*2!A;F0@4"AB+&$I(')E='5R;B!T<G5E(&9O<B!A/2 B(#P\ M('9A;'5E<UMI72 \/" B(&%N9"!B/2 B(#P\('9A;'5E<UMJ72 I.PH*(" @ M(" @(" @(" @9F]R*&EN="!K/3 [:SQD871A7W-E=%]S:7IE.RLK:RD@>PH@ M(" @(" @(" @(" @(" @+R\@0VAE8VL@9F]R('1R86YS:71I=FET>3H@"B @ M(" @(" @(" @(" @(" O+R!C;7 H82QB*2 F(&-M<"AB+&,I("T^(&-M<"AA M+&,I"B @(" @(" @(" @(" @("!"3T]35%]#2$5#2U]-15-304=%*" A;'1? M86YS=V5R6VE=6VI=('Q\("%L=%]A;G-W97);:EU;:UT@?'P@;'1?86YS=V5R M6VE=6VM=+ H@(" @(" @(" @(" @(" @(" @(")0<F5D:6-A=&4@4"AA+&(I M/2(@/#P@<')E9&EC871E"B @(" @(" @(" @(" @(" @(" @/#P@(B!F86EL M<R!T<F%N<VET:79I='D@=&5S=#L@8F]T:"!0*&$L8BD@86YD(% H8BQC*2!R M971U<FX@=')U92!B=70@4"AA+&,I(')E='5R;G,@9F%L<V4@9F]R(&$]("(@ M"B @(" @(" @(" @(" @(" @(" @/#P@=F%L=65S6VE=(#P\("(L(&(]("(@ M/#P@=F%L=65S6VI=(#P\("(@86YD(&,]("(@/#P@=F%L=65S6VM=("D["@H@ M(" @(" @(" @(" @(" @+R\@0VAE8VL@9F]R('1R86YS:71I=FET>2!O9B!E M<75I=F%L96YC93H@"B @(" @(" @(" @(" @(" O+R A8VUP*&$L8BD@)B A M8VUP*&(L8RD@+3X@(6-M<"AA+&,I"B @(" @(" @(" @(" @("!"3T]35%]# M2$5#2U]-15-304=%*"!L=%]A;G-W97);:5U;:ET@?'P@;'1?86YS=V5R6VI= M6VM=('Q\("%L=%]A;G-W97);:5U;:UTL"B @(" @(" @(" @(" @(" @(" @ M(E!R961I8V%T92!0*&$L8BD](B \/"!P<F5D:6-A=&4@/#P*(" @(" @(" @ M(" @(" @(" @(" B(&9A:6QS('1R86YS:71I=FET>2!O9B!E<75I=6%L96YC M92!T97-T.R!B;W1H(% H82QB*2!A;F0@4"AB+&,I(')E='5R;B!F86QS92!B M=70@4"AA+&,I(')E='5R;G,@=')U92!F;W(@83T@(@H@(" @(" @(" @(" @ M(" @(" @(#P\('9A;'5E<UMI72 \/" B+"!B/2 B(#P\('9A;'5E<UMJ72 \ M/" B(&%N9"!C/2 B(#P\('9A;'5E<UMK72 I.PH@(" @(" @(" @("!]"B @ M(" @(" @?0H@(" @?0I]"@HC9&5F:6YE($)/3U-47T-(14-+7U-44DE#5%]7 M14%+7T]21$5224Y'*"!0<F5D:6-A=&4L(&)E9VEN+"!E;F0@*2!<"B @("!T M97-T7W-T<FEC=%]W96%K7V]R9&5R:6YG*" C4')E9&EC871E+"!0<F5D:6-A M=&4L(&)E9VEN+"!E;F0@*0H*(V5N9&EF("\O(%)53E1)345?0T].0T505%]# M2$5#2U](4% *"B\O("!2979I<VEO;B!(:7-T;W)Y"B\O(" @,CD@2F%N(# R M("!);FET:6%L('9E<G-I;VX@*$IO:&X@4&%N>F5R*0HO+R @(#(Y($IA;B P M,B @36]D:69I960@=&\@8F4@=7-E9"!W:71H($)O;W-T(%1E<W0@3&EB<F%R 6>2 H1V5N;F%D:7D@4F]Z96YT86PI"@`` ` end
Gennadiy Rozental wrote:
"Thorsten Ottosen" <thorsten.ottosen@dezide.com> wrote in message news:45C3529C.6040804@dezide.com...
Hi,
I couldn't find a way to do this. Maybe I have overlooked something. Anyway, making sure that operator<, operator== does the right thing is pretty important.
While ago there was an idea to have test_strict_weak_ordering. I had a prototype implemented. It never got into "production". Let me know how does it match with what you need (see attachment)
I see this as bunch of garbage chars. I don't know why. Could you include the file in the message itself? -Thorsten
"Thorsten Ottosen" <thorsten.ottosen@dezide.com> wrote in message news:45C75E5A.7030309@dezide.com...
I see this as bunch of garbage chars. I don't know why. Could you include the file in the message itself?
Strange, I do not have any problems reading my post. Here it is: #ifndef RUNTIME_CONCEPT_CHECK_HPP #define RUNTIME_CONCEPT_CHECK_HPP // (C) Copyright John Panzer, Gennadiy Rozental 2002. // Permission to copy, use, modify, sell and distribute this software // is granted provided this copyright notice appears in all copies. // This software is provided "as is" without express or implied warranty, // and with no claim as to its suitability for any purpose. // // See http://www.boost.org for most recent version including documentation. // BOOST #include <boost/config.hpp> // BTL #include <boost/test/test_tools.hpp> // STL #include <vector> // ************************************************************************** // // ************** test_strict_weak_ordering ************** // // ************************************************************************** // // Tests whether a predicate functor cmp is a (model of) a // Strict Weak Ordering, suitable for use with ordering // algorithms and associative containers. // // Requires: // // Cmp cmp : A binary functor satisfying the interface // requirements for a Strict Weak Ordering. // // InputIterator begin, end : An iterator range defining // a test data set. The value_type must be copy // constructible, be compatible with the two input // arguments to cmp, and have an appropriate operator<< // defined for reporting purposes. // // Details: // // This algorithm runs a series of tests using the supplied // test data against the functor cmp. This checks whether // cmp is a (model of a) Strict Weak Ordering, as defined by: // // Stability: // cmp(a,b) must return the same answer for the same // values a,b regardless of number of times it is // queried (basic Predicate requirement). // Irreflexivity: // cmp(a,a) is false for any value a. // Antisymmetry: // cmp(a,b) -> !cmp(b,a) // Transitivity: // cmp(a,b) and cmp(b,c) implies cmp(a,c) for all // a,b,c. // Transitivity of Equivalence: // a~=b and b~=c implies a~=c for all a,b,c, where // x~=y is defined by !cmp(x,y). // // Note: If the value_type does not already have a reasonable // operator<<, adding the following to unit test code will // allow this function to link: // // ostream &operator << (ostream &os,T const &) { // return os << '*'; // } // // See also: // http://www.sgi.com/tech/stl/StrictWeakOrdering.html // template <class Predicate, typename InputIterator> void test_strict_weak_ordering( std::string predicate, Predicate cmp, InputIterator begin, InputIterator end ) { // Type of elements dealt with (must be copyable): typedef typename std::iterator_traits<InputIterator>::value_type value_type; // Array of values to test against, copied // from user-supplied input values: std::vector<value_type> values(begin,end); // A matrix recording functor comparison answers: std::vector<std::vector<bool> > lt_answer; int data_set_size=values.size(); int i, j; // Fill out lt_answer matrix using cmp: lt_answer.resize(data_set_size); for( i=0; i < data_set_size; ++i ) { lt_answer[i].resize( data_set_size ); for (j=0; j < data_set_size; ++j) { // Record result of comparison: lt_answer[i][j] = cmp(values[i], values[j]); // Test for stability: BOOST_CHECK_MESSAGE( lt_answer[i][j] == cmp(values[i], values[j]), "Predicate P(a,b)=" << predicate << " fails stability test; returns both true and false when called multiple times for: a= " << values[i] << " and b= " << values[j] ); } // Test for irreflexivity: BOOST_CHECK_MESSAGE( !cmp(values[i],values[i]), "Predicate P(a,b)=" << predicate << " fails irreflexivity test; P(a,a) returns true for a= " << values[i] ); } for(i=0;i<data_set_size;++i) { for(j=0;j<data_set_size;++j) { // Check for antisymmetry: cmp(a,b) -> !cmp(b,a) BOOST_CHECK_MESSAGE( !(lt_answer[i][j] && lt_answer[j][i]), "Predicate P(a,b)=" << predicate << " fails antisymmetry test; both P(a,b) and P(b,a) return true for a= " << values[i] << " and b= " << values[j] ); for(int k=0;k<data_set_size;++k) { // Check for transitivity: // cmp(a,b) & cmp(b,c) -> cmp(a,c) BOOST_CHECK_MESSAGE( !lt_answer[i][j] || !lt_answer[j][k] || lt_answer[i][k], "Predicate P(a,b)=" << predicate << " fails transitivity test; both P(a,b) and P(b,c) return true but P(a,c) returns false for a= " << values[i] << ", b= " << values[j] << " and c= " << values[k] ); // Check for transitivity of equivalence: // !cmp(a,b) & !cmp(b,c) -> !cmp(a,c) BOOST_CHECK_MESSAGE( lt_answer[i][j] || lt_answer[j][k] || !lt_answer[i][k], "Predicate P(a,b)=" << predicate << " fails transitivity of equiualence test; both P(a,b) and P(b,c) return false but P(a,c) returns true for a= " << values[i] << ", b= " << values[j] << " and c= " << values[k] ); } } } } #define BOOST_CHECK_STRICT_WEAK_ORDERING( Predicate, begin, end ) \ test_strict_weak_ordering( #Predicate, Predicate, begin, end ) #endif // RUNTIME_CONCEPT_CHECK_HPP // Revision History // 29 Jan 02 Initial version (John Panzer) // 29 Jan 02 Modified to be used with Boost Test Library (Gennadiy Rozental)
Gennadiy Rozental wrote:
"Thorsten Ottosen" <thorsten.ottosen@dezide.com> wrote in message news:45C75E5A.7030309@dezide.com...
I see this as bunch of garbage chars. I don't know why. Could you include the file in the message itself?
Strange, I do not have any problems reading my post. Here it is:
Thanks. I guess it may be a thunderbird problem. It looks good. I'm don't think it is necessary to check for // Check for transitivity of equivalence: // !cmp(a,b) & !cmp(b,c) -> !cmp(a,c) doesn't that follow from antisymmetri and transitivity? I would also like to see check for equality with operator==() and operator !=(). And then a test that combines the two, like I did, s.t. one may test that == only holds when !cmp(a,b) && !cmp(b,a). -Thorsten
Thorsten Ottosen wrote:
Gennadiy Rozental wrote:
"Thorsten Ottosen" <thorsten.ottosen@dezide.com> wrote in message news:45C75E5A.7030309@dezide.com...
I see this as bunch of garbage chars. I don't know why. Could you include the file in the message itself?
Strange, I do not have any problems reading my post. Here it is:
Thanks. I guess it may be a thunderbird problem.
It looks good.
I'm don't think it is necessary to check for
// Check for transitivity of equivalence: // !cmp(a,b) & !cmp(b,c) -> !cmp(a,c)
doesn't that follow from antisymmetri and transitivity?
If we should believe the SGI docs, the property does not follow. However, you seem to have misread the property. It should be !cmp(a,b) && !cmp(b,a) && !cmp(b,c) && !cmp(c,b) -> !cmp(a,c) && !cmp(c,a) right? -Thorsten
"Thorsten Ottosen" <thorsten.ottosen@dezide.com> wrote in message news:45CEFA3F.8080807@dezide.com...
Thorsten Ottosen wrote:
Gennadiy Rozental wrote:
"Thorsten Ottosen" <thorsten.ottosen@dezide.com> wrote in message news:45C75E5A.7030309@dezide.com...
I see this as bunch of garbage chars. I don't know why. Could you include the file in the message itself?
Strange, I do not have any problems reading my post. Here it is:
Thanks. I guess it may be a thunderbird problem.
It looks good.
Does it mean you would be interrested in getting this into Boost.Test? My original plan was to create a bunch of runtime testers for variety of predicates invariants/concepts Reflexivity Irreflexivity Symmetry Antisymmetry Transitivity Transitivity of equivalence Partial ordering Strict weak ordering Total ordering .... I will need to do some aditional investigation to see what else need to be covered.
I'm don't think it is necessary to check for
// Check for transitivity of equivalence: // !cmp(a,b) & !cmp(b,c) -> !cmp(a,c)
doesn't that follow from antisymmetri and transitivity?
If we should believe the SGI docs, the property does not follow. However, you seem to have misread the property.
It should be
!cmp(a,b) && !cmp(b,a) && !cmp(b,c) && !cmp(c,b)
->
!cmp(a,c) && !cmp(c,a)
right?
Hmmm. Look like you are right. Gennadiy
Gennadiy Rozental wrote:
"Thorsten Ottosen" <thorsten.ottosen@dezide.com> wrote in message news:45CEFA3F.8080807@dezide.com...
Thorsten Ottosen wrote:
It looks good.
Does it mean you would be interrested in getting this into Boost.Test?
Oh yes, very much. IMO this stuff is difficult enough to get right to suggest it should be in the library.
My original plan was to create a bunch of runtime testers for variety of predicates invariants/concepts
Reflexivity Irreflexivity Symmetry Antisymmetry Transitivity Transitivity of equivalence Partial ordering Strict weak ordering Total ordering .....
I will need to do some aditional investigation to see what else need to be covered.
Sounds neat. It's probably hard to write tests that can make the internal predicates fail. Let me know if I can help. -Thorsten
participants (4)
-
David Abrahams -
Gennadiy Rozental -
Howard Hinnant -
Thorsten Ottosen