From 7bba7989909c9137561d9e330abcfadbf5212e44 Mon Sep 17 00:00:00 2001
From: Tom Hughes <tom@compton.nu>
Date: Sun, 8 May 2011 12:34:53 +0100
Subject: [PATCH] Add a C implementation of QuadTile.iterate_tiles_for_area

---
 lib/quad_tile.rb          |  38 ++++++-------
 lib/quad_tile/quad_tile.c | 115 +++++++++++++++++++++++++++++++++++---
 2 files changed, 127 insertions(+), 26 deletions(-)

diff --git a/lib/quad_tile.rb b/lib/quad_tile.rb
index 6e4fb6d22..1f7e6e501 100644
--- a/lib/quad_tile.rb
+++ b/lib/quad_tile.rb
@@ -39,6 +39,25 @@ module QuadTile
 
       return t
     end
+
+    def self.iterate_tiles_for_area(minlat, minlon, maxlat, maxlon)
+      tiles = tiles_for_area(minlat, minlon, maxlat, maxlon)
+      first = last = nil
+
+      tiles.sort.each do |tile|
+        if last.nil?
+          first = last = tile
+        elsif tile == last + 1
+          last = tile
+        else
+          yield first, last
+
+          first = last = tile
+        end
+      end
+
+      yield first, last unless last.nil?
+    end
   end
 
   def self.sql_for_area(minlat, minlon, maxlat, maxlon, prefix)
@@ -58,24 +77,5 @@ module QuadTile
     return "( " + sql.join(" OR ") + " )"
   end
 
-  def self.iterate_tiles_for_area(minlat, minlon, maxlat, maxlon)
-    tiles = tiles_for_area(minlat, minlon, maxlat, maxlon)
-    first = last = nil
-
-    tiles.sort.each do |tile|
-      if last.nil?
-        first = last = tile
-      elsif tile == last + 1
-        last = tile
-      else
-        yield first, last
-
-        first = last = tile
-      end
-    end
-
-    yield first, last unless last.nil?
-  end
-
   private_class_method :tile_for_xy, :iterate_tiles_for_area
 end
diff --git a/lib/quad_tile/quad_tile.c b/lib/quad_tile/quad_tile.c
index 137963bd0..089154597 100644
--- a/lib/quad_tile/quad_tile.c
+++ b/lib/quad_tile/quad_tile.c
@@ -1,6 +1,60 @@
 #include "ruby.h"
 #include "quad_tile.h"
 
+typedef struct {
+   unsigned int *tilev;
+   unsigned int tilec;
+} tilelist_t;
+
+static tilelist_t tilelist_for_area(unsigned int minx, unsigned int miny, unsigned int maxx, unsigned int maxy)
+{
+   unsigned int x;
+   unsigned int y;
+   tilelist_t   tl;
+   unsigned int maxtilec;
+
+   maxtilec = 256;
+   
+   tl.tilev = malloc(maxtilec * sizeof(unsigned int));
+   tl.tilec = 0;
+   
+   for (x = minx; x <= maxx; x++)
+   {
+      for (y = miny; y <= maxy; y++)
+      {
+         if (tl.tilec == maxtilec)
+         {
+            maxtilec = maxtilec * 2;
+
+            tl.tilev = realloc(tl.tilev, maxtilec * sizeof(unsigned int));
+         }
+
+         tl.tilev[tl.tilec++] = xy2tile(x, y);
+      }
+   }
+
+   return tl;
+}
+
+static int tile_compare(const void *ap, const void *bp)
+{
+   unsigned int a = *(unsigned int *)ap;
+   unsigned int b = *(unsigned int *)bp;
+
+   if (a < b)
+   {
+      return -1;
+   }
+   else if (a > b)
+   {
+      return 1;
+   }
+   else
+   {
+      return 0;
+   }
+}
+
 static VALUE tile_for_point(VALUE self, VALUE lat, VALUE lon)
 {
    unsigned int x = lon2x(NUM2DBL(lon));
@@ -15,18 +69,17 @@ static VALUE tiles_for_area(VALUE self, VALUE minlat, VALUE minlon, VALUE maxlat
    unsigned int maxx = lon2x(NUM2DBL(maxlon));
    unsigned int miny = lat2y(NUM2DBL(minlat));
    unsigned int maxy = lat2y(NUM2DBL(maxlat));
+   tilelist_t   tl = tilelist_for_area(minx, miny, maxx, maxy);
    VALUE        tiles = rb_ary_new();
-   unsigned int x;
-   unsigned int y;
+   unsigned int t;
 
-   for (x = minx; x <= maxx; x++)
+   for (t = 0; t < tl.tilec; t++)
    {
-      for (y = miny; y <= maxy; y++)
-      {
-         rb_ary_push(tiles, UINT2NUM(xy2tile(x, y)));
-      }
+      rb_ary_push(tiles, UINT2NUM(tl.tilev[tl.tilec]));
    }
 
+   free(tl.tilev);
+
    return tiles;
 }
 
@@ -35,6 +88,53 @@ static VALUE tile_for_xy(VALUE self, VALUE x, VALUE y)
    return UINT2NUM(xy2tile(NUM2UINT(x), NUM2UINT(y)));
 }
 
+static VALUE iterate_tiles_for_area(VALUE self, VALUE minlat, VALUE minlon, VALUE maxlat, VALUE maxlon)
+{
+   unsigned int minx = lon2x(NUM2DBL(minlon));
+   unsigned int maxx = lon2x(NUM2DBL(maxlon));
+   unsigned int miny = lat2y(NUM2DBL(minlat));
+   unsigned int maxy = lat2y(NUM2DBL(maxlat));
+   tilelist_t   tl = tilelist_for_area(minx, miny, maxx, maxy);
+
+   if (tl.tilec > 0)
+   {
+      unsigned int first;
+      unsigned int last;
+      unsigned int t;
+      VALUE        a = rb_ary_new();
+
+      qsort(tl.tilev, tl.tilec, sizeof(unsigned int), tile_compare);
+
+      first = last = tl.tilev[0];
+
+      for (t = 1; t < tl.tilec; t++)
+      {
+         unsigned int tile = tl.tilev[t];
+
+         if (tile == last + 1)
+         {
+            last = tile;
+         }
+         else
+         {
+            rb_ary_store(a, 0, UINT2NUM(first));
+            rb_ary_store(a, 1, UINT2NUM(last));
+            rb_yield(a);
+
+            first = last = tile;
+         }
+      }
+
+      rb_ary_store(a, 0, UINT2NUM(first));
+      rb_ary_store(a, 1, UINT2NUM(last));
+      rb_yield(a);
+   }
+
+   free(tl.tilev);
+
+   return Qnil;
+}
+
 void Init_quad_tile_so(void)
 {
    VALUE m = rb_define_module("QuadTile");
@@ -42,6 +142,7 @@ void Init_quad_tile_so(void)
    rb_define_module_function(m, "tile_for_point", tile_for_point, 2);
    rb_define_module_function(m, "tiles_for_area", tiles_for_area, 4);
    rb_define_module_function(m, "tile_for_xy", tile_for_xy, 2);
+   rb_define_module_function(m, "iterate_tiles_for_area", iterate_tiles_for_area, 4);
 
    return;
 }
-- 
2.39.5