Class: DSkipList

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/dskiplist.rb

Overview

The MIT License (MIT)

Copyright © 2014 Forrest Allison

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the “Software”), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Defined Under Namespace

Classes: Node

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(top_level = Float::INFINITY) ⇒ DSkipList

Returns a new instance of DSkipList.



43
44
45
46
47
48
49
 
# 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

Instance Attribute Details

#header ⇒ Object

Returns the value of attribute header.



27
28
29
 
# File 'lib/dskiplist.rb', line 27

def header
  @header
end

#level ⇒ Object

Returns the value of attribute level.



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

def level
  @level
end

Instance Method Details

#[](key) ⇒ Object 



70
71
72
73
74
75
76
77
 
# 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

#[]=(key, value) ⇒ Object 



138
139
140
 
# File 'lib/dskiplist.rb', line 138

def []= key, value
  self.insert(key, value)
end

#clear ⇒ Object 



51
52
53
54
 
# File 'lib/dskiplist.rb', line 51

def clear
  initialize(@max_level)
  return self
end

#count(from = nil, to = nil, level = 0) ⇒ Object 



147
148
149
 
# File 'lib/dskiplist.rb', line 147

def count(from = nil, to = nil, level = 0)
  each(from, to, nil, level, nil)
end

#delete(search_key) ⇒ Object 



87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
 
# 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

#each(from = nil, to = nil, limit = nil, level = 0, output = nil) ⇒ Object

accepts a block which is run on each element



152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
 
# 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

#find_node(search_key) ⇒ Object

returns previous node if exact key match is not found



57
58
59
60
61
62
63
64
65
66
67
68
 
# 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

#insert(search_key, new_value = nil) ⇒ Object 



108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
 
# 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

#insert_hash(hash) ⇒ Object 



142
143
144
145
 
# File 'lib/dskiplist.rb', line 142

def insert_hash(hash)
  hash.each {|key, value| self[key] = value}
  return self
end

#largest ⇒ Object 



195
196
197
198
199
200
201
202
203
 
# 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

#random_level ⇒ Object 



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

def random_level
  v = 0
  while rand < @p && v < @max_level
    v += 1
  end
  v
end

#smallest ⇒ Object 



205
206
207
 
# File 'lib/dskiplist.rb', line 205

def smallest 
  return @header.forward[0].value
end

#to_a(from = nil, to = nil, limit = nil, level = 0) ⇒ Object Also known as: to_ary 



190
191
192
 
# 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

#to_h(from = nil, to = nil, limit = nil, level = 0) ⇒ Object 



186
187
188
 
# 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

#to_s ⇒ Object 



209
210
211
212
213
214
215
 
# 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

#to_str ⇒ Object 



217
218
219
 
# File 'lib/dskiplist.rb', line 217

def to_str
  return "SkipList level #{@max_level}"
end