Class: WindingPolygon::AVLNode

Inherits:
Object
  • Object
show all
Defined in:
lib/winding-polygon/avltree.rb

Constant Summary collapse

BAL_H = 
1

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(args) ⇒ AVLNode

Returns a new instance of AVLNode.



153
154
155
156
157
158
159
160
161
162
 
# File 'lib/winding-polygon/avltree.rb', line 153

def initialize args
  @height = 0
  @left = nil
  @right = nil
  @value = nil
  @parent = nil
  args.each do |k,v|
    instance_variable_set("@#{k}", v) unless v.nil?
  end
end

Instance Attribute Details

#height ⇒ Object

Returns the value of attribute height.



152
153
154
 
# File 'lib/winding-polygon/avltree.rb', line 152

def height
  @height
end

#left ⇒ Object

Returns the value of attribute left.



152
153
154
 
# File 'lib/winding-polygon/avltree.rb', line 152

def left
  @left
end

#parent ⇒ Object

Returns the value of attribute parent.



152
153
154
 
# File 'lib/winding-polygon/avltree.rb', line 152

def parent
  @parent
end

#right ⇒ Object

Returns the value of attribute right.



152
153
154
 
# File 'lib/winding-polygon/avltree.rb', line 152

def right
  @right
end

#value ⇒ Object

Returns the value of attribute value.



152
153
154
 
# File 'lib/winding-polygon/avltree.rb', line 152

def value
  @value
end

Instance Method Details

#balance ⇒ Object 



164
165
166
167
168
 
# File 'lib/winding-polygon/avltree.rb', line 164

def balance
  rotate if difference.abs > BAL_H
  return self if @parent.nil?
  @parent.balance
end

#difference ⇒ Object 



235
236
237
238
239
 
# File 'lib/winding-polygon/avltree.rb', line 235

def difference
  r_height = @right.nil? ? 0 : @right.height
  l_height = @left.nil? ? 0 : @left.height
  r_height - l_height
end

#max ⇒ Object 



278
279
280
281
282
283
284
 
# File 'lib/winding-polygon/avltree.rb', line 278

def max
  node = self
  while !node.right.nil?
    node = node.right
  end
  node
end

#min ⇒ Object 



270
271
272
273
274
275
276
 
# File 'lib/winding-polygon/avltree.rb', line 270

def min
  node = self
  while !node.left.nil?
    node = node.left
  end
  node
end

#next ⇒ Object 



241
242
243
244
245
246
247
248
249
250
251
252
253
 
# File 'lib/winding-polygon/avltree.rb', line 241

def next
  if not @right.nil?
    @right.min
  else
    curr_node = self
    p_node = @parent
    while p_node != nil && curr_node == p_node.right
      curr_node = p_node
      p_node = p_node.parent
    end
    p_node
  end
end

#prev ⇒ Object 



255
256
257
258
259
260
261
262
263
264
265
266
267
 
# File 'lib/winding-polygon/avltree.rb', line 255

def prev
  if not @left.nil?
    @left.max
  else
    curr_node = self
    p_node = @parent
    while p_node != nil && curr_node == p_node.left
      curr_node = p_node
      p_node = p_node.parent
    end
    p_node
  end
end

#print ⇒ Object 



295
296
297
298
299
300
301
 
# File 'lib/winding-polygon/avltree.rb', line 295

def print
  out_s = "#{@value} - "
  instance_variables.each do |i|
    out_s += "(#{i}: #{instance_variable_get(i.to_sym)})"
  end
  puts out_s
end

#print_node ⇒ Object 



286
287
288
289
290
291
292
293
 
# File 'lib/winding-polygon/avltree.rb', line 286

def print_node
  out_s =  "\t\t\t\t\t\n"
  out_s += "\t\t#{@parent}\t\t\n"
  out_s += "#{@height}\t\t|#{@value}|\t\t\n"
  out_s += "\t#{@left}\t\t#{@right}\t\n"
  out_s +=  "\t\t\t\t\t\n"
  puts out_s
end

#rotate ⇒ Object 



177
178
179
180
181
182
183
184
185
186
187
 
# File 'lib/winding-polygon/avltree.rb', line 177

def rotate
  if difference >= BAL_H
    #check if children should rotate too
    @right.rotate if @right.difference <= -BAL_H
    rotate_left
  elsif difference <= - BAL_H
    #check if children should rotate too
    @left.rotate if @left.difference >= BAL_H
    rotate_right
  end
end

#rotate_left ⇒ Object 



189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
 
# File 'lib/winding-polygon/avltree.rb', line 189

def rotate_left
  #the old right is now the root
  root = @right
  root.parent = @parent
  #update the parent to point to the new root
  if not @parent.nil?
    if @parent.right == self
      @parent.right = root
    else
      @parent.left = root
    end
  end

  #this node's right is now the root's left
  @right = root.left
  root.left.parent = self unless root.left.nil?

  #the root is now the parent of this node
  @parent = root
  #this node is now the root's left
  root.left = self
  root.left.update_height
  root
end

#rotate_right ⇒ Object 



214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
 
# File 'lib/winding-polygon/avltree.rb', line 214

def rotate_right
  root = @left
  root.parent = @parent
  #update the parent to point to the new root
  if not @parent.nil?
    if @parent.right == self
      @parent.right = root
    else
      @parent.left = root
    end
  end

  @left = root.right
  root.right.parent = self unless root.right.nil?

  @parent = root
  root.right = self
  root.right.update_height
  root
end

#to_s ⇒ Object 



303
304
305
 
# File 'lib/winding-polygon/avltree.rb', line 303

def to_s
  @value.to_s
end

#update_height ⇒ Object 



170
171
172
173
174
175
 
# File 'lib/winding-polygon/avltree.rb', line 170

def update_height
  l_height = @left.nil? ? 0 : @left.height
  r_height = @right.nil? ? 0 : @right.height
  @height = ((l_height > r_height) ? l_height : r_height) + 1
  @parent.update_height unless @parent.nil?
end