ProgramGood.Net - Clean Code by Uncle Bob

Prime Number Refactoring

Dave Mateer — Mon, 08 Feb 2010 00:40:09 GMT

From Uncle Bobs book clean code example on refactoring:

        static void Main()

            int[]
result = GeneratePrimes.generatePrimes(30);

            foreach (var
i in result)

                Console.Write(i.ToString() + ",
");

    ///
<summary>

    ///
Given an array of integers starting at 2, cross out the multiples of 2. Fine the next

    ///
uncrossed integer, and cross out all of its multiples.

    ///
Repeat until you have passed the square root of the maximum value

    ///
</summary>

    public class GeneratePrimes

class Program

        public static int[]
generatePrimes(int maxValue)

            if (maxValue
>= 2) // the only valid case

                //
declarations

                int s
= maxValue + 1; // size of the array

                bool[]
f = new bool[s];

                int i;

                //
initialize array to be true

                for (i
= 0; i < s; i++)

                    f[i] = true;

                //
get rid of non-primes

                f[0] = f[1] = false;

                //sieve

                int j;

                for (i
= 2; i < Math.Sqrt(s) + 1; i++)

                    if (f[i]) //
if i is uncrossed, cross its multiples

                        for (j
= 2 * i; j < s; j += i)

                            f[j] = false; //
multiple is not a 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])

                        primes[j++] = i;

                return primes; //
return the primes

            } else //
maxvalue < 2

                return new int[0]; //
return null array if bad input

This is messy code because:

Variable names are cryptic
Some comments are unnecessary

Here is Bob’s refactored version:

///
<summary>

    ///
Generates prime number up to a user specified maximum

    ///
The algorithm used is the Sieve of Eratosthenes.

    ///
Given an array of integers starting at 2:

    ///
Find the first uncrossed (eg 3 ) integer, and cross out all its multiples (eg 6,9,12,14)

    ///
Repeat until there are no more multipes in the array

    ///
</summary>

    class PrimeGenerator

        static bool[]
crossedOut;

        static int[]
result;

        public static int[]
generatePrimes(int maxValue)

            if (maxValue
< 2)

                return new int[0];

            else

                uncrossIntegersUpTo(maxValue);

                crossOutMultiples();

                putUncrossedIntegersIntoResult();

                return result;

        static void uncrossIntegersUpTo(int maxValue)

            crossedOut = new bool[maxValue
+ 1]; // as bool array starts at 0, and if maxvalue =
10, we need an array of length 11

            for (int i
= 2; i < crossedOut.Length; i++) // less than as we
don't want to reference crossedOut[4] which doesn't exist

                crossedOut[i] = false;

        static void crossOutMultiples()

            int limit
= determineIterationLimit();

            for (int i
= 2; i <= limit; i++)

                if (notCrossed(i))

                    crossOutMultiplesOf(i);

        static int determineIterationLimit()

            //
Every multiple in the array has a prime factor that

            //
is less than or equal to the square root of the array size,

            //
which is the largest number we are trying to find primes in.

            //
So we don't have to cross out numbers

            //
larger than that square root of the maxnumber, as they will have been crossed out
already

            double iterationLimit
= Math.Sqrt(crossedOut.Length);

            return (int)
iterationLimit;

        static void crossOutMultiplesOf(int i)

            for (int multiple
= 2 * i; multiple < crossedOut.Length; multiple += i)

                crossedOut[multiple] = true;

        static bool notCrossed(int i)

            return crossedOut[i]
== false;

        static void putUncrossedIntegersIntoResult()

            result = new int[numberOfUncrossedIntegers()];

            for (int j
= 0, i = 2; i < crossedOut.Length; i++)

                if (notCrossed(i))

                    result[j++] = i;

        static int numberOfUncrossedIntegers()

            int count
= 0;

            for (int i
= 2; i < crossedOut.Length; i++)

                if (notCrossed(i))

                    count++;

            return count;

I like Bobs version because it splits the code into simple manageable chunks eg:

uncrossIntegersUpTo(maxValue);
crossOutMultiples();
putUncrossedIntegersIntoResult();

I paired with a friend over the weekend, and we thought this was better:

Initialised crossedOut in generatePrimes method instead of ‘child’ method
Pass in crossedOut as a parameter instead of a class scope variable
Took out (defactored), the notCrossed(i) method as !crossedOut[i] is very readable inline.
Make everything non static
Keep in /// summary method so intellisense works in the IDE – am trialling Ghostdoc.

///
<summary>

    ///
Generates prime number up to a user specified maximum

    ///
The algorithm used is the Sieve of Eratosthenes.

    ///
Given an array of integers starting at 2:

    ///
Find the first uncrossed (eg 3 ) integer, and cross out all its multiples (eg 6,9,12,14)

    ///
Repeat until there are no more multipes in the array

    ///
</summary>

    class PrimeGenerator

        public int[]
generatePrimes(int maxValue)

            bool[]
crossedOut;

            if (maxValue
< 2)

                return new int[0];

            else

                crossedOut = new bool[maxValue
+ 1];

                uncrossIntegersUpTo(crossedOut);

                crossOutMultiples(crossedOut);

                return putUncrossedIntegersIntoResult(crossedOut);

        void uncrossIntegersUpTo(bool[]
crossedOut)

            //
as bool array starts at 0, and if maxvalue = 10, we need an array of length 11

            for (int i
= 2; i < crossedOut.Length; i++) // less than as we
don't want to reference crossedOut[4] which doesn't exist

                crossedOut[i] = false;

        void crossOutMultiples(bool[]
crossedOut)

            int limit
= determineIterationLimit(crossedOut);

            for (int i
= 2; i <= limit; i++)

                if (!crossedOut[i])

                    crossOutMultiplesOf(crossedOut, i);

        int determineIterationLimit(bool[]
crossedOut)

            //
Every multiple in the array has a prime factor that

            //
is less than or equal to the square root of the array size,

            //
which is the largest number we are trying to find primes in.

            //
So we don't have to cross out numbers

            //
larger than that square root of the maxnumber, as they will have been crossed out
already

            double iterationLimit
= Math.Sqrt(crossedOut.Length);

            return (int)
iterationLimit;

        void crossOutMultiplesOf(bool[]
crossedOut, int i)

            for (int multiple
= 2*i; multiple < crossedOut.Length; multiple += i)

                crossedOut[multiple] = true;

        int[]
putUncrossedIntegersIntoResult(bool[] crossedOut)

            int[]
result = new int[numberOfUncrossedIntegers(crossedOut)];

            for (int j
= 0, i = 2; i < crossedOut.Length; i++)

                if (!crossedOut[i])

                    result[j++] = i;

            return result;

        int numberOfUncrossedIntegers(bool[]
crossedOut)

            int count
= 0;

            for (int i
= 2; i < crossedOut.Length; i++)

                if (!crossedOut[i])

                    count++;

            return count;

Clean Code by Uncle Bob

Dave Mateer — Sun, 07 Feb 2010 23:33:26 GMT

http://www.amazon.com/Clean-Code-Handbook-Software-Craftsmanship/dp/0132350882

My notes below on Bobs book.. also need next article on refactoring PrimeNumber code.

We need 'Clean Code' because otherwise it can bring a company to its knees
As messy code builds up, productivity decreases

What is clean code?
Elegant, Efficient, Does one thing well, Simple, crisp abstractions, Has Unit Tests, Meaningful Names, minimal dependencies, Clear, no duplication, minimal number of entities, What you expect, beautiful

Make code easy to read

Boy Scout Rule: Leave the campground cleaner than you found it... same for code.. leave it cleaner than you found it

Dave's Simplest Refactoring List
** change one variable name for the better
** break up a function thats a bit too large
** eliminate one small bit of duplication
** clean up a composite if statement

SRP - Single Responsibility Principle
OCP - Open Closed Principle
L
I
DIP - Dependency Inversion Principle

DRY - Don't repeat yourself

2. Meaningful Names

intention revealing names
// this is bad!
int d; // elapsed time in days

**// better....What is being measured, and the units
int elapsedTimeInDays;

see c:\development\ch2 Intentional Names.
and ch2 Statistics Message

**Class names - nouns (things), or noun phrases eg PrimeGenerator, WikiPage, Customer, Account, AddressParser.... not a verb (doing) eg manager, data, info

**Method names - verb or very phrases eg GeneratePrimes, postPayment, deletePage

3. Functions

**First rule: they should be small
Second rule: they should be smaller than that!

Do one thing!

** shrink function down.. so one level of abstration per function

TO test..
TO RenderPageWithSetupsAndTeardown, we check to see whether the page is a test page and if so, we include the setups and teardown. In either case we render the page in HTML.

One level of abstraction per function.

4. Comments

Comments are to compensate for our failure to express ourselves in code

eg
// Check to see if the employee is eligible for full benefits
if ((employee.flag && HOURLY_FLAG) && (employee.age > 65))

or
if (employee.isEligibleForFullBenefits())

Dont comment out code :-)

ch4Primes - great to understand at a higher level of abstraction

5. Formatting
important

6. Objects and Data Abstraction

A class does not push its variables out through getters and setters
Rather it exposes abstract interfaces that allow its users to manipulate the essence of the data,
without having to know its implementation.

** am here.. would be good to type in the code again looking at procedural stuff from page 96.
Objects expose behaviour and hide data.
Data Structures expose data and have no significant behaviour.

DTO's - public variables and no functions
Active Records are special forms of DTO's...with public variables... and naviagtaional methods like save and find.

7. Error Handling

8. Boundaries

9. Unit Tests
Very important to keep clean

10. Classes
SRP
Good prime generator example
Open Closed principle

11. Systems
Seperation of main
Factories
Dependency Injection

12. Emergent Design

13. Concurrency

14. Successive Refinement - Case Study - command line parser

15. JUnit internals - Case study (smaller)

16. Refactoring SerialDate

17. Smells and Heuristics
Comments
Environment
Functions
General
Java
Names