Class: ConsistentCluster::RedBlackTree::Node

Inherits:
Object
  • Object
show all
Defined in:
lib/consistent-cluster/consistent_hashing/red_black_tree.rb

Direct Known Subclasses

EmptyNode

Defined Under Namespace

Classes: EmptyNode

Constant Summary collapse

UNDEFINED = 
Object.new

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(key, value, left, right, color = :RED) ⇒ Node

Returns a new instance of Node.



13
14
15
16
17
18
19
20
 
# File 'lib/consistent-cluster/consistent_hashing/red_black_tree.rb', line 13

def initialize(key, value, left, right, color = :RED)
  @key = key
  @value = value
  @left = left
  @right = right
  # new node is added as RED
  @color = color
end

Instance Attribute Details

#color ⇒ Object

Returns the value of attribute color.



10
11
12
 
# File 'lib/consistent-cluster/consistent_hashing/red_black_tree.rb', line 10

def color
  @color
end

#key ⇒ Object (readonly)

Returns the value of attribute key.



10
11
12
 
# File 'lib/consistent-cluster/consistent_hashing/red_black_tree.rb', line 10

def key
  @key
end

#left ⇒ Object

Returns the value of attribute left.



11
12
13
 
# File 'lib/consistent-cluster/consistent_hashing/red_black_tree.rb', line 11

def left
  @left
end

#right ⇒ Object

Returns the value of attribute right.



11
12
13
 
# File 'lib/consistent-cluster/consistent_hashing/red_black_tree.rb', line 11

def right
  @right
end

#value ⇒ Object (readonly)

Returns the value of attribute value.



10
11
12
 
# File 'lib/consistent-cluster/consistent_hashing/red_black_tree.rb', line 10

def value
  @value
end

Instance Method Details

#black? ⇒ Boolean

Returns:

  • (Boolean) 


30
31
32
 
# File 'lib/consistent-cluster/consistent_hashing/red_black_tree.rb', line 30

def black?
  @color == :BLACK
end

#check_height ⇒ Object

for debugging



145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
 
# File 'lib/consistent-cluster/consistent_hashing/red_black_tree.rb', line 145

def check_height
  lh = @left.nil?  || @left.empty? ? 0 : @left.check_height
  rh = @right.nil? || @right.empty? ? 0 : @right.check_height
  if red?
    if @left.red? or @right.red?
      puts dump_tree(STDERR)
      raise 'red/red assertion failed'
    end
  else
    if lh != rh
      puts dump_tree(STDERR)
      raise "black height unbalanced: #{lh} #{rh}"
    end
  end
  (lh > rh ? lh : rh) + (black? ? 1 : 0)
end

#delete(key) ⇒ Object

returns [deleted_node, new_root, is_rebalance_needed]



106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
 
# File 'lib/consistent-cluster/consistent_hashing/red_black_tree.rb', line 106

def delete(key)
  ret = self
  case key <=> @key
  when -1
    deleted, @left, rebalance = @left.delete(key)
    if rebalance
      ret, rebalance = rebalance_for_left_delete
    end
  when 0
    deleted = self
    ret, rebalance = delete_node
  when 1
    deleted, @right, rebalance = @right.delete(key)
    if rebalance
      ret, rebalance = rebalance_for_right_delete
    end
  else
    raise TypeError, "cannot compare #{key} and #{@key} with <=>"
  end
  [deleted, ret, rebalance]
end

#dump_sexp ⇒ Object 



134
135
136
137
138
139
140
141
142
 
# File 'lib/consistent-cluster/consistent_hashing/red_black_tree.rb', line 134

def dump_sexp
  left = @left.dump_sexp
  right = @right.dump_sexp
  if left or right
    '(' + [@key, left || '-', right].compact.join(' ') + ')'
  else
    @key
  end
end

#dump_tree(io, indent = '') ⇒ Object 



128
129
130
131
132
 
# File 'lib/consistent-cluster/consistent_hashing/red_black_tree.rb', line 128

def dump_tree(io, indent = '')
  @right.dump_tree(io, indent + '  ')
  io << indent << sprintf("#<%s:0x%010x %s %s> => %s", self.class.name, __id__, @color, @key.inspect, @value.inspect) << $/
  @left.dump_tree(io, indent + '  ')
end

#each {|[@key, @value]| ... } ⇒ Object

inorder

Yields:



43
44
45
46
47
 
# File 'lib/consistent-cluster/consistent_hashing/red_black_tree.rb', line 43

def each(&block)
  @left.each(&block)
  yield [@key, @value]
  @right.each(&block)
end

#each_key ⇒ Object 



49
50
51
52
53
 
# File 'lib/consistent-cluster/consistent_hashing/red_black_tree.rb', line 49

def each_key
  each do |k, v|
    yield k
  end
end

#each_value ⇒ Object 



55
56
57
58
59
 
# File 'lib/consistent-cluster/consistent_hashing/red_black_tree.rb', line 55

def each_value
  each do |k, v|
    yield v
  end
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


34
35
36
 
# File 'lib/consistent-cluster/consistent_hashing/red_black_tree.rb', line 34

def empty?
  false
end

#insert(key, value) ⇒ Object

returns new_root



70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
 
# File 'lib/consistent-cluster/consistent_hashing/red_black_tree.rb', line 70

def insert(key, value)
  ret = self
  case key <=> @key
  when -1
    @left = @left.insert(key, value)
    if black? and @right.black? and @left.red? and !@left.children_color?(:BLACK)
      ret = rebalance_for_left_insert
    end
  when 0
    @value = value
  when 1
    @right = @right.insert(key, value)
    if black? and @left.black? and @right.red? and !@right.children_color?(:BLACK)
      ret = rebalance_for_right_insert
    end
  else
    raise TypeError, "cannot compare #{key} and #{@key} with <=>"
  end
  ret.pullup_red
end

#keys ⇒ Object 



61
62
63
 
# File 'lib/consistent-cluster/consistent_hashing/red_black_tree.rb', line 61

def keys
  collect { |k, v| k }
end

#red? ⇒ Boolean

Returns:

  • (Boolean) 


26
27
28
 
# File 'lib/consistent-cluster/consistent_hashing/red_black_tree.rb', line 26

def red?
  @color == :RED
end

#retrieve(key) ⇒ Object

returns value



92
93
94
95
96
97
98
99
100
101
102
103
 
# File 'lib/consistent-cluster/consistent_hashing/red_black_tree.rb', line 92

def retrieve(key)
  case key <=> @key
  when -1
    @left.retrieve(key)
  when 0
    @value
  when 1
    @right.retrieve(key)
  else
    nil
  end
end

#set_root ⇒ Object 



22
23
24
 
# File 'lib/consistent-cluster/consistent_hashing/red_black_tree.rb', line 22

def set_root
  @color = :BLACK
end

#size ⇒ Object 



38
39
40
 
# File 'lib/consistent-cluster/consistent_hashing/red_black_tree.rb', line 38

def size
  @left.size + 1 + @right.size
end

#values ⇒ Object 



65
66
67
 
# File 'lib/consistent-cluster/consistent_hashing/red_black_tree.rb', line 65

def values
  collect { |k, v| v }
end