#include <boost/unordered_map.hpp>
#include <boost/shared_ptr.hpp>
#include <boost/make_shared.hpp>



class TrieVertex;

typedef boost::shared_ptr<TrieVertex> VertexPtr;

class TrieEdge
 {
 public:
    char fC;
    VertexPtr fTarget;
    TrieEdge(char c, VertexPtr target) : fC(c), fTarget(target) {}
};

typedef boost::shared_ptr<TrieEdge> EdgePtr;


class TrieVertex {
public:
    boost::unordered_map<char, EdgePtr> fOutEdges;
    TrieVertex() : fOutEdges() {}
};



class ReverseTrie {
private:
    VertexPtr fRoot;
    size_t fSize;

public:
    ReverseTrie( ): fRoot(boost::make_shared<TrieVertex>()), fSize(0) {}

    ~ReverseTrie() {
        fRoot.reset();
    }

    void clear() {
        boost::make_shared<TrieVertex>().swap(fRoot);
        fSize = 0;
    }

    size_t size() {
        return fSize;
    }

    bool insertStringR(const std::string &word) {
        VertexPtr currentVertex = fRoot;

        for (std::string::const_reverse_iterator i = word.rbegin(); i != word.rend(); ++i) {
            if (*i == '') {
                continue;
            }
            if (currentVertex->fOutEdges.size() == 0 || currentVertex->fOutEdges.count(*i) == 0) {
                VertexPtr targetVertex = boost::make_shared<TrieVertex>();
                EdgePtr   e = boost::make_shared<TrieEdge>(*i, targetVertex);
                currentVertex->fOutEdges[*i] = e;
                currentVertex =  e->fTarget;//*currentVertex.fOutEdges[*i]->fTarget;
            } else {
                EdgePtr     e = currentVertex->fOutEdges[*i];
                currentVertex = e->fTarget;
            }
        }
        bool exists = true;
        //end of word.
        if (currentVertex->fOutEdges.count('') == 0) {
            VertexPtr targetVertex = boost::make_shared<TrieVertex>();
            EdgePtr   e = boost::make_shared<TrieEdge>('', targetVertex);
            currentVertex->fOutEdges[''] = e;
            exists = false;
        }
        fSize++;
        return exists;
    }

    bool containsString(const std::string &word) {
        VertexPtr currentVertex = fRoot;
        for (std::string::const_reverse_iterator i = word.rbegin(); i != word.rend(); ++i) {
            if (*i == '') {
                continue;
            }
            if (currentVertex->fOutEdges.size() == 0 || currentVertex->fOutEdges.count(*i) == 0) {
                return false;
            } else {
                currentVertex = currentVertex->fOutEdges[*i]->fTarget;
            }
        }
        if (currentVertex->fOutEdges.count('') == 0) {
            return false;
        }
        return true;
    }

    void logEdges(VertexPtr vp) {
        for ( boost::unordered_map<char, EdgePtr>::iterator it = vp->fOutEdges.begin(); it != vp->fOutEdges.end(); it++) {
            char c = it->first;
            EdgePtr ep = it->second;
            std::string output;
            if (c == '')
                output.append("EOW");
            else
                output.push_back(c);
            logWarning("---", "edge:  %s", output.c_str());
            logEdges(ep->fTarget);
        }
    }

    void logEdges() {
        logEdges(fRoot);
    }
};