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