Hi All,

I've already had some help on this forum, I'm so glad I found it -- I'm working on an assignment and I'm just struggling with a concept as I'm quite a newcomer with C++.

We are being taught to use doubly-linked lists rather than arrays (therefore the method to traverse between lists to access data is rather inefficient as it involves starting from the beginning each time) - and I'd like some suggestions on how to get started, as I can't think of the right way to do it... maybe to utilise a "row number" for the horizontal lists... I'm not sure.

Anyway, suggestions are very welcome, and I will post my code (it's all in one cpp file). Essentially I need to be able to traverse the list up and down so that I can see all the spaces to the immediate left, top and bottom of a position in one of the rows.

The function "calculate_metrics" alllll the way at the bottom is what I'm up to - I'm so close to getting it all functional!

Code:
#include <iostream>
#include <fstream>
#include <list>
#include <ctype.h>
#include <cstdlib>

using namespace std;

class row 
{
   private:
   
   list<char> row_chars;
   int row_number;
   
   public:
   
   row(int number) 
   {
      row_number = number; 
   }
   
   void store_chars(char ch);
   void new_row();
   void print_row();
   bool is_match(char data);
   void clear_row();
   bool is_char_valid();
   bool is_outside_maze(char findData);
   bool check_counts(int hash, int s, int f);
   int get_row_number();
};

void load_maze(list<row> &maze_rows, row &row_chars, const string &filein);
void print_maze(list<row> &maze_rows);
bool find_char(const char &findData, 
   list<row>::iterator &itr, list<row> &maze_rows);
int count_char(const char &findData, 
   list<row>::iterator &itr, list<row> &maze_rows);
bool is_maze_valid(list<row>::iterator &itr, list<row> &maze_rows);
bool is_outside(const char &findData, 
   list<row>::iterator &itr, list<row> &maze_rows);
int test_maze(list<row> &maze_rows);
void calculate_metrics(list<row> &maze_rows);

int main (int argc, char *argv[]) 
{
   string filein;
   list<row> maze_rows;
   
   row row_chars(1);
   
   //Make sure a maze file was provided
   
   if (argc != 2) 
   {
      cout << "Must supply 1 argument to this program\n";
      return 0; 
   }
  
   filein = argv[1];
  
   //Loading the file into lists...
  
   load_maze(maze_rows, row_chars, filein);
  
   //Running the tests on the lists...
  
   if(test_maze(maze_rows) == 0)
   {
      cout << "Unable to load maze " << filein << " \n";
      exit(0);
   }
    
   print_maze(maze_rows);
  
   //Calculate and print the maze metrics...
  
   calculate_metrics(maze_rows);
  
   return 0; 
}

void row::store_chars(char ch) 
{
   row_chars.push_back(ch); 
}
    
void row::new_row() 
{
   row_number++; 
}
    
void row::print_row()
{
   for(list<char>::iterator list_iter = row_chars.begin(); 
      list_iter != row_chars.end(); list_iter++)
      cout << *list_iter; 
}
    
bool row::is_match(char data) 
{
   
   //Return false if it cannot find the provided char in the row
   
   for(list<char>::iterator list_iter = row_chars.begin(); 
      list_iter != row_chars.end(); list_iter++) 
   {
      if(*list_iter == data)
         return true; 
   }
   return false; 
}
    
void row::clear_row() 
{
   row_chars.clear(); 
}
    
bool row::is_char_valid() 
{
   //Return true if all the chars match up with one of the specified characters
   for(list<char>::iterator list_iter = row_chars.begin(); 
      list_iter != row_chars.end(); list_iter++) 
   {      
      if(*list_iter == '#' || *list_iter == 's' || *list_iter == 'f' 
         || *list_iter == ' ' || *list_iter == '\n')
         continue;
      else
         return false; 
   }
   return true; 
}
    
bool row::is_outside_maze(char findData) 
{
   //Return true if the char is outside the maze
   int hash_count, s_count, f_count;
   
   hash_count = s_count = f_count = 0;
   
   for(list<char>::iterator list_iter = row_chars.begin(); 
      list_iter != row_chars.end(); list_iter++) 
   {      
      if(*list_iter == '#')
         hash_count++;
      if(*list_iter == 's')
         s_count++;
      if(*list_iter == 'f')
         f_count++;
      if(check_counts(hash_count, s_count, f_count))
         continue;
      else
         return true;
   }
   return false;
}

bool row::check_counts(int hash, int s, int f) 
{
   if((s > 0 || f > 0) && hash == 0)
      return false;
   else
      return true;
}

int row::get_row_number()
{
   return row_number;
}

void load_maze(list<row> &maze_rows, row &row_chars, const string &filein) 
{
   ifstream fin;
   char ch;
  
   //open stream to filein
   fin.open(filein.c_str());
   if (!fin) 
   {
      cerr << "Unable to load maze " << filein << " \n";
      exit(0); 
   }
  
   while (!fin.eof()) 
   {
      fin.get(ch);
      row_chars.store_chars(ch);
      if(ch == '\n') 
      {
         maze_rows.push_back(row_chars);
         row_chars.clear_row();
         row_chars.new_row(); 
      }
   }
  
   fin.close(); 
}

void print_maze(list<row> &maze_rows) 
{  
   for(list<row>::iterator list_iter = maze_rows.begin(); 
      list_iter != maze_rows.end(); list_iter++)
      list_iter->print_row(); 
}
     
bool find_char(const char &findData, 
   list<row>::iterator &itr, list<row> &maze_rows) 
{
   // Check if char is found in list

   for (itr = maze_rows.begin(); itr != maze_rows.end(); itr++) 
   {
      if (itr->is_match(findData)) 
         return true; 
   }
   return false; 
}

int count_char(const char &findData, 
   list<row>::iterator &itr, list<row> &maze_rows) 
{
   // Check how many times the char occurs in the row

   int data_count = 0;
   
   for (itr = maze_rows.begin(); itr != maze_rows.end(); itr++)
   {
      if (itr->is_match(findData))
         data_count++; 
   }
   return data_count; 
}

bool is_maze_valid(list<row>::iterator &itr, list<row> &maze_rows)
{
   // Testing if chars in the maze are valid

   for (itr = maze_rows.begin(); itr != maze_rows.end(); itr++) 
   {
      if (itr->is_char_valid())
         continue;
      else 
      {
         cout << "invalid character in maze\n";
         return false; 
      }
   }
   return true; 
}

bool is_outside(const char &findData, 
   list<row>::iterator &itr, list<row> &maze_rows) 
{
   //Testing if char is placed inside or outside of the maze
   
   for (itr = maze_rows.begin(); itr != maze_rows.end(); itr++) 
   {
      if (itr->is_outside_maze(findData))
         return true;
   }
   return false; 
}

int test_maze(list<row> &maze_rows) 
{   
   
   list<row>::iterator list_iter;
   
   //Testing to see if 's' is contained in the maze...
   if(!find_char('s', list_iter, maze_rows)) 
   {
      cout << "Error - no start found in maze";
      return(0);
   }
   
   //Testing to see if 'f' is contained in the maze...
   if(!find_char('f', list_iter, maze_rows)) 
   {
      cout << "Error - no finish found in maze";
      return(0);
   }
   
   //Testing to see if maze contains valid characters...
   if(!is_maze_valid(list_iter, maze_rows)) 
   {
      return(0);
   }
   
   //Testing to see if there is only one 's' and 'f' 
   // contained in the maze...
   if(count_char('s', list_iter, maze_rows) != 1)
   {
      cout << "Error - multiple start found in maze\n";
      return(0);
   }
   if (count_char('f', list_iter, maze_rows) != 1)
   {
      cout << "Error - multiple finish found in maze\n";
      return(0);
   }
         
   //Testing to see if 's' or 'f' is declared 
   // outside of the maze...
   if(is_outside('s', list_iter, maze_rows))
   {
      cout << "Error - start declared outside of maze\n";
      return(0); 
   }
   if(is_outside('f', list_iter, maze_rows))
   {
      cout << "Error - finish declared outside of maze\n";
      return(0); 
   }
   return(1);            
}

void calculate_metrics(list<row> &maze_rows) 
{
   /*Calculate the total number of branches in the maze*/
   /*Calculate the total number of dead ends in the maze*/
   int branches, dead_ends;
   
   branches = dead_ends = 0;
   
   cout << "\nNumber of branches in maze is " << branches << "\n";
   cout << "Number of dead-ends in maze is " << dead_ends << "\n"; 
}