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