tape.cpp

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

  if (actual_semi_tape_is_right ())
  {
    assert (get_actual_position () < right_semi_tape_.size());
    right_semi_tape_[get_actual_position ()] = symbol_i;
  }
  else
  {
    assert (actual_semi_tape_is_left ());
    assert (get_actual_position () < left_semi_tape_.size());
    left_semi_tape_[get_actual_position ()] = symbol_i;
  }
}


// =========
void Tape::set_max_symbol_size_ ()
{
vector<symbol_t>	tmp_full_alphabet = get_full_alphabet();
  assert (max_symbol_size_ == 0);
  for (size_t i = 0; i < tmp_full_alphabet.size(); i++)
  {
    max_symbol_size_ = MAX_VALUE (max_symbol_size_, tmp_full_alphabet[i].size()); 
  }
}


// =========
bool Tape::is_input_symbol (const symbol_t& symbol_i) const
{
  return (find (input_alphabet_.begin(), input_alphabet_.end(), symbol_i) != input_alphabet_.end());
}

// =========
bool Tape::is_internal_symbol (const symbol_t& symbol_i) const
{
  return (find (internal_alphabet_.begin(), internal_alphabet_.end(), symbol_i) != internal_alphabet_.end());
}

// =========
bool Tape::is_empty_symbol (const symbol_t& symbol_i) const
{
  return (find (empty_symbols_alphabet_.begin(), empty_symbols_alphabet_.end(), symbol_i) != empty_symbols_alphabet_.end());
}

// =========
bool Tape::is_valid_symbol (const symbol_t& symbol_i) const
{
  return (is_input_symbol (symbol_i) || is_internal_symbol (symbol_i) || is_empty_symbol (symbol_i));
}

// =========
bool Tape::is_valid_shift (shift_t shift_i) const
{
  return ((shift_i == LEFT_SHIFT) || (shift_i == NO_SHIFT) || (shift_i == RIGHT_SHIFT)); 
}



// =========
bool Tape::check_alphabet () const
{
bool	ret_bool_value = true;

symbol_t phisical_empty_symbol = string();
vector<symbol_t>::const_iterator iter;

  assert (!empty_symbols_alphabet_.empty());
  assert (!input_alphabet_.empty());
  // assert (!internal_alphabet_.empty()); ---> internal_alphabet_ may be empty

  // ---------
  // ---------
  iter = find (empty_symbols_alphabet_.begin(), empty_symbols_alphabet_.end(), HEAD_START_POSITION_POINTER_REDERVED_SYMBOL); 
  if (iter != empty_symbols_alphabet_.end())
  {
    ret_bool_value = false;
    FATAL_MSG	("Sorry. Empty symbols alphabet -> symbol#"
		<< distance (empty_symbols_alphabet_.begin(), iter)
		<< " is reserved symbol (for machine head) : <"
		<< *iter
		<< ">"
		);
  }


  iter = find (input_alphabet_.begin(), input_alphabet_.end(), HEAD_START_POSITION_POINTER_REDERVED_SYMBOL); 
  if (iter != input_alphabet_.end())
  {
    ret_bool_value = false;
    FATAL_MSG	("Sorry. Input alphabet -> symbol#"
		<< distance (input_alphabet_.begin(), iter)
		<< " is reserved symbol (for machine head) : <"
		<< *iter
		<< ">"
		);
  }


  iter = find (internal_alphabet_.begin(), internal_alphabet_.end(), HEAD_START_POSITION_POINTER_REDERVED_SYMBOL); 
  if (iter != internal_alphabet_.end())
  {
    ret_bool_value = false;
    FATAL_MSG	("Sorry. Internal alphabet -> symbol#"
		<< distance (internal_alphabet_.begin(), iter)
		<< " is reserved symbol (for machine head) : <"
		<< *iter
		<< ">"
		);
  }


  // ---------
  // ---------
  // ---------
  iter = find (empty_symbols_alphabet_.begin(), empty_symbols_alphabet_.end(), phisical_empty_symbol); 
  if (iter != empty_symbols_alphabet_.end())
  {
    ret_bool_value = false;
    FATAL_MSG	("Empty symbols alphabet -> symbol#"
		<< distance (empty_symbols_alphabet_.begin(), iter)
		<< " is phisically empty : <"
		<< *iter
		<< ">"
		);
  }

  iter = find (input_alphabet_.begin(), input_alphabet_.end(), phisical_empty_symbol); 
  if (iter != input_alphabet_.end())
  {
    ret_bool_value = false;
    FATAL_MSG	("Input alphabet -> symbol#"
		<< distance (input_alphabet_.begin(), iter)
		<< " is phisically empty : <"
		<< *iter
		<< ">"
		);
  }


  iter = find (internal_alphabet_.begin(), internal_alphabet_.end(), phisical_empty_symbol); 
  if (iter != internal_alphabet_.end())
  {
    ret_bool_value = false;
    FATAL_MSG	("Internal alphabet -> symbol#"
		<< distance (internal_alphabet_.begin(), iter)
		<< " is phisically empty : <"
		<< *iter
		<< ">"
		);
  }

  // ------
vector<symbol_t> tmp_full_alphabet = get_full_alphabet();
vector<symbol_t>::iterator	iter2;
  for (iter2 = tmp_full_alphabet.begin(); iter2 != tmp_full_alphabet.end(); iter2++)
  {
    assert (count (iter2, tmp_full_alphabet.end(), *iter2));
    if (count (iter2, tmp_full_alphabet.end(), *iter2) > 1)
    {
      ret_bool_value = false;
      FATAL_MSG	("Alphabets -> symbol "
		<< "<"
		<< (*iter2)
	 	<< ">"
		<< " occurs more than once"
		);
    }
  }
  
  return ret_bool_value;

}

// =========
void Tape::show_alphabet (const string& msg_i) const
{
  IF_NOT_EMPTY (msg_i, 3, '=');

string text_empty_symbols_alphabet ("Empty symbols alphabet");
string text_input_alphabet ("Input alphabet");
string text_internal_alphabet ("Internal alphabet");
size_t text_max_size = 0;

  text_max_size	= MAX_VALUE(text_max_size, text_empty_symbols_alphabet.size());
  text_max_size	= MAX_VALUE(text_max_size, text_input_alphabet.size());
  text_max_size	= MAX_VALUE(text_max_size, text_internal_alphabet.size());


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

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

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


}


// =========
void Tape::show_tape (const string& msg_i) const
{

  IF_NOT_EMPTY (msg_i, 3, '=');

  show_left_tape (msg_i);
  cout << SEMI_TAPES_DELIM;
  show_right_tape (msg_i);
  cout << endl;


}


// =========
void Tape::show_left_tape (const string& msg_i) const
{

  IF_NOT_EMPTY (msg_i, 3, '=');

string	left_delim;
string	right_delim;
  for (ulong k = left_semi_tape_.size(); k > 0; k--)
  {
    const ulong i = k - 1;
    if ((logical_position_ < 0) && (get_actual_position () == i))
    {
      left_delim  = LEFT_SCAN_DELIM;
      right_delim = RIGHT_SCAN_DELIM;
    }
    else
    {
      left_delim  = LEFT_USUAL_DELIM;
      right_delim = RIGHT_USUAL_DELIM;
    }

    cout << left_delim 
         << setw (max_symbol_size_) 
         << left_semi_tape_[i].c_str() 
         << right_delim 
         << " ";    
  }

}



// =========
void Tape::show_right_tape (const string& msg_i) const
{

  IF_NOT_EMPTY (msg_i, 3, '=');

string	left_delim;
string	right_delim;
  for (ulong i = 0; i < right_semi_tape_.size(); i++)
  {
    if ((logical_position_ >= 0) && (get_actual_position () == i))
    {
      left_delim  = LEFT_SCAN_DELIM;
      right_delim = RIGHT_SCAN_DELIM;
    }
    else
    {
      left_delim  = LEFT_USUAL_DELIM;
      right_delim = RIGHT_USUAL_DELIM;
    }

    cout << left_delim 
         << setw (max_symbol_size_) 
         << right_semi_tape_[i].c_str() 
         << right_delim 
         << " ";
  }

}



// =========
void Tape::visual_cleaning ()
{

  if (actual_semi_tape_is_right ())  visual_cleaning_right_semi_tape ();
  if (actual_semi_tape_is_left ())   visual_cleaning_left_semi_tape ();

}


// =========
void Tape::visual_cleaning_right_semi_tape ()
{

  assert (actual_semi_tape_is_right ());

  if (find (
		empty_symbols_alphabet_.begin(), 
		empty_symbols_alphabet_.end(), 
		right_semi_tape_.back()
		) 
		== empty_symbols_alphabet_.end())
  {
    return;
  }

  if (get_actual_position() == (right_semi_tape_.size() - 1)) return;

  assert (get_actual_position() < (right_semi_tape_.size() - 1));

  right_semi_tape_.erase (right_semi_tape_.end() - 1);

}



// =========
void Tape::visual_cleaning_left_semi_tape ()
{

  assert (actual_semi_tape_is_left ());

  if (find (
		empty_symbols_alphabet_.begin(), 
		empty_symbols_alphabet_.end(), 
		left_semi_tape_.back()
		) 
		== empty_symbols_alphabet_.end())
  {
    return;
  }

  if (get_actual_position() == (left_semi_tape_.size() - 1)) return;

  assert (get_actual_position() < (left_semi_tape_.size() - 1));

  left_semi_tape_.erase (left_semi_tape_.end() - 1);

}