run.cpp

The program simulates a Nondeterministic Multitape Turing Machine. It works as ordinary (Determinist

void Run::show_input_words_file_sample_S  ()
{
// -------------------
const string text11("Input words file sample-1");
const string text12("Number of tapes = 3");
vector<vector<string> >	sample1;

typedef char irow_t [3];

const irow_t row101[] = {"1", "0", "1", "0", "0", "1", "0"}; 
const irow_t row102[] = {"b"}; 
const irow_t row103[] = {"b"}; 

  sample1.push_back(vector<string> (row101, row101 + sizeof (row101)/sizeof(*row101)));
  sample1.push_back(vector<string> (row102, row102 + sizeof (row102)/sizeof(*row102)));
  sample1.push_back(vector<string> (row103, row103 + sizeof (row103)/sizeof(*row103)));

  cout	<< endl;
  cout	<< space3
	<< string (setw10, '=')
	<< " "
	<< text11
	<< " "
	<< string (setw10, '=')
	<< endl;
  cout	<< space3
	<< string (setw12, '-')
	<< " "
	<< text12
	<< " "
	<< string (setw12, '-')
	<< endl;

  for (size_t i = 0; i < sample1.size(); i++)
  {
    copy (sample1[i].begin(), sample1[i].end(), ostream_iterator<string> (cout, " "));
    cout << endl;
  }

  cout	<< space3 << string (setw10 + 1 + text11.size() + 1 + setw10, '=') << endl;


// -------------------
const string text21("Input words file sample-2");
const string text22("Number of tapes = 3");
vector<vector<string> >	sample2;

typedef char irow_t [3];

const irow_t row201[] = {"1", "0", HEAD_START_POSITION_POINTER_REDERVED_SYMBOL, "1", "0", "0", "1", "0"}; 
const irow_t row202[] = {"b"}; 
const irow_t row203[] = {HEAD_START_POSITION_POINTER_REDERVED_SYMBOL, "b"}; 

  sample2.push_back(vector<string> (row201, row201 + sizeof (row201)/sizeof(*row201)));
  sample2.push_back(vector<string> (row202, row202 + sizeof (row202)/sizeof(*row202)));
  sample2.push_back(vector<string> (row203, row203 + sizeof (row203)/sizeof(*row203)));

  cout	<< endl;
  cout	<< space3
	<< string (setw10, '=')
	<< " "
	<< text21
	<< " "
	<< string (setw10, '=')
	<< endl;
  cout	<< space3
	<< string (setw12, '-')
	<< " "
	<< text22
	<< " "
	<< string (setw12, '-')
	<< endl;

  for (size_t i = 0; i < sample2.size(); i++)
  {
    copy (sample2[i].begin(), sample2[i].end(), ostream_iterator<string> (cout, " "));
    cout << endl;
  }

  cout	<< space3 << string (setw10 + 1 + text21.size() + 1 + setw10, '=') << endl;

  cout	<< space3
        << "Note! Symbol " 
        << "\"" 
        << HEAD_START_POSITION_POINTER_REDERVED_SYMBOL 
        << "\"" 
        << " is (optional) pointer to start position of machine head"
        << endl;

}


// =========
void Run::show_metafile_content_S ()
{
size_t	text_setw = 0;
const string text1 ("Number of tapes");
const string text2 ("States file name");
const string text3 ("Alphabet file name");
const string text4 ("Transitions file name");
const string text5 ("Input words files names");
const string text6 ("Description file name");

  text_setw = MAX_VALUE (text_setw, text1.size());
  text_setw = MAX_VALUE (text_setw, text2.size());
  text_setw = MAX_VALUE (text_setw, text3.size());
  text_setw = MAX_VALUE (text_setw, text4.size());
  text_setw = MAX_VALUE (text_setw, text5.size());
  text_setw = MAX_VALUE (text_setw, text6.size());


  cout << space3 << string (setw10, '=') << " Data selected from Metafile " << metafile_name_s << " " << string (setw10, '=') << endl;

  for (size_t i = 0; i < metafile_data_s.size(); i++)
  {
    cout << space5 << string (setw10, '-') << " Nondeterministic Turing Machine# " << (i + 1) << " " << string (setw10, '-') << endl;
    cout << space6 << setw(text_setw) << left << text6.c_str() << " : " << metafile_data_s[i][METAFILE_FIELD__DESCR_FILE_NAME] << endl;
    cout << space6 << setw(text_setw) << left << text1.c_str() << " : " << metafile_data_s[i][METAFILE_FIELD__NUMBER_OF_TAPES] << endl;
    cout << space6 << setw(text_setw) << left << text2.c_str() << " : " << metafile_data_s[i][METAFILE_FIELD__STATES_FILE_NAME] << endl;
    cout << space6 << setw(text_setw) << left << text3.c_str() << " : " << metafile_data_s[i][METAFILE_FIELD__ALPHABET_FILE_NAME] << endl;
    cout << space6 << setw(text_setw) << left << text4.c_str() << " : " << metafile_data_s[i][METAFILE_FIELD__TRANSITIONS_FILE_NAME] << endl;
    cout << space6 << setw(text_setw) << left << text5.c_str() << " : ";
    copy (metafile_data_s[i].begin() + METAFILE_FIELD__INPUT_WORDS_FILE1_NAME, metafile_data_s[i].end(), ostream_iterator<string> (cout, " "));
    cout << endl;
    cout << endl;
  }


} // show_metafile_content_S

// =========
void Run::show_alphabet_file_content  () const
{
size_t	text_setw = 0;
const string text1 ("Empty state");
const string text2 ("Internal symbols");
const string text3 ("Input symbols");

  text_setw = MAX_VALUE (text_setw, text1.size());
  text_setw = MAX_VALUE (text_setw, text2.size());
  text_setw = MAX_VALUE (text_setw, text3.size());


  //cout << space3 << string (setw10, '=') << " INFO selected from Alphabet file " << alphabet_file_name_ << " " << string (setw10, '=') << endl;

  cout << space6 << setw(text_setw) << left << text1.c_str() << " : "; 
  copy (alphabet_file_data_[ALPHABET_FILE_ROW__EMPTY_SYMBOLS].begin(), alphabet_file_data_[ALPHABET_FILE_ROW__EMPTY_SYMBOLS].end(), ostream_iterator<string> (cout, " "));
  cout << endl;

  cout << space6 << setw(text_setw) << left << text2.c_str() << " : "; 
  copy (alphabet_file_data_[ALPHABET_FILE_ROW__INTERNAL_SYMBOLS].begin(), alphabet_file_data_[ALPHABET_FILE_ROW__INTERNAL_SYMBOLS].end(), ostream_iterator<string> (cout, " "));
  cout << endl;

  cout << space6 << setw(text_setw) << left << text3.c_str() << " : "; 
  copy (alphabet_file_data_[ALPHABET_FILE_ROW__INPUT_SYMBOLS].begin(), alphabet_file_data_[ALPHABET_FILE_ROW__INPUT_SYMBOLS].end(), ostream_iterator<string> (cout, " "));
  cout << endl;

  cout << endl;


} // show_alphabet_file_content


// =========
void Run::show_descr_file_content  () const
{

  for (size_t i = 0; i < descr_file_data_.size(); i++)
  {
    cout << space6;
    copy (descr_file_data_[i].begin(), descr_file_data_[i].end(), ostream_iterator<string> (cout, " "));
    cout << endl;
  }

  cout << endl;
				 
} // show_descr_file_content



// =========
void Run::show_states_file_content  () const
{
size_t	text_setw = 0;
const string text1 ("Initial state");
const string text2 ("Halting state");
const string text3 ("Internal states");

  text_setw = MAX_VALUE (text_setw, text1.size());
  text_setw = MAX_VALUE (text_setw, text2.size());
  text_setw = MAX_VALUE (text_setw, text3.size());


  //cout << space3 << string (setw10, '=') << " INFO selected from States file " << states_file_name_ << " " << string (setw10, '=') << endl;

  cout << space6 << setw(text_setw) << left << text1.c_str() << " : "; 
  copy (states_file_data_[STATES_FILE_ROW__INITIAL_STATES].begin(), states_file_data_[STATES_FILE_ROW__INITIAL_STATES].end(), ostream_iterator<string> (cout, " "));
  cout << endl;

  cout << space6 << setw(text_setw) << left << text2.c_str() << " : "; 
  copy (states_file_data_[STATES_FILE_ROW__HALTING_STATES].begin(), states_file_data_[STATES_FILE_ROW__HALTING_STATES].end(), ostream_iterator<string> (cout, " "));
  cout << endl;

  cout << space6 << setw(text_setw) << left << text3.c_str() << " : "; 
  copy (states_file_data_[STATES_FILE_ROW__INTERNAL_STATES].begin(), states_file_data_[STATES_FILE_ROW__INTERNAL_STATES].end(), ostream_iterator<string> (cout, " "));
  cout << endl;

  cout << endl;
				 
} // show_states_file_content


// =========
void Run::show_transitions_file_content  () const
{
  for (size_t i = 0; i < transitions_file_data_.size(); i++)
  {
    //cout << space6 << "Row#" << setw(4) << right << i << " : ";
    cout << space6 << "Rule" << " :   ";
    copy (transitions_file_data_[i].begin(), transitions_file_data_[i].end(), ostream_iterator<string> (cout, " "));
    cout << endl;
  }

  cout << endl;

} // show_transitions_file_content

// =========
void Run::show_input_words_files_content  () const
{
  for (size_t i = 0; i < input_words_files_data_.size(); i++)
  {
    cout << space6 << "Input words --> Set#" << setw(3) << (i + 1) << endl;
    for (size_t j = 0; j < input_words_files_data_[i].size(); j++)
    {
      cout << space9 << "Tape#" << setw(3) << j << " : ";
      copy (input_words_files_data_[i][j].begin(), input_words_files_data_[i][j].end(), ostream_iterator<symbol_t> (cout, " "));
      cout << endl;
    }
    cout << endl;
  }


} // show_input_words_files_content


// =========
void Run::invoke_turing_machine_S (
		size_t		serial_number_i,
		size_t		number_of_tapes_i,
		const string&	descr_file_name_i,
		const string&	states_file_name_i,
		const string&	alphabet_file_name_i,
		const string&	transitions_file_name_i,
		const vector<string>&	input_words_files_names_i
		)
{
ostringstream oss1, oss2;

  cout	<< endl;
  cout	<< endl;
  cout	<< endl;
  cout	<< endl;
  
  oss1	<< space5 
	<< string (setw10, '#') 
	<< " Nondeterministic Turing Machine# " 
	<< serial_number_i 
	<< " : "; 
  
  oss2	<< " " 
	<< string (setw10, '#'); 

  cout << oss1.str() << "BEGIN" << oss2.str() << endl;


Run run_inst(
	serial_number_i,
	number_of_tapes_i,
	descr_file_name_i,
	states_file_name_i,
	alphabet_file_name_i,
	transitions_file_name_i,
	input_words_files_names_i
	);

  if (!run_inst.check_results_)
  {
    cout	<< space5 
    		<< "---> " 
       		<< "Invalid Data !!!" 
      		<< endl; 
  }
  cout	<< endl;
  cout	<< endl;

  cout << oss1.str() << " END " << oss2.str() << endl;

} // invoke_turing_machine_S


// =========
void Run::show_usage_S (const string& exe_name_i)
{
  cout << "\tUSAGE    : " 
       << exe_name_i 
       << " [ metafile-name : Default = " 
       << DEFAULT_METAFILE 
       << " ]"
       << endl;
 
  cout << "\t         : " 
       << exe_name_i 
       << " [ ";
  for (size_t i = 0; i < help_request_keys_s.size(); i++)
  {
    if (i) cout << " | ";
    cout << help_request_keys_s[i];
  }
  cout << " ]" << endl;

  cout << endl;
  cout << "\tEXAMPLES : " << exe_name_i << endl;
  cout << "\t         : " << exe_name_i << " metafile1" << endl;
  for (size_t i = 0; i < help_request_keys_s.size(); i++)
  {
    cout << "\t         : " << exe_name_i << " " << help_request_keys_s[i] << endl;
  }

}

// =========
void Run::show_help_S (const string& exe_name_i)
{
  show_usage_S(exe_name_i);

  cout << endl;
  show_metafile_structure_S ();
  cout << endl;
  show_descr_file_structure_S ();
  cout << endl;
  show_states_file_structure_S ();
  cout << endl;
  show_alphabet_file_structure_S ();
  cout << endl;
  show_transitions_file_structure_S ();
  cout << endl;
  show_input_words_file_structure_S ();
  cout << endl;

  show_sample_S();
}


// =========
void Run::show_sample_S ()
{
  cout << endl << endl;
  show_metafile_sample_S ();
  cout << endl;		    

  cout << endl;		    

const string prefix1 (9, ' ');	   
const string prefix2 (5, ' ');	   
const string l_border ("/// ---");	   
const string r_border ("--- \\\\\\");	   

const string text1 ("Sample of Nondeterministic Turing Machine Definition");
  cout << endl;
  cout << endl;
  cout << ""
       << prefix2 << l_border << " " << text1 << " : " << "BEGIN" << " " << r_border 
       << endl;

  cout << "" 
       << prefix1 << "A Nondeterministic Turing Machine example : Partition Problem"
       << endl
       << prefix1 << "* from \"The Design and Analysis of Computer Algorithms [1976]\""
       << endl
       << prefix1 << "* by A.V.Aho, J.E.Hopcroft, J.D.Ullman"
       << endl
       << prefix1 << "* --> See examples 10.1"
       << endl
       << prefix1 << "is used in samples below" 
       << endl;
  cout << endl;

  show_descr_file_sample_S ();
  cout << endl;
  show_states_file_sample_S ();
  cout << endl;
  show_alphabet_file_sample_S ();
  cout << endl;
  show_transitions_file_sample_S ();
  cout << endl;
  show_input_words_file_sample_S ();
  cout << endl;

  cout << endl;
  cout << ""
       << prefix2 << l_border << " " << text1 << " : " << "END" << " " << r_border 
       << endl;
  cout << endl;

}


// =========
void Run::run (uint argc, char** argv)
{
  cout << endl;
  cout << endl;
  cout << "\t---> YOUR COMMAND LINE : ";
  for (uint i = 0; i < argc; i++)
  {
    cout << argv[i] << " ";
  }
  cout << endl;
  cout << endl;

  assert (!help_request_keys_s.empty());

  if (argc >= 2)
  {
    if (find (help_request_keys_s.begin(), help_request_keys_s.end(), string(argv[1])) != help_request_keys_s.end())
    {
      show_help_S(argv[0]);
      return;
    }
  }

  if (argc == 1)
  {
    cout << endl;
    show_usage_S (argv[0]);
    cout << endl;
    cout << endl;
  }
  
  // ---------------------------
  if (!((argc < 2) ? read_metafile_S() : read_metafile_S (argv[1])))
  {
    cout << endl;
    FATAL_MSG	("Unable to select data from metafile");
    cout << endl;
    show_metafile_structure_S ();
    show_metafile_sample_S ();
    cout << endl;
    return ;
  }

  cout << endl;

size_t	number_of_tapes;

  for (size_t i = 0; i < metafile_data_s.size(); i++)
  {
     vector<string>	input_words_files_names;

     number_of_tapes = atoi (metafile_data_s[i][METAFILE_FIELD__NUMBER_OF_TAPES].c_str());

     for (size_t j = METAFILE_FIELD__INPUT_WORDS_FILE1_NAME; 
		 j < metafile_data_s[i].size(); 
		 j++
		 )
     {
       input_words_files_names.push_back (metafile_data_s[i][j]);
     }

     //copy (metafile_data_s[i].begin() + METAFILE_FIELD__INPUT_WORDS_FILE1_NAME, metafile_data_s[i].end(), input_words_files_names.begin());

     //assert (number_of_tapes != 0);
     invoke_turing_machine_S (
	(i + 1),
	number_of_tapes,
	metafile_data_s[i][METAFILE_FIELD__DESCR_FILE_NAME], 
	metafile_data_s[i][METAFILE_FIELD__STATES_FILE_NAME], 
	metafile_data_s[i][METAFILE_FIELD__ALPHABET_FILE_NAME], 
	metafile_data_s[i][METAFILE_FIELD__TRANSITIONS_FILE_NAME], 
	input_words_files_names
	);

  }

} // run