| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #ifndef LYTHON_TRIE_H | ||
| 2 | #define LYTHON_TRIE_H | ||
| 3 | |||
| 4 | #include <array> | ||
| 5 | #include <cstdio> | ||
| 6 | #include <memory> | ||
| 7 | |||
| 8 | #include "logging/logging.h" | ||
| 9 | |||
| 10 | namespace lython { | ||
| 11 | |||
| 12 | // This use a flat array to store children | ||
| 13 | // it use more memory than a simple node trie | ||
| 14 | // | ||
| 15 | // Depth is usually 2-3 tries since it is only used for operators | ||
| 16 | // | ||
| 17 | // | ||
| 18 | template <size_t size> | ||
| 19 | class Trie { | ||
| 20 | public: | ||
| 21 | Trie() { | ||
| 22 |
2/2✓ Branch 0 taken 6784 times.
✓ Branch 1 taken 53 times.
|
6837 | for (auto& child: children) { |
| 23 | 6784 | child = nullptr; | |
| 24 | } | ||
| 25 | 53 | } | |
| 26 | |||
| 27 | Trie(Trie const& trie) { | ||
| 28 | ✗ | for (size_t i = 0; i < size; i++) { | |
| 29 | ✗ | auto& child = trie.children[i]; | |
| 30 | |||
| 31 | ✗ | if (child != nullptr) { | |
| 32 | // call copy constructor recursively | ||
| 33 | ✗ | children[i] = ::std::make_unique<Trie>(*child.get()); | |
| 34 | } | ||
| 35 | } | ||
| 36 | ✗ | } | |
| 37 | |||
| 38 | Trie operator=(Trie const& trie) { | ||
| 39 | ✗ | for (size_t i = 0; i < size; i++) { | |
| 40 | ✗ | auto& child = trie.children[i]; | |
| 41 | |||
| 42 | ✗ | if (child != nullptr) { | |
| 43 | // call copy constructor recursively | ||
| 44 | ✗ | children[i] = std::make_unique<Trie>(*child.get()); | |
| 45 | } | ||
| 46 | } | ||
| 47 | |||
| 48 | ✗ | return *this; | |
| 49 | } | ||
| 50 | |||
| 51 | //! Returns if the the value was inserted of not | ||
| 52 | bool insert(std::string_view const& name) { | ||
| 53 | 41 | Trie* ptr = this; | |
| 54 |
2/2✓ Branch 2 taken 79 times.
✓ Branch 3 taken 41 times.
|
120 | for (auto c: name) { |
| 55 |
2/2✓ Branch 2 taken 52 times.
✓ Branch 3 taken 27 times.
|
79 | if (ptr->children[c] == nullptr) { |
| 56 |
1/2✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
|
52 | ptr->children[c] = std::make_unique<Trie>(); |
| 57 | } | ||
| 58 | |||
| 59 | 79 | ptr = ptr->children[c].get(); | |
| 60 | } | ||
| 61 | |||
| 62 | assert(ptr != nullptr, "ptr cant be null"); | ||
| 63 | |||
| 64 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 41 times.
|
41 | if (ptr->leaf()) { |
| 65 | ✗ | return false; | |
| 66 | } | ||
| 67 | |||
| 68 | 41 | ptr->_leaf = true; | |
| 69 | 41 | return true; | |
| 70 | } | ||
| 71 | |||
| 72 | //! return the last Trie that match the given string | ||
| 73 | //! for autocompletion for example | ||
| 74 | Trie const* matching(std::string_view const& name) const { | ||
| 75 | Trie const* ptr = this; | ||
| 76 | |||
| 77 | for (auto c: name) { | ||
| 78 | ptr = ptr->matching(int(c)); | ||
| 79 | |||
| 80 | if (ptr == nullptr) { | ||
| 81 | return nullptr; | ||
| 82 | } | ||
| 83 | } | ||
| 84 | return ptr; | ||
| 85 | } | ||
| 86 | |||
| 87 | Trie const* matching(int c) const { | ||
| 88 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 5390 times.
|
5390 | if (c >= size) { |
| 89 | ✗ | return nullptr; | |
| 90 | } | ||
| 91 | |||
| 92 | 5390 | return children.at(c).get(); | |
| 93 | } | ||
| 94 | |||
| 95 | bool has(std::string_view const& name) const { | ||
| 96 | Trie const* ptr = matching(name); | ||
| 97 | return ptr != nullptr && ptr->leaf(); | ||
| 98 | } | ||
| 99 | |||
| 100 | int has_children() const { | ||
| 101 | int count = 0; | ||
| 102 | for (auto& child: children) { | ||
| 103 | count += child != nullptr; | ||
| 104 | } | ||
| 105 | return count; | ||
| 106 | } | ||
| 107 | |||
| 108 | bool leaf() const { return _leaf; } | ||
| 109 | |||
| 110 | private: | ||
| 111 | std::array<std::unique_ptr<Trie>, size> children; | ||
| 112 | bool _leaf = false; | ||
| 113 | }; | ||
| 114 | |||
| 115 | // naive CoWTrie | ||
| 116 | // this should not happen often as the top level module should be the one | ||
| 117 | // handling the addition of new operators. Although users can define | ||
| 118 | // local operators which does require to copy the entrie Trie | ||
| 119 | template <size_t size> | ||
| 120 | class CoWTrie { | ||
| 121 | public: | ||
| 122 | CoWTrie(Trie<size> const* original): original(original) {} | ||
| 123 | |||
| 124 | // if no original is provided just use the copy | ||
| 125 | CoWTrie(): was_copied(true), original(nullptr) {} | ||
| 126 | |||
| 127 | bool insert(std::string_view const& name) { return trie().insert(name); } | ||
| 128 | |||
| 129 | bool leaf() const { return trie().leaf(); } | ||
| 130 | |||
| 131 | int has_children() const { return trie().has_children(); } | ||
| 132 | |||
| 133 | bool has(std::string_view const& name) const { return trie().has(name); } | ||
| 134 | |||
| 135 | Trie<size> const* matching(std::string_view const& name) const { return trie().matching(name); } | ||
| 136 | |||
| 137 | Trie<size> const* matching(int c) const { return trie().matching(c); } | ||
| 138 | |||
| 139 | Trie<size> const& trie() const { return was_copied ? copy : *original; } | ||
| 140 | |||
| 141 | private: | ||
| 142 | Trie<size>& trie() { | ||
| 143 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 41 times.
|
41 | if (!was_copied) { |
| 144 | ✗ | copy = Trie<size>(*original); | |
| 145 | } | ||
| 146 | 41 | return copy; | |
| 147 | } | ||
| 148 | |||
| 149 | bool was_copied = false; | ||
| 150 | Trie<size> const* original; | ||
| 151 | Trie<size> copy; | ||
| 152 | }; | ||
| 153 | } // namespace lython | ||
| 154 | |||
| 155 | #endif | ||
| 156 |