Posts tagged: technical

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)

Rise of the Video Game Zinesters

I’ve been reading Anna Anthropy‘s Rise of the Videogame Zinesters
and I just came across what (to me) may be the most important message in the entire book.

Perfection isn't a useful goal; if anything, it keeps amateurs
from getting their feet wet and authors from finishing their works.
- Anna Anthropy. Rise of the Video Game Zinesters. Page 125. 2012 ed.

I cannot agree more. When I met my wife and she was getting to know me, I told her “I make games”. That wasn’t entirely true. What I should have said was “I try to make games” because my struggle for perfection constantly got in the way.

I thought there was one right way to make games, and because I didn’t know the way that I should not even try. I abandoned every game I tried to make.

It wasn’t until the last few years that I finally understood that there is no one right way to make games. That the best way to make games is just do it. Give up on perfection. Expect to make mistakes. Use bubblegum and duct tape to piece your game together and cover it up in attractive gift wrap.

People don’t see your engine (the source of my anxiety, the fear that my coding abilities would be criticised). They only see your game. Don’t try to be perfect, just make something to the best of your ability. You’ll surprise yourself.

SpaceFight! trigonometry and limiting mobility

One of the “features” I wanted to include in SpaceFight! is a range of mobility for the player pawns. The units of measurement for the distance is arbitrary, and the screenshot below reflects 200 “units”.

That green circle surrounding the highlighted pawn shows the player the possible area they can place that pawn. The tricky part here was limiting the “potential new location” to never exceed the radius of that circle. Perhaps there was an easier way to do this, but I solved it with a little high school trigonometry.

Calculate distance

a^2 + b^2 = c^2

or

square root of (a^2 + b^2) = c

In this case, a = x1 – x2, and b = y1 – y2 (using cartesian coordinates)

dist = Math.sqrt(
Math.pow((getX() - getMouseX()), 2)
+
Math.pow((getY() - getMouseY()), 2)
);

If that value c exceeds the pawn’s range then find the coordinate of the intersect between the circle and the line drawn between the pawn and the mouse cursor.

Calculate angle

Now, to force the new location to be where the lines intersect we only need two things. First, the distance which is just the pawn’s range of mobility. Second, the angle between the pawn and the mouse cursor.

angleRadian = Math.atan2(
(getMouseY() - getY()) ,
(getMouseX() - getX())
);

Set the location

Now that we have the angle we can calculate the new location.

pX = getX() + range * Math.cos(angleRadian);
pY = getY() + range * Math.sin(angleRadian);
setNewLocation(pX, pY);

Now if the mouse is located outside the pawn’s range then the new location will always be somewhere along the edge of the pawn’s range.

FizzBuzz and a false coin

I just had my co-worker visit me at home. We all work remotely so we don’t see each other on a daily basis, but he was passing through town. He brought up an interesting topic; a programming “test” called “FizzBuzz”.

The rules: Print out all values between 1 and 100. When a number is divisible by 3 print “FIZZ” and when divisible by 5 print “BUZZ”. When the number is divisible by both, print “FIZZ BUZZ”.

My simple solution to it (a Perl script) is as follows:

for ($i = 1; $i <= 100; $i++) {
 print "$i:\t";
 if ($i%3==0) { print "FIZZ "; }
 if ($i%5==0) { print "BUZZ "; }
 print "\n";
}

This meets the criteria, though I don’t check if a number is specifically divisible by both within a condition.

This brought back a memory of an “Algorithm Analysis” exam from University. I call it “The False Coin” problem, though it probably has many names.

You have a pile of coins. All of the coins are equal, except one, which is lighter than the other coins. This is the false coin. You also have a scale which allows you to compare two weights against each other. Using the scale, what is the most efficient way to find the false coin?

The other students insisted you split the pile of coins into two equal piles, weigh the two against each other and find the lighter pile, then split the lighter pile into two piles, and so on.

Close. But wrong. There is a better way and it involves splitting the first pile into three equal piles. Compare two piles, identify which of the three is the lightest pile and split that into three more equal piles, and so on. With every weighing you get rid of 66% of the remaining coins, compared to only 50% when splitting the piles by half.

So keep that in mind before your next programming interview.

Beer Bottle Rocket Man

It’s done. I made the deadline (after two full days of working on it).

BBRM_Teaser01

Next time I’ve got a full month to work on the game, I’ll manage my time better. No more leaving it until the last few days.

Here is the forum post announcing the details.

Pretend this is an old Nintendo game and the story
and instructions are in the booklet but the game doesn't
make sense without the booklet.

This is the booklet: The evil doctor wants a beer, so he
sent you, his robot, down into the cellar to get it.
It's easy enough for you to walk down stairs, but your
legs are too short to climb back up. Being a heavy robot
with short legs, you can't jump very high. 

How are you going to get back up to the doctor to give
him his beer?

Note: It is possible to finish the game with a beer for each of
you and the doctor.

Staypressed theme by Themocracy