Step 0

Step 1

Step 2

Step 3

I just switched to CppUTest 2.0 and something I noticed is that if you use <vector> or other std-based classes, you need to make sure to include those first before including <CppUTest/TestHarness.h>. This is because CppUTest overloads new and delete, which causes havoc with the std-based classes. No big deal, I just made sure to include that file as the last header (rather than the first, which is what I used to do).

RunAllTests.cpp

1
2
3
4
5

#include <CppUTest/CommandLineTestRunner.h>

int main(int argc, char** argv) {
  CommandLineTestRunner::RunAllTests(argc, argv);
}

BowlingScoreCardTest.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

#include "BowlingScoreCard.h"

#include <CppUTest/TestHarness.h>

TEST_GROUP(BowlingScoreCard) {
  BowlingScoreCard* card;

  TEST_SETUP() {
    card = new BowlingScoreCard;
  }

  TEST_TEARDOWN() {
    delete card;
  }

  void throwOne(int value) {
      card->recordThrow(value);
  }

  void throwMany(int rolls, int value) {
    for(int i = 0; i < rolls; ++i)
      throwOne(value);
  }

  void confirmScoreIs(int expected) {
    LONGS_EQUAL(expected, card->score());
  }
};

TEST(BowlingScoreCard, noRollsGame) {
  confirmScoreIs(0);
}

TEST(BowlingScoreCard, throwAll0s) {
  throwMany(20, 0);
  confirmScoreIs(0);
}

TEST(BowlingScoreCard, throwAll1s) {
  throwMany(20, 1);
  confirmScoreIs(20);
}

TEST(BowlingScoreCard, throwOneSpare) {
  throwOne(7);
  throwOne(3);
  throwOne(6);
  throwMany(17, 0);
  confirmScoreIs(22);
}

TEST(BowlingScoreCard, all5sthrown) {
  throwMany(21, 5);
  confirmScoreIs(150);
}

TEST(BowlingScoreCard, throwOneStrike) {
  throwOne(10);
  throwOne(4);
  throwOne(3);
  confirmScoreIs(24);
}

TEST(BowlingScoreCard, perfectGame) {
  throwMany(12, 10);
  confirmScoreIs(300);
}

TEST(BowlingScoreCard, dutch200StrikeSpare) {
  for(int i = 0; i < 10; ++i) {
    throwOne(10);
    throwMany(2, 5);
  }
  throwOne(10);
  confirmScoreIs(200);
}

TEST(BowlingScoreCard, dutch200SpareStrike) {
  for(int i = 0; i < 10; ++i) {
    throwMany(2, 5);
    throwOne(10);
  }
  throwMany(2, 5);
  confirmScoreIs(200);
}

BowlingScoreCard.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#pragma once

#ifndef BOWLING_SCORE_CARD_H
#define BOWLING_SCORE_CARD_H

#include <vector>
using namespace std;

class BowlingScoreCard
{
public:
  enum { Frames = 10, Mark = 10 };

  BowlingScoreCard();
  virtual ~BowlingScoreCard();
  int score();
  void recordThrow(int roll);

private:
  typedef vector<int> v_int;
  typedef v_int::size_type size_type;

  int scoreFrameAt(size_type index);
  int nextTwoRollsSummed(size_type index);
  int scoreAt(size_type index);
  int frameSizeAt(size_type index);
  bool isStrikeAt(size_type index);
  bool isSpareAt(size_type index);
  int scoreStrikeAt(size_type index);
  int scoreSpareAt(size_type index);

  v_int rolls;
};

#endif

BowlingScoreCard.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

#include "BowlingScoreCard.h"

BowlingScoreCard::BowlingScoreCard() {
}

BowlingScoreCard::~BowlingScoreCard() {
}

int BowlingScoreCard::score() {
  int score = 0;

  for(int index = 0, frame = 0; frame < Frames; ++frame) {
    score += scoreFrameAt(index);
    index += frameSizeAt(index);
  }

  return score;
}

int BowlingScoreCard::scoreFrameAt(size_type index) {
  if(isStrikeAt(index))
    return scoreStrikeAt(index);
  else if(isSpareAt(index))
    return scoreSpareAt(index);

  return nextTwoRollsSummed(index);
}

bool BowlingScoreCard::isStrikeAt(size_type index) {
  return scoreAt(index) == Mark;
}

bool BowlingScoreCard::isSpareAt(size_type index) {
  return !isStrikeAt(index) && nextTwoRollsSummed(index) == Mark;
}

int BowlingScoreCard::scoreStrikeAt(size_type index) {
  return Mark + nextTwoRollsSummed(index + 1);
}

int BowlingScoreCard::scoreSpareAt(size_type index) {
  return Mark + scoreAt(index + 2);
}

int BowlingScoreCard::frameSizeAt(size_type index) {
  if(scoreAt(index) == Mark)
    return 1;
  return 2;
}

int BowlingScoreCard::nextTwoRollsSummed(size_type index) {
  return scoreAt(index) + scoreAt(index + 1);
}

int BowlingScoreCard::scoreAt(size_type index) {
  return index < rolls.size() ? rolls[index] : 0;
}

void BowlingScoreCard::recordThrow(int roll) {
  rolls.push_back(roll);
}

I sure do miss refactoring tools!-)

• Forth
• Operator precedence
• Operator associativity
• L-Values and R-Values
• Directed Acyclic Graphis
• In-fix, pre-fix, post-fix binary tree traversal
• Abstract Syntax Trees (AST)
• The list goes on, I’m a big-time extrovert, so I told Chad to occasionally tell me to shut the heck up

• 1 + 3 becomes 1 3 +
• a = b = 17 becomes a b 17 = =
• 2 + 3 * 5 becomes 2 3 5 * +
• 2 * 3 + 5 becomes 2 3 * 5 +

One typical approach to this problem is to develop an AST from the in-fix representation and then recursively traversing the AST using a recursive post-fix traversal.

What I like about he Shunting Yard Algorithm is it takes a traditionally recursive algorithm (DAG traversal, where a binary tree is a degenerate DAG) and writes it iteratively using it’s own stack (local or instance variable) storage versus using the program stack to store activation records (OK stack frames). Essentially, the local stack is used for pending work.

This is one of those things I think is a useful skill to learn: writing traditionally recursive algorithms using a stack-based approach. This allows you to step through something (think iteration) versus having to do things whole-hog (recursively, with a block (lambda) passed in). In fact, I bought a used algorithm book 20 years ago because it had a second on this subject. And looking over my left shoulder, I just saw that book. Nice.

To illustrate, here’s the AST for the first example:

Since the group had not done a lot with recursive algorithms (at least not recently), we discussed a short hand way to remember the various traversal algorithms using three letters: L, R, P

• L -> Go Left
• R -> Go Right
• P -> Print (or process)

• in-fix, in -> in between -> L P R
• pre-fix, pre, before -> P L R
• post-fix, post, after -> L R P

• in-fix: Go left, you hit the 1, it’s a leaf note so print it, go up to the +, print it, go to the right, you end up with 1 + 3
• post-fix: Go left you hit the 1, it’s a leaf node, print it, go back to the +, since this is post-fix, don’t print yet, go to the right, you get the 3, it’s a leaf node, print it, then finally print the +, giving: 1 3 +
• pre-fix: start at + and print it, then go left, it’s a leaf note, print it, go right, it’s a leaf node, print it, so you get: + 1 3 – which looks like a function call (think operator+(1, 3))

It’s not quite this simple – we actually looked at larger examples – but this gets the essence across. And to move from a tree to a DAG, simply iterate over all children, printing before or after the complete iteration; in-fix doesn’t make as much sense in a general DAG. We also discussed tracking the visited nodes if you’ve got a graph versus an acyclic graph.

After we got a multi-operator expression with same-precedence operators working, e.g., 1 + 3 – 2, which results in: 1 3 + 2 -, we moved on to handling different operator precedence.

Around this time, there was some skepticism that post-fix could represent the same expression as in-fix. This is normal, if you have not seen these kinds of representations. And let’s be frank, how often do most of us deal with these kinds of things? Not often.

Also, there was another question: WHY?

In a nutshell, with a post-fix notation, you do not need parentheses. As soon as an operator is encountered, you can immediately process it rather than waiting until the next token to complete the operator (no look-ahead required). This also led to HP developing a calculator in 1967 (or ‘68) that was < 50 pounds and around USD $5,000 that could add, subtract, multiply and divide, which was huge at the time (with a stack size of 3 – later models went to a stack size of 4, giving us the x, y, z and t registers).

During this rat-hole, we discussed associativity. For example, a = b = c is really (a = (b = c))

That’s because the assignment operator is right-associative. This lead into r-values and l-values.

• The driver finishes by writing a new failing test.
• The driver commits the code with the newest failing test (we’ll be using git)
• Change drivers and give him/her some time-box (5 – 10 minutes)
• If, at the end of the current time-box, the current driver has all tests passing, go back to the first bullet in this list.
• If at the end, the same test that was failing is still failing, (fist time only) give them a bit more time.
• However, if any other tests are failing, then we revert back to the last check in and switch drivers.

Here’s an approximation of these rules using yuml.me:

(start)->(Create New Failing Test)->(Commit Work)->(Change Drivers)
(Change Drivers)->(Driver Working)
(Driver Working)-><d1>[tick]->(Driver Working)
<d1>[alarm]->(Check Results)->([All Tests Passing])->(Create New Failing Test)
(Check Results)->([Driver Broke Stuff])->(git -reset hard)->(Change Drivers)
(Check Results)->([First Time Only and Still Only Newest Test Failing])->(Give Driver A Touch More Time)->(Check Results)

Note that this is not a strict activity diagram, the feature is still in beta, and creating this diagram as I did made the results a bit more readable. Even so, I like this tool so I wanted to throw another example in there (and try out this diagram type I have not used before – at least not with this tool, I’ve created too many activity diagrams). If you’d like to see an accurate activity diagram, post a comment and I’ll draw one in Visio and post it.

Anyway, we’re going to try to move to a weekly informal practice session with either bi-weekly or monthly “formal” meetings. We’ll keep switching out the language and the tools. I’m even tempted to do design sessions – NO CODING?! What?! Why not. Some people still work that way, so it’s good to be able to work in different modes.

If you’re in Oklahoma City, hope to see you. If not, and I’m in your town, I’d be interested in dropping into your dojos!

Interested? First the ground rules, then the problem and the starting code. This is Java. However, if someone responds in another language, that’s cool. I might try and follow up, but you’re welcome to do so yourself. I can imagine having multiple threads going on at the same time. (If you’d like your own language thread, ask and I’ll post another blog entry for that particular language.)

Ground Rules

• Follow the three rules of TDD + Refactoring.
• Fix the one failing test.
• Add one to three more tests before posting.
• Make sure you leave one and only one failing test for the next person to fix. (Meaning you can add two passing tests but leave a third test failing, or you can just add one failing test).
• You can/should refactor the test code and the production code
• If you feel a test is wrong, you may change it, but be prepared to justify it.
• I’ll serve as the customer, so I get to define what is “correct” – however, I can be argued with and I can lose arguments (see some of my other blog postings for evidence).
• Feel free to respond with comments/suggestions rather than additional tests.
• Feel free to apply refactorings like extract method, rename, split loop, ... Keep the code clean!

The Problem

The Start

• <typo:code>, and </typo:code>
• <pre>, and </pre>

InfixToPostfixConverterTest

package com.om.example;

import static org.junit.Assert.assertEquals;

import java.util.ArrayList;
import java.util.Collection;

import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.Parameterized;
import org.junit.runners.Parameterized.Parameters;

@RunWith(Parameterized.class)
public class InfixToPostfixConverterTest {
   private final String infix;
   private final String expectedPostfix;

   @Parameters
   public static Collection<String[]> data() {
      ArrayList<String[]> values = new ArrayList<String[]>();

      addTestCase(values, null, "");
      addTestCase(values, "", "");
      addTestCase(values, "45", "45");
      addTestCase(values, "+", "+");
      addTestCase(values, "3 + 8", "3 8 +");

      return values;
   }

   private static void addTestCase(ArrayList<String[]> values, String infix,
         String expectedPostfix) {
      values.add(new String[] { infix, expectedPostfix });
   }

   public InfixToPostfixConverterTest(String infix, String expectedPostfix) {
      this.infix = infix;
      this.expectedPostfix = expectedPostfix;
   }

   @Test
   public void checkTranslation() {
      InfixToPostfixConverter converter = new InfixToPostfixConverter();
      String result = converter.translate(infix);

      assertEquals(expectedPostfix, result);
   }
}

InfixToPostfixConverter

package com.om.example;

public class InfixToPostfixConverter {
   public String translate(String string) {
      if(null == string)
         return "";

      return string;
   }
}

So is that true? Is using a continuous test execution tool as different from not using one as using TDD is from not testing? I’m not sure I’m there yet. However, I will say my brain is having some difficulty getting used to the cool feedback.

Here are two recent experiences I had using it.

Classpath Issues

• I directly edited the .classpath file in Eclipse
• Saved what I was doing
• Waited about a second
• Noticed the new stack trace
• Found the next jar file I needed to add
• Repeat until tests passed.

Might sound like a bit of overkill, but in the end I built a classpath from scratch and I ended up adding 13 jar files. So it saved some time.

Note, I wasn’t looking for this. I had only installed Infinitest the day before so this was unexpected and welcome! Oh, and before my @Before method was handling the exception properly, Infinitest showed that the code had a problem (it was in the @After with a null pointer exception), which it indicated as an error like a syntax error or a validation error. Nice!

Using Mockito

Next, I updated my test to use the @Mock annotation. I removed the hand-written initialization and immediately I noticed a “syntax” error – null pointer exception. I was immediately (OK 1 second later) showed the impact of removing a single line of code. I added the missing line to auto-initialize the @Mock annotated fields but I did it incorrectly, so the error remained. I finally got the line correct and the “syntax error” went away.

Observations

I was also about as skeptical that moving to TDD from being Test Infected was useful. I was wrong. History tends to repeat itself, so I’m guessing, based on my initial resistance, that this is the future.

Embrace it.

This first DoJo is with C#, though I hope we manage to use several languages over time. I’d like to sneak in Smalltalk as soon as we have enough of a critical mass so we don’t lose people. I also plan to slowly introduce BDD (maybe not so slowly, who knows – depends on the group).

The recent refactoring exercises (here and here), they come from this problem. We’ll be starting from scratch, so you can probably imagine that those refactoring examples are not going to come up right away (actually probably not at all given the time).

So your challenge this time is not one of refactoring but rather one of an initial value problem. Given the problem statement, how would you go about starting it? I’m assuming TDD, do you make that same assumption? If so, what’s your first test? Your first few tests? What features do you try to tackle first? What questions do you ask yourself about the problem?

• Test Driven Development
• refactoring (lower case r deliberate – can you guess why?)
• Refactoring to Design Patterns
• Most of the SOLID principles

Anyway, how would you go about starting this problem? Or better yet, give it a try and post your first few tests (in the order you create them).

I’ll be interested in seeing how people start and I’ll compare it to what I’ve done (hint, I use this as a class-driven thing, so I’m pretty flexible on how to start it).

p.s. As a result of studying the manual for my HP 32SII, I have a much better understanding of just how its stack works. I have a EE and CS background, so the stack implementation makes sense, but I left some of its details out of the problem.

When TDDing, I see info on using interfaces, but how do interfaces get created through TDD? How do you unit test your way to an interface?

Interfaces and TDD

• You have some existing code that has a concrete dependency on something and you want to remove that relationship.
• You are working on new production code, taking a mockist approach and you want to create an object, inject dependencies represented by test-doubles that implement interfaces that do not yet exist.

@GBGames goes on to write (remember, this was in Twitter, so I left the abbreviations and such as is):

Game uses HardwareLayer. HL used libSDL but don’t need SDL for unit tests so I wanted IHL for a mockHL. But how to get IHL? Most info I find assumes interface exists or class exists to extract interface. I feel like I’m trying to do 2 things at once.

This additional information suggests something like the following:

@GBGames suggests using an IHardwareLayer to fully get rid of libSDL, which is a fine approach. Another approach is testing the HardwareLayer directly (with unit tests on the HardwareLayer) and passing in an adapter to libSDL (basically an ILibSdl):

What are we Testing?

When using TDD to test a class that depends on an interface that does not yet exist, how do you go about doing that?

• What methods exist in the interface
• How will the class under test use that interface.

• Create interfaces
• Add methods to those interfaces needed to add functionality
• Set expectations on the use of those interfaces

• The Hardware layer, apparently, does not yet exist.
• By extension, the interface does not yet exist.
• When writing the real hardware layer class, it will ultimately have to implement all of the methods in the interface created while TDDing the game class
• Writing the actual hardware layer class will require TDDing it, and passing in an ILibSDL class. This is not strictly necessary, but if you want to test the HardwareLayer without using the real lib SDL, that’s your best option.

Now to get more concrete

• Creating a game properly initializes the hardware layer
• Creating a game properly acquires some kind of game configuration information, which is used to configure the hardware layer (e.g., preferred resolution, color depth, anti-aliasing, ...) (Do you see that even these two test categories actually suggest more than just two classes if you consider the single responsibility principle.)

This is enough to start to express my intent. Almost time to start with something.

• One assertion per test?
• TDD or BDD (At the very lest, looks like we’re staring outside in)
• ...

Test 1: Initializing

package com.om.example.gameandhw;

import static org.mockito.Mockito.mock;
import static org.mockito.Mockito.times;
import static org.mockito.Mockito.verify;

import org.junit.Test;

public class GameTest {
  @Test
  public void itShouldInitializeHardwareLayerDringGameConstruction() {
    IHardwareLayer layer = mock(IHardwareLayer.class);
    new Game(layer);
    verify(layer, times(1)).setResolution(1024, 768);
    verify(layer, times(1)).setColorDepth(8);
  }
}

• On the first line, I had to create and interface IHardwareLayer, no methods.
• On the first line, I also had to stop to statically import the mock method.
• On the second line I had to stop and create the Game class.
• On the second line I had to stop and add a constructor with a parameter (the injected IHardwareLayer, for which I use the Mockito library to create a test-double, which I am using as a Spy)
• On the third line I had to stop to add the method setResolution to the IHardwareLayer interface.
• On the third line I had to stop to add the static import of the verify method.
• On the fourth line I had to stop to add the setColorDepth method to the IHardwareLayer interface.

(Trust me, it too much longer to type that list than to do the work. The actual work was well under 30 seconds to do all of that.)

package com.om.example.gameandhw;

public interface IHardwareLayer {
  void setResolution(int widthInBits, int heightInBits);
  void setColorDepth(int bitsPerChannel);
}

package com.om.example.gameandhw;

public class Game {
  public Game(IHardwareLayer layer) {
    layer.setResolution(1024, 768);
    layer.setColorDepth(8);
  }
}

Now I have no idea if this is even beginning to make any sense for the original problem. This is where having a pair partner with expertise on the game requirements (and maybe some idea about this libSDL) would greatly help.

Notice, however, that as I try to write the Game class, I am adding methods to the IHardwareLayer class AND figuring out how the game will interact with those methods.

Hope this helps GBGames. I also hope to see some discussion in the comments section.

Brett