home *** CD-ROM | disk | FTP | other *** search
/ MacHack 1998 / MacHack 1998.toast / Programming Contest / ~Solutions Submitted / Problem 09 - Three and One / Solution.cp < prev    next >
Encoding:
Text File  |  1998-06-19  |  3.5 KB  |  95 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:
  7. UInt32 );
  8. procedure AddTransition( state_machine: Handle; state1, state2: UInt32;
  9. first_char, last_char: UInt32 );
  10. procedure RunStateMachine( state_machine: Handle; start_state: UInt32;
  11. GetNextChar: GetNextCharProc; var stop_state: UInt32 );
  12.  
  13. This problem requires you to maintain and operate a state machine, consisting
  14. of rules that change the current machine state based on the current input.  Our
  15. state machines do not require that you produce any output other than the
  16. machine state.
  17.  
  18. StateMachineInit creates a new, empty state machine ready to accept state
  19. transitions, and containing states states (numbers 1 to states) and chars
  20. characters (numbered 1 to chars).  All the state machine information must be
  21. stored in the real Mac memory manager handle - it will be disposed with
  22. DisposeHandle and that must release all memory, so dont store any extra
  23. information outside the handle.  Also, you must be able to deal with having
  24. multiple state machine instantiated simultaneously.
  25.  
  26. AddTransition adds a transition from state1 to state2 for characters between
  27. (inclusive) first_char and last_char.  When you get to state1 and get a
  28. character between first_char and last_char you should proceed to state2.  The
  29. new transition overrides and previous transitions for these characters from
  30. state1 (ie, if you get transition 1->2 for chars 1-10, and then 1->3 for chars
  31. 5-6, you now have transition 1->2 for chars 1-4 and 7-10 and transition 1->3
  32. for chars 5-6).
  33.  
  34. RunStateMachine starts in start_state and calls GetNextChar repeatedly until
  35. either it returns 0 or until it returns a character for which there is no
  36. transition at the current state.  Each time GerNewChar supplies a character,
  37. the current state is updated based on the transition rule that applies to that
  38. combination of current state and current input.  When GetNextChar supplies a
  39. state for which no transition rule exists, the state machine halts and the
  40. final state is returned in stop_state.
  41. */
  42.  
  43. #include "Solution.h"
  44.  
  45. // Fill in your solution and then submit this folder
  46.  
  47. // Team Name: Three And One!
  48.  
  49. struct Header {
  50.     int numTransitions;
  51. };
  52.  
  53. struct Transition {
  54.     UInt32 state1; UInt32 state2; UInt32 first_char; UInt32 last_char;
  55. };
  56.  
  57. static UInt32 NextState(int numTransitions, const Transition transitions[], UInt32 state, UInt32 character)
  58. {
  59.     while (numTransitions != 0) {
  60.         const Transition& t = transitions[--numTransitions];
  61.         if (t.state1 == state && t.first_char <= character && t.last_char >= character)
  62.             return t.state2;
  63.     }
  64.     return 0;
  65. }
  66.  
  67. pascal void StateMachineInit( Handle  *state_machine, UInt32 /*states*/, UInt32 /*chars*/)
  68. {
  69.     *state_machine = NewHandleClear(sizeof(Header));
  70. }
  71.  
  72. pascal void AddTransition( Handle state_machine, UInt32 state1, UInt32 state2, UInt32 first_char, UInt32 last_char )
  73. {
  74.     Transition t = { state1, state2, first_char, last_char };
  75.     PtrAndHand(&t, state_machine, sizeof(t));
  76.     (**(Header**)state_machine).numTransitions += 1;
  77. }
  78.  
  79. pascal void RunStateMachine( Handle state_machine, UInt32 state, GetNextCharProc GetNextChar, UInt32 *stop_state)
  80. {
  81.     HLock(state_machine);
  82.     while (1) {
  83.         UInt32 character = GetNextChar(state_machine, state);
  84.         if (character == 0)
  85.             break;
  86.         UInt32 nextState = NextState((**(Header**)state_machine).numTransitions,
  87.             (Transition *)(*state_machine + sizeof(Header)), state, character);
  88.         if (nextState == 0)
  89.             break;
  90.         state = nextState;
  91.     }
  92.     HUnlock(state_machine);
  93.     *stop_state = state;
  94. }
  95.