infinite_state_machine.hpp

Go to the documentation of this file.

// SPDX-License-Identifier: MIT
 
#ifndef INFINITE_STATE_MACHINE_HPP_
#define INFINITE_STATE_MACHINE_HPP_
 
// for efficient double-ended queue operations
#include <deque>
 
// for find algorithms
#include <algorithm>
 
// Why infinite state machine? This state machine allows for an arbitrary number
// of nested states, enabling complex state hierarchies and transitions. No
// limits on the nesting depth, i.e. the number of active states is only limited
// by the available memory.
namespace infinite {
 
template <typename Topology> struct state {
  using topology_ptr = Topology *;
  topology_ptr super;
  topology_ptr self() { return static_cast<topology_ptr>(this); }
};
 
template <typename Topology> class state_machine {
public:
  virtual ~state_machine() {}
 
  // state_machine (const state_machine &other);
  // state_machine (state_machine &&other);
  // state_machine& operator= (state_machine &&other);
  // state_machine& operator= (const state_machine &other);
 
  struct transition {
    std::deque<state<Topology> *> exits;
    std::deque<state<Topology> *> enters;
  };
 
  struct transition go(state<Topology> *to) {
    std::deque<state<Topology> *> exits, enters;
    // super, sub --> sub, super (reverse)
    exits.assign(states.rbegin(), states.rend());
    states.clear();
    if (to != nullptr) {
      // super.super, super, to!
      //
      // Avoid duplicating states in the enters deque.
      // Duplicates correspond to cyclic state topologies.
      for (;
           to && std::find(enters.rbegin(), enters.rend(), to) == enters.rend();
           to = to->super)
        enters.push_front(to);
      // Now match up the exits and enters.
      // Transfer any matching states from exits to states.
      while (!exits.empty() && !enters.empty() &&
             exits.back() == enters.front()) {
        states.push_back(exits.back());
        exits.pop_back();
        enters.pop_front();
      }
      states.insert(states.end(), enters.begin(), enters.end());
    }
    return {exits, enters};
  }
 
  // Operation go(to) is the only mutator.
  // The rest are query methods on the state vector.
 
  state<Topology> *at() const {
    return states.empty() ? nullptr : states.back();
  }
 
  bool in(state<Topology> *state) const {
    return std::find(states.cbegin(), states.cend(), state) != states.cend();
  }
 
private:
  std::deque<state<Topology> *> states;
};
 
} /* namespace infinite */
 
#endif /* INFINITE_STATE_MACHINE_HPP_ */