trie.cpp

#include <array>
#include <bitset>

using namespace std;
const int ALPH_SIZE = 26;

template <typename T, int size>
struct heap_array {
    T *          m_data;
    bitset<size> m_allocated;

    heap_array() : m_data(reinterpret_cast<T *>(new char[sizeof(T) * size])), m_allocated(0) {
    }

    bool has(int c) const {
        return m_allocated[c];
    }

    T & operator[](int c) {
        alloc(c);
        return m_data[c];
    }

    const T & operator[](int c) const {
        const_cast<heap_array *>(this)->alloc(c);
        return m_data[c];
    }

private:
    void alloc(int c) {
        if (!m_allocated[c]) {
            new(m_data + c)T();
            m_allocated[c] = true;
        }
    }
};

struct Trie {
    heap_array<Trie, ALPH_SIZE> m_children;
    bool                        m_isLeaf;

    Trie(): m_isLeaf(false), m_children() {}

    void add(const char * word) {
        if (!*word) {
            m_isLeaf = true;
        } else {
            m_children[toIdx(*word)].add(word + 1);
        }
    }

    void print(ostream & out) const {
        auto len = maxLen();
        char * buf = new char[len + 1];
        memset(buf, 0, len + 1);
        print(out, 0, buf);
        delete buf;
    }

    int maxLen() const {
        int len = 0;
        for (int c = 0; c < ALPH_SIZE; ++c) {
            if (m_children.has(c)) {
                len = max(len, m_children[c].maxLen() + 1);
            }
        }
        return len;
    }

    int countUnique() const {
        auto children = 0;
        for (int c = 0; c < ALPH_SIZE; ++c) {
            children += m_children.has(c) ? m_children[c].countUnique() : 0;
        }
        return children + m_isLeaf;
    }

    bool has(const char * word) {
        if (!*word) {
            return m_isLeaf;
        } else {
            const auto idx = toIdx(*word);
            return m_children.has(idx) && m_children[idx].has(word + 1);
        }
    }
private:
    void print(ostream & out, int lvl, char * buf) const {
        if (m_isLeaf) {
            buf[lvl] = 0;
            out << buf << endl;
        }
        for (int c = 0; c < ALPH_SIZE; ++c) {
            if (m_children.has(c)) {
                buf[lvl] = fromIdx(c);
                m_children[c].print(out, lvl + 1, buf);
            }
        }
    }

    char fromIdx(int c) const {
        return c + 'a';
    }

    int toIdx(char c) const {
        return c - 'a';
    }
};


#include <fstream>
#include <iostream>

int main() {
    const auto path = "words.txt";
    Trie t;

    ifstream file(path, ios::in);
    while (file) {
        string c;
        file >> c;
        bool ok = true;
        for (auto ch : c) {
            if (ch > 'z' || ch < 'a') {
                ok = false;
                break;
            }
        }
        if (ok) {
            t.add(c.c_str());
        }
    }

    cout << "MAX: " << t.maxLen() << endl << "UNIQUE: " << t.countUnique() << endl;
    getchar();
    t.print(cout);

    return 0;
}