class Collatz::TreeGraphNode
Nodes that form a “tree graph”, structured as a tree, with their own node’s value, as well as references to either possible child node, where a node can only ever have two children, as there are only ever two reverse values. Also records any possible “terminal sequence state”, whether that be that the “orbit distance” has been reached, as an “out of bounds” stop, which is the regularly expected terminal state. Other terminal states possible however include the cycle state and cycle length (end) states.
Attributes
The value of this node in the tree.
The “Pre aN+b” TreeGraphNode
child of this node that is present if it exists and this is not a terminal node.
The “Pre N/P” TreeGraphNode
child of this node that is always present if this is not a terminal node.
The terminal SequenceState
; nil if not a terminal node, MAX_STOP_OUT_OF_BOUNDS if the max_orbit_distance has been reached, CYCLE_LENGTH if the node’s value is found to have occured previously, or CYCLE_INIT, retroactively applied when a CYCLE_LENGTH state node is found.
Public Class Methods
Create an instance of TreeGraphNode
which will yield its entire sub-tree of all child nodes.
@raise FailedSaneParameterCheck
If p or a are 0.
@param Integer
node_value: The value for which to find the tree graph node reversal.
@param Integer
max_orbit_distance: The maximum distance/orbit/branch length to travel.
@param Integer
p: Modulus used to devide n, iff n is equivalent to (0 mod p).
@param Integer
a: Factor by which to multiply n.
@param Integer
b: Value to add to the scaled value of n.
@param +Hash<Integer>+ cycle_check: A hash used to keep track of already graphed values
@param Boolean
create_raw: Used to instruct the initialiser method to take 1:1 inputs, used in testing.
@param SequenceState
terminal_sequence_state:
@param TreeGraphNode
pre_n_div_p_node:
@param TreeGraphNode
pre_an_plus_b_node:
@return [TreeGraphNode] A computed tree graph node
# File lib/collatz/tree_graph.rb, line 55 def initialize(node_value, max_orbit_distance, p, a, b, cycle_check: nil, create_raw: false, terminal_sequence_state: nil, pre_n_div_p_node: nil, pre_an_plus_b_node: nil) @node_value = node_value if create_raw @terminal_sequence_state = terminal_sequence_state @pre_n_div_p_node = pre_n_div_p_node @pre_an_plus_b_node = pre_an_plus_b_node return end # Handle cycle prevention for recursive calls if cycle_check.nil? cycle_check = { @node_value => self } elsif !cycle_check[@node_value].nil? # The value already exists in the cycle so this is a cyclic terminal cycle_check[@node_value].terminal_sequence_state = SequenceState::CYCLE_INIT @terminal_sequence_state = SequenceState::CYCLE_LENGTH @pre_n_div_p_node = nil @pre_an_plus_b_node = nil return else cycle_check[@node_value] = self end if [0, max_orbit_distance].max.zero? @terminal_sequence_state = SequenceState::MAX_STOP_OUT_OF_BOUNDS @pre_n_div_p_node = nil @pre_an_plus_b_node = nil else reverses = Collatz.reverse_function(node_value, p: p, a: a, b: b) @pre_n_div_p_node = TreeGraphNode.new(reverses[0], max_orbit_distance-1, p, a, b, cycle_check: cycle_check) if reverses.length == 2 @pre_an_plus_b_node = TreeGraphNode.new(reverses[1], max_orbit_distance-1, p, a, b, cycle_check: cycle_check) else @pre_an_plus_b_node = nil end end end
Public Instance Methods
This will only confirm an equality if the whole subtree of both nodes, including node values, sequence states, and child nodes, checked recursively, are equal.
@param TreeGraphNode
tgn: The TreeGraphNode
with which to compare equality.
@return Boolean
true, if the entire sub-trees are equal.
# File lib/collatz/tree_graph.rb, line 98 def sub_tree_equals(tgn) return false if self.node_value != tgn.node_value return false if self.terminal_sequence_state != tgn.terminal_sequence_state return false if self.pre_n_div_p_node.nil? && !tgn.pre_n_div_p_node.nil? return false if !self.pre_n_div_p_node.nil? && !self.pre_n_div_p_node.sub_tree_equals(tgn.pre_n_div_p_node) return false if self.pre_an_plus_b_node.nil? && !tgn.pre_an_plus_b_node.nil? return false if !self.pre_an_plus_b_node.nil? && !self.pre_an_plus_b_node.sub_tree_equals(tgn.pre_an_plus_b_node) true end