ring.rb in consistent-hashing-0.2.0

- old
+ new

@@ -8,12 +8,11 @@
   class Ring
 
     # Public: returns a new ring object
     def initialize(nodes = [], replicas = 3)
       @replicas = replicas
-      @sorted_keys = []
-      @ring = Hash.new
+      @ring = AVLTree.new
 
       nodes.each { |node| add(node) }
     end
 
     # Public: returns the (virtual) points in the hash ring
@@ -29,15 +28,12 @@
       @replicas.times do |i|
         # generate the key of this (virtual) point in the hash
         key = hash_key(node, i)
 
         @ring[key] = VirtualPoint.new(node, key)
-        @sorted_keys << key
       end
 
-      @sorted_keys.sort!
-
       self
     end
     alias :<< :add
 
     # Public: removes a node from the hash ring
@@ -45,29 +41,24 @@
     def delete(node)
       @replicas.times do |i|
         key = hash_key(node, i)
 
         @ring.delete key
-        @sorted_keys.delete key
       end
 
       self
     end
 
     # Public: gets the point for an arbitrary key
     #
     #
     def point_for(key)
       return nil if @ring.empty?
-
       key = hash_key(key)
-
-      @sorted_keys.each do |i|
-        return @ring[i] if key <= i
-      end
-
-      @ring[@sorted_keys[0]]
+      _, value = @ring.next_gte_pair(key)
+      _, value = @ring.minimum_pair unless value
+      value
     end
 
     # Public: gets the node where to store the key
     #
     # Returns: the node Object
@@ -98,6 +89,6 @@
     def hash_key(key, index = nil)
       key = "#{key}:#{index}" if index
       Digest::MD5.hexdigest(key.to_s)[0..16].hex
     end
   end
-end
\ No newline at end of file
+end