!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!");

}