class DSkipList

# File lib/dskiplist.rb, line 43
def initialize(top_level = Float::INFINITY)
 @header = Node.new(1) 
 @level = 0
 @max_level = top_level
 @p = 0.5
 @node_nil = Node.new(1000000)
end

# File lib/dskiplist.rb, line 70
def [] key
  node = self.find_node(key)
  if node and node.key == key
    return node.value
  else
    return nil
  end
end

# File lib/dskiplist.rb, line 138
def []= key, value
  self.insert(key, value)
end

# File lib/dskiplist.rb, line 51
def clear
  initialize(@max_level)
  return self
end

# File lib/dskiplist.rb, line 147
def count(from = nil, to = nil, level = 0)
  each(from, to, nil, level, nil)
end

# File lib/dskiplist.rb, line 87
def delete(search_key)
  update = []
  x = @header
  @level.downto(0) do |i|
    while x.forward[i] and x.forward[i].key < search_key
      x = x.forward[i]
    end
    update[i] = x
  end
  x = x.forward[0]
  if x and x.key == search_key
    0.upto(x.forward.length - 1) do |i|
        update[i].forward[i] = x.forward[i]
    end
    return true
  else
    return false
  end
end

# File lib/dskiplist.rb, line 152
def each(from=nil, to=nil, limit=nil, level=0, output=nil)
  if from 
    x = find_node(from)
    x = x.forward[level] if x.forward[level]
  else
    x = @header.forward[level]
  end
  #if no block is given, assume we are trying to count and avoid the expensive yield below
  if !block_given? 
    count = 0
    while x
      break if to && x.key >= to
      count += 1
      x = x.forward[level]
    end
    return count
  elsif to or limit
    count = 0 
    while !x.nil?
      yield(x, output) 
      count += 1
      break if to and x.key >= to 
      break if limit and count == limit 
      x = x.forward[level]
    end
  else
    while x
      yield(x, output)
      x = x.forward[level]
    end
  end
  return output
end

# File lib/dskiplist.rb, line 57
def find_node(search_key)
  x = @header
  @level.downto(0) do |i|
    #puts "on level #{i}"
    while x.forward[i] and x.forward[i].key < search_key
      #puts "walked node #{x.key} on level #{i}"
      x = x.forward[i]
    end
  end 
  x = x.forward[0] if x.forward[0] and x.forward[0].key == search_key
  return x
end

# File lib/dskiplist.rb, line 108
def insert(search_key, new_value = nil)
  new_value = search_key if new_value.nil? 
  update = []
  x = @header
  @level.downto(0) do |i|
    while x.forward[i] and x.forward[i].key < search_key
      x = x.forward[i]
    end
    update[i] = x
  end   
  x = x.forward[0]
  if x and x.key == search_key
    x.value = new_value
  else
    v = random_level
    if v > @level
      (@level + 1).upto(v) do |i|
        update[i] = @header
      end
      @level = v
    end
    x = Node.new(search_key, new_value) 
    0.upto(v) do |i|
      x.forward[i] = update[i].forward[i]
      update[i].forward[i] = x
    end
  end
  return self
end

# File lib/dskiplist.rb, line 142
def insert_hash(hash)
  hash.each {|key, value| self[key] = value}
  return self
end

# File lib/dskiplist.rb, line 195
def largest 
  x = @header
  @level.downto(0) do |i|
    while x.forward[i]
      x = x.forward[i]
    end
  end
  return x.value
end

# File lib/dskiplist.rb, line 79
def random_level
  v = 0
  while rand < @p && v < @max_level
    v += 1
  end
  v
end

# File lib/dskiplist.rb, line 205
def smallest 
  return @header.forward[0].value
end

# File lib/dskiplist.rb, line 190
def to_a(from = nil, to = nil, limit = nil, level = 0)
  each(from, to, limit, level, []) {|n, arr| arr.push(n.value)}
end

# File lib/dskiplist.rb, line 186
def to_h(from = nil, to = nil, limit = nil, level = 0)
  each(from, to, limit, level, {}) {|n, hash| hash[n.key] = n.value}
end

# File lib/dskiplist.rb, line 209
def to_s
  str = ""
  @level.downto(0) do |l|
    str << "Level #{l}: " + to_a(nil, nil, nil, l).join('-') + "\n" 
  end
   return str 
end

# File lib/dskiplist.rb, line 217
def to_str
  return "SkipList level #{@max_level}"
end