hTree method

Map<String, dynamic> hTree(List<int> d, int mb)

Implementation

Map<String,dynamic> hTree(List<int> d, int mb) {
    // Need extra info to make a tree
    List<Map<String,dynamic>> t = [];
    for (int i = 0; i < d.length; ++i) {
      if (d[i] != 0){
        t.add({ 's': i, 'f': d[i] });
      }
    }
    int s = t.length;
    var t2 = t.removeLast();//.slice();
    if (s == 0){
      return { 't': et, 'l': 0 };
    }
    if (s == 1) {
      u8 v = u8(t[0]['s'] + 1);
      v[t[0]['s']] = 1;
      return { 't': v, 'l': 1 };
    }
    t.sort((a, b) { return a['f'] - b['f']; });
    // after i2 reaches last ind, will be stopped
    // freq must be greater than largest possible number of symbols
    t.add({ 's': -1, 'f': 25001 });
    var l = t[0], r = t[1];
    int i0 = 0, i1 = 1, i2 = 2;
    t[0] = { 's': -1, 'f': l['f'] + r['f'], 'l': l, 'r': r };
    // efficient algorithm from UZIP.js
    // i0 is lookbehind, i2 is lookahead - after processing two low-freq
    // symbols that combined have high freq, will start processing i2 (high-freq,
    // non-composite) symbols instead
    // see https://reddit.com/r/photopea/comments/ikekht/uzipjs_questions/
    while (i1 != s - 1) {
      l = t[t[i0]['f'] < t[i2]['f'] ? i0++ : i2++];
      r = t[i0 != i1 && t[i0]['f'] < t[i2]['f'] ? i0++ : i2++];
      t[i1++] = { 's': -1, 'f': l['f'] + r['f'], 'l': l, 'r': r };
    }
    int maxSym = t2[0]['s'];
    for (int i = 1; i < s; ++i) {
      if (t2[i]['s'] > maxSym){
        maxSym = t2[i]['s'];
      }
    }
    // code lengths
    u16 tr = u16(maxSym + 1);
    // max bits in tree
    int mbt = ln(t[i1 - 1], tr, 0);
    if (mbt > mb) {
      // more algorithms from UZIP.js
      // TODO: find out how this code works (debt)
      //  ind    debt
      int i = 0, dt = 0;
      //    left            cost
      int lft = mbt - mb;
      int cst = 1 << lft;
      //t2.sort((a, b) { return tr[b['s']] - tr[a['s']] ?? a['f'] - b['f']; });
      //{
        List<MapEntry<String,dynamic>> sortedEntries = t2.entries.toList();
        sortedEntries.sort((a, b) { final i = tr[b.value['s']] - tr[a.value['s']]; return i != 0 ?i:a.value['f'] - b.value['f']; });
        t2 = Map.fromEntries(sortedEntries);
      //}
      for (; i < s; ++i) {
        int i2_1 = t2[i]['s'];
        if (tr[i2_1] > mb) {
          dt += cst - (1 << (mbt - tr[i2_1]));
          tr[i2_1] = mb;
        }
        else{
          break;
        }
      }
      dt >>= lft;
      while (dt > 0) {
        int i2_2 = t2[i]['s'];
        if (tr[i2_2] < mb){
          dt -= 1 << (mb - tr[i2_2]++ - 1);
        }
        else{
          ++i;
        }
      }
    for (; i >= 0 && dt != 0; --i) {
      int i2_3 = t2[i]['s'];
      if (tr[i2_3] == mb) {
        --tr[i2_3];
        ++dt;
      }
    }
    mbt = mb;
  }
  return { 't': u8.fromList(tr), 'l': mbt };
}