Class: RedBlackTree

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

Direct Known Subclasses

ConcurrentRedBlackTree

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) ⇒ RedBlackTree

Returns a new instance of RedBlackTree.



433
434
435
436
437
438
439
440
 
# File 'lib/red_black_tree.rb', line 433

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.



430
431
432
 
# File 'lib/red_black_tree.rb', line 430

def default
  @default
end

#default_proc ⇒ Object (readonly)

Returns the value of attribute default_proc.



431
432
433
 
# File 'lib/red_black_tree.rb', line 431

def default_proc
  @default_proc
end

Instance Method Details

#[](key) ⇒ Object 



511
512
513
514
515
516
517
518
 
# File 'lib/red_black_tree.rb', line 511

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

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



499
500
501
502
503
 
# File 'lib/red_black_tree.rb', line 499

def []=(key, value)
  @root = @root.insert(key, value)
  @root.set_root
  @root.check_height if $DEBUG
end

#clear ⇒ Object 



495
496
497
 
# File 'lib/red_black_tree.rb', line 495

def clear
  @root = Node::EMPTY
end

#delete(key) ⇒ Object 



520
521
522
523
524
525
526
527
 
# File 'lib/red_black_tree.rb', line 520

def delete(key)
  deleted, @root, rebalance = @root.delete(key)
  unless empty?
    @root.set_root
    @root.check_height if $DEBUG
  end
  deleted.value
end

#dump_sexp ⇒ Object 



535
536
537
 
# File 'lib/red_black_tree.rb', line 535

def dump_sexp
  root.dump_sexp || ''
end

#dump_tree(io = '') ⇒ Object 



529
530
531
532
533
 
# File 'lib/red_black_tree.rb', line 529

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

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



455
456
457
458
459
460
461
462
 
# File 'lib/red_black_tree.rb', line 455

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

#each_key ⇒ Object 



465
466
467
468
469
470
471
472
473
474
 
# File 'lib/red_black_tree.rb', line 465

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 



476
477
478
479
480
481
482
483
484
485
 
# File 'lib/red_black_tree.rb', line 476

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) 


446
447
448
 
# File 'lib/red_black_tree.rb', line 446

def empty?
  root == Node::EMPTY
end

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

Returns:

  • (Boolean) 


506
507
508
 
# File 'lib/red_black_tree.rb', line 506

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

#keys ⇒ Object 



487
488
489
 
# File 'lib/red_black_tree.rb', line 487

def keys
  root.keys
end

#root ⇒ Object 



442
443
444
 
# File 'lib/red_black_tree.rb', line 442

def root
  @root
end

#size ⇒ Object Also known as: length 



450
451
452
 
# File 'lib/red_black_tree.rb', line 450

def size
  root.size
end

#to_hash ⇒ Object 



539
540
541
 
# File 'lib/red_black_tree.rb', line 539

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

#values ⇒ Object 



491
492
493
 
# File 'lib/red_black_tree.rb', line 491

def values
  root.values
end