CS 214 Lab 11: Ruby

Surprisingly, Ruby does not provide a standard List class, so we will need to build our own.

Begin by making a ruby subdirectory in your labs/11 directory. Then copy the files max.rb and List.rb from the course labs/11/ruby directory into your new directory. Use your favorite text editor to open these files, and take a moment to study their contents.

The file List.rb contains a skeleton for class List. Look over its contents carefully, to get a sense for what has been done, and what remains to be done...

Building A Ruby List Type. Since a list consists of linked nodes, we might begin by creating a Node type that stores an integer and a pointer to a Node:

   class Node 
   end

Find the appropriate comment within the List class and replace it with this declaration.

We can encapsulate class Node by nesting it within List, but Ruby unfortunately does not allow us to actually make a nested class private, which prevents us from truly hiding it. This seems like a curious weakness in Ruby's design.

Node Instance Variables. As we have seen before, Ruby does not require us to declare instance variables; we need only name them in methods. Since our Node class needs two instance variables -- one to store the value and one to store the link to the next node -- we might proceed by defining constructor for our Node class:

   class Node
      def initialize(item, link)
         @value = item
         @next = link
      end
   end

The next question we should consider is this: what kind of access should we provide for these instance variables?

To answer the question, let's examine example methods like append() that create and manipulate Nodes, to see what kind of access they need. There, we can see that we need read access to the @value member, but read and write access to the @next member. Based on this usage, we add these statements to our class:

   class Node
      def initialize(item, link)
         @value = item
         @next = link
      end

      attr_reader :value
      attr_accessor :next
   end

This gives us a Node class that we can use in our List methods, and if necessary, we can always return later and modify it.

List Instance Variables. Switch for a moment to max.rb and note that the program does these things:

it imports our List class,
it constructs empty List objects,
it appends values to them,
it prints them, and
it finds their maximum values.

These provide us with a road map for what we need to do in the remainder of this exercise.

Our next task is thus to define a List constructor. Again referring to the append() method, we see that our List has three instance variables for the constructor to initialize:

@first, a reference to the first node in the list, and
@last, a reference to the last node in the list;
@length, an integer storing the number of values in the list.

In Ruby, nil is the equivalent of null pointer in C++.

Using this information, add an initialize method to the List class that initializes @first and @last to nil and @length to zero.

Then add a statement that creates a reader method for the @length member.

Defining a Print Method. To display the values in a List, we will write a method that traverses the list, displaying each of its values in turn. In List.rb, scan through its contents until you reach the documentation for the print method. There, we can create a stub method named print, that satisfies the specification given back in the introduction:

   class List 
      ...
      def print
      end
      ...
   end

To fill in this stub, we can use the following algorithm to traverse the List:

   1. Define a local variable named temp
      and initialize it to refer to the first node.
   2. While temp is not nil:
       a. Display the value of temp's node.
       b. Advance temp to the next node (if any).

Ruby does not have pointer variables as a distinct type like C++. Instead, it is more like Java, in that variables that refer to objects (i.e., instances of classes) are reference or pointer variables under the hood. Unlike Java, Ruby has no primitive types, so all Ruby types are classes, which means that all Ruby variables are really pointers. So Ruby does not require us to do anything unusual to define, initialize, assign or compare pointer variables/values other than what we have seen previously. Using this information, we can declare temp, and initialize it to the address of our first node, which is stored in @first:

   class List 
      ...
      def print
         temp = @first
      end
      ...
   end

To perform step 2 of our algorithm, we can use Ruby's pretest loop. For its condition, we can use the nil? method -- a message that can be sent to any Ruby object -- which returns true if the object's value is nil and returns false otherwise. We can thus construct a loop to traverse our List as follows:

   class List 
      ...
      def print
         temp = @first
         while !temp.nil?
         end
      end
      ...
   end

Within this loop, we can add statements to display the value member of the node pointed to by temp, and to change the value of temp to the value of the next member of the node to which temp points. Since using print to display a Node's value would be a recursive call and produce a runaway recursion, we will use Ruby's printf statement instead:

   class List 
      ...
      def print
         temp = @first
         while !temp.nil?
            printf " #{temp.value}"
            temp = temp.next
         end
      end
      ...
   end

Note that the expression

   temp.item

is actually invoking the reader method for class Node's @item member that we defined using the attr_reader statement. Likewise, the expression:

   temp = temp.next

is invoking the reader method for class Node's @next member that we defined using the attr_accessor statement.

If we have not made any mistakes, our method to display the values in a List should now be complete, and you should be able to run the program in max.rb to test what you have done thus far.

Finding the Maximum Value in a List. If necessary take a moment to review the specification for this operation. To find the maximum value in a list, we can use this algorithm:

   1. Initialize a variable named temp to the address of our first node.
   2. Initialize maxValue to a very negative integer (e.g., -999999).
   3. While temp is not nil:
       a. If the value of temp's node is greater than maxValue,
             Change maxValue to the value of temp's node.
       b. Advance temp to the next node (if any).
   4. Return maxValue.

Using everything you have learned thus far, find the documentation for the max method within class List. There, define a Ruby method that implements this algorithm.

Testing. To test the correctness of your work, uncomment the lines in max.rb that invoke the max method. Save your changes, run max.rb, and continue when everything works correctly.

Turn In. When all is correct, create a script file in which you (i) run your program to show that it works correctly, and (ii) use cat to display the contents of each of your two .rb files.

That concludes the Ruby part of this lab.

If this was your last exercise, return to the lab 11 page and follow the "Turn In" instructions there.

Calvin > CS > 214 > Labs > 11 > Ruby

This page maintained by Joel Adams.