#pragma once

#include <istream>
#include <cassert>
#include <ostream>
#include <set>
#include <list>
#include <vector>
#include <map>
#include <string>
#include "synchronized.cpp"
#include <unordered_map>
#include <future>
#include <mutex>
#include <shared_mutex>
#define A (26)
#define BIT(k) (1ULL<<(k))
#define TST(u,i) (((u) >> (i)) & 1ull)

const size_t oo= numeric_limits<size_t>::max();
using namespace std;

class InvertedIndex {
public:
    InvertedIndex() {
        root= new cell();
    }
  void Add(string document);
  const list<size_t> &Lookup(const string& word) const;
  const list<size_t> &Lookup(string_view sv) const;

  const string& GetDocument(size_t id) const {
    return docs[id];
  }
  int size() const { return docs.size(); }

private:
  struct cell {
      cell *son[A];
      unsigned int mask;
      size_t id;
      cell() {
          mask= 0, id= +oo;
      }
  };
  cell *root;
  size_t current_id= 0;
  size_t insert( const string &s ) {
      cell *x= root;
      for ( int i= 0; i < s.size(); ++i ) {
          auto ch= s[i]-'a';
          if ( not TST(x->mask,ch) )
              x->mask|= BIT(ch), x->son[ch]= new cell();
          x= x->son[ch];
      }
      if ( x->id < +oo )
          return x->id;
      index.emplace_back();
      x->id= current_id++;
      assert( x->id < index.size() );
      return x->id;
  }
  size_t insert( string_view s ) {
      cell *x= root;
      for ( int i= 0; i < s.size(); ++i ) {
          auto ch= s[i]-'a';
          if ( not TST(x->mask,ch) )
              x->mask|= BIT(ch), x->son[ch]= new cell();
          x= x->son[ch];
      }
      if ( x->id < +oo )
          return x->id;
      index.emplace_back();
      x->id= current_id++;
      assert( x->id < index.size() );
      return x->id;
  }
  size_t find( const string &s ) const {
      cell *x= root;
      for ( int i= 0; i < s.size(); ++i ) {
          auto ch= s[i]-'a';
          if ( not TST(x->mask,ch) )
              return +oo;
          x= x->son[ch];
      }
      if ( x->id < +oo )
          return x->id;
      return +oo;
  }
  size_t find( string_view s ) const {
      cell *x= root;
      for ( int i= 0; i < s.size(); ++i ) {
          auto ch= s[i]-'a';
          if ( not TST(x->mask,ch) )
              return +oo;
          x= x->son[ch];
      }
      if ( x->id < +oo )
          return x->id;
      return +oo;
  }
  vector<list<size_t>> index;
  vector<string> docs;
  list<size_t> empty_list;
};

class SearchServer {
public:
  SearchServer() = default;
  explicit SearchServer(istream& document_input);
  void UpdateDocumentBase(istream& document_input);
  void AddQueriesStream(istream& query_input, ostream& search_results_output);
private:
  Synchronized<InvertedIndex> index;
  void AddQueriesStreamWorker( istream& query_input, ostream& search_results_output ) ;
  mutex mtx;
};