!7

cprint {

  switchable S query = "world";

  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)

  transient Map<Int, L<Int>> fileOffsetMap; // for every file index, character offsets

  start-thread {

    dm_reloadOnFieldChange query();

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

    prodLengths = new Map;

    fileOffsetMap = new Map;

    for (int i = iFirstFile; i < l(productions); i++) {

      L<Int> prod = productions.get(i);

      new L<Int> l;

      int ofs = 0;

      for (int x : prod) {

        l.add(ofs);

        ofs += getProdLength(x);

      }

      fileOffsetMap.put(i, l);

    }

    // 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);

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

    print("Result", 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;

  }

  L<IntPair> reconstitute(L<Int> baseList, int i) {

    L<Int> needLeft = subList(baseList, 0, i);

    L<Int> needRight = subList(baseList, i+1);

    ret reconstitute(baseList.get(i),

      lcUncompressItems(lc, needLeft),

      lcUncompressItems(lc, needRight));

  }

  // returns list of (file index, character offset)

  L<IntPair> 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);

    new L<IntPair> out;

    search: for (IntPair p : l) {

      int iProd = p.a;

      L<Int> prod = productions.get(iProd);

      int j = p.b;

      bool isFile = iProd >= iFirstFile;

      if (isFile) {

        int iChar = fileOffsetMap.get(iProd).get(j);

        print("Reached file level: " + iProd + "/" + iChar + " with " + quote(needLeft) + "/" + quote(needRight));

        // check left & right

        if (nempty(needLeft)) fail(); // needLeft not used yet

        int iRight = j+1;

        while (nempty(needRight)) {

          if (j >= l(prod)) continue search; // need more, but have no more text

          S rest = itemStartsWith(prod.get(iRight), needRight);

          if (rest == null) continue search; // mismatch

          needRight = rest;

          ++iRight;

        }

        // result found!

        out.add(intPair(iProd, iChar));

      } else { // we're on a pair, check left & right and then go higher up

        if (j == 0) {

          S rest = itemStartsWith(prod.get(1), needRight);

          print("checking right: " + quote(lcUncompressItem(lc, prod.get(1)))

            + " => " + quote(rest));

          if (rest == null) continue;

          out.addAll(reconstitute(iProd, needLeft, rest));

        } else {

          S rest = itemEndsWith(prod.get(0), needLeft);

          print("checking left: " + quote(lcUncompressItem(lc, prod.get(0)))

            + " => " + quote(rest));

          if (rest == null) continue;

          out.addAll(reconstitute(iProd, rest, needRight));

        }

      }

    }

    ret out;

  }

  S itemStartsWith(int i, S need) {

    if (empty(need)) ret need;

    S have = lcUncompressItem(lc, i);

    int l = lCommonPrefix(have, need);

    if (l < l(need) && l < l(have)) null;

    ret substring(need, l);

  }

  S itemEndsWith(int i, S need) {

    if (empty(need)) ret need;

    S have = lcUncompressItem(lc, i);

    int l = lCommonSuffix(have, need);

    if (l < l(need) && l < l(have)) null;

    ret dropLast(need, l);

  }

}