// A = element  (e.g. a word)
// B = instance (e.g. a text snippet)
// should support concurrent lookups
transient sclass ElementInstanceMatrix<B, A> {
  new UniqueList<B> instances;
  new Map<A, Entry> index;
  
  swappable int instanceToNumber(B b) { ret instances.addOrGetIndex(b); }
  swappable B numberToInstance(int i) { ret instances.get(i); }
  swappable Set<A> extractElements(B instance) { fail("implement me"); }
  
  bool doneAdding;

  // each word can be represented as either an int array, a bit set or both
  // for now, the int array is always there
  sclass Entry {
    new Set<Int> intSet; // while building the index
    int[] intArray;
    BitSet bitSet;
    
    BitSet bitSet() {
      if (bitSet == null)
        bitSet = intArrayToBitSet(intArray);
      ret bitSet;
    }
    
    int count() { ret intArray.length; }
  }
  
  *() {}

  void add(B instance, Cl<A> elements default extractElements(instance)) {
    assertFalse(doneAdding);
    int idx = instanceToNumber(instance);
    fOr (A word : elements) addMatrixDot(idx, word);
  }
  
  void addMatrixDot(int idx, A 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() {
    if (doneAdding) ret;
    set doneAdding;
    for (Entry e : values(index)) {
      e.intArray = sortIntArrayInPlace(toIntArray(e.intSet));
      e.intSet = null;
    }
  }
  
  L<B> instancesContainingElement(A element) {
    ret instanceListFromIntArray(instancesContainingElement_intArray(element));
  }
  
  int[] instancesContainingElement_intArray(A element) {
    doneAdding();
    Entry e = index.get(element);
    ret e == null ? null : e.intArray;
  }
  
  L<B> instanceListFromIntArray(int[] array) {
    ret array == null ? null : listFromFunction(array.length, i -> numberToInstance(array[i]));
  }
  
  // may return null (=empty list)
  L<B> instancesContainingAllElements(Cl<A> elements) {
    ret instanceListFromIntArray(instancesContainingAllElements_intArray(elements));
  }
  
  // may return null (=empty list). also returns null for 0 elements
  int[] instancesContainingAllElements_intArray(Cl<A> elements) {
    doneAdding();
    int n = l(elements);
    if (n == 0) null;
    if (n == 1) ret instancesContainingElement_intArray(first(elements));

    // get entries for elements, exit when an element is unknown
    Entry[] entries = new[n];
    Iterator<A> itElements = iterator(elements);
    for i to n: {
      Entry e = index.get(itElements.next());
      if (e == null) null;
      entries[i] = e;
    }
    
    // go through elements again, AND-combine all bit sets
    BitSet bs = cloneBitSet(entries[0].bitSet());
    for (int i = 1; i < n; i++)
      bs.and(entries[i].bitSet());

    ret bitSetToIntArray(bs);
  }
  
  L<B> instancesThatAreSuperSetsOf(B instance, O... _) {
    ret instancesContainingAllElements(extractElements(instance));
  }
  
  NavigableSet<S> elements() { ret (NavigableSet) keys(index); }
  
  int numElements() { ret l(index); }
}

Began life as a copy of #1029068