Huffman Encoder - Recursive, coding function fail

Question

I'm working on a Huffman code generator. Below is my function to make up the tree. The tree is based off a vector of object pointers. I have checked and it seems to be working properly. I would now like to pass the pointer at position pointerVect[0] which should be the root of the tree to my Huffman encoding recursive function below, but for some reason it isn't working properly, as when i try to print the contents of the map where the codes are stored nothing prints out.

class asciiChar  //Individual character module >>> Base Class
{

public:

    void setCharValue (char letter)
    {
        charValue = letter;
    }

    char getCharValue ()
    {
        return charValue;
    }

    void incrementCharCount ()
    {
        charCount++;
    }

    int getCharCount()
    {
        return charCount;
    }

    virtual asciiChar * getLeft()
    {
        return left;
    }

    virtual asciiChar * getRight()
    {
        return right;
    }


    asciiChar(char c, int f)  //Constructor
    {
        charValue = c;
        charCount = f;
    }


    asciiChar & operator= (const asciiChar & other)  //Overloaded assignment operator
    {
        charValue = other.charValue;
        charCount = other.charCount;

        return *this;
    }


    char charValue;
    int charCount = 0;
    asciiChar * left = NULL;
    asciiChar * right = NULL;
};


class parentNode : public asciiChar  //Connector node
{

public:

    parentNode(asciiChar c0, asciiChar c1) : asciiChar(NULL, c0.getCharCount() + c1.getCharCount())
    {
        left = &c0;
        right = &c1;

    }

    ~parentNode()
    {
        if (left) delete left;
        if (right) delete right;
    }

};


asciiChar* createTree (vector<asciiChar> sortedVector)
{
    vector<asciiChar*> pointerVect;
    pointerVect.reserve(sortedVector.size());

    for(int i=0; i < sortedVector.size(); i++)
    {
        pointerVect.push_back(new asciiChar(sortedVector[i].getCharValue(), sortedVector[i].getCharCount()));

    }

    while (pointerVect.size() > 1)
    {
        asciiChar * newL = pointerVect.back();
        pointerVect.pop_back();

        asciiChar * newR = pointerVect.back();
        pointerVect.pop_back();

        asciiChar * parent = new parentNode(* newL, * newR);
        pointerVect.push_back(parent);

        vectSort2 (pointerVect);

    }

    return pointerVect[0]; //Returns pointer at very top (The root of the tree)
}

Answer 1

My suspicion is with your first function 'createTree'

As my initial comment indicates, you should consider using a priority queue for various reasons. Here is a quick list of problems I am noticing

• You are sorting a vector of pointers. So the pointers will be sorted based on their address values and not the objects they point too. However, it is possible you are supplying a comparator. If this is the case, ignore this bullet.
• Resorting the vector each while loop iteration is O(nLog(n)) where inserting into a priority queue and maintaining sorted order is O(Log(n))
• Since you are sorting on pointers, the index of 0 for the vector isn't guaranteed to be the root of the tree.

Consider using a priority queue instead: In the header file

 #include <queue>

// Comparator for priority queue. Use this so it compared what the pointers point too  and not the pointers themselves. This way the frequencies are used for the
// comparisons. This forces the priority queue to order from lowest freq
// to the highest frequency
struct CompareHuffChars : public binary_function<asciiChar*, asciiChar*, bool>
{
    bool operator()(const asciiChar* left, const asciiChar* right) const
    {
        // Be sure to add functionality to get frequency for each asciiChar object
        return left->getFrequency() > right->getFrequency();
    }
}; // end struct

priority_queue<asciiChar*,vector<asciiChar*>,CompareHuffChars > * bytePriorityQueue;
asciiChar * huffmanTree; // Pointer to assign to root node of tree when found

In the implementation file....

while (!(this->bytePriorityQueue->empty())) {
    asciiChar * qtop = this->bytePriorityQueue->top();
    this->bytePriorityQueue->pop();
if (this->bytePriorityQueue->empty()) {
        // Found the root asciiChar node
        this->huffmanTree = qtop; // huffManTree = asciiChar *
    } else {
        // There are more asciiChar nodes so we need to grab the 2nd from top
        // and combine their frequencies into a new asciiChar node and insert it
        // back into the priority queue

        asciiChar * newNode;
        asciiCharChar * qtopSecond = this->bytePriorityQueue->top();

        // Remove it from the queue
        this->bytePriorityQueue->pop();

        // Now create a new asciiChar node with the added frequences
        // qtopSecond should always be > or = qtop
        // which will adhere to the binary tree structure

        // This assumes asciiChar adds the frequencies of qtop and qtopSecond in constructor
        newNode = new asciiChar(qtop,qtopSecond);

        // Push the new node into the p queue
        // Stays sorted with Log(n) insertion
        this->bytePriorityQueue->push(newNode);

        // Now repeat this until the tree is formed (1 node left in queue)

    } // end if

} // end while

//The p queue should now be completely empty (len =0)

}

Now my version would require a little refactoring of asciiChar. But, this method should work better than the one posted and resolve your error.

EDIT

Okay I 'think' I have found your error. In your header file for asciiChar, getLeft and getRight functions are non virtual. This means when you have a base pointer of type asciiChar * pointing to an object of type parentNode (child class) it will be invoking the parent's (asciiChar) getLeft and getRight function which will always return NULL. You re declared a left and right in your child class (parentNode) which you don't need to do since these member variables were public in your parent class. Make the getLeft and getRight functions virtual and remove the declarations for left and right in the parentNode class along with their respective getter functions.

// In aschiiChar
virtual asciiChar * getLeft()
{
    return left;
}

virtual asciiChar * getRight()
{
    return right;
}

Side Note: You should check in your destructors if pointers are NULL before deleting.

if (left) delete left;
if (right) delete right;

Final Edit

Thanks for posting more information. Okay your problem boiled down to the following:

// This is your parentNode constructor
parentNode(asciiChar c0, asciiChar c1) : asciiChar(NULL, c0.getCharCount() + c1.getCharCount())
{
    left = &c0;
    right = &c1;

}

// This is what the parentNode constructor should look like
parentNode(asciiChar * c0, asciiChar * c1) : asciiChar(NULL, c0->getCharCount() + c1->getCharCount())
{
    left = c0;
    right = c1;

}

and lastly...

asciiChar* createTree (vector<asciiChar> sortedVector)
{
vector<asciiChar*> pointerVect;
pointerVect.reserve(sortedVector.size());

for(int i=0; i < sortedVector.size(); i++)
{
    pointerVect.push_back(new asciiChar(sortedVector[i].getCharValue(), sortedVector[i].getCharCount()));

}

while (pointerVect.size() > 1)
{
    asciiChar * newL = pointerVect.back();
    pointerVect.pop_back();

    asciiChar * newR = pointerVect.back();
    pointerVect.pop_back();

    // CHANGE HERE
    // Don't dereference the pointers. If you dereference them you are passing by value
    // and creating copies in the constructor which are destroyed upon exit of the constructor
    asciiChar * parent = new parentNode( newL,  newR);
    pointerVect.push_back(parent);

    vectSort2 (pointerVect);

}

return pointerVect[0]; //Returns pointer at very top (The root of the tree)
}

Your problem boiled down you were passing by value and assigning the address of the local copies to member variable pointers of parentNode. These pointers in parentNode were then pointing to non existent memory or memory that didn't belong to them.

Hope this helped...