TIPatterns--复杂系统的状态(Complex system states)

    下面你将看到的一个基本状态机的框架，使整个系统从一个状态迁移到下一个状态的代码通常都是符合模板方法模式(Template Method)的。一开始，我们先定义一个标记接口（tagging interface）用来输入对象。

//: statemachine:Input.java
// Inputs to a state machine
package statemachine;
 
public interface Input {} ///:~

    每个状态都通过run()函数来完成它的行为，而且（在这个设计里）你可以传给它一个输入对象，这样它就能根据这个输入对象告诉它会迁移到哪个新的状态。这个设计和下一小节的设计的主要区别是：对于这个设计，每个State对象根据输入对象决定它自己可以迁移到哪些其它状态；下面那个设计，所有状态迁移都包含在一张单独的表里。换一种说法就是：这个设计里，每个State对象都拥有一张自己的小型状态表，而下面那个设计里整个系统只有一张状态迁移的总表。

//: statemachine:State.java
// A State has an operation, and can be moved
// into the next State given an Input:
package statemachine;
 
public interface State {
  void run();
  State next(Input i);
} ///:~

    StateMachine会记录当前状态，这个状态是在StateMachine的构造函数里初始化的。RunAll()方法接受一个关于一系列输入对象的迭代器（这里使用迭代器是为了图个简单方便，重要的是输入信息是从别的地方传进来的）。这个方法不但使状态机迁移到下一个状态，而且它还调用每一个状态对象的run()方法——你会发现它是State模式的扩展，因为run()根据系统所处的不同状态做出不同的事情。

//: statemachine:StateMachine.java
// Takes an Iterator of Inputs to move from State
// to State using a template method.
package statemachine;
import java.util.*;
 
public class StateMachine {
  private State currentState;
  public StateMachine(State initialState) {
    currentState = initialState;
    currentState.run();
  }
  // Template method:
  public final void runAll(Iterator inputs) {
    while(inputs.hasNext()) {
      Input i = (Input)inputs.next();
      System.out.println(i);
      currentState = currentState.next(i);
      currentState.run();
    }
  }
}  ///:~

 
    我把runAll()当作一个模板方法来实现。这是一种典型的做法，当然并不是说必须得这么做——你可能想要concievably重载它，但是通常这些行为的改变还是会发生在State对象的run()方法里。

    到这里为止，这种风格的状态机（每个状态决定它的下一个状态）的基本框架就算完成了。我会写一个假想的捕鼠器（mousetrap）作为例子，这个捕鼠器在诱捕老鼠的过程中会经历几个不同的状态。Mouse类和与之相关的信息都存储在mouse package里，包括一个用来代表老鼠所有可能动作的类，这些动作会作为状态机的输入。

//: statemachine:mouse:MouseAction.java

package statemachine.mouse;

import java.util.*;

import statemachine.*;

 

public class MouseAction implements Input {

  private String action;

  private static List instances = new ArrayList();

  private MouseAction(String a) {

    action = a;

    instances.add(this);

  }

  public String toString() { return action; }

  public int hashCode() {

    return action.hashCode();

  }

  public boolean equals(Object o) {

    return (o instanceof MouseAction)

      && action.equals(((MouseAction)o).action);

  }

  public static MouseAction forString(String description) {

    Iterator it = instances.iterator();

    while(it.hasNext()) {

      MouseAction ma = (MouseAction)it.next();

      if(ma.action.equals(description))

        return ma;

    }

    throw new RuntimeException("not found: " + description);

  }

  public static MouseAction

    appears = new MouseAction("mouse appears"),

    runsAway = new MouseAction("mouse runs away"),

    enters = new MouseAction("mouse enters trap"),

    escapes = new MouseAction("mouse escapes"),

    trapped = new MouseAction("mouse trapped"),

    removed = new MouseAction("mouse removed");

} ///:~ 

    你会注意到，hashCode()和equals()都被重载了，这么做是为了MouseAction对象能够作为HashMap的键值来使用，但是在mousetrap的第一个版本里我们先不这么做。另外，老鼠所有可能的动作都作为一个静态的MouseAction对象被枚举出来。

    为了便于书写测试代码，一系列有关老鼠（动作）的输入是作为一个文本文件提供的。

//:! statemachine:mouse:MouseMoves.txt
mouse appears
mouse runs away
mouse appears
mouse enters trap
mouse escapes
mouse appears
mouse enters trap
mouse trapped
mouse removed
mouse appears
mouse runs away
mouse appears
mouse enters trap
mouse trapped
mouse removed
///:~

    为了用通用的（generic fashion）方法来读这个文件，我写了一个通用的StringList工具：

//: com:bruceeckel:util:StringList.java
// General-purpose tool that reads a file of text
// lines into a List, one line per list.
package com.bruceeckel.util;
import java.io.*;
import java.util.*;
 
public class StringList extends ArrayList {
  public StringList(String textFilePath) {
    try {
      BufferedReader inputs = new BufferedReader (
        new FileReader(textFilePath));
      String line;
      while((line = inputs.readLine()) != null)
        add(line.trim());
    } catch(IOException e) {
      throw new RuntimeException(e);
    }
  }
} ///:~

    这个StringList只能像ArrayList那样存储对象，所以我们还需要一个适配器（adapter）用来把String对象转换成MouseAction对象：

//: statemachine:mouse:MouseMoveList.java
// A "transformer" to produce a
// List of MouseAction objects.
package statemachine.mouse;
import java.util.*;
import com.bruceeckel.util.*;
 
public class MouseMoveList extends ArrayList {
  public MouseMoveList(Iterator it) {
    while(it.hasNext())
      add(MouseAction.forString((String)it.next()));
  }
} ///:~

 
    MouseMoveList看起来有点像一个装饰者（decorator），而实际上干的又有点像adapter干的活。不管到底是什么，adapter把一个接口改变为另外一个接口，decorator（给现有类）添加功能或者数据。MouseMoveList改变了容器的内容，所以可能叫做Transformer更合适。

    有了上面这些工具，现在就可以创建第一个版本的mousetrap了。每一个由State派生的类都定义它自己的run()行为，然后用if-else语句确定它的下一个状态。

//: statemachine:mousetrap1:MouseTrapTest.java
// State Machine pattern using 'if' statements
// to determine the next state.
package statemachine.mousetrap1;
import statemachine.mouse.*;
import statemachine.*;
import com.bruceeckel.util.*;
import java.util.*;
import java.io.*;
import junit.framework.*;
 
// A different subclass for each state:
 
class Waiting implements State {
  public void run() {
    System.out.println(
      "Waiting: Broadcasting cheese smell");
  }
  public State next(Input i) {
    MouseAction ma = (MouseAction)i;
    if(ma.equals(MouseAction.appears))
      return MouseTrap.luring;
    return MouseTrap.waiting;
  }
}
 
class Luring implements State {
  public void run() {
    System.out.println(
      "Luring: Presenting Cheese, door open");
  }
  public State next(Input i) {
    MouseAction ma = (MouseAction)i;
    if(ma.equals(MouseAction.runsAway))
      return MouseTrap.waiting;
    if(ma.equals(MouseAction.enters))
      return MouseTrap.trapping;
    return MouseTrap.luring;
  }
}
 
class Trapping implements State {
  public void run() {
    System.out.println("Trapping: Closing door");
  }
  public State next(Input i) {
    MouseAction ma = (MouseAction)i;
    if(ma.equals(MouseAction.escapes))
      return MouseTrap.waiting;
    if(ma.equals(MouseAction.trapped))
      return MouseTrap.holding;
    return MouseTrap.trapping;
  }
}
 
class Holding implements State {
  public void run() {
    System.out.println("Holding: Mouse caught");
  }
  public State next(Input i) {
    MouseAction ma = (MouseAction)i;
    if(ma.equals(MouseAction.removed))
      return MouseTrap.waiting;
    return MouseTrap.holding;
  }
}
 
class MouseTrap extends StateMachine {
  public static State
    waiting = new Waiting(),
    luring = new Luring(),
    trapping = new Trapping(),
    holding = new Holding();
  public MouseTrap() {
    super(waiting); // Initial state
  }
}
 
public class MouseTrapTest extends TestCase  {
  MouseTrap trap = new MouseTrap();
  MouseMoveList moves =
    new MouseMoveList(
      new StringList("../mouse/MouseMoves.txt")
        .iterator());
  public void test() {
    trap.runAll(moves.iterator());
  }
  public static void main(String args[]) {
    junit.textui.TestRunner.run(MouseTrapTest.class);
  }
} ///:~

    StateMachine类简单的把所有可能的状态都定义成静态对象，然后设置自己的初始状态。UnitTest创建一个MouseTrap对象，然后用MouseMoveList（所存储的MouseMove）作为输入来测试它。

    虽然在next()方法内部使用if-else语句是无可厚非的，但是如果状态数目非常多，用这种方法就会变的很麻烦。另一种方法是在每个State对象内部创建一个表结构，根据输入信息定义不同的次状态（next state）。

    刚开始，这看起来似乎应该很简单。你需要在每一个State子类里定义一个静态表结构，而这个表又要根据其它State对象来确定它们之间该如何迁移。但是，这种方法在初始化的时候会产生循环依赖。为了解决这个问题，我必须得把表结构的初始化延迟到某个特定的State对象的next()方法第一次被调用的时候。由于这个原因，next()方法初看起来可能会显得有点怪。

    StateT类是State接口的一个实现（这样它就能和上面那个例子共用同一个StateMachine类），此外它还添加了一个Map和一个用来从两维数组初始化这个map的方法。Next()方法在基类里有一个实现，派生类重载过的next()方法首先测试Map是否为空（如果为空，则初始化之），然后它会调用基类的next()方法。

//: statemachine:mousetrap2:MouseTrap2Test.java
// A better mousetrap using tables
package statemachine.mousetrap2;
import statemachine.mouse.*;
import statemachine.*;
import java.util.*;
import java.io.*;
import com.bruceeckel.util.*;
import junit.framework.*;
 
abstract class StateT implements State {
  protected Map transitions = null;
  protected void init(Object[][] states) {
    transitions = new HashMap();
    for(int i = 0; i < states.length; i++)
      transitions.put(states[i][0], states[i][1]);
  }
  public abstract void run();
  public State next(Input i) {
    if(transitions.containsKey(i))
      return (State)transitions.get(i);
    else
      throw new RuntimeException(
        "Input not supported for current state");
  }
}
 
class MouseTrap extends StateMachine {
  public static State
    waiting = new Waiting(),
    luring = new Luring(),
    trapping = new Trapping(),
    holding = new Holding();
  public MouseTrap() {
    super(waiting); // Initial state
  }
}
 
class Waiting extends StateT {
  public void run() {
    System.out.println(
      "Waiting: Broadcasting cheese smell");
  }
  public State next(Input i) {
    // Delayed initialization:
    if(transitions == null)
      init(new Object[][] {
        { MouseAction.appears, MouseTrap.luring },
      });
    return super.next(i);
  }
}
 
class Luring extends StateT {
  public void run() {
    System.out.println(
      "Luring: Presenting Cheese, door open");
  }
  public State next(Input i) {
    if(transitions == null)
      init(new Object[][] {
        { MouseAction.enters, MouseTrap.trapping },
        { MouseAction.runsAway, MouseTrap.waiting },
      });
    return super.next(i);
  }
}
 
class Trapping extends StateT {
  public void run() {
    System.out.println("Trapping: Closing door");
  }
  public State next(Input i) {
    if(transitions == null)
      init(new Object[][] {
        { MouseAction.escapes, MouseTrap.waiting },
        { MouseAction.trapped, MouseTrap.holding },
      });
    return super.next(i);
  }
}
 
class Holding extends StateT {
  public void run() {
    System.out.println("Holding: Mouse caught");
  }
  public State next(Input i) {
    if(transitions == null)
      init(new Object[][] {
        { MouseAction.removed, MouseTrap.waiting },
      });
    return super.next(i);
  }
}
 
public class MouseTrap2Test extends TestCase  {
  MouseTrap trap = new MouseTrap();
  MouseMoveList moves =
    new MouseMoveList(
      new StringList("../mouse/MouseMoves.txt")
        .iterator());
  public void test() {
    trap.runAll(moves.iterator());
  }
  public static void main(String args[]) {
    junit.textui.TestRunner.run(MouseTrap2Test.class);
  }
} ///:~

    代码的后面一部分和上面那个例子是完全相同的——不同的部分在next()方法和StateT类里。

    如果你必须得创建并且维护非常多的State类，这种方法（相对于上一个例子）有所改善，因为通过查看表结构可以更容易和迅速的读懂各个状态之间的迁移关系。

练习
1. 改写MouseTRap2Test.java，从一个只包含状态表信息的外部的文本文件加载状态表信息。

表驱动的状态机(Table-Driven State Machine)

    上面那个设计的好处是所有有关状态的信息，包括状态迁移信息，都位于state类的内部。通常来说，这是一个好的设计习惯。

    但是，对于一个纯粹的状态机来说，它完全可以用一个单独的状态迁移表来表示。这么做的好处是所有有关状态机的信息都可以放在同一个地方，也就意味着你可以简单的根据一个传统的状态迁移图来创建和维护它。

    传统的状态迁移图用圆圈来代表每各个状态，用不同的细线来指向某一状态可以迁移到的所有其它状态。每条迁移线都标注有迁移条件和动作。下面是一张状态图：

(一张简单的状态机图)

目标：
·  直接翻译状态图
· Vector of change: the state diagram representation
· 合理的实现
· 没有过剩的状态（你可以用新的状态来表示每个单独的变化）
· 简单灵活

观察结果：
· 状态不是最重要的——它们不包含信息或者函数/数据，只是一个标识
· 跟State模式没有相似性
· 状态机控制各个状态之间的迁移
· 和享元（flyweight）有些类似
· 每个状态都可能迁移到多个其它状态
· 迁移条件和动作必须位于状态的外部
· 为了使配置方便，集中描述所有状态变化，把它放到一张单独的表里面。

例子：
· 状态机和用于表驱动的代码
· 实现一个自动售货机
· 用到其它的几个模式
· 把通用的状态机代码和特定的程序代码相分离（像template method模式那样）
· 为每个输入搜索合适的解决方案（像职责链模式那样）
· 测试和状态迁移都封装在函数对象里（封装函数的对象）.
· Java约束：methods are not first-class objects

State类
    这个State类和上面的完全不同，它只是个有名字的占位符（placeholder）。所以它就没有继承上一个State类。

//: statemachine2:State.java
package statemachine2;
 
public class State {
  private String name;
  public State(String nm) { name = nm; }
  public String toString() { return name; }
} ///:~

 

迁移条件(Conditions for transition)
    在状态迁移图上，会针对输入检验它是否满足迁移条件，进而决定它能否迁移到对应的次状态。跟前面的例子一样，这里Input类还是一个标记接口(tagging interface)。

//: statemachine2:Input.java
// Inputs to a state machine
package statemachine2;
 
public interface Input {} ///:~ 

    Condition类通过对输入的Input对象求值（evaluates）来决定表中这一行是否是符合条件的迁移。

//: statemachine2:Condition.java
// Condition function object for state machine
package statemachine2;
 
public interface Condition {
  boolean condition(Input i);
} ///:~
 

迁移动作(Transition actions)
    如果Condition类返回true，（当前状态）就会迁移到新的状态，在这个迁移的过程中会发生一些动作（在前面那个状态机的设计里，这个动作就是run()方法）：

//: statemachine2:Transition.java
// Transition function object for state machine
package statemachine2;
 
public interface Transition {
  void transition(Input i);
} ///:~
 

{ {CurrentState},
  {Input, Condition(Input), Transition(Input), Next},
  {Input, Condition(Input), Transition(Input), Next},
  {Input, Condition(Input), Transition(Input), Next},
   ...
}

基本状态机The basic machine

//: statemachine2:StateMachine.java

// A table-driven state machine

package statemachine2;

import java.util.*;

 

public class StateMachine {

  private State state;

  private Map map = new HashMap();

  public StateMachine(State initial) {

    state = initial;

  }

  public void buildTable(Object[][][] table) {

    for(int i = 0; i < table.length; i++) {

      Object[][] row = table[i];

      Object currentState = row[0][0];

      List transitions = new ArrayList();

      for(int j = 1; j < row.length; j++)

        transitions.add(row[j]);

      map.put(currentState, transitions);

    }

  }

  public void nextState(Input input) {

    Iterator it=((List)map.get(state)).iterator();

    while(it.hasNext()) {

      Object[] tran = (Object[])it.next();

      if(input == tran[0] ||

         input.getClass() == tran[0]) {

        if(tran[1] != null) {

          Condition c = (Condition)tran[1];

          if(!c.condition(input))

            continue; // Failed test

        }

        if(tran[2] != null)

          ((Transition)tran[2]).transition(input);

        state = (State)tran[3];

        return;

      }

    }

    throw new RuntimeException(

      "Input not supported for current state");

  }

} ///:~

简单的自动售货机Simple vending machine

 

//: statemachine:vendingmachine:VendingMachine.java

// Demonstrates use of StateMachine.java

package statemachine.vendingmachine;

import statemachine2.*;

 

final class VM extends State {

  private VM(String nm) { super(nm); }

  public final static VM

    quiescent = new VM("Quiesecent"),

    collecting = new VM("Collecting"),

    selecting = new VM("Selecting"),

    unavailable = new VM("Unavailable"),

    wantMore = new VM("Want More?"),

    noChange = new VM("Use Exact Change Only"),

    makesChange = new VM("Machine makes change");

}

final class HasChange implements Input {

  private String name;

  private HasChange(String nm) { name = nm; }

  public String toString() { return name; }

  public final static HasChange

    yes = new HasChange("Has change"),

    no = new HasChange("Cannot make change");

}

class ChangeAvailable extends StateMachine {

  public ChangeAvailable() {

    super(VM.makesChange);

    buildTable(new Object[][][]{

      { {VM.makesChange}, // Current state

        // Input, test, transition, next state:

        {HasChange.no, null, null, VM.noChange}},

      { {VM.noChange}, // Current state

        // Input, test, transition, next state:

        {HasChange.yes, null,

         null, VM.makesChange}},

    });

  }

}

final class Money implements Input {

  private String name;

  private int value;

  private Money(String nm, int val) {

    name = nm;

    value = val;

  }

  public String toString() { return name; }

  public int getValue() { return value; }

  public final static Money

    quarter = new Money("Quarter", 25),

    dollar = new Money("Dollar", 100);

}

final class Quit implements Input {

  private Quit() {}

  public String toString() { return "Quit"; }

  public final static Quit quit = new Quit();

}

final class FirstDigit implements Input {

  private String name;

  private int value;

  private FirstDigit(String nm, int val) {

    name = nm;

    value = val;

  }

  public String toString() { return name; }

  public int getValue() { return value; }

  public final static FirstDigit

    A = new FirstDigit("A", 0),

    B = new FirstDigit("B", 1),

    C = new FirstDigit("C", 2),

    D = new FirstDigit("D", 3);

}

final class SecondDigit implements Input {

  private String name;

  private int value;

  private SecondDigit(String nm, int val) {

    name = nm;

    value = val;

  }

  public String toString() { return name; }

  public int getValue() { return value; }

  public final static SecondDigit

    one = new SecondDigit("one", 0),

    two = new SecondDigit("two", 1),

    three = new SecondDigit("three", 2),

    four = new SecondDigit("four", 3);

}

class ItemSlot {

  int price;

  int quantity;

  static int counter = 0;

  String id = Integer.toString(counter++);

  public ItemSlot(int prc, int quant) {

    price = prc;

    quantity = quant;

  }

  public String toString() { return id; }

  public int getPrice() { return price; }

  public int getQuantity() { return quantity; }

  public void decrQuantity() { quantity--; }

}

public class VendingMachine extends StateMachine{

  StateMachine changeAvailable =

    new ChangeAvailable();

  int amount = 0;

  FirstDigit first = null;

  ItemSlot[][] items = new ItemSlot[4][4];

  Condition notEnough = new Condition() {

    public boolean condition(Input input) {

      int i1 = first.getValue();

      int i2 = ((SecondDigit)input).getValue();

      return items[i1][i2].getPrice() > amount;

    }

  };

  Condition itemAvailable = new Condition() {

    public boolean condition(Input input) {

      int i1 = first.getValue();

      int i2 = ((SecondDigit)input).getValue();

      return items[i1][i2].getQuantity() > 0;

    }

  };

  Condition itemNotAvailable = new Condition() {

    public boolean condition(Input input) {

      return !itemAvailable.condition(input);

    }

  };

  Transition clearSelection = new Transition() {

    public void transition(Input input) {

      int i1 = first.getValue();

      int i2 = ((SecondDigit)input).getValue();

      ItemSlot is = items[i1][i2];

      System.out.println(

        "Clearing selection: item " + is +

        " costs " + is.getPrice() +

        " and has quantity " + is.getQuantity());

      first = null;

    }

  };

  Transition dispense = new Transition() {

    public void transition(Input input) {

      int i1 = first.getValue();

      int i2 = ((SecondDigit)input).getValue();

      ItemSlot is = items[i1][i2];

      System.out.println("Dispensing item " +

        is + " costs " + is.getPrice() +

        " and has quantity " + is.getQuantity());

      items[i1][i2].decrQuantity();

      System.out.println("New Quantity " +

        is.getQuantity());

      amount -= is.getPrice();

      System.out.println("Amount remaining " +

        amount);

    }

  };

  Transition showTotal = new Transition() {

    public void transition(Input input) {

      amount += ((Money)input).getValue();

      System.out.println("Total amount = " +

        amount);

    }

  };

  Transition returnChange = new Transition() {

    public void transition(Input input) {

      System.out.println("Returning " + amount);

      amount = 0;

    }

  };

  Transition showDigit = new Transition() {

    public void transition(Input input) {

      first = (FirstDigit)input;

      System.out.println("First Digit= "+ first);

    }

  };

  public VendingMachine() {

    super(VM.quiescent); // Initial state

    for(int i = 0; i < items.length; i++)

      for(int j = 0; j < items[i].length; j++)

        items[i][j] = new ItemSlot((j+1)*25, 5);

    items[3][0] = new ItemSlot(25, 0);

    buildTable(new Object[][][]{

      { {VM.quiescent}, // Current state

        // Input, test, transition, next state:

        {Money.class, null,

         showTotal, VM.collecting}},

      { {VM.collecting}, // Current state

        // Input, test, transition, next state:

        {Quit.quit, null,

         returnChange, VM.quiescent},

        {Money.class, null,

         showTotal, VM.collecting},

        {FirstDigit.class, null,

         showDigit, VM.selecting}},

      { {VM.selecting}, // Current state

        // Input, test, transition, next state:

        {Quit.quit, null,

         returnChange, VM.quiescent},

        {SecondDigit.class, notEnough,

         clearSelection, VM.collecting},

        {SecondDigit.class, itemNotAvailable,

         clearSelection, VM.unavailable},

        {SecondDigit.class, itemAvailable,

         dispense, VM.wantMore}},

      { {VM.unavailable}, // Current state

        // Input, test, transition, next state:

        {Quit.quit, null,

         returnChange, VM.quiescent},

        {FirstDigit.class, null,

         showDigit, VM.selecting}},

      { {VM.wantMore}, // Current state

        // Input, test, transition, next state:

        {Quit.quit, null,

         returnChange, VM.quiescent},

        {FirstDigit.class, null,

         showDigit, VM.selecting}},

    });

  }

} ///:~

 

测试自动售货机Testing the machine

//: statemachine:vendingmachine:VendingMachineTest.java

// Demonstrates use of StateMachine.java

package statemachine.vendingmachine;

import statemachine2.*;

import junit.framework.*;

 

public class VendingMachineTest extends TestCase {

  VendingMachine vm = new VendingMachine();

  Input[] inputs = {

    Money.quarter,

    Money.quarter,

    Money.dollar,

    FirstDigit.A,

    SecondDigit.two,

    FirstDigit.A,

    SecondDigit.two,

    FirstDigit.C,

    SecondDigit.three,

    FirstDigit.D,

    SecondDigit.one,

    Quit.quit,

  };

  public void test() {

    for(int i = 0; i < inputs.length; i++)

      vm.nextState(inputs[i]);

  }

  public static void main(String[] args) {

    junit.textui.TestRunner.run(VendingMachineTest.class);

  }

} ///:~

工具Tools
    当状态机越来越复杂的时候，另外一种方法就是使用自动化工具通过配置一张表让工具来产生状态机的代码。你可以用像Python这样的语言自己写一个，但是已经有人写好了免费的，并且是开放源码的工具，比如Libero，可以在这里找到 http://www.imatix.com.

通过匿名内部类来实现表驱动
参见TIJ第9章ListPerformance.java那个例子。
以及 GreenHouse.java

练习