Tuesday, October 18, 2011

Dealing with floating points in models - Part II

Today I’m going to follow up on Part I, but I’ll give you the implementation details of the classes. I provided you with a generic interface:
IDomainVariableSampler<T>

Now as I pointed out previously, we can choose to implement this interface for any domain type, so let’s try implementing it for a double domain:
    public class DomainDoubleSampler : IDomainVariableSampler<double>
    {
        public double Maximum { get { return 100.0; } }
        public double Minimum { get { return -100.0; } }

        public double BoundaryNegative(double boundary)
        {
            return boundary - double.Epsilon;
        }

        public double BoundaryPositive(double boundary)
        {
            return boundary + double.Epsilon;
        }

        public double Sample(double lowerBound, double upperBound)
        {
            Random rand = new Random(1);
            return lowerBound + rand.NextDouble() * (upperBound - lowerBound);
        }
    }

This implementation defines an input range of [-100.0, 100.0] and is sampling at random inside partitions of this interval.

Friday, October 14, 2011

James D. McCaffrey implements Recursive Binary Search Tree

Today I came across this blog article by James D. McCaffrey, where he actually implements a recursive binary search tree, and I couldn’t resist the urge to apply my own Model-Based Testing solution [1,2] to his implementation!

I had to extend his solution a bit to allow for an internal validation function of any constructed tree, but besides from that my only comment to his solution is that he treats error conditions by silently ignore them – that is the following actions generate no errors/exceptions:
A)     Deleting an element that does not exist in the tree.
B)     Inserting an element twice into the tree.

Patching these up in his code, my model generated test cases all passed, so his implementation is rock-solid! Kudos for that!

References:
[1] Application of Model Based Testing to a Binary Search Tree - Part I
[2] Application of Model Based Testing to a Binary Search Tree - Part II

Wednesday, October 5, 2011

Domain input partitioning / dealing with floating points in models – Part I

Originally I wanted to post everything in one article, but it got too long, so I decided to split it and save the hardcore details for the next post.

I find that dealing with models involving floating point input can be a tad tricky, so why not post on this topic? The problem here is infinity. It stems from the fact that any given slice of a floating point argument is of infinite size (or at least close to). Often when working with integer models we limit the input variables to a specified range like: where x in {0..2}. However, this does of course not work if x is a floating point input.

So how do we deal with infinity? First of all we need to clarify what it is we want. Clearly we do not want to test every possible floating point values between 0 and 2. Also, what we want is determined by what we are testing. So let’s make up an example. Assume we are to test the square root function (of real values to keep it simple), what kind of inputs would we give it? If you are a software tester your testing aptitude should kick-in right about now. We want to try a sunshine scenario with a positive value. We also want to make sure any negative input gives an error and also the boundary case 0 gives an error. Then we also have some extreme ranges like a very large positive number, a large negative number and the maximum and minimum values of the input type.

If we analyze our pattern here, all we are doing is partitioning the input domain. If you have been following this blog for a while you may recall I referenced equivalence class partitioning before – this is the same stuff. Simplifying a bit we end up with an input domain like:

The important part here is that we have fixed points of interest (the boundaries) and between we have ranges. For the boundary cases, besides the actual boundary value of interest is the near neighbors ±e, where e is a very small number. For the ranges we do not really care what the exact number is, for want of better we draw a random sample from the region.

Note on Spec Explorer and small floating point values:
Unfortunately I found a bug in Spec Explorer, that it crashes when working with small values in floating point. This limits me from trying out combinations where the parameter is e. The implementation of the automatic domain partitioning will thus also be limited to testing only at boundary cases and not their near neighbors as well.


Tuesday, October 4, 2011

Comments fixed

I realized today that comments were not working on my blog.

This should have been fixed now, and you should be able to post anonymous comments!

Sorry for the inconvenience, and please leave a comment to test the site.