range_hash
##Problem
Given a list of ranges, how do you effectively find if an element exist in any of them?
##Solution
[sudo] gem install range_hash
##Example
Simple
require 'range_hash'
ranges = RangeHash.new
ranges[1..3] = 'a'
ranges[10..15] = 'b'
ranges[27...30] = 'c'
ranges[7..10] = 'd'
ranges[2] #=> 'a'
ranges[15] #=> 'b'
ranges[100] #=> nil
Callbacks
require 'range_hash'
ranges = RangeHash.new
ranges.add_callback(1..13) do |elem|
puts "#{elem} is between 1 and 3"
end
ranges.add_callback(10..15) do |elem|
puts "#{elem} is between 10 and 15!"
end
ranges.add_callback(27...30) do |elem|
puts "#{elem} is between 27 and 29!"
end
ranges.add_callback(7..10) do |elem|
puts "#{elem} is between 7 and 10!"
end
ranges.add_callback(:default) do |elem|
puts "Couldn't find a range for #{elem}"
end
ranges.call(2) #=> 2 is between 1 and 3!
ranges.call(15) #=> 15 is between 10 and 15!
ranges.call(100) #=> Couldn't find a range of 100
##Wait ... why?
Because O(log n) is better than O(N). RangeHash keeps an internal sorted array that uses a binary search to find your range. This allows you to achieve (log n) search. Another option would be to store a dense hash that stores all possible elements within the ranges, however this isn't efficient in terms of memory usage. This is great happy medium.
On-top of that, RangeHash provides some awesome functionality such as callbacks.
##Notes
- Tested against 1.8.7, 1.9.2, 1.9.3
- Currently does not support ranges that overlap one another.