Class: Collatz::TreeGraphNode

Inherits:
Object
  • Object
show all
Defined in:
lib/collatz/tree_graph.rb

Overview

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.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#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) ⇒ TreeGraphNode

Create an instance of TreeGraphNode which will yield its entire sub-tree of all child nodes.

Parameters:

  • +Integer+ —

    node_value: The value for which to find the tree graph node reversal.

  • +Integer+ —

    max_orbit_distance: The maximum distance/orbit/branch length to travel.

  • +Integer+ —

    p: Modulus used to devide n, iff n is equivalent to (0 mod p).

  • +Integer+ —

    a: Factor by which to multiply n.

  • +Integer+ —

    b: Value to add to the scaled value of n.

  • +Hash (Integer) —

    + cycle_check: A hash used to keep track of already graphed values

  • +Boolean+ —

    create_raw: Used to instruct the initialiser method to take 1:1 inputs, used in testing.

  • SequenceState —

    terminal_sequence_state:

  • TreeGraphNode —

    pre_n_div_p_node:

  • TreeGraphNode —

    pre_an_plus_b_node:

Raises:

  • FailedSaneParameterCheck If p or a are 0.



55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
 
# 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

Instance Attribute Details

#node_value ⇒ Object (readonly)

The value of this node in the tree.



15
16
17
 
# File 'lib/collatz/tree_graph.rb', line 15

def node_value
  @node_value
end

#pre_an_plus_b_node ⇒ Object (readonly)

The “Pre aN+b” TreeGraphNode child of this node that is present if it exists and this is not a terminal node.



28
29
30
 
# File 'lib/collatz/tree_graph.rb', line 28

def pre_an_plus_b_node
  @pre_an_plus_b_node
end

#pre_n_div_p_node ⇒ Object (readonly)

The “Pre N/P” TreeGraphNode child of this node that is always present if this is not a terminal node.



24
25
26
 
# File 'lib/collatz/tree_graph.rb', line 24

def pre_n_div_p_node
  @pre_n_div_p_node
end

#terminal_sequence_state ⇒ Object

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.



20
21
22
 
# File 'lib/collatz/tree_graph.rb', line 20

def terminal_sequence_state
  @terminal_sequence_state
end

Instance Method Details

#sub_tree_equals(tgn) ⇒ Object

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.

Parameters:

  • TreeGraphNode —

    tgn: The TreeGraphNode with which to compare equality.

Returns:

  • Boolean true, if the entire sub-trees are equal.



98
99
100
101
102
103
104
105
106
 
# 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