Merge change I0a56959e into eclair-mr2

* changes:
  Implement a HierarchicalStateMachine

9 files changed, 2848 insertions, 456 deletions

diff --git a/core/java/android/os/HandlerState.java b/core/java/android/os/HandlerState.java
deleted file mode 100644
index 0708f7d42cb7..000000000000
--- a/core/java/android/os/HandlerState.java
+++ /dev/null
@@ -1,33 +0,0 @@
-/*
- * Copyright (C) 2006 The Android Open Source Project
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- *      http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-package android.os;
-
-/**
- * {@hide}
- */
-public abstract class HandlerState {
-    public HandlerState() {
-    }
-
-    public void enter(Message message) {
-    }
-
-    public abstract void processMessage(Message message);
-
-    public void exit(Message message) {
-    }
-}
diff --git a/core/java/android/os/HandlerStateMachine.java b/core/java/android/os/HandlerStateMachine.java
deleted file mode 100644
index 9e7902b5c7e4..000000000000
--- a/core/java/android/os/HandlerStateMachine.java
+++ /dev/null
@@ -1,290 +0,0 @@
-/*
- * Copyright (C) 2006 The Android Open Source Project
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- *      http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-package android.os;
-
-import android.util.Log;
-import android.util.LogPrinter;
-
-/**
- * {@hide}
- *
- * Implement a state machine where each state is an object,
- * HandlerState. Each HandlerState must implement processMessage
- * and optionally enter/exit. When a state machine is created
- * the initial state must be set. When messages are sent to
- * a state machine the current state's processMessage method is
- * invoked. If this is the first message for this state the
- * enter method is called prior to processMessage and when
- * transtionTo is invoked the state's exit method will be
- * called after returning from processMessage.
- *
- * If a message should be handled in a different state the
- * processMessage method may call deferMessage. This causes
- * the message to be saved on a list until transitioning
- * to a new state, at which time all of the deferred messages
- * will be put on the front of the state machines queue and
- * processed by the new current state's processMessage
- * method.
- *
- * Below is an example state machine with two state's, S1 and S2.
- * The initial state is S1 which defers all messages and only
- * transition to S2 when message.what == TEST_WHAT_2. State S2
- * will process each messages until it receives TEST_WHAT_2
- * where it will transition back to S1:
-<code>
-     class StateMachine1 extends HandlerStateMachine {
-        private static final int TEST_WHAT_1 = 1;
-        private static final int TEST_WHAT_2 = 2;
-
-        StateMachine1(String name) {
-            super(name);
-            setInitialState(mS1);
-        }
-
-        class S1 extends HandlerState {
-            &amp;#064;Override public void enter(Message message) {
-            }
-
-            &amp;#064;Override public void processMessage(Message message) {
-                deferMessage(message);
-                if (message.what == TEST_WHAT_2) {
-                    transitionTo(mS2);
-                }
-            }
-
-            &amp;#064;Override public void exit(Message message) {
-            }
-        }
-
-        class S2 extends HandlerState {
-            &amp;#064;Override public void processMessage(Message message) {
-                // Do some processing
-                if (message.what == TEST_WHAT_2) {
-                    transtionTo(mS1);
-                }
-            }
-        }
-
-        private S1 mS1 = new S1();
-        private S2 mS2 = new S2();
-    }
-</code>
- */
-public class HandlerStateMachine {
-
-    private boolean mDbg = false;
-    private static final String TAG = "HandlerStateMachine";
-    private String mName;
-    private SmHandler mHandler;
-    private HandlerThread mHandlerThread;
-
-    /**
-     * Handle messages sent to the state machine by calling
-     * the current state's processMessage. It also handles
-     * the enter/exit calls and placing any deferred messages
-     * back onto the queue when transitioning to a new state.
-     */
-    class SmHandler extends Handler {
-
-        SmHandler(Looper looper) {
-          super(looper);
-        }
-
-        /**
-         * This will dispatch the message to the
-         * current state's processMessage.
-         */
-        @Override
-        final public void handleMessage(Message msg) {
-            if (mDbg) Log.d(TAG, "SmHandler.handleMessage E");
-            if (mDestState != null) {
-                if (mDbg) Log.d(TAG, "SmHandler.handleMessage; new destation call enter");
-                mCurrentState = mDestState;
-                mDestState = null;
-                mCurrentState.enter(msg);
-            }
-            if (mCurrentState != null) {
-                if (mDbg) Log.d(TAG, "SmHandler.handleMessage; call processMessage");
-                mCurrentState.processMessage(msg);
-            } else {
-                /* Strange no state to execute */
-                Log.e(TAG, "handleMessage: no current state, did you call setInitialState");
-            }
-
-            if (mDestState != null) {
-                if (mDbg) Log.d(TAG, "SmHandler.handleMessage; new destination call exit");
-                mCurrentState.exit(msg);
-
-                /**
-                 * Place the messages from the deferred queue:t
-                 * on to the Handler's message queue in the
-                 * same order that they originally arrived.
-                 *
-                 * We set cur.when = 0 to circumvent the check
-                 * that this message has already been sent.
-                 */
-                while (mDeferredMessages != null) {
-                    Message cur = mDeferredMessages;
-                    mDeferredMessages = mDeferredMessages.next;
-                    cur.when = 0;
-                    if (mDbg) Log.d(TAG, "SmHandler.handleMessage; queue deferred message what="
-                                                + cur.what + " target=" + cur.target);
-                    sendMessageAtFrontOfQueue(cur);
-                }
-                if (mDbg) Log.d(TAG, "SmHandler.handleMessage X");
-            }
-        }
-
-        public HandlerState mCurrentState;
-        public HandlerState mDestState;
-        public Message mDeferredMessages;
-    }
-
-    /**
-     * Create an active StateMachine, one that has a
-     * dedicated thread/looper/queue.
-     */
-    public HandlerStateMachine(String name) {
-        mName = name;
-        mHandlerThread =  new HandlerThread(name);
-        mHandlerThread.start();
-        mHandler = new SmHandler(mHandlerThread.getLooper());
-    }
-
-    /**
-     * Get a message and set Message.target = this.
-     */
-    public final Message obtainMessage()
-    {
-        Message msg = Message.obtain(mHandler);
-        if (mDbg) Log.d(TAG, "StateMachine.obtainMessage() EX target=" + msg.target);
-        return msg;
-    }
-
-    /**
-     * Get a message and set Message.target = this and
-     * Message.what = what.
-     */
-    public final Message obtainMessage(int what) {
-        Message msg = Message.obtain(mHandler, what);
-        if (mDbg) {
-            Log.d(TAG, "StateMachine.obtainMessage(what) EX what=" + msg.what +
-                       " target=" + msg.target);
-        }
-        return msg;
-    }
-
-    /**
-     * Enqueue a message to this state machine.
-     */
-    public final void sendMessage(Message msg) {
-        if (mDbg) Log.d(TAG, "StateMachine.sendMessage EX msg.what=" + msg.what);
-        mHandler.sendMessage(msg);
-    }
-
-    /**
-     * Enqueue a message to this state machine after a delay.
-     */
-    public final void sendMessageDelayed(Message msg, long delayMillis) {
-        if (mDbg) {
-            Log.d(TAG, "StateMachine.sendMessageDelayed EX msg.what="
-                            + msg.what + " delay=" + delayMillis);
-        }
-        mHandler.sendMessageDelayed(msg, delayMillis);
-    }
-
-    /**
-     * Set the initial state. This must be invoked before
-     * and messages are sent to the state machine.
-     */
-    public void setInitialState(HandlerState initialState) {
-        if (mDbg) {
-            Log.d(TAG, "StateMachine.setInitialState EX initialState"
-                            + initialState.getClass().getName());
-        }
-        mHandler.mDestState = initialState;
-    }
-
-    /**
-     * transition to destination state. Upon returning
-     * from processMessage the current state's exit will
-     * be executed and upon the next message arriving
-     * destState.enter will be invoked.
-     */
-    final public void transitionTo(HandlerState destState) {
-        if (mDbg) {
-            Log.d(TAG, "StateMachine.transitionTo EX destState"
-                            + destState.getClass().getName());
-        }
-        mHandler.mDestState = destState;
-    }
-
-    /**
-     * Defer this message until next state transition.
-     * Upon transitioning all deferred messages will be
-     * placed on the queue and reprocessed in the original
-     * order. (i.e. The next state the oldest messages will
-     * be processed first)
-     */
-    final public void deferMessage(Message msg) {
-        if (mDbg) {
-            Log.d(TAG, "StateMachine.deferMessage EX mDeferredMessages="
-                            + mHandler.mDeferredMessages);
-        }
-
-        /* Copy the "msg" to "newMsg" as "msg" will be recycled */
-        Message newMsg = obtainMessage();
-        newMsg.copyFrom(msg);
-
-        /* Place on front of queue */
-        newMsg.next = mHandler.mDeferredMessages;
-        mHandler.mDeferredMessages = newMsg;
-    }
-
-    /**
-     * @return the name
-     */
-    public String getName() {
-        return mName;
-    }
-
-    /**
-     * @return Handler
-     */
-    public Handler getHandler() {
-        return mHandler;
-    }
-
-    /**
-     * @return if debugging is enabled
-     */
-    public boolean isDbg() {
-        return mDbg;
-    }
-
-    /**
-     * Set debug enable/disabled.
-     */
-    public void setDbg(boolean dbg) {
-        mDbg = dbg;
-        if (mDbg) {
-            mHandlerThread.getLooper().setMessageLogging(new LogPrinter(Log.VERBOSE, TAG));
-        } else {
-            mHandlerThread.getLooper().setMessageLogging(null);
-        }
-   }
-}
diff --git a/core/java/com/android/internal/util/HierarchicalState.java b/core/java/com/android/internal/util/HierarchicalState.java
new file mode 100644
index 000000000000..002338adfe94
--- /dev/null
+++ b/core/java/com/android/internal/util/HierarchicalState.java
@@ -0,0 +1,75 @@
+/**
+ * Copyright (C) 2009 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.internal.util;
+
+import android.os.Message;
+
+/**
+ * {@hide}
+ *
+ * The abstract class for implementing states in a
+ * HierarchicalStateMachine and HandlerStateMachine.
+ */
+public abstract class HierarchicalState {
+
+    /**
+     * Constructor
+     */
+    protected HierarchicalState() {
+    }
+
+    /**
+     * Called when a state is entered.
+     */
+    protected void enter() {
+    }
+
+    /**
+     * Called when a message is to be processed by the
+     * state machine.
+     *
+     * This routine is never reentered thus no synchronization
+     * is needed as only one processMessage method will ever be
+     * executing within a state machine at any given time. This
+     * does mean that processing by this routine must be completed
+     * as expeditiously as possible as no subsequent messages will
+     * be processed until this routine returns.
+     *
+     * @param msg to process
+     * @return true if processing has completed and false
+     *         if the parent state's processMessage should
+     *         be invoked.
+     */
+    abstract protected boolean processMessage(Message msg);
+
+    /**
+     * Called when a state is exited.
+     */
+    protected void exit() {
+    }
+
+    /**
+     * @return name of state, but default returns the states
+     * class name. An instance name would be better but requiring
+     * it seems unnecessary.
+     */
+    public String getName() {
+        String name = getClass().getName();
+        int lastDollar = name.lastIndexOf('$');
+        return name.substring(lastDollar + 1);
+    }
+}
diff --git a/core/java/com/android/internal/util/HierarchicalStateMachine.java b/core/java/com/android/internal/util/HierarchicalStateMachine.java
new file mode 100644
index 000000000000..a1c5078b567a
--- /dev/null
+++ b/core/java/com/android/internal/util/HierarchicalStateMachine.java
@@ -0,0 +1,1164 @@
+/**
+ * Copyright (C) 2009 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.internal.util;
+
+import android.os.Handler;
+import android.os.HandlerThread;
+import android.os.Looper;
+import android.os.Message;
+import android.util.Log;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+
+/**
+ * {@hide}
+ *
+ * A hierarchical state machine is a state machine which processes messages
+ * and can have states arranged hierarchically. A state is a <code>HierarchicalState</code>
+ * object and must implement <code>processMessage</code> and optionally <code>enter/exit/getName</code>.
+ * The enter/exit methods are equivalent to the construction and destruction
+ * in Object Oriented programming and are used to perform initialization and
+ * cleanup of the state respectively. The <code>getName</code> method returns the
+ * name of the state the default implementation returns the class name it may be
+ * desirable to have this return the name of the state instance name instead.
+ * In particular if a particular state class has multiple instances.
+ *
+ * When a state machine is created <code>addState</code> is used to build the
+ * hierarchy and <code>setInitialState</code> is used to identify which of these
+ * is the initial state. After construction the programmer calls <code>start</code>
+ * which initializes the state machine and calls <code>enter</code> for all of the initial
+ * state's hierarchy, starting at its eldest parent. For example given the simple
+ * state machine below after start is called mP1.enter will have been called and
+ * then mS1.enter.
+<code>
+        mP1
+       /   \
+      mS2   mS1 ----> initial state
+</code>
+ * After the state machine is created and started, messages are sent to a state
+ * machine using <code>sendMessage</code and the messages are created using
+ * <code>obtainMessage</code>. When the state machine receives a message the
+ * current state's <code>processMessage</code> is invoked. In the above example
+ * mS1.processMessage will be invoked first. The state may use <code>transitionTo</code>
+ * to change the current state to a new state
+ *
+ * Each state in the state machine may have a zero or one parent states and if
+ * a child state is unable to handle a message it may have the message processed
+ * by its parent by returning false. If a message is never processed <code>unhandledMessage</code>
+ * will be invoked to give one last chance for the state machine to process
+ * the message.
+ *
+ * When all processing is completed a state machine may choose to call
+ * <code>transitionToHaltingState</code>. When the current <code>processingMessage</code>
+ * returns the state machine will transfer to an internal <code>HaltingState</code>
+ * and invoke <code>halting</code>. Any message subsequently received by the state
+ * machine will cause <code>haltedProcessMessage</code> to be invoked.
+ *
+ * In addition to <code>processMessage</code> each <code>HierarchicalState</code> has
+ * an <code>enter</code> method and <code>exit</exit> method which may be overridden.
+ *
+ * Since the states are arranged in a hierarchy transitioning to a new state
+ * causes current states to be exited and new states to be entered. To determine
+ * the list of states to be entered/exited the common parent closest to
+ * the current state is found. We then exit from the current state and its
+ * parent's up to but not including the common parent state and then enter all
+ * of the new states below the common parent down to the destination state.
+ * If there is no common parent all states are exited and then the new states
+ * are entered.
+ *
+ * Two other methods that states can use are <code>deferMessage</code> and
+ * <code>sendMessageAtFrontOfQueue</code>. The <code>sendMessageAtFrontOfQueue</code> sends
+ * a message but places it on the front of the queue rather than the back. The
+ * <code>deferMessage</code> causes the message to be saved on a list until a
+ * transition is made to a new state. At which time all of the deferred messages
+ * will be put on the front of the state machine queue with the oldest message
+ * at the front. These will then be processed by the new current state before
+ * any other messages that are on the queue or might be added later. Both of
+ * these are protected and may only be invoked from within a state machine.
+ *
+ * To illustrate some of these properties we'll use state machine with 8
+ * state hierarchy:
+<code>
+          mP0
+         /   \
+        mP1   mS0
+       /   \
+      mS2   mS1
+     /  \    \
+    mS3  mS4  mS5  ---> initial state
+</code>
+ *
+ * After starting mS5 the list of active states is mP0, mP1, mS1 and mS5.
+ * So the order of calling processMessage when a message is received is mS5,
+ * mS1, mP1, mP0 assuming each processMessage  indicates it can't handle this
+ * message by returning false.
+ *
+ * Now assume mS5.processMessage receives a message it can handle, and during
+ * the handling determines the machine should changes states. It would call
+ * transitionTo(mS4) and return true. Immediately after returning from
+ * processMessage the state machine runtime will find the common parent,
+ * which is mP1. It will then call mS5.exit, mS1.exit, mS2.enter and then
+ * mS4.enter. The new list of active states is mP0, mP1, mS2 and mS4. So
+ * when the next message is received mS4.processMessage will be invoked.
+ *
+ * To assist in describing an HSM a simple grammar has been created which
+ * is informally defined here and a formal EBNF description is at the end
+ * of the class comment.
+ *
+ * An HSM starts with the name and includes a set of hierarchical states.
+ * A state is preceeded by one or more plus signs (+), to indicate its
+ * depth and a hash (#) if its the initial state. Child states follow their
+ * parents and have one more plus sign then their parent. Inside a state
+ * are a series of messages, the actions they perform and if the processing
+ * is complete ends with a period (.). If processing isn't complete and
+ * the parent should process the message it ends with a caret (^). The
+ * actions include send a message ($MESSAGE), defer a message (%MESSAGE),
+ * transition to a new state (>MESSAGE) and an if statement
+ * (if ( expression ) { list of actions }.)
+ *
+ * The Hsm HelloWorld could documented as:
+ *
+ * HelloWorld {
+ *   + # mState1.
+ * }
+ *
+ * and interpreted as HSM HelloWorld:
+ *
+ * mState1 a root state (single +) and initial state (#) which
+ * processes all messages completely, the period (.).
+ *
+ * The implementation is:
+<code>
+class HelloWorld extends HierarchicalStateMachine {
+    Hsm1(String name) {
+        super(name);
+        addState(mState1);
+        setInitialState(mState1);
+    }
+
+    public static HelloWorld makeHelloWorld() {
+        HelloWorld hw = new HelloWorld("hw");
+        hw.start();
+        return hw;
+    }
+
+    class State1 extends HierarchicalState {
+        @Override public boolean processMessage(Message message) {
+            Log.d(TAG, "Hello World");
+            return true;
+        }
+    }
+    State1 mState1 = new State1();
+}
+
+void testHelloWorld() {
+    HelloWorld hw = makeHelloWorld();
+    hw.sendMessage(hw.obtainMessage());
+}
+</code>
+ *
+ * A more interesting state machine is one of four states
+ * with two independent parent states.
+<code>
+        mP1      mP2
+       /   \
+      mS2   mS1
+</code>
+ *
+ * documented as:
+ *
+ * Hsm1 {
+ *   + mP1 {
+ *       CMD_2 {
+ *          $CMD_3
+ *          %CMD_2
+ *          >mS2
+ *       }.
+ *     }
+ *   ++ # mS1 { CMD_1{ >mS1 }^ }
+ *   ++   mS2 {
+ *            CMD_2{$CMD_4}.
+ *            CMD_3{%CMD_3 ; >mP2}.
+ *     }
+ *
+ *   + mP2 e($CMD_5) {
+ *            CMD_3, CMD_4.
+ *            CMD_5{>HALT}.
+ *     }
+ * }
+ *
+ * and interpreted as HierarchicalStateMachine Hsm1:
+ *
+ * mP1 a root state.
+ *      processes message CMD_2 which sends CMD_3, defers CMD_2, and transitions to mS2
+ *
+ * mS1 a child of mP1 is the initial state:
+ *      processes message CMD_1 which transitions to itself and returns false to let mP1 handle it.
+ *
+ * mS2 a child of mP1:
+ *      processes message CMD_2 which send CMD_4
+ *      processes message CMD_3 which defers CMD_3 and transitions to mP2
+ *
+ * mP2 a root state.
+ *      on enter it sends CMD_5
+ *      processes message CMD_3
+ *      processes message CMD_4
+ *      processes message CMD_5 which transitions to halt state
+ *
+ * The implementation is below and also in HierarchicalStateMachineTest:
+<code>
+class Hsm1 extends HierarchicalStateMachine {
+    private static final String TAG = "hsm1";
+
+    public static final int CMD_1 = 1;
+    public static final int CMD_2 = 2;
+    public static final int CMD_3 = 3;
+    public static final int CMD_4 = 4;
+    public static final int CMD_5 = 5;
+
+    public static Hsm1 makeHsm1() {
+        Log.d(TAG, "makeHsm1 E");
+        Hsm1 sm = new Hsm1("hsm1");
+        sm.start();
+        Log.d(TAG, "makeHsm1 X");
+        return sm;
+    }
+
+    Hsm1(String name) {
+        super(name);
+        Log.d(TAG, "ctor E");
+
+        // Add states, use indentation to show hierarchy
+        addState(mP1);
+            addState(mS1, mP1);
+            addState(mS2, mP1);
+        addState(mP2);
+
+        // Set the initial state
+        setInitialState(mS1);
+        Log.d(TAG, "ctor X");
+    }
+
+    class P1 extends HierarchicalState {
+        @Override public void enter() {
+            Log.d(TAG, "mP1.enter");
+        }
+        @Override public boolean processMessage(Message message) {
+            boolean retVal;
+            Log.d(TAG, "mP1.processMessage what=" + message.what);
+            switch(message.what) {
+            case CMD_2:
+                // CMD_2 will arrive in mS2 before CMD_3
+                sendMessage(obtainMessage(CMD_3));
+                deferMessage(message);
+                transitionTo(mS2);
+                retVal = true;
+                break;
+            default:
+                // Any message we don't understand in this state invokes unhandledMessage
+                retVal = false;
+                break;
+            }
+            return retVal;
+        }
+        @Override public void exit() {
+            Log.d(TAG, "mP1.exit");
+        }
+    }
+
+    class S1 extends HierarchicalState {
+        @Override public void enter() {
+            Log.d(TAG, "mS1.enter");
+        }
+        @Override public boolean processMessage(Message message) {
+            Log.d(TAG, "S1.processMessage what=" + message.what);
+            if (message.what == CMD_1) {
+                // Transition to ourself to show that enter/exit is called
+                transitionTo(mS1);
+                return true;
+            } else {
+                // Let parent process all other messages
+                return false;
+            }
+        }
+        @Override public void exit() {
+            Log.d(TAG, "mS1.exit");
+        }
+    }
+
+    class S2 extends HierarchicalState {
+        @Override public void enter() {
+            Log.d(TAG, "mS2.enter");
+        }
+        @Override public boolean processMessage(Message message) {
+            boolean retVal;
+            Log.d(TAG, "mS2.processMessage what=" + message.what);
+            switch(message.what) {
+            case(CMD_2):
+                sendMessage(obtainMessage(CMD_4));
+                retVal = true;
+                break;
+            case(CMD_3):
+                deferMessage(message);
+                transitionTo(mP2);
+                retVal = true;
+                break;
+            default:
+                retVal = false;
+                break;
+            }
+            return retVal;
+        }
+        @Override public void exit() {
+            Log.d(TAG, "mS2.exit");
+        }
+    }
+
+    class P2 extends HierarchicalState {
+        @Override public void enter() {
+            Log.d(TAG, "mP2.enter");
+            sendMessage(obtainMessage(CMD_5));
+        }
+        @Override public boolean processMessage(Message message) {
+            Log.d(TAG, "P2.processMessage what=" + message.what);
+            switch(message.what) {
+            case(CMD_3):
+                break;
+            case(CMD_4):
+                break;
+            case(CMD_5):
+                transitionToHaltingState();
+                break;
+            }
+            return true;
+        }
+        @Override public void exit() {
+            Log.d(TAG, "mP2.exit");
+        }
+    }
+
+    @Override
+    protected void halting() {
+        Log.d(TAG, "halting");
+        synchronized (this) {
+            this.notifyAll();
+        }
+    }
+
+    P1 mP1 = new P1();
+    S1 mS1 = new S1();
+    S2 mS2 = new S2();
+    P2 mP2 = new P2();
+}
+</code>
+ *
+ * If this is executed by sending two messages CMD_1 and CMD_2
+ * (Note the synchronize is only needed because we use hsm.wait())
+ *
+ * Hsm1 hsm = makeHsm1();
+ * synchronize(hsm) {
+ *      hsm.sendMessage(obtainMessage(hsm.CMD_1));
+ *      hsm.sendMessage(obtainMessage(hsm.CMD_2));
+ *      try {
+ *           // wait for the messages to be handled
+ *           hsm.wait();
+ *      } catch (InterruptedException e) {
+ *           Log.e(TAG, "exception while waiting " + e.getMessage());
+ *      }
+ * }
+ *
+ *
+ * The output is:
+ *
+ * D/hsm1    ( 1999): makeHsm1 E
+ * D/hsm1    ( 1999): ctor E
+ * D/hsm1    ( 1999): ctor X
+ * D/hsm1    ( 1999): mP1.enter
+ * D/hsm1    ( 1999): mS1.enter
+ * D/hsm1    ( 1999): makeHsm1 X
+ * D/hsm1    ( 1999): mS1.processMessage what=1
+ * D/hsm1    ( 1999): mS1.exit
+ * D/hsm1    ( 1999): mS1.enter
+ * D/hsm1    ( 1999): mS1.processMessage what=2
+ * D/hsm1    ( 1999): mP1.processMessage what=2
+ * D/hsm1    ( 1999): mS1.exit
+ * D/hsm1    ( 1999): mS2.enter
+ * D/hsm1    ( 1999): mS2.processMessage what=2
+ * D/hsm1    ( 1999): mS2.processMessage what=3
+ * D/hsm1    ( 1999): mS2.exit
+ * D/hsm1    ( 1999): mP1.exit
+ * D/hsm1    ( 1999): mP2.enter
+ * D/hsm1    ( 1999): mP2.processMessage what=3
+ * D/hsm1    ( 1999): mP2.processMessage what=4
+ * D/hsm1    ( 1999): mP2.processMessage what=5
+ * D/hsm1    ( 1999): mP2.exit
+ * D/hsm1    ( 1999): halting
+ *
+ * Here is the HSM a BNF grammar, this is a first stab at creating an
+ * HSM description language, suggestions corrections or alternatives
+ * would be much appreciated.
+ *
+ * Legend:
+ *   {}  ::= zero or more
+ *   {}+ ::= one or more
+ *   []  ::= zero or one
+ *   ()  ::= define a group with "or" semantics.
+ *
+ * HSM EBNF:
+ *   HSM = HSM_NAME "{" { STATE }+ "}" ;
+ *   HSM_NAME = alpha_numeric_name ;
+ *   STATE = INTRODUCE_STATE [ ENTER ] "{" [ MESSAGES ] "}" [ EXIT ] ;
+ *   INTRODUCE_STATE = { STATE_DEPTH }+ [ INITIAL_STATE_INDICATOR ] STATE_NAME ;
+ *   STATE_DEPTH = "+" ;
+ *   INITIAL_STATE_INDICATOR = "#"
+ *   ENTER = "e(" SEND_ACTION | TRANSITION_ACTION | HALT_ACTION ")" ;
+ *   MESSAGES = { MSG_LIST MESSAGE_ACTIONS } ;
+ *   MSG_LIST = { MSG_NAME { "," MSG_NAME } ;
+ *   EXIT = "x(" SEND_ACTION | TRANSITION_ACTION | HALT_ACTION ")" ;
+ *   PROCESS_COMPLETION = PROCESS_IN_PARENT_OR_COMPLETE | PROCESS_COMPLETE ;
+ *   SEND_ACTION = "$" MSG_NAME ;
+ *   DEFER_ACTION = "%" MSG_NAME ;
+ *   TRANSITION_ACTION = ">" STATE_NAME ;
+ *   HALT_ACTION = ">" HALT ;
+ *   MESSAGE_ACTIONS = { "{" ACTION_LIST "}" } [ PROCESS_COMPLETION ] ;
+ *   ACTION_LIST = ACTION { (";" | "\n") ACTION } ;
+ *   ACTION = IF_ACTION | SEND_ACTION | DEFER_ACTION | TRANSITION_ACTION | HALT_ACTION ;
+ *   IF_ACTION = "if(" boolean_expression ")" "{" ACTION_LIST "}"
+ *   PROCESS_IN_PARENT_OR_COMPLETE = "^" ;
+ *   PROCESS_COMPLETE = "." ;
+ *   STATE_NAME = alpha_numeric_name ;
+ *   MSG_NAME = alpha_numeric_name | ALL_OTHER_MESSAGES ;
+ *   ALL_OTHER_MESSAGES = "*" ;
+ *   EXP = boolean_expression ;
+ *
+ * Idioms:
+ *   * { %* }. ::= All other messages will be deferred.
+ */
+public class HierarchicalStateMachine {
+
+    private static final String TAG = "HierarchicalStateMachine";
+    private String mName;
+
+    private static class HsmHandler extends Handler {
+
+        /** The debug flag */
+        private boolean mDbg = false;
+
+        /** A list of messages that this state machine has processed */
+        private ProcessedMessages mProcessedMessages = new ProcessedMessages();
+
+        /** true if construction of the state machine has not been completed */
+        private boolean mIsConstructionCompleted;
+
+        /** Stack used to manage the current hierarchy of states */
+        private StateInfo mStateStack[];
+
+        /** Top of mStateStack */
+        private int mStateStackTopIndex = -1;
+
+        /** A temporary stack used to manage the state stack */
+        private StateInfo mTempStateStack[];
+
+        /** The top of the mTempStateStack */
+        private int mTempStateStackCount;
+
+        /** State used when state machine is halted */
+        private HaltingState mHaltingState = new HaltingState();
+
+        /** Reference to the HierarchicalStateMachine */
+        private HierarchicalStateMachine mHsm;
+
+        /**
+         * Information about a state.
+         * Used to maintain the hierarchy.
+         */
+        private class StateInfo {
+            /** The state */
+            HierarchicalState state;
+
+            /** The parent of this state, null if there is no parent */
+            StateInfo parentStateInfo;
+
+            /** True when the state has been entered and on the stack */
+            boolean active;
+
+            /**
+             * Convert StateInfo to string
+             */
+            @Override
+            public String toString() {
+                return "state=" + state.getName() + ",active=" + active
+                        + ",parent=" + ((parentStateInfo == null) ?
+                                        "null" : parentStateInfo.state.getName());
+            }
+        }
+
+        /** The map of all of the states in the state machine */
+        private HashMap<HierarchicalState, StateInfo> mStateInfo =
+            new HashMap<HierarchicalState, StateInfo>();
+
+        /** The initial state that will process the first message */
+        private HierarchicalState mInitialState;
+
+        /** The destination state when transitionTo has been invoked */
+        private HierarchicalState mDestState;
+
+        /** The list of deferred messages */
+        private ArrayList<Message> mDeferredMessages = new ArrayList<Message>();
+
+        /**
+         * State entered when transitionToHaltingState is called.
+         */
+        private class HaltingState extends HierarchicalState {
+            @Override
+            public boolean processMessage(Message msg) {
+                mHsm.haltedProcessMessage(msg);
+                return true;
+            }
+        }
+
+        /**
+         * Handle messages sent to the state machine by calling
+         * the current state's processMessage. It also handles
+         * the enter/exit calls and placing any deferred messages
+         * back onto the queue when transitioning to a new state.
+         */
+        @Override
+        public final void handleMessage(Message msg) {
+            if (mDbg) Log.d(TAG, "handleMessage: E msg.what=" + msg.what);
+
+            /**
+             * Check that construction was completed
+             */
+            if (!mIsConstructionCompleted) {
+                Log.e(TAG, "The start method not called, ignore msg: " + msg);
+                return;
+            }
+
+            /**
+             * Process the message abiding by the hierarchical semantics.
+             */
+            processMsg(msg);
+
+            /**
+             * If transitionTo has been called, exit and then enter
+             * the appropriate states.
+             */
+            if (mDestState != null) {
+                if (mDbg) Log.d(TAG, "handleMessage: new destination call exit");
+
+                /**
+                 * Determine the states to exit and enter and return the
+                 * common ancestor state of the enter/exit states. Then
+                 * invoke the exit methods then the enter methods.
+                 */
+                StateInfo commonStateInfo = setupTempStateStackWithStatesToEnter(mDestState);
+                invokeExitMethods(commonStateInfo);
+                int stateStackEnteringIndex = moveTempStateStackToStateStack();
+                invokeEnterMethods(stateStackEnteringIndex);
+
+
+                /**
+                 * Since we have transitioned to a new state we need to have
+                 * any deferred messages moved to the front of the message queue
+                 * so they will be processed before any other messages in the
+                 * message queue.
+                 */
+                moveDeferredMessageAtFrontOfQueue();
+
+                /**
+                 * Call halting() if we've transitioned to the halting
+                 * state. All subsequent messages will be processed in
+                 * in the halting state which invokes haltedProcessMessage(msg);
+                 */
+                if (mDestState == mHaltingState) {
+                    mHsm.halting();
+                }
+                mDestState = null;
+            }
+
+            if (mDbg) Log.d(TAG, "handleMessage: X");
+        }
+
+        /**
+         * Complete the construction of the state machine.
+         */
+        private final void completeConstruction() {
+            if (mDbg) Log.d(TAG, "completeConstruction: E");
+
+            /**
+             * Determine the maximum depth of the state hierarchy
+             * so we can allocate the state stacks.
+             */
+            int maxDepth = 0;
+            for (StateInfo si : mStateInfo.values()) {
+                int depth = 0;
+                for (StateInfo i = si; i != null; depth++) {
+                    i = i.parentStateInfo;
+                }
+                if (maxDepth < depth) {
+                    maxDepth = depth;
+                }
+            }
+            if (mDbg) Log.d(TAG, "completeConstruction: maxDepth=" + maxDepth);
+
+            mStateStack = new StateInfo[maxDepth];
+            mTempStateStack = new StateInfo[maxDepth];
+            setupInitialStateStack();
+
+            /**
+             * Construction is complete call all enter methods
+             * starting at the first entry.
+             */
+            mIsConstructionCompleted = true;
+            invokeEnterMethods(0);
+
+            if (mDbg) Log.d(TAG, "completeConstruction: X");
+        }
+
+        /**
+         * Process the message. If the current state doesn't handle
+         * it, call the states parent and so on. If it is never handled then
+         * call the state machines unhandledMessage method.
+         */
+        private final void processMsg(Message msg) {
+            StateInfo curStateInfo = mStateStack[mStateStackTopIndex];
+            if (mDbg) {
+                Log.d(TAG, "processMsg: " + curStateInfo.state.getName());
+            }
+            while (!curStateInfo.state.processMessage(msg)) {
+                /**
+                 * Not processed
+                 */
+                curStateInfo = curStateInfo.parentStateInfo;
+                if (curStateInfo == null) {
+                    /**
+                     * No parents left so it's not handled
+                     */
+                    mHsm.unhandledMessage(msg);
+                    break;
+                }
+                if (mDbg) {
+                    Log.d(TAG, "processMsg: " + curStateInfo.state.getName());
+                }
+            }
+
+            /**
+             * Record that we processed the message
+             */
+            if (curStateInfo != null) {
+                HierarchicalState orgState = mStateStack[mStateStackTopIndex].state;
+                mProcessedMessages.add(msg, curStateInfo.state, orgState);
+            } else {
+                mProcessedMessages.add(msg, null, null);
+            }
+        }
+
+        /**
+         * Call the exit method for each state from the top of stack
+         * up to the common ancestor state.
+         */
+        private final void invokeExitMethods(StateInfo commonStateInfo) {
+            while ((mStateStackTopIndex >= 0) &&
+                    (mStateStack[mStateStackTopIndex] != commonStateInfo)) {
+                HierarchicalState curState = mStateStack[mStateStackTopIndex].state;
+                if (mDbg) Log.d(TAG, "invokeExitMethods: " + curState.getName());
+                curState.exit();
+                mStateStack[mStateStackTopIndex].active = false;
+                mStateStackTopIndex -= 1;
+            }
+        }
+
+        /**
+         * Invoke the enter method starting at the entering index to top of state stack
+         */
+        private final void invokeEnterMethods(int stateStackEnteringIndex) {
+            for (int i = stateStackEnteringIndex; i <= mStateStackTopIndex; i++) {
+                if (mDbg) Log.d(TAG, "invokeEnterMethods: " + mStateStack[i].state.getName());
+                mStateStack[i].state.enter();
+                mStateStack[i].active = true;
+            }
+        }
+
+        /**
+         * Move the deferred message to the front of the message queue.
+         */
+        private final void moveDeferredMessageAtFrontOfQueue() {
+            /**
+             * The oldest messages on the deferred list must be at
+             * the front of the queue so start at the back, which
+             * as the most resent message and end with the oldest
+             * messages at the front of the queue.
+             */
+            for (int i = mDeferredMessages.size() - 1; i >= 0; i-- ) {
+                Message curMsg = mDeferredMessages.get(i);
+                if (mDbg) Log.d(TAG, "moveDeferredMessageAtFrontOfQueue; what=" + curMsg.what);
+                sendMessageAtFrontOfQueue(curMsg);
+            }
+            mDeferredMessages.clear();
+        }
+
+        /**
+         * Move the contents of the temporary stack to the state stack
+         * reversing the order of the items on the temporary stack as
+         * they are moved.
+         *
+         * @return index into mStateState where entering needs to start
+         */
+        private final int moveTempStateStackToStateStack() {
+            int startingIndex = mStateStackTopIndex + 1;
+            int i = mTempStateStackCount - 1;
+            int j = startingIndex;
+            while (i >= 0) {
+                if (mDbg) Log.d(TAG, "moveTempStackToStateStack: i=" + i + ",j=" + j);
+                mStateStack[j] = mTempStateStack[i];
+                j += 1;
+                i -= 1;
+            }
+
+            mStateStackTopIndex = j - 1;
+            if (mDbg) {
+                Log.d(TAG, "moveTempStackToStateStack: X mStateStackTop="
+                      + mStateStackTopIndex + ",startingIndex=" + startingIndex
+                      + ",Top=" + mStateStack[mStateStackTopIndex].state.getName());
+            }
+            return startingIndex;
+        }
+
+        /**
+         * Setup the mTempStateStack with the states we are going to enter.
+         *
+         * This is found by searching up the destState's ancestors for a
+         * state that is already active i.e. StateInfo.active == true.
+         * The destStae and all of its inactive parents will be on the
+         * TempStateStack as the list of states to enter.
+         *
+         * @return StateInfo of the common ancestor for the destState and
+         * current state or null if there is no common parent.
+         */
+        private final StateInfo setupTempStateStackWithStatesToEnter(HierarchicalState destState) {
+            /**
+             * Search up the parent list of the destination state for an active
+             * state. Use a do while() loop as the destState must always be entered
+             * even if it is active. This can happen if we are exiting/entering
+             * the current state.
+             */
+            mTempStateStackCount = 0;
+            StateInfo curStateInfo = mStateInfo.get(destState);
+            do {
+                mTempStateStack[mTempStateStackCount++] = curStateInfo;
+                curStateInfo = curStateInfo.parentStateInfo;
+            } while ((curStateInfo != null) && !curStateInfo.active);
+
+            if (mDbg) {
+                Log.d(TAG, "setupTempStateStackWithStatesToEnter: X mTempStateStackCount="
+                      + mTempStateStackCount + ",curStateInfo: " + curStateInfo);
+            }
+            return curStateInfo;
+        }
+
+        /**
+         * Initialize StateStack to mInitialState.
+         */
+        private final void setupInitialStateStack() {
+            if (mDbg) {
+                Log.d(TAG, "setupInitialStateStack: E mInitialState="
+                    + mInitialState.getName());
+            }
+
+            StateInfo curStateInfo = mStateInfo.get(mInitialState);
+            for (mTempStateStackCount = 0; curStateInfo != null; mTempStateStackCount++) {
+                mTempStateStack[mTempStateStackCount] = curStateInfo;
+                curStateInfo = curStateInfo.parentStateInfo;
+            }
+
+            // Empty the StateStack
+            mStateStackTopIndex = -1;
+
+            moveTempStateStackToStateStack();
+        }
+
+        /**
+         * @return current state
+         */
+        private final HierarchicalState getCurrentState() {
+            return mStateStack[mStateStackTopIndex].state;
+        }
+
+        /**
+         * Add a new state to the state machine. Bottom up addition
+         * of states is allowed but the same state may only exist
+         * in one hierarchy.
+         *
+         * @param state the state to add
+         * @param parent the parent of state
+         * @return stateInfo for this state
+         */
+        private final StateInfo addState(HierarchicalState state, HierarchicalState parent) {
+            if (mDbg) {
+                Log.d(TAG, "addStateInternal: E state=" + state.getName()
+                        + ",parent=" + ((parent == null) ? "" : parent.getName()));
+            }
+            StateInfo parentStateInfo = null;
+            if (parent != null) {
+                parentStateInfo = mStateInfo.get(parent);
+                if (parentStateInfo == null) {
+                    // Recursively add our parent as it's not been added yet.
+                    parentStateInfo = addState(parent, null);
+                }
+            }
+            StateInfo stateInfo = mStateInfo.get(state);
+            if (stateInfo == null) {
+                stateInfo = new StateInfo();
+                mStateInfo.put(state, stateInfo);
+            }
+
+            // Validate that we aren't adding the same state in two different hierarchies.
+            if ((stateInfo.parentStateInfo != null) &&
+                    (stateInfo.parentStateInfo != parentStateInfo)) {
+                    throw new RuntimeException("state already added");
+            }
+            stateInfo.state = state;
+            stateInfo.parentStateInfo = parentStateInfo;
+            stateInfo.active = false;
+            if (mDbg) Log.d(TAG, "addStateInternal: X stateInfo: " + stateInfo);
+            return stateInfo;
+        }
+
+        /**
+         * Constructor
+         *
+         * @param looper for dispatching messages
+         * @param hsm the hierarchical state machine
+         */
+        private HsmHandler(Looper looper, HierarchicalStateMachine hsm) {
+            super(looper);
+            mHsm = hsm;
+
+            addState(mHaltingState, null);
+        }
+
+        /** @see HierarchicalStateMachine#setInitialState(HierarchicalState) */
+        private final void setInitialState(HierarchicalState initialState) {
+            if (mDbg) Log.d(TAG, "setInitialState: initialState" + initialState.getName());
+            mInitialState = initialState;
+        }
+
+        /** @see HierarchicalStateMachine#transitionTo(HierarchicalState) */
+        private final void transitionTo(HierarchicalState destState) {
+            if (mDbg) Log.d(TAG, "StateMachine.transitionTo EX destState" + destState.getName());
+            mDestState = destState;
+        }
+
+        /** @see HierarchicalStateMachine#deferMessage(Message) */
+        private final void deferMessage(Message msg) {
+            if (mDbg) Log.d(TAG, "deferMessage: msg=" + msg.what);
+
+            /* Copy the "msg" to "newMsg" as "msg" will be recycled */
+            Message newMsg = obtainMessage();
+            newMsg.copyFrom(msg);
+
+            mDeferredMessages.add(newMsg);
+        }
+
+        /** @see HierarchicalStateMachine#isDbg() */
+        private final boolean isDbg() {
+            return mDbg;
+        }
+
+        /** @see HierarchicalStateMachine#setDbg(boolean) */
+        private final void setDbg(boolean dbg) {
+            mDbg = dbg;
+        }
+
+        /** @see HierarchicalStateMachine#setProcessedMessagesSize(int) */
+        private final void setProcessedMessagesSize(int maxSize) {
+            mProcessedMessages.setSize(maxSize);
+        }
+
+        /** @see HierarchicalStateMachine#getProcessedMessagesSize() */
+        private final int getProcessedMessagesSize() {
+            return mProcessedMessages.size();
+        }
+
+        /** @see HierarchicalStateMachine#getProcessedMessagesCount() */
+        private final int getProcessedMessagesCount() {
+            return mProcessedMessages.count();
+        }
+
+        /** @see HierarchicalStateMachine#getProcessedMessage(int) */
+        private final ProcessedMessages.Info getProcessedMessage(int index) {
+            return mProcessedMessages.get(index);
+        }
+
+    }
+
+    private HsmHandler mHsmHandler;
+    private HandlerThread mHsmThread;
+
+    /**
+     * Initialize.
+     *
+     * @param looper for this state machine
+     * @param name of the state machine
+     */
+    private void initStateMachine(Looper looper, String name) {
+        mName = name;
+        mHsmHandler = new HsmHandler(looper, this);
+    }
+
+    /**
+     * Constructor creates an HSM with its own thread.
+     *
+     * @param name of the state machine
+     */
+    protected HierarchicalStateMachine(String name) {
+        mHsmThread = new HandlerThread(name);
+        mHsmThread.start();
+        Looper looper = mHsmThread.getLooper();
+
+        initStateMachine(looper, name);
+    }
+
+    /**
+     * Constructor creates an HSMStateMachine using the looper.
+     *
+     * @param name of the state machine
+     */
+    protected HierarchicalStateMachine(Looper looper, String name) {
+        initStateMachine(looper, name);
+    }
+
+    /**
+     * Add a new state to the state machine
+     * @param state the state to add
+     * @param parent the parent of state
+     */
+    protected final void addState(HierarchicalState state, HierarchicalState parent) {
+        mHsmHandler.addState(state, parent);
+    }
+    /**
+     * @return current state
+     */
+    protected final HierarchicalState getCurrentState() {
+        return mHsmHandler.getCurrentState();
+    }
+
+
+    /**
+     * Add a new state to the state machine, parent will be null
+     * @param state to add
+     */
+    protected final void addState(HierarchicalState state) {
+        mHsmHandler.addState(state, null);
+    }
+
+    /**
+     * Set the initial state. This must be invoked before
+     * and messages are sent to the state machine.
+     *
+     * @param initialState is the state which will receive the first message.
+     */
+    protected final void setInitialState(HierarchicalState initialState) {
+        mHsmHandler.setInitialState(initialState);
+    }
+
+    /**
+     * transition to destination state. Upon returning
+     * from processMessage the current state's exit will
+     * be executed and upon the next message arriving
+     * destState.enter will be invoked.
+     *
+     * @param destState will be the state that receives the next message.
+     */
+    protected final void transitionTo(HierarchicalState destState) {
+        mHsmHandler.transitionTo(destState);
+    }
+
+    /**
+     * transition to halt state. Upon returning
+     * from processMessage we will exit all current
+     * states, execute the halting() method and then
+     * all subsequent messages haltedProcessMesage
+     * will be called.
+     */
+    protected final void transitionToHaltingState() {
+        mHsmHandler.transitionTo(mHsmHandler.mHaltingState);
+    }
+
+    /**
+     * Defer this message until next state transition.
+     * Upon transitioning all deferred messages will be
+     * placed on the queue and reprocessed in the original
+     * order. (i.e. The next state the oldest messages will
+     * be processed first)
+     *
+     * @param msg is deferred until the next transition.
+     */
+    protected final void deferMessage(Message msg) {
+        mHsmHandler.deferMessage(msg);
+    }
+
+
+    /**
+     * Called when message wasn't handled
+     *
+     * @param msg that couldn't be handled.
+     */
+    protected void unhandledMessage(Message msg) {
+        Log.e(TAG, "unhandledMessage: msg.what=" + msg.what);
+    }
+
+    /**
+     * Called for any message that is received after
+     * transitionToHalting is called.
+     */
+    protected void haltedProcessMessage(Message msg) {
+    }
+
+    /**
+     * Called after the message that called transitionToHalting
+     * is called and should be overridden by StateMachine's that
+     * call transitionToHalting.
+     */
+    protected void halting() {
+    }
+
+    /**
+     * @return the name
+     */
+    public final String getName() {
+        return mName;
+    }
+
+    /**
+     * Set size of messages to maintain and clears all current messages.
+     *
+     * @param maxSize number of messages to maintain at anyone time.
+     */
+    public final void setProcessedMessagesSize(int maxSize) {
+        mHsmHandler.setProcessedMessagesSize(maxSize);
+    }
+
+    /**
+     * @return number of messages processed
+     */
+    public final int getProcessedMessagesSize() {
+        return mHsmHandler.getProcessedMessagesSize();
+    }
+
+    /**
+     * @return the total number of messages processed
+     */
+    public final int getProcessedMessagesCount() {
+        return mHsmHandler.getProcessedMessagesCount();
+    }
+
+    /**
+     * @return a processed message
+     */
+    public final ProcessedMessages.Info getProcessedMessage(int index) {
+        return mHsmHandler.getProcessedMessage(index);
+    }
+
+    /**
+     * @return Handler
+     */
+    public final Handler getHandler() {
+        return mHsmHandler;
+    }
+
+    /**
+     * Get a message and set Message.target = this.
+     *
+     * @return message
+     */
+    public final Message obtainMessage()
+    {
+        return Message.obtain(mHsmHandler);
+    }
+
+    /**
+     * Get a message and set Message.target = this and what
+     *
+     * @param what is the assigned to Message.what.
+     * @return message
+     */
+    public final Message obtainMessage(int what) {
+        return Message.obtain(mHsmHandler, what);
+    }
+
+    /**
+     * Get a message and set Message.target = this,
+     * what and obj.
+     *
+     * @param what is the assigned to Message.what.
+     * @param obj is assigned to Message.obj.
+     * @return message
+     */
+    public final Message obtainMessage(int what, Object obj)
+    {
+        return Message.obtain(mHsmHandler, what, obj);
+    }
+
+    /**
+     * Enqueue a message to this state machine.
+     */
+    public final void sendMessage(Message msg) {
+        mHsmHandler.sendMessage(msg);
+    }
+
+    /**
+     * Enqueue a message to this state machine after a delay.
+     */
+    public final void sendMessageDelayed(Message msg, long delayMillis) {
+        mHsmHandler.sendMessageDelayed(msg, delayMillis);
+    }
+
+    /**
+     * Enqueue a message to the front of the queue for this state machine.
+     * Protected, may only be called by instances of HierarchicalStateMachine.
+     */
+    protected final void sendMessageAtFrontOfQueue(Message msg) {
+        mHsmHandler.sendMessageAtFrontOfQueue(msg);
+    }
+
+    /**
+     * @return if debugging is enabled
+     */
+    public boolean isDbg() {
+        return mHsmHandler.isDbg();
+    }
+
+    /**
+     * Set debug enable/disabled.
+     *
+     * @param dbg is true to enable debugging.
+     */
+    public void setDbg(boolean dbg) {
+        mHsmHandler.setDbg(dbg);
+    }
+
+    /**
+     * Start the state machine.
+     */
+    public void start() {
+        /** Send the complete construction message */
+        mHsmHandler.completeConstruction();
+    }
+}
diff --git a/core/java/com/android/internal/util/ProcessedMessages.java b/core/java/com/android/internal/util/ProcessedMessages.java
new file mode 100644
index 000000000000..244474e31bd0
--- /dev/null
+++ b/core/java/com/android/internal/util/ProcessedMessages.java
@@ -0,0 +1,198 @@
+/**
+ * Copyright (C) 2009 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.internal.util;
+
+import android.os.Message;
+
+import java.util.Vector;
+
+/**
+ * {@hide}
+ *
+ * A list of messages recently processed by the state machine.
+ *
+ * The class maintains a list of messages that have been most
+ * recently processed. The list is finite and may be set in the
+ * constructor or by calling setSize. The public interface also
+ * includes size which returns the number of recent messages,
+ * count which is the number of message processed since the
+ * the last setSize, get which returns a processed message and
+ * add which adds a processed messaged.
+ */
+public class ProcessedMessages {
+
+    public static final int DEFAULT_SIZE = 20;
+
+    /**
+     * The information maintained for a processed message.
+     */
+    public class Info {
+        private int what;
+        private HierarchicalState state;
+        private HierarchicalState orgState;
+
+        /**
+         * Constructor
+         * @param message
+         * @param state that handled the message
+         * @param orgState is the first state the received the message but
+         * did not processes the message.
+         */
+        Info(Message message, HierarchicalState state, HierarchicalState orgState) {
+            update(message, state, orgState);
+        }
+
+        /**
+         * Update the information in the record.
+         * @param state that handled the message
+         * @param orgState is the first state the received the message but
+         * did not processes the message.
+         */
+        public void update(Message message, HierarchicalState state, HierarchicalState orgState) {
+            this.what = message.what;
+            this.state = state;
+            this.orgState = orgState;
+        }
+
+        /**
+         * @return the command that was executing
+         */
+        public int getWhat() {
+            return what;
+        }
+
+        /**
+         * @return the state that handled this message
+         */
+        public HierarchicalState getState() {
+            return state;
+        }
+
+        /**
+         * @return the original state that received the message.
+         */
+        public HierarchicalState getOriginalState() {
+            return orgState;
+        }
+
+        /**
+         * @return as string
+         */
+        public String toString() {
+            StringBuilder sb = new StringBuilder();
+            sb.append("what=");
+            sb.append(what);
+            sb.append(" state=");
+            sb.append(cn(state));
+            sb.append(" orgState=");
+            sb.append(cn(orgState));
+            return sb.toString();
+        }
+
+        /**
+         * @return an objects class name
+         */
+        private String cn(Object n) {
+            if (n == null) {
+                return "null";
+            } else {
+                String name = n.getClass().getName();
+                int lastDollar = name.lastIndexOf('$');
+                return name.substring(lastDollar + 1);
+            }
+        }
+    }
+
+    private Vector<Info> mMessages = new Vector<Info>();
+    private int mMaxSize = DEFAULT_SIZE;
+    private int mOldestIndex = 0;
+    private int mCount = 0;
+
+    /**
+     * Constructor
+     */
+    ProcessedMessages() {
+    }
+
+    ProcessedMessages(int maxSize) {
+        setSize(maxSize);
+    }
+
+    /**
+     * Set size of messages to maintain and clears all current messages.
+     *
+     * @param maxSize number of messages to maintain at anyone time.
+    */
+    void setSize(int maxSize) {
+        mMaxSize = maxSize;
+        mCount = 0;
+        mMessages.clear();
+    }
+
+    /**
+     * @return the number of recent messages.
+     */
+    int size() {
+        return mMessages.size();
+    }
+
+    /**
+     * @return the total number of messages processed since size was set.
+     */
+    int count() {
+        return mCount;
+    }
+
+    /**
+     * @return the information on a particular record. 0 is the oldest
+     * record and size()-1 is the newest record. If the index is to
+     * large null is returned.
+     */
+    Info get(int index) {
+        int nextIndex = mOldestIndex + index;
+        if (nextIndex >= mMaxSize) {
+            nextIndex -= mMaxSize;
+        }
+        if (nextIndex >= size()) {
+            return null;
+        } else {
+            return mMessages.get(nextIndex);
+        }
+    }
+
+    /**
+     * Add a processed message.
+     *
+     * @param message
+     * @param state that handled the message
+     * @param orgState is the first state the received the message but
+     * did not processes the message.
+     */
+    void add(Message message, HierarchicalState state, HierarchicalState orgState) {
+        mCount += 1;
+        if (mMessages.size() < mMaxSize) {
+            mMessages.add(new Info(message, state, orgState));
+        } else {
+            Info info = mMessages.get(mOldestIndex);
+            mOldestIndex += 1;
+            if (mOldestIndex >= mMaxSize) {
+                mOldestIndex = 0;
+            }
+            info.update(message, state, orgState);
+        }
+    }
+}
diff --git a/telephony/java/com/android/internal/telephony/gsm/stk/CommandParamsFactory.java b/telephony/java/com/android/internal/telephony/gsm/stk/CommandParamsFactory.java
index bfde616639f5..ce4c459100e5 100644
--- a/telephony/java/com/android/internal/telephony/gsm/stk/CommandParamsFactory.java
+++ b/telephony/java/com/android/internal/telephony/gsm/stk/CommandParamsFactory.java
@@ -203,7 +203,7 @@ class CommandParamsFactory extends Handler {
     }
 
     private void sendCmdParams(ResultCode resCode) {
-        mCaller.sendMessageParamsDecoded(resCode, mCmdParams);
+        mCaller.sendMsgParamsDecoded(resCode, mCmdParams);
     }
 
     /**
diff --git a/telephony/java/com/android/internal/telephony/gsm/stk/RilMessageDecoder.java b/telephony/java/com/android/internal/telephony/gsm/stk/RilMessageDecoder.java
index 1cf38ed07cb7..a82177cd330d 100644
--- a/telephony/java/com/android/internal/telephony/gsm/stk/RilMessageDecoder.java
+++ b/telephony/java/com/android/internal/telephony/gsm/stk/RilMessageDecoder.java
@@ -20,18 +20,18 @@ import com.android.internal.telephony.gsm.SIMFileHandler;
 import com.android.internal.telephony.IccUtils;
 
 import android.os.Handler;
-import android.os.HandlerState;
-import android.os.HandlerStateMachine;
+import com.android.internal.util.HierarchicalState;
+import com.android.internal.util.HierarchicalStateMachine;
 import android.os.Message;
 
 /**
  * Class used for queuing raw ril messages, decoding them into CommanParams
  * objects and sending the result back to the STK Service.
  */
-class RilMessageDecoder extends HandlerStateMachine {
+class RilMessageDecoder extends HierarchicalStateMachine {
 
     // constants
-    private static final int START = 1;
+    private static final int CMD_START = 1;
     private static final int CMD_PARAMS_READY = 2;
 
     // members
@@ -54,6 +54,7 @@ class RilMessageDecoder extends HandlerStateMachine {
     public static synchronized RilMessageDecoder getInstance(Handler caller, SIMFileHandler fh) {
         if (sInstance == null) {
             sInstance = new RilMessageDecoder(caller, fh);
+            sInstance.start();
         }
         return sInstance;
     }
@@ -65,7 +66,7 @@ class RilMessageDecoder extends HandlerStateMachine {
      * @param rilMsg
      */
     public void sendStartDecodingMessageParams(RilMessage rilMsg) {
-        Message msg = obtainMessage(START);
+        Message msg = obtainMessage(CMD_START);
         msg.obj = rilMsg;
         sendMessage(msg);
     }
@@ -76,7 +77,7 @@ class RilMessageDecoder extends HandlerStateMachine {
      * @param resCode
      * @param cmdParams
      */
-    public void sendMessageParamsDecoded(ResultCode resCode, CommandParams cmdParams) {
+    public void sendMsgParamsDecoded(ResultCode resCode, CommandParams cmdParams) {
         Message msg = obtainMessage(RilMessageDecoder.CMD_PARAMS_READY);
         msg.arg1 = resCode.value();
         msg.obj = cmdParams;
@@ -91,28 +92,31 @@ class RilMessageDecoder extends HandlerStateMachine {
 
     private RilMessageDecoder(Handler caller, SIMFileHandler fh) {
         super("RilMessageDecoder");
-        setDbg(false);
+
+        addState(mStateStart);
+        addState(mStateCmdParamsReady);
         setInitialState(mStateStart);
 
         mCaller = caller;
         mCmdParamsFactory = CommandParamsFactory.getInstance(this, fh);
     }
 
-    private class StateStart extends HandlerState {
-        @Override public void processMessage(Message msg) {
-            if (msg.what == START) {
+    private class StateStart extends HierarchicalState {
+        @Override protected boolean processMessage(Message msg) {
+            if (msg.what == CMD_START) {
                 if (decodeMessageParams((RilMessage)msg.obj)) {
                     transitionTo(mStateCmdParamsReady);
                 }
             } else {
                 StkLog.d(this, "StateStart unexpected expecting START=" +
-                         START + " got " + msg.what);
+                         CMD_START + " got " + msg.what);
             }
+            return true;
         }
     }
 
-    private class StateCmdParamsReady extends HandlerState {
-        @Override public void processMessage(Message msg) {
+    private class StateCmdParamsReady extends HierarchicalState {
+        @Override protected boolean processMessage(Message msg) {
             if (msg.what == CMD_PARAMS_READY) {
                 mCurrentRilMessage.mResCode = ResultCode.fromInt(msg.arg1);
                 mCurrentRilMessage.mData = msg.obj;
@@ -123,6 +127,7 @@ class RilMessageDecoder extends HandlerStateMachine {
                          + CMD_PARAMS_READY + " got " + msg.what);
                 deferMessage(msg);
             }
+            return true;
         }
     }
 
diff --git a/tests/AndroidTests/src/com/android/unit_tests/os/HandlerStateMachineTest.java b/tests/AndroidTests/src/com/android/unit_tests/os/HandlerStateMachineTest.java
deleted file mode 100644
index 29045a397ae8..000000000000
--- a/tests/AndroidTests/src/com/android/unit_tests/os/HandlerStateMachineTest.java
+++ /dev/null
@@ -1,119 +0,0 @@
-/*
- * Copyright (C) 2006 The Android Open Source Project
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- *      http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-package com.android.unit_tests.os;
-
-import junit.framework.TestCase;
-import java.util.Vector;
-
-import android.os.Handler;
-import android.os.HandlerState;
-import android.os.HandlerStateMachine;
-import android.os.HandlerThread;
-import android.os.Looper;
-import android.os.Process;
-import android.os.Message;
-import android.test.suitebuilder.annotation.MediumTest;
-import android.test.suitebuilder.annotation.SmallTest;
-
-import android.util.Log;
-
-public class HandlerStateMachineTest extends TestCase {
-    private static final int TEST_WHAT_1 = 1;
-    private static final int TEST_WHAT_2 = 2;
-
-    private static final boolean DBG = false;
-    private static final String TAG = "HandlerStateMachineTest";
-
-    private boolean mDidEnter = false;
-    private boolean mDidExit = false;
-    private Vector<Integer> mGotMessagesWhat = new Vector<Integer>();
-
-    /**
-     * This test statemachine has two states, it receives
-     * two messages in state mS1 deferring them until what == TEST_WHAT_2
-     * and then transitions to state mS2. State mS2 should then receive
-     * both of the deferred messages first TEST_WHAT_1 and then TEST_WHAT_2.
-     * When TEST_WHAT_2 is received it invokes notifyAll so the test can
-     * conclude.
-     */
-    class StateMachine1 extends HandlerStateMachine {
-        StateMachine1(String name) {
-            super(name);
-            mThisSm = this;
-            setDbg(DBG);
-            setInitialState(mS1);
-        }
-
-        class S1 extends HandlerState {
-            @Override public void enter(Message message) {
-                mDidEnter = true;
-            }
-
-            @Override public void processMessage(Message message) {
-                deferMessage(message);
-                if (message.what == TEST_WHAT_2) {
-                    transitionTo(mS2);
-                }
-            }
-
-            @Override public void exit(Message message) {
-                mDidExit = true;
-            }
-        }
-
-        class S2 extends HandlerState {
-            @Override public void processMessage(Message message) {
-                mGotMessagesWhat.add(message.what);
-                if (message.what == TEST_WHAT_2) {
-                    synchronized (mThisSm) {
-                        mThisSm.notifyAll();
-                    }
-                }
-            }
-        }
-
-        private StateMachine1 mThisSm;
-        private S1 mS1 = new S1();
-        private S2 mS2 = new S2();
-    }
-
-    @SmallTest
-    public void testStateMachine1() throws Exception {
-        StateMachine1 sm1 = new StateMachine1("sm1");
-        if (sm1.isDbg()) Log.d(TAG, "testStateMachine1 E");
-
-        synchronized (sm1) {
-            // Send two messages
-            sm1.sendMessage(sm1.obtainMessage(TEST_WHAT_1));
-            sm1.sendMessage(sm1.obtainMessage(TEST_WHAT_2));
-
-            try {
-                // wait for the messages to be handled
-                sm1.wait();
-            } catch (InterruptedException e) {
-                Log.e(TAG, "testStateMachine1: exception while waiting " + e.getMessage());
-            }
-        }
-
-        assertTrue(mDidEnter);
-        assertTrue(mDidExit);
-        assertTrue(mGotMessagesWhat.size() == 2);
-        assertTrue(mGotMessagesWhat.get(0) == TEST_WHAT_1);
-        assertTrue(mGotMessagesWhat.get(1) == TEST_WHAT_2);
-        if (sm1.isDbg()) Log.d(TAG, "testStateMachine1 X");
-    }
-}
diff --git a/tests/AndroidTests/src/com/android/unit_tests/os/HierarchicalStateMachineTest.java b/tests/AndroidTests/src/com/android/unit_tests/os/HierarchicalStateMachineTest.java
new file mode 100644
index 000000000000..c5ca5a721118
--- /dev/null
+++ b/tests/AndroidTests/src/com/android/unit_tests/os/HierarchicalStateMachineTest.java
@@ -0,0 +1,1392 @@
+/**
+ * Copyright (C) 2009 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.unit_tests.os;
+
+import junit.framework.TestCase;
+
+import android.os.Debug;
+import android.os.HandlerThread;
+import android.os.Looper;
+import android.os.Message;
+import android.os.SystemClock;
+import android.test.suitebuilder.annotation.SmallTest;
+
+import android.util.Log;
+
+import com.android.internal.util.HierarchicalStateMachine;
+import com.android.internal.util.HierarchicalState;
+import com.android.internal.util.ProcessedMessages;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+
+/**
+ * Test for HierarchicalStateMachine.
+ *
+ * @author wink@google.com (Wink Saville)
+ */
+public class HierarchicalStateMachineTest extends TestCase {
+    private static final int TEST_CMD_1 = 1;
+    private static final int TEST_CMD_2 = 2;
+    private static final int TEST_CMD_3 = 3;
+    private static final int TEST_CMD_4 = 4;
+    private static final int TEST_CMD_5 = 5;
+    private static final int TEST_CMD_6 = 6;
+
+    private static final boolean DBG = true;
+    private static final boolean WAIT_FOR_DEBUGGER = false;
+    private static final String TAG = "HierarchicalStateMachineTest";
+
+    /**
+     * Tests that ProcessedMessage works as a circular buffer.
+     */
+    class StateMachine0 extends HierarchicalStateMachine {
+        StateMachine0(String name) {
+            super(name);
+            mThisSm = this;
+            setDbg(DBG);
+            setProcessedMessagesSize(3);
+
+            // Setup state machine with 1 state
+            addState(mS1);
+
+            // Set the initial state
+            setInitialState(mS1);
+        }
+
+        class S1 extends HierarchicalState {
+            @Override protected boolean processMessage(Message message) {
+                if (message.what == TEST_CMD_6) {
+                    transitionToHaltingState();
+                }
+                return true;
+            }
+        }
+
+        @Override
+        protected void halting() {
+            synchronized (mThisSm) {
+                mThisSm.notifyAll();
+            }
+        }
+
+        private StateMachine0 mThisSm;
+        private S1 mS1 = new S1();
+    }
+
+    @SmallTest
+    public void testStateMachine0() throws Exception {
+        if (WAIT_FOR_DEBUGGER) Debug.waitForDebugger();
+
+        StateMachine0 sm0 = new StateMachine0("sm0");
+        sm0.start();
+        if (sm0.isDbg()) Log.d(TAG, "testStateMachine0 E");
+
+        synchronized (sm0) {
+            // Send 6 messages
+            for (int i = 1; i <= 6; i++) {
+                sm0.sendMessage(sm0.obtainMessage(i));
+            }
+
+            try {
+                // wait for the messages to be handled
+                sm0.wait();
+            } catch (InterruptedException e) {
+                Log.e(TAG, "testStateMachine0: exception while waiting " + e.getMessage());
+            }
+        }
+
+        assertTrue(sm0.getProcessedMessagesCount() == 6);
+        assertTrue(sm0.getProcessedMessagesSize() == 3);
+
+        ProcessedMessages.Info pmi;
+        pmi = sm0.getProcessedMessage(0);
+        assertEquals(TEST_CMD_4, pmi.getWhat());
+        assertEquals(sm0.mS1, pmi.getState());
+        assertEquals(sm0.mS1, pmi.getOriginalState());
+
+        pmi = sm0.getProcessedMessage(1);
+        assertEquals(TEST_CMD_5, pmi.getWhat());
+        assertEquals(sm0.mS1, pmi.getState());
+        assertEquals(sm0.mS1, pmi.getOriginalState());
+
+        pmi = sm0.getProcessedMessage(2);
+        assertEquals(TEST_CMD_6, pmi.getWhat());
+        assertEquals(sm0.mS1, pmi.getState());
+        assertEquals(sm0.mS1, pmi.getOriginalState());
+
+        if (sm0.isDbg()) Log.d(TAG, "testStateMachine0 X");
+    }
+
+    /**
+     * This tests enter/exit and transitions to the same state.
+     * The state machine has one state, it receives two messages
+     * in state mS1. With the first message it transitions to
+     * itself which causes it to be exited and reentered.
+     */
+    class StateMachine1 extends HierarchicalStateMachine {
+        StateMachine1(String name) {
+            super(name);
+            mThisSm = this;
+            setDbg(DBG);
+
+            // Setup state machine with 1 state
+            addState(mS1);
+
+            // Set the initial state
+            setInitialState(mS1);
+            if (DBG) Log.d(TAG, "StateMachine1: ctor X");
+        }
+
+        class S1 extends HierarchicalState {
+            @Override protected void enter() {
+                mEnterCount++;
+            }
+
+            @Override protected boolean processMessage(Message message) {
+                if (message.what == TEST_CMD_1) {
+                    assertEquals(1, mEnterCount);
+                    assertEquals(0, mExitCount);
+                    transitionTo(mS1);
+                } else if (message.what == TEST_CMD_2) {
+                    assertEquals(2, mEnterCount);
+                    assertEquals(1, mExitCount);
+                    transitionToHaltingState();
+                }
+                return true;
+            }
+
+            @Override protected void exit() {
+                mExitCount++;
+            }
+        }
+
+        @Override
+        protected void halting() {
+            synchronized (mThisSm) {
+                mThisSm.notifyAll();
+            }
+        }
+
+        private StateMachine1 mThisSm;
+        private S1 mS1 = new S1();
+
+        private int mEnterCount;
+        private int mExitCount;
+    }
+
+    @SmallTest
+    public void testStateMachine1() throws Exception {
+        StateMachine1 sm1 = new StateMachine1("sm1");
+        sm1.start();
+        if (sm1.isDbg()) Log.d(TAG, "testStateMachine1 E");
+
+        synchronized (sm1) {
+            // Send two messages
+            sm1.sendMessage(sm1.obtainMessage(TEST_CMD_1));
+            sm1.sendMessage(sm1.obtainMessage(TEST_CMD_2));
+
+            try {
+                // wait for the messages to be handled
+                sm1.wait();
+            } catch (InterruptedException e) {
+                Log.e(TAG, "testStateMachine1: exception while waiting " + e.getMessage());
+            }
+        }
+
+        assertEquals(2, sm1.mEnterCount);
+        assertEquals(2, sm1.mExitCount);
+
+        assertTrue(sm1.getProcessedMessagesSize() == 2);
+
+        ProcessedMessages.Info pmi;
+        pmi = sm1.getProcessedMessage(0);
+        assertEquals(TEST_CMD_1, pmi.getWhat());
+        assertEquals(sm1.mS1, pmi.getState());
+        assertEquals(sm1.mS1, pmi.getOriginalState());
+
+        pmi = sm1.getProcessedMessage(1);
+        assertEquals(TEST_CMD_2, pmi.getWhat());
+        assertEquals(sm1.mS1, pmi.getState());
+        assertEquals(sm1.mS1, pmi.getOriginalState());
+
+        assertEquals(2, sm1.mEnterCount);
+        assertEquals(2, sm1.mExitCount);
+
+        if (sm1.isDbg()) Log.d(TAG, "testStateMachine1 X");
+    }
+
+    /**
+     * Test deferring messages and states with no parents. The state machine
+     * has two states, it receives two messages in state mS1 deferring them
+     * until what == TEST_CMD_2 and then transitions to state mS2. State
+     * mS2 then receives both of the deferred messages first TEST_CMD_1 and
+     * then TEST_CMD_2.
+     */
+    class StateMachine2 extends HierarchicalStateMachine {
+        StateMachine2(String name) {
+            super(name);
+            mThisSm = this;
+            setDbg(DBG);
+
+            // Setup the hierarchy
+            addState(mS1);
+            addState(mS2);
+
+            // Set the initial state
+            setInitialState(mS1);
+            if (DBG) Log.d(TAG, "StateMachine2: ctor X");
+        }
+
+        class S1 extends HierarchicalState {
+            @Override protected void enter() {
+                mDidEnter = true;
+            }
+
+            @Override protected boolean processMessage(Message message) {
+                deferMessage(message);
+                if (message.what == TEST_CMD_2) {
+                    transitionTo(mS2);
+                }
+                return true;
+            }
+
+            @Override protected void exit() {
+                mDidExit = true;
+            }
+        }
+
+        class S2 extends HierarchicalState {
+            @Override protected boolean processMessage(Message message) {
+                if (message.what == TEST_CMD_2) {
+                    transitionToHaltingState();
+                }
+                return true;
+            }
+        }
+
+        @Override
+        protected void halting() {
+            synchronized (mThisSm) {
+                mThisSm.notifyAll();
+            }
+        }
+
+        private StateMachine2 mThisSm;
+        private S1 mS1 = new S1();
+        private S2 mS2 = new S2();
+
+        private boolean mDidEnter = false;
+        private boolean mDidExit = false;
+    }
+
+    @SmallTest
+    public void testStateMachine2() throws Exception {
+        StateMachine2 sm2 = new StateMachine2("sm2");
+        sm2.start();
+        if (sm2.isDbg()) Log.d(TAG, "testStateMachine2 E");
+
+        synchronized (sm2) {
+            // Send two messages
+            sm2.sendMessage(sm2.obtainMessage(TEST_CMD_1));
+            sm2.sendMessage(sm2.obtainMessage(TEST_CMD_2));
+
+            try {
+                // wait for the messages to be handled
+                sm2.wait();
+            } catch (InterruptedException e) {
+                Log.e(TAG, "testStateMachine2: exception while waiting " + e.getMessage());
+            }
+        }
+
+        assertTrue(sm2.getProcessedMessagesSize() == 4);
+
+        ProcessedMessages.Info pmi;
+        pmi = sm2.getProcessedMessage(0);
+        assertEquals(TEST_CMD_1, pmi.getWhat());
+        assertEquals(sm2.mS1, pmi.getState());
+
+        pmi = sm2.getProcessedMessage(1);
+        assertEquals(TEST_CMD_2, pmi.getWhat());
+        assertEquals(sm2.mS1, pmi.getState());
+
+        pmi = sm2.getProcessedMessage(2);
+        assertEquals(TEST_CMD_1, pmi.getWhat());
+        assertEquals(sm2.mS2, pmi.getState());
+
+        pmi = sm2.getProcessedMessage(3);
+        assertEquals(TEST_CMD_2, pmi.getWhat());
+        assertEquals(sm2.mS2, pmi.getState());
+
+        assertTrue(sm2.mDidEnter);
+        assertTrue(sm2.mDidExit);
+
+        if (sm2.isDbg()) Log.d(TAG, "testStateMachine2 X");
+    }
+
+    /**
+     * Test that unhandled messages in a child are handled by the parent.
+     * When TEST_CMD_2 is received.
+     */
+    class StateMachine3 extends HierarchicalStateMachine {
+        StateMachine3(String name) {
+            super(name);
+            mThisSm = this;
+            setDbg(DBG);
+
+            // Setup the simplest hierarchy of two states
+            // mParentState and mChildState.
+            // (Use indentation to help visualize hierarchy)
+            addState(mParentState);
+                addState(mChildState, mParentState);
+
+            // Set the initial state will be the child
+            setInitialState(mChildState);
+            if (DBG) Log.d(TAG, "StateMachine3: ctor X");
+        }
+
+        class ParentState extends HierarchicalState {
+            @Override protected boolean processMessage(Message message) {
+                if (message.what == TEST_CMD_2) {
+                    transitionToHaltingState();
+                }
+                return true;
+            }
+        }
+
+        class ChildState extends HierarchicalState {
+            @Override protected boolean processMessage(Message message) {
+                return false;
+            }
+        }
+
+        @Override
+        protected void halting() {
+            synchronized (mThisSm) {
+                mThisSm.notifyAll();
+            }
+        }
+
+        private StateMachine3 mThisSm;
+        private ParentState mParentState = new ParentState();
+        private ChildState mChildState = new ChildState();
+    }
+
+    @SmallTest
+    public void testStateMachine3() throws Exception {
+        StateMachine3 sm3 = new StateMachine3("sm3");
+        sm3.start();
+        if (sm3.isDbg()) Log.d(TAG, "testStateMachine3 E");
+
+        synchronized (sm3) {
+            // Send two messages
+            sm3.sendMessage(sm3.obtainMessage(TEST_CMD_1));
+            sm3.sendMessage(sm3.obtainMessage(TEST_CMD_2));
+
+            try {
+                // wait for the messages to be handled
+                sm3.wait();
+            } catch (InterruptedException e) {
+                Log.e(TAG, "testStateMachine3: exception while waiting " + e.getMessage());
+            }
+        }
+
+        assertTrue(sm3.getProcessedMessagesSize() == 2);
+
+        ProcessedMessages.Info pmi;
+        pmi = sm3.getProcessedMessage(0);
+        assertEquals(TEST_CMD_1, pmi.getWhat());
+        assertEquals(sm3.mParentState, pmi.getState());
+        assertEquals(sm3.mChildState, pmi.getOriginalState());
+
+        pmi = sm3.getProcessedMessage(1);
+        assertEquals(TEST_CMD_2, pmi.getWhat());
+        assertEquals(sm3.mParentState, pmi.getState());
+        assertEquals(sm3.mChildState, pmi.getOriginalState());
+
+        if (sm3.isDbg()) Log.d(TAG, "testStateMachine3 X");
+    }
+
+    /**
+     * Test a hierarchy of 3 states a parent and two children
+     * with transition from child 1 to child 2 and child 2
+     * lets the parent handle the messages.
+     */
+    class StateMachine4 extends HierarchicalStateMachine {
+        StateMachine4(String name) {
+            super(name);
+            mThisSm = this;
+            setDbg(DBG);
+
+            // Setup a hierarchy of three states
+            // mParentState, mChildState1 & mChildState2
+            // (Use indentation to help visualize hierarchy)
+            addState(mParentState);
+                addState(mChildState1, mParentState);
+                addState(mChildState2, mParentState);
+
+            // Set the initial state will be child 1
+            setInitialState(mChildState1);
+            if (DBG) Log.d(TAG, "StateMachine4: ctor X");
+        }
+
+        class ParentState extends HierarchicalState {
+            @Override protected boolean processMessage(Message message) {
+                if (message.what == TEST_CMD_2) {
+                    transitionToHaltingState();
+                }
+                return true;
+            }
+        }
+
+        class ChildState1 extends HierarchicalState {
+            @Override protected boolean processMessage(Message message) {
+                transitionTo(mChildState2);
+                return true;
+            }
+        }
+
+        class ChildState2 extends HierarchicalState {
+            @Override protected boolean processMessage(Message message) {
+                return false;
+            }
+        }
+
+        @Override
+        protected void halting() {
+            synchronized (mThisSm) {
+                mThisSm.notifyAll();
+            }
+        }
+
+        private StateMachine4 mThisSm;
+        private ParentState mParentState = new ParentState();
+        private ChildState1 mChildState1 = new ChildState1();
+        private ChildState2 mChildState2 = new ChildState2();
+    }
+
+    @SmallTest
+    public void testStateMachine4() throws Exception {
+        StateMachine4 sm4 = new StateMachine4("sm4");
+        sm4.start();
+        if (sm4.isDbg()) Log.d(TAG, "testStateMachine4 E");
+
+        synchronized (sm4) {
+            // Send two messages
+            sm4.sendMessage(sm4.obtainMessage(TEST_CMD_1));
+            sm4.sendMessage(sm4.obtainMessage(TEST_CMD_2));
+
+            try {
+                // wait for the messages to be handled
+                sm4.wait();
+            } catch (InterruptedException e) {
+                Log.e(TAG, "testStateMachine4: exception while waiting " + e.getMessage());
+            }
+        }
+
+
+        assertTrue(sm4.getProcessedMessagesSize() == 2);
+
+        ProcessedMessages.Info pmi;
+        pmi = sm4.getProcessedMessage(0);
+        assertEquals(TEST_CMD_1, pmi.getWhat());
+        assertEquals(sm4.mChildState1, pmi.getState());
+        assertEquals(sm4.mChildState1, pmi.getOriginalState());
+
+        pmi = sm4.getProcessedMessage(1);
+        assertEquals(TEST_CMD_2, pmi.getWhat());
+        assertEquals(sm4.mParentState, pmi.getState());
+        assertEquals(sm4.mChildState2, pmi.getOriginalState());
+
+        if (sm4.isDbg()) Log.d(TAG, "testStateMachine4 X");
+    }
+
+    /**
+     * Test transition from one child to another of a "complex"
+     * hierarchy with two parents and multiple children.
+     */
+    class StateMachine5 extends HierarchicalStateMachine {
+        StateMachine5(String name) {
+            super(name);
+            mThisSm = this;
+            setDbg(DBG);
+
+            // Setup a hierarchy with two parents and some children.
+            // (Use indentation to help visualize hierarchy)
+            addState(mParentState1);
+                addState(mChildState1, mParentState1);
+                addState(mChildState2, mParentState1);
+
+            addState(mParentState2);
+                addState(mChildState3, mParentState2);
+                addState(mChildState4, mParentState2);
+                    addState(mChildState5, mChildState4);
+
+            // Set the initial state will be the child
+            setInitialState(mChildState1);
+            if (DBG) Log.d(TAG, "StateMachine5: ctor X");
+        }
+
+        class ParentState1 extends HierarchicalState {
+            @Override protected void enter() {
+                mParentState1EnterCount += 1;
+            }
+            @Override protected boolean processMessage(Message message) {
+                return true;
+            }
+            @Override protected void exit() {
+                mParentState1ExitCount += 1;
+            }
+        }
+
+        class ChildState1 extends HierarchicalState {
+            @Override protected void enter() {
+                mChildState1EnterCount += 1;
+            }
+            @Override protected boolean processMessage(Message message) {
+                assertEquals(1, mParentState1EnterCount);
+                assertEquals(0, mParentState1ExitCount);
+                assertEquals(1, mChildState1EnterCount);
+                assertEquals(0, mChildState1ExitCount);
+                assertEquals(0, mChildState2EnterCount);
+                assertEquals(0, mChildState2ExitCount);
+                assertEquals(0, mParentState2EnterCount);
+                assertEquals(0, mParentState2ExitCount);
+                assertEquals(0, mChildState3EnterCount);
+                assertEquals(0, mChildState3ExitCount);
+                assertEquals(0, mChildState4EnterCount);
+                assertEquals(0, mChildState4ExitCount);
+                assertEquals(0, mChildState5EnterCount);
+                assertEquals(0, mChildState5ExitCount);
+
+                transitionTo(mChildState2);
+                return true;
+            }
+            @Override protected void exit() {
+                mChildState1ExitCount += 1;
+            }
+        }
+
+        class ChildState2 extends HierarchicalState {
+            @Override protected void enter() {
+                mChildState2EnterCount += 1;
+            }
+            @Override protected boolean processMessage(Message message) {
+                assertEquals(1, mParentState1EnterCount);
+                assertEquals(0, mParentState1ExitCount);
+                assertEquals(1, mChildState1EnterCount);
+                assertEquals(1, mChildState1ExitCount);
+                assertEquals(1, mChildState2EnterCount);
+                assertEquals(0, mChildState2ExitCount);
+                assertEquals(0, mParentState2EnterCount);
+                assertEquals(0, mParentState2ExitCount);
+                assertEquals(0, mChildState3EnterCount);
+                assertEquals(0, mChildState3ExitCount);
+                assertEquals(0, mChildState4EnterCount);
+                assertEquals(0, mChildState4ExitCount);
+                assertEquals(0, mChildState5EnterCount);
+                assertEquals(0, mChildState5ExitCount);
+
+                transitionTo(mChildState5);
+                return true;
+            }
+            @Override protected void exit() {
+                mChildState2ExitCount += 1;
+            }
+        }
+
+        class ParentState2 extends HierarchicalState {
+            @Override protected void enter() {
+                mParentState2EnterCount += 1;
+            }
+            @Override protected boolean processMessage(Message message) {
+                assertEquals(1, mParentState1EnterCount);
+                assertEquals(1, mParentState1ExitCount);
+                assertEquals(1, mChildState1EnterCount);
+                assertEquals(1, mChildState1ExitCount);
+                assertEquals(1, mChildState2EnterCount);
+                assertEquals(1, mChildState2ExitCount);
+                assertEquals(2, mParentState2EnterCount);
+                assertEquals(1, mParentState2ExitCount);
+                assertEquals(1, mChildState3EnterCount);
+                assertEquals(1, mChildState3ExitCount);
+                assertEquals(2, mChildState4EnterCount);
+                assertEquals(2, mChildState4ExitCount);
+                assertEquals(1, mChildState5EnterCount);
+                assertEquals(1, mChildState5ExitCount);
+
+                transitionToHaltingState();
+                return true;
+            }
+            @Override protected void exit() {
+                mParentState2ExitCount += 1;
+            }
+        }
+
+        class ChildState3 extends HierarchicalState {
+            @Override protected void enter() {
+                mChildState3EnterCount += 1;
+            }
+            @Override protected boolean processMessage(Message message) {
+                assertEquals(1, mParentState1EnterCount);
+                assertEquals(1, mParentState1ExitCount);
+                assertEquals(1, mChildState1EnterCount);
+                assertEquals(1, mChildState1ExitCount);
+                assertEquals(1, mChildState2EnterCount);
+                assertEquals(1, mChildState2ExitCount);
+                assertEquals(1, mParentState2EnterCount);
+                assertEquals(0, mParentState2ExitCount);
+                assertEquals(1, mChildState3EnterCount);
+                assertEquals(0, mChildState3ExitCount);
+                assertEquals(1, mChildState4EnterCount);
+                assertEquals(1, mChildState4ExitCount);
+                assertEquals(1, mChildState5EnterCount);
+                assertEquals(1, mChildState5ExitCount);
+
+                transitionTo(mChildState4);
+                return true;
+            }
+            @Override protected void exit() {
+                mChildState3ExitCount += 1;
+            }
+        }
+
+        class ChildState4 extends HierarchicalState {
+            @Override protected void enter() {
+                mChildState4EnterCount += 1;
+            }
+            @Override protected boolean processMessage(Message message) {
+                assertEquals(1, mParentState1EnterCount);
+                assertEquals(1, mParentState1ExitCount);
+                assertEquals(1, mChildState1EnterCount);
+                assertEquals(1, mChildState1ExitCount);
+                assertEquals(1, mChildState2EnterCount);
+                assertEquals(1, mChildState2ExitCount);
+                assertEquals(1, mParentState2EnterCount);
+                assertEquals(0, mParentState2ExitCount);
+                assertEquals(1, mChildState3EnterCount);
+                assertEquals(1, mChildState3ExitCount);
+                assertEquals(2, mChildState4EnterCount);
+                assertEquals(1, mChildState4ExitCount);
+                assertEquals(1, mChildState5EnterCount);
+                assertEquals(1, mChildState5ExitCount);
+
+                transitionTo(mParentState2);
+                return true;
+            }
+            @Override protected void exit() {
+                mChildState4ExitCount += 1;
+            }
+        }
+
+        class ChildState5 extends HierarchicalState {
+            @Override protected void enter() {
+                mChildState5EnterCount += 1;
+            }
+            @Override protected boolean processMessage(Message message) {
+                assertEquals(1, mParentState1EnterCount);
+                assertEquals(1, mParentState1ExitCount);
+                assertEquals(1, mChildState1EnterCount);
+                assertEquals(1, mChildState1ExitCount);
+                assertEquals(1, mChildState2EnterCount);
+                assertEquals(1, mChildState2ExitCount);
+                assertEquals(1, mParentState2EnterCount);
+                assertEquals(0, mParentState2ExitCount);
+                assertEquals(0, mChildState3EnterCount);
+                assertEquals(0, mChildState3ExitCount);
+                assertEquals(1, mChildState4EnterCount);
+                assertEquals(0, mChildState4ExitCount);
+                assertEquals(1, mChildState5EnterCount);
+                assertEquals(0, mChildState5ExitCount);
+
+                transitionTo(mChildState3);
+                return true;
+            }
+            @Override protected void exit() {
+                mChildState5ExitCount += 1;
+            }
+        }
+
+        @Override
+        protected void halting() {
+            synchronized (mThisSm) {
+                mThisSm.notifyAll();
+            }
+        }
+
+        private StateMachine5 mThisSm;
+        private ParentState1 mParentState1 = new ParentState1();
+        private ChildState1 mChildState1 = new ChildState1();
+        private ChildState2 mChildState2 = new ChildState2();
+        private ParentState2 mParentState2 = new ParentState2();
+        private ChildState3 mChildState3 = new ChildState3();
+        private ChildState4 mChildState4 = new ChildState4();
+        private ChildState5 mChildState5 = new ChildState5();
+
+        private int mParentState1EnterCount = 0;
+        private int mParentState1ExitCount = 0;
+        private int mChildState1EnterCount = 0;
+        private int mChildState1ExitCount = 0;
+        private int mChildState2EnterCount = 0;
+        private int mChildState2ExitCount = 0;
+        private int mParentState2EnterCount = 0;
+        private int mParentState2ExitCount = 0;
+        private int mChildState3EnterCount = 0;
+        private int mChildState3ExitCount = 0;
+        private int mChildState4EnterCount = 0;
+        private int mChildState4ExitCount = 0;
+        private int mChildState5EnterCount = 0;
+        private int mChildState5ExitCount = 0;
+    }
+
+    @SmallTest
+    public void testStateMachine5() throws Exception {
+        StateMachine5 sm5 = new StateMachine5("sm5");
+        sm5.start();
+        if (sm5.isDbg()) Log.d(TAG, "testStateMachine5 E");
+
+        synchronized (sm5) {
+            // Send 6 messages
+            sm5.sendMessage(sm5.obtainMessage(TEST_CMD_1));
+            sm5.sendMessage(sm5.obtainMessage(TEST_CMD_2));
+            sm5.sendMessage(sm5.obtainMessage(TEST_CMD_3));
+            sm5.sendMessage(sm5.obtainMessage(TEST_CMD_4));
+            sm5.sendMessage(sm5.obtainMessage(TEST_CMD_5));
+            sm5.sendMessage(sm5.obtainMessage(TEST_CMD_6));
+
+            try {
+                // wait for the messages to be handled
+                sm5.wait();
+            } catch (InterruptedException e) {
+                Log.e(TAG, "testStateMachine5: exception while waiting " + e.getMessage());
+            }
+        }
+
+
+        assertTrue(sm5.getProcessedMessagesSize() == 6);
+
+        assertEquals(1, sm5.mParentState1EnterCount);
+        assertEquals(1, sm5.mParentState1ExitCount);
+        assertEquals(1, sm5.mChildState1EnterCount);
+        assertEquals(1, sm5.mChildState1ExitCount);
+        assertEquals(1, sm5.mChildState2EnterCount);
+        assertEquals(1, sm5.mChildState2ExitCount);
+        assertEquals(2, sm5.mParentState2EnterCount);
+        assertEquals(2, sm5.mParentState2ExitCount);
+        assertEquals(1, sm5.mChildState3EnterCount);
+        assertEquals(1, sm5.mChildState3ExitCount);
+        assertEquals(2, sm5.mChildState4EnterCount);
+        assertEquals(2, sm5.mChildState4ExitCount);
+        assertEquals(1, sm5.mChildState5EnterCount);
+        assertEquals(1, sm5.mChildState5ExitCount);
+
+        ProcessedMessages.Info pmi;
+        pmi = sm5.getProcessedMessage(0);
+        assertEquals(TEST_CMD_1, pmi.getWhat());
+        assertEquals(sm5.mChildState1, pmi.getState());
+        assertEquals(sm5.mChildState1, pmi.getOriginalState());
+
+        pmi = sm5.getProcessedMessage(1);
+        assertEquals(TEST_CMD_2, pmi.getWhat());
+        assertEquals(sm5.mChildState2, pmi.getState());
+        assertEquals(sm5.mChildState2, pmi.getOriginalState());
+
+        pmi = sm5.getProcessedMessage(2);
+        assertEquals(TEST_CMD_3, pmi.getWhat());
+        assertEquals(sm5.mChildState5, pmi.getState());
+        assertEquals(sm5.mChildState5, pmi.getOriginalState());
+
+        pmi = sm5.getProcessedMessage(3);
+        assertEquals(TEST_CMD_4, pmi.getWhat());
+        assertEquals(sm5.mChildState3, pmi.getState());
+        assertEquals(sm5.mChildState3, pmi.getOriginalState());
+
+        pmi = sm5.getProcessedMessage(4);
+        assertEquals(TEST_CMD_5, pmi.getWhat());
+        assertEquals(sm5.mChildState4, pmi.getState());
+        assertEquals(sm5.mChildState4, pmi.getOriginalState());
+
+        pmi = sm5.getProcessedMessage(5);
+        assertEquals(TEST_CMD_6, pmi.getWhat());
+        assertEquals(sm5.mParentState2, pmi.getState());
+        assertEquals(sm5.mParentState2, pmi.getOriginalState());
+
+        if (sm5.isDbg()) Log.d(TAG, "testStateMachine5 X");
+    }
+
+    /**
+     * Test that the initial state enter is invoked immediately
+     * after construction and before any other messages arrive and that
+     * sendMessageDelayed works.
+     */
+    class StateMachine6 extends HierarchicalStateMachine {
+        StateMachine6(String name) {
+            super(name);
+            mThisSm = this;
+            setDbg(DBG);
+
+            // Setup state machine with 1 state
+            addState(mS1);
+
+            // Set the initial state
+            setInitialState(mS1);
+            if (DBG) Log.d(TAG, "StateMachine6: ctor X");
+        }
+
+        class S1 extends HierarchicalState {
+
+            @Override protected void enter() {
+                sendMessage(obtainMessage(TEST_CMD_1));
+            }
+
+            @Override protected boolean processMessage(Message message) {
+                if (message.what == TEST_CMD_1) {
+                    mArrivalTimeMsg1 = SystemClock.elapsedRealtime();
+                } else if (message.what == TEST_CMD_2) {
+                    mArrivalTimeMsg2 = SystemClock.elapsedRealtime();
+                    transitionToHaltingState();
+                }
+                return true;
+            }
+
+            @Override protected void exit() {
+            }
+        }
+
+        @Override
+        protected void halting() {
+            synchronized (mThisSm) {
+                mThisSm.notifyAll();
+            }
+        }
+
+        private StateMachine6 mThisSm;
+        private S1 mS1 = new S1();
+
+        private long mArrivalTimeMsg1;
+        private long mArrivalTimeMsg2;
+    }
+
+    @SmallTest
+    public void testStateMachine6() throws Exception {
+        long sentTimeMsg2;
+        final int DELAY_TIME = 250;
+        final int DELAY_FUDGE = 20;
+
+        StateMachine6 sm6 = new StateMachine6("sm6");
+        sm6.start();
+        if (sm6.isDbg()) Log.d(TAG, "testStateMachine6 E");
+
+        synchronized (sm6) {
+            // Send a message
+            sentTimeMsg2 = SystemClock.elapsedRealtime();
+            sm6.sendMessageDelayed(sm6.obtainMessage(TEST_CMD_2), DELAY_TIME);
+
+            try {
+                // wait for the messages to be handled
+                sm6.wait();
+            } catch (InterruptedException e) {
+                Log.e(TAG, "testStateMachine6: exception while waiting " + e.getMessage());
+            }
+        }
+
+        /**
+         * TEST_CMD_1 was sent in enter and must always have been processed
+         * immediately after construction and hence the arrival time difference
+         * should always >= to the DELAY_TIME
+         */
+        long arrivalTimeDiff = sm6.mArrivalTimeMsg2 - sm6.mArrivalTimeMsg1;
+        long expectedDelay = DELAY_TIME - DELAY_FUDGE;
+        if (sm6.isDbg()) Log.d(TAG, "testStateMachine6: expect " + arrivalTimeDiff
+                                    + " >= " + expectedDelay);
+        assertTrue(arrivalTimeDiff >= expectedDelay);
+
+        if (sm6.isDbg()) Log.d(TAG, "testStateMachine6 X");
+    }
+
+    /**
+     * Test that enter is invoked immediately after exit. This validates
+     * that enter can be used to send a watch dog message for its state.
+     */
+    class StateMachine7 extends HierarchicalStateMachine {
+        private final int SM7_DELAY_TIME = 250;
+
+        StateMachine7(String name) {
+            super(name);
+            mThisSm = this;
+            setDbg(DBG);
+
+            // Setup state machine with 1 state
+            addState(mS1);
+            addState(mS2);
+
+            // Set the initial state
+            setInitialState(mS1);
+            if (DBG) Log.d(TAG, "StateMachine7: ctor X");
+        }
+
+        class S1 extends HierarchicalState {
+            @Override protected boolean processMessage(Message message) {
+                transitionTo(mS2);
+                return true;
+            }
+            @Override protected void exit() {
+                sendMessage(obtainMessage(TEST_CMD_2));
+            }
+        }
+
+        class S2 extends HierarchicalState {
+
+            @Override protected void enter() {
+                // Send a delayed message as a watch dog
+                sendMessageDelayed(obtainMessage(TEST_CMD_3), SM7_DELAY_TIME);
+            }
+
+            @Override protected boolean processMessage(Message message) {
+                if (message.what == TEST_CMD_2) {
+                    mMsgCount += 1;
+                    mArrivalTimeMsg2 = SystemClock.elapsedRealtime();
+                } else if (message.what == TEST_CMD_3) {
+                    mMsgCount += 1;
+                    mArrivalTimeMsg3 = SystemClock.elapsedRealtime();
+                }
+
+                if (mMsgCount == 2) {
+                    transitionToHaltingState();
+                }
+                return true;
+            }
+
+            @Override protected void exit() {
+            }
+        }
+
+        @Override
+        protected void halting() {
+            synchronized (mThisSm) {
+                mThisSm.notifyAll();
+            }
+        }
+
+        private StateMachine7 mThisSm;
+        private S1 mS1 = new S1();
+        private S2 mS2 = new S2();
+
+        private int mMsgCount = 0;
+        private long mArrivalTimeMsg2;
+        private long mArrivalTimeMsg3;
+    }
+
+    @SmallTest
+    public void testStateMachine7() throws Exception {
+        long sentTimeMsg2;
+        final int SM7_DELAY_FUDGE = 20;
+
+        StateMachine7 sm7 = new StateMachine7("sm7");
+        sm7.start();
+        if (sm7.isDbg()) Log.d(TAG, "testStateMachine7 E");
+
+        synchronized (sm7) {
+            // Send a message
+            sentTimeMsg2 = SystemClock.elapsedRealtime();
+            sm7.sendMessage(sm7.obtainMessage(TEST_CMD_1));
+
+            try {
+                // wait for the messages to be handled
+                sm7.wait();
+            } catch (InterruptedException e) {
+                Log.e(TAG, "testStateMachine7: exception while waiting " + e.getMessage());
+            }
+        }
+
+        /**
+         * TEST_CMD_3 was sent in S2.enter with a delay and must always have been
+         * processed immediately after S1.exit. Since S1.exit sent TEST_CMD_2
+         * without a delay the arrival time difference should always >= to SM7_DELAY_TIME.
+         */
+        long arrivalTimeDiff = sm7.mArrivalTimeMsg3 - sm7.mArrivalTimeMsg2;
+        long expectedDelay = sm7.SM7_DELAY_TIME - SM7_DELAY_FUDGE;
+        if (sm7.isDbg()) Log.d(TAG, "testStateMachine7: expect " + arrivalTimeDiff
+                                    + " >= " + expectedDelay);
+        assertTrue(arrivalTimeDiff >= expectedDelay);
+
+        if (sm7.isDbg()) Log.d(TAG, "testStateMachine7 X");
+    }
+
+    /**
+     * Test unhandledMessage.
+     */
+    class StateMachineUnhandledMessage extends HierarchicalStateMachine {
+        StateMachineUnhandledMessage(String name) {
+            super(name);
+            mThisSm = this;
+            setDbg(DBG);
+
+            // Setup state machine with 1 state
+            addState(mS1);
+
+            // Set the initial state
+            setInitialState(mS1);
+        }
+
+        @Override protected void unhandledMessage(Message message) {
+            mUnhandledMessageCount += 1;
+        }
+
+        class S1 extends HierarchicalState {
+            @Override protected boolean processMessage(Message message) {
+                if (message.what == TEST_CMD_2) {
+                    transitionToHaltingState();
+                }
+                return false;
+            }
+        }
+
+        @Override
+        protected void halting() {
+            synchronized (mThisSm) {
+                mThisSm.notifyAll();
+            }
+        }
+
+        private StateMachineUnhandledMessage mThisSm;
+        private int mUnhandledMessageCount;
+        private S1 mS1 = new S1();
+    }
+
+    @SmallTest
+    public void testStateMachineUnhandledMessage() throws Exception {
+
+        StateMachineUnhandledMessage sm = new StateMachineUnhandledMessage("sm");
+        sm.start();
+        if (sm.isDbg()) Log.d(TAG, "testStateMachineUnhandledMessage E");
+
+        synchronized (sm) {
+            // Send 2 messages
+            for (int i = 1; i <= 2; i++) {
+                sm.sendMessage(sm.obtainMessage(i));
+            }
+
+            try {
+                // wait for the messages to be handled
+                sm.wait();
+            } catch (InterruptedException e) {
+                Log.e(TAG, "testStateMachineUnhandledMessage: exception while waiting "
+                        + e.getMessage());
+            }
+        }
+
+        assertTrue(sm.getProcessedMessagesCount() == 2);
+        assertEquals(2, sm.mUnhandledMessageCount);
+
+        if (sm.isDbg()) Log.d(TAG, "testStateMachineUnhandledMessage X");
+    }
+
+    /**
+     * Test state machines sharing the same thread/looper. Multiple instances
+     * of the same state machine will be created. They will all share the
+     * same thread and thus each can update <code>sharedCounter</code> which
+     * will be used to notify testStateMachineSharedThread that the test is
+     * complete.
+     */
+    class StateMachineSharedThread extends HierarchicalStateMachine {
+        StateMachineSharedThread(Looper looper, String name, int maxCount) {
+            super(looper, name);
+            mMaxCount = maxCount;
+            setDbg(DBG);
+
+            // Setup state machine with 1 state
+            addState(mS1);
+
+            // Set the initial state
+            setInitialState(mS1);
+        }
+
+        class S1 extends HierarchicalState {
+            @Override protected boolean processMessage(Message message) {
+                if (message.what == TEST_CMD_4) {
+                    transitionToHaltingState();
+                }
+                return true;
+            }
+        }
+
+        @Override
+        protected void halting() {
+            // Update the shared counter, which is OK since all state
+            // machines are using the same thread.
+            sharedCounter += 1;
+            if (sharedCounter == mMaxCount) {
+                synchronized (waitObject) {
+                    waitObject.notifyAll();
+                }
+            }
+        }
+
+        private int mMaxCount;
+        private S1 mS1 = new S1();
+    }
+    private static int sharedCounter = 0;
+    private static Object waitObject = new Object();
+
+    @SmallTest
+    public void testStateMachineSharedThread() throws Exception {
+        if (DBG) Log.d(TAG, "testStateMachineSharedThread E");
+
+        // Create and start the handler thread
+        HandlerThread smThread = new HandlerThread("testStateMachineSharedThread");
+        smThread.start();
+
+        // Create the state machines
+        StateMachineSharedThread sms[] = new StateMachineSharedThread[10];
+        for (int i = 0; i < sms.length; i++) {
+            sms[i] = new StateMachineSharedThread(smThread.getLooper(), "sm", sms.length);
+            sms[i].start();
+        }
+
+        synchronized (waitObject) {
+            // Send messages to each of the state machines
+            for (StateMachineSharedThread sm : sms) {
+                for (int i = 1; i <= 4; i++) {
+                    sm.sendMessage(sm.obtainMessage(i));
+                }
+            }
+
+            // Wait for the last state machine to notify its done
+            try {
+                waitObject.wait();
+            } catch (InterruptedException e) {
+                Log.e(TAG, "testStateMachineSharedThread: exception while waiting "
+                        + e.getMessage());
+            }
+        }
+
+        for (StateMachineSharedThread sm : sms) {
+            assertTrue(sm.getProcessedMessagesCount() == 4);
+            for (int i = 0; i < sm.getProcessedMessagesCount(); i++) {
+                ProcessedMessages.Info pmi = sm.getProcessedMessage(i);
+                assertEquals(i+1, pmi.getWhat());
+                assertEquals(sm.mS1, pmi.getState());
+                assertEquals(sm.mS1, pmi.getOriginalState());
+            }
+        }
+
+        if (DBG) Log.d(TAG, "testStateMachineSharedThread X");
+    }
+
+    @SmallTest
+    public void testHsm1() throws Exception {
+        if (DBG) Log.d(TAG, "testHsm1 E");
+
+        Hsm1 sm = Hsm1.makeHsm1();
+
+        // Send messages
+        sm.sendMessage(sm.obtainMessage(Hsm1.CMD_1));
+        sm.sendMessage(sm.obtainMessage(Hsm1.CMD_2));
+
+        synchronized (sm) {
+            // Wait for the last state machine to notify its done
+            try {
+                sm.wait();
+            } catch (InterruptedException e) {
+                Log.e(TAG, "testHsm1: exception while waiting " + e.getMessage());
+            }
+        }
+
+        assertEquals(7, sm.getProcessedMessagesCount());
+        ProcessedMessages.Info pmi = sm.getProcessedMessage(0);
+        assertEquals(Hsm1.CMD_1, pmi.getWhat());
+        assertEquals(sm.mS1, pmi.getState());
+        assertEquals(sm.mS1, pmi.getOriginalState());
+
+        pmi = sm.getProcessedMessage(1);
+        assertEquals(Hsm1.CMD_2, pmi.getWhat());
+        assertEquals(sm.mP1, pmi.getState());
+        assertEquals(sm.mS1, pmi.getOriginalState());
+
+        pmi = sm.getProcessedMessage(2);
+        assertEquals(Hsm1.CMD_2, pmi.getWhat());
+        assertEquals(sm.mS2, pmi.getState());
+        assertEquals(sm.mS2, pmi.getOriginalState());
+
+        pmi = sm.getProcessedMessage(3);
+        assertEquals(Hsm1.CMD_3, pmi.getWhat());
+        assertEquals(sm.mS2, pmi.getState());
+        assertEquals(sm.mS2, pmi.getOriginalState());
+
+        pmi = sm.getProcessedMessage(4);
+        assertEquals(Hsm1.CMD_3, pmi.getWhat());
+        assertEquals(sm.mP2, pmi.getState());
+        assertEquals(sm.mP2, pmi.getOriginalState());
+
+        pmi = sm.getProcessedMessage(5);
+        assertEquals(Hsm1.CMD_4, pmi.getWhat());
+        assertEquals(sm.mP2, pmi.getState());
+        assertEquals(sm.mP2, pmi.getOriginalState());
+
+        pmi = sm.getProcessedMessage(6);
+        assertEquals(Hsm1.CMD_5, pmi.getWhat());
+        assertEquals(sm.mP2, pmi.getState());
+        assertEquals(sm.mP2, pmi.getOriginalState());
+
+        if (DBG) Log.d(TAG, "testStateMachineSharedThread X");
+    }
+}
+
+class Hsm1 extends HierarchicalStateMachine {
+    private static final String TAG = "hsm1";
+
+    public static final int CMD_1 = 1;
+    public static final int CMD_2 = 2;
+    public static final int CMD_3 = 3;
+    public static final int CMD_4 = 4;
+    public static final int CMD_5 = 5;
+
+    public static Hsm1 makeHsm1() {
+        Log.d(TAG, "makeHsm1 E");
+        Hsm1 sm = new Hsm1("hsm1");
+        sm.start();
+        Log.d(TAG, "makeHsm1 X");
+        return sm;
+    }
+
+    Hsm1(String name) {
+        super(name);
+        Log.d(TAG, "ctor E");
+
+        // Add states, use indentation to show hierarchy
+        addState(mP1);
+            addState(mS1, mP1);
+            addState(mS2, mP1);
+        addState(mP2);
+
+        // Set the initial state
+        setInitialState(mS1);
+        Log.d(TAG, "ctor X");
+    }
+
+    class P1 extends HierarchicalState {
+        @Override protected void enter() {
+            Log.d(TAG, "P1.enter");
+        }
+        @Override protected boolean processMessage(Message message) {
+            boolean retVal;
+            Log.d(TAG, "P1.processMessage what=" + message.what);
+            switch(message.what) {
+            case CMD_2:
+                // CMD_2 will arrive in mS2 before CMD_3
+                sendMessage(obtainMessage(CMD_3));
+                deferMessage(message);
+                transitionTo(mS2);
+                retVal = true;
+                break;
+            default:
+                // Any message we don't understand in this state invokes unhandledMessage
+                retVal = false;
+                break;
+            }
+            return retVal;
+        }
+        @Override protected void exit() {
+            Log.d(TAG, "P1.exit");
+        }
+    }
+
+    class S1 extends HierarchicalState {
+        @Override protected void enter() {
+            Log.d(TAG, "S1.enter");
+        }
+        @Override protected boolean processMessage(Message message) {
+            Log.d(TAG, "S1.processMessage what=" + message.what);
+            if (message.what == CMD_1) {
+                // Transition to ourself to show that enter/exit is called
+                transitionTo(mS1);
+                return true;
+            } else {
+                // Let parent process all other messages
+                return false;
+            }
+        }
+        @Override protected void exit() {
+            Log.d(TAG, "S1.exit");
+        }
+    }
+
+    class S2 extends HierarchicalState {
+        @Override protected void enter() {
+            Log.d(TAG, "S2.enter");
+        }
+        @Override protected boolean processMessage(Message message) {
+            boolean retVal;
+            Log.d(TAG, "S2.processMessage what=" + message.what);
+            switch(message.what) {
+            case(CMD_2):
+                sendMessage(obtainMessage(CMD_4));
+                retVal = true;
+                break;
+            case(CMD_3):
+                deferMessage(message);
+                transitionTo(mP2);
+                retVal = true;
+                break;
+            default:
+                retVal = false;
+                break;
+            }
+            return retVal;
+        }
+        @Override protected void exit() {
+            Log.d(TAG, "S2.exit");
+        }
+    }
+
+    class P2 extends HierarchicalState {
+        @Override protected void enter() {
+            Log.d(TAG, "P2.enter");
+            sendMessage(obtainMessage(CMD_5));
+        }
+        @Override protected boolean processMessage(Message message) {
+            Log.d(TAG, "P2.processMessage what=" + message.what);
+            switch(message.what) {
+            case(CMD_3):
+                break;
+            case(CMD_4):
+                break;
+            case(CMD_5):
+                transitionToHaltingState();
+                break;
+            }
+            return true;
+        }
+        @Override protected void exit() {
+            Log.d(TAG, "P2.exit");
+        }
+    }
+
+    @Override
+    protected void halting() {
+        Log.d(TAG, "halting");
+        synchronized (this) {
+            this.notifyAll();
+        }
+    }
+
+    P1 mP1 = new P1();
+    S1 mS1 = new S1();
+    S2 mS2 = new S2();
+    P2 mP2 = new P2();
+}