class DSA::SkipList

Attributes

height[R]
length[R]

Public Class Methods

new() click to toggle source
# File lib/DSA/skip_list.rb, line 32
def initialize
  @levels = [SkipListLevel.new]
  @length = 0
  @height = 0
end

Public Instance Methods

add(key, value = nil) click to toggle source
# File lib/DSA/skip_list.rb, line 177
def add(key, value = nil)
  potential_place = []
  walk = start_node
  while 1
    if walk.next.is_sentinel? || key <= walk.next.key
      if walk.down
        potential_place.push walk
        walk = walk.down
        next
      else
        insert_node_between walk, walk.next, SkipListNode.new(key, value)
        @length += 1
        build_tower walk.next, potential_place, key, value
        break
      end
    else
      walk = walk.next
      next
    end
  end
end
delete(key, value = nil) click to toggle source

if value provided, the nodes have the same key/value pairs will be deleted, otherwise, all nodes have the same key are deleted return the value of last deleted node

# File lib/DSA/skip_list.rb, line 161
def delete(key, value = nil)
  nodes = find_nodes(key)
  return false unless nodes

  return_value = false
  nodes.each do |node|
    if !value || value == node.value
      return_value = remove_tower node
      @length -= 1
      remove_empty_level
    end
  end

  return_value
end
each() { |key, value| ... } click to toggle source
# File lib/DSA/skip_list.rb, line 56
def each
  walk = @levels.first.head
  if block_given?
    walk = walk.next
    until walk.is_sentinel?
      yield [ walk.key, walk.value ]
      walk = walk.next
    end
  else
    Enumerator.new do |y|
      each do |key, value|
        y << [key, value]
      end
    end
  end
end
find(key) { |key, value| ... } click to toggle source
# File lib/DSA/skip_list.rb, line 38
def find(key)
  nodes = find_nodes key

  if block_given?
    return unless nodes
    nodes.each do |node|
      yield [node.key, node.value]
    end
  else
    Enumerator.new do |y|
      find(key) do |key, value|
        y << [key, value]
      end
    end
  end

end
ge(key) { |key, value| ... } click to toggle source
# File lib/DSA/skip_list.rb, line 92
def ge(key)
  nodes = find_nodes(key, true, false)

  if block_given?
    return unless nodes
    if nodes.first.key == key
      walk = nodes.first
    else
      walk = nodes.first.next
    end
    until walk.is_sentinel?
      yield [ walk.key, walk.value ]
      walk = walk.next
    end
  else
    Enumerator.new do |y|
      ge(key) do |key, value|
        y << [key, value]
      end
    end
  end
end
gt(key) { |key, value| ... } click to toggle source
# File lib/DSA/skip_list.rb, line 73
def gt(key)
  nodes = find_nodes(key, true, false)

  if block_given?
    return unless nodes
    walk = nodes.last.next
    until walk.is_sentinel?
      yield [ walk.key, walk.value ]
      walk = walk.next
    end
  else
    Enumerator.new do |y|
      gt(key) do |key, value|
        y << [key, value]
      end
    end
  end
end
le(key) { |key, value| ... } click to toggle source
# File lib/DSA/skip_list.rb, line 134
def le(key)
  nodes = find_nodes(key, false, true)

  if block_given?
    return unless nodes
    if nodes.first.key == key
      walk = nodes.last
    else
      walk = nodes.last.prev
    end
    until walk.is_sentinel?
      yield [ walk.key, walk.value ]
      walk = walk.prev
    end
  else
    Enumerator.new do |y|
      le(key) do |key, value|
        y << [key, value]
      end
    end
  end
end
lt(key) { |key, value| ... } click to toggle source
# File lib/DSA/skip_list.rb, line 115
def lt(key)
  nodes = find_nodes(key, false, true)

  if block_given?
    return unless nodes
    walk = nodes.first.prev
    until walk.is_sentinel?
      yield [ walk.key, walk.value ]
      walk = walk.prev
    end
  else
    Enumerator.new do |y|
      lt(key) do |key, value|
        y << [key, value]
      end
    end
  end
end
print_me(width = 10) click to toggle source

Private Instance Methods

add_level() click to toggle source
# File lib/DSA/skip_list.rb, line 316
def add_level
  new_level = SkipListLevel.new
  vertical_link_node  new_level.head, @levels.last.head
  vertical_link_node  new_level.tail, @levels.last.tail
  @levels.push new_level
end
build_tower(base, tower, key, value) click to toggle source
# File lib/DSA/skip_list.rb, line 298
def build_tower(base, tower, key, value)
  up_stair_previous = nil
  tower.reverse_each do |node|
    return unless go_up?
    up_stair_previous = node
    new_node = SkipListNode.new(key, value)
    insert_node_between up_stair_previous, up_stair_previous.next, new_node
    vertical_link_node new_node, base
    base = new_node
  end
  # add new level
  if go_up?
    add_level
    @height += 1
  end

end
end_node() click to toggle source
# File lib/DSA/skip_list.rb, line 352
def end_node
  @levels.first.tail
end
find_nodes(key, return_previous = false, return_next = false ) click to toggle source

if not found, two more options are provided

# File lib/DSA/skip_list.rb, line 245
def find_nodes(key, return_previous = false, return_next = false )
  walk = start_node
  while 1
    if !walk.is_sentinel? && key == walk.key
      break
    elsif walk.next.is_sentinel? || key < walk.next.key
      if walk.down
        walk = walk.down
        next
      else
        if return_previous
          return [walk]
        elsif return_next
          return [walk.next]
        else
          return nil
        end
      end
    else
      walk = walk.next
      next
    end
  end

  nodes = []
  while !walk.is_sentinel? && walk.down
    walk = walk.down
  end

  nodes.push walk

  # to find the duplicates
  other_node = walk.next
  while !other_node.is_sentinel? && other_node.key == key
    nodes.push other_node
    other_node = other_node.next
  end

  other_node = walk.prev
  while !other_node.is_sentinel? && other_node.key == key
    nodes.unshift other_node
    other_node = other_node.prev
  end

  nodes
end
go_up?() click to toggle source
# File lib/DSA/skip_list.rb, line 328
def go_up?
  [true, false].sample
end
insert_node_between(a, b, new_one) click to toggle source
# File lib/DSA/skip_list.rb, line 332
def insert_node_between(a, b, new_one)
  a.next = new_one
  new_one.prev = a
  new_one.next = b
  b.prev = new_one
end
remove_empty_level() click to toggle source
# File lib/DSA/skip_list.rb, line 235
def remove_empty_level
  return if @length < 2
  one_to_last = @levels[-2]
  if one_to_last.head.next.is_sentinel?
    @levels.pop
    @height -= 1
  end
end
remove_node(node) click to toggle source

remove a node

# File lib/DSA/skip_list.rb, line 340
def remove_node(node)
  before = node.prev
  after = node.next
  before.next = after
  after.prev = before
  node
end
remove_tower(base) click to toggle source
# File lib/DSA/skip_list.rb, line 292
def remove_tower(base)
  remove_node base
  remove_tower base.up if base.up
  base.value
end
start_node() click to toggle source
# File lib/DSA/skip_list.rb, line 348
def start_node
  @levels.last.head
end