!7

static Map<S, Set<S>> theSet;
static new LinkedHashSet<Updatable> allObjects;
static long changes;
static new MultiMap<S, Pair<S>> groupingsByA;
static new MultiMap<S> subClasses;

static S groupings = [[
  <preposition> + <noun> = <adverbial_phrase>
  <determiner> + <noun> = <noun>
  <adverb> + <verb_phrase> = <verb_phrase>
  <verb> = <verb_phrase>
  <verb> + <noun> = <verb_phrase>
  <noun> + <verb_phrase> = <sentence>
  <adverbial_phrase> + <sentence> = <sentence>
]];

sclass Updatable {
  void update {}
  
  void setField(S field, O value) {
    if (eq(get(this, field), value)) ret;
    set(this, field, value);
    change();
  }
}

sclass Expectation {
  S ifClass;
  Runnable action;
  
  *() {}
  *(S *ifClass, Runnable *action) {}
}

sclass Word extends Updatable {
  S text; // or null if unknown
  new LinkedHashSet<Word> prev;
  new LinkedHashSet<Word> next;
  L<Word> constituents; // if group
  new L<Expectation> expectations;
  new L<Expectation> fulfilledExpectations;
  new TreeSet<S> classes;
  int classesConvertedToTraits;
  new LinkedHashSet<Word> groups; // I am part of
  new L<Trait> traits;
  
  void update {
    // Add direct word classes
    if (text != null)
      for (S c : reverseLookupInMapToSets(theSet, text))
        addClass(c);
    
    // Make text for group  
    if (isGroup() && text == null) {
      L<S> l = collect(constituents, 'text);
      if (!anyNull(l)) setField(text := joinWithSpace(l));
    }
    
    // Process expectations
    for (Expectation e : cloneList(expectations)) {
      //print("Checking expected class " + e.ifClass);
      if (classes.contains(e.ifClass)) {
        moveElementFromCollectionToCollection(e, expectations, fulfilledExpectations);
        change();
        callF(e.action);
      }
    }
    
    if (l(classes) > classesConvertedToTraits) {
      for (fS c : dropFirst(classesConvertedToTraits, classes))
        addTraitsForClass(c);
      classesConvertedToTraits = l(classes);
    }
    
    for (Trait t : iterateListConcurrently(traits))
      t.update();
  }
  
  bool isGroup() { ret constituents != null; }
  
  bool addClass(S c) {
    if (!classes.add(c)) false;
    change();
    long n;
    do {
      n = changes;
      // optimizable
      for (S d : iterateListConcurrently(asList(classes)))
        for (S e : subClasses.get(d))
          if (classes.add(e)) change();
    } while (changes != n);
    true;
  }
  
  void addExpectation(Expectation e) {
    //print("addExpectation " + e);
    expectations.add(e);
    change();
  }
  
  void addTraitsForClass(S c) {
    for (PairS p : groupingsByA.get(c))
      addTrait(LinkWithTo(p.a, p.b));
  }
  
  void addTrait(Trait t) {
    set(t, w := this);
    traits.add(t);
  }
}

static Word makeGroup(Word a, Word b, S newClass) {
  //print("makeGroup " + a.text + " / " + b.text);
  L<Word> list = ll(a, b);
  
  // look for existing group
  for (Word g : a.groups)
    if (eq(g.constituents, list)) {
      if (g.addClass(newClass))
        print("Added class " + newClass + " to existing group: " + a.text + " + " + b.text);
      ret g;
    }
      
  // new group
  print("Making group " + newClass + " " + a.text + " + " + b.text);
  print("  prev=" + sfu(collect(a.prev, 'text)));
  print("  next=" + sfu(collect(b.next, 'text)));
  new Word g;
  allObjects.add(g);
  g.addClass(newClass);
  g.constituents = list;
  for (Word w : list)
    w.groups.add(g);
  g.prev.addAll(a.prev);
  g.next.addAll(b.next);
  for (Word prev : a.prev) prev.next.add(g);
  for (Word next : b.next) next.prev.add(g);
  ret g;
}

sclass Trait extends Updatable {
  Word w;
}

sclass LinkWithTo extends Trait {
  S linkWith, linkTo; // classes
  int expectationsSentToNext;
  
  *() {}
  *(S *linkWith, S *linkTo) {}
  
  void update {
    if (l(w.next) > expectationsSentToNext) {
      for (final Word next : dropFirst(expectationsSentToNext, w.next))
        next.addExpectation(Expectation(linkWith, r {
          makeGroup(w, next, linkTo)
        }));
      expectationsSentToNext = l(w.next);
    }
  }
}

p-exp {
  fS sentence = "In the movies Dracula always wears a cape";
  L<S> rawWords = printStruct(words(sentence));
  
  theSet = ai_englishWordCategoriesWithElements();
  parseGroupings();
  
  new L<Word> words;
  for (S w : rawWords)
    words.add(nu(Word, text := w));
  for (int i = 0; i < l(words)-1; i++)
    linkWords(words.get(i), words.get(i+1));
  //printStruct(first(words));
  
  addAll(allObjects, words);
  long lastChanges;
  do {
    lastChanges = changes;
    print(n2(changes, "change"));
    for (Updatable w : cloneList(allObjects))
      w.update();
  } while (lastChanges != changes);
  
  //for (Word w : words) printStruct(cloneForPrinting(w));
  for (Word w : words) print("  " + textAndClasses(w));
  print();
    
  L<Word> groups = [Word w : instancesOf(Word, allObjects) | w.constituents != null];
  print();
  print(n2(groups, "group"));
  for (Word g : groups) {
    print("Group: " + textAndClasses(g));
    print("  " + grouped(g));
  }
    
  assertNempty([Word g : groups | eq(g.text, sentence) && g.classes.contains("<sentence>")]);
  print("OK");
}

sS textAndClasses(Word w) {
  ret w.text + " (" + joinWithComma(w.classes) + ")";
}

svoid linkWords(Word a, Word b) {
  a.next.add(b);
  b.prev.add(a);
}

static O cloneForPrinting(Word w) {
  ret cloneWithoutFields(w, 'prev, 'next, 'constituents);
}

svoid change() { ++changes; }

svoid parseGroupings() {
  for (S s : tlft(groupings)) {
    L<S> tok = javaTokWithAngleBracketsC(s);
    if (l(tok) == 5)
      groupingsByA.put(tok.get(0), pair(tok.get(2), tok.get(4)));
    else if (l(tok) == 3)
      subClasses.put(tok.get(0), tok.get(2));
  }
}

sS grouped(Word g) {
  if (g.constituents == null) ret g.text;
  new L<S> l;
  for (Word w : g.constituents)
    l.add(curlyBraceIfMultipleTokens(grouped(w)));
  ret joinWithSpace(l);
}

Began life as a copy of #1017342