Cleanup trailing whitespace
[rails.git] / lib / short_link.rb
1 ##
2 # Encodes and decodes locations from Morton-coded "quad tile" strings. Each
3 # variable-length string encodes to a precision of one pixel per tile (roughly,
4 # since this computation is done in lat/lon coordinates, not mercator).
5 # Each character encodes 3 bits of x and 3 of y, so there are extra characters
6 # tacked on the end to make the zoom levels "work".
7 module ShortLink
8
9   # array of 64 chars to encode 6 bits. this is almost like base64 encoding, but
10   # the symbolic chars are different, as base64's + and / aren't very
11   # URL-friendly.
12   ARRAY = ('A'..'Z').to_a + ('a'..'z').to_a + ('0'..'9').to_a + ['_','~']
13
14   ##
15   # Given a string encoding a location, returns the [lon, lat, z] tuple of that
16   # location.
17   def self.decode(str)
18     x = 0
19     y = 0
20     z = 0
21     z_offset = 0
22
23     # keep support for old shortlinks which use the @ character, now
24     # replaced by the ~ character because twitter is horribly broken
25     # and we can't have that.
26     str.gsub!("@","~")
27
28     str.each_char do |c|
29       t = ARRAY.index c
30       if t.nil?
31         z_offset -= 1
32       else
33         3.times do
34           x <<= 1; x = x | 1 unless (t & 32).zero?; t <<= 1
35           y <<= 1; y = y | 1 unless (t & 32).zero?; t <<= 1
36         end
37         z += 3
38       end
39     end
40     # pack the coordinates out to their original 32 bits.
41     x <<= (32 - z)
42     y <<= (32 - z)
43
44     # project the parameters back to their coordinate ranges.
45     [(x * 360.0 / 2**32) - 180.0,
46      (y * 180.0 / 2**32) - 90.0,
47      z - 8 - (z_offset % 3)]
48   end
49
50   ##
51   # given a location and zoom, return a short string representing it.
52   def self.encode(lon, lat, z)
53     code = interleave_bits(((lon + 180.0) * 2**32 / 360.0).to_i,
54                            ((lat +  90.0) * 2**32 / 180.0).to_i)
55     str = ""
56     # add eight to the zoom level, which approximates an accuracy of
57     # one pixel in a tile.
58     ((z + 8)/3.0).ceil.times do |i|
59       digit = (code >> (58 - 6 * i)) & 0x3f
60       str << ARRAY[digit]
61     end
62     # append characters onto the end of the string to represent
63     # partial zoom levels (characters themselves have a granularity
64     # of 3 zoom levels).
65     ((z + 8) % 3).times { str << "-" }
66
67     return str
68   end
69
70   private
71
72   ##
73   # interleaves the bits of two 32-bit numbers. the result is known
74   # as a Morton code.
75   def self.interleave_bits(x, y)
76     c = 0
77     31.downto(0) do |i|
78       c = (c << 1) | ((x >> i) & 1)
79       c = (c << 1) | ((y >> i) & 1)
80     end
81     c
82   end
83
84 end