Skip to content

Instantly share code, notes, and snippets.

@jcelerier
Last active May 26, 2016 10:09
Show Gist options
  • Save jcelerier/28c3d159d8fa52a741667d21f18870e8 to your computer and use it in GitHub Desktop.
Save jcelerier/28c3d159d8fa52a741667d21f18870e8 to your computer and use it in GitHub Desktop.
#include <fstream>
#include <iostream>
#include <vector>
#include <string>
#include <array>
#include <memory>
#include <boost/range/algorithm.hpp>
using std::string;
using std::vector;
using std::array;
using std::unique_ptr;
using std::move;
using std::cout;
using std::make_unique;
const string _CHARS = "abcdefghijklmnopqrstuvwxyz0123456789.:-_/";
const size_t MAX_NODES = 41;
struct node
{
void clear()
{
for(auto& a_node : next)
{
a_node.reset();
}
isWord = false;
}
vector<string> files;
array<unique_ptr<node>, MAX_NODES> next{};
bool isWord = false;
};
class key_index
{
public:
void add(string s, string fileName)
{
boost::range::transform(s, s.begin(), tolower);
string h;
for(auto c : s)
{
if( c == 32 )
{
pushFileName(addWord(h), fileName);
h.clear();
continue;
}
h.append(1, c);
}
if(!h.empty())
pushFileName(addWord(h), fileName);
}
void findWord(string s)
{
vector<string> v = find(s);
if(v.empty())
{
cout << s + " was not found!\n";
return;
}
cout << s << " found in:\n";
for(auto& str : v)
{
cout << str << "\n";
}
cout << "\n";
}
private:
void pushFileName(node& n, string fn)
{
auto i = boost::range::find(n.files, fn);
if(i == n.files.end())
n.files.push_back(fn);
}
vector<string> find(string s)
{
size_t idx;
boost::range::transform(s, s.begin(), tolower);
node* rt = &root;
for(auto c : s)
{
idx = _CHARS.find(c);
if(idx < MAX_NODES)
{
if(!rt->next[idx])
return {};
rt = rt->next[idx].get();
}
}
if(rt->isWord)
return rt->files;
return {};
}
node& addWord(string s)
{
size_t idx;
node* rt = &root;
node* n;
for(auto c : s)
{
idx = _CHARS.find(c);
if(idx < MAX_NODES)
{
n = rt->next[idx].get();
if(n)
{
rt = n;
continue;
}
rt->next[idx] = make_unique<node>();
n = rt->next[idx].get();
rt = n;
}
}
rt->isWord = true;
return *rt;
}
node root;
};
int main()
{
key_index t;
string s;
for(auto file : { "file1.txt", "f_text.txt", "text_1b.txt" })
{
std::ifstream f;
f.open( file, std::ios::in );
if( f.good() ) {
while( !f.eof() )
{
f >> s;
t.add(s, file);
s.clear();
}
f.close();
}
}
while( true )
{
cout << "Enter one word to search for, return to exit: ";
std::getline( std::cin, s );
if( !s.length() ) break;
t.findWord( s );
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment