Homework/cs3460/typeahead/WordTree.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

#include "WordTree.hpp"

WordTree::WordTree() :
    m_root(std::make_shared<TreeNode>()) {}

WordTree::~WordTree()
{
}

WordTree::TreeNode::TreeNode() :
    m_endOfWord(false), m_children()
{
}

void WordTree::add(const std::string& word)
{
    if (word.empty())
        return;

    std::shared_ptr<TreeNode> current = m_root;

    for (char c : word)
    {
        if (current->m_children[c - 'a'] == nullptr)
            current->m_children[c - 'a'] = std::make_shared<TreeNode>();
        current = current->m_children[c - 'a'];
    }
    current->m_endOfWord = true;
}

bool WordTree::find(const std::string& word)
{
    std::shared_ptr<TreeNode> current = m_root;

    for (char c : word)
    {
        if (current->m_children[c - 'a'] == nullptr)
            return false;
        current = current->m_children[c - 'a'];
    }
    return current->m_endOfWord;
}

std::vector<std::string> WordTree::predict(std::string partial, std::uint8_t howMany)
{
    std::vector<std::string> predictions;
    if (partial.empty())
        return predictions;

    std::shared_ptr<TreeNode> partialEnd = m_root;

    for (char c : partial)
    {
        if (partialEnd->m_children[c - 'a'] == nullptr)
            return predictions;
        partialEnd = partialEnd->m_children[c - 'a'];
    }

    std::queue<std::pair<std::string, std::shared_ptr<TreeNode>>> queue;
    queue.push({ partial, partialEnd });

    while (!queue.empty() && predictions.size() < howMany)
    {
        auto curr = queue.front();
        queue.pop();

        if (curr.second->m_endOfWord && curr.second != partialEnd)
            predictions.push_back(curr.first);

        for (int i = 0; i < 26; i++)
            if (curr.second->m_children[i] != nullptr)
                queue.push({ curr.first + static_cast<char>(i + 'a'), curr.second->m_children[i] });
    }

    return predictions;
}

std::size_t WordTree::size()
{
    std::size_t size = 0;

    std::queue<std::shared_ptr<TreeNode>> queue;
    queue.push(m_root);

    while (!queue.empty())
    {
        auto curr = queue.front();
        queue.pop();

        if (curr->m_endOfWord)
            size++;

        for (int i = 0; i < 26; i++)
            if (curr->m_children[i] != nullptr)
                queue.push(curr->m_children[i]);
    }
    return size;
}