Entries Tagged 'Ruby' ↓

Binary trees are a data structure that I first encountered in a Turbo Pascal course. Later encounters with trees, not necessarily binary in nature, involved primitive text file compression. Binary means having two of something. Binary numbers have one of two values: 0 or 1. Binary trees can have up to two children, a left and a right child. Like Tarzan swinging from vine to vine, there are different ways to leap from one node to another on a binary tree. Well, there are three different ways: preorder, inorder, and postorder transversals.

We will need a binary tree to work with. In my explanations below, I’ll use the following binary tree, referring to the circles with numbers in them as nodes. For example, node 5 is the topmost circle or the root of the binary tree. The two trees with children are outlined as Tree 1 and Tree 2 for easier explanation.

All three transversals explore the left subtree followed by the right subtree. However, the order in which the current node is display differs in each transversal.

Preorder. I’ll start with a preorder transversal first which is also known as a depth first transversal, charting the descent to the depths of the binary tree. The preorder transversal displays the contents of the current node prior to transversing any children. Each time that a new node is visited, the steps of the algorithm start from the beginning.

Display this node.
Visit the left child, transversing that tree.
Visit the right child, transversing that tree.

The transversal begins at the root of the tree, node 5.

1. Display node 5

Tree 2:

1. We haven’t visited the left child. Go left to node 10.
2. Display node 10.
3. We haven’t visited the left child. Display node 20.
4. At node 20, we can neither go left nor right. Climb up to node 10.
5. We haven’t visited the right child. Display node 25.
6. Climb up to node 10.

Tree 1:

1. Since we’ve visited both children at node 10, climb up to node 5.
2. We haven’t visited the right child. Display node 15.

The output of the preorder transversal would be: 5, 10, 20, 25, 15.

Inorder. The inorder transversal explores the left subtree, prior to display the current node. Then, the right subtree is explored.

Visit the left child, transversing that tree.
Display this node.
Visit the right child, transversing that tree.

The transversal begins at node 5.

1. We haven’t visited the left child. Go left to node 10.

Tree 2:

1. We haven’t visited the left child. Go left to node 20.
2. At node 20, we can neither go left nor right. Display node 20.
3. Climb up to node 10.
4. We already been to the left child. Display node 10.
5. We haven’t visited the right child. Go right to node 25.
6. At node 25, we’ve reached another leaf (childless) node. Display node 25.
7. Climb up to node 10.

Tree 1:

1. Climb up to node 5.
2. Since we’ve already visited the left child, display node 5.
3. We have not go to the right child. Go right to node 15.
4. Display node 15.

The output of the preorder transversal would be: 20, 10, 25, 5, 15.

Postorder. This is the easiest to conceptualize for me. You transverse the left subtree, transverse the right subtree, and then display the current node’s value.

Visit the left child, transversing that tree.
Visit the right child, transversing that tree.
Display this node.

Using the example above, the transversal begins at node 5.

1. We haven’t visited the left child. Go left to node 10.

Enter Tree 2:

1. We haven’t visited the left child. Go left to node 20.
2. At node 20 we can’t go left nor right. Display node 20.
3. Climb up to node 10, go right to node 25.
4. At node 25 we can’t go left nor right. Display node 25.
5. Climb up to node 10. We’ve already visited both children. Display node 10.

Enter Tree 1:

1. Climb up to node 5.
2. We’ve visited the child to the left of node 5, but we haven’t visited node 15. Go right to node 15.
3. At node 15 we can’t go left or right. Display node 15.
4. Climb up to node 5.
5. We’ve visited both children. Display node 5.

The output of this transversal would be: 20, 25, 10, 15, 5.

Now, that the dry explanation is done, it’s time to dust-off some of the Ruby code that I’ve written last year.

First, we have an implementation of a binary tree node. The object has the ability to hold a node value, a left node, and a right child.

File: BinaryTreeNode.rb

# This is an implementation of a binary tree node,
# a primitive data structure.
class BinaryTreeNode
  attr_writer :value, :left, :right
  attr_reader :value, :left, :right

  # Constructor for a BinaryTreeNode
  #
  # [value] The value of the node
  # [left] The left child node.
  # [right] The right child node.
  def initialize(value, left = nil, right = nil)
    @value = value
    @left = left
    @right = right
  end

  # Display the value of the node.
  def to_s
    return @value
  end

  # Determines if a left child exists.
  def hasLeft
    has_left = false

    if (@left != nil) then
      has_left = true
    end
  end

  # Determines if a right child exists.
  def hasRight
    has_right = false

    if (@right != nil) then
      has_right = true
    end
  end

  # Determines if this node has no children.
  def isLeaf
    is_leaf = false

    if ((@left == nil) && (@right == nil)) then
      is_leaf = true
    end

    return is_leaf
  end
end

Next, here’s the class that transverses the binary tree. It has the ability to do preorder, inorder, and postorder transversals.

File: BinaryTreeTransverser.rb

require('BinaryTreeNode')

# Responsible for transversing a binary tree
class BinaryTreeTransverser

  # Follows a recursive preorder transveral
  # [node] The node to begin the transversal
  # [transveralArray] An array of node values transversed
  def preorder(node, transversalArray)
    transversalArray.push(node.to_s)

    if (node.hasLeft) then
      preorder(node.left, transversalArray)
    end

    if (node.hasRight) then
      preorder(node.right, transversalArray)
    end
  end

  # Follows a recursive inorder transveral
  # [node] The node to begin the transversal
  # [transveralArray] An array of node values transversed
  def inorder(node, transversalArray)
    if (node.hasLeft) then
      inorder(node.left, transversalArray)
    end

    transversalArray.push(node.to_s)

    if (node.hasRight) then
      inorder(node.right, transversalArray)
    end
  end

  # Follows a recursive postorder transversal
  # [node] The node to begin the transversal
  # [transveralArray] An array of node values transversed
  def postorder(node, transversalArray)
    if (node.hasLeft) then
      postorder(node.left, transversalArray)
    end

    if (node.hasRight) then
      postorder(node.right, transversalArray)
    end

    transversalArray.push(node.to_s)
  end

end

Finally, here are the unit test cases ensuring that each transversal operates correctly. As it turns out, I didn’t assemble the test tree correctly, leading to the unit tests not passing.

File: BinaryTreeTransverserTest.rb

require 'test/unit'
require 'BinaryTreeNode'
require 'BinaryTreeTransverser'

# Tests pre, post, and inorder binary tree transversals
class BinaryTreeTransverserTest < Test::Unit::TestCase

  # Creates a binary tree to test with
  def setup
    @test_tree = nil;

    # Time to practice my ASCII art skills.
    # The first four trees will be the legs of our tree.
    #
    #     A
    #   /   \
    #  5     8
    leftLeaf = BinaryTreeNode.new(5, nil, nil)
    rightLeaf = BinaryTreeNode.new(8, nil, nil)
    nodeA = BinaryTreeNode.new('A', leftLeaf, rightLeaf)

    #     B
    #   /
    #  20
    leftLeaf = BinaryTreeNode.new(20, nil, nil)
    nodeB = BinaryTreeNode.new('B', leftLeaf, nil)

    #     C
    #      \
    #       4
    rightLeaf = BinaryTreeNode.new(4, nil, nil)
    nodeC = BinaryTreeNode.new('C', nil, rightLeaf)

    #     D
    #   /   \
    #  12    42
    leftLeaf = BinaryTreeNode.new(12, nil, nil)
    rightLeaf = BinaryTreeNode.new(42, nil, nil)
    nodeD = BinaryTreeNode.new('D', leftLeaf, rightLeaf)

    # Constructs the rest of the tree.
    #
    #                       R
    #                     /   \
    #                  L         M
    #                /  \      /
    #              Z     X    W
    #             / \   / \
    #            A   B C   D
    #           /|  /   \  | \
    #          5 8 20    4 12 42
    nodeZ = BinaryTreeNode.new('Z', nodeA, nodeB)
    nodeX = BinaryTreeNode.new('X', nodeC, nodeD)
    nodeW = BinaryTreeNode.new('W', nil, nil)
    nodeL = BinaryTreeNode.new('L', nodeZ, nodeX)
    nodeM = BinaryTreeNode.new('M', nodeW, nil)

    # The root node of the tree which all test case
    # will test against
    @rootNode = BinaryTreeNode.new('R', nodeL, nodeM)
  end

  # Tests a preorder transveral
  def testPreorder
    correctPreorder = ['R', 'L', 'Z', 'A', 5, 8, 'B', 20, 'X', 'C', 4, 'D', 12, 42, 'M', 'W']
    testTransversal = Array.new
    BinaryTreeTransverser.new.preorder(@rootNode, testTransversal) 

    assert_equal(correctPreorder, testTransversal)
  end

  # Tests an inorder transversal
  def testInorder
    correctPreorder = [5, 'A', 8, 'Z', 20, 'B', 'L', 'C', 4, 'X', 12, 'D', 42, 'R', 'W', 'M']
    testTransversal = Array.new
    BinaryTreeTransverser.new.inorder(@rootNode, testTransversal)

    assert_equal(correctPreorder, testTransversal)
  end

  # Tests a postorder transversal
  def testPostorder
    correctPostorder = [5, 8, 'A', 20, 'B', 'Z', 4, 'C', 12, 42, 'D', 'X', 'L', 'W', 'M', 'R']
    testTransversal = Array.new
    BinaryTreeTransverser.new.postorder(@rootNode, testTransversal)

    assert_equal(correctPostorder, testTransversal)
  end

end

My first step to creating a hello-world style Rails application involves using a database. Using PHP on a regular basis and being the type of person that tries to use a tool without reading the instructions first, I jump into a MySQL console and create a table to work with.

mysql> create table newsletter_subscribers (
email varchar(150) primary key,
created timestamp default now()
);

After reading several Rail database tutorials, there’s a better way of doing this. Rails provides a Migration class which will do the database dirty work for you.

First create a project to work with. I called my project newsletter.

rails newsletter

This creates a bunch of files and places it in a directory called newsletter. Now, I want to programmatically create a database table called subscribers.

cd newsletter
ruby script/generate model subscriber

The last line of output that Ruby generates is of particular interest.

create test/unit/subscriber_test.rb
create test/fixtures/subscribers.yml
create db/migrate
create db/migrate/001_create_subscribers.rb

Editing the 001_create_subscribers.rb file, I’ll add the columns that I want. Keep in mind that this doesn’t match the CREATE TABLE MySQL example that I used at the beginning on this entry.

class CreateSubscribers < ActiveRecord::Migration
  # Initial table setup in this migration
  def self.up
    # Create a subscribers table
    # Most documentation recommends making naming
    # tables using the plural form of the word
    create_table :subscribers do |table|
      # Declare an email field as a string
      table.column :email, :string,
                   # Restrict the size to 150 characters
                   :limit => 150,
                   # The field cannot have a null value
                   :null => false
      # Declare a join_timestamp as a datetime value
      table.column :join_timestamp, :datetime,
                   :null => false
    end

    # Create an index on the email field
    # Enforce that email addresses are unique
    add_index :subscribers, :email, :unqiue => true
  end

  # Undo this migration
  def self.down
    drop_table :subscribers
  end
end

Personally, I never encountered using an object in a programming language to create a table before. The idea behind this from what I’ve read allows incremental table, or schema, changes. If I wanted to rename a column, this infrastructure supports it. I’m not going to delve into that at this time since I’m trying to create my first table.

I’ll create a database in MySQL for this project. Ruby will programmatically create the table for me, but it will not create the database for the table. The convention that Ruby uses is project name_development for the development version of this database. Since I called this project newsletter, I’ll create a newsletter_development database.

mysqladmin -u root -p create newsletter_development

Next, I’ll use the rake command (where do they come up with these names), to migrate the changes.

rake db:migrate

The table is created, generating the following output.

== CreateSubscribers: migrating ===============================
– create_table(:subscribers)
-> 0.0149s
– add_index(:subscribers, :email, {:unqiue=>true})
-> 0.0196s
== CreateSubscribers: migrated (0.0349s) ======================

Jumping into the MySQL console, let’s see definition of the subscribers table.

mysql> use newsletter_development;
mysql> describe subscribers;

The two columns that I defined in the CreateSubscribers object are in this table. There is an additional column, id, which I did not define. To quote my Rails book: “Rails really doesn’t work too well unless each table has a numeric primary key…My strong advice is to go with the flow and let Rails have its id column.”

In the event that I wanted to undo the first step of migration, I would revert to version zero by typing.

rake db:migrate VERSION=0

Ruby will revert to the original state, dropping the table that I created in my first revision.

== CreateSubscribers: reverting ===============================
– drop_table(:subscribers)
-> 0.0035s
== CreateSubscribers: reverted (0.0037s) ======================

One strong point of unit tests is when modifications are made to code, a unit test can quickly ensure that a function or method is not broken. In my past work experience, developing unit tests aren’t put into practice. Typically, the following happens:

1. I make a code change.
2. I test the code change from an end-user standpoint to verify that the change works as expected.
3. A person from the testing or quality assurance department verifies that the change works as expected.

One of the main challenges in modifying existing complicated code is you could inadvertently impact another piece of the application that uses a function or method in a negative manner no matter how careful you are. In scenarios where this negative impact is undetected, more time is spent rolling back (undoing) the code change, correcting corrupted data, and redeploying another correction. Creating and using unit tests are another safeguard in preventing unwanted, time wasting, situations like this. In more extreme cases, if a method or function is completely rewritten, a unit test case can quickly confirm that the revised code is working as desired.

Below, I’ve created a test case for a function that generates an array of Fibonacci numbers. Refer to my previous blog entry for more information about it.

require 'test/unit'
# File that holds the generate_fibonacci_seq method
require 'fib.rb'

# Unit test cases for a function which computes Fibonacci numbers
# Refer to my previous blog entry for more details concerning
# the implementation of generate_fibonacci_seq
class FibTest < Test::Unit::TestCase

  # Initializes instance variable(s) used for each test case.
  # Before a unit test case method is run, setup() is invoked.
  def setup
    # A correct computation of the first 32 Fibonacci numbers from
    # obtained from another website
    @correct_fibonacci_seq = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,
                              233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946,
                              17711, 28657, 46368, 75025, 121393, 196418, 317811,
                              514229, 832040, 1346269]
  end

  # Tests the validity of the first 32 Fibonacci numbers
  def test_fibonacci_seq_32
    test_array = generate_fibonacci_seq(31)

    # Ensure that the generated array contains 32 numbers
    if (test_array.size != 32) then
      flunk("Generated Fibonacci sequence must contain 32 numbers.")
    end

    i = 0
    for test_element in test_array
      # Displays a custom output messag showing which index in the array
      # did not match
      assert_equal(test_element, @correct_fibonacci_seq[i],
                   "Item at element " + i.to_s + " did not match.")
      i = i + 1
    end
  end

  # Tests the scenario when a user enters a negative number
  # into generate_fibonacci_seq()
  def test_fibonacci_seq_neg
    test_array = generate_fibonacci_seq(-1)

    assert_equal(test_array, Array.new)
  end

  # Tests the scenario when a user enters a zero
  # into generate_fibonacci_seq()
  def test_fibonacci_seq_0
    test_array = generate_fibonacci_seq(0)

    assert_equal(test_array, [0])
  end

  # Spot checks the a few Fibonacci numbers
  def test_fibonacci_seq_at_100
    test_array = generate_fibonacci_seq(99)

    # Ensure that the generated array contains 100 numbers
    if (test_array.size != 100) then
      flunk("Generated Fibonacci sequence must contain at 100 numbers.")
    end

    # Test that the hundredth number is correct
    assert_equal(test_array[99], 218922995834555169026)

    # Test that number 75 is correct
    assert_equal(test_array[74], 1304969544928657)

    # Test that number 42, the meaning of life, is correct
    assert_equal(test_array[41], 165580141)
  end

end

One amusing thing about creating test cases is that there’s a method named flunk to flag that a test failed. I use flunk enforce that the size of the arrays are correct.

In the test_fibonacci_seq_32 test case, I manually loop through each element instead of passing in the entire array to assert_equal. This way I can display a custom message stating which index into the array did not match. I found that passing arrays into assert_equal caused a failure to regurgitate both arrays in the output. I didn’t feel like sifting through sixty-four numbers to figure out which two did not match.

The four tests done in this unit test case generates the following output.

Loaded suite FibTest
Started
….
Finished in 0.001782 seconds.

4 tests, 37 assertions, 0 failures, 0 errors

The Fibonacci sequence is a one of those mathematical formulas that I learned in grade school and promptly went in one ear and out the other. This formula solved a rabbit breeding problem that Fibonacci created in one of his works in 1202. Recursive in nature, the formula creates a sequence of numbers where the sum of the last two numbers in the sequence create the next number.

For the first two numbers in the sequence they are defined as follows.

The next number is the sum of the last two numbers in the sequence.

By substituting the first two known numbers, the third number in the sequence would be.

And the fourth number would be.

The following Ruby program computes the Fibonacci sequence, using an array fibonacci_seq to store calculated numbers in the sequence. This makes it easy to compute higher numbers for F(n) where n > 1, as the numbers are easily accessible in the array.

Note: Due to some quirks in the Wordpress’ new sourcecode feature, I am unable to display the less-than symbol. I’ve had to use the greater-than symbol in conditionals where I wouldn’t normally put them.

# Generates the sequence of Fibonacci numbers starting
# from F(0) and ending at F(_max_amount_) where F is
# the Fibonacci formula.
# [+max_amount+]  The highest fibonacci number to
#                 generate in the sequence.
def generate_fibonacci_seq(max_amount)
  n = 0
  # An array of Fibonacci numbers
  fibonacci_seq = Array.new

  if (max_amount >= 0) then
    while (max_amount >= n)
      if n == 0 then
        # F(0) = 0
        fibonacci_seq.push(0)
      elsif n == 1 then
        # F(1) = 1
        fibonacci_seq.push(1)
      else
        # F(n) = F(n - 2) + F(n - 1)
        last_two_numbers = fibonacci_seq.last(2)
        fibonacci_seq.push(last_two_numbers[0] + last_two_numbers[1])
      end

      n = n + 1
    end
  end

  return fibonacci_seq
end

# Generate the first 32 Fibonacci numbers
fib_seq = generate_fibonacci_seq(31)
puts fib_seq

Ruby Rant: The abbreviated form of the conditional keyword elsif annoys me because other programming languages spell out the phrase as else if. I’d personally prefer being able to switch from one programming language to another without worrying these inconsistencies. One day I’m going to type an elsif in PHP and have my editor flag the conditional keyword as an error.

The output of the first five numbers are:

0
1
1
2
3

I’d prefer to display the number in a list that flows horizontally. The Array class provides a method each which iterates through each element in the array. Ruby provides a nice feature for quickly processing iterators, in this case the iterator is the each method, with a feature known as blocks. A (code) block appears to the right of the iterator method between braces {code_block}.

# Generate the first 32 Fibonacci numbers
fib_seq = generate_fibonacci_seq(31)
fib_seq.each { |element| print "#{element} " }
print "\n"

Within a block, the parameter appears between two pipe symbols |parameter|. In the above example, the parameter is element. To the right of the parameter are instructions for processing the element. For each element that I encounter, I’ll print the element with a trailing space to separate the next number.

Using the each iterator, the output for the first 32 number of the Fibonacci sequence is:

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269

As with any introduction to a programming language, I start off with a simple Hello World program. What takes me a minute to do in a language that I know, takes much longer with one that is foreign to me.

I’ll make this a bit more complicated, asking for the person’s name and telling them hello in my reply.

# Ask the user their name
puts "What is your name?"
user_name = gets

# Cunningly impress them with your response
puts "Hello, #{user_name.capitalize}!"

When I run the program and it asks for my name, I’ll type in Joe.

Output:

What is your name?
joe
Hello, Joe
!

The output of the program is not quite what I envisioned. The exclamation point appears on separate line. When I typed joe and pressed enter, the enter (or newline) is printed in the response. String object provides a method, chomp, that will move unwanted display characters, namely the enter key that I pressed. I’ll call chomp when I receive the input from the gets method.

# Ask the user their name
puts "What is your name?"
# Get the user name and remove newline characters
user_name = gets.chomp

# Cunningly impress them with your response
puts "Hello, #{user_name.capitalize}!"

Running the revised program, I hope that the response appears on one line when I tell the program that my name is Joe.

Output:

What is your name?
joe
Hello, Joe!

There you have it. My first Hello World program written in Ruby.