Posts tagged: list

Remove Items While Iterating List In Java

Edit: Some (better) alternatives here and here

Edit 2: @kattehus was awesome enough to compare the three methods. 1) my graveyard method, 2) Joe’s iterator method, and 3) Kattehus’ standard for-loop method. Go with the standard for-loop. I’ll leave the rest of my post so others can see one method of doing so, though it’s not the best method.

1
2
3
4
5
6
for (int i = items.size()-1; i >= 0; i--) {
	SomeItem item = items.get(i);
	if (item.value < 25) {
		items.remove(i);
	}
}

End of edit 2.

So you have a list of something and you want to remove some of those things from the list. So you loop through them, check to see if the item should be removed, and you remove it from the list.

*CRASH*

What happened? You likely ended up with the following stack trace.

java.util.ConcurrentModificationException
 at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:819)
 at java.util.ArrayList$Itr.next(ArrayList.java:791)
 at RemoveFromListExample.thisWillNotWork(RemoveFromListExample.java:36)
 at RemoveFromListExample.<init>(RemoveFromListExample.java:13)
 at RemoveFromListExample.main(RemoveFromListExample.java:79)

Oops. So what went wrong? As far as Java sees it, it was happily looping through the list of items, knowing exactly how many items were in the list, when suddenly the list size changed. Java didn’t like that and so it put an end to the loop.

But you still need to remove those things from that list. What do you do? Build a second list!

I like to call the second list the “graveyard”. Basically, loop through the list and when you find something you want removed from the list just add it to the graveyard. Outside the loop just tell the first list to remove all items found in the second list. Like this:

1
2
3
4
5
6
7
8
9
public void thisOneWorks(List<SomeItem> items) {
	List<SomeItem> graveyard = new ArrayList<SomeItem>();
	for (SomeItem item : items) {
		if (item.value < discardBelowValue) {
			graveyard.add(item);
		}
	}
	items.removeAll(graveyard);
}

Below is the full source code for an example of what does and does not work, followed by the output of the program. Give it a try to see for yourself. It’s not limited to ArrayList, either. It also works with LinkedList and I presume whatever else you find in Collections.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
import java.util.ArrayList;
import java.util.List;
 
public class RemoveFromListExample {
 
	protected int discardBelowValue;
 
	public RemoveFromListExample(int discardBelowValue) {
 
		this.discardBelowValue = discardBelowValue;
 
		try {
			thisWillNotWork(getList());
		} catch (Exception e) {
			e.printStackTrace();
		}
 
		thisOneWorks(getList());
	}
 
	public List<SomeItem> getList() {
		List<SomeItem> items = new ArrayList<SomeItem>();
 
		items.add(new SomeItem("Penny", 1));
		items.add(new SomeItem("Nickle", 5));
		items.add(new SomeItem("Dime", 10));
		items.add(new SomeItem("Quarter", 25));
		items.add(new SomeItem("Dollar", 100));
 
		return items;
	}
 
	public void thisWillNotWork(List<SomeItem> items) {
		printList(items);
		System.out.println("Try to delete while iterating...");
		for (SomeItem item : items) {
			if (item.value < discardBelowValue) {
				items.remove(item);
			}
		}
		printList(items);
	}
 
	public void thisOneWorks(List<SomeItem> items) {
		printList(items);
		System.out.println("Delete after iterating...");
		List<SomeItem> graveyard = new ArrayList<SomeItem>();
		for (SomeItem item : items) {
			if (item.value < discardBelowValue) {
				graveyard.add(item);
			}
		}
		items.removeAll(graveyard);
		printList(items);
	}
 
	public void printList(List<SomeItem> items) {
 
		System.out.println("Items in list");
		for (SomeItem item : items) {
			System.out.println(" * " + item.name + " (" + item.value + ")");
		}
	}
 
	private class SomeItem {
 
		protected String name;
		protected int value;
 
		public SomeItem(String name, int value) {
			this.name = name;
			this.value = value;
		}
 
	}
 
	public static void main(String[] args) {
		int discardBelowValue = 25;
		System.out.println("Discard below " + discardBelowValue + " cents");
		new RemoveFromListExample(discardBelowValue);
	}
 
}

Output:

Discard below 25 cents
Items in list
 * Penny (1)
 * Nickle (5)
 * Dime (10)
 * Quarter (25)
 * Dollar (100)
Try to delete while iterating...
java.util.ConcurrentModificationException
	at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:819)
	at java.util.ArrayList$Itr.next(ArrayList.java:791)
	at RemoveFromListExample.thisWillNotWork(RemoveFromListExample.java:36)
	at RemoveFromListExample.(RemoveFromListExample.java:13)
	at RemoveFromListExample.main(RemoveFromListExample.java:79)
Items in list
 * Penny (1)
 * Nickle (5)
 * Dime (10)
 * Quarter (25)
 * Dollar (100)
Delete after iterating...
Items in list
 * Quarter (25)
 * Dollar (100)

Points, Comparators, and Thread

Trying hard to figure out an efficient way to do the following:

Limiting Accessible Area

And so far, only coming up with something like this:

Remaining thread from points

Imagine a thread of fixed length N stuck to a location on your desk. Now picture a coffee cup in the path of that thread. Now fill in only the area that the thread can reach.

I’ve tried to work it out on a whiteboard but that was only getting me so far with the subject. Now I’ve got a hunch that if I iterate (and recurse) the points within the line-of-sight from the closest to furthest points from the player that I can calculate the accessible region based on the player’s position, and how far the player can move (the length of the thread).

That brings me to Comparators. In PHP there’s a handy function called usort. It takes an array for the first argument, and the name of a function as the second argument. The function as a second argument is one usually written by you, the developer, to tell usort how to compare two elements in the array.

In Java you can accomplish usort via the Comparator interface which usually works out to something like the following:

int compare(a, b) {
	if (a == b) return 0;
	return (a < b) ? -1 : 1;
}

In this case I’d compare Point objects and sort them from closest to most distant locations from the player. For reference, this page was informative enough to show how to create and use your own Comparator.

Staypressed theme by Themocracy