Class: Containers::RubyRBTreeMap::Node

Inherits:
Object
  • Object
show all
Defined in:
lib/containers/rb_tree_map.rb

Overview

:nodoc: all

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(key, value) ⇒ Node

Returns a new instance of Node.



227
228
229
230
231
232
233
234
235
 
# File 'lib/containers/rb_tree_map.rb', line 227

def initialize(key, value)
  @key = key
  @value = value
  @color = :red
  @left = nil
  @right = nil
  @size = 1
  @height = 1
end

Instance Attribute Details

#color ⇒ Object

Returns the value of attribute color.



226
227
228
 
# File 'lib/containers/rb_tree_map.rb', line 226

def color
  @color
end

#height ⇒ Object

Returns the value of attribute height.



226
227
228
 
# File 'lib/containers/rb_tree_map.rb', line 226

def height
  @height
end

#key ⇒ Object

Returns the value of attribute key.



226
227
228
 
# File 'lib/containers/rb_tree_map.rb', line 226

def key
  @key
end

#left ⇒ Object

Returns the value of attribute left.



226
227
228
 
# File 'lib/containers/rb_tree_map.rb', line 226

def left
  @left
end

#right ⇒ Object

Returns the value of attribute right.



226
227
228
 
# File 'lib/containers/rb_tree_map.rb', line 226

def right
  @right
end

#size ⇒ Object

Returns the value of attribute size.



226
227
228
 
# File 'lib/containers/rb_tree_map.rb', line 226

def size
  @size
end

#value ⇒ Object

Returns the value of attribute value.



226
227
228
 
# File 'lib/containers/rb_tree_map.rb', line 226

def value
  @value
end

Instance Method Details

#colorflip ⇒ Object 



241
242
243
244
245
 
# File 'lib/containers/rb_tree_map.rb', line 241

def colorflip
  @color       = @color == :red       ? :black : :red
  @left.color  = @left.color == :red  ? :black : :red
  @right.color = @right.color == :red ? :black : :red
end

#fixup ⇒ Object 



306
307
308
309
310
311
312
 
# File 'lib/containers/rb_tree_map.rb', line 306

def fixup
  rotate_left if @right && @right.red?
  rotate_right if (@left && @left.red?) && (@left.left && @left.left.red?)
  colorflip if (@left && @left.red?) && (@right && @right.red?)

  update_size
end

#move_red_left ⇒ Object 



287
288
289
290
291
292
293
294
295
 
# File 'lib/containers/rb_tree_map.rb', line 287

def move_red_left
  colorflip
  if (@right.left && @right.left.red?)
    @right.rotate_right
    rotate_left
    colorflip
  end
  self
end

#move_red_right ⇒ Object 



297
298
299
300
301
302
303
304
 
# File 'lib/containers/rb_tree_map.rb', line 297

def move_red_right
  colorflip
  if (@left.left && @left.left.red?)
    rotate_right
    colorflip
  end
  self
end

#red? ⇒ Boolean

Returns:

  • (Boolean) 


237
238
239
 
# File 'lib/containers/rb_tree_map.rb', line 237

def red?
  @color == :red
end

#rotate_left ⇒ Object 



259
260
261
262
263
264
265
266
267
268
269
270
271
 
# File 'lib/containers/rb_tree_map.rb', line 259

def rotate_left
  r = @right
  r_key, r_value, r_color = r.key, r.value, r.color
  b = r.left
  r.left = @left
  @left = r
  @right = r.right
  r.right = b
  r.color, r.key, r.value = :red, @key, @value
  @key, @value = r_key, r_value
  r.update_size
  update_size
end

#rotate_right ⇒ Object 



273
274
275
276
277
278
279
280
281
282
283
284
285
 
# File 'lib/containers/rb_tree_map.rb', line 273

def rotate_right
  l = @left
  l_key, l_value, l_color = l.key, l.value, l.color
  b = l.right
  l.right = @right
  @right = l
  @left = l.left
  l.left = b
  l.color, l.key, l.value = :red, @key, @value
  @key, @value = l_key, l_value
  l.update_size
  update_size
end

#update_size ⇒ Object 



247
248
249
250
251
252
253
254
255
256
257
 
# File 'lib/containers/rb_tree_map.rb', line 247

def update_size
  @size = (@left ? @left.size : 0) + (@right ? @right.size : 0) + 1
  left_height = (@left ? @left.height : 0)
  right_height = (@right ? @right.height : 0)
  if left_height > right_height
    @height = left_height + 1
  else
    @height = right_height + 1
  end
  self
end