proposal: provide a function to verify strict weak ordering

[GoogleCodeExporter]

Many algorithms (e.g. std::sort) require a binary comparator to be a strict
weak ordering, or the program may crash or result in corrupted memory.  It
would be very useful to provide a function template to verify that a
comparitor is a strict weak ordering:

  VerifyStrictWeakOrdering(comp, values);

will test comp on the given collection of values.  When a counter example
is found, the function will generate a failure and print the counter
example to help the user understand why comp is not an SWO.  The time
complexity of this function may be O(N^2) where N is the number of values.

Original issue reported on code.google.com by zhanyong...@gmail.com on 2 Nov 2009 at 9:22

[GoogleCodeExporter]

It's better done as a gmock matcher.

Original comment by w...@google.com on 26 Feb 2010 at 8:03

• Added labels: Priority-High
• Removed labels: Priority-Medium

[GoogleCodeExporter]

Original comment by w...@google.com on 27 Sep 2010 at 7:11

[GoogleCodeExporter]

Original comment by w...@google.com on 28 Sep 2010 at 4:49

• Changed state: Started

[GoogleCodeExporter]

I have a solution almost finished that uses O(N) memory and
O(N^2) time.  It has sit there fore 6 months and I just have to find
the time to give it the final touch! ;-)

My solution is implemented as a googlemock matcher, such that you can
easily compose the predicate with other predicates, e.g.

 EXPECT_THAT(MyComparator(), IsSWO(some_array));
 EXPECT_THAT(MyComparator(), AnyOf(IsSWO(some_array), HasSomeOtherProperty()));

I'm not sure if the generality for allowing composition is really
needed, but it's nice to have that option. ;-)

Original comment by w...@google.com on 28 Jan 2011 at 8:53