Class: ConsistentCluster::RedBlackTree

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/consistent-cluster/consistent_hashing/red_black_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) ⇒ RedBlackTree

Returns a new instance of RedBlackTree.



434
435
436
437
438
439
440
441
 
# File 'lib/consistent-cluster/consistent_hashing/red_black_tree.rb', line 434

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.



431
432
433
 
# File 'lib/consistent-cluster/consistent_hashing/red_black_tree.rb', line 431

def default
  @default
end

#default_proc ⇒ Object (readonly)

Returns the value of attribute default_proc.



432
433
434
 
# File 'lib/consistent-cluster/consistent_hashing/red_black_tree.rb', line 432

def default_proc
  @default_proc
end

Instance Method Details

#[](key) ⇒ Object 



512
513
514
515
516
517
518
519
 
# File 'lib/consistent-cluster/consistent_hashing/red_black_tree.rb', line 512

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

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



500
501
502
503
504
 
# File 'lib/consistent-cluster/consistent_hashing/red_black_tree.rb', line 500

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

#clear ⇒ Object 



496
497
498
 
# File 'lib/consistent-cluster/consistent_hashing/red_black_tree.rb', line 496

def clear
  @root = Node::EMPTY
end

#delete(key) ⇒ Object 



521
522
523
524
525
526
527
528
 
# File 'lib/consistent-cluster/consistent_hashing/red_black_tree.rb', line 521

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 



536
537
538
 
# File 'lib/consistent-cluster/consistent_hashing/red_black_tree.rb', line 536

def dump_sexp
  root.dump_sexp || ''
end

#dump_tree(io = '') ⇒ Object 



530
531
532
533
534
 
# File 'lib/consistent-cluster/consistent_hashing/red_black_tree.rb', line 530

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

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



456
457
458
459
460
461
462
463
 
# File 'lib/consistent-cluster/consistent_hashing/red_black_tree.rb', line 456

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

#each_key ⇒ Object 



466
467
468
469
470
471
472
473
474
475
 
# File 'lib/consistent-cluster/consistent_hashing/red_black_tree.rb', line 466

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 



477
478
479
480
481
482
483
484
485
486
 
# File 'lib/consistent-cluster/consistent_hashing/red_black_tree.rb', line 477

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) 


447
448
449
 
# File 'lib/consistent-cluster/consistent_hashing/red_black_tree.rb', line 447

def empty?
  root == Node::EMPTY
end

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

Returns:

  • (Boolean) 


507
508
509
 
# File 'lib/consistent-cluster/consistent_hashing/red_black_tree.rb', line 507

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

#keys ⇒ Object 



488
489
490
 
# File 'lib/consistent-cluster/consistent_hashing/red_black_tree.rb', line 488

def keys
  root.keys
end

#minimum_pair ⇒ Object 



544
545
546
547
548
549
550
551
552
553
554
 
# File 'lib/consistent-cluster/consistent_hashing/red_black_tree.rb', line 544

def minimum_pair()
   # Return the key with the smallest key value.
   return nil if @root.empty?

   current_node = @root
   while not current_node.left.empty?
     current_node = current_node.left
   end

   [current_node.key, current_node.value]
end

#next_gte_pair(key) ⇒ Object 



556
557
558
559
560
561
 
# File 'lib/consistent-cluster/consistent_hashing/red_black_tree.rb', line 556

def next_gte_pair(key)
  # Returns the key/value pair with a key that follows the provided key in
  # sorted order.
  node = next_gte_node(@root, key)
  [node.key, node.value] if not node.empty?
end

#root ⇒ Object 



443
444
445
 
# File 'lib/consistent-cluster/consistent_hashing/red_black_tree.rb', line 443

def root
  @root
end

#size ⇒ Object Also known as: length 



451
452
453
 
# File 'lib/consistent-cluster/consistent_hashing/red_black_tree.rb', line 451

def size
  root.size
end

#to_hash ⇒ Object 



540
541
542
 
# File 'lib/consistent-cluster/consistent_hashing/red_black_tree.rb', line 540

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

#values ⇒ Object 



492
493
494
 
# File 'lib/consistent-cluster/consistent_hashing/red_black_tree.rb', line 492

def values
  root.values
end