treestring.hpp

Go to the documentation of this file.

#ifndef TREESTRING_HPP
#define TREESTRING_HPP

#include <cassert>
#include <string>
#include <forward_list>
#include <utility>
#include <sstream>

using std::string;
using std::forward_list;
using std::stringstream;
using std::pair;

class TreeStringException : std::exception {
    private:
        char* _cause; 
    public:
        TreeStringException(char* cause):
            _cause(cause)
            {}
        
        virtual ~TreeStringException() throw(){
            // do nothing
        }
        
        virtual const char* what()const throw(){
            return _cause;
        }
};

class Node {
    
    private:
        int _childNbr;
        int _wordFrequency;
        char _tag;
        forward_list<Node*> _children;
    
    public:
        Node(const Node &other):
            _childNbr(other._childNbr),
            _wordFrequency(other._wordFrequency),
            _tag(other._tag),
            _children(other._children)
            {}
            
        Node(char data, int frequency):
        _childNbr(0),
        _wordFrequency(frequency),
        _tag(data)
        {
            // initialize the simply-linked list
            _children = forward_list<Node*>();
        }
        
        Node():
        _childNbr(0),
        _wordFrequency(0),
        _tag('@')
        {
            // initialize the simply-linked list
            _children = forward_list<Node*>();
        }
        
        ~Node(){
            // usefull ?
            //delete &_children;
            //delete &_tag;
        }
        
        Node& operator=(const Node &other){
            // prevent objet copying itself
            if(this != &other){
                this->_childNbr = other._childNbr;
                this->_tag = other._tag;
                this->_wordFrequency = other._wordFrequency;
                this->_children = other._children;
            }
            return (*this); // allow a = b = c
        }
        
        bool operator==(const Node& rhs){
            // same adress ⇒ same item
            return this == &rhs;
        }
        
        bool operator!=(const Node &rhs){
            return this != &rhs;
            // return not(lhs == rhs);
        }
        
        bool isLeaf(){
            return 0 == _childNbr;
            //return frenquency > 0;
        }
        
        int height(){
            if(isLeaf()){
                return 0;
            }
            else {
                // start heights at zero
                // heights[0] : greatest height, heights[1] : computed height in the loop
                int heights[2] = {0,0};
                // for each child - using C++11 syntax
                for(Node* child : _children){
                    // compute child height and store it
                    heights[1] = 1 + child->height();
                    // if computed height is greater then the old one
                    if(heights[0] < heights[1]){
                        // store it as the new greate one
                        heights[0] = heights[1];
                    } // else, nothing
                }
                return heights[0];
            }
        }
        
        Node* append(const char n_data, int frequency){
            Node* tmp;
            bool undone = true;
            auto it = _children.begin();
            // while n_data is not added
            while(undone and it != _children.end()){
                if(n_data == (*it)->_tag){
                    (*it)->_wordFrequency += frequency; // update word frenquency
                    tmp = (*it);
                    undone = !undone; // job is now done
                }
                ++it;
            }
            // if letter is not present, add it
            if(undone){
                 tmp = new Node(n_data, frequency);
                _children.push_front(tmp);
                _childNbr++;
            }
            return tmp;
        }  
        
        char getTag(){ return _tag; }
        
        
        string toString(){
            if(isLeaf()){
                return string(&_tag);
            }
            else {
                string desc = string(&_tag);
                for(Node* child: _children){
                    desc += ", " + child->toString();
                }
                return desc;
            }
        }

        void toList(forward_list<string> &words, string word){
            '@' != _tag?word += _tag:word; // if it's not the root, add tag
            if(0 < _wordFrequency){
                words.push_front(word);
            }
            if(not isLeaf()){
                for(Node* child : _children){
                    child->toList(words, word);
                }
            }
        }

        void toFrequencedList(forward_list<pair<string,int>> &words, string word){
            // if it's not the root, add tag
            // avoid to prefix words with '@', the root char
            '@' != _tag?word += _tag:word;
            // if it's a word end
            if(0 < _wordFrequency){
                // add the word and his frequency in a pair and
                // add it to the list
                words.push_front(pair<string,int>(word, _wordFrequency));
            }
            // if it's not a leaf
            if(not isLeaf()){
                // for each child
                for(Node* child : _children){
                    // get words in the subtree
                    child->toFrequencedList(words, word);
                }
            }
        }

};

class TreeString {
    
    private:
        Node _root; 
    public:
        TreeString():
            _root(Node())
            {}
            
        TreeString(const TreeString &other):
            _root(other._root)
            {}
        
        ~TreeString(){
            //delete &_root;
        }
        
        int height(){
            return _root.height();
        }
        
        void put(const string &word){
            // adress of the last added Node
            Node* lastInserted = &_root;
            int i;
            int i_end = word.size()-1;
            // from the first to the last-but-one char
            for(i=0; i<i_end; ++i){
                // add it to the tree
                lastInserted = lastInserted->append(word[i], 0);
            }
            // add the last char and the frequence of the word
            lastInserted->append(word[i], 1); // end of the word
        }

        string toString(){
            return _root.toString();
        }

        void getWords(forward_list<string> &list){
            _root.toList(list, string());
        }
        
        void getWordsFrequencies(forward_list<pair<string,int>> &words){
            // get the list of all words stored
            _root.toFrequencedList(words, string());
        }
};

#endif // TREESTRING_HPP