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 java.util.ArrayList;
17import java.util.HashMap;
18import java.util.Iterator;
19import java.util.Map;
20
21/**
22 * Linear or DAG of {@link State}s. StateMachine is by default a linear model, until
23 * {@link #addState(State, State)} is called.  Each State has three status:
24 * STATUS_ZERO, STATUS_INVOKED, STATUS_EXECUTED.   We allow client to run a State, which will
25 * put State in STATUS_INVOKED.  A State will be executed when prior States are executed and
26 * Precondition for this State is true, then the State will be marked as STATUS_EXECUTED.
27 *
28 * @hide
29 */
30public final class StateMachine {
31
32    /**
33     * No request on the State
34     */
35    public static final int STATUS_ZERO = 0;
36    /**
37     * Somebody wants to run the state but not yet executed because either the condition is
38     * false or lower States are not executed.
39     */
40    public static final int STATUS_INVOKED = 1;
41    /**
42     * Somebody wants to run the State and the State was executed.
43     */
44    public static final int STATUS_EXECUTED = 2;
45
46    public static class State {
47
48        private int mStatus;
49        private ArrayList<State> mPriorStates;
50
51        /**
52         * Run State, Subclass may override.
53         */
54        public void run() {
55        }
56
57        /**
58         * Returns true if State can run, false otherwise.  Subclass may override.
59         * @return True if State can run, false otherwise.  Subclass may override.
60         */
61        public boolean canRun() {
62            return true;
63        }
64
65        /**
66         * @return True if the State has been executed.
67         */
68        final boolean runIfNeeded() {
69            if (mStatus!= STATUS_EXECUTED) {
70                if (mStatus == STATUS_INVOKED && canRun()) {
71                    run();
72                    mStatus = STATUS_EXECUTED;
73                } else {
74                    return false;
75                }
76            }
77            return true;
78        }
79
80        void addPriorState(State state) {
81            if (mPriorStates == null) {
82                mPriorStates = new ArrayList<State>();
83            }
84            if (!mPriorStates.contains(state)) {
85                mPriorStates.add(state);
86            }
87        }
88
89        final void markInvoked() {
90            if (mStatus == STATUS_ZERO) {
91                mStatus = STATUS_INVOKED;
92            }
93        }
94
95        final void updateStatus(int status) {
96            mStatus = status;
97        }
98
99        /**
100         * Get status, return one of {@link #STATUS_ZERO}, {@link #STATUS_INVOKED},
101         * {@link #STATUS_EXECUTED}.
102         * @return Status of the State.
103         */
104        public final int getStatus() {
105            return mStatus;
106        }
107
108        @Override
109        public final boolean equals(Object other) {
110            return this == other;
111        }
112    }
113
114    private boolean mSorted = true;
115    private final ArrayList<State> mSortedList = new ArrayList<State>();
116
117    /**
118     * Add a State to StateMachine, ignore if it is already added.
119     * @param state The state to add.
120     */
121    public void addState(State state) {
122        if (!mSortedList.contains(state)) {
123            state.updateStatus(STATUS_ZERO);
124            mSortedList.add(state);
125        }
126    }
127
128    /**
129     * Add two States to StateMachine and create an edge between this two.
130     * StateMachine is by default a linear model, until {@link #addState(State, State)} is called.
131     * sort() is required to sort the Direct acyclic graph.
132     * @param fromState The from state to add.
133     * @param toState The to state to add.
134     */
135    public void addState(State fromState, State toState) {
136        addState(fromState);
137        addState(toState);
138        toState.addPriorState(fromState);
139        mSorted = false;
140    }
141
142    void verifySorted() {
143        if (!mSorted) {
144            throw new RuntimeException("Graph not sorted");
145        }
146    }
147
148    public void runState(State state) {
149        verifySorted();
150        state.markInvoked();
151        runPendingStates();
152    }
153
154    public void runPendingStates() {
155        verifySorted();
156        for (int i = 0, size = mSortedList.size(); i < size; i++) {
157            if (!mSortedList.get(i).runIfNeeded()) {
158                break;
159            }
160        }
161    }
162
163    public void resetStatus() {
164        for (int i = 0, size = mSortedList.size(); i < size; i++) {
165            mSortedList.get(i).updateStatus(STATUS_ZERO);
166        }
167    }
168
169    /**
170     * StateMachine is by default a linear model, until {@link #addState(State, State)} is called.
171     * sort() is required to sort the Direct acyclic graph.
172     */
173    public void sort() {
174        if (mSorted) {
175            return;
176        }
177        // L: Empty list that will contain the sorted States
178        ArrayList<State> L = new ArrayList<State>();
179        // S: Set of all nodes with no incoming edges
180        ArrayList<State> S = new ArrayList<State>();
181        HashMap<State, ArrayList<State>> edges = new HashMap<State, ArrayList<State>>();
182        for (int i = mSortedList.size() - 1; i >= 0 ; i--) {
183            State state = mSortedList.get(i);
184            if (state.mPriorStates != null && state.mPriorStates.size() > 0) {
185                edges.put(state, new ArrayList<State>(state.mPriorStates));
186            } else {
187                S.add(state);
188            }
189        }
190
191        while (!S.isEmpty()) {
192            // remove a State without incoming Node from S, add to L
193            State state = S.remove(S.size() - 1);
194            L.add(state);
195            // for each toState that having an incoming edge from "state":
196            for (Iterator<Map.Entry<State, ArrayList<State>>> iterator =
197                    edges.entrySet().iterator(); iterator.hasNext();) {
198                Map.Entry<State, ArrayList<State>> entry = iterator.next();
199                ArrayList<State> fromStates = entry.getValue();
200                // remove edge from graph
201                if (fromStates.remove(state)) {
202                    if (fromStates.size() == 0) {
203                        State toState = entry.getKey();
204                        // insert the toState to S if it has no more incoming edges
205                        S.add(toState);
206                        iterator.remove();
207                    }
208                }
209            }
210        }
211        if (edges.size() > 0) {
212            throw new RuntimeException("Cycle in Graph");
213        }
214
215        mSortedList.clear();
216        mSortedList.addAll(L);
217        mSorted = true;
218    }
219}
220