home *** CD-ROM | disk | FTP | other *** search
/ MacHack 1998 / MacHack 1998.toast / Programming Contest / Secret Solutions Folder / Problem 09 - State Machine / Solution.cp < prev    next >
Encoding:
Text File  |  1998-06-18  |  4.4 KB  |  119 lines  |  [TEXT/CWIE]
  1. /*
  2. Problem 09 - State Machine
  3.  
  4. type GetNextCharProc = function( curstate: UInt32 ): UInt32;
  5.  
  6. procedure StateMachineInit( var state_machine: Handle; states: UInt32; chars: UInt32 );
  7. procedure AddTransition( state_machine: Handle; state1, state2: UInt32; first_char, last_char: UInt32 );
  8. procedure RunStateMachine( state_machine: Handle; start_state: UInt32; GetNextChar: GetNextCharProc; var stop_state: UInt32 );
  9.  
  10. StateMachineInit creates a new, empty state machine ready to accept state transitions, and containing states states (numbers 1 to states) and chars characters (numbered 1 to chars).  All the state machine information must be stored in the real Mac memory manager handle - it will be disposed with DisposeHandle and that must release all memory, so dont store any extra information outside the handle.  Also, you must be able to deal with having multiple state machine instantiated simultaneously.
  11.  
  12. AddTransition adds a transition from state1 to state2 for characters between (inclusive) first_char and last_char.  When you get to state1 and get a character between first_char and last_char you should proceed to state2.  The new transition overrides and previous transitions for these characters from state1 (ie, if you get transition 1->2 for chars 1-10, and then 1->3 for chars 5-6, you now have transition 1->2 for chars 1-4 and 7-10 and transition 1->3 for chars 5-6).
  13.  
  14. RunStateMachine starts in start_state and calls GetNextChar repeatedly until either it returns 0 or until it returns a character for which there is no transition at the current state.  Each time it gets a character, the state is moved to the state for which there is a transition from that state with that character [blerg :-].  The final state is returned in stop_state.
  15. */
  16.  
  17. #include "Solution.h"
  18.  
  19. #define kMaxInt 0xffffffff;
  20.  
  21. #define TheState(state_machine) ((MyState *)(*(state_machine)))
  22. #define TheStateTransitions(state_machine) ((MyStateTransition *)(*(state_machine) + sizeof(MyState)))
  23.  
  24. typedef struct MyStateTransition {
  25.     UInt32 inputChar;
  26.     UInt32 oldState;
  27.     UInt32 newState;
  28. } MyStateTransition;
  29.  
  30. typedef struct MyState {
  31.     UInt32 numStates;
  32.     UInt32 numChars;
  33.     UInt32 numTransitions;
  34. } MyState;
  35.  
  36. // Fill in your solution and then submit this folder
  37.  
  38. // Team Name: FILL IN YOUR TEAM NAME!
  39.  
  40. pascal void StateMachineInit( Handle  *state_machine, UInt32 states, UInt32 chars)
  41. {
  42.     MyState *stateInfo;
  43.     MyStateTransition *stateArray;
  44.     int i;
  45.  
  46.     *state_machine = NewHandleClear(sizeof(MyState) + states*chars*sizeof(MyStateTransition));
  47.     if (0==*state_machine) DebugStr("\p mem alloc err");
  48.  
  49.     stateInfo = TheState(*state_machine);
  50.     stateArray = TheStateTransitions(*state_machine);
  51.  
  52.     stateInfo->numStates = states;
  53.     stateInfo->numChars = chars;
  54.     stateInfo->numTransitions = 0;
  55.     
  56.     for (i=0; i<states*chars; i++) {
  57.         stateArray->inputChar = kMaxInt;
  58.         stateArray->oldState = kMaxInt;
  59.         stateArray->newState = kMaxInt;
  60.         stateArray++;
  61.     }
  62. }
  63.  
  64. pascal void AddTransition( Handle state_machine, UInt32 state1, UInt32 state2, UInt32 first_char, UInt32 last_char )
  65. {
  66.     MyState *stateInfo;
  67.     MyStateTransition *nextState, *lastState, *p;
  68.     UInt32 i;
  69.  
  70.     stateInfo = TheState(state_machine);
  71.     lastState = nextState = TheStateTransitions(state_machine) + stateInfo->numTransitions;
  72.     
  73.     for (i=first_char; i<=last_char; i++) {
  74.         Boolean foundIt = false;
  75.         for (p = TheStateTransitions(state_machine); p<lastState; p++) {
  76.             if ((p->oldState == state1) && (p->inputChar==i)) {
  77.                 p->newState = state2;
  78.                 foundIt = true;
  79.                 break;
  80.             }
  81.         }
  82.         if (!foundIt) {
  83.             nextState->inputChar = i;
  84.             nextState->oldState = state1;
  85.             nextState->newState = state2;
  86.             nextState++;
  87.         }
  88.     }
  89.     stateInfo->numTransitions = nextState - TheStateTransitions(state_machine);
  90. }
  91.  
  92. pascal void RunStateMachine( Handle state_machine, UInt32 start_state, GetNextCharProc GetNextChar, UInt32 *stop_state)
  93. {
  94.     MyState *stateInfo;
  95.     MyStateTransition *lastState, *p;
  96.     UInt32 theInput,currentState;
  97.  
  98.     stateInfo = TheState(state_machine);
  99.     lastState = TheStateTransitions(state_machine) + stateInfo->numTransitions;
  100.     
  101.     currentState = start_state;
  102.     while (true) {
  103.         Boolean foundIt;
  104.         theInput = (*GetNextChar)(state_machine,currentState);
  105.         for (p=TheStateTransitions(state_machine); p<lastState; p++) {
  106.             foundIt = false;
  107.             if ((p->oldState == currentState) && (p->inputChar == theInput)) {
  108.                 currentState = p->newState;
  109.                 foundIt=true;
  110.                 break;
  111.             }
  112.         }
  113.         if (!foundIt) {
  114.             *stop_state = currentState;
  115.             return;
  116.         }
  117.     }
  118. }
  119.