RetroSearch Browse

Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from https://TheAlgorithms.github.io/C-Plus-Plus/d5/d8a/trieusinghashmap_8cpp_source.html below:

TheAlgorithms/C++: data_structures/trie_using_hashmap.cpp Source File

Go to the documentation of this file. 17#include <unordered_map> 45

std::unordered_map<char16_t, std::shared_ptr<Node>>

52

std::make_shared<Node>();

62 void insert

(

const

std::string& word) {

64 for

(

char

ch : word) {

65 if

(curr->children.find(ch) == curr->children.end()) {

66

curr->children[ch] = std::make_shared<Node>();

68

curr = curr->children[ch];

71 if

(!curr->word_end && curr !=

root_node

) {

72

curr->word_end =

true

;

82 bool search

(

const

std::string& word) {

84 for

(

char

ch : word) {

85 if

(curr->children.find(ch) == curr->children.end()) {

88

curr = curr->children[ch];

109 for

(

char

ch : prefix) {

110 if

(curr->children.find(ch) == curr->children.end()) {

113

curr = curr->children[ch];

124

std::stack<std::shared_ptr<Node>> nodes;

126 for

(

char

ch : word) {

127 if

(curr->children.find(ch) == curr->children.end()) {

130 if

(curr->word_end) {

134

nodes.push(curr->children[ch]);

135

curr = curr->children[ch];

139 if

(nodes.top()->word_end) {

140

nodes.top()->word_end =

false

;

144 while

(!(nodes.top()->word_end) && nodes.top()->children.empty()) {

146

nodes.top()->children.erase(word.back());

161 const

std::shared_ptr<Node>& element,

162

std::string prefix) {

163 if

(element->word_end) {

164

results.push_back(prefix);

166 if

(element->children.empty()) {

169 for

(

auto const

& x : element->children) {

170

std::string key =

""

;

189

std::vector<std::string> result;

193 for

(

char

ch : prefix) {

194 if

(curr->children.find(ch) == curr->children.end()) {

198

curr = curr->children[ch];

202 if

(curr->word_end && curr->children.empty()) {

203

result.push_back(prefix);

226

obj.

insert

(

"abscond"

);

232

obj.

insert

(

"approach"

);

238

assert(!obj.

(

"appy"

));

239

std::cout <<

"appy is not a word in trie"

<< std::endl;

241

assert(!obj.

(

"car"

));

242

std::cout <<

"car is not a word in trie"

<< std::endl;

243

assert(obj.

(

"app"

));

244

assert(obj.

(

"apple"

));

245

assert(obj.

(

"apples"

));

246

assert(obj.

(

"apps"

));

247

assert(obj.

(

"apen"

));

248

assert(obj.

(

"approach"

));

249

assert(obj.

(

"about"

));

250

assert(obj.

(

"abscond"

));

251

assert(obj.

(

"bus"

));

252

assert(obj.

(

"buses"

));

253

assert(obj.

(

"Bounce"

));

254

assert(obj.

(

"Apple"

));

256

std::cout <<

"All the Inserted words are present in the trie"

<< std::endl;

277

std::cout <<

"All the tests passed for startwith method"

<< std::endl;

281

std::vector<std::string> pred_words = obj.

predict_words

(

"a"

);

284

std::cout << str << std::endl;

286

assert(pred_words.size() == 8);

287

std::cout <<

"Returned all words that start with prefix a "

<< std::endl;

290 for

(

const

std::string& str : pred_words) {

291

std::cout << str << std::endl;

294

assert(pred_words.size() == 5);

295

std::cout <<

"Returned all words that start with prefix app "

<< std::endl;

298 for

(

const

std::string& str : pred_words) {

299

std::cout << str << std::endl;

302

assert(pred_words.size() == 1);

303

std::cout <<

"Returned all words that start with prefix A "

<< std::endl;

306 for

(

const

std::string& str : pred_words) {

307

std::cout << str << std::endl;

310

assert(pred_words.size() == 2);

311

std::cout <<

"Returned all words that start with prefix bu "

<< std::endl;

316

assert(!obj.

(

"app"

));

317

std::cout <<

"word app is deleted sucessful"

<< std::endl;

320 for

(

const

std::string& str : pred_words) {

321

std::cout << str << std::endl;

323

assert(pred_words.size() == 4);

324

std::cout <<

"app is deleted sucessful"

<< std::endl;

332

assert(pred_words.size() == 0);

333

std::cout <<

"No word starts with prefix h in trie"

<< std::endl;

335

std::cout <<

"All tests passed"

<< std::endl;

Trie class, implementation of trie using hashmap in each trie node for all the characters of char16_t...

Trie()=default

< Constructor

std::vector< std::string > get_all_words(std::vector< std::string > results, const std::shared_ptr< Node > &element, std::string prefix)

helper function to predict/recommend words that starts with a given prefix from the end of prefix's n...

std::shared_ptr< Node > root_node

declaring root node of trie

void insert(const std::string &word)

insert the string into the trie

void delete_word(std::string word)

delete a word/string from a trie

bool search(const std::string &word)

search a word/string inside the trie

std::vector< std::string > predict_words(const std::string &prefix)

predict/recommend a word that starts with a given prefix

bool startwith(const std::string &prefix)

search a word/string that starts with a given prefix

Functions for Trie data structure using hashmap implementation.

struct representing a trie node.

std::unordered_map< char16_t, std::shared_ptr< Node > > children

bool word_end

boolean variable to represent the node end

static void test()

Self-test implementations.

int main()

Main function.

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4

Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from https://TheAlgorithms.github.io/C-Plus-Plus/d5/d8a/trie__using__hashmap_8cpp_source.html below:

TheAlgorithms/C++: data_structures/trie_using_hashmap.cpp Source File

Showing content from https://TheAlgorithms.github.io/C-Plus-Plus/d5/d8a/trieusinghashmap_8cpp_source.html below: