Class: RedBlackTree::Node

Inherits:
Object
  • Object
show all
Includes:
Comparable, DataDelegation, Implementation
Defined in:
lib/red_black_tree/node.rb,
lib/red_black_tree/node/left_right_element_referencers.rb

Direct Known Subclasses

LeafNode

Defined Under Namespace

Modules: Implementation, LeftRightElementReferencers

Constant Summary

Constants included from Implementation

Implementation::BLACK, Implementation::COLOURS, Implementation::DIRECTIONS, Implementation::LEFT, Implementation::RED, Implementation::RIGHT

Instance Attribute Summary collapse

Attributes included from Implementation

#colour, #left, #parent, #right

Class Method Summary collapse

Instance Method Summary collapse

Methods included from Implementation

#black!, #black?, #children, #children_are_leaves?, #children_are_valid?, #close_nephew, #distant_nephew, #leaf?, #opposite_position, #position, #red!, #red?, #sibling, #single_child_is_leaf?, #swap_colour_with!, #swap_position_with!, #valid?, #validate!, #validate_free!

Methods included from LeftRightElementReferencers

#[], #[]=

Methods included from DataDelegation

#method_missing, #respond_to_missing?

Constructor Details

#initialize(data) ⇒ Node

Returns a new instance of Node.

Parameters:

  • data (any) —

    a non-nil data/value representing the node

Raises:

  • (ArgumentError) 


27
28
29
30
31
32
33
34
35
 
# File 'lib/red_black_tree/node.rb', line 27

def initialize data
  raise ArgumentError, "data cannot be nil" if data.nil? && !(instance_of? RedBlackTree::LeafNode)

  @data = data
  @colour = nil
  @parent = @left = @right = nil

  validate_free!
end

Dynamic Method Handling

This class handles dynamic methods through the method_missing method in the class RedBlackTree::DataDelegation

Instance Attribute Details

#data ⇒ any (readonly)

Returns the data/value representing the node.

Returns:

  • (any) —

    the data/value representing the node



20
21
22
 
# File 'lib/red_black_tree/node.rb', line 20

def data
  @data
end

#tree ⇒ RedBlackTree::Node? (readonly)

Returns the tree this node belongs to.

Returns:



23
24
25
 
# File 'lib/red_black_tree/node.rb', line 23

def tree
  @tree
end

Class Method Details

.inherited(subclass) ⇒ Object 



11
12
13
 
# File 'lib/red_black_tree/node.rb', line 11

def inherited subclass
  subclass.prepend LeafNodeComparable unless subclass == ::RedBlackTree::LeafNode
end

Instance Method Details

#<=>(other) ⇒ Object

Needs to be implemented in a subclass of RedBlackTree::Node. Will be used to calculate the ideal position of this node when adding it to a tree.

Raises:

  • (NotImplementedError) 


40
41
42
 
# File 'lib/red_black_tree/node.rb', line 40

def <=> other
  raise NotImplementedError, "Comparable operator <=> must be implemented in subclass"
end