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
}
@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