Tag Archives: Testing

How to initialise data concisely in C++

In the past, creating a collection of dates was a chore, because you had to individually insert them into a container (e.g. declaring a vector on one line and then pushing dates into it on subsequent lines). With features like std::initializer_list from C++11 onwards, it’s now much easier to do this concisely.

Here’s some simple, concise code to create dates without all the hassle:

struct Date
{
    std::string Event;

    int Year;
    int Month;
    int Day;
};

void print( const Date& date )
{
    std::cout << date.Event << ": "<< date.Year << "/" << date.Month << "/" << date.Day << "\n";
}

void print( const std::vector<Date>& dates )
{
    for ( auto date : dates )
    {
        print( date );
    }
}

void test()
{
    std::cout << "Print date:\n";
    print( { "Today", 2015, 5, 5 } );

    std::cout << "Print dates:\n";
    print( {
        { "Christmas", 2015, 12, 25 },
        { "Spring Bank Holiday", 2016, 6, 30 }
           } );
}

This style is particularly useful when writing tests – you can write a whole test, including setting up the data, on a single line (or at least, in a single function call).

Another compelling use case comes when creating test cases for graph algorithms. Suppose you have the following data structures for an undirected, weighted graph:

struct Edge
{
    const size_t end1;
    const size_t end2;
    const size_t cost;
};

struct Graph
{
    size_t source;
    size_t nodes;
    std::vector<Edge> edges;
};

Then creating a test graph to pass into an algorithm is as simple as:

shortest_path( { 0, 4, { {0,1,24}, {0,3,20}, {2,0,3}, {3,2,12} } })

Leave a comment

Filed under C++, C++ Code, Programming

How to efficiently find the n’th biggest element in a collection

Looking at std::nth_element the other day, I noticed that it’s complexity is O(n) for a collection of size n, and wondered how that was achieved. A basic implementation of an algorithm to find the ith-biggest element might start by sorting the collection and index to the ith afterwards – complexity O(n*log(n)):

int ith_element_by_sorting( std::vector<int> input, int i )
{
    std::sort( std::begin(input), std::end(input) );
    return input[i];
}

It’s a small step to realise then that you don’t need to sort all n elements of the collection – only the first i elements, so complexity O(n*log(i)):

int ith_element_by_partial_sort( std::vector<int> input, int i )
{
    std::partial_sort( std::begin( input ), std::begin( input ) + i + 1, std::end( input ) );
    return input[i];
}

But the real trick is that you don’t need to do any sorting at all. That’s the approach taken by quickselect, which is the selection sibling to quicksort, and achieves O(n) complexity on average:

int partition( std::vector<int>& values, int left, int right, int pivot )
{
     auto pivotValue = values[ pivot ];

     std::swap( values[pivot], values[right] ); // Move pivot to end
     auto store_pos = left;

     for ( int j = left; j < right; ++j )
     {
         if ( values[j] < pivotValue )
         {
             std::swap( values[ store_pos ], values[j] );
             ++store_pos;
         }
     }

     std::swap( values[right], values[ store_pos ] );  // Move pivot to its final place

     return store_pos;
}

int quickselect( std::vector<int> values, int left, int right, int i )
{
    // Unordered - no need to sort values at all, 
    // instead we recursively partition only the subset of values
    // containing the i'th element, until we have either
    // a) trivial subset of 1
    // b) pivot is moved to exactly the location we wanted 
    while( 1 )
    {
         if ( left == right )
         {
             return values[left];
         }

         // Pick a pivot from middle of values.
         // Better options are a random pivot or median of 3
         auto pivot = (left + right)/2; 

         // Move anything smaller than values[pivot] to the left of pivot,
         // and return updated position of pivot
         pivot = partition( values, left, right, pivot );

         if ( pivot == i )
         {
             return values[i];
         }
         else if ( i < pivot )
         {
             right = pivot - 1;
         }
         else
         {
             left = pivot + 1;
         }
    }
}

int ith_element_by_quickselect( const std::vector<int>& input, int i )
{
    return quickselect( input, 0, input.size()-1, i );
}

int ith_element( const std::vector<int>& input, int i )
{
    if ( i < 0 || i >= input.size() )
    {
        std::ostringstream ss;
        ss << "Input '" << i << "' outside range [0," << input.size() << ")";
        throw std::out_of_range( ss.str() );
    }

    return ith_element_by_quickselect( input, i );
}

Here’s some test code to check that the implementation works:

template <typename F, typename T>
void should_be( T t, F f, const std::string& message )
{
    try
    {
        std::ostringstream ss;

        auto got = f();
        if ( got != t )
        {
            ss << message << " got " << got << ", expected " << t;
            throw std::runtime_error( ss.str() );
        }
        else
        {
            ss << "OK: " << message << ": got " << got;
            std::cout << ss.str() << "\n";
        }
    }
    catch( const std::exception& ex )
    {
        // Report error if either f() threw or we found unexpected value
        std::cout << "ERROR: " << ex.what() << "\n";
    }
}

template <typename F>
void should_throw( F f, const std::string& message )
{
    try
    {
        f();
    }
    catch( const std::exception& ex )
    {
        std::cout << "OK: " << message << ": threw \"" << ex.what() << "\"\n";
        return;
    }

    std::cout << "ERROR: " << message << " should have thrown\n";
}

#define SHOULD_BE( t, expr ) should_be( t, [](){ return expr; }, #expr )
#define SHOULD_THROW( expr ) should_throw( [](){ expr; }, #expr )

void testIthElement()
{
    SHOULD_THROW( ith_element( {}, 0 ) );
    SHOULD_THROW( ith_element( {1,2}, -1 ) );
    SHOULD_THROW( ith_element( {1,2,3}, 3 ) );

    SHOULD_BE( 1, ith_element( {1}, 0 ) );
    SHOULD_BE( 0, ith_element( {0,1,2,3,4,5,6,7,8}, 0 ) );
    SHOULD_BE( 2, ith_element( {0,1,2,3,4,5,6,7,8}, 2 ) );
    SHOULD_BE( 6, ith_element( {5,4,7,6,1,2,0,8,3}, 6 ) );
    SHOULD_BE( 8, ith_element( {5,4,7,6,1,2,0,8,3}, 8 ) );
    SHOULD_BE( 5, ith_element( {5,5,5,5,5,5}, 1 ) );
}

Here’s the output:
QuickSelect

In fact, reviewing old posts on this blog, I found this link that dates back to 2013, when std::nth_element was only required by the standard to have worst-case O(N^2) complexity, with O(N) on average – precisely what you’d get from quickselect. Now though, thanks to introselect, O(N) is possible.

Leave a comment

Filed under C++, C++ Code, Programming

Software bug causes prisoners’ early release

BBC News reports that 3200 US prisoners were released early over a 13 year period due to a software bug.  It’s hard to fathom how this could have been released in the first place, how it remained undetected for so long, and finally why it’s taken so long to fix.

The bug miscalculated the sentence reductions prisoners in Washington state had received for good behaviour.  It was introduced in 2002 as part of an update that followed a court ruling about applying good behaviour credits.

Ok, we know that there’s always room for mis-interpretation of requirements when developing software, and every program needs some period of user acceptance testing.

The Washington Department of Corrections (DoC) added that it was made aware of the problem in 2012 when the family of one victim found out that the offender was getting out too early.

Huh? It took ten years for someone to notice? The average mis-calculation was 49 days and a maximum of 600 days – and it wasn’t noticed? What sort of testing did they do – surely some worked examples were provided?

Despite this, the faulty software was not corrected until a new IT boss for the DoC was appointed, who realised how serious the problem had become.

This is the crux of the matter – if you’re writing mission-critical software, you have to test accordingly. Here, prisoners released early may have committed further crimes – that’s a hefty penalty that could have been avoided by professional software practices: code reviews, test coverage analysis, user acceptance testing.  Surely some regression data tests existed when they were releasing the upgrade – someone must have signed off that all these differences were fine “because the rules have changed”.  Yes, but not by that much!

Mr Inslee said he had ordered the DoC to fix the software as quickly as possible.   An update that applies the correct formula for calculating sentence cuts is due to be in place by 7 January.

Let’s hope they’ve thoroughly reviewed their test coverage now and that the release goes smoothly.  Also, they should review any other software developed by the same team in that 2002 period, it’s unlikely to be an isolated mistake.

 

Leave a comment

Filed under Musing, Programming

ACCU: Testing Times

CVu264CoverPete Goodliffe wrote this excellent article (login to ACCU may be required) on how to test software. It’s a decent summary on types of test, who should write them, when to write them, what to test and suitable test frameworks. Anyone looking for a robust argument for why effective testing is vital should refer to this.

Leave a comment

Filed under Programming

How to generate tests under GTest

One of the many features provided by GTest is the ability to generate test at runtime. One useful application of this is that you can execute data-driven testing by obtaining a list of test file names, then generating a test for each of them. It’s actually very simple to do this in GTest – they call these value-parameterized tests (see documentation). Here’s a snippet of code to demonstrate how little overhead is involved:

#include <gtest/gtest.h>

using namespace testing;

// placeholder - could be used for test setup/cleanup
class MyTest : public ::testing::TestWithParam<std::string>
{
};

TEST_P( MyTest, IntegrationTest )
{
    std::string test_file_name = GetParam();

    // open file and run the integration test
}

std::vector<std::string> test_file_names();

INSTANTIATE_TEST_CASE_P( MyLibraryName, MyTest, test::ValuesIn( test_file_names() ) );

On one hand, this approach isn’t really in the spirit of unit test – data-driven tests have a habit of quickly escalating to integration tests between libraries. However, such integration tests also have their place in a testing strategy, and this is a neat way to accomplish it with minimal overhead.

1 Comment

Filed under C++, C++ Code, Programming

How to Integrate GTest into Visual Studio 2010

I’m using GTest for C++ unit tests and have found a neat way to integrate this into Visual Studio 2010. It’s very low-tech, but works pretty well – see http://stackoverflow.com/questions/6414788/how-can-i-add-a-custom-command-to-visual-studio

  • Go to Tools | External Tools… to add the command line running your GTest executable
  • In the dialog, browse to your command, add the command line arguments, and be sure to select “Use Output window”
  • Count up the external tools to identify the index of your new one (starting at one, not zero)
  • Create/customize a toolbar – click “Add Command” and pick your new tool under category Tools, External Commands 1,2,3 … n
  • Edit the name using “Modify Selection”

That’s it! Now, your command runs inside Visual Studio and writes into the output window. Even better, if there’s a test failure that includes the source location, you can double-click on it to go to that line in the editor.

1 Comment

Filed under C++, Programming

Unit Testing with GTest and GMock

In recent years, I’ve found myself writing less user interface code and more server code (typically COM servers that are exercised on client workstations or on nodes in a compute farm). Given the lack of a UI for driving and testing the code (excepting spreadsheets), automated tests are vital to achieve a high degree of code coverage.
The Art Of Unit Testing
Given that I’ve been doing this for years now, I was surprised to learn that I haven’t been writing unit tests, as I previously supposed. According to The Art of Unit Testing, the tests I’ve been writing are typically interaction tests. These are useful too, but unless a component can be tested in isolation with tests that run without delay due to network/database interaction, it isn’t a unit test.

Since reading the book, I’ve adopted the Google Test framework for both writing unit tests and implementing mock objects to accompany the tests. Without a good library for writing mock objects, you’re dragged straight back in to writing tests that call other objects in your library. With GMock, you can easily create mock objects and inject behaviour into them in order to test your server code in various scenarios. Using GTest and GMock is easy – just call RUN_ALL_TESTS() in main, and the framework discovers all the unit test you’ve written and launches them:

#include "gmock\gmock.h"
using namespace testing;

// Start writing unit tests here!

int _tmain(int argc, _TCHAR* argv[])
{
    ::InitGoogleMock( &amp;argc, argv );
    return RUN_ALL_TESTS();
}

Here’s a simple example that defines a WeatherStation interface and a UserInterface class. We wish to test the UserInterface, but the weather station isn’t written yet – so we define a MockWeatherStation, and set up tests to invoke the UserInterface in different situations:

#include "gmock\gmock.h"

#include <iostream>
#include <list>
#include <memory>

class WeatherStation
{
public:
    virtual ~WeatherStation(){};

    typedef enum
    {
        North, South, East, West
    } Direction;

    typedef enum
    {
        Optimistic, Pessimistic
    } Outlook;

    // NB Semantics on wind deliberately ugly to show a neat feature in gmock
    virtual void wind( Direction* pDirection, double* strength ) const = 0;
    virtual double rainfall() const = 0;
    virtual std::string prediction( Outlook outlook ) const = 0;
};

class UserInterface
{
public:
    UserInterface( const std::shared_ptr<WeatherStation>& weather_station ) :
        weather_station_( weather_station )
    {
    }

    typedef enum
    {
        Heavy, Medium, Light
    } Range;

    Range rain()
    {
        auto rainfall = weather_station_->rainfall();
        if ( 0.0 <= rainfall && rainfall < 2.0 ) return Light;
        else if ( 2.0 <= rainfall && rainfall < 4.0 ) return Medium;
        else return Heavy;
    }

    Range wind()
    {
        WeatherStation::Direction direction;
        double strength;
        weather_station_->wind( &direction, &strength );

        if ( 0.0 <= strength && strength < 5.0 ) return Light;
        else if ( 5.0 <= strength && strength < 10.0 ) return Medium;
        else return Heavy;
    }

    std::pair<std::string, std::string> predict_range()
    {
        return std::make_pair( 
            weather_station_->prediction( WeatherStation::Optimistic ),
            weather_station_->prediction( WeatherStation::Pessimistic ) );
    }

private:
    std::shared_ptr<WeatherStation> weather_station_;
};

using namespace testing;

class MockWeatherStation : public WeatherStation
{
public:
    MOCK_CONST_METHOD0( rainfall, double() );
    MOCK_CONST_METHOD2( wind, void(WeatherStation::Direction*, double*) );
    MOCK_CONST_METHOD1( prediction, std::string( WeatherStation::Outlook ) );
};

TEST( WeatherStationUserInterface, rain_should_be_heavy )
{
    auto weather_station = std::make_shared<MockWeatherStation>();
    // GMock: specify a simple return value using Return(x)
    EXPECT_CALL( *weather_station, rainfall() )
        .WillOnce( Return(5.0) );
    UserInterface ui( weather_station );
    EXPECT_EQ( UserInterface::Heavy, ui.rain() );
}

TEST( WeatherStationUserInterface, wind_should_be_light )
{
    auto weather_station = std::make_shared<MockWeatherStation>();
    // GMock: specify out parameter values using SetArgPointee
    EXPECT_CALL( *weather_station, wind(_,_) )
        .WillOnce( DoAll( SetArgPointee<0>( WeatherStation::North ),
                          SetArgPointee<1>( 0.5 )) );
    UserInterface ui( weather_station );
    EXPECT_EQ( UserInterface::Light, ui.wind() );
}

TEST( WeatherStationUserInterface, predictions_are_displayed )
{
    auto weather_station = std::make_shared<MockWeatherStation>();
    // GMock: inject more complex logic using C++11 lambdas,
    // and pattern match on the input value
    EXPECT_CALL( *weather_station, prediction(WeatherStation::Optimistic) )
        .WillOnce( Invoke( []( WeatherStation::Outlook _ ) -> std::string
            {
                return "Sunny";
            }) );
    EXPECT_CALL( *weather_station, prediction(WeatherStation::Pessimistic) )
        .WillOnce( Invoke( []( WeatherStation::Outlook _ ) -> std::string
            {
                return "Overcast";
            }) );

    UserInterface ui( weather_station );
    auto predicted_range = ui.predict_range();
    EXPECT_EQ( "Sunny", predicted_range.first );
    EXPECT_EQ( "Overcast", predicted_range.second );
}

When you run the executable, it’s easy to spot if the tests pass or fail:
WeatherStationOutput

As a bonus, Visual Studio 2012 has neat integration for GoogleTest:
WeatherStation

See also

4 Comments

Filed under C++, C++ Code, Programming