[mkgmap-dev] [PATCH 09/14] Switch to using a binary search instead of a map for finding matching regions.

From Jeffrey C. Ollie jeff at ocjtech.us on Thu Sep 9 21:12:09 BST 2010

From: Scott Crosby <scrosby at cs.rice.edu>

---
 src/uk/me/parabola/splitter/SplitProcessor.java |   28 ++++++++++++++++++-----
 1 files changed, 22 insertions(+), 6 deletions(-)

diff --git a/src/uk/me/parabola/splitter/SplitProcessor.java b/src/uk/me/parabola/splitter/SplitProcessor.java
index 97b014e..4f7220e 100644
--- a/src/uk/me/parabola/splitter/SplitProcessor.java
+++ b/src/uk/me/parabola/splitter/SplitProcessor.java
@@ -46,10 +46,13 @@ class SplitProcessor implements MapProcessor {
 	
 	private final int maxThreads;
 
-	TreeMap<Integer,ArrayList<OSMWriter>> writermap = new TreeMap<Integer,ArrayList<OSMWriter>>();
+	int lats[];
+	ArrayList<OSMWriter> writersets[];
+	
 	HashMap<OSMWriter,Integer> writerToID = new HashMap<OSMWriter,Integer>();
 	
 	void makeWriterMap() {
+		TreeMap<Integer,ArrayList<OSMWriter>> writermap = new TreeMap<Integer,ArrayList<OSMWriter>>();
 		for (int i = 0 ; i < writers.length ; i++) {
 			writerToID.put(writers[i],i);
 		}
@@ -58,6 +61,10 @@ class SplitProcessor implements MapProcessor {
 			writermap.put(w.getExtendedBounds().getMinLat(),new ArrayList<OSMWriter>());
 			writermap.put(w.getExtendedBounds().getMaxLat(),new ArrayList<OSMWriter>());
 		}
+		// Sentinel keys
+		writermap.put(Integer.MIN_VALUE,new ArrayList<OSMWriter>());
+		writermap.put(Integer.MAX_VALUE,new ArrayList<OSMWriter>());
+
 		for (OSMWriter w: writers) {
 			int minlat = w.getExtendedBounds().getMinLat();
 			int maxlat = w.getExtendedBounds().getMaxLat();
@@ -65,7 +72,14 @@ class SplitProcessor implements MapProcessor {
 				writermap.get(i).add(w);
 			}
 		}
-
+		lats = new int[writermap.size()];
+		writersets = new ArrayList[writermap.size()];
+		int i = 0;
+		for (Entry<Integer, ArrayList<OSMWriter>> e : writermap.entrySet()) {
+			lats[i] =  e.getKey();
+			writersets[i] = e.getValue();
+			i++;
+		}
 	}
 
 	SplitProcessor(OSMWriter[] writers, int maxThreads) {
@@ -226,10 +240,12 @@ class SplitProcessor implements MapProcessor {
 	}
 
 	private void writeNode(Node currentNode) throws IOException {
-		Entry<Integer, ArrayList<OSMWriter>> entry = writermap.floorEntry(currentNode.getMapLat());
-		if (entry == null)
-			return;
-		for (OSMWriter w : entry.getValue()) {
+		int index = Arrays.binarySearch(lats, currentNode.getMapLat());
+		if (index < 0)
+			index = -index-1;
+
+		//System.out.println("Send to "+entry.getValue().size());
+		for (OSMWriter w : writersets[index]) {
 			int n = writerToID.get(w);
 			boolean found = w.nodeBelongsToThisArea(currentNode); 
 			if (found) {
-- 
1.7.2.3

---

• Previous message: [mkgmap-dev] [PATCH 08/14] Be more efficient with handling ways.
• Next message: [mkgmap-dev] [PATCH 10/14] Switch to using an ArrayList instead of hash table for Tags.
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

---

More information about the mkgmap-dev mailing list