Class: FractionTree

Inherits:
Object
  • Object
show all
Defined in:
lib/fraction_tree/node.rb,
lib/fraction_tree/fraction_tree.rb

Overview

Author:

  • Jose Hales-Garcia

Defined Under Namespace

Classes: Node

Constant Summary collapse

DEFAULT_TREE_DEPTH = 
20

Class Method Summary collapse

Class Method Details

.child_of(number1, number2) ⇒ FractionTree::Node

Note:

return nil if bc - ad |= 1, for a/b, c/d

Returns the mediant child of the given numbers.

Examples:

FractionTree.child_of(1/1r, 4/3r) => (5/4)
FractionTree.child_of(7/4r, 4/3r) => nil

Parameters:

  • number1 (Rational) —

    one of two parents

  • number2 (Rational) —

    two of two parents

Returns:



171
172
173
174
175
 
# File 'lib/fraction_tree/fraction_tree.rb', line 171

def child_of(number1, number2)
  return nil unless neighbors?(number1, number2)
  # node(number1.numerator, number1.denominator) + node(number2.numerator, number2.denominator)
  node(number1) + node(number2)
end

.decode(str) ⇒ FractionTree::Node

Returns the node decoded from the given string.

Examples:

FractionTree.decode("RLL") => (4/3)

Returns:



101
102
103
104
 
# File 'lib/fraction_tree/fraction_tree.rb', line 101

def decode(str)
  wrk_node = Node.decode(str)
  nodes[wrk_node.number] ||= wrk_node
end

.descendants_of(parent1, parent2, depth: 5) ⇒ Array

Of fraction tree nodes descended from parent1 and parent2 Return empty array if bc - ad |= 1, for a/b, c/d

Examples:

FractionTree.descendants_of(1/1r, 4/3r)
=> [(1/1), (7/6), (6/5), (11/9), (5/4), (14/11), (9/7), (13/10), (4/3)]

Parameters:

  • parent1 (Rational) —

    one of two parents

  • parent2 (Rational) —

    two of two parents

  • depth (Integer) (defaults to: 5) —

    the depth to collect

Returns:

  • (Array) —

    of fraction tree nodes descended from parent1 and parent2 Return empty array if bc - ad |= 1, for a/b, c/d



187
188
189
190
 
# File 'lib/fraction_tree/fraction_tree.rb', line 187

def descendants_of(parent1, parent2, depth: 5)
  return [] unless neighbors?(parent1, parent2)
  sequence(depth:, left_node: Node.new(parent1), right_node: Node.new(parent2))
end

.left_node ⇒ Object

Note:

defaults to Stern-Brocot left-most range, 0

Returns the left-most node of the range of the tree.

Examples:

FractionTree.left_node => 0/1

Returns:

  • the left-most node of the range of the tree



14
15
16
 
# File 'lib/fraction_tree/fraction_tree.rb', line 14

def left_node
  @left_node || 0/1r
end

.left_node=(rhs) ⇒ Object

Set the left-most node of the range of the tree

Examples:

FractionTree.left_node = 1/1r


31
32
33
 
# File 'lib/fraction_tree/fraction_tree.rb', line 31

def left_node=(rhs)
  @left_node = rhs
end

.mediant_sum(n1, n2) ⇒ FractionTree::Node

Returns the mediant sum of the given numbers.

Examples:

FractionTree.mediant_sum(3/2r, 4/3r) => (7/5)

Returns:



110
111
112
 
# File 'lib/fraction_tree/fraction_tree.rb', line 110

def mediant_sum(n1, n2)
  Node.new(n1) + Node.new(n2)
end

.neighbors?(number1, number2) ⇒ Boolean

Note:

Neighbor definition: abs(a * d - b * c) = 1, for a/b, c/d

Note:

Float::INFINITY => 1/0

Returns whether two numbers are neighbors.

Examples:

FractionTree.neighbors?(3/2r, 4/3r) => true
FractionTree.neighbors?(3/2r, 7/4r) => false
FractionTree.neighbors?(2/1r, Float::INFINITY) => true

Parameters:

  • number1 —

    of comparison

  • number2 —

    of comparison

Returns:

  • (Boolean) —

    whether two numbers are neighbors



124
125
126
127
128
 
# File 'lib/fraction_tree/fraction_tree.rb', line 124

def neighbors?(number1, number2)
  (a, b) = number1.infinite? ? [1, 0] : [number1.numerator, number1.denominator]
  (c, d) = number2.infinite? ? [1, 0] : [number2.numerator, number2.denominator]
  (a * d - b * c).abs == 1
end

.node(number) ⇒ FractionTree::Node

Returns the node in the tree representing the given number.

Examples:

FractionTree.node(3/2r) => (3/2)

Returns:



92
93
94
95
 
# File 'lib/fraction_tree/fraction_tree.rb', line 92

def node(number)
  validate(number)
  nodes[number] ||= Node.new(number)
end

.nodes ⇒ Object

Note:

Intended for internal use.

The cache of nodes used for faster lookup



76
77
78
 
# File 'lib/fraction_tree/fraction_tree.rb', line 76

def nodes
  @@nodes ||= {}
end

.numeric_sequence ⇒ Array

Returns of numerators of the fraction tree nodes. Aka the Stern-Brocot sequence.

Examples:

FractionTree.numeric_sequence.take(12)
=> [1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2]

Returns:

  • (Array) —

    of numerators of the fraction tree nodes. Aka the Stern-Brocot sequence.



210
211
212
213
214
215
216
217
218
 
# File 'lib/fraction_tree/fraction_tree.rb', line 210

def numeric_sequence
  return enum_for :numeric_sequence unless block_given?
  a=[1,1]

  0.step do |i|
    yield a[i]
    a << a[i]+a[i+1] << a[i+1]
  end
end

.range ⇒ Object

Note:

defaults to Stern-Brocot range, (0..Infinity)

Returns the range of the tree.

Examples:

FractionTree.range => (0/1..Infinity)

Returns:

  • the range of the tree



48
49
50
 
# File 'lib/fraction_tree/fraction_tree.rb', line 48

def range
  (left_node..right_node)
end

.range=(rhs) ⇒ Object

Note:

Accepts keywords: :farey, :keyboard, :scale_step, :log2 => (0/1..1/1) :stern_brocot, :scale => (0/1..1/0) :octave_reduced => (1/1..2/1)

Set the range of the tree

Examples:

FractionTree.range = :farey
=> (0/1..1/1)


61
62
63
64
65
66
67
68
69
70
71
72
 
# File 'lib/fraction_tree/fraction_tree.rb', line 61

def range=(rhs)
  case rhs
  when :farey, :keyboard, :scale_step, :log2
    @left_node, @right_node = 0/1r, 1/1r
  when :stern_brocot, :scale
    @left_node, @right_node = 0/1r, Float::INFINITY
  when :octave_reduced
    @left_node, @right_node = 1/1r, 2/1r
  else
    @left_node = @right_node = nil
  end
end

.reset_nodes ⇒ Object

Reset the cache of nodes

Examples:

FractionTree.reset_nodes => {}


84
85
86
 
# File 'lib/fraction_tree/fraction_tree.rb', line 84

def reset_nodes
  @@nodes = {}
end

.right_node ⇒ Object

Note:

defaults to Stern-Brocot right-most range, Infinity

Returns the right-most node of the range of the tree.

Examples:

FractionTree.right_node => Infinity

Returns:

  • the right-most node of the range of the tree



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

def right_node
  @right_node || Float::INFINITY
end

.right_node=(rhs) ⇒ Object

Set the right-most node of the range of the tree

Examples:

FractionTree.right_node = 2/1r


39
40
41
 
# File 'lib/fraction_tree/fraction_tree.rb', line 39

def right_node=(rhs)
  @right_node = rhs
end

.sequence(depth: 5, left_node: default_left_node, right_node: default_right_node) ⇒ Array

Returns a sequence of fraction tree nodes.

Examples:

FractionTree.new.sequence(3)
  => [(0/1), (1/3), (1/2), (2/3), (1/1), (3/2), (2/1), (3/1), (1/0)]

Parameters:

  • depth (Integer) (defaults to: 5) —

    the number of iterations of the algorithm to run. The number of nodes returned will be greater

  • left_node (FractionTree::Node) (defaults to: default_left_node) —

    the left starting node

  • right_node (FractionTree::Node) (defaults to: default_right_node) —

    the right starting node

Returns:

  • (Array) —

    a sequence of fraction tree nodes



201
202
203
 
# File 'lib/fraction_tree/fraction_tree.rb', line 201

def sequence(depth: 5, left_node: default_left_node, right_node: default_right_node)
  [left_node]+_sequence(depth:, left_node:, right_node:)+[right_node]
end

.tree(depth: 10, left_node: default_left_node, right_node: default_right_node) ⇒ Array

Returns a multi-dimensional array of fraction tree nodes.

Examples:

FractionTree.tree(depth: 4)
=> [[(0/1), (1/0)],
    [(1/1)],
    [(1/2), (2/1)],
    [(1/3), (2/3), (3/2), (3/1)]]

Parameters:

  • depth (Integer) (defaults to: 10) —

    the depth of the tree

  • left_node (FractionTree::Node) (defaults to: default_left_node) —

    the left starting node

  • right_node (FractionTree::Node) (defaults to: default_right_node) —

    the right starting node

Returns:

  • (Array) —

    a multi-dimensional array of fraction tree nodes



142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
 
# File 'lib/fraction_tree/fraction_tree.rb', line 142

def tree(depth: 10, left_node: default_left_node, right_node: default_right_node)
  Array.new(depth, 0).tap do |sbt|
    row = 0
    sbt[row] = [left_node, right_node]
    i = 2
    while i <= depth do
      figure_from = sbt[0..row].flatten.sort
      new_frow = Array.new(2**(i-2), 0)
      idx = 0
      figure_from.each_cons(2) do |left, right|
        new_frow[idx] = left + right
        idx += 1
      end
      row += 1
      sbt[row] = new_frow
      i += 1
    end
  end
end