Friday, April 27, 2012

Different ways to calculate Fibonacci number - recursive, dynamic, memorize, and multi-threading

Calculating Fibonacci number is an interesting computer  science problem.

fib (n) = fib (n-1) + fib(n-2).

There are many ways to implement the Fibonacci calculator. Following are Java implementations.


1. Recursion. Looks pretty, just like math formula. Lots of stack frames get created. Expensive to run. Hard to mix with multi-threading
 /**
  * calculate Fibonacci number through Recursion.
  * 
  * Recursion. Looks pretty, just like math formula. Lots of stack frames get created. Expensive to run.
  *   
  * @param number
  * @return
  */
    static long getFibViaRecursion(long number) {
     if (number==0 || number==1)
      return number;
     else 
      return getFibViaRecursion(number-1) + getFibViaRecursion(number-2);
    }

    static void testFibViaRecursion () {
  long start = System.currentTimeMillis();
     System.out.println("getFibViaRecursion(10) - " + getFibViaRecursion(10) );
     System.out.println("getFibViaRecursion(20) - " + getFibViaRecursion(20) );
     System.out.println("getFibViaRecursion(40) - " + getFibViaRecursion(40) );
  long end = System.currentTimeMillis() - start;
  System.out.println("FibViaRecursion took: " + end + "ms");
    }


2. Straight Dynamic. Short in this case, easy to follow, fast.
 /**
  * calculate Fibonacci number with straight forward dynamic method. 
  * 
  * Straight Dynamic. Short in this case, easy to follow, fast.  
  * 
  * @author lei zou
  *
  */
    static long getFibViaDynamic(long number) {
     long val1 = 0;
     long val2 = 1;
     long sum = val1 + val2;
     for (long i=1; i<number; i++) {
      sum = val1 + val2;
      val1 = val2;
      val2 = sum;
     }
     return sum;
    }

    static void testFibViaDynamic () {
  long start = System.currentTimeMillis();
     System.out.println("getFibViaDynamic(10) - " + getFibViaDynamic(10) );
     System.out.println("getFibViaDynamic(20) - " + getFibViaDynamic(20) );
     System.out.println("getFibViaDynamic(50) - " + getFibViaDynamic(50) );
  long end = System.currentTimeMillis() - start;
  System.out.println("testFibViaDynamic took: " + end + "ms");
    }



3. Dynamic memorize with Hashtable - cool, less calculation, higher memory requirement.

    
    static void testDynamicFibViaHashTable () {
  long start = System.currentTimeMillis();
     System.out.println("new DynamicFibViaHashTable().getFib( new Long(10) ) - " + new DynamicFibViaHashTable().getFib( new Long(10) ) );
     System.out.println("new DynamicFibViaHashTable().getFib( new Long(20) ) - " + new DynamicFibViaHashTable().getFib( new Long(20) ) );
     System.out.println("new DynamicFibViaHashTable().getFib( new Long(50) ) - " + new DynamicFibViaHashTable().getFib( new Long(50) ) );
  long end = System.currentTimeMillis() - start;
  System.out.println("testDynamicFibViaHashTable took: " + end + "ms");
    }

    /**
     * 
     * calculate Fibonacci number through memorize (Hashtable)
     * 
     * Dynamic memorize with Hashtable, cool, less calculation, higher memory requirement.     
     * 
     * @author lei zou
     *
     */
 static public class DynamicFibViaHashTable {
  private Hashtable<Long,Long> memorize = new Hashtable<Long,Long>() {
   {
    put(new Long(0),new Long(0));
    put(new Long(1),new Long(1));
   }
  };

     Long getFib(Long number) {

         if (memorize.containsKey(number))  return memorize.get(number); // Return it.
         
         Long val1 = (memorize.containsKey(number-1)) ? memorize.get(number-1) : getFib( number-1);
         Long val2 = (memorize.containsKey(number-2)) ? memorize.get(number-2) : getFib( number-2);

         // The number hasn't been calculated, so let's calculate it.
         Long val = val1+val2;

         // Store the value for later use.
         memorize.put(number, val);
         return val;
     }
 }




4. Dynamic memorize with HashMap - cool, less calculation, higher memory requirement, faster than Hashtable. This is because that Hashtable is synchronized.
 /**
  * calculate Fibonacci number through memorize (HashMap)
  * 
  */
 static void testDynamicFibViaHashMap () {
  long start = System.currentTimeMillis();
     System.out.println("new DynamicFibViaHashMap().getFib( 10 ) - " + new DynamicFibViaHashMap().getFib( 10 ) );
     System.out.println("new DynamicFibViaHashMap().getFib( 20 ) - " + new DynamicFibViaHashMap().getFib( 20 ) );
     System.out.println("new DynamicFibViaHashMap().getFib( 50 ) - " + new DynamicFibViaHashMap().getFib( 50 ) );
  long end = System.currentTimeMillis() - start;
  System.out.println("testDynamicFibViaHashMap took: " + end + "ms");
    }
 
 static public class DynamicFibViaHashMap {

  private Map<Integer, BigInteger> memoize = new HashMap<Integer, BigInteger>();

  public DynamicFibViaHashMap() {
    memoize.put(0, BigInteger.ZERO);
    memoize.put(1, BigInteger.ONE);
  }

  public BigInteger getFib(final int index) {

   if (!memoize.containsKey(index)) {
    BigInteger val1 = memoize.containsKey(index-1) ? memoize.get(index-1) : getFib(index - 1);
    BigInteger val2 = memoize.containsKey(index-2) ? memoize.get(index-2) : getFib(index - 2);
    memoize.put(index, val1.add(val2));
   }

     return memoize.get(index);
    }
 }


5. Dynamic memorize with ConcurrentHashMap in multi-threaded - less calculation, not necessary to speed up the calculation because thread creation is expensive.

 static void testMultiThreadDynamicFib () {
  long start = System.currentTimeMillis();
  MultiThreadDynamicFib proc = new MultiThreadDynamicFib();
     System.out.println("proc.getFib( 10 ) - " + proc.getFib( 10 ) );
     System.out.println("proc.getFib( 20 ) - " + proc.getFib( 20 ) );
     System.out.println("proc.getFib( 50 ) - " + proc.getFib( 50 ) );
     proc.shutDown();
  long end = System.currentTimeMillis() - start;
  System.out.println("testMultiThreadDynamicFib took: " + end + "ms");
    }

 /**
  * calculate Fibonacci number through memorize (ConcurrentHashMap) with multi-threads
  * 
  * @author lei zou
  *
  */
 static public class MultiThreadDynamicFib  {

  private final ExecutorService threads = Executors.newCachedThreadPool();
  
  private ConcurrentHashMap<Integer, BigInteger> memorize = new ConcurrentHashMap<Integer, BigInteger>();

  public void shutDown () {
   threads.shutdown();
  }
  private Callable<BigInteger> createTask (final int index) {
   return new Callable<BigInteger>() {
    @Override
    public BigInteger call() throws Exception {
     return splitFibNumberAtIndex(index);
    }
   };
  }

  public BigInteger getFib(final int index) {
   if (memorize.containsKey(index)) return memorize.get(index);
   
      FutureTask<BigInteger> task = new FutureTask<BigInteger>(createTask(index));
      threads.submit(task);
      BigInteger val =  null;
   while ( val==null && ! task.isDone() ) {
       try {
        val = task.get();
    } catch (InterruptedException e) {
     e.printStackTrace();
    } catch (ExecutionException e) {
     e.printStackTrace();
    } 
      }

   if (val!=null) {
    memorize.putIfAbsent(index, val);
   }
      return val;
     }
  
  public MultiThreadDynamicFib() {
   memorize.put(0, BigInteger.ZERO);
   memorize.put(1, BigInteger.ONE);
  }

  
  public BigInteger splitFibNumberAtIndex(final int index) {

   if (!memorize.containsKey(index)) {
    BigInteger val1 = memorize.containsKey(index-1) ?memorize.get(index-1) :  getFib(index - 1);
    BigInteger val2 = memorize.containsKey(index-2) ?memorize.get(index-2) :  getFib(index - 2);
    memorize.putIfAbsent(index, val1.add(val2));
   }
     return memorize.get(index);
    }
 }
 




Here is the main method:

    public static void main(String [] args) {

     testFibViaDynamic ();
     testFibViaRecursion ();
     testDynamicFibViaHashTable() ;
        testDynamicFibViaHashMap ();     
        testMultiThreadDynamicFib ();
    }

getFibViaDynamic(10) - 55
getFibViaDynamic(20) - 6765
getFibViaDynamic(50) - 12586269025
testFibViaDynamic took: 1ms

getFibViaRecursion(10) - 55
getFibViaRecursion(20) - 6765
getFibViaRecursion(40) - 102334155
FibViaRecursion took: 1086ms

new DynamicFibViaHashTable().getFib( new Long(10) ) - 55
new DynamicFibViaHashTable().getFib( new Long(20) ) - 6765
new DynamicFibViaHashTable().getFib( new Long(50) ) - 12586269025
testDynamicFibViaHashTable took: 6ms

new DynamicFibViaHashMap().getFib( 10 ) - 55
new DynamicFibViaHashMap().getFib( 20 ) - 6765
new DynamicFibViaHashMap().getFib( 50 ) - 12586269025
testDynamicFibViaHashMap took: 3ms

proc.getFib( 10 ) - 55
proc.getFib( 20 ) - 6765
proc.getFib( 50 ) - 12586269025
testMultiThreadDynamicFib took: 71ms

Enjoy the journey.

Thursday, April 19, 2012

Monopoly Game OOD and Implementation Framework with Java


I played speedy chess for fun a while back; to be more precise, two previous jobs ago. That was fun. Never played Monopoly in my life. OOD for the Monopoly is an interesting problem. The game itself is very loosely defined. Players can define their own rules?!

I am here to make an attempt to crack OOD of the game. 

Inheritance modeling is not so typical. To begin with, we have House, Hotel, FreePackingLot and Chance as the board slots. It's a bit stretch to use simplistic "is-a" to define all relationship. It makes sense to me to use Java's interface as the base (interface Square), House, Hotel, FreePackingLot and Chance all implement Square interface. 

Dice is an excellent candidate for a immutable object. Enum is perfect fit for dice face implementation. 

Command pattern can be utilized to capture players' activities, ie buy property, pay rent, make a move after roll a dice. The RequestFactory is used to generate Action based on game rules and/or player's playing strategy. A new Action could be generated (triggered) right after the completion of the first one (a player landed on a Square and decide to buy it). 

The pattern Strategy is a good fit for Card implementation. Each Card has different task or a set of tasks. 

MonopolyBoard consists of Squares. I used the Vistors pattern to update Square after each action is performed. Update is generated from RequestFactory, for example, rent double for Blue colored properties since a Player occupied all Blue colored property. 

The most interesting part of the Framework is the rule implementation. I don't have full grasp of all Monopoly rules. One reasonable thing that we do is to implement each rule as an object, which generates the Action and Update based on the input - player's status, and chain the rule together based on priorities/preferences. Rule can be defined as game rule (task play must perform) or player's playing strategy (buy the first free property landed on wherever available).

GameFacade is a bit over simplified: each player takes turn and play. An Action gets generated and a Update created right after the completion of the Action.

I feel this framework can meet most of requirement, given that  I have ZERO playing experience.

Here is the Framework in Java: 


GameFacade.java
package com.lei.oop.monopolygame;

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


/**
 * 
 * GameFacade for playing monopoly game
 * 
 * @author lei zou
 *
 */
final public class GameFacade {
 
 private static GameFacade self;
 
 private MonopolyBoard board;
 private List<Player> players;
 private List<Card> cards;
 
 private GameFacade() { }
 
 public void reset () {
  String boardFile = System.getProperty("monopoly_game.xml");
  board = new MonopolyBoard(boardFile);
  players = loadPlayers ("monopoly_player_list.xml");
  cards = loadCards ("monopoly_game_cards.xml");
 }
 
 public void play () {
  boolean noWinner=true;
  int playerIdx = 0;
  while (noWinner) {
   Player currentPlayer = players.get( (playerIdx++) % players.size() );
   Dice dice = Dice.rollDice();
   currentPlayer.addDice(dice);
   ActionPerform action = RequestFactory.generationNextAction(currentPlayer);
   while (action!=null) {
    SquareUpdate update = RequestFactory.generationNextUpdate (action);
    this.board.update(update);
    action = RequestFactory.generationNextAction(currentPlayer);
   }
   // check winner 
  }
  
 }

 static public GameFacade getInstance() {
  if (self==null) self = new GameFacade();
  return self;
 }
 
 private List<Player> loadPlayers (String fileName) {
  List<Player> list = new ArrayList<Player> ();
  return list;
 }

 private List<Card> loadCards (String cardFileName) {
  List<Card> list = new ArrayList<Card> ();
  list.add(new Card("card_one", new Card.CardActionOne() ));
  list.add(new Card("card_two", new Card.CardActionTwo() ));
  // ... 
  return list;
  
 }

 public MonopolyBoard getBoard() {
  return board;
 }

 public void setBoard(MonopolyBoard board) {
  this.board = board;
 }

}




Action.java
package com.lei.oop.monopolygame;

/**
 * Action class for the Monopoly game
 * 
 * Command design pattern is utilized to encapsulate the request 
 * 
 * @author lei zou
 *
 */
public class Action implements ActionPerform {
 private Player[] actors; 
 private Square currentPosition;
 private Square newPosition;
 private ActionUpdate callback;
 private boolean status; 

 // Purchase property 
 static public class PurchaseProperty extends Action implements ActionPerform {
  public PurchaseProperty (Square square, Player[] players, ActionUpdate callback) {
   super(square, players, callback);
  }
  public void execute () {
   // buy the property
   update ();
  }

 }

 // Pay rent 
 static public class PayRent extends Action implements ActionPerform {
  public PayRent (Square square, Player[] players, ActionUpdate callback) {
   super(square, players, callback);
  }
  public void execute () {
   // pay rent
   update ();
  }

 }

 // Pay tax 
 static public class PayTax extends Action implements ActionPerform {
  public PayTax (Square square, Player[] players, ActionUpdate callback) {
   super(square, players, callback);
  }
  public void execute () {
   // pay tax
   update ();
  }

 }

 // Take a card  
 static public class DrawACard extends Action implements ActionPerform {
  public DrawACard (Square square, Player[] players, ActionUpdate callback) {
   super(square, players, callback);
  }
  public void execute () {
   // buy the property
   update ();
  }

 }


 // Make a move 
 static public class MakeAMove extends Action implements ActionPerform {
  private int stepsForward;
  public MakeAMove (Square square, Player player, int steps) {
   super(square, new Player[] { player}, player );
   stepsForward = steps;
  }

  public void execute () {
   // move to the next square 
   this.setNewPosition ( GameFacade.getInstance().getBoard().nextSquare(this) );
   update ();
  }
 }

 
 // Action base class 
 public Action (Square square, Player[] players, ActionUpdate callback) {
  this.currentPosition = square;
  this.actors = players;
  this.callback = callback;
 }
 
 public void execute () { }
 
 public void update () { 
  if (callback!=null)  callback.update(this);
 }

 public Square getCurrentPosition() { return currentPosition; }

 public void setCurrentPosition(Square currentPosition) { this.currentPosition = currentPosition; }

 public Square getNewPosition() { return newPosition; }

 public void setNewPosition(Square newPosition) { this.newPosition = newPosition;}
 
 
}




ActionPerform.java
package com.lei.oop.monopolygame;

/**
 * 
 * ActionPerform Interface 
 * 
 * @author lei zou
 *
 */
public interface ActionPerform {

 void execute ();
 
}



ActionUpdate.java
package com.lei.oop.monopolygame;

/**
 * 
 * ActionUpdate Interface 
 * 
 * @author lei zou
 *
 */

public interface ActionUpdate {
 void update(Action command);
}


Asset.java
package com.lei.oop.monopolygame;

import com.lei.oop.monopolygame.ColorGroup.COLOR;

/**
 * Asset class, which has value, player can purchase it or need to pay rent 
 *  
 * @author lei zou
 *
 */

public abstract class Asset implements Square {
 private String name;
 private int purchasePrice;
 private int rentPrice;
 final private int position;
 final private COLOR color;
 private Participant owner;
 
 public Asset (int position) {
  this(position, null); 
 }
 
 public Asset (int position, COLOR color) {
  this.position = position; 
  this.color = color;
 }

 public String getName() { return name; }
 public void setName(String name) { this.name = name; }
 public int getRentPrice() { return rentPrice; }
 public void setRentPrice(int rentPrice) { this.rentPrice = rentPrice; }
 public int getPurchasePrice() { return purchasePrice; }
 public void setPurchasePrice(int purchasePrice) { this.purchasePrice = purchasePrice; }
 public int getPosition() { return position; }
 public COLOR getColor() {return color;}
 
}




Banker.java
package com.lei.oop.monopolygame;

/**
 * 
 * Banker class 
 * 
 * @author lei zou
 *
 */
public class Banker extends  Participant implements  ActionUpdate {
 
 private int balance;
 
 
 public Banker (String name) {
  super(name);
 }
 
 public void update(Action command) {
  // update the Banker after the command action is performed.  
 }
 
}


Card.java
package com.lei.oop.monopolygame;

/**
 * 
 * Card class for monopoly game
 * 
 * Strategy pattern is utilized to implement the instructions from the Card
 * 
 * @author lei zou
 *
 */
public class Card implements CardAction {
 
 static public class CardActionOne implements CardAction {
  public CardActionOne() {};
  public void followInstruction () {
   System.out.println("do CardActionOne");
  }
 }
 static public class CardActionTwo implements CardAction {
  public CardActionTwo() {};
  public void followInstruction () {
   System.out.println("do CardActionTwo");
  }
 }

 private String name;
 private CardAction action;

 
 public Card(String name, CardAction action) {
  super();
  this.name = name;
  this.action = action;
 }
 
 public void move() {
  action.followInstruction();
 }
 public String getName() {
  return name;
 }
 public void setName(String name) {
  this.name = name;
 }
 public CardAction getAction() {
  return action;
 }
 public void setAction(CardAction action) {
  this.action = action;
 }
 
 public void followInstruction () {
  action.followInstruction();
 }
 
}


CardAction.java
package com.lei.oop.monopolygame;

/**
 * Card Action interface 
 * 
 * @author lei zou
 *
 */
public interface CardAction {
 
 void followInstruction () ;

}



Chance.java
package com.lei.oop.monopolygame;

import com.lei.oop.monopolygame.ColorGroup.COLOR;

/**
 *  Chance class, it implements Square  
 * 
 * @author lei zou
 *
 */
public class Chance implements Square {

 final private int position; 
 final private COLOR color = null;
 
 
 public Chance(int position) {
  super();
  this.position = position;
 }

 public void playerLanded  (Player p) {
  // ... 
 }

 public int getPosition() {
  return position;
 }

 public ColorGroup.COLOR getColor() {
  return color;
 }

 public void update (SquareUpdate rule) {
  rule.update(this);
 }

}

ColorGroup.java
package com.lei.oop.monopolygame;

import java.util.HashMap;
import java.util.Map;


/**
 * 
 * ColorGroup class 
 * 
 * @author lei zou
 *
 */
final public class ColorGroup {

 static public enum COLOR { BLUE(1), YELLOW(2), RED(3), GREEN(4), BLACK(5), WHITE(6);
  private final int value; 
  COLOR(int val) { this.value = val; } 
  public int getValue() { return value; }
 }

 private static final Map<Integer, COLOR> IntToColorMap = new HashMap<Integer, COLOR>();
 
 static {
  for (COLOR type : COLOR.values()) IntToColorMap.put(type.value, type);
 }
  
 public static COLOR getColor (int idx) {
  return IntToColorMap.get(new Integer(idx));
 }
}

Dice.java
vp2c01b-dhcp68:LeiJava lei$ sed 's/\&/\&/g;  s/\"/\"/g; s//\>/g;' ./src/main/java/com/lei/oop/monopolygame/Dice.java   | sed "s/\'/\'/g;" 
package com.lei.oop.monopolygame;


import java.util.HashMap;
import java.util.Map;

/**
 * 
 * Dice class, roll a dice and return a dice object 
 * 
 * @author lei zou
 *
 */
final public class Dice {

 static public enum DiceFace { ONE(1), TWO(2), THREE(3), FOUR(4), FIVE(5), SIX(6);
  static public int FaceDifference = SIX.value - ONE.value;
  private final int value; 
  DiceFace(int val) { this.value = val; } 
  public int getValue() { return value; }
 }
 private final DiceFace faceValueOne;
 private final DiceFace faceValueTwo;

 public Dice (final DiceFace faceValue1, final DiceFace faceValue2) {
  faceValueOne = faceValue1;
  faceValueTwo = faceValue2;
 }
 
 private static final Map<Integer, DiceFace> IntToDiceFaceMap = new HashMap<Integer, DiceFace>();
  static {
   for (DiceFace type : DiceFace.values()) {
    IntToDiceFaceMap.put(type.value, type);
     }
 }


 final public DiceFace getFaceValueOne () { return faceValueOne;}
 final public DiceFace getFaceValueTwo () { return faceValueTwo;}
 
 
 @Override
 public String toString() {
  StringBuilder builder = new StringBuilder();
  builder.append("Dice [faceValueOne=").append(faceValueOne)
    .append(", faceValueTwo=").append(faceValueTwo).append("]");
  return builder.toString();
 }
 static public Dice rollDice () {
  int valOne = (int) ( (double)DiceFace.ONE.value + Math.random() * DiceFace.FaceDifference ) ;
  int valTwo = (int) ( (double)DiceFace.ONE.value + Math.random() * DiceFace.FaceDifference ) ;
  return new Dice( IntToDiceFaceMap.get(valOne), IntToDiceFaceMap.get(valTwo));
 }
 
 public static void main(String[] args) throws Exception {
  Dice d = Dice.rollDice();
  System.out.println(d);
 }
}
vp2c01b-dhcp68:LeiJava lei$ 


FreePackingLot.java
package com.lei.oop.monopolygame;

import com.lei.oop.monopolygame.ColorGroup.COLOR;

/**
 * FreePackingLot class, implements Square
 * 
 * @author lei zou
 *
 */
public class FreePackingLot implements Square {

 final private int position;
 
 public FreePackingLot (int pos) {
  this.position = pos;
 }
 
 public void playerLanded (Player p) { }
 
 public int getPosition() {
  return position;
 }
 
 public COLOR getColor () {
  return null;
 }
 
 public void update (SquareUpdate rule) {
  
 }

}


GameRule.java
package com.lei.oop.monopolygame;

/**
 * 
 * GameRule class to implement the monopoly game rules. 
 * 
 * @author lei zou
 *
 */
public class GameRule extends RequestGeneration {
 
 public GameRule (RequestGeneration successor) {
  super(successor);
 }

 public ActionPerform generationNextAction (Participant p) {
  
  ActionPerform action = null;
  
  // 
  return action;
  
  
 }
}


GameStrategy.java
package com.lei.oop.monopolygame;

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

/**
 * GameStrategy to implement the monopoly game playing strategy 
 * 
 * @author lei zou
 *
 */
public class GameStrategy extends RequestGeneration {

 static private List<GameStrategy> listGameStrategy = new ArrayList<GameStrategy>(); 
 
 public GameStrategy (RequestGeneration successor) {
  super(successor);
 }

 public ActionPerform generationNextAction (Participant p) {
  
  ActionPerform action = null;
  
  // if multiple  
  return action;
  
  
 }
}


MonopolyBoard.java
package com.lei.oop.monopolygame;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import com.lei.oop.monopolygame.ColorGroup.COLOR;



/**
 * 
 * MonopolyBoard class, which is for the monopoly game board.   
 * 
 * @author lei zou
 *
 */
final public class MonopolyBoard {
 
 final private List<Square> squares;
 final private Map<COLOR, Square> ColoredPropertyMap;
   
 public MonopolyBoard(String fileName) {
  
   // load the board square from system property
  squares = new ArrayList<Square>();
  // load the colored properties   
  ColoredPropertyMap = new HashMap<COLOR, Square>();
 }

   
 public Square nextSquare (Action move) {
  Square next = null;
  Action.MakeAMove nextMove = (Action.MakeAMove) move;
  if (nextMove!=null) {
   
  }
  return next;
 }
 
 public void update (SquareUpdate update) {
  for (Square square : squares) {
   square.update(update);
  }
 }
}



Participant.java
package com.lei.oop.monopolygame;

/**
 * Participant abstract class 
 * 
 * @author lei zou
 *
 */
public abstract class Participant {
 private String name;
 public Participant (String name) {
  this.name = name;
 }
 public String getName() {return name;}
 public void setName(String name) {this.name = name;}

}


Player.java
package com.lei.oop.monopolygame;


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

/**
 * Player class 
 *  
 * @author lei zou
 *
 */
public class Player extends Participant implements  ActionUpdate {
 
 private int money;
 private Square currentSquare;
 private List<Square> properties = new ArrayList<Square>();
 private List<Dice> rolledDices = new ArrayList<Dice>();
 private List<Card> cards = new ArrayList<Card>();

 public Player (String name) { super(name);}
 
 void addDice (Dice dice) {
  rolledDices.add(dice);
 }

 public boolean pay (int amount) {
  this.money -= amount;
  return (money>0)? true:false;  
 }
 public void collect (int amount) {
  this.money += amount;
 }

 public int getMoney() {
  return money;
 }

 public void setMoney(int money) {
  this.money = money;
 }

 public Square getCurrentSquare() {
  return currentSquare;
 }

 public void setCurrentSquare(Square currentSquare) {
  this.currentSquare = currentSquare;
 }
 
 public void update(Action command) {
  // callback to update after the action is perform
 }

}



Property.java
package com.lei.oop.monopolygame;

import com.lei.oop.monopolygame.ColorGroup.COLOR;


/**
 * 
 * Property: rent, purchase price
 * 
 * @author lei zou
 *
 */
public class Property extends Asset implements Square {
 private int rent;

 static public class Hotel extends Property implements Square {
  public Hotel (int position) {
   super(position);
  }
 }

 public Property (int position) {
  super(position);
 }
 
 public Property (int position, COLOR color) {
  super(position, color);
 }
 public void playerLanded (Player p) {
  // ... 
 }
 
 public int getRent() { return rent; }
 
 public void setRent(int rent) { this.rent = rent; }

 public void update (SquareUpdate rule) {
  rule.update(this);
 }

}


RequestFactory.java
package com.lei.oop.monopolygame;

import java.util.HashMap;
import java.util.Map;


/**
 * RequestFactory to generate Actions and Updates
 * 
 * @author lei zou
 *
 */

public class RequestFactory {

 static abstract class AbstractFactory {
  abstract ActionPerform createAction(Participant p);
  abstract SquareUpdate createUpdate(ActionPerform a);
 }
 
 static private class ConcreteFactory extends AbstractFactory {
  static private RequestGeneration requestGenerator = loadRequestGenerator();
  static private UpdateGeneration updateGenerator = loadUpdateGenerator();
  ActionPerform createAction(Participant p) {
   RequestGeneration proc = requestGenerator;
   ActionPerform action = proc.generationNextAction(p);
   proc = proc.next();
   while (action==null && proc!=null) {
    // create a new request action 
    action = proc.generationNextAction(p);
   }
   return action; 
  }
  
  SquareUpdate createUpdate(ActionPerform a) {
   
   UpdateGeneration proc = updateGenerator;
   SquareUpdate update = proc.generateNextUpdate(a);
   proc = proc.next();
   while (update==null && proc!=null) {
    // create new update request to update the board 
    update = proc.generateNextUpdate(a);
   }
   
   return update;
  }
  static private RequestGeneration loadRequestGenerator() {
   RequestGeneration first = null;
   // 
   return first;
  }
  
  static private UpdateGeneration loadUpdateGenerator() {
   UpdateGeneration first = null;
   // 
   return first;
   
  }
 }
 
 private static final Map<String, AbstractFactory> FactoryMap = new HashMap<String, AbstractFactory>();
 static {
  FactoryMap.put("Request", new ConcreteFactory());
 }
 
 private static AbstractFactory pf=FactoryMap.get("Request");
 
 static public ActionPerform generationNextAction (Participant p) {
  return pf.createAction(p);
 }
 
 static public SquareUpdate generationNextUpdate (ActionPerform a) {
  return pf.createUpdate(a);
 }

}





RequestGeneration.java
package com.lei.oop.monopolygame;

/**
 * Rule chain to generate action request 
 * 
 * @author lei zou
 *
 */
public abstract class RequestGeneration {
 
 private RequestGeneration successor;
 
 public RequestGeneration (RequestGeneration successor) {
  this.successor = successor;
 }
 public RequestGeneration next () { return successor; }
 public abstract ActionPerform generationNextAction (Participant p);
 public RequestGeneration getSuccessor() { return successor; }
 public void setSuccessor(RequestGeneration successor) { this.successor = successor; }
 
}


Square.java
package com.lei.oop.monopolygame;

import com.lei.oop.monopolygame.ColorGroup.COLOR;


/**
 * Square interface, it represent the slot on the board. 
 * 
 * @author lei zou
 *
 */
public interface Square {

 public void playerLanded (Player p);
 public int getPosition();
 public COLOR getColor ();
 public void update (SquareUpdate rule);
}



SquareUpdate.java
package com.lei.oop.monopolygame;

/**
 * interface SquareUpdate to update the board squares
 * 
 * Vistors pattern is used here to update Square for example double the rent, update the owner 
 * 
 * @author lei zou
 *
 */
public interface SquareUpdate {
 
 void update (Property property);
 void update (Asset asset);
 void update (Square square);
}


SquareUpdateDoubleRent.java
package com.lei.oop.monopolygame;

import com.lei.oop.monopolygame.ColorGroup.COLOR;

/**
 * 
 * double the rent for the asset square 
 * 
 * @author lei zou
 *
 */
public class SquareUpdateDoubleRent implements SquareUpdate {

 final private COLOR color;
 public SquareUpdateDoubleRent (COLOR color) {
  this.color = color;
 }
 
 public void update (Property property) {
  if (property.getColor()!=null && this.color!=null && property.getColor()==this.color)
   property.setRent(property.getRent()*2);
 }

 public void update (Asset asset) {
 }
 
 public void update (Square square) {
 }

}

UpdateGeneration.java
package com.lei.oop.monopolygame;

/**
 *  Rule chain for generate updates 
 * 
 * @author lei zou
 *
 */

public abstract class UpdateGeneration {

 private UpdateGeneration successor;
 
 public abstract UpdateGeneration next ();
 public abstract SquareUpdate generateNextUpdate(ActionPerform a);
 public UpdateGeneration getSuccessor() { return successor; }
 public void setSuccessor(UpdateGeneration successor) { this.successor = successor; }
 

}



Well, that is it. Enjoy the Journey!

Tuesday, April 10, 2012

Simple Thread-Safe Bounded Queue Implementation in Java

I was asked to implement a thread-safe bounded queue for a pattern of producer and customer. The implementation involves ReentrantLock and Condition; it's straight forward. The testing of the queue requires a bit more work. For verification,  I created create a thread pool of size 2. One for consumer, one for producer.

Here is the BoundedQueue code:


public class BoundedQueue <T> {

    private final T[] buffer;
    private final int capacity;
 
    private int front;
    private int rear;
    private int count;
 
    private final Lock lock = new ReentrantLock();
 
    private final Condition notFull = lock.newCondition();
    private final Condition notEmpty = lock.newCondition();

    /**
     * 
     * @param capacity is the fixed queue capacity 
     */
    public BoundedQueue (int capacity) {
        super();
        this.capacity = capacity;
        buffer = ((T[])new Object[capacity]);
    }

    /**
     * 
     * @return the object in the front of the queue 
     * 
     * @throws InterruptedException
     */
    public T get() throws InterruptedException {
        lock.lock();
 
        try {
            while (count == 0) {
                notEmpty.await();
            }
 
            T result = buffer[front];
            front = (front + 1) % capacity;
            count--;
            notFull.signal();
            return result;
        } finally {
            lock.unlock();
        }
    }

    /**
     * return object of the subclass 
     * 
     * @param <R>
     * @param type
     * @return
     * @throws InterruptedException
     */
    public <R extends T> R get(final Class<R> type) throws InterruptedException {
     return (R)this.get();
    }

    /**
     * put the object in the rear of the queue
     * @param data
     * @throws InterruptedException
     */
    public void put(final T data) throws InterruptedException {
        lock.lock();
        try {
            while (count == capacity) {
                notFull.await();
            }
 
            buffer[rear] = data;
            rear = (rear + 1) % capacity;
            count++;
 
            notEmpty.signal();
        } finally {
            lock.unlock();
        }
    }
 
}

Here is the JUnit test code for BoundedQueue:
public class BoundedQueueTest {
 static public class QueueConsumer implements Runnable, Callable<Long> {
  private BoundedQueue<Integer> queue;
  private long sleepTime;
  private int itemCount;
  private List items = new LinkedList<Integer>(); 
  public QueueConsumer (BoundedQueue<Integer> que, int itemCount, long sleepTime) {
   this.queue = que;
   this.itemCount = itemCount;
   this.sleepTime = sleepTime;
  }
 
  @Override
  public Long call() throws Exception {
   long sum = 0;
   try {
    for ( int i=0; i<itemCount; i++) {
     Integer obj = this.queue.get();
     Integer compareToObj = new Integer(i);
     items.add(obj);
     Assert.assertEquals(obj, compareToObj);
     //System.out.println("item - " + obj);
     sum++;
     Thread.sleep(sleepTime);
    }
   } catch (InterruptedException e) {
    e.printStackTrace();
   }

   return sum;
  }

  
  public void run () {
   try {
    long sum = this.call();
   } catch (Exception e) {
    e.printStackTrace();
   }
  }
 }

 static public class QueueProducer implements Runnable, Callable<Long> {
  private BoundedQueue<Integer> queue;
  private int itemCount;
  private long sleepTime;
  private Integer[] items; 
  public QueueProducer (BoundedQueue<Integer> que, int itemCount, long sleepTime) {
   this.queue = que;
   this.itemCount = itemCount;
   this.sleepTime = sleepTime;
   this.items = new Integer[itemCount];
   for ( int i=0; i<itemCount; i++) {
    this.items[i] = new Integer(i);
   }
  }

  @Override
  public Long call() throws Exception {
   long sum = 0;
   try {
    for ( int i=0; i<itemCount; i++) {
     this.queue.put(this.items[i]);
     sum++;
     Thread.sleep(sleepTime);
    }
   } catch (InterruptedException e) {
    e.printStackTrace();
   }
   return sum;
  }
  public void run () {
   try {
    call();
   } catch (Exception e) {
    e.printStackTrace();
   }
  }
 }


 @Test
 public void doFastConsumerBoundedQueueTest() {

  try {
   test(2, 100, 1000, 10, 8);
  } catch (InterruptedException e) {
   e.printStackTrace();
  } catch (ExecutionException e) {
   e.printStackTrace();
  }
 }

 @Test
 public void doFastProducerBoundedQueueTest() {

  try {
   test(2, 100, 1000, 10, 15);
  } catch (InterruptedException e) {
   e.printStackTrace();
  } catch (ExecutionException e) {
   e.printStackTrace();
  }
 }

 
 private void test(final int threadCount, int queueSize, int itemCound, long produceSleepTime, long consumerSleepTime) throws InterruptedException, ExecutionException {
  BoundedQueue<Integer> queue = new BoundedQueue<Integer>(queueSize);
  Callable<Long> task1 = new QueueProducer(queue, itemCound, produceSleepTime);
  Callable<Long> task2 = new QueueConsumer(queue, itemCound, consumerSleepTime);
  
  List<Callable<Long>> tasks = new ArrayList<Callable<Long>>(); 
  tasks.add(task1);
  tasks.add(task2);
  
  ExecutorService executorService = Executors.newFixedThreadPool(2);
  
  List<Future<Long>> futures = executorService.invokeAll(tasks);
  List<Long> resultList = new ArrayList<Long>(futures.size());

  for (Future<Long> future : futures) {
   resultList.add(future.get());
  }
  
  executorService.shutdown();
 }
 
 public static void main(String args[]) {
  new BoundedQueueTest().doFastProducerBoundedQueueTest();
  
 }

}

Enjoy the journey.