Last active
October 12, 2023 09:09
-
-
Save Mastersam07/71ef771809af86e8e71908a6e1cf7527 to your computer and use it in GitHub Desktop.
Some operation on list
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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 | |
| } |
Author
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;
}
}Wowwww
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Using KMP algorithm for the
firstIndexOfandcontainsSequencemethods.