Class: AVLTree

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/avl_tree.rb

Defined Under Namespace

Classes: Node

Constant Summary collapse

DEFAULT = 
Object.new

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(default = DEFAULT, &block) ⇒ AVLTree

Returns a new instance of AVLTree.



299
300
301
302
303
304
305
306
 
# File 'lib/avl_tree.rb', line 299

def initialize(default = DEFAULT, &block)
  if block && default != DEFAULT
    raise ArgumentError, 'wrong number of arguments'
  end
  @root = Node::EMPTY
  @default = default
  @default_proc = block
end

Instance Attribute Details

#default ⇒ Object

Returns the value of attribute default.



296
297
298
 
# File 'lib/avl_tree.rb', line 296

def default
  @default
end

#default_proc ⇒ Object (readonly)

Returns the value of attribute default_proc.



297
298
299
 
# File 'lib/avl_tree.rb', line 297

def default_proc
  @default_proc
end

Instance Method Details

#[](key) ⇒ Object 



375
376
377
378
379
380
381
382
 
# File 'lib/avl_tree.rb', line 375

def [](key)
  value = @root.retrieve(key)
  if value == Node::UNDEFINED
    default_value
  else
    value
  end
end

#[]=(key, value) ⇒ Object Also known as: insert 



365
366
367
 
# File 'lib/avl_tree.rb', line 365

def []=(key, value)
  @root = @root.insert(key, value)
end

#clear ⇒ Object 



361
362
363
 
# File 'lib/avl_tree.rb', line 361

def clear
  @root = Node::EMPTY
end

#delete(key) ⇒ Object 



384
385
386
387
 
# File 'lib/avl_tree.rb', line 384

def delete(key)
  deleted, @root = @root.delete(key)
  deleted.value
end

#dump_sexp ⇒ Object 



395
396
397
 
# File 'lib/avl_tree.rb', line 395

def dump_sexp
  @root.dump_sexp || ''
end

#dump_tree(io = '') ⇒ Object 



389
390
391
392
393
 
# File 'lib/avl_tree.rb', line 389

def dump_tree(io = '')
  @root.dump_tree(io)
  io << $/
  io
end

#each(&block) ⇒ Object Also known as: each_pair 



321
322
323
324
325
326
327
328
 
# File 'lib/avl_tree.rb', line 321

def each(&block)
  if block_given?
    @root.each(&block)
    self
  else
    Enumerator.new(@root)
  end
end

#each_key ⇒ Object 



331
332
333
334
335
336
337
338
339
340
 
# File 'lib/avl_tree.rb', line 331

def each_key
  if block_given?
    @root.each do |k, v|
      yield k
    end
    self
  else
    Enumerator.new(@root, :each_key)
  end
end

#each_value ⇒ Object 



342
343
344
345
346
347
348
349
350
351
 
# File 'lib/avl_tree.rb', line 342

def each_value
  if block_given?
    @root.each do |k, v|
      yield v
    end
    self
  else
    Enumerator.new(@root, :each_value)
  end
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


308
309
310
 
# File 'lib/avl_tree.rb', line 308

def empty?
  @root == Node::EMPTY
end

#height ⇒ Object 



317
318
319
 
# File 'lib/avl_tree.rb', line 317

def height
  @root.height
end

#key?(key) ⇒ Boolean Also known as: has_key?

Returns:

  • (Boolean) 


370
371
372
 
# File 'lib/avl_tree.rb', line 370

def key?(key)
  @root.retrieve(key) != Node::UNDEFINED
end

#keys ⇒ Object 



353
354
355
 
# File 'lib/avl_tree.rb', line 353

def keys
  @root.keys
end

#size ⇒ Object Also known as: length 



312
313
314
 
# File 'lib/avl_tree.rb', line 312

def size
  @root.size
end

#to_hash ⇒ Object 



399
400
401
 
# File 'lib/avl_tree.rb', line 399

def to_hash
  inject({}) { |r, (k, v)| r[k] = v; r }
end

#values ⇒ Object 



357
358
359
 
# File 'lib/avl_tree.rb', line 357

def values
  @root.values
end