dicttest.cpp (cpp-lecture/trie3/dicttest.cpp)

       1
       2
       3
       4
       5
       6
       7
       8
       9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      62
      63
      64
      65
      66
      67
      68
      69
      70
      71
      72
      73
      74
      75
      76
      77
      78
      79
      80
      81
      82
      83
      84
      85
      86
      87
      88
      89
      90
      91
      92
      93
      94
      95
      96
      97
      98
      99
     100
     101
     102
     103
     104
     105

#include <fstream>
#include <iostream>
#include "trie.hpp"

struct Key
{
    static constexpr size_t
    size()
    {
        return ('Z' - 'A' + 1);
    }

    static constexpr size_t
    map(char c)
    {
        assert(c>='a' && c<='z' || c>='A' && c<='Z');
        if (c>='a' && c<='z') {
            c = c - 'a' + 'A';
        }
        return c - 'A';
    }

    static constexpr char
    unmap(size_t key)
    {
        assert(key<size());
        return 'a' + key;
    }
};

bool
is_word(const std::string& word)
{
    for (char ch: word) {
        if (!((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z'))) {
            return false;
        }
    }
    return true;
}

void
longest_path(Trie<std::string, Key>::Pointer p, unsigned int count,
             unsigned int& maxcount, Trie<std::string, Key>::Pointer& maxseen)
{
    if (!p.defined()) return;
    if (p.exists()) {
        ++count;
        if (count > maxcount) {
            maxcount = count; maxseen = p;
        }
    }
    for (char ch: p) {
        auto ptr = p;
        ptr.descend(ch);
        longest_path(ptr, count, maxcount, maxseen);
    }
}

int
main()
{
    //std::ifstream words("/usr/dict/words");
    std::ifstream words("words");
    if (!words) {
        std::cerr << "Can not open /usr/dict/words" << std::endl;
    }

    Trie<std::string, Key>  trie;
    std::string             line;
    while (std::getline(words, line)) {
        if (is_word(line)) {
            trie.insert(line, line);
        }
    }

    std::string key;
    while (std::cin >> key) {
        if (is_word(key)) {
            auto ptr = trie.descend();
            if (ptr.defined()) {
                for (char ch: key) {
                    if (!ptr.descend(ch)) break;
                    if (ptr.exists()) {
                        std::cout << *ptr << std::endl;
                    }
                }
                if (ptr.defined()) {
                    std::cout << "continuation possible with: ";
                    for (char ch: ptr) {
                        std::cout << ch;
                    }
                    std::cout << std::endl;
                }
            }
        }
    }
    Trie<std::string, Key>::Pointer maxpath;
    unsigned int maxcount = 0;
    longest_path(trie.descend(), 0, maxcount, maxpath);
    if (maxcount > 0) {
        std::cout << *maxpath << std::endl;
    }
}