machine - Código C++ para máquina de estado
machine state in c (6)
Considere el uso de tablas en lugar de instrucciones de switch . Una columna podría ser el criterio de transición y otra columna es el estado de destino.
Esto se ajusta muy bien porque no tiene que cambiar la función de procesamiento de tablas; sólo agrega otra fila a la tabla.
+------------------+---------------------+---------------+
| Current state ID | transition criteria | Next state ID |
+------------------+---------------------+---------------+
| | | |
+------------------+---------------------+---------------+
En mi código en el trabajo, usamos una columna de punteros de función en lugar de la "ID de estado siguiente". La tabla es un archivo separado con funciones de acceso definidas. Hay una o más instrucciones de inclusión para resolver cada puntero de función.
Edición 1: Ejemplo de archivos de tablas separadas.
tabla.h
#ifndef TABLE_H
#define TABLE_H
struct Table_Entry
{
unsigned int current_state_id;
unsigned char transition_letter;
unsigned int next_state_id;
};
Table_Entry const * table_begin(void);
Table_Entry const * table_end(void);
#endif // TABLE_H
table.cpp:
#include "table.h"
static const Table_Entry my_table[] =
{
// Current Transition Next
// State ID Letter State ID
{ 0, ''A'', 1}, // From 0 goto 1 if letter is ''A''.
{ 0, ''B'', 2}, // From 0 goto 2 if letter is ''B''.
{ 0, ''C'', 3}, // From 0 goto 3 if letter is ''C''.
{ 1, ''A'', 1}, // From 1 goto 1 if letter is ''A''.
{ 1, ''B'', 3}, // From 1 goto 3 if letter is ''B''.
{ 1, ''C'', 0}, // From 1 goto 0 if letter is ''C''.
};
static const unsigned int TABLE_SIZE =
sizeof(my_table) / sizeof(my_table[0]);
Table_Entry const *
table_begin(void)
{
return &my_table[0];
}
Table_Entry const *
table_end(void)
{
return &my_table[TABLE_SIZE];
}
state_machine.cpp
#include "table.h"
#include <iostream>
using namespace std; // Because I''m lazy.
void
Execute_State_Machine(void)
{
unsigned int current_state = 0;
while (1)
{
char transition_letter;
cout << "Current state: " << current_state << "/n";
cout << "Enter transition letter: ";
cin >> transition_letter;
cin.ignore(1000, ''/n''); /* Eat up the ''/n'' still in the input stream */
Table_Entry const * p_entry = table_begin();
Table_Entry const * const p_table_end = table_end();
bool state_found = false;
while ((!state_found) && (p_entry != p_table_end))
{
if (p_entry->current_state_id == current_state)
{
if (p_entry->transition_letter == transition_letter)
{
cout << "State found, transitioning"
<< " from state " << current_state
<< ", to state " << p_entry->next_state_id
<< "/n";
current_state = p_entry->next_state_id;
state_found = true;
break;
}
}
++p_entry;
}
if (!state_found)
{
cerr << "Transition letter not found, current state not changed./n";
}
}
}
Esta fue una pregunta de entrevista para ser codificada en C ++:
Escriba el código para una máquina expendedora: comience con una simple donde solo venda un tipo de artículo. Así que dos variables de estado: dinero e inventario, harían.
Mi respuesta:
Yo usaría una máquina de estados que tiene alrededor de 3-4 estados. Use una variable de enumeración para indicar el estado y use una declaración de cambio de caso, donde cada caso tiene las operaciones que se deben hacer correspondientes a cada estado y permanezca en un bucle para pasar de un estado a otro.
La siguiente pregunta:
Pero el uso de una declaración de cambio de caso no se "escala bien" para la adición de más estados y la modificación de las operaciones existentes en un estado. ¿Cómo vas a lidiar con ese problema?
No pude responder a esta pregunta en ese momento. Pero luego pensé, probablemente pueda:
- tienen diferentes funciones para diferentes estados (cada función corresponde a un estado)
- tiene un
std::mapfrom (string, function) donde string indica el estado para llamar a la función de estado correspondiente. - La función principal tiene una variable de cadena (que comienza en el estado inicial) y llama a la función correspondiente a esa variable en un bucle. Cada función realiza las operaciones necesarias y devuelve el nuevo estado a la función principal.
Mis preguntas son:
- ¿Cuál es el problema con las declaraciones de cambio de caso con respecto a la escalabilidad en el contexto de los sistemas de software a gran escala?
- Si es así, ¿mi solución (que actualmente creo que es un poco más modular que tener un código lineal largo) va a resolver el problema?
La pregunta de la entrevista está esperando respuestas de los modismos de C ++ y los patrones de diseño para sistemas de software a gran escala.
Estaba pensando en un enfoque más OO, utilizando el State Pattern :
La máquina:
// machine.h
#pragma once
#include "MachineStates.h"
class AbstractState;
class Machine {
friend class AbstractState;
public:
Machine(int inStockQuantity);
void sell(int quantity);
void refill(int quantity);
int getCurrentStock();
~Machine();
private:
int mStockQuantity;
AbstractState* mState;
};
// machine.cpp
#include "Machine.h"
Machine::Machine(int inStockQuantity) :
mStockQuantity(inStockQuantity), mState(new Normal()) {
}
Machine::~Machine() {
delete mState;
}
void Machine::sell(int quantity) {
mState->sell(*this, quantity);
}
void Machine::refill(int quantity) {
mState->refill(*this, quantity);
}
int Machine::getCurrentStock() {
return mStockQuantity;
}
Los Estados:
// MachineStates.h
#pragma once
#include "Machine.h"
#include <exception>
#include <stdexcept>
class Machine;
class AbstractState {
public:
virtual void sell(Machine& machine, int quantity) = 0;
virtual void refill(Machine& machine, int quantity) = 0;
virtual ~AbstractState();
protected:
void setState(Machine& machine, AbstractState* st);
void updateStock(Machine& machine, int quantity);
};
class Normal : public AbstractState {
public:
virtual void sell(Machine& machine, int quantity);
virtual void refill(Machine& machine, int quantity);
virtual ~Normal();
};
class SoldOut : public AbstractState {
public:
virtual void sell(Machine& machine, int quantity);
virtual void refill(Machine& machine, int quantity);
virtual ~SoldOut();
};
// MachineStates.cpp
#include "MachineStates.h"
AbstractState::~AbstractState() {
}
void AbstractState::setState(Machine& machine, AbstractState* state) {
AbstractState* aux = machine.mState;
machine.mState = state;
delete aux;
}
void AbstractState::updateStock(Machine& machine, int quantity) {
machine.mStockQuantity = quantity;
}
Normal::~Normal() {
}
void Normal::sell(Machine& machine, int quantity) {
int currStock = machine.getCurrentStock();
if (currStock < quantity) {
throw std::runtime_error("Not enough stock");
}
updateStock(machine, currStock - quantity);
if (machine.getCurrentStock() == 0) {
setState(machine, new SoldOut());
}
}
void Normal::refill(Machine& machine, int quantity) {
int currStock = machine.getCurrentStock();
updateStock(machine, currStock + quantity);
}
SoldOut::~SoldOut() {
}
void SoldOut::sell(Machine& machine, int quantity) {
throw std::runtime_error("Sold out!");
}
void SoldOut::refill(Machine& machine, int quantity) {
updateStock(machine, quantity);
setState(machine, new Normal());
}
No estoy acostumbrado a programar en C ++, pero este código se compila aparentemente contra GCC 4.8.2 y valgrind no muestra fugas, así que supongo que está bien. No estoy calculando dinero, pero no necesito esto para mostrarte la idea.
Para probarlo:
#include <iostream>
#include <stdexcept>
#include "Machine.h"
#include "MachineStates.h"
int main() {
Machine m(10);
m.sell(10);
std::cout << "Sold 10 items" << std::endl;
try {
m.sell(1);
} catch (std::exception& e) {
std::cerr << e.what() << std::endl;
}
m.refill(20);
std::cout << "Refilled 20 items" << std::endl;
m.sell(10);
std::cout << "Sold 10 items" << std::endl;
std::cout << "Remaining " << m.getCurrentStock() << " items" << std::endl;
m.sell(5);
std::cout << "Sold 5 items" << std::endl;
std::cout << "Remaining " << m.getCurrentStock() << " items" << std::endl;
try {
m.sell(10);
} catch (std::exception& e) {
std::cerr << e.what() << std::endl;
}
return 0;
}
La salida es:
Sold 10 items Sold out! Refilled 20 items Sold 10 items Remaining 10 items Sold 5 items Remaining 5 items Not enough stock
Ahora, si desea agregar un estado Broken , todo lo que necesita es otro hijo de AbstractState . Tal vez necesites agregar una propiedad broken en la Machine también.
Para agregar más productos, debe tener un mapa de productos y su respectiva cantidad en inventario, y así sucesivamente ...
He escrito muchas máquinas de estados usando estos métodos. Pero cuando escribí Transceiver Library de Cisco para el Nexus 7000 (un conmutador de $ 117,000) usé un método que inventé en los años 80. Eso fue usar una macro que hace que la máquina de estado se parezca más al código de bloqueo multitarea. Las macros están escritas para C, pero las he usado con pequeñas modificaciones para C ++ cuando trabajé para DELL. Puede leer más sobre esto aquí: https://www.codeproject.com/Articles/37037/Macros-to-simulate-multi-tasking-blocking-code-at
No sé si eso te habría llevado a la entrevista, pero personalmente me abstendré de codificar manualmente cualquier máquina de estado, especialmente si se trata de un entorno profesional. Las máquinas de estado son un problema bien investigado, y existen herramientas de código abierto bien probadas que a menudo producen un código superior al que usted mismo producirá a mano, y también lo ayudan a diagnosticar problemas con su máquina de estado, por ejemplo. Ser capaz de generar diagramas de estado automáticamente.
Mis herramientas para ir a este tipo de problema son:
Una vez escribí una máquina de estados en C ++, donde necesitaba la misma transición para muchos pares de estados (fuente → pares de destino). Quiero ilustrar un ejemplo:
4 -> 8 /
5 -> 9 /_ action1()
6 -> 10 /
7 -> 11 /
8 -> 4 /
9 -> 5 /_ action2()
10 -> 6 /
11 -> 7 /
Lo que se me ocurrió fue un conjunto de (criterios de transición + próximo estado + función de "acción" que se llamará). Para mantener las cosas en general, tanto los criterios de transición como el siguiente estado se escribieron como funtores (funciones lambda):
typedef std::function<bool(int)> TransitionCriteria;
typedef std::function<int(int)> TransitionNewState;
typedef std::function<void(int)> TransitionAction; // gets passed the old state
Esta solución es agradable si tiene muchas transiciones que se aplican a muchos estados diferentes como en el ejemplo anterior. Sin embargo, para cada "paso", este método requiere escanear linealmente la lista de todas las diferentes transiciones.
Para los ejemplos anteriores, habría dos transiciones de este tipo:
struct Transition {
TransitionCriteria criteria;
TransitionNewState newState;
TransitionAction action;
Transition(TransitionCriteria c, TransitionNewState n, TransitionAction a)
: criteria(c), newState(n), action(a) {}
};
std::vector<Transition> transitions;
transitions.push_back(Transition(
[](int oldState){ return oldState >= 4 && oldState < 8; },
[](int oldState){ return oldState + 4; },
[](int oldState){ std::cout << "action1" << std::endl; }
));
transitions.push_back(Transition(
[](int oldState){ return oldState >= 8 && oldState < 12; },
[](int oldState){ return oldState - 4; },
[](int oldState){ std::cout << "action2" << std::endl; }
));
#include <stdio.h>
#include <iostream>
using namespace std;
class State;
enum state{ON=0,OFF};
class Switch {
private:
State* offState;
State* onState;
State* currState;
public:
~Switch();
Switch();
void SetState(int st);
void on();
void off();
};
class State{
public:
State(){}
virtual void on(Switch* op){}
virtual void off(Switch* op){}
};
class OnState : public State{
public:
OnState(){
cout << "OnState State Initialized" << endl;
}
void on(Switch* op);
void off(Switch* op);
};
class OffState : public State{
public:
OffState(){
cout << "OffState State Initialized" << endl;
}
void on(Switch* op);
void off(Switch* op);
};
Switch::Switch(){
offState = new OffState();
onState = new OnState();
currState=offState;
}
Switch::~Switch(){
if(offState != NULL)
delete offState;
if(onState != NULL)
delete onState;
}
void Switch::SetState(int newState){
if(newState == ON)
{
currState = onState;
}
else if(newState == OFF)
{
currState = offState;
}
}
void Switch::on(){
currState->on(this);
}
void Switch::off(){
currState->off(this);
}
void OffState::on(Switch* op){
cout << "State transition from OFF to ON" << endl;
op->SetState(ON);
}
void OffState::off(Switch* op){
cout << "Already in OFF state" << endl;
}
void OnState::on(Switch* op){
cout << "Already in ON state" << endl;
}
void OnState::off(Switch* op){
cout << "State transition from ON to OFF" << endl;
op->SetState(OFF);
}
int main(){
Switch* swObj = new Switch();
int ch;
do{
switch(ch){
case 1: swObj->on();
break;
case 0: swObj->off();
break;
default : cout << "Invalid choice"<<endl;
break;
}
cout << "Enter 0/1: ";
cin >> ch;
}while(true);`enter code here`
delete swObj;
return 0;
}