Class: Searching::SkipList

Inherits:
Object
  • Object
show all
Defined in:
lib/searching/skip_list.rb

Defined Under Namespace

Classes: NilKey, Node

Constant Summary collapse

DEFAULT_MAX_LEVEL = 
32
DEFAULT_PROBABILITY = 
0.5
NIL_NODE = 
Node.new 0, NilKey.new, nil

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(max_level = DEFAULT_MAX_LEVEL, probability = DEFAULT_PROBABILITY) ⇒ SkipList

Returns a new instance of SkipList.



28
29
30
31
32
33
34
 
# File 'lib/searching/skip_list.rb', line 28

def initialize(max_level=DEFAULT_MAX_LEVEL, probability=DEFAULT_PROBABILITY)
  @max_level = max_level - 1
  @probability = probability
  @current_level = 0
  @header = Node.new @max_level, nil, nil
  @size = 0
end

Instance Attribute Details

#current_level ⇒ Object (readonly)

Returns the value of attribute current_level.



26
27
28
 
# File 'lib/searching/skip_list.rb', line 26

def current_level
  @current_level
end

#size ⇒ Object (readonly)

Returns the value of attribute size.



25
26
27
 
# File 'lib/searching/skip_list.rb', line 25

def size
  @size
end

Instance Method Details

#<<(value) ⇒ Object 



36
37
38
 
# File 'lib/searching/skip_list.rb', line 36

def <<(value)
  self[value] = value
end

#[](key) ⇒ Object 



40
41
42
43
 
# File 'lib/searching/skip_list.rb', line 40

def [](key)
  element = find key
  element.key == key ? element.value : nil
end

#[]=(key, value) ⇒ Object 



45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
 
# File 'lib/searching/skip_list.rb', line 45

def []=(key, value)
  update = []
  element = find key, update
  if element.key == key
    element.value = value 
  else
    target_level = random_level
    if target_level > @current_level
      ((@current_level+1)..target_level).each do |level|
        update[level] = @header
      end
      @current_level = target_level
    end
    target_element = Node.new @max_level, key, value
    (0..target_level).each do |level|
      target_element.forward[level] = update[level].forward[level]
      update[level].forward[level] = target_element
    end
    @size += 1
  end
end

#delete(key) ⇒ Object 



67
68
69
70
71
72
73
74
75
76
77
 
# File 'lib/searching/skip_list.rb', line 67

def delete(key)
  update = []
  element = find key, update
  if element.key == key
    (1..@current_level).each do |level|
      update[level].forward[level] = element.forward[level] if update[level].forward[level] == element
      @current_level -= 1 if @header.forward[level] == NIL_NODE
    end
    @size -= 1
  end
end

#to_a(level = 0) ⇒ Object 



87
88
89
90
91
92
93
94
95
 
# File 'lib/searching/skip_list.rb', line 87

def to_a(level=0)
  element = @header
  result = []
  while (forward = element.forward[level]) != NIL_NODE
    element = forward
    result << [element.key, element.value]
  end
  result
end

#to_s ⇒ Object 



79
80
81
82
83
84
85
 
# File 'lib/searching/skip_list.rb', line 79

def to_s
  str = ""
  @current_level.downto(0).each do |level|
    str << "(#{level}): #{to_a(level).inspect}"
  end
  str
end