Bonescraper
asked on
Run time error in recursive function
Hi there.
I'm writing a program which reads in a boolean grid from a TXT file and finds groups of "true" values called blobs.
It includes a recursive function which finds the size of a blob at any grid point. A run time error occurs in the program and I believe it is due to a mistake in this function, called "getBlobSize".
Here is the source code:
#include <iostream>
#include <cstdlib>
#include <string>
#include <fstream>
#include <vector>
using namespace std;
class grid
{
// A class which manipulates a 2-dimensional grid of bool
public :
grid();
// default constructor - initialises variables
void readGrid(string filename);
// precondition : none
// postcondition :
// if a file called filename exists then the file of grid
// data has been read in
// otherwise the message "File does not exist" is
// displayed
void printGrid();
// displays the grid data with each row on a new line
int getMaxBlob();
// precondition : isEmpty is false and findAllBlobs has been invoked
// postcondition : returns the size of the maximum blob
bool isEmpty();
// returns true if grid data is empty (not successfully read in)
// and otherwise false
void findAllBlobs();
// precondition : isEmpty is false
// postcondition : the size of each blob has been determined
// and displayed (integers separated by tabs)
// the maximum blob size has been determined.
protected :
int getBlobSize(int curRow, int curCol);
// recursive function called by findAllBlobs()
// returns the size of the current blob
// (a blob starting at row CurRow and column curCol).
private :
vector < vector <bool> > v; // the 2-dimensional grid of data
int rows; // the number of rows in the grid data
int cols; // the number of columns in the grid data
int maxBlob; // the size of the maximum blob found
// (set by findAllBlobs())
};
int main()
{
grid mainGrid;
string file;
cout << "Enter filename" << endl;
cin >> file; // type data.txt
mainGrid.readGrid(file);
if (!mainGrid.isEmpty())
{
mainGrid.printGrid();
mainGrid.findAllBlobs();
cout << "The maximum blob size is " << mainGrid.getMaxBlob() << endl;
}
system("PAUSE");
return 0;
}
grid::grid()
{
rows = 0;
cols = 0;
maxBlob = 0;
}
void grid::readGrid(string filename)
{
char cell;
ifstream inFile;
inFile.open(filename.c_str ());
if (!inFile)
cout << "File does not exist" << endl;
else
{
inFile >> rows >> cols;
v.resize(rows, vector <bool> (cols, false));
for (int i=0; i < rows; i++)
{
for (int j=0; j < cols; j++)
{
inFile >> cell;
if (cell == '*')
{
v[i][j] = true;
}
else if (cell == '.')
{
v[i][j] = false;
}
}
}
}
inFile.close();
}
void grid::printGrid()
{
char cell;
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < cols; j++)
{
if (v[i][j] == true)
{
cell = '*';
}
else if (v[i][j] == false)
{
cell = '.';
}
cout << cell;
}
cout << endl;
}
}
int grid::getMaxBlob()
{
return maxBlob;
}
bool grid::isEmpty()
{
return v.empty();
}
void grid::findAllBlobs()
{
int curSize = 0;
for (int i=0; i < rows; i++)
{
for (int j=0; j < cols; j++)
{
curSize = getBlobSize(i, j);
if (curSize >= 2) cout << curSize << '\t';
if (curSize > maxBlob) maxBlob = curSize;
}
}
cout << endl;
}
int grid::getBlobSize(int curRow, int curCol)
{
// I believe the run time error is caused somewhere in this function
if (curRow > rows || curRow < 0 || curCol > cols || curCol < 0)
return 0;
else if (!v[curRow][curCol]) return 0;
else
{
v[curRow][curCol] = 0;
return 1 + getBlobSize(curRow - 1, curCol)
+ getBlobSize(curRow - 1, curCol + 1)
+ getBlobSize(curRow, curCol + 1)
+ getBlobSize(curRow + 1, curCol + 1)
+ getBlobSize(curRow + 1, curCol)
+ getBlobSize(curRow + 1, curCol - 1)
+ getBlobSize(curRow, curCol - 1)
+ getBlobSize(curRow - 1, curCol - 1);
}
}
Here is the contents of the data file called "data.txt":
6 8
......*.
.**..*.*
.***..*.
..*.....
....*...
...**...
I've checked the function and can't find the problem. Any thoughts about why this error occurs and possible solutions would be greatly appreciated.
Thankyou.
I'm writing a program which reads in a boolean grid from a TXT file and finds groups of "true" values called blobs.
It includes a recursive function which finds the size of a blob at any grid point. A run time error occurs in the program and I believe it is due to a mistake in this function, called "getBlobSize".
Here is the source code:
#include <iostream>
#include <cstdlib>
#include <string>
#include <fstream>
#include <vector>
using namespace std;
class grid
{
// A class which manipulates a 2-dimensional grid of bool
public :
grid();
// default constructor - initialises variables
void readGrid(string filename);
// precondition : none
// postcondition :
// if a file called filename exists then the file of grid
// data has been read in
// otherwise the message "File does not exist" is
// displayed
void printGrid();
// displays the grid data with each row on a new line
int getMaxBlob();
// precondition : isEmpty is false and findAllBlobs has been invoked
// postcondition : returns the size of the maximum blob
bool isEmpty();
// returns true if grid data is empty (not successfully read in)
// and otherwise false
void findAllBlobs();
// precondition : isEmpty is false
// postcondition : the size of each blob has been determined
// and displayed (integers separated by tabs)
// the maximum blob size has been determined.
protected :
int getBlobSize(int curRow, int curCol);
// recursive function called by findAllBlobs()
// returns the size of the current blob
// (a blob starting at row CurRow and column curCol).
private :
vector < vector <bool> > v; // the 2-dimensional grid of data
int rows; // the number of rows in the grid data
int cols; // the number of columns in the grid data
int maxBlob; // the size of the maximum blob found
// (set by findAllBlobs())
};
int main()
{
grid mainGrid;
string file;
cout << "Enter filename" << endl;
cin >> file; // type data.txt
mainGrid.readGrid(file);
if (!mainGrid.isEmpty())
{
mainGrid.printGrid();
mainGrid.findAllBlobs();
cout << "The maximum blob size is " << mainGrid.getMaxBlob() << endl;
}
system("PAUSE");
return 0;
}
grid::grid()
{
rows = 0;
cols = 0;
maxBlob = 0;
}
void grid::readGrid(string filename)
{
char cell;
ifstream inFile;
inFile.open(filename.c_str
if (!inFile)
cout << "File does not exist" << endl;
else
{
inFile >> rows >> cols;
v.resize(rows, vector <bool> (cols, false));
for (int i=0; i < rows; i++)
{
for (int j=0; j < cols; j++)
{
inFile >> cell;
if (cell == '*')
{
v[i][j] = true;
}
else if (cell == '.')
{
v[i][j] = false;
}
}
}
}
inFile.close();
}
void grid::printGrid()
{
char cell;
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < cols; j++)
{
if (v[i][j] == true)
{
cell = '*';
}
else if (v[i][j] == false)
{
cell = '.';
}
cout << cell;
}
cout << endl;
}
}
int grid::getMaxBlob()
{
return maxBlob;
}
bool grid::isEmpty()
{
return v.empty();
}
void grid::findAllBlobs()
{
int curSize = 0;
for (int i=0; i < rows; i++)
{
for (int j=0; j < cols; j++)
{
curSize = getBlobSize(i, j);
if (curSize >= 2) cout << curSize << '\t';
if (curSize > maxBlob) maxBlob = curSize;
}
}
cout << endl;
}
int grid::getBlobSize(int curRow, int curCol)
{
// I believe the run time error is caused somewhere in this function
if (curRow > rows || curRow < 0 || curCol > cols || curCol < 0)
return 0;
else if (!v[curRow][curCol]) return 0;
else
{
v[curRow][curCol] = 0;
return 1 + getBlobSize(curRow - 1, curCol)
+ getBlobSize(curRow - 1, curCol + 1)
+ getBlobSize(curRow, curCol + 1)
+ getBlobSize(curRow + 1, curCol + 1)
+ getBlobSize(curRow + 1, curCol)
+ getBlobSize(curRow + 1, curCol - 1)
+ getBlobSize(curRow, curCol - 1)
+ getBlobSize(curRow - 1, curCol - 1);
}
}
Here is the contents of the data file called "data.txt":
6 8
......*.
.**..*.*
.***..*.
..*.....
....*...
...**...
I've checked the function and can't find the problem. Any thoughts about why this error occurs and possible solutions would be greatly appreciated.
Thankyou.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.