Class: VebTree::PureRuby

Inherits:
Object
  • Object
show all
Defined in:
lib/veb_tree/pure_ruby.rb

Constant Summary collapse

NIL_VALUE = 
-1

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(universe_size) ⇒ PureRuby

Returns a new instance of PureRuby.

Raises:

  • (ArgumentError) 


11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
# File 'lib/veb_tree/pure_ruby.rb', line 11

def initialize(universe_size)
  raise ArgumentError, "Universe size must be positive" if universe_size <= 0
  
  @universe_size = next_power_of_2(universe_size)
  warn "Universe size #{universe_size} rounded up to #{@universe_size}" if @universe_size != universe_size
  
  @size = 0
  @min = NIL_VALUE
  @max = NIL_VALUE
  
  # Base case
  if @universe_size <= 2
    @base_case = true
    return
  end
  
  @base_case = false
  
  # Calculate sqrt
  log_u = Math.log2(@universe_size).to_i
  @sqrt_size = 1 << (log_u / 2)
  @num_clusters = @universe_size / @sqrt_size
  
  # Lazy allocation
  @clusters = Array.new(@num_clusters)
  @summary = nil
end

Instance Attribute Details

#size ⇒ Object (readonly)

Returns the value of attribute size.



7
8
9
 
# File 'lib/veb_tree/pure_ruby.rb', line 7

def size
  @size
end

#universe_size ⇒ Object (readonly)

Returns the value of attribute universe_size.



7
8
9
 
# File 'lib/veb_tree/pure_ruby.rb', line 7

def universe_size
  @universe_size
end

Instance Method Details

#clear ⇒ Object 



226
227
228
229
230
231
232
233
234
 
# File 'lib/veb_tree/pure_ruby.rb', line 226

def clear
  @min = @max = NIL_VALUE
  @size = 0
  unless @base_case
    @summary&.clear
    @clusters.fill(nil)
  end
  self
end

#delete(key) ⇒ Object 



87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
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
137
138
139
140
141
142
143
 
# File 'lib/veb_tree/pure_ruby.rb', line 87

def delete(key)
  return false unless include?(key)
  
  # Base case
  if @base_case
    if key == @min && key == @max
      @min = @max = NIL_VALUE
    elsif key == @min
      @min = @max
    else
      @max = @min
    end
    @size -= 1
    return true
  end
  
  # Only one element
  if @size == 1
    @min = @max = NIL_VALUE
    @size = 0
    return true
  end
  
  # Replace min with successor if deleting min
  if key == @min
    first_cluster = @summary.min
    key = index(first_cluster, @clusters[first_cluster].min)
    @min = key
  end
  
  # Recursive delete
  h = high(key)
  l = low(key)
  
  @clusters[h].delete(l) if @clusters[h]
  
  # If cluster is empty, remove from summary
  if @clusters[h] && @clusters[h].min == NIL_VALUE
    @summary.delete(h)
    @clusters[h] = nil
    
    # Update max if necessary
    if key == @max
      summary_max = @summary.max
      if summary_max == NIL_VALUE
        @max = @min
      else
        @max = index(summary_max, @clusters[summary_max].max)
      end
    end
  elsif key == @max && @clusters[h]
    @max = index(h, @clusters[h].max)
  end
  
  @size -= 1
  true
end

#each ⇒ Object 



236
237
238
239
240
241
242
243
244
245
246
247
 
# File 'lib/veb_tree/pure_ruby.rb', line 236

def each
  return enum_for(:each) unless block_given?
  
  current = @min
  while current && current != NIL_VALUE
    yield current
    break if current == @max
    current = successor(current)
  end
  
  self
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


222
223
224
 
# File 'lib/veb_tree/pure_ruby.rb', line 222

def empty?
  @size == 0
end

#include?(key) ⇒ Boolean Also known as: member?

Returns:

  • (Boolean) 


145
146
147
148
149
150
151
152
 
# File 'lib/veb_tree/pure_ruby.rb', line 145

def include?(key)
  return false if key < 0 || key >= @universe_size
  return true if key == @min || key == @max
  return false if @base_case
  
  h = high(key)
  @clusters[h] && @clusters[h].include?(low(key))
end

#insert(key) ⇒ Object 



39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
 
# File 'lib/veb_tree/pure_ruby.rb', line 39

def insert(key)
  validate_key(key)
  return false if include?(key)
  
  # Empty tree
  if @min == NIL_VALUE
    @min = @max = key
    @size += 1
    return true
  end
  
  # Base case
  if @base_case
    @min = key if key < @min
    @max = key if key > @max
    @size += 1
    return true
  end
  
  # Ensure key is not min
  if key < @min
    key, @min = @min, key
  end
  
  @max = key if key > @max
  
  # Recursive insert
  h = high(key)
  l = low(key)
  
  # Lazy create cluster
  @clusters[h] ||= PureRuby.new(@sqrt_size)
  
  # If cluster was empty, update summary
  if @clusters[h].min == NIL_VALUE
    @summary ||= PureRuby.new(@num_clusters)
    @summary.insert(h)
    @clusters[h].instance_variable_set(:@min, l)
    @clusters[h].instance_variable_set(:@max, l)
    @clusters[h].instance_variable_set(:@size, 1)
  else
    @clusters[h].insert(l)
  end
  
  @size += 1
  true
end

#max ⇒ Object 



159
160
161
 
# File 'lib/veb_tree/pure_ruby.rb', line 159

def max
  @max == NIL_VALUE ? nil : @max
end

#min ⇒ Object 



155
156
157
 
# File 'lib/veb_tree/pure_ruby.rb', line 155

def min
  @min == NIL_VALUE ? nil : @min
end

#predecessor(key) ⇒ Object 



192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
 
# File 'lib/veb_tree/pure_ruby.rb', line 192

def predecessor(key)
  return nil if @max == NIL_VALUE
  
  # Base case
  if @base_case
    return @max if key > @max
    return @min if key > @min
    return nil
  end
  
  return @max if key > @max
  
  h = high(key)
  l = low(key)
  
  # Check same cluster
  if @clusters[h] && l > @clusters[h].min
    offset = @clusters[h].predecessor(l)
    return index(h, offset)
  end
  
  # Previous cluster
  pred_cluster = @summary.predecessor(h)
  return @min if pred_cluster == NIL_VALUE && key > @min
  return nil if pred_cluster == NIL_VALUE
  
  offset = @clusters[pred_cluster].max
  index(pred_cluster, offset)
end

#successor(key) ⇒ Object 



163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
 
# File 'lib/veb_tree/pure_ruby.rb', line 163

def successor(key)
  return nil if @min == NIL_VALUE
  
  # Base case
  if @base_case
    return @min if key < @min
    return @max if key < @max
    return nil
  end
  
  return @min if key < @min
  
  h = high(key)
  l = low(key)
  
  # Check same cluster
  if @clusters[h] && l < @clusters[h].max
    offset = @clusters[h].successor(l)
    return index(h, offset)
  end
  
  # Next cluster
  succ_cluster = @summary.successor(h)
  return nil if succ_cluster == NIL_VALUE
  
  offset = @clusters[succ_cluster].min
  index(succ_cluster, offset)
end

#to_a ⇒ Object 



249
250
251
 
# File 'lib/veb_tree/pure_ruby.rb', line 249

def to_a
  each.to_a
end