1/*
2 * Copyright (C) 2014 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
5 * in compliance with the License. You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software distributed under the License
10 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
11 * or implied. See the License for the specific language governing permissions and limitations under
12 * the License.
13 */
14package android.support.v17.leanback.util;
15
16import static android.support.annotation.RestrictTo.Scope.LIBRARY_GROUP;
17
18import android.support.annotation.RestrictTo;
19import android.util.Log;
20
21import java.util.ArrayList;
22
23/**
24 * State: each State has incoming Transitions and outgoing Transitions.
25 * When {@link State#mBranchStart} is true, all the outgoing Transitions may be triggered, when
26 * {@link State#mBranchStart} is false, only first outgoing Transition will be triggered.
27 * When {@link State#mBranchEnd} is true, all the incoming Transitions must be triggered for the
28 * State to run. When {@link State#mBranchEnd} is false, only need one incoming Transition triggered
29 * for the State to run.
30 * Transition: three types:
31 * 1. Event based transition, transition will be triggered when {@link #fireEvent(Event)} is called.
32 * 2. Auto transition, transition will be triggered when {@link Transition#mFromState} is executed.
33 * 3. Condiitonal Auto transition, transition will be triggered when {@link Transition#mFromState}
34 * is executed and {@link Transition#mCondition} passes.
35 * @hide
36 */
37@RestrictTo(LIBRARY_GROUP)
38public final class StateMachine {
39
40    static boolean DEBUG = false;
41    static final String TAG = "StateMachine";
42
43    /**
44     * No request on the State
45     */
46    public static final int STATUS_ZERO = 0;
47
48    /**
49     * Has been executed
50     */
51    public static final int STATUS_INVOKED = 1;
52
53    /**
54     * Used in Transition
55     */
56    public static class Event {
57        final String mName;
58
59        public Event(String name) {
60            mName = name;
61        }
62    }
63
64    /**
65     * Used in transition
66     */
67    public static class Condition {
68        final String mName;
69
70        public Condition(String name) {
71            mName = name;
72        }
73
74        /**
75         * @return True if can proceed and mark the transition INVOKED
76         */
77        public boolean canProceed() {
78            return true;
79        }
80    }
81
82    static class Transition {
83        final State mFromState;
84        final State mToState;
85        final Event mEvent;
86        final Condition mCondition;
87        int mState = STATUS_ZERO;
88
89        Transition(State fromState, State toState, Event event) {
90            if (event == null) {
91                throw new IllegalArgumentException();
92            }
93            mFromState = fromState;
94            mToState = toState;
95            mEvent = event;
96            mCondition = null;
97        }
98
99        Transition(State fromState, State toState) {
100            mFromState = fromState;
101            mToState = toState;
102            mEvent = null;
103            mCondition = null;
104        }
105
106        Transition(State fromState, State toState, Condition condition) {
107            if (condition == null) {
108                throw new IllegalArgumentException();
109            }
110            mFromState = fromState;
111            mToState = toState;
112            mEvent = null;
113            mCondition = condition;
114        }
115
116        @Override
117        public String toString() {
118            String signalName;
119            if (mEvent != null) {
120                signalName = mEvent.mName;
121            } else if (mCondition != null) {
122                signalName = mCondition.mName;
123            } else {
124                signalName = "auto";
125            }
126            return "[" + mFromState.mName + " -> " + mToState.mName + " <"
127                    + signalName + ">]";
128        }
129    }
130
131    /**
132     * @see StateMachine
133     */
134    public static class State {
135
136        final String mName;
137        final boolean mBranchStart;
138        final boolean mBranchEnd;
139        int mStatus = STATUS_ZERO;
140        int mInvokedOutTransitions = 0;
141        ArrayList<Transition> mIncomings;
142        ArrayList<Transition> mOutgoings;
143
144        @Override
145        public String toString() {
146            return "[" + mName + " " + mStatus + "]";
147        }
148
149        /**
150         * Create a State which is not branch start and a branch end.
151         */
152        public State(String name) {
153            this(name, false, true);
154        }
155
156        /**
157         * Create a State
158         * @param branchStart True if can run all out going transitions or false execute the first
159         *                    out going transition.
160         * @param branchEnd True if wait all incoming transitions executed or false
161         *                              only need one of the transition executed.
162         */
163        public State(String name, boolean branchStart, boolean branchEnd) {
164            mName = name;
165            mBranchStart = branchStart;
166            mBranchEnd = branchEnd;
167        }
168
169        void addIncoming(Transition t) {
170            if (mIncomings == null) {
171                mIncomings = new ArrayList();
172            }
173            mIncomings.add(t);
174        }
175
176        void addOutgoing(Transition t) {
177            if (mOutgoings == null) {
178                mOutgoings = new ArrayList();
179            }
180            mOutgoings.add(t);
181        }
182
183        /**
184         * Run State, Subclass may override.
185         */
186        public void run() {
187        }
188
189        final boolean checkPreCondition() {
190            if (mIncomings == null) {
191                return true;
192            }
193            if (mBranchEnd) {
194                for (Transition t: mIncomings) {
195                    if (t.mState != STATUS_INVOKED) {
196                        return false;
197                    }
198                }
199                return true;
200            } else {
201                for (Transition t: mIncomings) {
202                    if (t.mState == STATUS_INVOKED) {
203                        return true;
204                    }
205                }
206                return false;
207            }
208        }
209
210        /**
211         * @return True if the State has been executed.
212         */
213        final boolean runIfNeeded() {
214            if (mStatus != STATUS_INVOKED) {
215                if (checkPreCondition()) {
216                    if (DEBUG) {
217                        Log.d(TAG, "execute " + this);
218                    }
219                    mStatus = STATUS_INVOKED;
220                    run();
221                    signalAutoTransitionsAfterRun();
222                    return true;
223                }
224            }
225            return false;
226        }
227
228        final void signalAutoTransitionsAfterRun() {
229            if (mOutgoings != null) {
230                for (Transition t: mOutgoings) {
231                    if (t.mEvent == null) {
232                        if (t.mCondition == null || t.mCondition.canProceed()) {
233                            if (DEBUG) {
234                                Log.d(TAG, "signal " + t);
235                            }
236                            mInvokedOutTransitions++;
237                            t.mState = STATUS_INVOKED;
238                            if (!mBranchStart) {
239                                break;
240                            }
241                        }
242                    }
243                }
244            }
245        }
246
247        /**
248         * Get status, return one of {@link #STATUS_ZERO}, {@link #STATUS_INVOKED}.
249         * @return Status of the State.
250         */
251        public final int getStatus() {
252            return mStatus;
253        }
254    }
255
256    final ArrayList<State> mStates = new ArrayList<State>();
257    final ArrayList<State> mFinishedStates = new ArrayList();
258    final ArrayList<State> mUnfinishedStates = new ArrayList();
259
260    public StateMachine() {
261    }
262
263    /**
264     * Add a State to StateMachine, ignore if it is already added.
265     * @param state The state to add.
266     */
267    public void addState(State state) {
268        if (!mStates.contains(state)) {
269            mStates.add(state);
270        }
271    }
272
273    /**
274     * Add event-triggered transition between two states.
275     * @param fromState The from state.
276     * @param toState The to state.
277     * @param event The event that needed to perform the transition.
278     */
279    public void addTransition(State fromState, State toState, Event event) {
280        Transition transition = new Transition(fromState, toState, event);
281        toState.addIncoming(transition);
282        fromState.addOutgoing(transition);
283    }
284
285    /**
286     * Add a conditional auto transition between two states.
287     * @param fromState The from state.
288     * @param toState The to state.
289     */
290    public void addTransition(State fromState, State toState, Condition condition) {
291        Transition transition = new Transition(fromState, toState, condition);
292        toState.addIncoming(transition);
293        fromState.addOutgoing(transition);
294    }
295
296    /**
297     * Add an auto transition between two states.
298     * @param fromState The from state to add.
299     * @param toState The to state to add.
300     */
301    public void addTransition(State fromState, State toState) {
302        Transition transition = new Transition(fromState, toState);
303        toState.addIncoming(transition);
304        fromState.addOutgoing(transition);
305    }
306
307    /**
308     * Start the state machine.
309     */
310    public void start() {
311        if (DEBUG) {
312            Log.d(TAG, "start");
313        }
314        mUnfinishedStates.addAll(mStates);
315        runUnfinishedStates();
316    }
317
318    void runUnfinishedStates() {
319        boolean changed;
320        do {
321            changed = false;
322            for (int i = mUnfinishedStates.size() - 1; i >= 0; i--) {
323                State state = mUnfinishedStates.get(i);
324                if (state.runIfNeeded()) {
325                    mUnfinishedStates.remove(i);
326                    mFinishedStates.add(state);
327                    changed = true;
328                }
329            }
330        } while (changed);
331    }
332
333    /**
334     * Find outgoing Transitions of invoked State whose Event matches, mark the Transition invoked.
335     */
336    public void fireEvent(Event event) {
337        for (int i = 0; i < mFinishedStates.size(); i++) {
338            State state = mFinishedStates.get(i);
339            if (state.mOutgoings != null) {
340                if (!state.mBranchStart && state.mInvokedOutTransitions > 0) {
341                    continue;
342                }
343                for (Transition t : state.mOutgoings) {
344                    if (t.mState != STATUS_INVOKED && t.mEvent == event) {
345                        if (DEBUG) {
346                            Log.d(TAG, "signal " + t);
347                        }
348                        t.mState = STATUS_INVOKED;
349                        state.mInvokedOutTransitions++;
350                        if (!state.mBranchStart) {
351                            break;
352                        }
353                    }
354                }
355            }
356        }
357        runUnfinishedStates();
358    }
359
360    /**
361     * Reset status to orignal status
362     */
363    public void reset() {
364        if (DEBUG) {
365            Log.d(TAG, "reset");
366        }
367        mUnfinishedStates.clear();
368        mFinishedStates.clear();
369        for (State state: mStates) {
370            state.mStatus = STATUS_ZERO;
371            state.mInvokedOutTransitions = 0;
372            if (state.mOutgoings != null) {
373                for (Transition t: state.mOutgoings) {
374                    t.mState = STATUS_ZERO;
375                }
376            }
377        }
378    }
379}
380