class Redis::HashRing

def add_node(node)
  @nodes << node
  @replicas.times do |i|
    key = server_hash_for("#{node.id}:#{i}")
    @ring[key] = node
    @sorted_keys << key
  end
  @sorted_keys.sort!
end

def binary_search(ary, value)
  upper = ary.size
  lower = 0
  while lower < upper
    mid = (lower + upper) / 2
    if ary[mid] > value
      upper = mid
    else
      lower = mid + 1
    end
  end
  upper - 1
end

def get_node(key)
  hash = hash_for(key)
  idx = binary_search(@sorted_keys, hash)
  @ring[@sorted_keys[idx]]
end

def hash_for(key)
  Zlib.crc32(key)
end

def initialize(nodes = [], replicas = POINTS_PER_SERVER)
  @replicas = replicas
  @ring = {}
  @nodes = []
  @sorted_keys = []
  nodes.each do |node|
    add_node(node)
  end
end

def iter_nodes(key)
  return [nil, nil] if @ring.empty?
  crc = hash_for(key)
  pos = binary_search(@sorted_keys, crc)
  @ring.size.times do |n|
    yield @ring[@sorted_keys[(pos + n) % @ring.size]]
  end
end

def remove_node(node)
  @nodes.reject! { |n| n.id == node.id }
  @replicas.times do |i|
    key = server_hash_for("#{node.id}:#{i}")
    @ring.delete(key)
    @sorted_keys.reject! { |k| k == key }
  end
end

def server_hash_for(key)
  Digest::MD5.digest(key).unpack1("L>")
end