Class: Puppet::Graph::RbTreeMap::Node

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

Overview

:nodoc: all

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(key, value) ⇒ Node


200
201
202
203
204
205
206
# File 'lib/puppet/graph/rb_tree_map.rb', line 200

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

Instance Attribute Details

#colorObject

Returns the value of attribute color


199
200
201
# File 'lib/puppet/graph/rb_tree_map.rb', line 199

def color
  @color
end

#keyObject

Returns the value of attribute key


199
200
201
# File 'lib/puppet/graph/rb_tree_map.rb', line 199

def key
  @key
end

#leftObject

Returns the value of attribute left


199
200
201
# File 'lib/puppet/graph/rb_tree_map.rb', line 199

def left
  @left
end

#rightObject

Returns the value of attribute right


199
200
201
# File 'lib/puppet/graph/rb_tree_map.rb', line 199

def right
  @right
end

#valueObject

Returns the value of attribute value


199
200
201
# File 'lib/puppet/graph/rb_tree_map.rb', line 199

def value
  @value
end

Instance Method Details

#colorflipObject


225
226
227
228
229
# File 'lib/puppet/graph/rb_tree_map.rb', line 225

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

#fixupObject


276
277
278
279
280
281
282
# File 'lib/puppet/graph/rb_tree_map.rb', line 276

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?)

  self
end

#move_red_leftObject


257
258
259
260
261
262
263
264
265
# File 'lib/puppet/graph/rb_tree_map.rb', line 257

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

#move_red_rightObject


267
268
269
270
271
272
273
274
# File 'lib/puppet/graph/rb_tree_map.rb', line 267

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

#red?Boolean


221
222
223
# File 'lib/puppet/graph/rb_tree_map.rb', line 221

def red?
  @color == :red
end

#rotate_leftObject


231
232
233
234
235
236
237
238
239
240
241
242
# File 'lib/puppet/graph/rb_tree_map.rb', line 231

def rotate_left
  r = @right
  r_key, r_value = r.key, r.value
  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
  self
end

#rotate_rightObject


244
245
246
247
248
249
250
251
252
253
254
255
# File 'lib/puppet/graph/rb_tree_map.rb', line 244

def rotate_right
  l = @left
  l_key, l_value = l.key, l.value
  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
  self
end

#to_hashObject


208
209
210
211
212
213
214
215
216
217
218
219
# File 'lib/puppet/graph/rb_tree_map.rb', line 208

def to_hash
  h = {
    :node => {
      :key => @key,
      :value => @value,
      :color => @color,
    }
  }
  h[:left] = left.to_hash if @left
  h[:right] = right.to_hash if @right
  h
end