Can't print object's attributes in a binary tree - "no member named 'toString'"

Hi All,

This was in another thread but it's a completely new problem so I thought I'd create a new thread...

I am writing a program for an assignment which uses binary trees to store a text file (a kind of maze):
1) Create a maze object which contains a binary tree of rows
2) Create a row object which contains a binary tree of maze points and a y value
3) Create a maze point object which contains a char attribute and an x value

This way, I should be able to traverse the file as if it was a 2D-Array, I think. I then have to run tests on it and print it out. But I am getting an error before I can even get as far as to run tests - i.e, when I try to just print the maze:

error:

Code:

binnode.h: In member function 'void binNode<dataType>::print() const [with dataType = mazePoint]':
bintree.h:129:   instantiated from 'void bintree<dataType>::print() const [with dataType = mazePoint]'
assign3.cpp:126:   instantiated from here
binnode.h:200: error: 'const class mazePoint' has no member named 'toString'

Here's my latest cpp code: I tried including string.h, but that didn't work. I gave the class a toString function, but it wasn't happy with that either; there were more errors.
Note: I am not allowed to modify the header files.

Code:

#include <iostream>
#include <fstream>
#include <ctype.h>
#include <cstdlib>
#include <string.h>

#include "bintree.h"
#include "binnode.h"

using namespace std;

class mazePoint
{
   private:
   
   int x;
   char point_type;
      
   public:   
   
   void set_maze_point(char point, int i);
   void print();
   //const string toString();
   bool operator!=(const mazePoint &other) const;
   bool operator==(const mazePoint &other) const;
   bool operator<(const mazePoint &other) const;
};

class mazeRow
{
   private:
   
   bintree<mazePoint> points;
   int y;
      
   public:   
   
   void set_maze_row(int row_number);   
   void store_points(char ch, int i);
   int get_size();
   void new_row();
   void print();
   void clear();
   bool operator!=(const mazeRow &other) const;
   bool operator==(const mazeRow &other) const;
   bool operator<(const mazeRow &other) const;
};

void load_maze(bintree<mazeRow> &maze, string arg);
void print_maze(bintree<mazeRow> &maze);

int main (int argc, char *argv[]) 
{
   bintree<mazeRow> maze;
   
   //Make sure a maze file was provided   
   if (argc != 2) 
   {
      cout << "Must supply 1 argument to this program\n";
      return 0; 
   }     
   
   //Load and test the maze  
   load_maze(maze, argv[1]);
    
   //If load successful, calculate and print solution  
//   find_solution(maze);
//   print_solution(maze);
   
   //Cleanup
//   clear_rows(maze_rows);

   return 0; 
}

void mazeRow::set_maze_row(int row_number)
{
   y = row_number;
}

int mazeRow::get_size()
{
   return points.size();
}

void mazeRow::store_points(char ch, int i)
{
   mazePoint point;
   point.set_maze_point(ch, i);
   points.insert(point);
}

void mazeRow::new_row()
{
   y++;
}

void mazePoint::set_maze_point(char point, int i)
{
   point_type = point;
   x=i;
}

bool mazeRow::operator==(const mazeRow &other) const
{
   return(this->y == other.y);
}

bool mazePoint::operator==(const mazePoint &other) const 
{
   return(this->x == other.x);
}

bool mazePoint::operator<(const mazePoint &other) const
{
   return(this->x < other.x);
}

bool mazeRow::operator<(const mazeRow &other) const
{
   return(this->y < other.y);
}

void mazeRow::print()
{
   points.print();
}

void mazePoint::print()
{
   cout << point_type;
}

/*const mazePoint::string toString()
{
   stringstream ss;
   string s;
   ss << point_type;
   ss >> s;
}*/

void load_maze(bintree<mazeRow> &maze, string arg) 
{
   string filein;
   
   mazeRow row;
   row.set_maze_row(1);
   
   ifstream fin;
   char ch;
   int i = 0;
  
   filein = arg;
  
   //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);
      i++;
      row.store_points(ch, i);
      if(ch == '\n') 
      {         
         maze.insert(row);
         row.new_row();
      }
   }
  
   fin.close();      
         
   //Print the maze (temp test)
   print_maze(maze);
   
   row.print();
   
   //Run tests on the maze to make sure it is valid  
//   if(test_maze(maze) == 0)
//   {
//      cout << "Unable to load maze " << filein << " \n";
//      exit(0);
//   }
}

void print_maze(bintree<mazeRow> &maze)
{
}

bintree.h:

Code:

#ifndef BINTREE_H_
#define BINTREE_H_

#include <stdexcept>
#include <math.h>

#include "binnode.h"

/********************************************************\
   template class for a binary tree
\********************************************************/
      

template <typename dataType> class bintree
{  
   private:
      binNode<dataType> *root;
      int numItems;
      
   public:
      /*******************************************************\
         constructors & destructors
      \*******************************************************/
      
      // constructor
      bintree() : root(NULL), numItems(0) {}
      
      // destructor
      ~bintree() {
         if (root != NULL) delete root;
      }
      
      /*******************************************************\
         misc functions
      \*******************************************************/
      
      bool empty() const {
         return (numItems == NULL);
      }
      
      int size() const {
         return numItems;
      }
      
      int numNodes() const {
         if (root == NULL) {
            return 0;
         } else {
            return root->numNodes();
         }
      }
      
      int maxTreeDepth() const {
         if (root == NULL) {
            return 0;
         } else {
            return root->maxTreeDepth();
         }
      }
      
      int numLeafNodes() const {
         if (root == NULL) {
            return 0;
         } else {
            return root->numLeafNodes();
         }
      }
      
      double balance() const {
         // Returns a measure of how balanced a tree is.
         // A value of 1 is a prefectly balanced tree.
         // The closer to 0 the value is the more unbalanced
         // the tree.
         // A value < 0.5 indicates a tree that is seriously unbalanced
         
         if (numItems == 0) return 1.0;
         else return root->balance();
      }
      
      void rebalance() {
         // Rebalance tree using the AVL algorithm
         // While this does not guarantee a perfectly balanced tree
         // it does make it mostly balanced by guranteeing that the diference
         // in depth between every right and left subtree is at most 1
         
         if (root != NULL) {
            while (root->rebalance(root));
         }
      }
      
      /*******************************************************\
         insertion and erasure functions
      \*******************************************************/
      
      void insert(const dataType& newData) {
         if (root == NULL) {
            root = new binNode<dataType>(newData);
         } else {
            root->insert(newData);
         }
         numItems++;
      }
      
      void erase(const dataType& delData) {
      
         if (root == NULL) {
            throw std::invalid_argument("data does not exist in tree to erase");
         }
         
         root->erase(&root, delData);
         
         numItems--;
      }
      
      dataType* find(const dataType &findData) const {
         // this function looks for findData in the tree.
	 // If it finds the data it will return the address of the data in the tree
	 // otherwise it will return NULL
         if (root == NULL) return NULL;
         else return root->find(findData);
      }
	  
      /*******************************************************\
         print function for assignment. 
         assumes dataType has print() function 
      \*******************************************************/
	  
      void print() const {
          if (root != NULL) root->print();
      }
};

#endif

binnode.h:

Code:

#ifndef BINNODE_H
#define BINNODE_H

#include <math.h>
#include <iostream> 

/********************************************************\
   template node class for binary tree
\********************************************************/

template <typename dataType> class binNode 
{
   private:
      dataType nodeData;
      binNode<dataType> *left, *right;
      
      void deleteNode(binNode<dataType> **root) {
         if (left == NULL && right == NULL) {
            // leaf node
            *root = NULL;
         } else if (left == NULL) {
            // right branch but no left branch
            *root = right;
         } else if (right == NULL) {
            // left branch but no right branch
            *root = left;
         } else {
            // has left and right branch
            binNode<dataType> *temp = right;
            // find left most node of right branch
            while (temp->left != NULL) temp = temp->left;
            // attach left branch to left side of right branch
            temp->left = left;
            // make root point to right branch
            *root = right;
         }
         left = NULL;
         right = NULL;
         delete (this); 
      }
           
   public:
      // constructors
      binNode() : left(NULL), right(NULL) {
      }
   
      binNode(const dataType& dataItem) :
         nodeData(dataItem), left(NULL), right(NULL) {
      }
   
      // destructor
      ~binNode() {
         if (left != NULL) delete left;
         if (right != NULL) delete right;
      }
   
      void insert(const dataType& dataItem) {
         if (nodeData == dataItem) {
            throw std::invalid_argument("dataItem already in tree");
         }
      
         if (dataItem < nodeData) {
            if (left == NULL) {
               left = new binNode(dataItem);
            } else {
               left->insert(dataItem);
            }
         } else {
            if (right == NULL) {
               right = new binNode(dataItem);
            } else {
               right->insert(dataItem);
            }
         }
      }
      
      void erase(binNode<dataType> **root, const dataType &delData) {
         if (delData == nodeData) {
            deleteNode(root);
         } else {
            if (delData < nodeData) {
               if (left == NULL) {
                  throw std::invalid_argument("delItem not in tree");
               } else {
                  left->erase(&left, delData);
               }
            } else {
               if (right == NULL) {
                  throw std::invalid_argument("delItem not in tree");
               } else {
                  right->erase(&right, delData);
               }
            }
         }
      }
      
      dataType* find(const dataType &findData) {
         if (findData == nodeData) {
            return &nodeData;
         } else if (findData < nodeData) {
            if (left == NULL) return NULL;
            else return left->find(findData);
         } else {
            if (right == NULL) return NULL;
            else return right->find(findData);
         }
      }


      
      bool rebalance(binNode<dataType>* &root) {
         // rebalance the subtrees hanging from this node
         int rnodes=0, lnodes=0, nodes, dif;
         bool rotate = false;
            
         if (left != NULL) {
            if (left->rebalance(left)) rotate = true;
            lnodes = left->numNodes();
         }
         if (right != NULL) {
            if (right->rebalance(right)) rotate = true;
            rnodes = right->numNodes();
         }
         
         if (rnodes > lnodes) {
            dif = rnodes - lnodes;
            // work out node difference if we rotate anticlockwise
            rnodes = 0;
            if (right != NULL && right->right != NULL) rnodes = right->right->numNodes(); 
            nodes = 0;
            if (right != NULL && right->left != NULL) nodes = right->left->numNodes();
            lnodes = 1 + lnodes + nodes;
            if (abs(lnodes - rnodes) < dif) {
               // rotate anticlockwise
               root = right;
               right = right->left;
               root->left = this;
               rotate = true;
            }
         }
         else if (lnodes > rnodes) {
            // work out node difference if we rotate clockwise
            dif = lnodes - rnodes;
            lnodes = 0;
            if (left != NULL && left->left != NULL) lnodes = left->left->numNodes();
            nodes = 0;
            if (left != NULL && left->right != NULL) nodes = left->right->numNodes();
            rnodes = 1 + rnodes + nodes;
            if (abs(lnodes - rnodes) < dif) {
               // rotate clockwise
               root = left;
               left = left->right;
               root->right = this;
               rotate = true;
            }
         }
         return rotate;
      }

      double balance() const {
         int lheight = 0, rheight = 0, dif;
         double bal = 1.0;

         if (left != NULL) {
            lheight = left->maxTreeDepth();
            bal *= sqrt(left->balance());
         }
         if (right != NULL) {
            rheight = right->maxTreeDepth();
            bal *= sqrt(right->balance());
         }

         dif = abs(lheight - rheight);
         if (dif <= 1) return bal;
         else return bal / log(dif);
      }
      
      // tree statistic functions
      int maxTreeDepth() const {
         int rdepth = 0, ldepth = 0;
         
         if (left != NULL) ldepth = left->maxTreeDepth();
         if (right != NULL) rdepth = right->maxTreeDepth();
         
         if (ldepth > rdepth) return 1 + ldepth;
         else return 1 + rdepth;
      }
      
      int numNodes() const {
         int size = 1;
         
         if (left != NULL) size += left->numNodes();
         if (right != NULL) size += right->numNodes();
         
         return size;
      }
	  
	  void print() const {
	     if (left != NULL) left->print();
		 std::cout << nodeData.toString() << "\n";
		 if (right != NULL) right->print();
      }
      
      int numLeafNodes() const {
         if (left == NULL && right == NULL) return 1;
         
         int numLeaf = 0;
         if (left != NULL) numLeaf += left->numLeafNodes();
         if (right != NULL) numLeaf += right->numLeafNodes();
         return numLeaf;
      }
      
      // overloaded dereference operator
      const dataType& operator * () const {
         return nodeData;
      }
};

#endif

Well guess what the problem is.
There IS no member named toString!

You already figured that out and made an attempt to solve it, but apparently you took a step backwards again just because there were more bugs than just the one.

So, re-add toString and work from there. One hint though: make the function const. Not the return value, but the entire function!

If you look at my cpp code you'll see I commented out a prototype for toString, and the function is included just before the last function (load_maze). So, I uncommented them and am receiving this compilation error:

Code:

assign3.cpp:134: error: 'string' in class 'mazePoint' does not name a type

I've been pulling my hair out here -> this is the first line of the toString function:
Also note I added the word const to the end of the prototype and function.

Code:

const mazePoint::string toString() const

try including "<string>" and "<sstream>"

I'm afraid I get the exact same error EVOEx, I can't for the life of me figure out why..

If toString was an unknown member though wouldn't the compiler have a problem with it just being mentioned in the binnode.h header file (in the print() function) regardless of whether I was going to call the print function in my cpp file? What I'm trying to say is, the compiler accepts toString() in the header file, but when I try to utilise it in the cpp file it has a problem. toString() is not defined in the header file though.

Does this help shed some light on the issue? It just feels like I'm meant to leave toString() alone, and that it is some other nagging problem which is causing this issue... like I need to add something to the mazeRow and mazePoint classes for the compiler to understand what it's actually printing when it receives the command print with the binary trees.

When you're implementing the toString() function, take the "mazePoint::" prefix off. There is no type named mazePoint::string declared or defined in your code.

The declaration within class mazePoint would be better as

Code:

    std::string toString() const;

rather than having the const in front where it is, more or less meaningless. The implementation of the function needs to match the declaration too.

I don't like this:

Code:

void load_maze(bintree<mazeRow> &maze, string arg) 
{
   string filein;
   
   mazeRow row;
   row.set_maze_row(1);
   
   ifstream fin;
   char ch;
   int i = 0;
  
   filein = arg;
  
   //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);
      i++;
      row.store_points(ch, i);
      if(ch == '\n') 
      {         
         maze.insert(row);
         row.new_row();
      }
   }
  
   fin.close();      
         
   //Print the maze (temp test)
   print_maze(maze);
   
   row.print();
   
   //Run tests on the maze to make sure it is valid  
//   if(test_maze(maze) == 0)
//   {
//      cout << "Unable to load maze " << filein << " \n";
//      exit(0);
//   }
}

...though it doesn't have anything to do with your question here. Don't rely on testing eof to control your loops.

grumpy, you have totally just solved that part of my problem. It just had to be one of those silly errors, I'd put mazePoint:: too early! It was meant to say:

Code:

string mazePoint::toString() const;

Now it compiles AND prints. I am eternally grateful. Many an hour do I spend being held up with forgetful nuisances like this one :P

hk_, are you implying it would be an issue if I had an overly large file or is eof a troublesome function? Can you please explain why testing for the end of the file would be a bad idea?

Thankyou everyone for being so helpful.
I now have one more question: the binnode.h header file defines the print() function in a way that it prints a new line after each node - however, the way the program works, is that the new line character is actually a node - so it will start new lines when there is a new line in the file. This printing of a new line after each character seems to me to be pointless; I don't quite understand why it's included in the header file. So instead of getting the file printed on screen as-is, I just get one-character lines.

I tried to make my own print function to override the header file's one as you can see above for the mazePoint class but evidently it ignores this and continues with the binnode.h version.

I was thinking that I could try to adapt my mazeRow class' print() function to take only the first char of binnode.h's print() function and I was hoping I could get a bit of feedback on this idea before wrestling with the practicality of doing it? Greatly appreciated in advance folks!

Originally Posted by abrownin

hk_, are you implying it would be an issue if I had an overly large file or is eof a troublesome function? Can you please explain why testing for the end of the file would be a bad idea?

Testing for eof sounds like a great idea. The catch is, that's not really what the eof function does. If you click on the link that was in hk's post, then you'll see what it actually does.

Originally Posted by abrownin

I tried to make my own print function to override the header file's one as you can see above for the mazePoint class but evidently it ignores this and continues with the binnode.h version.

mazePoint and binnode<mazePoint> are different objects, and defining print for one of them will be irrelevant when dealing with the other. If you don't want what's there, you can do a template specialization, i.e., define the function

Code:

template <>
void binnode<mazePoint>::print()

(note: untested, but I'm pretty sure that's the right syntax). Whether your instructor will like you for it, I can't say, but it's the best way to get around the "this is a great idea except in the case when" problem.

Originally Posted by abrownin

hk_, are you implying it would be an issue if I had an overly large file or is eof a troublesome function? Can you please explain why testing for the end of the file would be a bad idea?

The eof function will only return true after an attempt to read past the end of the file has occurred. Up to the point where you read the last character eof will still return false. This is a problem since you'll then test eof at the beginning of the while loop and it will return false seemingly indicating that you've still got more to read even though you are at the physical end of the file. Since the test fails and the overall condition in the while loop is to keep going while the eof test fails you'll enter the loop one last time even when there is nothing more to be read from the file. The fin.get will execute and fail which likely means that ch retains its previous value and you will be operating on bad data and since you're already in the body of loop it's too late to do anything in your current version of that code. The net effect of all this is that your loop executes one time too many processing invalid data.

The solution is usually to test the return value of the read operation instead of eof. That is, instead of:

Code:

while( !fin.eof() )
{
    fin.get(ch);
    ...

...you would instead have:

Code:

while( fin.get(ch) )
{
    ...

In this case if the read op (get) fails (there's nothing left to get or there is some other error in the file stream) the loop never gets executed. You could also put in a second eof test immediately after the read (get) and break out of the loop prematurely.

Thanks hk_, I'll take your advice and implement it, it makes a lot of sense and I agree is much safer.

tabstop, regarding the following code:

Code:

template <>
void binnode<mazePoint>::print()

Is this something I would put as-is into my cpp file?

What I mean is the following:

Code:

previous functions...

template <>
void binnode<mazePoint>::print()
{
   cout << point_type;
}

... more functions

And then when I call row.print(), it will call points.print() for each point in the row.

I'm at work so I can't test it until much later..

That's right -- and since points is a binnode<mazePoint>, calling points.print() will call the print function as defined for binnode<mazePoint>. Right now it's filling in the template for binnode<T>, but if you give a specific specialization it will use that one instead (provided it appears after the template version in your code).

Thanks tabstop I'll give it a go tonight if I get a chance and post an update