1 /* 2 SPDX-FileCopyrightText: 2009-2021 Graeme Gott <graeme@gottcode.org> 3 4 SPDX-License-Identifier: GPL-3.0-or-later 5 */ 6 7 #ifndef TANGLET_TRIE_H 8 #define TANGLET_TRIE_H 9 10 #include <QChar> 11 #include <QHash> 12 #include <QStringList> 13 #include <QVector> 14 class QDataStream; 15 16 /** 17 * @brief The Trie class contains a word list for fast lookup. 18 */ 19 class Trie 20 { 21 public: 22 /** 23 * @brief The Node struct contains a letter in the trie. 24 */ 25 struct Node 26 { 27 /** 28 * Constructs a node instance. 29 */ NodeNode30 Node() 31 : m_letter(QChar()) 32 , m_word(0) 33 , m_children(0) 34 , m_word_count(0) 35 , m_child_count(0) 36 { 37 } 38 39 /** 40 * @return whether the node has any child letters 41 */ isEmptyNode42 bool isEmpty() const 43 { 44 return !m_child_count; 45 } 46 47 /** 48 * @return whether the node points to a complete word 49 */ isWordNode50 bool isWord() const 51 { 52 return m_word_count; 53 } 54 55 /** 56 * Compares node with a letter. 57 * @param c letter to compare 58 * @return whether node is a matching letter 59 */ 60 bool operator==(const QChar& c) const 61 { 62 return c == m_letter; 63 } 64 65 QChar m_letter; /**< letter represented by the node */ 66 quint32 m_word; /**< offset into word list if this node is a word */ 67 quint32 m_children; /**< offset into the node list for children of node */ 68 quint8 m_word_count; /**< how many spellings of the word the node has */ 69 quint8 m_child_count; /**< how many children the node has */ 70 }; 71 72 public: 73 /** 74 * Constructs an empty trie instance. 75 */ 76 explicit Trie(); 77 78 /** 79 * Constructs a trie instance containing a single word. 80 * @param word the word to store 81 */ 82 explicit Trie(const QString& word); 83 84 /** 85 * Constructs a trie instance from a word list. 86 * @param data contents of a word list file including alternate spellings 87 */ 88 explicit Trie(const QByteArray& data); 89 90 /** 91 * Removes all nodes and spellings. 92 */ 93 void clear(); 94 95 /** 96 * @return the top-level node of the trie 97 */ child()98 const Node* child() const 99 { 100 return &m_nodes[0]; 101 } 102 103 /** 104 * Fetches a child node. 105 * @param letter the letter to check for 106 * @param node the parent node 107 * @return child node or @c nullptr if no child matches @p letter 108 */ 109 const Node* child(const QChar& letter, const Node* node) const; 110 111 /** 112 * Fetches the spellings of a word. 113 * @param word the word to look up 114 * @param default_value fallback list of spellings 115 * @return spellings of a word 116 */ 117 QStringList spellings(const QString& word, const QStringList& default_value = QStringList()) const; 118 119 /** 120 * @return whether the trie is empty 121 */ isEmpty()122 bool isEmpty() const 123 { 124 return m_nodes.isEmpty(); 125 } 126 127 friend QDataStream& operator<<(QDataStream& stream, const Trie& trie); 128 friend QDataStream& operator>>(QDataStream& stream, Trie& trie); 129 130 private: 131 /** 132 * Verify that no nodes reference outside the list of nodes. 133 */ 134 void checkNodes(); 135 136 private: 137 QVector<Node> m_nodes; /**< list of nodes */ 138 QStringList m_spellings; /**< list of words */ 139 }; 140 141 /** 142 * Writes a trie to a data stream. 143 * @param stream the output stream 144 * @param trie the trie to write 145 * @return reference to the stream 146 */ 147 QDataStream& operator<<(QDataStream& stream, const Trie& trie); 148 149 /** 150 * Reads a trie from a data stream. 151 * @param stream the input stream 152 * @param trie the trie to read into 153 * @return reference to the stream 154 */ 155 QDataStream& operator>>(QDataStream& stream, Trie& trie); 156 157 /** 158 * Writes a trie node to a data stream. 159 * @param stream the output stream 160 * @param node the trie node to write 161 * @return reference to the stream 162 */ 163 QDataStream& operator<<(QDataStream& stream, const Trie::Node& node); 164 165 /** 166 * Reads a trie node from a data stream. 167 * @param stream the input stream 168 * @param node the trie node to read into 169 * @return reference to the stream 170 */ 171 QDataStream& operator>>(QDataStream& stream, Trie::Node& node); 172 173 #endif // TANGLET_TRIE_H 174