title: Refactoring Fun - Prime Numbers
body: <p>From Uncle Bob's book Clean Code (example was in Java, so this was my first java translation), I've been playing with the refactoring example on prime numbers.  </p>
  
  <p>The question is:   How would you refactor the following code? </p>
  
  <p>There are 4 versions here:  UglyVersion :-) , BobVersion, PeteVersion, PeteVersionClassMember.  I'm doing this for fun, and hope you enjoy too :-)</p>
  
  <pre><code>class ProgramBad
  {
      static void Main()
      {
          int[] result = GeneratePrimes.generatePrimes(30);
          foreach (var i in result)
              Console.Write(i.ToString() + ", ");
      }
  }
  
  /// &lt;summary&gt;
  /// 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
  /// &lt;/summary&gt;
  public class GeneratePrimes
  {
      public static int[] generatePrimes(int maxValue)
      {
          if (maxValue &gt;= 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 &lt; s; i++)
              {
                  f[i] = true;
              }
  
              // get rid of non-primes
              f[0] = f[1] = false;
  
              //sieve
              int j;
              for (i = 2; i &lt; Math.Sqrt(s) + 1; i++)
              {
                  if (f[i]) // if i is uncrossed, cross its multiples
                  {
                      for (j = 2 * i; j &lt; s; j += i)
                          f[j] = false; // multiple is not a prime
                  }
              }
  
              // how many primes are there?
              int count = 0;
              for (i = 0; i &lt; 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&lt;s ; i++)
              {
                  if (f[i])
                      primes[j++] = i;
              }
  
              return primes; // return the primes
          } else // maxvalue &lt; 2
              return new int[0]; // return null array if bad input
      }
  }
  </code></pre>
  
  <p>Bob's refactored version:</p>
  
  <pre><code>class ProgramBob
      {
          static void Main()
          {
              int[] result = PrimeGeneratorBob.generatePrimes(30);
              foreach (var i in result)
                  Console.Write(i + ", ");
          }
      }
  
      /// &lt;summary&gt;
      /// 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
      /// &lt;/summary&gt;
      class PrimeGeneratorBob
      {
          static bool[] crossedOut;
          static int[] result;
  
          static public int[] generatePrimes(int maxValue)
          {
              if (maxValue &lt; 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 &lt; 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 &lt;= 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 &lt; 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 &lt; crossedOut.Length; i++)
                  if (notCrossed(i))
                      result[j++] = i;
          }
  
          static int numberOfUncrossedIntegers()
          {
              int count = 0;
              for (int i = 2; i &lt; crossedOut.Length; i++)
                  if (notCrossed(i))
                      count++;
              return count;
          }
      }
  </code></pre>
  
  <p>What I like about this is:</p>
  
  <ul>
  <li>How easy it is to get an overall feeling of how the program works eg
  uncrossIntegersUpTo(maxValue);
  crossOutMultiples();
  putUncrossedIntegersIntoResult();</li>
  </ul>
  
  <p>I paired with a friend over the weekend, and we came up with this version:</p>
  
  <pre><code>class PetesRefactored
  {
      static void MainPete()
      {
          PrimeGeneratorPete pg = new PrimeGeneratorPete();
          int[] arrayOfPrimes = pg.generatePrimes(30);
          foreach (int prime in arrayOfPrimes)
              Console.Write(prime + ", ");
      }
  }
  
  /// &lt;summary&gt;
  /// 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
  /// &lt;/summary&gt;
  class PrimeGeneratorPete
  {
      public int[] generatePrimes(int maxValue)
      {
          bool[] crossedOut;
  
          if (maxValue &lt; 2)
              return new int[0];
          else
          {
              crossedOut = new bool[maxValue + 1];
              uncrossIntegersUpTo(crossedOut);
              crossOutMultiples(crossedOut);
              return putUncrossedIntegersIntoResult(crossedOut);
          }
      }
  
      void uncrossIntegersUpTo(bool[] crossedOut)
      {
          for (int i = 2; i &lt; crossedOut.Length; i++) 
              crossedOut[i] = false;
      }
  
      void crossOutMultiples(bool[] crossedOut)
      {
          int limit = determineIterationLimit(crossedOut);
          for (int i = 2; i &lt;= 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 &lt; crossedOut.Length; multiple += i)
              crossedOut[multiple] = true;
      }
  
      int[] putUncrossedIntegersIntoResult(bool[] crossedOut)
      {
          int[] result = new int[numberOfUncrossedIntegers(crossedOut)];
          for (int j = 0, i = 2; i &lt; crossedOut.Length; i++)
              if (!crossedOut[i])
                  result[j++] = i;
          return result;
      }
  
      int numberOfUncrossedIntegers(bool[] crossedOut)
      {
          int count = 0;
          for (int i = 2; i &lt; crossedOut.Length; i++)
              if (!crossedOut[i])
                  count++;
          return count;
      }
  }
  </code></pre>
  
  <p>We:</p>
  
  <ul>
  <li>Initialised crossedOut in generatePrimes method instead of ‘child’ method</li>
  <li>Pass in crossedOut as a parameter instead of a class scope variable</li>
  <li>Took out (defactored), the notCrossed(i) method as !crossedOut[i] is very readable inline.</li>
  <li>Make everything non static</li>
  </ul>
  
  <p>And thanks to Casey and anon.</p>
  
  <p>Here is the code with crossedOut as a class level variable.  I like this as it cuts down on some noise when passing parameters into methods.</p>
  
  <pre><code>class PrimeGeneratorPeteClassMember
  {
      bool[] crossedOut;
  
      public int[] generatePrimes(int maxValue)
      {
          if (maxValue &lt; 2)
              return new int[0];
          else
          {
              crossedOut = new bool[maxValue + 1];
              uncrossIntegersUpTo();
              crossOutMultiples();
              return putUncrossedIntegersIntoResult();
          }
      }
  
      void uncrossIntegersUpTo()
      {
          for (int i = 2; i &lt; crossedOut.Length; i++)
              crossedOut[i] = false;
      }
  
      void crossOutMultiples()
      {
          int limit = determineIterationLimit();
          for (int i = 2; i &lt;= limit; i++)
              if (!crossedOut[i])
                  crossOutMultiplesOf(i);
      }
  
      int determineIterationLimit()
      {
          double iterationLimit = Math.Sqrt(crossedOut.Length);
          return (int)iterationLimit;
      }
  
      void crossOutMultiplesOf(int i)
      {
          for (int multiple = 2 * i; multiple &lt; crossedOut.Length; multiple += i)
              crossedOut[multiple] = true;
      }
  
      int[] putUncrossedIntegersIntoResult()
      {
          int[] result = new int[numberOfUncrossedIntegers()];
          for (int j = 0, i = 2; i &lt; crossedOut.Length; i++)
              if (!crossedOut[i])
                  result[j++] = i;
          return result;
      }
  
      int numberOfUncrossedIntegers()
      {
          int count = 0;
          for (int i = 2; i &lt; crossedOut.Length; i++)
              if (!crossedOut[i])
                  count++;
          return count;
      }
  }
  </code></pre>