turing-m.cpp

这是个很好的源代码,有用的

  cout << endl;

  cout << setw(text_max_size) << left << text_internal_states.c_str() << " : ";
  for (size_t i = 0; i < internal_states_.size(); i++)
  {
    cout << setw (max_state_size_) << internal_states_[i].c_str() << " ";
  }
  cout << endl;


}

// =========
void TuringMachine::show_alphabet (const Tapes_t::const_iterator& iter) const
{
  iter->second.show_alphabet();
}

// =========
void TuringMachine::show_alphabets () const
{
Tapes_t::const_iterator iter;
  cout << "\t   ====== Alphabet Definition ======" << endl;
  for (iter = tapes_.begin(); iter != tapes_.end(); iter++)
  {
    cout << "\t      ------ Tape# " << distance (tapes_.begin(), iter) << " ------" << endl;
    show_alphabet (iter);
    cout << endl;
  }
}

// =========
void TuringMachine::show_transition () const
{
Transitions_t::const_iterator iter;
  cout << "\t   ====== Transition Rules Definition ======" << endl;
  for (iter = transitions_.begin(); iter != transitions_.end(); iter++)
  {
    cout << getstr_rule_S (transitions_.begin(), iter, max_state_size_, max_symbol_size_) << endl;
  }
  cout << endl;
}

// =========
string TuringMachine::getstr_rule_S (
		Transitions_t::const_iterator iter0_i,
		Transitions_t::const_iterator iter_i,
		size_t	max_state_size_i,	
		size_t	max_symbol_size_i	
		)
{
ostringstream oss;
  oss	<< ""
	<< "Rule#"
	<< setw (SETW_RULE_NUMBER)
	<< right
	<< distance (iter0_i, iter_i)
	<< " :   "
	<< setw (max_state_size_i)
	<< iter_i->first.get_state().c_str()
	<< " [ " 
	<< iter_i->first.getstr_symbols(max_symbol_size_i)
	<< "] ---> "
	<< setw (max_state_size_i)
	<< iter_i->second.get_state().c_str()
	<< " [ " 
	<< iter_i->second.getstr_symbols_and_shifts(max_symbol_size_i)
	<< "]";

  return oss.str();
}
   
// =========
void TuringMachine::show_tape (const Tapes_t::const_iterator& iter) const
{
  iter->second.show_tape();
}


// =========
void TuringMachine::show_situation (const string& msg_i) const
{
Tapes_t::const_iterator const_iter;
const size_t size1 = 5;

  if (!cur_transitions_.empty())
  {  
const Transitions_t::const_iterator find_iter = transitions_.find ((*cur_transitions_.rbegin())->first);
    assert (find_iter != transitions_.end());
    cout << "\t" 
         << getstr_id_info ()
         << "Applied " 
         << getstr_rule_S (transitions_.begin(), find_iter, max_state_size_, max_symbol_size_) 
         << endl;
    cout << endl;
  }

  IF_NOT_EMPTY (msg_i, size1, '-');


  cout << "\tState  : " << *cur_states_.rbegin() << endl;
  //cout << "\t" << string (size2, '-') << endl;

  for (const_iter = tapes_.begin(); 
       const_iter != tapes_.end(); 
       const_iter++
      )
  {
    cout << "Tape#" << distance (tapes_.begin(), const_iter) << " : ";
    show_tape (const_iter);
  }
  //cout << endl;

}


// =========
void TuringMachine::show_statistics (const string& msg_i) const
{
const size_t size1 = 5;

  IF_NOT_EMPTY (msg_i, size1, '-');

uint total = accumulate (transition_statistics_.begin(), transition_statistics_.end(), 0);

const string text_statistics ("Statistics");
const string text_transition ("Transition");
const string text_rules ("Rules");
const string text_times ("Times");
const string text_total ("Total");
const string delim (":");

const size_t max_size1 = MAX_VALUE (text_statistics.size(), text_transition.size());
const size_t the_size2 = 3;
const size_t the_size1 = the_size2 + 1 + max_size1 + 1 + the_size2;
const size_t the_size3 = (the_size1 - 1)/2;
const size_t the_size4 = (the_size1 - 1) - the_size3;
  assert (text_rules.size() < (the_size3 - 1));
  assert (text_times.size() < (the_size4 - 1));

const string l_border ("\t      |");		
const string r_border ("|");		

  cout << l_border << string (the_size1, '=') << r_border << endl;

  cout << l_border 
       << string (the_size2, '-') 
       << " "
       << setw (max_size1)
       << left
       << text_statistics.c_str()
       << " "
       << string (the_size2, '-') 
       << r_border 
       << endl;

  cout << l_border 
       << string (the_size2, '.') 
       << " "
       << setw (max_size1)
       << left
       << text_transition.c_str()
       << " "
       << string (the_size2, '.') 
       << r_border 
       << endl;

  cout << l_border << string (the_size1, '-') << r_border << endl;

  cout << l_border 
       << setw (the_size3 - 1)
       << right
       << text_rules.c_str()
       << " "
       << delim
       << setw (the_size4 - 1)
       << right
       << text_times.c_str()
       << " "
       << r_border 
       << endl;

  cout << l_border << string (the_size1, '-') << r_border << endl;

  for (size_t i = 0; i < transition_statistics_.size(); i++)
  {
    cout << l_border 
         << setw (the_size3 - 1)
         << right
         << i
         << " "
         << delim
         << setw (the_size4 - 1)
         << right
         << transition_statistics_[i]
         << " "
         << r_border 
         << endl;
  }
  cout << l_border << string (the_size1, '-') << r_border << endl;

  cout << l_border 
       << setw (the_size3 - 1)
       << right
       << text_total.c_str()
       << " "
       << delim
       << setw (the_size4 - 1)
       << right
       << total
       << " "
       << r_border 
       << endl;

  cout << l_border << string (the_size1, '=') << r_border << endl;

}


// =========
bool TuringMachine::is_initial_state (const state_t& state_i) const
{
  return (find (initial_states_.begin(), initial_states_.end(), state_i) != initial_states_.end());
}

// =========
bool TuringMachine::is_halting_state (const state_t& state_i) const
{
  return (find (halting_states_.begin(), halting_states_.end(), state_i) != halting_states_.end());
}


// =========
bool TuringMachine::is_internal_state (const state_t& state_i) const
{
  return (find (internal_states_.begin(), internal_states_.end(), state_i) != internal_states_.end());
}

// =========
bool TuringMachine::is_valid_state (const state_t& state_i) const
{
  return (is_initial_state(state_i) || is_halting_state (state_i) || is_internal_state (state_i));
}



// =========
bool TuringMachine::check_states () const
{
bool	ret_bool_value = true;

state_t	phisical_empty_state = string();
vector<state_t>::const_iterator	iter;

  assert (!initial_states_.empty());
  assert (!halting_states_.empty());
  assert (!internal_states_.empty());

  // ---------
  iter = find (initial_states_.begin(), initial_states_.end(), phisical_empty_state); 
  if (iter != initial_states_.end())
  {
    ret_bool_value = false;
    FATAL_MSG	("Initial state#"
		<< distance (initial_states_.begin(), iter)
		<< " is empty : <"
		<< *iter
		<< ">"
		);
  }

  iter = find (halting_states_.begin(), halting_states_.end(), phisical_empty_state); 
  if (iter != halting_states_.end())
  {
    ret_bool_value = false;
    FATAL_MSG	("Halting state#"
		<< distance (halting_states_.begin(), iter)
		<< " is empty : <"
		<< *iter
		<< ">"
		);
  }


  iter = find (internal_states_.begin(), internal_states_.end(), phisical_empty_state); 
  if (iter != internal_states_.end())
  {
    ret_bool_value = false;
    FATAL_MSG	("Internal state#"
		<< distance (internal_states_.begin(), iter)
		<< " is empty : <"
		<< *iter
		<< ">"
		);
  }

  // ------
vector<state_t> tmp_all_states = get_all_states();
vector<state_t>::iterator	iter2;
  for (iter2 = tmp_all_states.begin(); iter2 != tmp_all_states.end(); iter2++)
  {
    assert (count (iter2, tmp_all_states.end(), *iter2));
    if (count (iter2, tmp_all_states.end(), *iter2) > 1)
    {
      ret_bool_value = false;
      FATAL_MSG	("State "
		<< "<"
		<< (*iter2)
	 	<< ">"
		<< " occurs more than once"
		);
    }
  }

  // -----------
  return ret_bool_value;
} // check_states


// =========
bool TuringMachine::check_alphabets () const
{
bool	ret_bool_value = true;

Tapes_t::const_iterator	iter;
  for (iter = tapes_.begin(); iter != tapes_.end(); iter++)
  {
    assert (iter->first == static_cast<size_t> (distance (tapes_.begin(), iter)));
    if (!(iter->second.check_alphabet()))	ret_bool_value = false;	
  }

  return ret_bool_value;
}


// =========
bool TuringMachine::check_transition () const
{
bool	ret_bool_value = true;

Transitions_t::const_iterator	iter;
Tapes_t::const_iterator		iter2;
size_t		i;
state_t		cur_state;
size_t		cur_total_symbols;
symbol_t	cur_symbol;

state_t		next_state;
size_t		next_total_symbols;
symbol_t	next_symbol;
shift_t	shift;

  if (transitions_.empty())
  {
    ret_bool_value = false;
    FATAL_MSG	("No transition function");
  }

  for (iter = transitions_.begin(); iter != transitions_.end(); iter++)
  {
    const string transitions_line_info ("Transition Line#" + to_string (distance (transitions_.begin(), iter)));
    const string transitions_line_and_tape_no_info (transitions_line_info + ", tape#");

    // --- first ---
    cur_state = iter->first.get_state();
    cur_total_symbols = iter->first.get_total_symbols();

    if (!((is_initial_state (cur_state)) || (is_internal_state (cur_state))))
    {
      ret_bool_value = false;
      FATAL_MSG	(transitions_line_info
		<< " : illegal cur-state = <"
		<< cur_state
		<< ">"
		);
    }

    if (cur_total_symbols != tapes_.size())
    {
      ret_bool_value = false;
      FATAL_MSG	(transitions_line_info
		<< " : number-of-cur-symbols = "
		<< cur_total_symbols
		<< " is not equal number-of-tapes = "
		<< tapes_.size()
		);
    }


    for (i = 0, iter2 = tapes_.begin(); i < cur_total_symbols; i++, iter2++)
    {
      assert (iter2->first == i);
      cur_symbol = iter->first.get_symbol(i);

      if (!(iter2->second.is_valid_symbol(cur_symbol)))
      {
        ret_bool_value = false;
        FATAL_MSG	(transitions_line_and_tape_no_info
			<< i
			<< " : illegal cur-symbol = <"
			<< cur_symbol
			<< ">"
			);
      }
    }

    
    // --- second ---
    next_state = iter->second.get_state();
    next_total_symbols = iter->second.get_total_symbols();

    //if (!((is_halting_state (next_state)) || (is_internal_state (next_state))))
    if (!is_valid_state(next_state))
    {
      ret_bool_value = false;
      FATAL_MSG	(transitions_line_info
		<< " : illegal next-state = <"
		<< next_state
		<< ">"
		);
    }

    if (next_total_symbols != tapes_.size())
    {
      ret_bool_value = false;
      FATAL_MSG	(transitions_line_info
		<< " : number-of-next-symbols = "
		<< next_total_symbols
		<< " is not equal number-of-tapes = "
		<< tapes_.size()
		);
    }

    for (i = 0, iter2 = tapes_.begin(); i < next_total_symbols; i++, iter2++)
    {
      assert (iter2->first == i);
      next_symbol = iter->second.get_symbol(i);
      shift = iter->second.get_shift(i);

      if (!(iter2->second.is_valid_symbol(next_symbol)))
      {
        ret_bool_value = false;
        FATAL_MSG	(transitions_line_and_tape_no_info
			<< i
			<< " : illegal next-symbol = <"
			<< next_symbol
			<< ">"
			);
      }

      if (!(iter2->second.is_valid_shift(shift)))
      {
        ret_bool_value = false;
        FATAL_MSG	(transitions_line_and_tape_no_info
			<< i
			<< " : illegal shift = <"
			<< shift
			<< ">"
			);
      }

    }

  } // for (iter = transition.begin(); ...
  return ret_bool_value;
}

	
// =========
bool TuringMachine::get_check_results () const
{
  return check_results_;
}

// =========
string TuringMachine::getstr_id_info (bool detail_flag_i) const
{
ostringstream oss;
  oss << "< ";
  if (detail_flag_i)
  {
    oss << "TM #"
        << serial_no_ 
        << ", "
        << "Input #"
        << cur_input_set_no_;
  }
  else
  {
    oss << "Run "
        << serial_no_ 
        << "."
        << cur_input_set_no_;
  }
  oss << " > ";

  return oss.str();
}