trie.cpp (1182B)
1 #include <algorithm> 2 #include <cstdint> 3 4 #include "poafloc/poafloc.hpp" 5 6 namespace poafloc { 7 8 bool Parser::trie_t::insert(const std::string& option, int key) 9 { 10 trie_t* crnt = this; 11 12 if (!is_valid(option)) return false; 13 14 for (const char chr : option) 15 { 16 if (!crnt->m_terminal) crnt->m_key = key; 17 crnt->m_count++; 18 19 const size_t idx = static_cast<unsigned>(chr) - 'a'; 20 if (!crnt->m_children.at(idx)) 21 crnt->m_children.at(idx) = std::make_unique<trie_t>(); 22 23 crnt = crnt->m_children.at(idx).get(); 24 } 25 26 crnt->m_terminal = true; 27 crnt->m_key = key; 28 29 return true; 30 } 31 32 int Parser::trie_t::get(const std::string& option) const 33 { 34 const trie_t* crnt = this; 35 36 if (!is_valid(option)) return 0; 37 38 for (const char chr : option) 39 { 40 const size_t idx = static_cast<unsigned>(chr) - 'a'; 41 if (!crnt->m_children.at(idx)) return 0; 42 43 crnt = crnt->m_children.at(idx).get(); 44 } 45 46 if (!crnt->m_terminal && crnt->m_count > 1) return 0; 47 return crnt->m_key; 48 } 49 50 bool Parser::trie_t::is_valid(const std::string& option) 51 { 52 return std::all_of( 53 begin(option), end(option), [](char chr) { return std::islower(chr); }); 54 } 55 56 } // namespace poafloc