bwtInverse function

List<int> bwtInverse(List<int> transformedWithIndex)

Implementation

List<int> bwtInverse(List<int> transformedWithIndex) {
  if (transformedWithIndex.isEmpty) return [];
  if (transformedWithIndex.length == 1) return [];
  final n = transformedWithIndex.length - 1;
  final last = transformedWithIndex.sublist(0, n);
  final primary = transformedWithIndex.last;
  final counts = <int, int>{};
  for (var c in last) {
    counts[c] = (counts[c] ?? 0) + 1;
  }
  final keys = counts.keys.toList()..sort();
  final starts = <int, int>{};
  var sum = 0;
  for (var k in keys) {
    starts[k] = sum;
    sum += counts[k]!;
  }
  final occ = <int>[];
  final seen = <int, int>{};
  for (var ch in last) {
    final s = (seen[ch] ?? 0);
    occ.add(starts[ch]! + s);
    seen[ch] = s + 1;
  }
  final res = List<int>.filled(n, 0);
  var idx = primary;
  for (var i = n - 1; i >= 0; i--) {
    res[i] = last[idx];
    idx = occ[idx];
  }
  return res;
}