text: #include "search_space.h"
  
  #include "global_state.h"
  #include "globals.h"
  #include "task_proxy.h"
  
  #include <cassert>
  #include "search_node_info.h"
  
  using namespace std;
  
  SearchNode::SearchNode(const StateRegistry &state_registry,
                         StateID state_id,
                         SearchNodeInfo &info,
                         OperatorCost cost_type)
      : state_registry(state_registry),
        state_id(state_id),
        info(info),
        cost_type(cost_type) {
      assert(state_id != StateID::no_state);
  }
  
  GlobalState SearchNode::get_state() const {
      return state_registry.lookup_state(state_id);
  }
  
  bool SearchNode::is_open() const {
      return info.status == SearchNodeInfo::OPEN;
  }
  
  bool SearchNode::is_closed() const {
      return info.status == SearchNodeInfo::CLOSED;
  }
  
  bool SearchNode::is_dead_end() const {
      return info.status == SearchNodeInfo::DEAD_END;
  }
  
  bool SearchNode::is_new() const {
      return info.status == SearchNodeInfo::NEW;
  }
  
  int SearchNode::get_g() const {
      assert(info.g >= 0);
      return info.g;
  }
  
  int SearchNode::get_real_g() const {
      return info.real_g;
  }
  
  void SearchNode::open_initial() {
      assert(info.status == SearchNodeInfo::NEW);
      info.status = SearchNodeInfo::OPEN;
      info.g = 0;
      info.real_g = 0;
      info.parent_state_id = StateID::no_state;
      info.creating_operator = OperatorID::no_operator;
  }
  
  void SearchNode::open(const SearchNode &parent_node,
                        const OperatorProxy &parent_op) {
      assert(info.status == SearchNodeInfo::NEW);
      info.status = SearchNodeInfo::OPEN;
      info.g = parent_node.info.g + get_adjusted_action_cost(parent_op, cost_type);
      info.real_g = parent_node.info.real_g + parent_op.get_cost();
      info.parent_state_id = parent_node.get_state_id();
      info.creating_operator = OperatorID(parent_op.get_id());
  }
  
  void SearchNode::reopen(const SearchNode &parent_node,
                          const OperatorProxy &parent_op) {
      assert(info.status == SearchNodeInfo::OPEN ||
             info.status == SearchNodeInfo::CLOSED);
  
      // The latter possibility is for inconsistent heuristics, which
      // may require reopening closed nodes.
      info.status = SearchNodeInfo::OPEN;
      info.g = parent_node.info.g + get_adjusted_action_cost(parent_op, cost_type);
      info.real_g = parent_node.info.real_g + parent_op.get_cost();
      info.parent_state_id = parent_node.get_state_id();
      info.creating_operator = OperatorID(parent_op.get_id());
  }
  
  // like reopen, except doesn't change status
  void SearchNode::update_parent(const SearchNode &parent_node,
                                 const OperatorProxy &parent_op) {
      assert(info.status == SearchNodeInfo::OPEN ||
             info.status == SearchNodeInfo::CLOSED);
      // The latter possibility is for inconsistent heuristics, which
      // may require reopening closed nodes.
      info.g = parent_node.info.g + get_adjusted_action_cost(parent_op, cost_type);
      info.real_g = parent_node.info.real_g + parent_op.get_cost();
      info.parent_state_id = parent_node.get_state_id();
      info.creating_operator = OperatorID(parent_op.get_id());
  }
  
  void SearchNode::close() {
      assert(info.status == SearchNodeInfo::OPEN);
      info.status = SearchNodeInfo::CLOSED;
  }
  
  void SearchNode::mark_as_dead_end() {
      info.status = SearchNodeInfo::DEAD_END;
  }
  
  void SearchNode::dump(const TaskProxy &task_proxy) const {
      cout << state_id << ": ";
      get_state().dump_fdr();
      if (info.creating_operator != OperatorID::no_operator) {
          OperatorsProxy operators = task_proxy.get_operators();
          OperatorProxy op = operators[info.creating_operator.get_index()];
          cout << " created by " << op.get_name()
               << " from " << info.parent_state_id << endl;
      } else {
          cout << " no parent" << endl;
      }
  }
  
  SearchSpace::SearchSpace(StateRegistry &state_registry, OperatorCost cost_type)
      : state_registry(state_registry),
        cost_type(cost_type) {
  }
  
  SearchNode SearchSpace::get_node(const GlobalState &state) {
      return SearchNode(
          state_registry, state.get_id(), search_node_infos[state], cost_type);
  }
  
  void SearchSpace::trace_path(const GlobalState &goal_state,
                               vector<OperatorID> &path) const {
      GlobalState current_state = goal_state;
      assert(path.empty());
      for (;;) {
          const SearchNodeInfo &info = search_node_infos[current_state];
          if (info.creating_operator == OperatorID::no_operator) {
              assert(info.parent_state_id == StateID::no_state);
              break;
          }
          path.push_back(info.creating_operator);
          current_state = state_registry.lookup_state(info.parent_state_id);
      }
      reverse(path.begin(), path.end());
  }
  
  void SearchSpace::dump(const TaskProxy &task_proxy) const {
      OperatorsProxy operators = task_proxy.get_operators();
      for (StateID id : state_registry) {
          /* The body duplicates SearchNode::dump() but we cannot create
             a search node without discarding the const qualifier. */
          GlobalState state = state_registry.lookup_state(id);
          const SearchNodeInfo &node_info = search_node_infos[state];
          cout << id << ": ";
          state.dump_fdr();
          if (node_info.creating_operator != OperatorID::no_operator &&
              node_info.parent_state_id != StateID::no_state) {
              OperatorProxy op = operators[node_info.creating_operator.get_index()];
              cout << " created by " << op.get_name()
                   << " from " << node_info.parent_state_id << endl;
          } else {
              cout << "has no parent" << endl;
          }
      }
  }
  
  void SearchSpace::print_statistics() const {
      cout << "Number of registered states: "
           << state_registry.size() << endl;
  }
  