StateMachine.java revision 99ec8b0cb375f7e5577ea3ec9f09e6ff7a95de0d
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 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