Fix for TODO in OpenStreetMapAsyncTileProvider

[GoogleCodeExporter]

Cleaned up OpenStreetMapAsyncTileProvider to do the TODO.  Specifically:

 - Changed pending map to pending TreeSet and Sorting on PendingEntry
 - Synchronizing on pending set to prevent concurrent modification exception.  I realize this was breaking the loop to ensure the next tile loaded was the last added...but I think using the sorted set and not iterating over the entire pending map will make this better.

OpenStreetMapAsyncTileProviderTest passes.

Original issue reported on code.google.com by yelirk...@gmail.com on 18 Jul 2010 at 4:27

Attachments:

• osm_async_tile_provider_cleanup.patch

[GoogleCodeExporter]

Ooops!  Wrong patch.  This one should be correct.

Original comment by yelirk...@gmail.com on 18 Jul 2010 at 5:01

Attachments:

• osm_async_tile_provider_cleanup.patch

[GoogleCodeExporter]

Hi
Bear with me as I'm not so familiar with the osmdroid code yet.
Can you explain what you mean by "I realize this was breaking the loop to 
ensure the next tile loaded was the last added"?

In your patch:
+           PendingEntry ent = new PendingEntry(aTile);
+           mPending.remove(ent);
+           mPending.add(ent);
What's the logics behind doing mPending.remove(ent)? Could two entries ever 
have the same System.currentTimeMillis()?

Original comment by andpet@gmail.com on 18 Jul 2010 at 10:00

• Changed state: Accepted

[GoogleCodeExporter]

Basically, the TileLoader.nextTile() method used to iterate over all of the 
entries in mPending until it reached the tail.  I believe it used 
ConcurrentModificationException as a signal to restart the iteration as this 
would have been thrown when an entry was added to mPending.  The patch I 
submitted should remove the need for the iteration (thus "do the todo") and 
remove the need to use ConcurrentModificationException as a signal.

The remove() followed by the add() is necessary because we want to ensure that 
the most recent tile requested is the next tile loaded, even if the tile has 
already been requested.  If the tile was previously requested and is in the 
mPending set, it should be moved to the top of the set.  To achieve this 
behavior, when PendingEntries refer to the same (.equal()) tiles, they are 
determined equal even with different add timestamps.  So the remove() will 
remove the existing entry and the add() ensures its at the head.

I apologize if I've misinterpreted the code or its intent as I am new to the 
codebase as well.

Original comment by yelirk...@gmail.com on 19 Jul 2010 at 4:35

[GoogleCodeExporter]

Thanks for your explanation. Using an exception as a control signal sounds like 
a bad thing so your patch seems much better.

  "To achieve this behavior, when PendingEntries refer to the same (.equal()) tiles, they are determined equal even with different add timestamps."
Don't you need a custom equals() in PendingEntry for this?

Original comment by andpet@gmail.com on 19 Jul 2010 at 8:28

[GoogleCodeExporter]

Because the Set uses .compareTo() for Comparable items, I used that instead.  
See the first two lines of PendingEntry.compareTo for details.

Original comment by yelirk...@gmail.com on 19 Jul 2010 at 4:35

[GoogleCodeExporter]

Committed in r292

Original comment by andpet@gmail.com on 20 Jul 2010 at 9:01

• Changed state: Fixed

[GoogleCodeExporter]

The code that you changed was introduced as a result of issue 27.

I haven't compared the performance yet, but using a LinkedHashMap had a great 
performance improvement.

Of course catching a ConcurrentModificationException isn't great design, but it 
seemed like a reasonable compromise.

You've also changed a catch Throwable into a catch Exception. I haven't checked 
this specific case, but in general the reason for catching Throwable is because 
OutOfMemoryError is not an Exception.

So although the code is tidier, performance is more important. So you should 
check that the remove/add and the synchronization doesn't add too much 
performance overhead.

Just to be clear, I'm not criticising this change - I'm glad that more people 
are looking at the code.  I'm just trying to point out the history to anyone 
who's newer than me.

Original comment by neilboyd on 21 Jul 2010 at 8:41

[GoogleCodeExporter]

I'm certainly newer than neilboyd. The code seemed reasonable enough to me but 
if you have a better idea, of course I don't mind.

Original comment by andpet@gmail.com on 21 Jul 2010 at 8:52

[GoogleCodeExporter]

Neil,

I understand your concerns.  I can try to put together some tests which will 
determine if the synch decreases performance over the previous code.

I did find, however, that there is a bug in my code.  The remove/add will not 
work properly when more than one pending entry exist between two pending 
entries referencing the same tile.  Basically, the sorted set will not remove 
the existing pending entry as I thought because the set is obviously not 
comparing each item for insert/removal.  Sorry...I don't know what I was 
thinking.

Anyway...I will attach another patch shortly.  Unfortunately it will most 
likely require maintaining multiple collections of pending entries :(.

Original comment by yelirk...@gmail.com on 21 Jul 2010 at 11:11