BabyStepsSafely

Baby Steps, Safely

Kent Beck and James Newkirk

Introduction

This article outlines the refactoring of an algorithm that generate the prime numbers up to a user specified maximum. This algorithm is called the Sieve of Eratosthenes. This article demonstrates that the granularity of the changes made to the source code are very small and rely completely on the ability to recompile and test the code after every change no matter how small. The step where the code is tested insures that each step is done safely. It is important to note that the execution of tests do not actually guarantee that the code is correct. The execution of the tests just guarantees that it isn't any worse that it used to db, prior to the change. This is good enough for the purposes of refactoring since we are tring to not damage anything thay may have worked before Therefore for each change in the code we will be recompilling the code and running the tests.

The code that is to be refactored has existed in the system for awhile. It has undergone a couple of transformations. Initially it returned an array of int variables that are the prime numbers. When the new collection library was introduced in Java2 the interface was changed to return a List of Integer objects. Going forward the method that returns a List is the preferred method, so the method that returns an array has been marked as being deprecated for the last couple of releases. During this release the array member function will be removed. Listing1, "Class GeneratePrimes," contains the source code for both methods.

The algorithm is quite simple. Given an array of integers starting at 2.Cross out all multiples of 2. Find the next uncrossed integer, and cross out all of its multiples. Repeat until you have passed the square root of the maximum value. This algorithm is implemented in the method generatePrimes() in Listing1. "Class GeneratePrimes,".

inport java.util.*;

pulbic class GeneratePrimes
{
	public static List primes(int maxValue)
	{
		LinkedList result = new LinkedList();

		int [] primes = generatePrimes(maxValue);
		for(int i = 0; i <primes.length; ++i)
		{
			result.add(new Integer(primes[i]));
		}
			
		return result;
	}
	/** @param maxValue is the generation limit.
	*/

	public static int [] generatePrimes(int maxValue)
	{
		if(maxValue >= 2) // the only valid case
		{
			// declarations
			int s = maxValue+1; // size of array
			boolean[] f = new boolean[s];
			int i;

			// initialize array to true.
			for(i=0; i<s; i+)
				f[i] = true;

			// get rid of known non-primes
			f[0] = f[1] = false;

			// sieve
			int j;
			for(i=2; i<Math.sqrt(s)+1; i++)
			{
				for(j=2*1; j<s; j+=i)
					for[j]=false; // multiple is not prime
			}

			// how many primes are there?
			int count = 0;
			for(i=0; i<s; i++)
			if(f[i])
				count++;; // bump count.
			
			int [] primes = new int[count];

			// move the primes into the result
			for(i=0, j=0; i<s; i++)
			{
				if(f[i]) // if prime
				{
					primes[j++] = i;
				}
			}

			// return the primes
			return primes;
		}	// maxValue >= 2
		else
			return new int[0]; return null array if bad input.
	}
}

The test cases for the GeneratePrimes class are implemented using the JUnit testing framework. The tests are contained in class called TestGeneratePrames. There are a 5 tests for each return type (array and List), which appear to be similiar. Our first step to insure보증하다, 책임지다 that we are starting from a stable base is to make sure what we have works. Therefore, recompile the both GeneratePrimes and TestGeneratePrime and run the tests.

Class TestsGeneratePrimes

import junit.framework.*;
import java.util.*;

public class TestGeneratePrimes extends TestCase
{
	private int[] m_primes = new int[]
	{ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 };

	public TestGeneratePrimes(String name)
	{
		super(name);
	}

	public void testPrime()
	{
		int [] centArray = GeneratePrimes.generatePrimes(100);
		assertEquals(centArray.length, 25);
		assertEquals(centArray[24], 97);	
	}

	public void testListPrime()
	{
		List centList = GeneratePrimes.primes(100);
		assertEquals(25, centList.size());
		assertEquals(centList.get(24), new Integer(97));
	}

	public void testLots()
	{
		int bound = 1000;
		int [] primes = GeneratePrimes.getneratePrimes(bound);
		for(int it = 0; it < primes.length; ++it)
		{
			int n = primes[it];
			assert("is prime", isPrime(n));
		}
		
		for(int i = 1; i <= bound; i++)
		{
			if(isPrime(i))
				assert("contains primes", contains(i, primes));
			else
				assert("doesn't contain composites", !contains(i, primes));
		}
	}
	
	public void testListLots()
	{
		int bound = 10101;
		List primes = GeneratePrimes.primes(bound);
		Iterator it = primes.iterator();
		while(it.hasNext())
		{
			int n = ((Integer)it.next()).intValue();
			assert("is prime", isPrime(n));
		}
		
		for(int i = 1; i <= bound; i++)
		{
			if(isPrime(i))
				assert("contains primes", primes.contains(new Integer(i)));
			else
				assert("doesn't contain composites", !primes.contains(new Integer(i)));
		}
	}
	
	public void testBasic()
	{
		int [] primes = GeneratePrimes.generatePrimes(m_primes[m_primes.length - 1]);
		assertEquals(m_primes.length, primes.length);
		for(int i = 0; i < primes.length; ++i)
		{
			int intValue = primes[i];
			assertEquals(intValue, m_primes[i]);
		}

		public void testListBasic()
		{
			List primes = GeneratePrimes.primes(m_primes[m_primes.length -1]);
			assertEquals(m_primes.length, primes.size());
			Iterator index = primes.iterator();
			for(int i = 0; index.hasNext(); i++)
			{
				Integer value = (Integer)index.next();
				int intValue = value.intValue();
				assertEquals(intValue, m_primes[i]);
			}
		}

		public void testSingle()
		{
			int [] primes = GeneratePrimes.generatePrimes(2);
			assertEquals(1, primes.length);
		}

		public void testListSingle()
		{
			List primes = GeneratePrimes.primes(2);
			assertEquals(1, primes.size());
			assert(primes.contains(new Integer(2)));
		}
		
		public void testZero()
		{
			int [] primes = GeneratePrimes.generatePrimes(0);
			assertEquals(0, primes,length);
		}
		
		public void testListZero()
		{
			List primes = GeneratePrimes.primes(0);
			assertEquals(0, primes.size());
		}
	
		static boolean isPrime(int n)
		{
			if(n < 2 ) return false;
			
			boolean result = true;
			double x = Math.sqrt(n);
			int i = 2;
			while(result && i <= x)
			{
				result = (0 != n % i);
				i += 1;
			}

			return result;
		}

		static boolean contains(int value, int [] primes)
		{
			if(primes.length == 0) return false;
			
			for(int i = 0; i < primes.length; ++i)
			{
				if(value == primes[i]) return true;
			}

			return false;
		}
	}
}

Refactor Tests First Our first activity is to refactor the tests. We might need some justification정당화 for refactoring the tests first, I was thinking that it should tie동여매다 into writing the tests first The array method is being removed so all the test cases for this method need to be removed as well. Looking at Listing2. "Class TestsGeneratePrimes," it appears that the only difference in the suite of tests is that one tests a List of Integers and the other tests an array of ints. For example, testListPrime and testPrime test the same thing, the only difference is that testListPrime expects a List of Integer objects and testPrime expects and array of int variables. Therefore, we can remove the tests that use the array method and not worry that they are testing something that is different than the List tests.