class Redis::HashRing

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

def binary_search(ary, value, &block)
  upper = ary.size - 1
  lower = 0
  idx = 0
  while(lower <= upper) do
    idx = (lower + upper) / 2
    comp = ary[idx] <=> value
    if comp == 0
      return idx
    elsif comp > 0
      upper = idx - 1
    else
      lower = idx + 1
    end
  end
  if upper < 0
    upper = ary.size - 1
  end
  return upper
end

def get_node(key)
  get_node_pos(key)[0]
end

def get_node_pos(key)
  return [nil,nil] if @ring.size == 0
  crc = Zlib.crc32(key)
  idx = HashRing.binary_search(@sorted_keys, crc)
  return [@ring[@sorted_keys[idx]], idx]
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.size == 0
  _, pos = get_node_pos(key)
  @sorted_keys[pos..-1].each do |k|
    yield @ring[k]
  end
end

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