Saturday, March 26, 2011

Objectifying Java's Life...

This is the second post in the series which started with "Scala Comes to Life".

As much as I want to jump right to the Scala version of the Java code, I must wait. The Java code needs to be "cleaned up" at least to the point where it's similarity to the Scala code can be detected. And that's going to be a bit challenging as I have little motivation to want to write even more Java code. Alas, it must be done.

So, what needs to be done and in what order? The overall objective (for now) is to refactor the Java code towards the values of OO design, performance, configuration, multi-threading, etc.. This means the design needs to incorporate default immutability to easily enable parallel processing (later).

Frame.java:
In the current version of the code, there are references to boolean[][] content everywhere. This is a problem as arrays in Java are immutable (Sidenote: I sure wish Scala had decided to implement immutable arrays...sure could have save a tonnage of time for code needing to transition from Java to Scala). And if we are going to have default immutability, we need to change that implementation. This exposes that there are actually two problems; A) we have to figure out how to move to immutability and B) an implementation detail has "escaped" encapsulation. So, it appears we have our first strong candidate for a class.

So, we will create the class Frame and it's sole goal is to generate immutability around boolean[][] content. Here is a first pass at the new class in attempt to make it immutable (contain and control access to the array):

package com.blogspot.fromjavatoscala.life.java;

public class Frame {
  private boolean[][] content;
  
  public Frame(boolean [][] content) {
    this.content = content;
  }
  
  public boolean[][] getContent() {
    return this.content;
  }
}

This is a good start as there is no mutator/setter which moves us towards the goal of immutability. However, the accessor/getter is returning the internal array which is a leak in the immutability contract. Why? Any client who called getContent() can then make changes to the array returned and those changes will occur to the original object encapsulated array at this.content.

So, we must change the accessor/getter to return a copy of the array. This is called a defensive copy. The client might not and even probably won't change the contents of the array. However, that's not sufficient if one is needing the level of guaranteed immutibility, especially in a multi-threaded environment. So, the getContent() method now looks like this:

public boolean[][] getContent() {
    return this.content.clone(); //defensive copy
  }

Looks good, right? Well, while it is better, there's still a mutability leak. Can you find it? If you look closely, you will see that content is an array of arrays. While we are now defensively copying the over-all array, we are not also copying the sub-arrays. So, any modifications made to those sub-arrays by an untoward client would leak through to our object. Annoying subtlety, huh?

So, now the code just to return a defensive array just got a bit heavier; i.e. let's add some boilerplate to the boilerplate accessor/getter:

public boolean[][] getContent() {
    boolean[][] result = new boolean[this.content.length][]; //defensive copy
    for (int i = 0, count = result.length; i < count; ++i) {
      result[i] = this.content[i].clone(); //defensive copy
    }
    return result;
  }

Now, we need to also make sure that when the object is created, it is valid. This is also known as checking the invariants in terms of Design By Contract. To do this, we need to verify that the value passed in is valid. After verifying it exists (is not null and has a length greater than 0), we need to verify that it is uniform (all of the sub-arrays have the same length). So, let's add some more boilerplate, this time to the constructor, shall we?:

public Frame(boolean [][] content) {
    if (!(content != null)) {
      throw new NullPointerException("content must not be null");
    }
    if (!(content.length > 0)) {
      throw new IllegalArgumentException("content.length must be greater than 0");
    }
    if (!(content[0] != null)) {
      throw new IllegalArgumentException("content[0] must not be null");
    }
    if (!(content[0].length > 0)) {
      throw new IllegalArgumentException("content[0].length must be greater than 0");
    }
    for (int i = 1, count = content.length; i < count; ++i) {
      if (!(content[i].length == content[0].length)) {
        throw new IllegalArgumentException
            (   "content[" + i + "].length [" + content[i].length
              + "] must be equal to content[0].length [" + content[0].length + "]"
            );
      }
    }
    this.content = content;
  }

We're done, right? Nope! There's one more mutability leak staring us right in the face. Again, can you see it? I didn't initially, either. It's subtle, but it's the final line in constructor above. We are just assigning the reference. That means the caller can still mutate the reference changing our object's state. So, just like we had to defensively copy the accessor/getter, we now have to defensively copy the passed in array. And it's even a bit more difficult than that. Do we copy and THEN check the contents? Or do we check the contents and then copy? If we do the former, we lower (but don't eliminate) our risk profile that the caller will modify it during our copy operation. If we do the latter, it's possible for the caller to modify it into an invalid state right AFTER we have run our validation checks and just BEFORE we make the copy.

Ugh! I feel some more boilerplate coming on. Are arrays really worth this much trouble to get the simple behaviors we need? Rather than clutter the constructor with all the code for a safer (but still not perfectly safe) deep copy of the array, here's a utility method:

private boolean[][] deepCopy(boolean[][] content) {
    boolean[][] result = null;
    if (content != null) {
      synchronized(content) { //do our best to make this as multi-threaded friendly as possible
        result = new boolean[content.length][];
        for (int i = 0, count = content.length; i < count; ++ i) {
          if (content[i] != null)
          {
            synchronized(content[i]) {
              result[i] = content[i].clone();
            }
          }
        }
      }
    }
    return result;
  }

And now we have to modify the constructor so that it is using the copy as opposed to the original provided by the content parameter. Here's what that looks like:

public Frame(boolean [][] content) {
    boolean[][] threadSafeCopy = deepCopy(content);
    if (!(threadSafeCopy != null)) {
      throw new NullPointerException("content must not be null");
    }
    if (!(threadSafeCopy.length > 0)) {
      throw new IllegalArgumentException("content.length must be greater than 0");
    }
    if (!(threadSafeCopy[0] != null)) {
      throw new IllegalArgumentException("content[0] must not be null");
    }
    if (!(threadSafeCopy[0].length > 0)) {
      throw new IllegalArgumentException("content[0].length must be greater than 0");
    }
    for (int i = 1, count = threadSafeCopy.length; i < count; ++i) {
      if (!(threadSafeCopy[i].length == threadSafeCopy[0].length)) {
        throw new IllegalArgumentException
            (   "content[" + i + "].length [" + threadSafeCopy[i].length
              + "] must be equal to content[0].length [" + threadSafeCopy[0].length + "]"
            );
      }
    }
    this.content = threadSafeCopy;
  }

And that completes our creating the basic immutable class for Frame. We can now safely assert that once an instance of Frame has been constructed, like an instance of String, it will remain unchanged for the duration of it's existence. Here's the final version of Frame.java:

package com.blogspot.fromjavatoscala.life.java;

public class Frame {
  private boolean[][] content;
  
  public Frame(boolean [][] content) {
    boolean[][] threadSafeCopy = deepCopy(content);
    if (!(threadSafeCopy != null)) {
      throw new NullPointerException("content must not be null");
    }
    if (!(threadSafeCopy.length > 0)) {
      throw new IllegalArgumentException("content.length must be greater than 0");
    }
    if (!(threadSafeCopy[0] != null)) {
      throw new IllegalArgumentException("content[0] must not be null");
    }
    if (!(threadSafeCopy[0].length > 0)) {
      throw new IllegalArgumentException("content[0].length must be greater than 0");
    }
    for (int i = 1, count = threadSafeCopy.length; i < count; ++i) {
      if (!(threadSafeCopy[i].length == threadSafeCopy[0].length)) {
        throw new IllegalArgumentException
            (   "content[" + i + "].length [" + threadSafeCopy[i].length
              + "] must be equal to content[0].length [" + threadSafeCopy[0].length + "]"
            );
      }
    }
    this.content = threadSafeCopy;
  }
  
  private boolean[][] deepCopy(boolean[][] content) {
    boolean[][] result = null;
    if (content != null) {
      synchronized(content) { //do our best to make this as multi-threaded friendly as possible
        result = new boolean[content.length][];
        for (int i = 0, count = content.length; i < count; ++ i) {
          if (content[i] != null)
          {
            synchronized(content[i]) {
              result[i] = content[i].clone();
            }
          }
        }
      }
    }
    return result;
  }
  
  public boolean[][] getContent() {
    boolean[][] result = new boolean[this.content.length][]; //defensive copy
    for (int i = 0, count = result.length; i < count; ++i) {
      result[i] = this.content[i].clone(); //defensive copy
    }
    return result;
  }
}

Whew! For such a simple notion conceptually, the amount of boilerplate overhead got pretty high very quickly, huh? Onward ho!

FrameFactory.java:
Next up, we need to produce instances of Frame. There are two basic events where a Frame needs to be created; A) establishing an initial state and B) deriving a state from the state of an existing frame (i.e. applying the rules). A typical way to approach this design problem is to use the Factory pattern. A factory is used to control all the instantiations of a class (or set of classes). So, we will create a class called FrameFactory. It will have several methods correlating to these two basic events. Here's the first pass (for the very observant, I will cover the unaddressed Frame.next() method shortly):

package com.blogspot.fromjavatoscala.life.java;

import java.util.Random;

public class FrameFactory {
  public static Frame first(boolean[][] content) {
    return new Frame(content);
  }
  
  public static Frame firstRandom(int width, int height) {
    return firstRandom(width, height, null);
  }
  
  public static Frame firstRandom(int width, int height, Random random) {
    return first(generateRandomContent(width, height, random));
  }
  
  public static Frame next(Frame current) {
    if (!(current != null)) {
      throw new NullPointerException("current must not be null");
    }
    return current.next();
  }
  
  private static boolean[][] generateRandomContent(int width, int height, Random random) {
    if (!(width > 0)) {
      throw new IllegalArgumentException("width must be greater than 0");
    }
    if (!(height > 0)) {
      throw new IllegalArgumentException("width must be greater than 0");
    }
    Random randomToUse = (random != null) ? random : new Random();
    boolean[][] result = new boolean[height][];
    for (int y = 0, yCount = result.length; y < yCount; ++y) {
      result[y] = new boolean[width];
      for (int x = 0, xCount = result[y].length; x < xCount; ++x) {
        result[y][x] = randomToUse.nextBoolean();
      }
    }

    return result;
  }
}


Frame.java - next():
The last touch is to update the class Frame with the next() method, copying and adapting the implementation from FrameVersion1. The full class with the new content looks like this:

package com.blogspot.fromjavatoscala.life.java;

public class Frame {
  private static final int[][] NEIGHBOR_OFFSETS = //{x, y} pairs
      new int[][] {   {-1, -1}, {0, -1}, {1, -1}
                    , {-1,  0},          {1,  0}
                    , {-1,  1}, {0,  1}, {1,  1}
                  };
  
  private boolean[][] content;
  
  public Frame(boolean [][] content) {
    boolean[][] threadSafeCopy = deepCopy(content);
    if (!(threadSafeCopy != null)) {
      throw new NullPointerException("content must not be null");
    }
    if (!(threadSafeCopy.length > 0)) {
      throw new IllegalArgumentException("content.length must be greater than 0");
    }
    if (!(threadSafeCopy[0] != null)) {
      throw new IllegalArgumentException("content[0] must not be null");
    }
    if (!(threadSafeCopy[0].length > 0)) {
      throw new IllegalArgumentException("content[0].length must be greater than 0");
    }
    for (int i = 1, count = threadSafeCopy.length; i < count; ++i) {
      if (!(threadSafeCopy[i].length == threadSafeCopy[0].length)) {
        throw new IllegalArgumentException
            (   "content[" + i + "].length [" + threadSafeCopy[i].length
              + "] must be equal to content[0].length [" + threadSafeCopy[0].length + "]"
            );
      }
    }
    this.content = threadSafeCopy;
  }
  
  private boolean[][] deepCopy(boolean[][] content) {
    boolean[][] result = null;
    if (content != null) {
      synchronized(content) { //do our best to make this as multi-threaded friendly as possible
        result = new boolean[content.length][];
        for (int i = 0, count = content.length; i < count; ++ i) {
          if (content[i] != null)
          {
            synchronized(content[i]) {
              result[i] = content[i].clone();
            }
          }
        }
      }
    }
    return result;
  }
  
  public Frame next() {
    boolean[][] result = new boolean[this.content.length][this.content[0].length];
    //iterate through rows
    for (int y = 0, yCount = this.content.length; y < yCount; ++y) {
      //iterate through columns of particular row
      for (int x = 0, xCount = this.content.length; x < xCount; ++x) {
        result[y][x] = calcState(x, y);
      }
    }
    
    return new Frame(result);
  }
  
  private boolean calcState(int x, int y) {
    boolean result = false;
    
    int neighborsAliveCount = 0;
    for (int i = 0, count = NEIGHBOR_OFFSETS.length; (i < count); ++i) {
      int[] offset = NEIGHBOR_OFFSETS[i];
      if (isAlive(x + offset[0], y + offset[1])) {
        ++neighborsAliveCount;
      }
    }
    boolean self = this.content[y][x];
    if (self && (neighborsAliveCount < 2)) {
      result = false; //live cell dies from aloneness (too few live neighbors)
    } else if (    self 
                && ((neighborsAliveCount == 2) || (neighborsAliveCount == 3))
              ) {
      result = true; //live cell lives (sufficient live neighbors)
    } else if (self && (neighborsAliveCount > 3)) {
      result = false; //live cell dies from overcrowding (too many live neighbors)
    } else if ((!self) && (neighborsAliveCount == 3)) {
      result = true;  //dead cell births (precisely enough neighbors)
    }
    
    return result;
  }
  
  private boolean isAlive(int x, int y) {
    boolean result = false;
    
    if (    (y >= 0) && (y < this.content.length)
         && (x >= 0) && (x < this.content[y].length)
       ) {
      result = this.content[y][x];
    }
    
    return result;
  }

  public boolean[][] getContent() {
    boolean[][] result = new boolean[this.content.length][]; //defensive copy
    for (int i = 0, count = result.length; i < count; ++i) {
      result[i] = this.content[i].clone(); //defensive copy
    }
    return result;
  }
}


Main.java:
The last step is to update the Main class to now refer to our new FrameFactory. The edits here ought to be obvious (and if not, you can observe them in bitbucket.org/Mercurial SCM in the Eclipse workspace):

package com.blogspot.fromjavatoscala.life.java;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class Main {

  public static void main(String[] args) {
    List<String> frames = new ArrayList<String>();
    Frame frame = FrameFactory.firstRandom(25, 25, new Random(0));
    String output = displayFrame(frame.getContent());
    frames.add(output);
    printOutput(0, output);
    boolean finished = false;
    int i = 0;
    while (!finished) {
      frame = frame.next();
      output = displayFrame(frame.getContent());
      finished = frames.contains(output);
      if (!finished) {
        frames.add(output);
        printOutput(i + 1, output);
      }
      ++i;
    }
  }
  private static void printOutput(int tick, String output)
  {
    System.out.println("Tick #" + tick);
    System.out.println(output);
  }
  
  private static String displayFrame(boolean[][] content) {
    String result = "";
    
    for (int y = 0, yCount = content.length; y < yCount; ++y) {
      for (int x = 0, xCount = content.length; x < xCount; ++x) {
        result += (content[y][x] ? "#" : " ");
      }
      result += "\n";
    }
    
    return result;
  }
}

And that's all she wrote. Try it out. The execution results are identical to those of the previous post. The code refactoring to get the Java code closer to an "ideal" state resulted in an almost doubling of the lines of code. This seems pretty consistent with my overall Java coding experience.

The code is located on bitbucket.org/Mercurial SCM as an Eclipse workspace. Don't hesitate to play with it. And I am open to any and all feedback.

What's Next:
My next post ought to be my first post to feature Scala code. I am so looking forward to it while I am simultaneously dreading it. My anticipation comes from the expressive power I can already feel Scala offers (ex: immutability by default). My dread comes from the fear that I will lose my motivation to code in Java ever again. And after 15 years and hundreds of thousands of lines of code with my dearest coding friend, it will be a bittersweet moment to see it begin to fade into my past.

No comments:

Post a Comment