Removing Sublist from ArrayList
For simplicity, let's say I have an ArrayList
whose indices contain exactly one single-digit integer. For instance:
6 4 5 6 0 6 3 4 1 6 1 6 0 6 8 3
I would like to filter out all occurrences of the sublist 6 0 6
, such that the new list becomes:
6 4 5 3 4 1 6 1 8 3
Is there any way of doing this? Using ListIterator
doesn't seem to work for me, because I have to consider three consecutive elements collectively and I'm honestly not sure how to do that.
Here's a skeleton of the method I have implemented:
public static void filterList(ArrayList<Integer> list) {
ListIterator<Integer> iterator = list.listIterator();
int elem;
while (iterator.hasNext()) {
// Remove any sublist of 6 0 6
}
}
Edit: Again, for simplicity, let's assume there won't be cases where we have 60606 or similar.
You can create an efficient and concise O(nm) solution by using Collections.indexOfSubList
:
public static void removeAllSubList(List<?> list, List<?> subList) {
// find first occurrence of the subList in the list, O(nm)
int i = Collections.indexOfSubList(list, subList);
// if found
if (i != -1) {
// bulk remove, O(m)
list.subList(i, i + subList.size()).clear();
// recurse with the rest of the list
removeAllSubList(list.subList(i, list.size()), subList);
}
}
Ideone Demo
[Edited - better, single pass approach]
Custom, enhanced indexOfSublist
starting the search from offset
; therefore, we don't restart from 0
each time we removed something (as we did when using Collections.indexOfSublist
see bottom of this answer).
static <T> int indexOfSublist(List<T> haystack, List<T> needle, int offset){
int toRet=-1;
int needleLen=needle.size();
if(needleLen>0) {
// it makes sense to search
int haystackLen=haystack.size();
for(;offset+needleLen<haystackLen && toRet<0; offset++) {
int compIx;
for(
compIx=0;
(
compIx<needleLen
&& false==haystack.get(offset+compIx).equals(needle.get(compIx))
);
compIx++
);
if(compIx==needleLen) { // found
toRet=offset;
}
}
}
return toRet;
}
public static void filterList(List<Integer> haystack, List<Integer> needle) {
for(
int offset=0, ixOfNeedle=indexOfSublist(haystack, needle, offset);
ixOfNeedle>=0;
ixOfNeedle=indexOfSublist(haystack, needle, offset)
) {
// found one place. We'll continue searching from here next time
offset=ixOfNeedle;
//////////////////////////////////////////
// for a better removal sequence, see the
// 4castle's answer using sublists
for(int i=needle.size(); i>0; i--) {
haystack.remove(ixOfNeedle);
}
}
}
Collections.indexOfSublist is what you are after.
public static void filterList(ArrayList<Integer> haystack, List<Integer> needle) {
for(
int ixOfNeedle=Collections.indexOfSublist(haystack, needle);
ixOfNeedle>=0;
ixOfNeedle=Collections.indexOfSublist(haystack, needle)
) {
for(int i=needle.size(); i>0; i--) {
haystack.remove(ixOfNeedle);
}
}
}