I have been lately working in my C++, and I finished up this trie, and I want to know how my C++ is looking so far.
Node.hpp
#pragma once
#include <memory>
static const int ALPHABETSIZE = 26;
struct Node {
bool isEnd;
int prefixCount;
std::shared_ptr<Node> child[ALPHABETSIZE];
};
Trie.hpp
#pragma once
#include "Node.hpp"
#include <string>
#include <vector>
class Trie {
std::shared_ptr<Node> head;
public:
Trie();
void insert(const std::string& word) const;
bool search(const std::string& word) const;
unsigned int wordsWithPrefix(const std::string& prefix) const;
};
Trie.cpp
#include "Trie.hpp"
Trie::Trie() {
head = std::make_unique<Node>();
head->isEnd = false;
head->prefixCount = 0;
for (int i = 0; i < ALPHABETSIZE; ++i) {
head->child[i] = nullptr;
}
}
void Trie::insert(const std::string& word) const{
auto current = head;
for (int i = 0; i < word.length(); ++i) {
int letter = word[i] - 'a';
if (!current->child[letter])
current->child[letter] = std::make_shared<Node>();
current->child[letter]->prefixCount++;
current = current->child[letter];
}
current->isEnd = true;
}
bool Trie::search(const std::string& word) const{
auto current = head;
for (int i = 0; i < word.length(); ++i) {
auto letter = word[i] - 'a';
if (!current->child[letter])
return false;
current = current->child[letter];
}
return current->isEnd;
}
unsigned int Trie::wordsWithPrefix(const std::string& prefix) const{
auto current = head;
for (int i = 0; i < prefix.length(); ++i) {
auto letter = prefix[i] - 'a';
if (!current->child[letter])
return 0;
current = current->child[letter];
}
return current->prefixCount;
}
Source.cpp
#include <iostream>
#include <fstream>
#include <algorithm>
#include "Trie.hpp"
int main() {
Trie trie;
std::ifstream file;
std::string word = " ", input;
file.open("dictionary.txt");
//Ask for input
std::cin >> input;
std::transform(input.begin(), input.end(), input.begin(), ::tolower);
auto beenHere = false;
//Add every word to the trie.
while (std::getline(file, word)) {
std::transform(word.begin(), word.end(), word.begin(), ::tolower);
//if word's first character equals to input's, go on, else, dont add it onto the trie.
if (word[0] == input[0]){
beenHere = true;
trie.insert(word);
}
//If you've already been on the word's first character
//, and it isn't the same as the input's you are done.
if (beenHere && word[0] != input[0]) break;
}
std::string x = "";
for (int i = 0, length = input.length(); i < length; ++i) {
x += input.at(i);
if (trie.wordsWithPrefix(x) == 0) {
std::cout << x << "<" << input.substr(i+1, length - 1);
break;
}
}
file.close();
}