bwtTransform function

List<int> bwtTransform(List<int> input)

Implementation

List<int> bwtTransform(List<int> input) {
  if (input.isEmpty) return [0];
  final n = input.length;
  final rotations = List<List<int>>.generate(n, (i) => List<int>.filled(n, 0));
  for (var i = 0; i < n; i++) {
    for (var j = 0; j < n; j++) {
      rotations[i][j] = input[(i + j) % n];
    }
  }
  rotations.sort((a, b) {
    for (var i = 0; i < n; i++) {
      if (a[i] != b[i]) return a[i] - b[i];
    }
    return 0;
  });
  final out = <int>[];
  for (var r in rotations) {
    out.add(r[n - 1]);
  }
  // append primary index for inversion (index of original input rotation)
  final primary = rotations.indexWhere((r) {
    if (r.length != input.length) return false;
    for (var i = 0; i < r.length; i++) {
      if (r[i] != input[i]) return false;
    }
    return true;
  });
  out.add(primary < 0 ? 0 : primary);
  return out;
}