!7

sclass LinkedToken {
  S t;
  LinkedToken prev, next;
  LinkedToken prevIdentical, nextIdentical;
  
  *() {}
  *(S *t) {}
}

sclass Tokenization {
  LinkedToken first, last;
  new Map<S, LinkedToken> firstByContent;
  new Map<S, LinkedToken> lastByContent;
  
  bool contains(S t) {
    ret firstByContent.get(t) != null;
  }
  
  int countInstances(S t) {
    int n = 0;
    LinkedToken lt = firstByContent.get(t);
    while (lt != null) {
      ++n;
      lt = lt.nextIdentical;
    }
    ret n;
  }
}

static Tokenization makeTokenization(L<S> tokens) {
  new Tokenization tok;
  for (S t : tokens) {
    LinkedToken lt = new(t);
    lt.t = t;
    if (tok.first == null)
      tok.first = lt;
    else {
      lt.prev = tok.last;
      tok.last.next = lt;
    }
    tok.last = lt;
    lt.prevIdentical = tok.lastByContent.get(t);
    if (lt.prevIdentical == null)
      tok.firstByContent.put(t, lt);
    else {
      lt.prevIdentical.nextIdentical = lt;
    }
    tok.lastByContent.put(t, lt);
  }
  ret tok;
}

p-experiment {
  S text = "hello hello";
  L<S> tokens = javaTok(text);
  
  Tokenization tok = makeTokenization(tokens);
  
  printStruct(tok);
  
  assertVerbose(true);
  assertEquals(true, tok.contains("hello"));
  assertEquals(true, tok.contains(" "));
  assertEquals(false, tok.contains("x"));
  assertEquals(2, tok.countInstances("hello"));
  assertEquals(1, tok.countInstances(" "));
  assertEquals(0, tok.countInstances("x"));
  
  print("OK!");
}