Odd output from a redefined << operator in c++

Question

Hi all, I am having a runtime error that I can not for the life of me figure out. My program almost does what I want it to, but there are some corrupted characters that print out as gibberish. The program is supposed to take in a text file that represents a forest of trees, build the forest of trees, then traverse the forest to print it out as it was taken in. The tree can be arbitrarily large and each node can have arbitrarily many children. The forest is represented in the textfile as such:

a  
  b  
    c  
  d  
    e  
    z  
f  
  g  
    h  
  i  
    j  

and would translate to the following forest of two trees:

    a     
   / \  
  b   d  
 /   / \  
c   e   z  

    f      
   / \  
  g   i  
 /   /  
h   j  

The commented out lines in the code are relics that remain from when I was testing to make sure that the file was being read correctly and that the nodes I was creating were properly tagged and pointed to.

My code is as follows:

(file node.h)

#ifndef NODE_H
#define NODE_H


template<typename NODETYPE> class Forest;

template<typename NODETYPE> class ForestNode
{
    friend class Forest<NODETYPE>;

    public:
        ForestNode();

        NODETYPE getTag() const;
        ForestNode<NODETYPE> * getLeftChild() const;
        ForestNode<NODETYPE> * getSibling() const;
        void setTag(NODETYPE);
        void setLeftChild(ForestNode<NODETYPE>*);
        void setSibling(ForestNode<NODETYPE>*);
    private:
        NODETYPE tag;
        ForestNode<NODETYPE> * leftChild;
        ForestNode<NODETYPE> * sibling;
};

template<typename NODETYPE> ForestNode<NODETYPE>::ForestNode()
    : tag(0), leftChild(NULL), sibling(NULL)
{

}

template<typename NODETYPE> NODETYPE ForestNode<NODETYPE>::getTag() const
{
    return tag;
}

template<typename NODETYPE> ForestNode<NODETYPE>* ForestNode<NODETYPE>::getLeftChild() const
{
    return leftChild;
}

template<typename NODETYPE> ForestNode<NODETYPE>* ForestNode<NODETYPE>::getSibling() const
{
    return sibling;
}

template<typename NODETYPE> void ForestNode<NODETYPE>::setTag(NODETYPE info)
{
    this->tag = info;
}
template<typename NODETYPE> void ForestNode<NODETYPE>::setLeftChild(ForestNode<NODETYPE>* info)
{
    leftChild = info;
}
template<typename NODETYPE> void ForestNode<NODETYPE>::setSibling(ForestNode<NODETYPE>* info)
{
    sibling = info;
}


#endif // NODE_H

(file forest.h)

#ifndef FOREST_H
#define FOREST_H

#include <iostream>
#include <cstdlib>
#include <string>
#include "node.h"

using namespace std;

template<typename NODETYPE> class Forest
{


    template<NODETYPE> friend ostream& operator<<(ostream& output, const Forest<NODETYPE>& f1);

    template<NODETYPE> friend void outputHelper(ostream& output, const ForestNode<NODETYPE>& currentNode, int depth);

    friend void inputHelper(istream& file, int previousDepth, ForestNode<char*>& previousNode, ForestNode<char*>* *nodeArray, int& nodeCount);

    friend istream& operator>>(istream& file, Forest<char*>& f1);

    public:

        Forest();
        Forest( const Forest& otherForest);
        void nodes(int&) const;

        ForestNode<NODETYPE> * root;

};

template<typename NODETYPE>ostream& operator<<(ostream& output, const Forest<NODETYPE>& f1)
{
    int depth = 0;

    output << f1.root->getTag();
    outputHelper(output, f1.root, depth);

    return output;
}

void outputHelper(ostream& output, const ForestNode<char*> *currentNode, int depth)
{
    for(int i = 0; i < depth; i++)
    {
        output << ' ' << ' ';
    }

    output << currentNode->getTag();
    output << endl;

    if(currentNode->getLeftChild() != NULL)
    {
        outputHelper(output, currentNode->getLeftChild(), depth+1);
    }

    if(currentNode->getSibling() != NULL)
    {
        outputHelper(output, currentNode->getSibling(), depth);
    }

}


void inputHelper(istream& file, int previousDepth, ForestNode<char*>* previousNode, ForestNode<char*> ** nodeArray, int& nodeCount)
{
    int spaceCounter = 0;

    while(file.peek() == ' ')
    {
        spaceCounter++;
        file.ignore(1);
    }


    ForestNode<char*>* currentNode = new ForestNode<char*>();

    char bar[100];
    file.getline(bar, 100);
//        cout << bar << endl;

    currentNode->setTag(bar);
//        cout << currentNode->getTag();

    if(spaceCounter/2 < previousDepth)
    {
        for(int i = (spaceCounter/2)+1; i < nodeCount; i++)
        {
            nodeArray[i] = NULL;
        }
    }

    cout << "array:";


    for(int i = 0; i < spaceCounter/2; i++)
    {
        cout << nodeArray[i]->getTag();
    }

//        cout << endl;

//        cout << spaceCounter/2 << ':';

    if(spaceCounter/2 == previousDepth+1)
    {
        previousNode->setLeftChild(currentNode);
//      cout << "i'm a child:" << previousNode->getLeftChild()->getTag() << " and my parent is:" << nodeArray[(spaceCounter/2)-1]->getTag();
        nodeArray[spaceCounter/2] = currentNode;
    }
    else
    {
        if(!(nodeArray[spaceCounter/2] == NULL))
        {
        nodeArray[spaceCounter/2]->setSibling(currentNode);
//      cout << "I'm a sibling:" << nodeArray[spaceCounter/2]->getSibling()->getTag() << " and my older sibling is:" << nodeArray[spaceCounter/2]->getTag();
        nodeArray[spaceCounter/2] = currentNode;
        }

    }

//        cout << endl;

//        cout << currentNode->getTag();

    if(!file.eof())
    {
    inputHelper(file, spaceCounter/2, currentNode, nodeArray, nodeCount);
    }


}

istream& operator>>(istream& file, Forest<char*>& f1)
{
    int charCount = 0;
    int nodeCount = 0;

    file.seekg(0, ios_base::end);

    charCount = file.tellg();

    file.seekg(0, ios_base::beg);

    for(int i=0; i <= charCount; i++)
    {
//            cout << i << ':' << file.peek() << endl;
        if(file.peek() == '\n')
        {
            nodeCount++;
        }
        file.seekg(i);
    }

    file.seekg(0, ios_base::beg);

    nodeCount = nodeCount/2;
    nodeCount = nodeCount + 1;

    ForestNode<char*>* forestNodeArray[nodeCount];//holds pointers to last node of depth i

    char bar[100];
    file.getline(bar, 100);
    cout << bar << endl;

    ForestNode<char*>* foo = new ForestNode<char*>();
    f1.root = foo;
    f1.root->setTag(bar);

    forestNodeArray[0] = f1.root;
    inputHelper(file, 0, f1.root, forestNodeArray, nodeCount);

    return file;
}

endif

(file main.h)

#include <iostream>
#include <fstream>
#include "forest.h"

using namespace std;

int main()
{
    Forest<char*> forest;
    filebuf fb;
    fb.open ("forest1.txt",ios::in);
    istream is(&fb);

    is >> forest;

    fb.close();

    cout << forest;
}

I am using the following text file:

a
  z
    c
      d
    e
      f
  g
    h
  i
    y
x
  w
    m
      n
    o
      p
  q
    r
  s
    t

And my output is as follows:

└@GƒtF
  ░≥9
    c
      d
    e
      f
  g
    h
  i
    Eⁿ(
☺
  L⌡(
    m
      n
    o
      p
  q
    r
  s
    t

Process returned 0 (0x0) execution time : 0.092 s Press any key to continue.

As you can see, the output is very close to what it should be, however some of the characters, or tags as they are contained within ForestNodes are corrupted, and I cannot for the life of me figure out why. Any help would be greatly appreciated, and you would be regarded by me as a god among men.

Answer 1

As far as I can tell, your nodes contain pointers to a local buffer bar in function inputHelper(). When you print the result of getTag() (commented out) right after the call to setTag(), the buffer is still valid. However, as soon as the function returns, your code results in undefined behavior because you are referring to some location on the stack that is not valid anymore.

Have you considered using std::string instead of char buffers and char*? The automatic memory management and copy semantics of std::string will solve your problem.

Edit: the output gibberish is explained by the fact that the lower stack frames are written over by some other function calls. Deper nodes in the trees happen to refer to memory that is further away and less likely to be overwritten, which is why their values are output properly.