Solving a Puzzle with Spring

Standard

Introduction

Spring

Spring uses the Inversion of Control (IoC) pattern. There are many ways to do IoC. From what I can tell (please comment if I am entirely wrong) is that instead of creating the objects yourself, you have someone else do it for you. For example, EJB lookups with EJB 2.1 (You can still do this in EJB 3.1), the server gives you an instance of the object you want. Spring creates the objects for you through a BeanFactory or an ApplicationContext. The other pattern that gets thrown around in reference to Spring is Dependency Injection (DI). Many times IoC and DI can be interchangeable. The main thrust of DI is that to make objects as decoupled as possible. This happens by injecting the objects to an object rather than the object creating them. Spring uses a configuration file so it can know what beans it can inject. If a bean has a property with setters, the property can be set in the configuration. Here is an example of a property being set.

Randy

One can also populate a java collection like a java.util.List or java.util.Map. These are beyond the scope of this article. For now, one should know that a spring bean’s property can be set.

Puzzle

There are many puzzle books out there but the one I have is Dr. Ecco’s Cyberpuzzles by Dennis E. Shasha. I am up to puzzle number 2. The puzzles are given as stories with the puzzle changing throughout the story. There are many points in the story where the reader is challenged to solve the puzzle before going on. What is interesting from a software development perspective is that the requirements while changing are well defined. This makes it ideal for writing programs that can do the boring work for you while thinking about the solution.

The puzzle we are going to solve deals with Monopoles. In the story the person with the Jordan Tyler is talking to Dr. Ecco and his niece Liane. Jordan explains that they are going to ship monopoles into space for a mission. The company that makes the monopoles makes 52 kinds. Monopoles have interesting properties. They bind three kind at a time. Once bound, they are forever bound. If the conditions to bond do not exist, the monopoles neither attract nor repel each other. The formula for what monopoles will bind is x + y = z. For example, monopoles 1,2 and 3 will bond together as will 5, 3 and 8. For the purposes of the mission, bonded monopoles are worthless. They have discovered that a barrier of tungsten will block the attraction of monopoles that would normally bond together. The company launching the monopoles into space doesn’t want to fill their ship with a rare metal. The challenge is what is the smallest number of containers that can hold all 52 monopoles types without any of them bonding together.

Example

Model

Monopole types are going to be modeled as integers. I could create a monopole class and define a function that returns the type number but that would be an int. Monopoles will be held in Chambers. Chambers will know if a monopole can be added or not and will not allow a monopole that will bind to other monopoles to be added. Chambers will be inside Ships. Ships will know if a monopole can be held by querying its chambers. A ship can have chambers added if there is not enough to hold all 52 types.

Interfaces

In the interest of keeping dependencies low, I decided to make a couple of interfaces, one for Ship and one for Chamber.

Ship.java:
package ship;

import java.util.List;

import chamber.Chamber;

public interface Ship {

public void addMonopole(int monopole);

public boolean canAddMonopole(int monopole);

public void addChamber(Chamber chamber);

public List getChambers();

public int getNumChambers();

public void reset();

public String toString();

}
Noticed that I have addChamber() with a parameter of Chamber. This is so the dependency can be injected by the ApplicationContext. Normally, I would have the Ship create the Chamber internally. The reset method is to clear the chambers of their monopoles in preparation for another try.

Chamber’s interface is next:
package chamber;

import java.util.List;

public interface Chamber {

public void addMonopole(int monopole);

public boolean canAddMonopole(int monopole);

public int numMonopoles();

public List getMonopoles();

public void clear();

public boolean isEmpty();

public String toString();

}
This is a pretty simple interface. Basically, it is a list with a simpler interface. The canAddMonopole method is what prevents monopoles that would bond outside the chamber.

Chamber Implementation

Chambers do two things, hold monopoles and prevent monopoles from bonding. My solution to the problem is found below.

LinkedListChamber.java:
package chamber;

import java.util.Collections;

import java.util.HashSet;

import java.util.LinkedList;

import java.util.List;

import java.util.Set;

public class LinkedListChamber implements Chamber {

private List monopoles;

private Set monopoleTypeCache;

public LinkedListChamber() {

monopoles = new LinkedList();

monopoleTypeCache = new HashSet();

}

@Override

public void addMonopole(int monopole) {

if(monopole < 1 || monopole > 52) {

throw new IllegalArgumentException(“the range for monopole is 1 to 52”);

}

if(canAddMonopole(monopole)) {

addToCache(monopole);

monopoles.add(monopole);

}

}

@Override

public boolean canAddMonopole(int monopole) {

return !monopoleTypeCache.contains(new Integer(monopole));

}

@Override

public int numMonopoles() {

return monopoles.size();

}

@Override

public List getMonopoles() {

return Collections.unmodifiableList(monopoles);

}

@Override

public void clear() {

monopoles.clear();

monopoleTypeCache.clear();

}

@Override

public boolean isEmpty() {

return monopoles.isEmpty();

}

@Override

public String toString() {

return “LinkedListChamberImpl{” + “monopoles=” + monopoles + “}”;

}

private void addToCache(int monopole) {

List temp = new LinkedList();

for(int m: monopoles){

temp.add(m + monopole);

}

monopoleTypeCache.addAll(temp);

}

}
As one can see, there are two data structures keeping track of the monopoles. The first one is a java.util.List. This holds the monopoles. The other structure is a java.util.Set that holds the possible monopoles that would bond to two other monopoles held in the chamber if added. Entries are added before the monopole is entered.

Ship Implementation

A ship places the monopoles into chambers. The way that it does this affects how many chambers are needed to hold all 52 monopoles. I created three ways the chambers are filled. All but one method was common among them so I extracted an abstract class and extended it three times. Here is the AbstractShip class.

AbstractShip.java:
package ship;

import java.util.ArrayList;

import java.util.Collections;

import java.util.List;

import chamber.Chamber;

abstract class AbstractShip implements Ship {

protected List chambers = new ArrayList();

public void addChamber(Chamber chamber) {

if (chamber == null) {

throw new NullPointerException(“chamber is null”);

}

chambers.add(chamber);

}

@Override

public abstract void addMonopole(int monopole);

@Override

public boolean canAddMonopole(int monopole) {

boolean canAdd = false;

for (Chamber c : chambers) {

if (c.canAddMonopole(monopole)) {

canAdd = true;

break;

}

}

return canAdd;

}

@Override

public List getChambers() {

return Collections.unmodifiableList(chambers);

}

@Override

public int getNumChambers() {

return chambers.size();

}

@Override

public void reset() {

for (Chamber c : chambers) {

c.clear();

}

}

@Override

public String toString() {

return “Ship{” + “chambers=” + chambers + ‘}’;

}

}
As one can see, the abstract class just implements everything but one method, addMonopole(). Here is my first attempt at placing all of the monopoles, FirstChamberShip.

FirstChamberShip.java:
package ship;

import java.util.ArrayList;

import java.util.Collections;

import java.util.List;

import chamber.Chamber;

public class FirstChamberShip extends AbstractShip {

@Override

public void addMonopole(int monopole) {

if(canAddMonopole(monopole)) {

for(Chamber c: chambers) {

if(c.canAddMonopole(monopole)){

c.addMonopole(monopole);

break;

}

}

}

}

}
This ship just places the monopole in the first chamber that can hold the monopole. I did two more types of ships to see how low I could get the chamber count. The lowest I could get it to was four. The other two ship classes can be found at http://darylmathisonblog.googlecode.com/svn/trunk/Monopole/src/ship/MaxChamberShip.java and http://darylmathisonblog.googlecode.com/svn/trunk/Monopole/src/ship/MinChamberShip.java.

Factories

Whenever I use interfaces, I normally want to use a factory to hide the implementation. This involves making a singleton and defining a method that returns the instance of the class you want. Then if I want to have a more dynamic factory, I need to define a property that tells the factory what class to create. If this sounds like a pain, it is a pain. What would happen if one could create a factory in a line of xml? What if one could define a factory that could instantiate several different classes all by just setting a property in an XML file? Both of those factories are possible in Spring.

DI depends on factories. The dependency is injected in from an outside source. Spring implementing DI creates objects via its BeanFactory or its ApplicationContext. The basic line of code that uses a spring injection is like this:
chamber = cxt.getBean(“chamber”, Chamber.class);
The object is created by Spring, not by using new. By default, all beans are singletons. Imagine that, every time the above line is called the same object is returned. This can be used everywhere a singleton is needed. The line in the configuration file that creates the bean is:

There it is, a factory that creates a singleton. As long as one uses the same id or name, the same instance is returned. This would be a problem for adding chambers to a ship. There in effect would be only one chamber! The Spring framework has an attribute in the bean tag named “scope.” There are several types of scopes, the majority of them are used for web applications. The ones that I am interested in are singleton (default) and prototype. The prototype scope creates a different instance every time one injects the bean. This is ideal for adding new chambers into a ship. The configuration line is this:

The only change is adding the scope and setting it to prototype. This way does not depend on anything that is specific to Spring. This trick can be used in other IoC frameworks. There is a Spring factory interface. It is named org.springframework.beans.factory.FactoryBean. Requires the three methods to be implemented:
public <? > getObject() throws Exception;

public Class<?> getObjectType();

public boolean isSingleton();
There is another interface that I used and that is org.springframework.beans.factory.InitializingBean. This defines the method that is called after a property is set. The method is:
public void afterPropertiesSet() throws Exception;
To configure Spring to use a FactoryBean one uses the factory class at the class attribute. An example is below:

This line configures Spring to call the factory when the ApplicationContext is called to inject firstChamberShip. One can add properties to the factory to make it create different beans. As one can tell from the above example line, I used a factory bean to create the different types of ships. I created an enum class to choose which one is created. Here is the class:
package ship;

public enum ShipType {

FIRSTCOME,

LARGEST,

SMALLEST;

}
I created the property shipType and set in the configuration file. Here is the full factory bean class that I made to create the different ships.
package ship;

import org.springframework.beans.factory.FactoryBean;

import org.springframework.beans.factory.InitializingBean;

public class ShipFactory implements FactoryBean, InitializingBean{

private Ship ship;

private ShipType shipType = ShipType.FIRSTCOME;

@Override

public Ship getObject() throws Exception {

return ship;

}

@Override

public Class<?> getObjectType() {

return Ship.class;

}

@Override

public boolean isSingleton() {

return true;

}

@Override

public void afterPropertiesSet() throws Exception {

if(shipType == ShipType.FIRSTCOME){

ship = new FirstChamberShip();

} else if(shipType == ShipType.LARGEST){

ship = new MaxChamberShip();

} else if(shipType == ShipType.SMALLEST) {

ship = new MinChamberShip();

}

}

public void setShipType(ShipType shipType) {

this.shipType = shipType;

}

}
Notice that when after the properties are set, the member attribute ship is set. The FirstChamberShip is the default ship type for the factory.

Here is the full configuration file that defines the different beans used in the program.

LARGEST

SMALLEST

This is a simple configuration file. All it does is define four beans, one with a prototype scope and three using a FactoryBean.

Putting It All Together

This would not be a fair if I did not show how it all fits together in one place. To show how it all works, here is the main class, monopole.Monopole:
package monopole;

import chamber.Chamber;

import ship.Ship;

import org.springframework.context.ApplicationContext;

import org.springframework.context.support.GenericXmlApplicationContext;

public class Monopole {

public static void main(String[] args) {

ApplicationContext cxt =

new GenericXmlApplicationContext(“classpath:swing/monopole.xml”);

Ship maxShip = cxt.getBean(“maxChamberShip”, Ship.class);

Ship firstShip = cxt.getBean(“firstChamberShip”, Ship.class);

Ship minShip = cxt.getBean(“minChamberShip”, Ship.class);

run(firstShip, cxt);

run(maxShip, cxt);

run(minShip, cxt);

}

public static void run(Ship ship, ApplicationContext cxt) {

int numOfMono = 0;

Chamber chamber = cxt.getBean(“chamber”, Chamber.class);

ship.addChamber(chamber);

while (numOfMono < 52 && ship.getNumChambers() < 52){

for(int i = 1; i <= 52; i++) {

if (ship.canAddMonopole(i)){

numOfMono++;

ship.addMonopole(i);

} else {

numOfMono = 0;

chamber = cxt.getBean(“chamber”, Chamber.class);

ship.addChamber(chamber);

ship.reset();

break;

}

}

}

System.out.println(“largest num ” + numOfMono + ” with “

+ ship.getNumChambers() + ” chambers”);

System.out.println(ship);

}

}
The ships are defined then run is called to put them through their paces. Ships are given one chamber at first and seen if they can load all of the monopoles. If they cannot load all of the monopoles, they print out how many they could and how many chambers. If the number of chambers is greater than 52 then the number of chambers and what is in the chambers are printed out.

The source code project can be found at https://github.com/darylmathison/monopole-example. I used Netbeans 7.3 to develop the source code.

Conclusion

A puzzle was used to feature the different factory styles that can be done in the Spring Framework. One style is the standard bean definition. It can be customized to create different instances or a singleton. The other way is to create a FactoryBean. When using a FactoryBean, the class attribute of the bean definition is the FactoryBean. A property can be added to have different beans coming out of the same FactoryBean. Using both of these styles, I was able to test three different solutions to the monopole puzzle. I was able to only use four chambers to store all 52 monopoles.

References

  • Ho, Clarence and Harrop, Rob. Pro Spring 3. New York:Springer Science+Business Media, 2012. Print
  • Shasha, Dennis E. Doctor Ecco’s Cyberpuzzles. New York:W.W. Norton & Company, Inc. 2002. Print
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s