!7

cprint {
  transient LineCompedSingle<Char> lc;
  transient LL<Int> productions;
  transient Map<Int> prodLengths; // prod index -> length of production in characters
  transient int iFirstPair, iFirstFile;
  transient Map<Char, Int> literalIndex;
  transient MultiMap<Int, IntPair> prodIndex; // keys: item looked for, value: pair(prod index, position in prod)
  
  start-thread {
    new LineCompCompressor comp;
    lc = lcString2(comp, "hello world world");
    
    // Turn pairs and file encodings into a single structure ("productions")
    productions = new L;
    productions.addAll(rep(null, l(lc.literals)));
    iFirstPair = l(productions);
    productions.addAll(intPairsToLists(lc.pairs));
    iFirstFile = l(productions);
    productions.add(lc.main);

    calcProdLengths();
    
    // build the reconstitution index
    literalIndex = indexList(lc.literals);
    prodIndex = new MultiMap;
    for iProd over productions: {
      L<Int> prod = productions.get(iProd);
      for (int i, int x : unpair iterateListWithIndex(prod)) {
        prodIndex.put(x, intPair(iProd, i));
      }
    }
    
    print(+literalIndex);
    print(+prodIndex);
    
    S query = "world";
    L<Char> queryList = characters(query);
    new L<Int> queryLiterals;
    for (Char c : queryList) {
      Int iLit = literalIndex.get(c);
      if (iLit == null) ret with print("literal not found");
      queryLiterals.add(iLit);
    }
    
    print(+queryLiterals);

    reconstitute(queryLiterals, 0);
  }

  void calcProdLengths {
    prodLengths = new Map;
    for (int i = iFirstPair; i < l(productions); i++)
      getProdLength(i);
  }

  int getProdLength(int i) {
    if (i < iFirstPair) ret 1; // literal
    Int x = prodLengths.get(i);
    if (x != null) ret x;
    prodLengths.put(i, x = intSum(lmap getProdLength(productions.get(i))));
    ret x;
  }
  
  void reconstitute(L<Int> baseList, int i) {
    L<Int> needLeft = subList(baseList, 0, i);
    L<Int> needRight = subList(baseList, i+1);
    reconstitute(baseList.get(i),
      lcUncompressItems(lc, needLeft),
      lcUncompressItems(lc, needRight));
  }
    
  void reconstitute(int item, S needLeft, S needRight) {
    print("Reconstituing " + quote(lcUncompressItem(lc, item)));
    print("  needLeft: " + quote(needLeft));
    print("  needRight: " + quote(needRight));
    L<IntPair> l = prodIndex.get(item);
    print("Found: " + l);
    for (IntPair p : l) {
      int iProd = p.a;
      L<Int> prod = productions.get(iProd);
      int j = p.b;
      bool isFile = iProd >= iFirstFile;
      if (isFile)
        print("Reached file level");
      else {
        if (j == 0) {
          S rest = itemStartsWith(prod.get(1), needRight);
          print("checking right: " + quote(lcUncompressItem(lc, prod.get(1)))
            + " => " + quote(rest));
          if (rest == null) ret;
          reconstitute(iProd, needLeft, rest);
        } else
          print("should checkleft");
      }
    }
  }

  S itemStartsWith(int i, S need) {
    /*if (empty(need)) true;
    if (i == first(need)) true;
    L<Int> prod = productions.get(i);
    if (prod == null) false;
    itemStartsWith(prod.first(*/
    ret dropPrefixOrNull(lcUncompressItem(lc, i), need);
  }
}