Feeds:
Posts
Comments

Archive for the ‘TDD’ Category

While pulling the images from an Exif formatted Canon camera flash memory card I noticed this off-by-one error in the way the images are stored.

This is an interesting bug. Think about the code behind this problem for a moment. If we were writing this from scratch, we might start like this:

[Test]
public void Should_increment_the_image_number()
{
    _imageNumber = 0;
    int next = GetNextImageNumber();
    next.ShouldBeEqualTo(1);
    _imageNumber.ShouldBeEqualTo(1);
}

[Test]
public void Should_reset_the_image_number_to_1_given_9999()
{
    _imageNumber = 9999;
    int next = GetNextImageNumber();
    next.ShouldBeEqualTo(1);
    _imageNumber.ShouldBeEqualTo(1);
}

with implementation

private volatile int _imageNumber;

private int GetNextImageNumber()
{
    _imageNumber = _imageNumber + 1;

    if (_imageNumber > 9999)
    {
        _imageNumber = 1;
    }
    return _imageNumber;
}

Next we’ll want to handle incrementing the directory number.

[Test]
public void Should_increment_the_directory_number()
{
    _directoryNumber = 100;
    IncrementDirectoryNumber();
    _directoryNumber.ShouldBeEqualTo(101);
}

[Test]
public void Should_reset_the_directory_number_to_100_given_999()
{
    _directoryNumber = 999;
    IncrementDirectoryNumber();
    _directoryNumber.ShouldBeEqualTo(100);
}

with implementation

private volatile int _directoryNumber;

private void IncrementDirectoryNumber()
{
    _directoryNumber = _directoryNumber + 1;
    if (_directoryNumber > 999)
    {
        _directoryNumber = 100;
    }
}

Now when the image number crosses to the next 100 we have to increment the directory number.

[Test]
public void Should_increment_the_directory_number_when_the_image_number_goes_to_the_next_hundred()
{
    _imageNumber = 99;
    _directoryNumber = 100;
    int next = GetNextImageNumber();
    next.ShouldBeEqualTo(100);
    _imageNumber.ShouldBeEqualTo(100);
    _directoryNumber.ShouldBeEqualTo(101);
}

private int GetNextImageNumber()
{
    if (_imageNumber % 100 == 99)
    {
        IncrementDirectoryNumber();
    }
    _imageNumber = _imageNumber + 1;

    if (_imageNumber > 9999)
    {
        _imageNumber = 1;
    }
    return _imageNumber;
}

And lastly we need to build the file path.

[Test]
public void Should_get_path__100CANON_IMG_0002__starting_with_directory_number_100_and_image_number_1()
{
    _directoryNumber = 100;
    _imageNumber = 1;
    var path = GetNextImagePath();
    path.ShouldBeEqualTo(@"100CANON\IMG_0002");
    _directoryNumber.ShouldBeEqualTo(100);
    _imageNumber.ShouldBeEqualTo(2);
}

public string GetNextImagePath()
{
    return String.Format(
        @"{0:000}CANON\IMG_{1:0000}",
        _directoryNumber,
        GetNextImageNumber());
}

All tests pass so we’re done right? Nope. The following test fails (as expected) given the values from my image above.

[Test]
public void Should_get_path__320CANON_IMG_2000__starting_with_directory_number_319_and_image_number_1999()
{
    _directoryNumber = 319;
    _imageNumber = 1999;
    var path = GetNextImagePath();
    path.ShouldBeEqualTo(@"320CANON\IMG_2000");
    _directoryNumber.ShouldBeEqualTo(320);
    _imageNumber.ShouldBeEqualTo(2000);
}

Did you cringe/notice when we wrote the code that introduced the bug? If not, you might find the answers to this stack exchange question enlightening.

There are two routes to fixing this problem, the easy way and the correct way. The easy way is:

public string GetNextImagePath()
{
    var imageNumber = GetNextImageNumber();
    return String.Format(
        @"{0:000}CANON\IMG_{1:0000}",
        _directoryNumber,
        imageNumber);
}

The correct way is to remove the side effect so that the method becomes:

public string GetNextImagePath()
{
    IncrementImageNumber();
    return String.Format(
        @"{0:000}CANON\IMG_{1:0000}",
        _directoryNumber,
        _imageNumber);
}

… a coding problem you might use as a refactoring TDD Kata.

Advertisements

Read Full Post »

Let’s build a Sort method that uses the quicksort algorithm. Note, we’re not trying to use TDD to derive the quicksort algorithm.

Step 1 – test for a null input

Stub the test

[TestFixture]
public class When_asked_to_sort_a_list
{
    [Test]
    public void Given_null()
    {
        Test.Verify(
            with_a_null_input,
            when_asked_to_sort_the_input,
            should_throw_an_ArgumentNullException
            );
    }
	
	public void Sort<T>(IList<T> input)
    {
        throw new NotImplementedException();
	}
}

next fill in the implied details

    private Exception _exception;
    private List<char> _input;

    [SetUp]
    public void BeforeEachTest()
    {
        _input = null;
        _exception = null;
    }
	
    private void with_a_null_input()
    {
        _input = null;
    }

    private void when_asked_to_sort_the_input()
    {
        try
        {
            Sort(_input);
        }
        catch (Exception <span class="hiddenGrammarError" pre="">exception)
        {
            _exception</span> = exception;
        }
    }

    private void should_throw_an_ArgumentNullException()
    {
        _exception.ShouldNotBeNull();
        _exception.ShouldBeOfType<ArgumentNullException>();
    }

run the test

WITH a null input
WHEN asked to sort the input
SHOULD throw an  Argument Null Exception - FAILED

then build the necessary implementation.

    public void Sort<T>(IList<T> input)
    {
        if (input == null)
        {
            throw new ArgumentNullException();
        }
        throw new NotImplementedException();
    }

Step 2 – test for an empty input

Write the test

    [Test]
    public void Given_an_empty_list()
    {
        Test.Verify(
            with_an_empty_list,
            when_asked_to_sort_the_input,
            should_not_throw_an_Exception
            );
    }
	
    private void with_an_empty_list()
    {
        _input = new List<char>();
    }

    private void should_not_throw_an_Exception()
    {
        _exception.ShouldBeNull();
    }	

run the test

WITH an empty list
WHEN asked to sort the input
SHOULD not throw an  Exception - FAILED

FluentAssert.Exceptions.ShouldBeNullAssertionException :   Expected: null
  But was:  System.NotImplementedException: The method or operation is not implemented.

then update the implementation.

    public void Sort<T>(IList<T> input)
    {
        if (input == null)
        {
            throw new ArgumentNullException();
        }
        if (!input.Any())
        {
            return;
        }
        throw new NotImplementedException();
    }

Step 3 – test for a single-element input

    [Test]
    public void Given_a_single_element_list()
    {
        Test.Verify(
            with_a_list,
            that_has_element__A,
            when_asked_to_sort_the_input,
            should_not_throw_an_Exception,
            the_element_of_the_list_should_be__A
            );
    }

    private void with_a_list()
    {
        with_an_empty_list();
    }

    private void that_has_element__A()
    {
        _input.Add('A');
    }

    private void the_element_of_the_list_should_be__A()
    {
        _input.ShouldContainAllInOrder(new[] { 'A' });
    }	

run the test

WITH a list
that has element   A - PASSED
WHEN asked to sort the input
SHOULD not throw an  Exception - FAILED

FluentAssert.Exceptions.ShouldBeNullAssertionException :   Expected: null
  But was:  System.NotImplementedException: The method or operation is not implemented.

update the implementation.

    public void Sort<T>(IList<T> input)
    {
        if (input == null)
        {
            throw new ArgumentNullException();
        }
        if (input.Count <= 1)
        {
            return;
        }
        throw new NotImplementedException();
    }

Step 4a – test sorting list { A B }

    [Test]
    public void Given_a_list_with_elements__A_B()
    {
        Test.Verify(
            with_a_list,
            that_starts_with_element__A,
            followed_by_element__B,
            when_asked_to_sort_the_input,
            should_not_throw_an_Exception,
            the_elements_of_the_sorted_list_should_be__A_B__in_that_order
            );
    }

    private void that_starts_with_element__A()
    {
        that_has_element__A();
    }

    private void followed_by_element__B()
    {
        _input.Add('B');
    }

    private void the_elements_of_the_sorted_list_should_be__A_B__in_that_order()
    {
        _input.ShouldContainAllInOrder("AB".ToArray());
    }

run the test

WITH a list
that starts with element   A - PASSED
followed by element   B - PASSED
WHEN asked to sort the input
SHOULD not throw an  Exception - FAILED

FluentAssert.Exceptions.ShouldBeNullAssertionException :   Expected: null
  But was:  System.NotImplementedException: The method or operation is not implemented.

update the implementation.

    public void Sort<T>(IList<T> input)
    {
        if (input == null)
        {
            throw new ArgumentNullException();
        }
        if (input.Count <= 1)
        {
            return;
        }

    }

Step 4b – test sorting list { B A }

    [Test]
    public void Given_a_list_with_elements__B_A()
    {
        Test.Verify(
            with_a_list,
            that_starts_with_element__B,
            followed_by_element__A,
            when_asked_to_sort_the_input,
            should_not_throw_an_Exception,
            the_elements_of_the_sorted_list_should_be__A_B__in_that_order
            );
    }

    private void that_has_element__B()
    {
        _input.Add('B');
    }

    private void followed_by_element__B()
    {
        that_has_element__B();
    }

    private void that_starts_with_element__B()
    {
        that_has_element__B();
    }

    private void followed_by_element__A()
    {
        that_has_element__A();
    }

run the test

WITH a list
that starts with element   B - PASSED
followed by element   A - PASSED
WHEN asked to sort the input
SHOULD not throw an  Exception - PASSED
the elements of the sorted list should be   A  B  in that order - FAILED

FluentAssert.Exceptions.ShouldBeEqualAssertionException : at offset 0

update the implementation.

    public void Sort<T>(IList<T> input) 
        where T : IComparable
    {
        if (input == null)
        {
            throw new ArgumentNullException();
        }
        if (input.Count <= 1)
        {
            return;
        }
        SwapIfOutOfOrder(input, 0, 1);
    }

    private static void SwapIfOutOfOrder<T>(IList<T> input, int first, int second)
        where T : IComparable
    {
        if (input[first].CompareTo(input[second]) == 1)
        {
            var temp = input[first];
            input[first] = input[second];
            input[second] = temp;
        }
    }

Step 4c – track comparisons

In order to verify that the sort algorithm used by Sort is quicksort we need the ability to introspect what it is doing. Verifying that the output is sorted is insufficient because it could be using some other sort algorithm and we specifically want to implement quicksort. In a previous post we passed an instrumented IComparer along with the list to the sorted to the Sort method. This time we’ll try something different. We’ll wrap the objects being sorted so that we can count the number of comparisons performed during the sort. This has the advantage of working with any Sort implementation that can sort IComparable elements and with lists that contain duplicate elements.

public class ComparableWrapper<T> : IComparable
    where T : IComparable
{
    private readonly T _value;
    private readonly Action _action;

    public ComparableWrapper(T value, Action action)
    {
        _value = value;
        _action = action;
    }

    public T Value
    {
        get { return _value; }
    }

    public int CompareTo(object obj)
    {
        var otherWrapper = obj as ComparableWrapper<T>;
        if (otherWrapper == null)
        {
            throw new ArgumentException("Object is not a ComparableWrapper");
        }
        _action();
        return _value.CompareTo(otherWrapper._value);
    }
}

update the tests to use the wrapper

    private List<ComparableWrapper<char>> _input;
    private int _comparisonCount;

    private void IncrementCount()
    {
        _comparisonCount++;
    }
	
	[SetUp]
    public void BeforeEachTest()
    {
        _comparisonCount = 0;
        _input = null;
        _exception = null;
    }
	
    private void with_an_empty_list()
    {
        _input = new List<ComparableWrapper<char>>();
    }	
	
    private void Add(char value)
    {
        _input.Add(new ComparableWrapper<char>(value, IncrementCount));
    }

    private void that_has_element__A()
    {
        Add('A');
    }

    private void that_has_element__B()
    {
        Add('B');
    }

    private void the_element_of_the_list_should_be__A()
    {
        _input.Select(x => x.Value)
              .ShouldContainAllInOrder(new[] {'A'});
    }
	
    private void the_elements_of_the_sorted_list_should_be__A_B__in_that_order()
    {
        _input.Select(x => x.Value)
          .ShouldContainAllInOrder("AB".ToArray());
    }	

and add to the tests to check the comparison count.

    [Test]
    public void Given_a_list_with_elements__A_B()
    {
        Test.Verify(
            with_a_list,
            that_starts_with_element__A,
            followed_by_element__B,
            when_asked_to_sort_the_input,
            should_not_throw_an_Exception,
            the_elements_of_the_sorted_list_should_be__A_B__in_that_order,
            should_perform_at_most_1_comparison
            );
    }

    private void should_perform_at_most_1_comparison()
    {
        _comparisonCount.ShouldBeLessThanOrEqualTo(1);
    }
	
    [Test]
    public void Given_a_list_with_elements__B_A()
    {
        Test.Verify(
            with_a_list,
            that_starts_with_element__B,
            followed_by_element__A,
            when_asked_to_sort_the_input,
            should_not_throw_an_Exception,
            the_elements_of_the_sorted_list_should_be__A_B__in_that_order,
            should_perform_at_most_1_comparison
            );
    }	

Step 5a – test sorting list { C B A }

    [Test]
    public void Given_a_list_with_elements__C_B_A()
    {
        Test.Verify(
            with_a_list,
            that_starts_with_element__C,
            followed_by_element__B,
            followed_by_element__A,
            when_asked_to_sort_the_input,
            should_not_throw_an_Exception,
            the_elements_of_the_sorted_list_should_be__A_B_C__in_that_order,
            should_perform_at_most_3_comparisons
            );
    }

    private void that_starts_with_element__C()
    {
        that_has_element__C();
    }

    private void that_has_element__C()
    {
        Add('C');
    }

    private void the_elements_of_the_sorted_list_should_be__A_B_C__in_that_order()
    {
        _input.Select(x => x.Value)
            .ShouldContainAllInOrder("ABC".ToArray());
    }

    private void should_perform_at_most_3_comparisons()
    {
        _comparisonCount.ShouldBeLessThanOrEqualTo(3);
    }

run the test

WITH a list
that starts with element   C - PASSED
followed by element   B - PASSED
followed by element   A - PASSED
WHEN asked to sort the input
SHOULD not throw an  Exception - PASSED
the elements of the sorted list should be   A  B  C  in that order - FAILED

FluentAssert.Exceptions.ShouldBeEqualAssertionException : at offset 0

update the implementation.

    public void Sort<T>(IList<T> input)
        where T : IComparable
    {
        if (input == null)
        {
            throw new ArgumentNullException();
        }
        if (input.Count <= 1)
        {
            return;
        }
        SwapIfOutOfOrder(input, 0, 1);
        if (input.Count == 2)
        {
            return;
        }
        SwapIfOutOfOrder(input, 0, 2);
        SwapIfOutOfOrder(input, 1, 2);
    }

Step 5b – test sorting all permutations of list { C B A }

To make sure the code works for all permutations of the list we’ll make use of the Permute extension and FormatForDisplay extension built in previous postings.

    [Test]
    public void Should_be_able_to_sort_all_permutations_of__C_B_A__with_at_most_3_comparisons_each()
    {
        with_a_list();
        that_starts_with_element__C();
        followed_by_element__B();
        followed_by_element__A();

        foreach (var permutation in _input.Permute(3))
        {
            _comparisonCount = 0;
            _input = permutation.ToList();
            try
            {
                when_asked_to_sort_the_input();
                the_elements_of_the_sorted_list_should_be__A_B_C__in_that_order();
                should_perform_at_most_3_comparisons();
            }
            catch (Exception e)
            {
                Console.WriteLine("failed on permutation " + permutation.Select(x => x.Value).FormatForDisplay());
                throw;
            }
        }
    }

run the test and get an unexpected failure

failed on permutation { C A B }

FluentAssert.Exceptions.ShouldBeEqualAssertionException : at offset 0

due to an assumption made about the values returned by CompareTo. Fix it:

    private static void SwapIfOutOfOrder<T>(IList<T> input, int first, int second)
        where T : IComparable
    {
        if (input[first].CompareTo(input[second]) > 0)
        {
            var temp = input[first];
            input[first] = input[second];
            input[second] = temp;
        }
    }

Step 6a – test sorting list { D C A B }

    [Test]
    public void Given_a_list_with_elements__D_C_A_B()
    {
        Test.Verify(
            with_a_list,
            that_starts_with_element__D,
            followed_by_element__C,
            followed_by_element__A,
            followed_by_element__B,
            when_asked_to_sort_the_input,
            should_not_throw_an_Exception,
            the_elements_of_the_sorted_list_should_be__A_B_C_D__in_that_order,
            should_perform_at_most_6_comparisons
            );
    }
	
	private void that_starts_with_element__D()
    {
        that_has_element__D();
    }
	
    private void that_has_element__D()
    {
        Add('D');
    }

	private void followed_by_element__C()
    {
        that_has_element__C();
    }
	
    private void the_elements_of_the_sorted_list_should_be__A_B_C_D__in_that_order()
    {
        _input.Select(x => x.Value)
            .ShouldContainAllInOrder("ABCD".ToArray());
    }

    private void should_perform_at_most_6_comparisons()
    {
        _comparisonCount.ShouldBeLessThanOrEqualTo(6);
    }	

run the test

WITH a list
that starts with element   D - PASSED
followed by element   C - PASSED
followed by element   A - PASSED
followed by element   B - PASSED
WHEN asked to sort the input
SHOULD not throw an  Exception - PASSED
the elements of the sorted list should be   A  B  C  D  in that order - FAILED

FluentAssert.Exceptions.ShouldBeEqualAssertionException : at offset 0

update the implementation to use bubble sort.

    public void Sort<T>(IList<T> input) where T : IComparable
    {
        if (input == null)
        {
            throw new ArgumentNullException();
        }
        for (int outer = input.Count; outer >= 1; outer--)
        {
            for (int inner = 0; inner < outer - 1; inner++)
            {
                SwapIfOutOfOrder(input, inner, inner + 1);
            }
        }
    }

Step 6b – test sorting all permutations of list { D C A B } with at most 6 comparisons each

    [Test]
    public void Should_be_able_to_sort_all_permutations_of__D_C_A_B__with_at_most_6_comparisons_each()
    {
        with_a_list();
        that_starts_with_element__D();
        followed_by_element__C();
        followed_by_element__A();
        followed_by_element__B();

        foreach (var permutation in _input.Permute(4))
        {
            _comparisonCount = 0;
            _input = permutation.ToList();
            try
            {
                when_asked_to_sort_the_input();
                the_elements_of_the_sorted_list_should_be__A_B_C_D__in_that_order();
                should_perform_at_most_6_comparisons();
            }
            catch (Exception e)
            {
                Console.WriteLine("failed on permutation " + permutation.Select(x => x.Value).FormatForDisplay());
                throw;
            }
        }
    }

test passes.

Step 6c – test sorting all permutations of list { D C A B } with less than 6 comparisons each on average

This is the where we force the implementation away from bubble sort. Bubble sort always uses 6 comparisons to sort 4 elements but quicksort only needs 6 in the worst case.

    [Test]
    public void Should_be_able_to_sort_all_permutations_of__D_C_A_B__with_less_than_6_comparisons_each_on_average()
    {
        with_a_list();
        that_starts_with_element__D();
        followed_by_element__C();
        followed_by_element__A();
        followed_by_element__B();

        int totalComparisons = 0;
        int totalPermutations = 0;
        foreach (var permutation in _input.Permute(4))
        {
            totalPermutations++;
            _comparisonCount = 0;
            _input = permutation.ToList();
            try
            {
                when_asked_to_sort_the_input();
                the_elements_of_the_sorted_list_should_be__A_B_C_D__in_that_order();
                should_perform_at_most_6_comparisons();
                totalComparisons += _comparisonCount;
            }
            catch (Exception e)
            {
                Console.WriteLine("failed on permutation " + permutation.Select(x => x.Value).FormatForDisplay());
                throw;
            }
        }

        var average = totalComparisons / (double)totalPermutations;
        average.ShouldBeLessThan(6, () => "Incorrect average number of comparisons - " + average);
    }

run the test

FluentAssert.Exceptions.ShouldBeLessThanAssertionException : Incorrect average number of comparisons - 6

update the implementation using the wikipedia algorithm as a guide.

    public void Sort<T>(IList<T> input)
        where T : IComparable
    {
        if (input == null)
        {
            throw new ArgumentNullException();
        }

        var segments = new Stack<int[]>();
        segments.Push(new[] { 0, input.Count - 1 });
        while (segments.Any())
        {
            var segment = segments.Pop();
            int first = segment[0];
            int last = segment[1];
            int middle = GetMiddle(first, last);
            while (first < last)
            {
                while (first < middle && AreInCorrectOrder(input, first, middle))
                {
                    first++;
                }
                while (last > middle && AreInCorrectOrder(input, middle, last))
                {
                    last--;
                }
                if (first < last)
                {
                    Swap(input, first, last);
                    first++;
                    last--;
                    if (first - 1 == middle)
                    {
                        middle = ++last;
                    }
                    else if (last + 1 == middle)
                    {
                        middle = --first;
                    }
                }
            }
            if (middle - segment[0] > 1)
            {
                segments.Push(new[] { segment[0], middle - 1 });
            }
            if (segment[1] - middle > 1)
            {
                segments.Push(new[] { middle + 1, segment[1] });
            }
        }
    }

    private static int GetMiddle(int first, int last)
    {
        return first + ((last - first) >> 1);
    }
	
    private static bool AreInCorrectOrder<T>(IList<T> input, int first, int second)
        where T : IComparable
    {
        return input[first].CompareTo(input[second]) <= 0;
    }	

    private static void Swap<T>(IList<T> input, int first, int second)
    {
        var temp = input[first];
        input[first] = input[second];
        input[second] = temp;
    }

Step 7 – make sure the implementation can handle all permutations of list { A B C D E F G H }

    [Test]
    public void Should_be_able_to_sort_all_permutations_of__A_B_C_D_E_F_G_H()
    {
        with_a_list();
        "ABCDEFGH".ToList().ForEach(Add);

        foreach (var permutation in _input.Permute(8))
        {
            _comparisonCount = 0;
            _input = permutation.ToList();
            try
            {
                when_asked_to_sort_the_input();
                the_elements_of_the_sorted_list_should_be__A_B_C_D_E_F_G_H_in_that_order();
            }
            catch (Exception e)
            {
                Console.WriteLine("failed on permutation " + permutation.Select(x => x.Value).FormatForDisplay());
                throw;
            }
        }
    }

    private void the_elements_of_the_sorted_list_should_be__A_B_C_D_E_F_G_H_in_that_order()
    {
        _input.Select(x => x.Value)
            .ShouldContainAllInOrder("ABCDEFGH".ToArray());
    }

test passes.

Final – how does this implementation compare to List.Sort?

First get the number of comparisons our Sort uses across all permutations of { A B C D E F G H }

    var input = "ABCDEFGH"
        .Select(x=>new ComparableWrapper<char>(x, IncrementCount))
        .ToList();

    foreach (var permutation in input.Permute(8))
    {
        Sort(permutation);
    }
    Console.WriteLine("total comparisons: "+_comparisonCount);

output

total comparisons: 682272

Now get the number of comparisons List.Sort uses for the same set of inputs.

    var input = "ABCDEFGH"
        .Select(x=>new ComparableWrapper<char>(x, IncrementCount))
        .ToList();

    foreach (var permutation in input.Permute(8))
    {
        permutation.ToList().Sort();
    }
    Console.WriteLine("total comparisons: "+_comparisonCount);

output

total comparisons: 1209888

whoa! Our no-frills implementation of quicksort uses only 56% of the comparisons that List.Sort requires to achieve the same goal!

682272 / 1209888 = 0.563913354

It kind of makes you wonder: which sort algorithm does List.Sort use?

Read Full Post »

Generating all permutations of a sequence in c#

Start with a basic null list test to get the classes and method prototype in place.

public class IListExtensionsTests
{
    [TestFixture]
    public class When_asked_to_generate_all_permutations_of_a_specific_length_from_a_list
    {
        private IList<char> _input;
        private int _length;
        private IEnumerable<IList<char>> _result;

        [Test]
        public void Given_a_null_list()
        {
            Test.Verify(
                with_a_null_list,
                and_a_requested_length_of_2,
                when_asked_to_generate_all_permutations_of_the_requested_length_from_the_list,
                should_return_an_empty_list_of_permutations
                );
        }

        private void with_a_null_list()
        {
            _input = null;
        }

        private void and_a_requested_length_of_2()
        {
            _length = 2;
        }

        private void when_asked_to_generate_all_permutations_of_the_requested_length_from_the_list()
        {
            _result = _input.Permute(_length).ToList();
        }

        private void should_return_an_empty_list_of_permutations()
        {
            _result.Count().ShouldBeEqualTo(0);
        }
    }
}

and implementation

public static class IListExtensions
{
    public static IEnumerable<IList<T>> Permute<T>(this IList<T> list, int length)
    {
        if (list == null)
        {
            yield break;
        }
        throw new NotImplementedException();
    }
}

Next add tests for other invalid parameters starting with empty list.

	[Test]
	public void Given_an_empty_list()
	{
		Test.Verify(
			with_an_empty_list,
			and_a_requested_length_of_2,
			when_asked_to_generate_all_permutations_of_the_requested_length_from_the_list,
			should_return_an_empty_list_of_permutations
			);
	}

	private void with_an_empty_list()
	{
		_input = new List<char>();
	}

    public static IEnumerable<IList<T>> Permute<T>(this IList<T> list, int length)
    {
        if (list == null || 
            list.Count == 0)
        {
            yield break;
        }
        throw new NotImplementedException();
    }

Then a negative requested length.

	[Test]
	public void Given_a_non_empty_list_and_a_negative_length()
	{
		Test.Verify(
			with_a_non_empty_list,
			and_a_negative_requested_length,
			when_asked_to_generate_all_permutations_of_the_requested_length_from_the_list,
			should_return_an_empty_list_of_permutations
			);
	}

	private void with_a_non_empty_list()
	{
		with_a_list_of_3_items();
	}

	private void with_a_list_of_3_items()
	{
		_input = new List<char>
                {
                    'A',
                    'B',
                    'C'
                };
	}

	private void and_a_negative_requested_length()
	{
		_length = -3;
	}

    public static IEnumerable<IList<T>> Permute<T>(this IList<T> list, int length)
    {
        if (list == null || 
            list.Count == 0 || 
            length < 0)
        {
            yield break;
        }
        throw new NotImplementedException();
    }

Then a zero requested length.

	[Test]
	public void Given_a_non_empty_list_and_length_zero()
	{
		Test.Verify(
			with_a_non_empty_list,
			and_a_requested_length_of_zero,
			when_asked_to_generate_all_permutations_of_the_requested_length_from_the_list,
			should_return_an_empty_list_of_permutations
			);
	}

	private void and_a_requested_length_of_zero()
	{
		_length = 0;
	}

    public static IEnumerable<IList<T>> Permute<T>(this IList<T> list, int length)
    {
        if (list == null || 
		    list.Count == 0 || 
			length <= 0)
        {
            yield break;
        }
        throw new NotImplementedException();
    }

And a test for the length being greater than the number of items in the list.

    [Test]
    public void Given_a_non_empty_list_and_length_greater_than_the_number_of_items_in_the_list()
    {
        Test.Verify(
            with_a_non_empty_list,
            and_a_requested_length_greater_than_the_number_of_items_in_the_list,
            when_asked_to_generate_all_permutations_of_the_requested_length_from_the_list,
            should_throw_an_ArgumentOutOfRangeException
            );
    }

    private void and_a_requested_length_greater_than_the_number_of_items_in_the_list()
    {
        _length = 1 + _input.Count;
    }

    private void should_throw_an_ArgumentOutOfRangeException()
    {
        _exception.ShouldNotBeNull();
        _exception.GetType().ShouldBeEqualTo(typeof(ArgumentOutOfRangeException));
    }

    private Exception _exception;

    private void when_asked_to_generate_all_permutations_of_the_requested_length_from_the_list()
    {
        try
        {
            _result = _input.Permute(_length).ToList();
        }
        catch (Exception e)
        {
            _exception = e;
        }
    }

    public static IEnumerable<IList<T>> Permute<T>(this IList<T> list, int length)
    {
        if (list == null || 
            list.Count == 0 || 
            length <= 0)
        {
            yield break;
        }

        if (length > list.Count)
        {
            throw new ArgumentOutOfRangeException("length",
                                                  "length must be between 1 and the length of the list inclusive");
        }        
        
        throw new NotImplementedException();
    }

Now we can drive out the permutations piece starting with permutations of length 1.

    [Test]
    public void Given_a_non_empty_list_and_length_1()
    {
        Test.Verify(
            with_a_non_empty_list,
            and_a_requested_length_of_1,
            when_asked_to_generate_all_permutations_of_the_requested_length_from_the_list,
            should_return_a_list_having_the_expected_number_of_permutations,
            each_input_should_appear_in_the_result_list_only_once
            );
    }

    private void and_a_requested_length_of_1()
    {
        _length = 1;
    }

    private void should_return_a_list_having_the_expected_number_of_permutations()
    {
        _result.Count().ShouldBeEqualTo(_expectedPermutationCount);
    }

    private void each_input_should_appear_in_the_result_list_only_once()
    {
        foreach (char value in _input)
        {
            _result.Count(x => x.Contains(value)).ShouldBeEqualTo(1);
        }
    }

    private int _expectedPermutationCount;

    private void when_asked_to_generate_all_permutations_of_the_requested_length_from_the_list()
    {
        SetExpectedPermutationCount();

        try
        {
            _result = _input.Permute(_length).ToList();
        }
        catch (Exception e)
        {
            _exception = e;
        }
    }
    private void SetExpectedPermutationCount()
    {
        if (_input == null ||
            _input.Count == 0 ||
            _input.Count < _length)
        {
            _expectedPermutationCount = 0;
        }
        else
        {
            _expectedPermutationCount
                = Numeric.Factorial(_input.Count)
                    / Numeric.Factorial(_input.Count - _length);
        }
    }
    
    public static IEnumerable<IList<T>> Permute<T>(this IList<T> list, int length)
    {
        if (list == null || 
            list.Count == 0 || 
            length <= 0)
        {
            yield break;
        }

        if (length > list.Count)
        {
            throw new ArgumentOutOfRangeException("length",
                                                  "length must be between 1 and the length of the list inclusive");
        }        
        
        foreach (T t in list)
        {
            yield return new[] { t };
        }
    }    

Next length 2 which will get the recursion part. When the length is 1 we’ll just return the list, otherwise we’ll call Permute() with the list items we didn’t select and the length reduced by 1 and yield each of the results combined with the selected list item, as follows:

start with: [ A, B, C ] and length 3

loop all items
    pick A => recurses with [ B, C ] and length 2
        loop all items
            pick B => recurses with [C] and length 1
                loop all items
                    yields [C]
                    concat that with [B] and yield [B,C]
                    concat that with [A] and yield [A,B,C]
            pick C => recurses with [B] and length 1
                loop all items
                    yields [B]
                    concat that with [C] and yield [C,B]
                    concat that with [A] and yield [A,C,B]
    pick B => recurses with [ A, C ] and length 2

    ... and so on

test and implementation

    [Test]
    public void Given_a_list_with_3_items_and_length_2()
    {
        Test.Verify(
            with_a_list_of_3_items,
            and_a_requested_length_of_2,
            when_asked_to_generate_all_permutations_of_the_requested_length_from_the_list,
            should_return_a_list_having_the_expected_number_of_permutations,
            all_permutations_should_be_unique,
            each_permutation_should_have_disinct_elements,
            each_permutation_should_have_the_requested_length
            );
    }

    private void all_permutations_should_be_unique()
    {
        _result.Count().ShouldBeEqualTo(_expectedPermutationCount);
        _result
            .Select(x => String.Join("|", x.Select(y => y.ToString()).ToArray()))
            .Distinct()
            .Count().ShouldBeEqualTo(_expectedPermutationCount);
    }

    private void each_permutation_should_have_disinct_elements()
    {
        foreach (var value in _result)
        {
            value.Distinct().Count().ShouldBeEqualTo(_length);
        }
    }

    private void each_permutation_should_have_the_requested_length()
    {
        foreach (var value in _result)
        {
            value.Count.ShouldBeEqualTo(_length);
        }
    }
    
    public static IEnumerable<IList<T>> Permute<T>(this IList<T> list, int length)
    {
        if (list == null || 
            list.Count == 0 || 
            length <= 0)
        {
            yield break;
        }

        if (length > list.Count)
        {
            throw new ArgumentOutOfRangeException("length",
                                                  "length must be between 1 and the length of the list inclusive");
        }        
        
        for (int i = 0; i < list.Count; i++)
        {
            var item = list[i];
            var initial = new[] { item };
            if (length == 1)
            {
                yield return initial;
            }
            else
            {
                foreach (var variation in Permute(list.Where((x, index) => index != i).ToList(), length - 1))
                {
                    yield return initial.Concat(variation).ToList();
                }
            }
        }
    }    
    
public static class Int32Extensions
{
    public static int Factorial(this int n)
    {
        if (n == 0)
        {
            return 1;
        }
        return n * Factorial(n - 1);
    }
}    

One last check to make sure we can get all the permutations.

    [Test]
    public void Given_a_list_with_4_items_and_length_equal_to_the_number_of_items_in_the_list()
    {
        Test.Verify(
            with_a_list_of_4_items,
            and_a_requested_length_equal_to_the_number_of_items_in_the_list,
            when_asked_to_generate_all_permutations_of_the_requested_length_from_the_list,
            should_return_a_list_having_the_expected_number_of_permutations,
            all_permutations_should_be_unique,
            each_permutation_should_have_disinct_elements,
            each_permutation_should_have_the_requested_length
            );
    }

    private void with_a_list_of_4_items()
    {
        _input = new List<char>
                {
                    'A', 'B', 'C', 'D'
                };
    }

    private void and_a_requested_length_equal_to_the_number_of_items_in_the_list()
    {
        _length = _input.Count;
    }

Now lets make sure Permute() works for value types too. This implies parallel test classes – one for integer and one for characters. First rename the current test class.

    [TestFixture]
    public class When_asked_to_generate_all_permutations_of_a_specific_length_from_a_list_of_integers
    {

Then fork all the tests into a new class and change the type of _input and related fillers to integer.

    [TestFixture]
    public class When_asked_to_generate_all_permutations_of_a_specific_length_from_a_list_of_characters
    {
        private IList<char> _input;
        private int _length;
        private IEnumerable<IList<char>> _result;

    private void with_a_list_of_3_items()
    {
        _input = new List<int>
                   {
                       1, 2, 3
                   };
    }

    private void with_a_list_of_4_items()
    {
        _input = new List<int>
                   {
                       1, 2, 3, 4
                   };
    }

    private void with_an_empty_list()
    {
        _input = new List<int>();
    }

Now run all the tests in both test classes and verify that they still pass.

The final code for the implementation and test classes is available from Github. Enjoy!

Update 8 Sep 2011 – Removed non-fluent tests and integrated fluent tests more closely with the related implementation to clarify the TDD. Added recursive permutation plan before the recursion implementation.

Read Full Post »

The self-referencing string indexer examines an input string and builds an array of index values for that input. The index is built according to rules as outlined below.

Create a String indexer with method int[] Index(string input)

  1. return an empty array if the input is null
  2. return an empty array if the input is empty
  3. the index array should have the same number of elements as the input
  4. the index array values should default to 0
  5. the first value of the index array should always be -1
  6. the second value of the index array should always be 0
  7. when an input character is one position to the right of a character that is the same as the input character at that character’s corresponding index value then its corresponding index value should be 1 + the index value of the character to its left

example:

input = "aab" 
output = [-1,0,1]
	output[0] is -1 // rule 5
	output[1] is 0  // rule 6
	output[2] is 1  // rule 7 because input[2-1] == input[output[2-1]] => input[1] == input[0] => 'a' == 'a'

example:

input = "abcabda" 
output = [-1,0,0,0,1,2,0]
	output[0] is -1 // rule 5
	output[1] is 0  // rule 6
	output[2] is 0  // rule 4
	output[3] is 0  // rule 4
	output[4] is 1  // rule 7 because input[4-1] == input[output[4-1]] => input[3] == input[0] => 'a' == 'a'
	output[5] is 2  // rule 7 because input[5-1] == input[output[5-1]] => input[4] == input[1] => 'b' == 'b'
	output[6] is 0  // rule 4

You have implemented the table-building portion of the Knuth-Morris-Pratt substring search algorithm.

Read Full Post »

This is a sample unit test written using the FluentAssert BDD framework.

	[Test]
	public void Given_a_business_object_with_no_natural_keys()
	{
		Test.Verify(
			with_a_business_object_that_has_no_natural_keys,
			when_lookup_is_called,
			should_return_a_valid_notification);
	}

When my cursor is on one of the test actions and I hit alt-enter Resharper is usually smart enough to suggest creating a method.

Other times, however, Resharper doesn’t offer the option we need.

My solution to this problem is a Visual Studio macro that creates a void parameterless method for the “word” the cursor is on. This necessitates determining where the new method should be created e.g. top of the file, bottom of the file, just before the method, just after the method. I like to keep the new method close to the test when I’m first creating it so that means above or below the method. Initially I tried it above the method but learned that in my workflow I expect the new method to be added below the test. So how do we do that? We’ll write a Visual Studio macro to do the work.

First we need to copy the proposed method name. We’ll grab the word under the cursor and put it in a variable. Also, since we don’t want to affect the user’s copy-paste buffer we’ll do it within an undo context.

        DTE.UndoContext.Open("AddBddMethod")

        DTE.ExecuteCommand("Edit.SelectCurrentWord")

        Dim name As String
        name = DTE.ActiveDocument.Selection.Text

Next to move to the end of the test method we’ll search for ‘}’ and close the find dialog when we’re done.

        DTE.ExecuteCommand("Edit.Find")
        DTE.Find.Target = vsFindTarget.vsFindTargetCurrentDocument
        DTE.Find.FindWhat = "}"
        DTE.Find.MatchCase = True
        DTE.Find.MatchWholeWord = False
        DTE.Find.Backwards = False
        DTE.Find.MatchInHiddenText = True
        DTE.Find.PatternSyntax = vsFindPatternSyntax.vsFindPatternSyntaxLiteral
        DTE.Find.Action = vsFindAction.vsFindActionFind
        If (DTE.Find.Execute() = vsFindResult.vsFindResultNotFound) Then
            Throw New System.Exception("vsFindResultNotFound")
        End If
        DTE.Windows.Item("{CF2DDC32-8CAD-11D2-9302-005345000000}").Close()

We want one newline between the test method and the new method so we move the cursor one position to the right to get past the ‘}’ then add two newlines.

        DTE.ActiveDocument.Selection.CharRight()
        DTE.ActiveDocument.Selection.NewLine()
        DTE.ActiveDocument.Selection.NewLine()

Next we’ll introduce the new method.

        DTE.ActiveDocument.Selection.Text = "private void "
        DTE.ActiveDocument.Selection.Text = name
        DTE.ActiveDocument.Selection.Text = "()"
        DTE.ActiveDocument.Selection.NewLine
        DTE.ActiveDocument.Selection.Text = "{}"

Our method now looks like:

	private void when_lookup_is_called()
	{
	}// <- cursor here

Now we want to set up to add contents to the new method so we move up between the ‘{}’ and add a newline.

        DTE.ActiveDocument.Selection.LineUp()
        DTE.ExecuteCommand("Edit.BreakLine")

Our method now looks like:

	private void when_lookup_is_called()
	{
		// <- cursor here
	}

Finally we need to close the undo context.

        DTE.UndoContext.Close()

That’s it.

Next we need to add it as a Visual Studio macro. First open the macro editor.

Create a new module called “RecordingModule” under MyMacros.

Then replace the entire contents of the default macro with the macro we built:

Option Strict Off
Option Explicit Off
Imports System
Imports EnvDTE
Imports EnvDTE80
Imports EnvDTE90
Imports System.Diagnostics

Public Module RecordingModule


	Sub Add_BDD_method()
        DTE.UndoContext.Open("AddBddMethod")
        DTE.ExecuteCommand("Edit.SelectCurrentWord")

        Dim name As String
        name = DTE.ActiveDocument.Selection.Text

        DTE.ExecuteCommand("Edit.Find")
        DTE.Find.Target = vsFindTarget.vsFindTargetCurrentDocument
        DTE.Find.FindWhat = "}"
        DTE.Find.MatchCase = True
        DTE.Find.MatchWholeWord = False
        DTE.Find.Backwards = False
        DTE.Find.MatchInHiddenText = True
        DTE.Find.PatternSyntax = vsFindPatternSyntax.vsFindPatternSyntaxLiteral
        DTE.Find.Action = vsFindAction.vsFindActionFind
        If (DTE.Find.Execute() = vsFindResult.vsFindResultNotFound) Then
            Throw New System.Exception("vsFindResultNotFound")
        End If
        DTE.Windows.Item("{CF2DDC32-8CAD-11D2-9302-005345000000}").Close()
        DTE.ActiveDocument.Selection.CharRight()
        DTE.ActiveDocument.Selection.NewLine()
        DTE.ActiveDocument.Selection.NewLine()
        DTE.ActiveDocument.Selection.Text = "private void "
        DTE.ActiveDocument.Selection.Text = name
        DTE.ActiveDocument.Selection.Text = "()"
	DTE.ActiveDocument.Selection.NewLine
        DTE.ActiveDocument.Selection.Text = "{}"
        DTE.ActiveDocument.Selection.LineUp()
        DTE.ExecuteCommand("Edit.BreakLine")
        DTE.UndoContext.Close()
    End Sub
End Module

Finally, bind a keystroke to the macro and you’ll be able to create test actions very quickly.

Read Full Post »

This is a repeatable Test Driven Development coding exercise that can be used to hone your test-first, red-green-refactor programming skills.

Adder

This adder allows you to add two integers together via a limited interface:

  • void SetValue(int value) – sets the value of the default register
  • int GetValue() – returns the value in the default register
  • void MakeOtherRegisterDefault() – makes the alternate register the default; the previous default
    register becomes the alternate
  • void Add() – sums the values of the default and alternate registers into the default register

Implement support for each method and remember to refactor between tests if necessary.

You may find the following use cases useful. Start each with a new Adder.

  • single instruction
    • GetValue() – should return 0
  • two instructions
    • Add() then GetValue() – should return 0
    • MakeOtherRegisterDefault() then GetValue() – should return 0
    • SetValue(10) then GetValue() – should return 10
  • three instructions
    • SetValue(10) then Add() then GetValue() should return 10
    • SetValue(10) then MakeOtherRegisterDefault() then GetValue() – should return 0
    • SetValue(10) then SetValue(20) then GetValue() – should return 20
  • four instructions
    • SetValue(10) then Add() then Add() then GetValue() should return 10
    • SetValue(10) then Add() then MakeOtherRegisterDefault() then GetValue() should return 0
    • SetValue(10) then MakeOtherRegisterDefault() then Add() then GetValue() should return 10
    • SetValue(10) then MakeOtherRegisterDefault() then MakeOtherRegisterDefault() then GetValue() should return 10
  • five instructions
    • SetValue(10) then Add() then MakeOtherRegisterDefault() then Add() then GetValue() should return 10
    • SetValue(10) then MakeOtherRegisterDefault() then Add() then Add() then GetValue() should return 20
    • SetValue(10) then MakeOtherRegisterDefault() then SetValue(5) then Add() then GetValue() should return 15

The final use case is the standard one that will be used when adding two numbers together e.g. 10 + 5:

  1. SetValue(10)
  2. MakeOtherRegisterDefault()
  3. SetValue(5)
  4. Add()
  5. GetValue()

Implementation variations to consider:

  • make default and alternate separate fields
  • use an int array to store default and alternate
  • use a Stack to store default and alternate

Read Full Post »

A response to this StackOverflow question, reproduced here:

What I want my final code to be on the class board is something of the form:

public class Board
{
    private Color[,] board;

    public Board(int x, int y)
    {
        board = new Color[x, y];
    }

    public void SetColorAt(int x, int y, Color color) {
        board[x, y] = color;
    }

    public Color GetColorAt(int x, int y) {
        return board[x, y];
    }
}
The question is... how to get there?

Start with a high level description of what you want to implement.

  • A square board with rows and columns.
  • Each board position should have a color.
  • A board user should be able to set the color of a specific board position (pixel).
  • A board user should be able to get the color of a specific board position.
  • etc.

Next, use small tests to drive out the implementation. Sometimes it is easier to start with boundary conditions.

    When asked to get the color at a specific board position
    - given a default board, and
      - the row value is less than zero
      - should throw argument exception

    When asked to get the color at a specific board position
    - given a default board, and
      - the row value is greater than the highest board row
      - should throw argument exception

“the row value is greater than the highest board row” forces you to have some way to set the highest board row. The test doesn’t care whether you set it via the constructor or a property setter.

    When constructed with board dimensions
     - should set the highest board row

“should set the highest board row” forces you to have some way to access the value that was set. Perhaps a property getter.

    When asked to get the color at a specific board position
    - given a default board, and
      - the column value is less than zero
      - should throw argument exception

    When asked to get the color at a specific board position
    - given a default board, and
      - the column value is greater than the highest board column
      - should throw argument exception

“the column value is greater than the highest board column” forces you to duplicate the highest row solution for the highest column.

    When constructed with board dimensions
     - should set the highest board column

etc.

    When asked to get the color at a specific board position
    - given a default board, and
      - the row value is within the board space, and
      - the column is within the board space
      - should return the default color

“should return the default color” forces you to expose the default color somewhere. This shouldn’t be a magic value that only the test knows about. Expose it as a const or read only value on Board.

    When asked to get the color at a specific board position
    - given a default board, and
      - the row value is within the board space, and
      - the column is within the board space, and
      - the requested position has a known color
      - should return the color of the board at the requested position

“the requested position has a known color” forces you to build out the ability to set the color of a board position. You can do that now because you have a failing test for getting the color at a position. So set that aside and build out the setter.

    When asked to SET the color at a specific board position
    - given a default board, and
      - the row value is less than zero
      - should throw argument exception

    When asked to set the color at a specific board position
    - given a default board, and
      - the row value is greater than the highest board row
      - should throw argument exception

    When asked to set the color at a specific board position
    - given a default board, and
      - the column value is less than zero
      - should throw argument exception

    When asked to set the color at a specific board position
    - given a default board, and
      - the column value is greater than the highest board column
      - should throw argument exception

    When asked to set the color at a specific board position
    - given a default board, and
      - the row value is within the board space, and
      - the column is within the board space
      - should set the color at the given position to the requested color

“should set the color at the given position to the requested color” uses your get implementation to verify the value was set correctly. Once you’ve implemented it correctly all your tests will be green again.

Just continue to build out additional functionality one small piece at a time.

When you approach the test in implementation-agnostic terms like this you can change the implementation to use IBoard or Ruby or whatever and the test descriptions don’t have to change. You’ll have to change some test implementation details but the stated goals of the tests don’t have to change.

Read Full Post »

Older Posts »

%d bloggers like this: