inverted_index.cpp

#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;
}