// A represents the id of a document to be indexed (e.g. a snippet ID)
transient sclass WordIndexWithBitSets<A> {
  S regexp = "\\w+";
  new UniqueList<A> documents;
  Map<S, Entry> index = ciMap();

  // each word can be represented as either an int array, a bit set or both
  sclass Entry {
    new Set<Int> intSet; // while building the index
    int[] intArray;
    BitSet bitSet;
  }
  
  *() {}
  *(Map<A, S> map) { fOr (A a, S text : map) add(a, text); }
  
  void add(A a, S text) {
    int idx = documents.addOrGetIndex(a);
    Set<S> words = extractWords(text);
    for (S word : words) addWord(idx, word);
  }
  
  void addWord(int idx, S word) {
    Entry e = index.get(word);
    if (e == null) index.put(word, e = new Entry);
    e.intSet.add(idx);
  }
  
  // Call this exactly once before doing queries on the index
  void doneAdding() {
    for (Entry e : values(index)) {
      e.intArray = sortIntArrayInPlace(toIntArray(e.intSet));
      e.bitSet = intArrayToBitSet(e.intArray);
      e.intSet = null;
    }
  }
  
  Set<S> extractWords(S text) {
    ret asCISet(extractWords_list(text));
  }
  
  LS extractWords_list(S text) {
    ret regexpExtractAll(regexp, text);
  }
  
  L<IntRange> wordRanges(S text) {
    ret regexpFindRanges(regexp, text);
  }
  
  L<A> documentsContainingWord(S word) {
    Entry e = index.get(word);
    ret e == null ? null : listFromFunction(e.intArray.length, i -> documents.get(e.intArray[i]));
  }
  
  NavigableSet<S> words() { ret (NavigableSet) keys(index); }
  
  int numWords() { ret l(index); }
  
  // These methods only work when A = S
  
  void add(S s) { add((A) s, s); }
  void remove(S s) { remove((A) s, s); }
}