Skip to content

Instantly share code, notes, and snippets.

@Mastersam07
Last active October 12, 2023 09:09
Show Gist options
  • Select an option

  • Save Mastersam07/71ef771809af86e8e71908a6e1cf7527 to your computer and use it in GitHub Desktop.

Select an option

Save Mastersam07/71ef771809af86e8e71908a6e1cf7527 to your computer and use it in GitHub Desktop.
Some operation on list
extension EfficientList<T> on List<T> {
List<List<T>> splitBy(Iterable<T> separator) {
List<List<T>> result = [];
List<T> current = [];
int i = 0;
while (i < length) {
bool isMatch = true;
for (int j = 0; j < separator.length; j++) {
if (i + j >= length || this[i + j] != separator.elementAt(j)) {
isMatch = false;
break;
}
}
if (isMatch) {
result.add(current);
current = [];
i += separator.length;
} else {
current.add(this[i]);
i++;
}
}
if (current.isNotEmpty) result.add(current);
return result;
}
int firstIndexOf(Iterable<T> sequence) {
for (int i = 0; i <= length - sequence.length; i++) {
bool isMatch = true;
for (int j = 0; j < sequence.length; j++) {
if (this[i + j] != sequence.elementAt(j)) {
isMatch = false;
break;
}
}
if (isMatch) return i;
}
return -1;
}
void removeEverySequence(Iterable<T> sequence) {
List<T> result = [];
int i = 0;
while (i < length) {
bool isMatch = true;
for (int j = 0; j < sequence.length; j++) {
if (i + j >= length || this[i + j] != sequence.elementAt(j)) {
isMatch = false;
break;
}
}
if (isMatch) {
i += sequence.length;
} else {
result.add(this[i]);
i++;
}
}
clear();
addAll(result);
}
bool containsSequence(Iterable<T> sequence) {
return this.firstIndexOf(sequence) != -1;
}
}
List<int> generateRandomBytes(int length) {
Random random = Random();
return List<int>.generate(length, (index) => random.nextInt(256));
}
void main() {
List<int> list = generateRandomBytes(25776);
print(list.splitBy([2, 3])); // Tweak per usage
print(list.firstIndexOf([2, 3])); // Tweak per usage
list.removeEverySequence([2, 3]); // Tweak per usage
print(list); // Tweak per usage
print(list.containsSequence([2, 3])); // Tweak per usage
}
@Mastersam07
Copy link
Author

Using KMP algorithm for the firstIndexOf and containsSequence methods.

extension EfficientList<T> on List<T> {
  List<List<T>> splitBy(Iterable<T> separator) {
    List<List<T>> result = [];
    List<T> current = [];
    int i = 0;
    while (i < length) {
      bool isMatch = true;
      for (int j = 0; j < separator.length; j++) {
        if (i + j >= length || this[i + j] != separator.elementAt(j)) {
          isMatch = false;
          break;
        }
      }
      if (isMatch) {
        result.add(current);
        current = [];
        i += separator.length;
      } else {
        current.add(this[i]);
        i++;
      }
    }
    if (current.isNotEmpty) result.add(current);
    return result;
  }

  void removeEverySequence(Iterable<T> sequence) {
  List<T> result = [];
  int i = 0;
  while (i < length) {
    bool isMatch = true;
    for (int j = 0; j < sequence.length; j++) {
      if (i + j >= length || this[i + j] != sequence.elementAt(j)) {
        isMatch = false;
        break;
      }
    }
    if (isMatch) {
      i += sequence.length;
    } else {
      result.add(this[i]);
      i++;
    }
  }
  clear();
  addAll(result);
}

List<int> _computeTemporaryArray(Iterable<T> sequence) {
    List<int> lps = List.filled(sequence.length, 0);
    int index = 0;
    for (int i = 1; i < sequence.length;) {
      if (sequence.elementAt(i) == sequence.elementAt(index)) {
        lps[i] = index + 1;
        index++;
        i++;
      } else {
        if (index != 0) {
          index = lps[index - 1];
        } else {
          lps[i] = 0;
          i++;
        }
      }
    }
    return lps;
  }

  int firstIndexOf(Iterable<T> sequence) {
    if (sequence.isEmpty) return -1;

    List<int> lps = _computeTemporaryArray(sequence);
    int i = 0;
    int j = 0;
    while (i < length && j < sequence.length) {
      if (this[i] == sequence.elementAt(j)) {
        i++;
        j++;
      }
      if (j == sequence.length) {
        return i - j;
      } else if (i < length && this[i] != sequence.elementAt(j)) {
        if (j != 0) {
          j = lps[j - 1];
        } else {
          i++;
        }
      }
    }
    return -1;
  }

  bool containsSequence(Iterable<T> sequence) {
    return this.firstIndexOf(sequence) != -1;
  }
}

void main() {
  List<int> list = [1, 2, 3, 4, 5, 2, 3, 6, 7, 2, 3];
  print(list.splitBy([2, 3])); // [[1], [4, 5], [6, 7], []]
  print(list.firstIndexOf([2, 3])); // 1
  list.removeEverySequence([2, 3]);
  print(list); // [1, 4, 5, 6, 7]
  print(list.containsSequence([2, 3])); // false
}

@folaoluwafemi
Copy link

folaoluwafemi commented Oct 12, 2023

here is my implementation of the splitting list

extension MyListExtension<T> on List<T> {
  /// Assuming sublit is a small list, this is O(log n)
  ///
  /// If sublist is a large list, this is O(n log n)
  List<List<T>> splitBy(List<T> sublist) {
    final List<T> remainingItems = copy;
    final List<List<T>> nextList = [];

    while (remainingItems.isNotEmpty) {
      final int indexOfFirst = remainingItems.indexOf(sublist.first);
      if (indexOfFirst == -1) {
        nextList.add(remainingItems);
        break;
      }

      bool isMatch = sublist.first == remainingItems[indexOfFirst];

      for (int i = (indexOfFirst); i < (indexOfFirst + sublist.length); i++) {
        final int sublistIndex = i - indexOfFirst;
        isMatch = sublist[sublistIndex] == remainingItems[i];
        if (!isMatch) break;
      }

      if (isMatch) {
        if (indexOfFirst == 0) {
          remainingItems.removeRange(0, sublist.length);
          continue;
        }

        nextList.add(remainingItems.sublist(0, indexOfFirst));

        remainingItems.removeRange(0, indexOfFirst + sublist.length);
      } else {
        final int nextFirstIndex = (remainingItems.copy..removeAt(indexOfFirst))
            .indexOf(sublist.first);

        nextList.add(
          remainingItems.sublist(
            0,
            (nextFirstIndex == -1 ? null : (nextFirstIndex + 1)),
          ),
        );

        remainingItems.removeRange(
          0,
          (nextFirstIndex == -1 ? remainingItems.length : (nextFirstIndex + 1)),
        );
      }
    }
    return nextList;
  }
}

@Tolulope05
Copy link

Wowwww

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment