The Ruby Way, by Hal E. Fulton
pub. Sams Publishing, 2001
Sample Chapter


Chapter 3
Manipulating Structured Data
All parts should go together without forcing. You must remember that the parts you are reassembling were disassembled by you. Therefore, if you can't get them together again, there must be a reason. By all means, do not use a hammer.
— IBM maintenance manual (1925)

Simple variables are not adequate for real-life programming. Every modern language supports more complex forms of structured data and also provides mechanisms for creating new abstract data types.

Historically, arrays are the earliest known and most widespread of the complex data structures. Long ago, in FORTRAN, they were called subscripted variables; today they have changed somewhat, but the basic idea is the same in all languages.

More recently, the hash has become an extremely popular programming tool. Like the array, it is an indexed collection of data items; unlike the array, it may be indexed by any arbitrary object. (In Ruby, as in most languages, array elements are accessed by a numerical index.)

Finally, we look at more advanced data structures. Some of these are just special "views" of an array or hash; for example, stacks and queues can be implemented easily using arrays. Other structures such as trees and graphs may be implemented in different ways according to the situation and the programmer's preference.

But let's not get ahead of ourselves. We will begin with arrays.

3.1 Working with Arrays

Arrays in Ruby are indexed by integers and are zero-based, just like C arrays. There the resemblance ends, however.

A Ruby array is dynamic. It is possible (but not necessary) to specify its size when you create it. After creation, it can grow as needed without any intervention by the programmer.

A Ruby array is heterogeneous in the sense that it can store multiple data types rather than just one type. Actually it stores object references rather than the objects themselves, except in the case of immediate values such as Fixnums.

An array keeps up with its own length so that we don't have to waste our time with calculating it or keeping an external variable in sync with the array. There are also iterators defined so that, in practice, we rarely need to know the array length anyway.

Finally, the Array class in Ruby provides arrays with many useful functions for accessing, searching, concatenating, and otherwise manipulating arrays. We'll spend the remainder of this section exploring the built-in functionality and expanding on it.

3.1.1 Creating and Initializing an Array

The special class method [] is used to create an array; the data items listed in the brackets are used to populate the array. The three ways of calling this method are shown below. (Arrays a, b, and c will all be populated identically.)

    a = Array.[](1,2,3,4)
    b = Array[1,2,3,4]
    c = [1,2,3,4]

There is also a class method called new that can take 0, 1, or 2 parameters. The first parameter is the initial size of the array (number of elements). The second parameter is the initial value of each of the elements.

    d =              # Create an empty array
    e =           # [nil, nil, nil]
    f =, "blah")   # ["blah", "blah", "blah"] 

3.1.2 Accessing and Assigning Array Elements

Element reference and assignment are done using the class methods [] and []= respectively. Each can take an integer parameter, a pair of integers (start and length), or a range. A negative index counts backward from the end of the array, starting at -1.

There is also a special instance method at that works like the simple case of element reference. Since it can take only a single integer parameter, it is slightly faster.

    a = [1, 2, 3, 4, 5, 6]
    b = a[0]                # 1
    c =             # 1
    d = a[-2]               # 5
    e =            # 5
    f = a[9]                # nil
    g =             # nil
    h = a[3,3]              # [4, 5, 6]
    i = a[2..4]             # [3, 4, 5]
    j = a[2...4]            # [3, 4]
    a[1] = 8                # [1, 8, 3, 4, 5, 6]
    a[1,3] = [10, 20, 30]   # [1, 10, 20, 30, 5, 6]
    a[0..3] = [2, 4, 6, 8]  # [2, 4, 6, 8, 5, 6]
    a[-1] = 12              # [2, 4, 6, 8, 5, 12]

Note in the following example how a reference beyond the end of the array causes the array to grow. Note also that a subarray can be replaced with more elements than were originally there, also causing the array to grow.

    k = [2, 4, 6, 8, 10]
    k[1..2] = [3, 3, 3]     # [2, 3, 3, 3, 8, 10]
    k[7] = 99               # [2, 3, 3, 3, 8, 10, nil, 99]

Finally, we should mention that an array assigned to a single element will actually insert that element as a nested array (unlike an assignment to a range).

    m = [1, 3, 5, 7, 9]
    m[2] = [20, 30]         # [1, 3, [20, 30], 7, 9]
    # On the other hand...
    m = [1, 3, 5, 7, 9]
    m[2..2] = [20, 30]      # [1, 3, 20, 30, 7, 9]

The method slice is simply an alias for the [] method.

    x = [0, 2, 4, 6, 8, 10, 12]
    a = x.slice(2)               # 4
    b = x.slice(2,4)             # [4, 6, 8, 10]
    c = x.slice(2..4)            # [4, 6, 8]

The special methods first and last will return the first and last elements of an array, respectively. They will return nil if the array is empty.

    x = %w[alpha beta gamma delta epsilon]
    a = x.first      # "alpha"
    b = x.last       # "epsilon"

We have seen that some of the element-referencing techniques actually can return an entire sub-array. There are other ways to access multiple elements, which we'll look at now.

The method indices will take a list of indices (or indexes, if you prefer) and return an array consisting of only those elements. It can be used where a range cannot (when the elements are not all contiguous). There is an alias called indexes.

    x = [10, 20, 30, 40, 50, 60]
    y = x.indices(0, 1, 4)        # [10, 20, 50]
    z = x.indexes(2, 10, 5, 4)    # [30, nil, 60, 50]

3.1.3 Finding an Array's Size

The method length or its alias size will give the number of elements in an array. Note that this is one less than the index of the last item.

    x = ["a", "b", "c", "d"]
    a = x.length               # 4
    b = x.size                 # 4

The method nitems is the same except that it does not count nil elements.

    y = [1, 2, nil, nil, 3, 4]
    c = y.size                 # 6
    d = y.length               # 6
    e = y.nitems               # 4

3.1.4 Comparing Arrays

Comparing arrays is slightly tricky. If you do it at all, you should do it with caution.

The instance method <=> is used to compare arrays. It works the same as in the other contexts in which it is used, returning either -1 (meaning "less than"), 0 (meaning "equal"), or 1 (meaning "greater than"). The methods == and != depend on this method.

Arrays are compared in an "elementwise" manner; the first two elements that are not equal will determine the inequality for the whole comparison. (Thus preference is given to the leftmost elements, just as if we were comparing two long integers "by eye," looking at one digit at a time.)

    a = [1, 2, 3, 9, 9]
    b = [1, 2, 4, 1, 1]
    c = a <=> b            # -1 (meaning a < b)

If all elements are equal, the arrays are equal. If one array is longer than another, and they are equal up to the length of the shorter array, the longer array is considered to be greater.

    d = [1, 2, 3]
    e = [1, 2, 3, 4]
    f = [1, 2, 3]
    if d == f
      puts "d equals f"   # Prints "d equals f"

Because the Array class does not mix in the Comparable module, the usual operators <, >, <=, and >= are not defined for arrays. But we can easily define them ourselves if we choose:

    class Array
      def <(other)
        (self <=> other) == -1
      def <=(other)
        (self < other) or (self == other)
      def >(other)
        (self <=> other) == 1
      def >=(other)
        (self > other) or (self == other)

And having defined them, we can use them as you would expect:

    if a < b
      print "a < b"       # Prints "a < b"
      print "a >= b"
    if d < e
      puts "d < e"        # Prints "d < e"

It is conceivable that comparing arrays will result in the comparison of two elements for which <=> is undefined or meaningless. This will result in a runtime error (a TypeError) since the comparison 3 <=> "x" is problematic.

    g = [1, 2, 3]
    h = [1, 2, "x"]
    if g < h             # Error!
      puts "g < h"       # No output

However, in case you are still not confused, equal and not-equal will still work in this case. This is because two objects of different types are naturally considered to be unequal even though we can't say which is greater or less than the other.

    if g != h             # No problem here.
      puts "g != h"       # Prints "g != h"

Finally, it is conceivable that two arrays containing mismatched data types will still compare with < and > operators. In the case shown here, we get a result before we stumble across the incomparable elements.

    i = [1, 2, 3]
    j = [1, 2, 3, "x"]
    if i < j             # No problem here.
      puts "i < j"       # Prints "i < j"

3.1.5 Sorting an Array

The easiest way to sort an array is to use the built-in sort method.

    words = %w(the quick brown fox)
    list = words.sort  # ["brown", "fox", "quick", "the"]
    # Or sort in place:
    words.sort!        # ["brown", "fox", "quick", "the"]

This method assumes that all the elements in the array are comparable with each other. A mixed array like [1, 2, "three", 4] will normally give a type error.

In a case like this one, you can use the block form of the same method call. The example here assumes that there is at least a to_s method for each element (to convert it to a string).

    a = [1, 2, "three", "four", 5, 6]
    b = a.sort {|x,y| x.to_s <=> y.to_s}
    # b is now [1, 2, 5, 6, "four", "three"]

Of course, such an ordering (in this case, depending on ASCII) may not be meaningful. If you have such a heterogeneous array, you may want to ask yourself why you are sorting it in the first place or why you are storing different types of objects.

This technique works because the block returns an integer (-1, 0, or 1) on each invocation. When a -1 is returned, meaning that x is less than y, the two elements are swapped. Thus, to sort in descending order, we could simply swap the order of the comparison.

    x = [1, 4, 3, 5, 2]
    y = x.sort {|a,b| b <=> a}    # [5, 4, 3, 2, 1]

The block style can also be used for more complex sorting. Let's suppose we want to sort a list of book and movie titles in a certain way: We ignore case; we ignore spaces entirely; and we want to ignore any certain kinds of embedded punctuation. In Listing 3.1 we present a simple example. (Both English teachers and computer programmers will be equally confused by this kind of alphabetizing.)

Listing 3.1: Specialized Sorting

    titles = ["Starship Troopers",
              "A Star is Born",
              "Star Wars",
              "Star 69",
              "The Starr Report"]
    sorted = titles.sort do |x,y|
      # Delete leading articles
      a = x.sub(/^(a |an |the )/i, "") 
      b = y.sub(/^(a |an |the )/i, "")
      # Delete spaces and punctuation
      a.delete!(" .,-?!")
      b.delete!(" .,-?!")
      # Convert to uppercase
      # Compare a and b
      a <=> b 

    # sorted is now:
    # [ "Star 69", "A Star is Born", "The Starr Report"
    #   "Starship Troopers", "Star Wars"]

This example is not overly useful, and it could certainly be written more compactly. The point is that any arbitrarily complex set of operations can be performed on two operands in order to compare them in a specialized way. (Note, however, that we left the original operands untouched by manipulating copies of them.) This general technique can be useful in many situations, e.g., sorting on multiple keys or sorting on keys that are computed at runtime.

3.1.6 Selecting from an Array by Criteria

Sometimes we want to locate an item or items in an array much as though we were querying a table in a database. There are several ways to do this; the ones we outline here are all mixed in from the Enumerable module.

The detect method will find at most a single element. It takes a block (into which the elements are passed sequentially) and returns the first element for which the block evaluates to a value that is not false.

    x = [5, 8, 12, 9, 4, 30]
    # Find the first multiple of 6
    x.detect {|e| e % 6 == 0 }         # 12
    # Find the first multiple of 7
    x.detect {|e| e % 7 == 0 }         # nil

Of course, the objects in the array can be of arbitrary complexity, as can the test in the block.

The find method is a synonym for detect; the method find_all is a variant that will return multiple elements as opposed to a single element. Finally, the method select is a synonym for find_all.

    # Continuing the above example...
    x.find {|e| e % 2 == 0}            # 8
    x.find_all {|e| e % 2 == 0}        # [8, 12, 4, 30] {|e| e % 2 == 0}          # [8, 12, 4, 30]

The grep method will invoke the relationship operator to match each element against the pattern specified. In its simplest form, it will simply return an array containing the matched elements. Since the relationship operator (===) is used, the so-called pattern need not be a regular expression. (The name grep, of course, comes from the UNIX tool of the same name, historically meaning something like general regular expression pattern-matcher.)

    a = %w[January February March April May]
    a.grep(/ary/)      # ["January, "February"]
    b = [1, 20, 5, 7, 13, 33, 15, 28]
    b.grep(12..24)     # [20, 13, 15]

There is a block form which will effectively transform each result before storing it in the array; the resulting array contains the return values of the block rather than the values passed into the block.

    # Continuing above example...
    # Let's store the string lengths
    a.grep(/ary/) {|m| m.length}     # [7, 8]
    # Let's square each value
    b.grep(12..24) {|n| n*n}         # {400, 169, 225}

The reject method is complementary to select. It excludes each element for which the block evaluates to true. The in-place mutator reject! is also defined.

    c = [5, 8, 12, 9, 4, 30]
    d = c.reject {|e| e % 2 == 0}    # [5, 9]
    c.reject! {|e| e % 3 == 0}
    # c is now [5, 8, 4]

The min and max methods may be used to find the minimum and maximum values in an array. There are two forms of each of these; the first form uses the "default" comparison, whatever that may be in the current situation (as defined by the <=> method). The second form uses a block to do a customized comparison.

    a = %w[Elrond Galadriel Aragorn Saruman Legolas]
    b = a.min                                 # "Aragorn"
    c = a.max                                 # "Saruman"
    d = a.min {|x,y| x.reverse <=> y.reverse} # "Elrond"
    e = a.max {|x,y| x.reverse <=> y.reverse} # "Legolas"

Suppose we wanted to find the index of the minimum or maximum element (assuming it is unique). We could use the index method for tasks such as this.

    # Continuing above example...
    i = a.index a.min     # 2
    j = a.index a.max     # 3

This same technique can be used in other similar situations. However, if the element is not unique, the first one in the array will naturally be the one found.

3.1.7 Using Specialized Indexing Functions

The internals of a language handle the mapping of array indices to array elements through what is called an indexing function. Because the methods that access array elements can be overridden, we can in effect index an array in any way we wish.

For example, in Listing 3.2 we implement an array that is one-based rather than zero-based.

Listing 3.2: Implementing a One-Based Array

    class Array2 < Array
      def [](index)
        if index>0
          raise IndexError
      def []=(index,obj)
        if index>0
          raise IndexError
    x =
    x[0]=1  # Error
    x[-1]=1 # Error

Note that the negative indexing (from the end of an array) is disallowed here. And be aware that if this were a real-life solution, there would be other changes to make, such as the slice method and others. But this gives the general idea.

A similar approach can be used to implement multidimensional arrays (as we shall see in section 3.1.11, "Using Multidimensional Arrays").

It is also possible to implement something like a triangular matrix (Listing 3.3). This is like a special case of a two-dimensional array in which element x,y is always the same as element y,x (so that only one need be stored). This is sometimes useful, for example, in storing an undirected graph (as we shall see toward the end of this chapter).

Listing 3.3: Triangular Matrix

    class TriMatrix
      def initialize
        @store = []
      def [](x,y)
        if x > y
          index = (x*x+x)/2 + y
          raise IndexError
      def []=(x,y,v)
        if x > y
          index = (x*x+x)/2 + y
          @store[index] = v
          raise IndexError
    t =
    t[3,2] = 1
    puts t[3,2]  # 1
    puts t[2,3]  # IndexError

Here we have chosen to implement the matrix so that the row number must be greater than or equal to the column number; we also could have coded it so that the same pair of indices simply mapped to the same element. These design decisions will depend on your use of the matrix.

It would have been possible to inherit from Array, but we thought this solution was easier to understand. The indexing formula is a little complex, but ten minutes with pencil and paper should convince anyone it is correct. There are probably enhancements that could be made to this class to make it truly useful, but we will leave that to the reader.

Also, it is possible to implement a triangular matrix as an array containing arrays which increase in size as the row number gets higher. This is somewhat similar to what we have done in section 3.1.11, "Using Multidimensional Arrays." The only tricky part would be to make sure that a row does not accidentally grow past its proper size.

3.1.8 Implementing a Sparse Matrix

Sometimes we need an array that has very few of its elements defined; the rest of its elements can be undefined (or more often zero). This so-called "sparse matrix" has historically been a waster of memory that led people to seek indirect ways of implementing it.

Of course, in most cases, a Ruby array will suffice, since modern architectures typically have large amounts of memory. An unassigned element will have the value nil, which takes only a few bytes to store.

But on the other hand, assigning an array element beyond the previous bounds of the array also creates all the nil elements in between. For example, if elements 0 through 9 are defined, and we suddenly assign to element 1000, we have in effect caused elements 10 through 999 to spring into being as nil values. If this is unacceptable, you might consider another alternative.

The alternative we have to suggest, however, does not involve arrays at all. If we really need a sparse matrix, a hash might be the best solution. See section 3.2.14, "Using a Hash as a Sparse Matrix."

3.1.9 Using Arrays as Mathematical Sets

Most languages do not directly implement sets (Pascal being one exception). But Ruby arrays have some features that make them usable as sets. We'll present these here, and add a few of our own.

First of all, an array can have duplicate entries. If you specifically want to treat the array as a set, you can remove these (using uniq or uniq!).

The two most basic operations performed on sets are union and intersection. These are accomplished by the | ("or") and & ("and") operators respectively. In accordance with the idea that a set does not contain duplicates, any duplicates will be removed. (This may be contrary to your expectations if you are used to array union and intersection operations in some other language.)

    a = [1, 2, 3, 4, 5]
    b = [3, 4, 5, 6, 7]
    c = a | b            # [1, 2, 3, 4, 5, 6, 7]
    d = a & b            # [3, 4, 5]
    # Duplicates are removed...
    e = [1, 2, 2, 3, 4]
    f = [2, 2, 3, 4, 5]
    g = e & f            # [2, 3, 4]

The concatenation operator + can be used for set union, but it does not remove duplicates.

The - method is a "set difference" operator that will produce a set with all the members of the first set except the ones appearing in the second set. (See section 3.1.12, "Finding Elements in One Array but Not Another").

    a = [1, 2, 3, 4, 5]
    b = [4, 5, 6, 7]
    c = a - b            # [1, 2, 3]
    # Note that the extra items 6 and 7 are irrelevant.
To "accumulate" sets it is possible to use the |= operator; as expected, a |= b simply means a = a | b. Likewise &= can progressively "narrow down" the elements of a set.

There is no exclusive-or defined for arrays, but we can make our own very easily. In set terms, this corresponds to elements that are in the union of two sets but not in the intersection.

    class Array
      def ^(other)
        (self | other) - (self & other)


    x = [1, 2, 3, 4, 5]
    y = [3, 4, 5, 6, 7]
    z = x ^ y            # [1, 2, 6, 7]

To check for the presence of an element in a set, we can use the method include? or member? (essentially an alias mixed in from Comparable).

    x = [1, 2, 3]
    if x.include? 2
      puts "yes"     # Prints "yes"
      puts "no"

Of course, this is a little backward from what we are used to in mathematics, where the operator resembling a Greek epsilon denotes set membership. It is backward in the sense that the set is on the left rather than on the right; we are not asking "Is this element in this set?" but rather "Does this set contain this element?"

Many people will not be bothered by this at all. But if you are used to Pascal or Python (or you have ingrained mathematical inclinations), you may want a different way. We present two options here.

    class Object
      def in(other)
        other.include? self
    x = [1, 2, 3]
    if x
      puts "yes"     # Prints "yes"
      puts "no"

This is still a trifle ugly, but at least the ordering is more familiar. As for making it look "more like an operator," Ruby's amazingly flexible parser allows you to write the expression x instead as 2 .in x or even 2. in x, should we wish to go that far.

For those who can't stand the presence of that period, it is conceivable that we could overload an operator like <= for that purpose. However, something like this should be done with caution.

There has been talk of a Python-like (or Pascal-like) in operator for Ruby. It is no more than talk at this time.

How do we tell whether a set is a subset or a superset of another? There are no built-in methods, but we can do it this way (Listing 3.4).

Listing 3.4: Subset and Superset

    class Array

      def subset?(other)
        self.each  do |x| 
          if !(other.include? x)
            return false

      def superset?(other)


    a = [1, 2, 3, 4]
    b = [2, 3]
    c = [2, 3, 4, 5]

    flag1 = c.subset? a     # false
    flag2 = b.subset? a     # true
    flag3 = c.superset? b   # true

Note that we've chosen the "natural" ordering, i.e., x.subset? y means "Is x a subset of y?" rather than vice versa.

To detect the null set (or empty set), we simply detect the empty array. The empty? method will do this.

The concept of set negation (or complement) depends on the concept of a universal set. Since in practical terms this will vary from one application or situation to another, the best way is the simplest: Define the universe, then do a set difference.

    universe = [1, 2, 3, 4, 5, 6]
    a = [2, 3]
    b = universe - a   # complement of a = [1, 4, 5, 6]

Of course, if you really felt the need, you could define a unary operator (such as - or ~) to do this.

You can iterate through a set just by iterating through the array. The only difference is that the elements will come out in order, which you may not want. To iterate randomly, see Section 3.1.18, "Iterating over an Array."

Finally, we may sometimes want to compute the powerset of a set. This is simply the set of all possible subsets (including the null set and the original set itself). Those familiar with discrete math or especially combinatorics will see that there must be 2n of these subsets. We can generate the powerset as follows (Listing 3.5).

Listing 3.5: Powerset of a Set

    class Array
      def powerset
        num = 2**size
        ps =, [])
        self.each_index do |i|
          a = 2**i
          b = 2**(i+1) - 1
          j = 0
          while j < num-1
            for j in j+a..j+b
              ps[j] += [self[i]]
            j += 1
    x = [1, 2, 3]
    y = x.powerset
    # y is now:
    #   [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

3.1.10 Randomizing an Array

Sometimes we want to scramble an array into a random order. The first example that might come to mind is a card game, but there are other circumstance such as presenting a list of questions to a user in a random order.

To accomplish this task, we can use the rand in the Kernel module. Here we show one way to do this.

  class Array
    def randomize
      arr.collect { arr.slice!(rand arr.length) }
    def randomize!
      result = arr.collect { arr.slice!(rand arr.length) }
      self.replace result
  x = [1, 2, 3, 4, 5]
  y = x.randomize      # [3, 2, 4, 1 ,5]
  x.randomize!         # x is now [3, 5, 4, 1, 2]

The key to understanding this solution is that the slice! method will return the value of an array element and at the same time delete that element from the array (so that it cannot be used again).

There are other ways to perform this operation. If you find a better one, let us know.

If we wanted simply to pick an array element at random (without disallowing duplicates), we could do that as follows.

    class Array
      def pick_random

Finally, we should remember that any time we are using rand, we can generate a predictable sequence (e.g., for testing) simply by seeding with a known seed using srand (see section

3.1.11 Using Multidimensional Arrays

If you want to use multidimensional arrays for numerical purposes, there is an excellent library in the Ruby Application Archive called NArray (by Masahiro Tanaka). If you want to use matrices, there is also the matrix.rb standard library as we mentioned in Chapter 2.

In Listing 3.6 we present a way of handling multidimensional arrays by overloading the [] and []= methods to map elements onto a nested array. The class Array3 presented here will handle three-dimensional arrays in a rudimentary fashion, but it is far from complete.

Listing 3.6: Three-dimensional Array

    class Array3

      def initialize
         @store = [[[]]]

      def [](a,b,c)
        if @store[a]==nil ||
           @store[a][b]==nil ||
          return nil
          return @store[a][b][c]

      def []=(a,b,c,x)
        @store[a] = [[]] if @store[a]==nil
        @store[a][b] = [] if @store[a][b]==nil
        @store[a][b][c] = x


    x =
    x[0,0,0] = 5
    x[0,0,1] = 6
    x[1,2,3] = 99

    puts x[1,2,3]

Note that all we really gain here is the convenience of a "comma" notation [x,y,z] instead of the more C-like [x][y][z]. If the C-style notation is acceptable to you, you can just use nested arrays in Ruby. Another minor benefit is the prevention of the situation in which nil is the receiver for the bracket method.

3.1.12 Finding Elements in One Array but Not Another

This is simpler in Ruby than in many languages. It is a simple "set difference" problem.

    text = %w[the magic words are squeamish ossifrage]
    dictionary = %w[an are magic the them these words]
    # Find potential misspellings
    unknown = text - dictionary   # ["squeamish", "ossifrage"]

3.1.13 Transforming or Mapping Arrays

The collect method (part of Enumerable) is a useful little tool that proves to be a time and labor saver in many circumstances. If you are a Smalltalk programmer, this may be more intuitive than if you come from a C background.

This method simply operates on each element of an array in some arbitrary way to produce a new array. In other words, it "maps" an array onto another array (hence the synonym map).

    x = %w[alpha bravo charlie delta echo foxtrot]
    # Get the initial letters
    a = x.collect {|w| w[0..0]}       # %w[a b c d e f]
    # Get the string lengths
    b = x.collect {|w| w.length}       # [5, 5, 7, 5, 4, 7]
    # map is just an alias
    c = {|w| w.length}           # [5, 5, 7, 5, 4, 7]

The in-place variant collect! (or map!) is also defined.

    x.collect! {|w| w.upcase}
    # x is now %w[ALPHA BRAVO CHARLIE DELTA ECHO FOXTROT]! {|w| w.reverse}

3.1.14 Removing nil Values from an Array

The compact method (or its in-place version compact!) will remove nil values from an array, leaving the rest untouched.

    a = [1, 2, nil, 3, nil, 4, 5]
    b = a.compact     # [1, 2, 3, 4, 5]
    a.compact!        # a is now [1, 2, 3, 4, 5]

3.1.15 Removing Specific Array Elements

It is easy to delete elements from a Ruby array, and there are many ways to do it. If you want to delete one specific element by index, delete_at is a good way:

    a = [10, 12, 14, 16, 18]
    a.delete_at(3)              # Returns 16
    # a is now [10, 12, 14, 18]
    a.delete_at(9)              # Returns nil (out of range)

If you want to delete all instances of a certain piece of data, delete will do the job. It will return the value of the objects deleted or nil if it was not found.

    b = %w(spam spam bacon spam eggs ham spam)
    b.delete("spam")            # Returns "spam"
    # b is now ["bacon", "eggs", "ham"]
    b.delete("caviar")          # Returns nil

The delete method will also accept a block. This may be a little counterintuitive; all that happens is that the block is evaluated (potentially performing a wide range of operations) if the object is not found and the value of the block is returned.

    c = ["alpha", "beta", "gamma", "delta"]
    c.delete("delta") { "Nonexistent" }
    # Returns "delta" (block is never evaulated)
    c.delete("omega") { "Nonexistent" }     
    # Returns "Nonexistent"

The delete_if will pass every element into the supplied block and delete the elements for which the block evaluates to true. It behaves similarly to reject!, except that the latter can return nil when the array remains unchanged.

    email = ["job offers", "greetings", "spam", "news items"]
    # Delete four-letter words
    email.delete_if {|x| x.length==4 }
    # email is now ["job offers", "greetings", "news items"]

The slice! method accesses the same elements as slice, but deletes them from the array as it returns their values.

    x = [0, 2, 4, 6, 8, 10, 12, 14, 16]
    a = x.slice!(2)                          # 4
    # x is now [0, 2, 6, 8, 10, 12, 14, 16]
    b = x.slice!(2,3)                        # [6, 8, 10]
    # x is now [0, 2, 12, 14, 16]
    c = x.slice!(2..3)                       # [12, 14]
    # x is now [0, 2, 16]

The shift and pop methods can be used for deleting array elements. (For more about their intended uses, see the discussion of stacks and queues elsewhere in this chapter.)

    x = [1, 2, 3, 4, 5]
    x.pop                   # Delete the last element
    # x is now [1, 2, 3, 4]
    x.shift                 # Delete the first element
    # x is now [2, 3, 4]

Finally, the clear method will delete all the elements in an array. It is equivalent to assigning an empty array to the variable, but is marginally more efficient.

    x = [1, 2, 3]
    # x is now []

3.1.16 Concatenating and Appending onto Arrays

Very frequently we want to take an array and append an element or another array. There are many ways to do this with a Ruby array.

The "append" operator << will append an object onto an array; the return value is the array itself, so that these operations can be "chained."

    x = [1, 5, 9]
    x << 13        # x is now [1, 5, 9, 13]
    x << 17 << 21  # x is now [1, 5, 9, 13, 17, 21]

Similar to the append are the unshift and push methods, which add to the beginning and end of an array respectively. See section 3.1.17, "Using an Array as a Stack or Queue."

Arrays may be concatenated with the concat method or by using the + and += operators.

    x = [1,2]
    y = [3,4]
    z = [5,6]
    b = y + z         # [3,4,5,6]
    b += x            # [3,4,5,6,1,2]
    z.concat y        # z is now [5,6,3,4]

3.1.17 Using an Array as a Stack or Queue

The basic stack operations are push and pop, which add and remove items at the end of an array. The basic queue operations are shift (which removes an item from the beginning of an array) and unshift (which adds an element to the beginning). The append operator << can also be used to add an item to the end of an array (basically a synonym for push).

Don't get confused. The shift and unshift methods work on the beginning of an array; the push, pop, and << methods work on the end.

For a better discussion of this topic, see section 3.3, "Working with Stacks and Queues."

3.1.18 Iterating over an Array

The Array class has the standard iterator each as is to be expected. However, it also has other useful iterators.

The reverse_each method will iterate in reverse order. It is equivalent to using reverse and then each, but it is faster.

    words = %w(Son I am able she said)
    str = ""
    words.reverse_each { |w| str += "#{w} "}
    # str is now "said she able am I Son "

If we only want to iterate over the indices, we can use each_index. Saying x.each_index is equivalent to saying (0..(x.size-1)).each (i.e., iterating over the range of indices).

The iterator each_with_index (mixed in from Comparable) will pass both the element and the index into the block.

    x = ["alpha", "beta", "gamma"]
    x.each_with_index do |x,i|
      puts "Element #{i} is #{x}"
    # Produces three lines of output

Suppose you wanted to iterate over an array in random order? We show here the iterator random_each (which simply invokes the randomize method from section 3.1.10, "Randomizing an Array").

    class Array
    # Assumes we have defined randomize 
      def random_each
        temp = self.randomize
        temp.each {|x| yield x}
    dwarves = %w(Sleepy Dopey Happy Sneezy Grumpy Bashful Doc)
    list = ""
    dwarves.random_each {|x| list += "#{x} "}
    # list is now:
    # "Bashful Dopey Sleepy Happy Grumpy Doc Sneezy "
    # (Your mileage may vary.)

3.1.19 Interposing Delimiters to Form a String

Frequently we will want to insert delimiters in between array elements in a "fencepost" fashion; that is, we want to put delimiters between the elements, but not before the first one or after the last one. The method join will do this, as will the * operator.

    been_there = ["Veni", "vidi", "vici."]
    journal = been_there.join(", ")        # "Veni, vidi, vici."
    # Default delimiter is space
    letters = ["Phi","Mu","Alpha"]
    musicians = letters.join               # "Phi Mu Alpha"
    people = ["Bob","Carol","Ted","Alice"]
    movie = people * " and "
    # movie is now "Bob and Carol and Ted and Alice"

Note that if we really need to treat the last element differently, perhaps by inserting the word and, we can do it manually.

    list = %w[A B C D E F]
    with_commas = list[0..-2]*", " + ", and " + list[-1]
    # with_commas is now "A, B, C, D, E, and F"

3.1.20 Reversing an Array

To reverse the order of an array, use the reverse or reverse! methods.

    inputs = ["red", "green", "blue"]
    outputs = inputs.reverse          # ["green","blue","red"]
    priorities = %w(eat sleep code)
    priorities.reverse!               # ["code","sleep","eat"]

3.1.21 Removing Duplicate Elements from an Array

If you want to remove duplicate elements from an array, the uniq method (or its in-place mutator uniq!) will do the job.

    breakfast = %w[spam spam eggs ham eggs spam]
    lunch = breakfast.uniq   # ["spam","eggs","ham"]
    breakfast.uniq!          # breakfast has changed now

3.1.22 Interleaving Arrays

Suppose you wanted to take two arrays and "interleave" them so that the new array contained alternating elements from each of the two original ones. There must be a hundred ways to do this. Here is one way.

    a = [1, 2, 3, 4]
    b = ["a", "b", "c", "d"]
    c = []
    a.each_with_index { |x,i| c << x << b[i]}
    # c is now [1, "a", 2, "b", 3, "c", 4, "d"]

3.1.23 Counting Frequency of Values in an Array

There is no count method for arrays as there is for strings (to count the occurrences of each data item). So we create one here.

    class Array
      def count
        self.each{|x| k[x]+=1 }
    meal = %w[spam spam eggs ham eggs spam]
    items = meal.count
    # items is {"ham" => 1, "spam" => 3, "eggs" => 2}
    spams = items["spam"]   # 3

Note that a hash is returned. No pun intended.

3.1.24 Inverting an Array to Form a Hash

An array is used to associate an integer index with a piece of data. But what if you want to invert that association, i.e., associate the data with the index, producing a hash? This method will do just that.

    class Array
      def invert
        self.each_with_index{|x,i| h[x]=i}
    a = ["red","yellow","orange"]
    h = a.invert     # {"orange"=>2, "yellow"=>1, "red"=>0}

3.1.25 Synchronized Sorting of Multiple Arrays

Suppose you wanted to sort an array, but you had other arrays that corresponded with this one on an element-for-element basis. In other words, you don't want to get them out of sync. How would you do this?

The solution we present (in Listing 3.7) will sort an array and gather the resulting set of indices. The list of indices (itself an array) can be applied to any other array to put its elements in the same order.

Listing 3.7: Synchronized Array Sorting

    class Array
      def sort_index
        self.each_with_index{|x,i| d[i]=[x,i]}
        if block_given?
          d.sort {|x,y| yield x[0],y[0]}.collect{|x| x[1]}
          d.sort.collect{|x| x[1]}
      def sort_by(ord=[])
        return nil if self.length!=ord.length
    a = [21, 33, 11, 34, 36, 24, 14]
    p a
    p b=a.sort_index
    p a.sort_by b
    p c=a.sort_index {|x,y| x%2 <=> y%2}
    p a.sort_by c

3.1.26 Establishing a Default Value for New Array Elements

When an array grows and new (unassigned) elements are created, these default to nil values:

    a =
    # a is now ["x", nil, nil, "y"]

What if we want to set those new elements to some other value? As a specific instance of a general principle, we offer the ZArray class in Listing 3.8, which will default new unassigned elements to 0.

Listing 3.8: Specifying a Default for Array Elements

    class ZArray < Array
      def [](x)
        if x > size
          for i in size+1..x
        v = super(x)
      def []=(x,v)
        max = size
        if size - max > 1
          (max..size-2).each do |i|
            self[i] = 0
    num =
    num[1] = 1
    num[2] = 4
    num[5] = 25
    # num is now [0, 1, 4, 0, 0, 25]

3.2 Working with Hashes

Hashes are known in some circles as associative arrays, dictionaries, and by various other names. Perl and Java programmers in particular will be familiar with this data structure.

Think of an array as an entity that creates an association between an index x and a data item y. A hash creates a similar association, with at least two exceptions. Firstly, for an array, x is always an integer; for a hash, it need not be. Secondly, an array is an ordered data structure; a hash typically has no ordering.

A hash key can be of any arbitrary type. As a side effect, this makes a hash a non-sequential data structure. In an array, we know that element 4 follows element 3; but in a hash, the key may be of a type that does not define a real predecessor or successor. For this reason (and others), there is no notion in Ruby of the pairs in a hash being in any particular order.

You may think of a hash as an array with a specialized index, or as a database "synonym table" with two fields, stored in memory. Regardless of how you perceive it, it is a powerful and useful programming construct.

3.2.1 Creating a New Hash

As with Array, the special class method [] is used to create a hash. The data items listed in the brackets are used to form the mapping of the hash.

Six ways of calling this method are shown here. (Hashes a1 through c2 will all be populated identically.)

    a1 = Hash.[]("flat",3,"curved",2)  
    a2 = Hash.[]("flat"=>3,"curved"=>2)
    b1 = Hash["flat",3,"curved",2]     
    b2 = Hash["flat"=>3,"curved"=>2]
    c1 = {"flat",3,"curved",2}         
    c2 = {"flat"=>3,"curved"=>2}
    # For a1, b1, and c1: There must be 
    # an even number of elements.

There is also a class method called new that can take a parameter specifying a default value. Note that this default value is not actually part of the hash; it is simply a value returned in place of nil.

    d =         # Create an empty hash
    e =     # Create an empty hash
    f ="a"=>3) # Create an empty hash
    e["angled"]          # 99
    e.inspect            # {}
    f["b"]               # {"a"=>3} (default value is
                         #   actually a hash itself)
    f.inspect            # {}

3.2.2 Specifying a Default Value for a Hash

The default value of a hash is an object that is referenced in place of nil in the case of a missing key. This is useful if you plan to use methods with the hash value that are not defined for nil. It can be assigned upon creation of the hash or at a later time using the default= method.

All missing keys point to the same default value object, so changing the default value has a side effect.

    a ="missing")  # default value object is "missing"
    a["hello"]               # "missing"
    a["hello"]               # "nothing"
    a["good"] << "bye"       # "nothingbye"
    a.default                # "nothingbye"

There is also a special instance method fetch that raises an IndexError exception if the key does not exist in the Hash object. It takes a second parameter that serves as a default value. Also fetch optionally accepts a block to produce a default value in case the key is not found. This is in contrast to default, since the block allows each missing key to have its own default.

    a = {"flat",3,"curved",2,"angled",5}
    a.fetch("pointed")                   # IndexError
    a.fetch("curved","na")               # 2
    a.fetch("x","na")                    # "na"
    a.fetch("flat") {|x| x.upcase}       # 3
    a.fetch("pointed") {|x| x.upcase}    # "POINTED"

3.2.3 Accessing and Adding Key-value Pairs

Hash has class methods [] and []= just as Array has; they are used much the same way, except that they accept only one parameter. The parameter can be any object, not just a string (although string objects are commonly used).

    a = {}
    a["flat"] = 3        # {"flat"=>3}
    a.[]=("curved",2)    # {"flat"=>3,"curved"=>2}"angled",5)  # {"flat"=>3,"curved"=>2,"angled"=>5}

The method store is simply an alias for the []= method, both of which take two arguments as shown in the example.

The method fetch is similar to the [] method, except that it raises an IndexError for missing keys. It also has an optional second argument (or alternatively a code block) for dealing with default values (see section 3.2.2, "Specifying a Default Value for a Hash").

    a["flat"]        # 3
    a.[]("flat")     # 3
    a.fetch("flat")  # 3
    a["bent"]        # nil

Suppose you are not sure whether the Hash object exists, and you would like to avoid clearing an existing hash. The obvious way is to check whether the hash is defined.

    unless defined? a
    a["flat"] = 3

Another way to do this is:

    a ||= {}
    a["flat"] = 3

The same problem can be applied to individual keys, where you only want to assign a value if the key does not exist.
    a[2]             # 99
    a                # {}
    a[2] ||= 5       # 99
    a                # {}       
    b                # {}
    b[2]             # nil
    b[2] ||= 5       # 5
    b                # {2=>5}

Note that nil may be used as either a key or an associated value.

    b[2]      # nil
    b         # {3=>nil}
    b[2].nil? # true
    b[3].nil? # true
    b         # {3=>nil,nil=>5}
    b[nil]    # 5
    b[b[3]]   # 5

3.2.4 Deleting Key-value Pairs

Key-value pairs of a Hash object can be deleted using clear, delete, delete_if, reject, reject!, and shift.

Use clear to remove all key-value pairs. This is essentially the same as assigning a new empty hash, but marginally faster.

Use shift to remove an unspecified key-value pair. This method returns the pair as a 2-element array, or nil if no keys are left.

    a = {1=>2, 3=>4}
    b = a.shift       # [1,2]
    # a is now {3=>4}

Use delete to remove a specific key-value pair. It accepts a key and returns the value associated with the key removed (if found). If not found, the default value is returned. It also accepts a block to produce a unique default value rather than just a reused object reference.

    a = {1=>1, 2=>4, 3=>9, 4=>16}
    a.delete(3)                     # 9
    # a is now {1=>1, 2=>4, 4=>16}
    a.delete(5)                     # nil in this case
    a.delete(6) { "not found" }     # "not found"

Use delete_if, reject, or reject! in conjunction with the required block to delete all keys for which the block evaluates to true. The method reject uses a copy of the hash, and reject! returns nil if no changes were made.

3.2.5 Iterating over a Hash

The Hash class has the standard iterator each as is to be expected. It also has each_key, each_pair, and each_value. (each_pair is an alias for each.)

    {"a"=>3,"b"=>2}.each do |key, val| 
      print val, " from ", key, "; "    # 3 from a; 2 from b;

The other two provide only one or the other of key or value to the block.

    {"a"=>3,"b"=>2}.each_key do |key| 
      print "key = #{key};"      # Prints: key = a; key = b;

    {"a"=>3,"b"=>2}.each_value do |value| 
      print "val = #{value};"    # Prints: val = 3; val = 2;

3.2.6 Inverting a Hash

Inverting a hash in Ruby is trivial with the invert method.

    a = {"fred"=>"555-1122","jane"=>"555-7779"}
    b = a.invert
    b["555-7779"]     # "jane"

Since hashes have unique keys, there is potential for data loss when doing this: duplicate associated values will be converted to a unique key using only one of the associated keys as its value. There is no predictable way to tell which one will be used.

3.2.7 Detecting Keys and Values in a Hash

Determining whether a key has been assigned can be done with has_key? or any one of its aliases include?, key?, and member?.

    a = {"a"=>1,"b"=>2}
    a.has_key? "c"        # false
    a.include? "a"        # true
    a.key? 2              # false
    a.member? "b"         # true

You can also use empty? to see if there are any keys at all left in the hash. length or its alias size can be used to determine how many there are.

    a.empty?        # false
    a.length        # 2

Alternatively, you can test for the existence of an associated value using has_value? or value?.

    a.has_value? 2        # true
    a.value? 99           # false

3.2.8 Extracting Hashes into Arrays

To convert the entire hash into an array, use the to_a method. In the resulting array, keys will even-numbered elements (starting with 0), and values will be odd-numbered elements of the array.

    h = {"a"=>1,"b"=>2}
    h.to_a        # ["a",1,"b",2]

It is also possible to convert only the keys or only the values of the hash into an array

    h.keys         # ["a","b"]
    h.values       # [1,2]

Finally, you can extract an array of values selectively based on a list of keys, using the indices method. This works for hashes much as the method of the same name works for arrays. There is an alias indexes also.

    h = {1=>"one",2=>"two",3=>"three",4=>"four","cinco"=>"five"}
    h.indices(3,"cinco",4)     # ["three","five","four"]
    h.indexes(1,3)             # ["one","three"]

3.2.9 Selecting Key-value Pairs by Criteria

The Hash class mixes in the Enumerable module, so you can use detect (find), select, (find_all), grep, min, max, and reject as with arrays.

The detect method (alias find) finds a single key-value pair. It takes a block (into which the pairs are passed one at a time) and returns the first pair for which the block evaluates to true.

    names = {"fred"=>"jones","jane"=>"tucker",
    # Find a tucker
    names.detect {|k,v| v=="tucker" }    # ["joe","tucker"]
    # Find a capitalized surname
    names.find {|k,v| v==v.upcase }    # ["mary", "SMITH"]

Of course, the objects in the hash can be of arbitrary complexity, as can the test in the block, but comparisons between differing types can cause problems.

The select method (alias find_all) will return multiple matches as opposed to a single match. {|k,v| v=="tucker" }      
    # [["joe", "tucker"], ["jane", "tucker"]]
    names.find_all {|k,v| k.count("r")>0}  
    # [["mary", "SMITH"], ["fred", "jones"]]

3.2.10 Sorting a Hash

Hashes are by their nature not ordered according to the value of their keys or associated values. In performing a sort on a hash, Ruby converts the hash to an array and then sorts that array. The result is naturally an array.

    names = {"Jack"=>"Ruby","Monty"=>"Python",
             "Blaise"=>"Pascal", "Minnie"=>"Perl"}
    list = names.sort
    # list is now:
    # [["Blaise","Pascal"], ["Jack","Ruby"],
    #  ["Minnie","Perl"], ["Monty","Python"]] 

3.2.11 Merging Two Hashes

Merging hashes may be useful sometimes. Ruby's update method will put the entries of one hash into the target hash, overwriting any previous duplicates.

    dict = {"base"=>"foundation", "pedestal"=>"base"}
    added = {"base"=>"non-acid", "salt"=>"NaCl"}
    # {"base"=>"non-acid", "pedestal"=>"base", "salt"=>"NaCl"}

3.2.12 Creating a Hash from an Array

The easiest way to do this is to remember the bracket notation for creating hashes. This works if the array has an even number of elements.

    array = [2, 3, 4, 5, 6, 7]
    hash = Hash[*array]
    # hash is now: {2=>3, 4=>5, 6=>7}

3.2.13 Finding Difference or Intersection of Hash Keys

Since the keys of a hash can be extracted as a separate array, the extracted arrays of different hashes can be manipulated using the Array class methods & and - to produce the intersection and difference of the keys. The matching values can be generated with the each method performed on a third hash representing the merge of the two hashes (to ensure all keys can be found in one place).

    a = {"a"=>1,"b"=>2,"z"=>3}
    b = {"x"=>99,"y"=>88,"z"=>77} 
    intersection = a.keys & b.keys
    difference = a.keys - b.keys
    c = a.dup.update(b)
    inter = {}
    intersection.each {|k| inter[k]=c[k] }
    # inter is {"z"=>77}
    difference.each {|k| diff[k]=c[k] }
    # diff is {"a"=>1, "b"=>2}

3.2.14 Using a Hash as a Sparse Matrix

Often we want to make use of an array or matrix that is nearly empty. We could store it in the conventional way, but this is often wasteful of memory. A hash provides a way to store only the values that actually exist.

Here is an example. We are assuming here that the nonexistent values should default to zero.

    values =
    values[1001] = 5
    values[2010] = 7
    values[9237] = 9
    x = values[9237]      # 9
    y = values[5005]      # 0

Obviously in the above example, an array would have created over nine thousand unused elements. This may not be acceptable.

What if we want to implement a sparse matrix of two or more dimensions? All we need do is use arrays as the hash keys.

    cube =
    cube[[2000,2000,2000]] = 2
    z = cube[[36,24,36]]       # 0

In this case, we see that literally billions of array elements would need to be created if this three-dimensional array were to be complete.

3.2.15 Implementing a Hash with Duplicate Keys

Purists would likely say that if a hash has duplicate keys, it isn't really a hash. We don't want to argue. Call it what you will, there might be occasions where you wanted a data structure that offered the flexibility and convenience of a hash, but allowed duplicate key values.

We offer a partial solution here (Listing 3.9). It is partial for two reasons. Firstly, we have not bothered to implement all the functionality that could be desired, but only a good representative subset. Secondly, the inner workings of Ruby are such that a hash literal is always an instance of the Hash class; and even though we were to inherit from Hash, a literal would not be allowed to contain duplicates. (We're thinking about this one further.)

But as long as you stay away from the hash-literal notation, this problem is doable. Here we implement a class that has a "store" (@store) which is a simple hash; each value in the hash is an array. We control access to the hash in such a way that when we find ourselves adding a key that already exists, we add the value to the existing array of items associated with that key.

What should size return? Obviously the "real" number of key-value pairs including duplicates. Likewise the keys method returns a value potentially containing duplicates. The iterators behave as expected; as with a normal hash, there is no predicting the order in which the pairs will be visited.

Besides the usual delete, we have implemented a delete_pair method. The former will delete all values associated with a key; the latter will delete only the specified key-value pair. (Note that it would have been difficult to make a single method like delete(k,v=nil) because nil is a valid value for any hash.

For brevity we have not implemented the entire class; and frankly, some of the methods like invert would require some design decisions as to what their behavior should be. The interested reader can flesh out the rest as needed.

Listing 3.9: Hash with Duplicate Keys

    class HashDup 
      def initialize(*all)
        raise IndexError if all.size % 2 != 0
        @store = {}
        if all[0]  # not nil
          keyval = all.dup
          while !keyval.empty?
            key = keyval.shift
            if @store.has_key?(key)
              @store[key] += [keyval.shift]
              @store[key] = [keyval.shift]
      def store(k,v)
        if @store.has_key?(k)
          @store[k] += [v]
          @store[k] = [v]
      def [](key)
      def []=(key,value),value)
      def to_s
      def to_a
      def inspect
      def keys
        @store.each do |k,v|
          result += ([k]*v.size)
      def values
      def each
        @store.each {|k,v| v.each {|y| yield k,y}}
      alias each_pair each
      def each_key
        self.keys.each {|k| yield k}
      def each_value
        self.values.each {|v| yield v}
      def has_key? k
        self.keys.include? k
      def has_value? v
        self.values.include? v
      def length
      alias size length
      def delete k 
        val = @store[k]
        @store.delete k
      def delete k,v
        @store[k] -= [v] if @store[k]
      # Other methods omitted here...
    # This won't work... dup key will ignore 
    # first occurrence.
    h = {1=>1, 2=>4, 3=>9, 4=>16, 2=>0}
    # This will work...
    h =,1, 2,4, 3,9, 4,16, 2,0)
    k = h.keys         # [4, 1, 2, 2, 3]
    v = h.values       # [16, 1, 4, 0, 9]
    n = h.size         # 5
    h.each {|k,v| puts "#{k} => #{v}"}
    # Prints:
    # 4 => 16
    # 1 => 1
    # 2 => 4
    # 2 => 0
    # 3 => 9

3.3 Working with Stacks and Queues

Stacks and queues are the first entities we have discussed that are not strictly built into Ruby. By this we mean that Ruby does not have Stack and Queue classes as it has Array and Hash classes.

And yet, in a way, they are built into Ruby after all. In fact, the Array class implements all the functionality we need to treat an array as a stack or a queue. We'll see this in detail shortly.

A stack is a last-in first-out (LIFO) data structure. The traditional everyday example is a stack of cafeteria trays on its spring-loaded platform; trays are added at the top and also taken away from the top.

There is a limited set of operations that can be performed on a stack. These include push and pop (to add and remove items) at the very least; usually there is a way to test for an empty stack, and there may be a way to examine the top element without removing it. A stack implementation never provides a way to examine an item in the middle of the stack.

You might ask how an array can implement a stack since array elements may be accessed randomly and stack elements may not. The answer is simple. A stack sits at a higher level of abstraction than an array; it is a stack only so long as you treat it as one. The moment you access an element illegally, it ceases to be a stack.

Of course, you can easily define a Stack class so that elements can only be accessed legally. We will show how this is done.

It is worth noting that many algorithms which use a stack also have elegant recursive solutions. The reason for this becomes clear with a moment's reflection. Function or method calls result in data being pushed onto the system stack, and these data are popped upon return. Thus a recursive algorithm simply trades an explicit user-defined stack for the implicit system-level stack. Which is better? That depends on how you value readability, efficiency, and other considerations.

A queue is a first-in first out (FIFO) data structure. It is analogous to a group of people standing in line at (for example) a movie theater. Newcomers go to the end of the line, while those who have waited longest are the next served. In most areas of programming, they are probably used less often than stacks.

Queues are useful in more real-time environments where entities are processed as they are presented to the system. They are useful in producer-consumer situations (especially where threads or multitasking are involved). A printer queue is a good example; print jobs are added to one end of the queue, and they "stand in line" until they are removed at the other end.

The two basic queue operations are usually called enqueue and dequeue in the literature. The corresponding instance methods in the Array class are called shift and unshift respectively.

Note that unshift could serve as a companion for shift in implementing a stack, not a queue, since unshift adds to the same end from which shift removes. There are various combinations of these methods that could implement stacks and queues, but we will not concern ourselves with all the variations.

That ends our introductory discussion of stacks and queues. Now let's look at some examples.

3.3.1 Implementing a Stricter Stack

We promised earlier to show how a stack could be made "idiot-proof" against illegal access. We may as well do that now (Listing 3.10). We present here a simple class that has an internal array and manages access to that array. (There are other ways of doing this— by delegating, for example— but what we show here is simple and works fine.)

Listing 3.10: Stack

    class Stack
      def initialize
        @store = []
      def push(x)
        @store.push x
      def pop
      def peek
      def empty?

We have added one more operation that is not defined for arrays; peek will simply examine the top of the stack and return a result without disturbing the stack.

Some of the rest of our examples will assume this class definition.

3.3.2 Converting Infix to Postfix

In writing algebraic expressions, we commonly use infix notation, with the operator in between the operands. Often it is more convenient to store an expression in postfix form, a parenthesis-free form in which the operator follows both the operands. (This is sometimes called Reverse Polish Notation.)

In Listing 3.11 we present a simple routine for converting infix to postfix using a stack. We make the simplifying assumptions that all operands are lowercase letters and the only operators are *, /, +, and -.

Listing 3.11: Infix to Postfix

    # Define level of precedence
    def level(opr)
      case opr
        when "*", "/"
        when "+", "-"
        when "("
    # "Main"
    infix = "(a+b)*(c-d)/(e-(f-g))"
    postfix = ""
    stack =
    infix.each_byte do |sym|
      sym = "" << sym   # Convert to string
      case sym
        when "("
          stack.push sym
        when /[a-z]/
          postfix += sym
        when "*", "/", "+", "-"
          finished = false
          until finished or stack.empty?
            if level(sym) > level(stack.peek)
              finished = true
              postfix += stack.pop
          stack.push sym
        when ")"
          while stack.peek != "("
            postfix += stack.pop
          stack.pop  # Get rid of paren on stack
    while !stack.empty?
      postfix += stack.pop
    puts postfix            # Prints "ab+cd-*efg--/"

3.3.3 Detecting Unbalanced Punctuation in Expressions

Because of the nature of grouped expressions like parentheses and brackets, their validity can be checked using a stack (Listing 3.12). For every level of nesting in the expression, the stack will grow one level higher; when we find closing symbols, we can pop the corresponding symbol off the stack. If the symbol does not correspond as expected, or if there are symbols left on the stack at the end, we know the expression is not well-formed.

Listing 3.12: Detecting Unbalanced Punctuation

    def paren_match str
      stack =
      lsym = "{[(<"
      rsym = "}])>"
      str.each_byte do |byte| 
        sym = byte.chr
        if lsym.include? sym
        elsif rsym.include? sym
          top = stack.peek
          if lsym.index(top) != rsym.index(sym)
            return false 
          # Ignore non-grouped characters...
      # Ensure stack is empty...
      return stack.empty?
    str1 = "Hello (yes, [um] you) there!"
    str2 = "(((a+b))*((c-d)-(e*f))"
    str3 = "[[(a-(b-c))], [[x,y]]]"
    paren_match str1          # true
    paren_match str2          # false
    paren_match str3          # true

3.3.4 Detecting Unbalanced Tags in HTML and XML

This example (Listing 3.13) is essentially the same as the previous one, "Detecting Unbalanced Punctuation in Expressions." We include it only to give a hint that this task is possible, i.e., that a stack is useful for validating HTML and XML.

In the old days, a string was considered, at best, a special case of an array. Your opinion may vary depending on your language background. In Ruby, strings are not arrays; but it is a tribute to the orthogonality of the language when we see how similar these two examples turned out. This is because, after all, there is a certain isomorphism between strings and arrays. They are both ordered sequences of elements, where in the case of a string, the element is a character.

Because we are talking about stacks and not HTML/XML, we have made a huge truckload of simplifying assumptions here. (Those interested in real-life HTML and XML examples can refer to later chapters.) First of all, we assume that the text has already been parsed and stuck into an array; secondly, we only care about a limited subset of the many tags possible; thirdly, we ignore the possibility of attributes and values associated with the tags.

In short, this is not a real life example at all; but like the previous example, it shows the underlying principle.

Listing 3.13: Detecting Unbalanced Tags

    def balanced_tags list
      stack =
      opening = %w[ <html> <body> <b> <i> <u> <sub> <sup> ]
      closing = %w[ </html> </body> </b> </i> </u> </sub> </sup> ]
      list.each do |word| 
        if opening.include? word
        elsif closing.include? word
          top = stack.peek
          if closing.index(top) != opening.index(word)
            return false 
          # Ignore other words
      # Ensure stack is empty...
      return stack.empty?
    text1 = %w[ <html> <body> This is <b> only </b> 
                a test. </body> </html> ]
    text2 = %w[ <html> <body> Don't take it <i> too </i>
                seriously... </html> ]
    balanced_tags(text1)    # true
    balanced_tags(text2)    # false

3.3.5 Understanding Stacks and Recursion

As an example of the isomorphism between stack-oriented algorithms and recursive algorithms, we will take a look at the classic "Tower of Hanoi" problem.

According to legend, there is a Buddhist temple somewhere in the far east, where monks have the sole task of moving disks from one pole to another while obeying certain rules about the moves they can make. There were originally sixty-four disks on the first pole; when they finished, the world would come to an end.

As an aside, we like to dispel myths when we can. It seems that in reality, this puzzle originated with the French mathematician Edouard Lucas in 1883, and has no actual basis in eastern culture. What's more, Lucas himself named the puzzle the "Tower of Hanoi" (in the singular).

So if you were worried about the world ending... don't worry on that account. And anyway, 64 disks would take 264-1 moves. A few minutes with a calculator will reveal that those monks would be busy for millions of years.

But on to the rules of the game. (We'll explain this even though every first-year computer science student in the world has already seen the puzzle.) We have a pole with a certain number of disks stacked on it; call this the source pole. We want to move all of these to the destination pole, using a third (auxiliary) pole as an intermediate resting place. The catch is that you can only move one disk at a time and you cannot ever place a larger disk onto a smaller one.

The example given below uses a stack to solve the problem. We use only 3 disks, since 64 would occupy a computer for centuries.

    def towers2(list)
      while !list.empty?
        n, src, dst, aux = list.pop
        if n == 1
          puts "Move disk from #{src} to #{dst}"
          list.push [n-1, aux, dst, src]
          list.push [1, src, dst, aux]
          list.push [n-1, src, aux, dst]
    list = []
    list.push([3, "a", "c", "b"])

The output produced here is:

    Move disk from a to c
    Move disk from a to b
    Move disk from c to b
    Move disk from a to c
    Move disk from b to a
    Move disk from b to c
    Move disk from a to c

Of course, the classic solution to this problem is recursive. And as we already pointed out, the close relationship between the two algorithms is no surprise, since recursion implies the use of an invisible system-level stack.

    def towers(n, src, dst, aux)
      if n==1
        puts "Move disk from #{src} to #{dst}"
        towers(n-1, src, aux, dst)
        towers(1, src, dst, aux)
        towers(n-1, aux, dst, src)
    towers(3, "a", "c", "b")

The output produced here is the same. And it may interest you to know that we tried commenting out the output statements and comparing the runtimes of these two methods. Don't tell anyone, but the recursive version is twice as fast.

3.3.6 Implementing a Stricter Queue

We define a queue here in much the same way we defined a stack earlier. If you want to protect yourself from accessing such a data structure in an illegal way, we recommend this practice.

Listing 3.14: A Stricter Queue

    class Queue
      def initialize
        @store = []
      def enqueue(x)
        @store << x
      def dequeue
      def peek
      def length
      def empty?

We should mention that there is a Queue class in the thread library that works very well in threaded code.

3.3.7 A Token Queue Example: Traffic Light Simulation

We offer here a fairly contrived example of using a queue. This code will simulate the arrival of cars at a traffic light and store the arrival times in four queues. At the end, it prints some (presumably meaningful) statistics about the queue lengths and wait times.

A number of simplifying assumptions have been made. Time is granularized at the level of one second. There are no threads involved; all car movements are serialized in a reasonable way. Cars turn neither left nor right, they never go through a yellow or red light, and so on. The code is shown in Listing 3.15.

Listing 3.15: Traffic Light Simulation with a Queue

    # Program: Traffic light simulation 
    #          (Queue example)
    # The traffic light has this behavior:
    # Green north/south for 40 seconds
    # Pause 2 seconds
    # Green east/west for 45 seconds
    # Pause 2 seconds
    # Repeat
    # The traffic behaves this way:
    # A northbound car arrives at the traffic light
    #   every 3 seconds;
    # Southbound, every 5 seconds;
    # Eastbound, every 4 seconds;
    # Westbound, every 6 seconds.
    # All times are approximate (random).
    # Assume no cars turn at the light.
    # Cars pass through the light at a rate of
    # one per second.
    # Let's run for 8900 seconds (100 full cycles or
    # more than two hours) and answer these questions: 
    # How long on the average is each line of cars 
    # when the light turns green? What is the average 
    # wait time in seconds? What is the longest wait 
    # time?
    # Direction constants
    NORTH, SOUTH, EAST, WEST = 0, 1, 2, 3
    dirs = %w[North South East West]
    # Probabilities for car arriving 
    # from each direction:
    p =
    p[NORTH] = 1.0/3.0
    p[SOUTH] = 1.0/5.0
    p[EAST]  = 1.0/4.0
    p[WEST]  = 1.0/6.0
    # Queues:
    waiting =
    waiting[NORTH] =
    waiting[SOUTH] =
    waiting[EAST]  =
    waiting[WEST]  =
    lengths = [0, 0, 0, 0]  # How long is queue 
                            # when light turns green?
    greens  = [0, 0, 0, 0]  # How many times did
                            # light turn green?
    times   = [0, 0, 0, 0]  # How long did cars wait?
    ncars   = [0, 0, 0, 0]  # Count cars through light.
    maxtime = [0, 0, 0, 0]  # Max wait time?
    # Looping...
    while time < 8900
      change = true  # Light changed
      for time in time..time+40          # North/south green
        # Enqueue all arrivals
        for dir in NORTH..WEST
          waiting[dir].enqueue(time) if rand < p[dir]
        # Record queue lengths, counts
        if change 
          for dir in NORTH..SOUTH
            lengths[dir] += waiting[dir].length
            greens[dir] += 1
          change = false
        # N/S can leave, one per second...
        for dir in NORTH..SOUTH
          if !waiting[dir].empty?
            car = waiting[dir].dequeue
            wait = time - car
            ncars[dir] += 1
            times[dir] += wait
            maxtime[dir] = [maxtime[dir],wait].max
      for time in time..time+2           # Yellow/red
        # Nothing happens...
      change = true  # Light changed
      for time in time..time+45          # East/west green
        # Enqueue all arrivals
        for dir in NORTH..WEST
          waiting[dir].enqueue(time) if rand < p[dir]
        # Record queue lengths, counts
        if change 
          for dir in EAST..WEST
            lengths[dir] += waiting[dir].length
            greens[dir] += 1
          change = false
        # N/S can leave, one per second...
        for dir in EAST..WEST
          if !waiting[dir].empty?
            car = waiting[dir].dequeue
            wait = time - car
            ncars[dir] += 1
            times[dir] += wait
            maxtime[dir] = [maxtime[dir],wait].max
      for time in time..time+2           # Yellow/red
        # Nothing happens...
    # Display results...
    puts "Average queue lengths:"
    for dir in NORTH..WEST
      printf "  %-5s %6.1f\n", dirs[dir],
    puts "Max wait times:"
    for dir in NORTH..WEST
      printf "  %-5s %4d\n", dirs[dir],
    puts "Average wait times:"
    for dir in NORTH..WEST
      printf "  %-5s %6.1f\n", dirs[dir],

And here is the output it produces (which will vary because of the use of the pseudorandom number generator rand).

    Average queue lengths:
      North   15.6
      South    9.5
      East    10.8
      West     7.3
    Max wait times:
      North   51
      South   47
      East    42
      West    42
    Average wait times:
      North   19.5
      South   16.2
      East    13.7
      West    12.9

The reader may at once see a dozen ways in which this program could be improved. However, it serves its purpose, which is to illustrate a simple queue.

3.4 Working with Trees
I think that I shall never see
A poem as lovely as a tree...
— "Trees," [Alfred] Joyce Kilmer

Trees in computer science are a relatively intuitive concept (except that they are usually drawn with the "root" at the top and the "leaves" at the bottom). This is because we are familiar with so many kinds of hierachical data in everyday life, from the family tree to the corporate org chart to the directory structures on our hard drives.

The terminology of trees is rich but easy to understand. Any item in a tree is a node; the first or topmost node is the root. A node may have descendants that are below it, and the immediate descendants are called children. Conversely, a node may also have a parent (only one) and ancestors. A node with no child nodes is called a leaf. A subtree consists of a node and all its descendants. To travel through a tree (for example, to print it out) is called traversing the tree.

We will look mostly at binary trees, though in practice a node can have any number of children. We will see how to create a tree, populate it, and traverse it; and we will look at a few real-life tasks that use trees.

We will mention here that in many languages such as C or Pascal, trees would be implemented using true address pointers. But in Ruby (as in Java, for instance), we don't use pointers; object references work just as well or better.

3.4.1 Implementing a Binary Tree

There is more than one way to implement a binary tree in Ruby. For example, we could use an array to store the values. Here we use a more traditional approach, coding much as we would in C, except that pointers are replaced with object references.

What is required in order to describe a binary tree? Well, each node needs an attribute of some kind for storing a piece of data. Each node also needs a pair of attributes for referring to the left and right subtrees under that node.

We also need a way to insert into the tree and a way of getting information out of the tree. A pair of methods will serve these purposes.

The first tree we'll look at will implement these methods in a slightly unorthodox way. Then we will expand on the Tree class in later examples.

A tree is in a sense defined by its insertion algorithm and by how it is traversed. In this first example (Listing 3.16), we define an insert method that inserts in a breadth-first fashion, i.e., top to bottom and left to right. This guarantees that the tree grows in depth relatively slowly and the tree is always balanced. Corresponding to the insert method, the traverse iterator will iterate over the tree in the same breadth-first order.

Listing 3.16: Breadth-first Insertion and Traversal in a Tree

    class Tree
    attr_accessor :left
    attr_accessor :right
    attr_accessor :data
    def initialize(x=nil)
      @left = nil
      @right = nil
      @data = x
    def insert(x)
      list = []
      if @data == nil
        @data = x
      elsif @left == nil
        @left =
      elsif @right == nil
        @right =
        list << @left
        list << @right
        loop do
          node = list.shift
          if node.left == nil
            list << node.left
          if node.right == nil
            list << node.right
    def traverse()
      list = []
      yield @data
      list << @left if @left != nil
      list << @right if @right != nil
      loop do
        break if list.empty?
        node = list.shift
        list << node.left if node.left != nil
        list << node.right if node.right != nil
    items = [1, 2, 3, 4, 5, 6, 7]
    tree =
    items.each {|x| tree.insert(x)}
    tree.traverse {|x| print "#{x} "}
    print "\n"
    # Prints "1 2 3 4 5 6 7 "

This kind of tree, as defined by its insertion and traversal algorithms, is not especially interesting. It does serve as an introduction and something on which we can build.

3.4.2 Sorting Using a Binary Tree

For random data, a binary tree is a good way to sort. (Although in the case of already-sorted data, it degenerates into a simple linked list.) The reason, of course, is that with each comparison, we are eliminating half the remaining alternatives as to where we should place a new node.

Although it might be fairly rare to do this nowadays, it can't hurt to know how to do it. The code in Listing 3.17 builds on the previous example.

Listing 3.17: Sorting with a Binary Tree

    class Tree
      # Assumes definitions from
      # previous example...
      def insert(x)
        if @data == nil
          @data = x
        elsif x <= @data
          if @left == nil
            @left = x
            @left.insert x
          if @right == nil
            @right = x
            @right.insert x 
      def inorder()
        @left.inorder {|y| yield y} if @left != nil
        yield @data
        @right.inorder {|y| yield y} if @right != nil
      def preorder()
        yield @data
        @left.preorder {|y| yield y} if @left != nil
        @right.preorder {|y| yield y} if @right != nil
      def postorder()
        @left.postorder {|y| yield y} if @left != nil
        @right.postorder {|y| yield y} if @right != nil
        yield @data
    items = [50, 20, 80, 10, 30, 70, 90, 5, 14,
             28, 41, 66, 75, 88, 96]
    tree =
    items.each {|x| tree.insert(x)}
    tree.inorder {|x| print x, " "}
    print "\n"
    tree.preorder {|x| print x, " "}
    print "\n"
    tree.postorder {|x| print x, " "}
    print "\n"

3.4.3 Using a Binary Tree as a Lookup Table

Suppose we have a tree already sorted. Traditionally this has made a good lookup table; for example, a balanced tree of a million items would take no more than twenty comparisons (the depth of the tree or log base 2 of the number of nodes) to find a specific node. For this to be useful, we assume that the data for each node is not just a single value, but has a key value and other information associated with it.

In most if not all situations, a hash or even an external database table will be preferable. But we present this code to you anyhow (Listing 3.18).

Listing 3.18: Searching a Binary Tree

    class Tree
      # Assumes definitions
      # from previous example...
      def search(x)
        if == x
          return self
          ltree = left != nil ? : nil
          return ltree if ltree != nil
          rtree = right != nil ? : nil
          return rtree if rtree != nil
    keys = [50, 20, 80, 10, 30, 70, 90, 5, 14,
            28, 41, 66, 75, 88, 96]
    tree =
    keys.each {|x| tree.insert(x)}
    s1 =   # Returns a reference to the node
                           # containing 75...
    s2 =  # Returns nil (not found)

3.4.4 Converting a Tree to a String or Array

The same old tricks that allow us to traverse a tree will allow us to convert it to a string or array if we wish (Listing 3.19). Here we assume an inorder traversal, though any other kind could be used.

Listing 3.19: Converting a Tree to a String or Array

    class Tree
      # Assumes definitions from 
      # previous example...
      def to_s
        "[" + 
        if left then left.to_s + "," else "" end + 
        data.inspect + 
        if right then "," + right.to_s else "" end + "]"
      def to_a
        temp = []
        temp += left.to_a if left
        temp << data
        temp += right.to_a if right
    items = %w[bongo grimace monoid jewel plover nexus synergy]
    tree =
    items.each {|x| tree.insert x}
    str = tree.to_s * ","
    # str is now "bongo,grimace,jewel,monoid,nexus,plover,synergy"
    arr = tree.to_a
    # arr is now:
    # ["bongo",["grimace",[["jewel"],"monoid",[["nexus"],"plover",
    #  ["synergy"]]]]]

Note that the resulting array is as deeply nested as the depth of the tree from which it came. You can, of course, use flatten to produce a non- nested array.

3.4.5 Storing an Infix Expression in a Tree

Here is another little contrived problem illustrating how a binary tree might be used (Listing 3.20). We are given a prefix arithmetic expression and we want to store it in standard infix form in a tree. (This is not completely unrealistic, since the Ruby interpreter itself stores expressions in a tree structure, though it is a couple of orders of magnitude greater in complexity.)

We define a "standalone" method called addnode which will add a node to a tree in the proper place. The result will be a tree in which every leaf is an operand and every non-leaf node is an operator. We also define a new Tree method called infix, which will traverse the tree in-order and act as an iterator. One twist is that it adds in parentheses as it goes, since prefix form is parenthesis-free but infix form is not. The output would look more elegant if only necessary parentheses were added, but we added them indiscriminately to simplify the code.

Listing 3.20: Storing an Infix Expression in a Tree

    class Tree
      # Assumes definitions from
      # previous example...
      def infix()
        if @left != nil
          flag = %w[* / + -].include?
          yield "(" if flag
          @left.infix {|y| yield y}
          yield ")" if flag
        yield @data
        if @right != nil
          flag = %w[* / + -].include?
          yield "(" if flag
          @right.infix {|y| yield y} if @right != nil
          yield ")" if flag
    def addnode(nodes)
      node = nodes.shift
      tree = node
      if %w[* / + -].include? node
        tree.left  = addnode nodes
        tree.right = addnode nodes
    prefix = %w[ * + 32 * 21 45 - 72 + 23 11 ]
    tree = addnode prefix
    str = ""
    tree.infix {|x| str += x}
    # str is now "(32+(21*45))*(72-(23+11))"

3.4.6 Additional Notes on Trees

We'll mention a few more things here. First of all, a tree is a special case of a graph (as you will see shortly); in fact, it is a directed acyclic graph or DAG. Thus you can learn more about trees by researching graph alogorithms in general.

There is no reason that a tree should necessarily be binary; this is a convenient simplification that frequently makes sense. But it is conceivable to define a multiway tree in which each node is not limited to two children but may have an arbitrary number. In such a case you would likely want to represent the child node pointers as an array of object references.

A B-tree is a specialized form of multiway tree. It is an improvement over a binary tree in that it is always balanced (i.e., its depth is minimal) whereas a binary tree in the degenerate case can have a depth that is equal to the number of nodes it has. There is plenty of information on the web and in textbooks if you need to learn about B-trees; and the principles we've applied to ordinary binary trees can be extended to B-trees as well.

A red-black tree is a specialized form of binary tree in which each node has a color (red or black) associated with it. In addition, each node has a pointer back to its parent (meaning that it is arguably not a tree at all, since it isn't truly acyclic). A red-black tree maintains its balance through rotations of its nodes; i.e., if one part of the tree starts to get too deep, the nodes can be rearranged so that depth is minimized (and in-order traversal ordering is preserved). The extra information in each node aids in performing these rotations.

Another tree that maintains its balance in spite of additions and deletions is the AVL tree. This structure is named for its discoverers, the two Russian researchers Adel'son-Vel'skii and Landis. An AVL tree is a binary tree that uses slightly more sophisticated insertion and deletion algorithms to keep the tree balanced. It performs rotation of subtrees similar to that done for red-black trees.

All these and more are potentially useful tree structures. If you need more information, search the web or find any book of advanced algorithms.

3.5 Working with Graphs

A graph is a collection of nodes that interconnect with each other arbitrarily. (A tree is a special case of a graph.) We will not get deeply into graphs, since the theory and terminology can have a steep learning curve. Before long, we would find ourselves wandering out of the field of computer science entirely and into the province of mathematicians.

Yet graphs do have many practical applications. Consider any ordinary highway map, with highways connecting cities; or consider a circuit diagram. These are both best represented as graphs. A computer network can be thought of in terms of graph theory, whether it is a LAN of a dozen systems or the Internet itself with its countless millions of nodes.

When we say "graph," we usually mean an undirected graph. In simplistic terms, this is a graph in which the connecting lines don't have arrows; two nodes are either connected or they are not. By contrast, a directed graph or digraph can have "one-way streets"; just because node x is connected to node y doesn't mean that the reverse is true. (A node is also commonly called a vertex.) Finally, a weighted graph has connections (or edges) that have weights associated with them; these weights may express, for instance, the "distance" between two nodes. We won't go beyond these basic kinds of graphs; the interested reader can refer to numerous references in computer science and mathematics.

In Ruby, as in most languages, a graph can be represented in multiple ways; for example, a true network of interconnected objects or a matrix storing the set of edges in the graph. We will look at both of these as we show a few practical examples of manipulating graphs.

3.5.1 Implementing a Graph as an Adjacency Matrix

The example here builds on two previous examples. Here we implement an undirected graph as an adjacency matrix, using the ZArray class (section 3.5.1) to make sure new elements are zero and inheriting from the TriMatrix (section 3.1.7) to get a lower triangular matrix form. See Listing 3.21.

Note that in the kind of graph we are implementing here, a node cannot be connected to itself, and two nodes can be connected by only one edge.

We provide a way to specify edges initially by passing pairs into the constructor. We also provide a way to add and remove edges and detect the presence of edges. The vmax method will return the highest- numbered vertex in the graph. The degree method will find the degree of the specified vertex, that is, the number of edges that connect to it.

Finally, we provide two iterators, each_vertex and each_edge. These will iterate over edges and vertices, respectively.

Listing 3.21: Adjacency Matrix

    class LowerMatrix < TriMatrix
      def initialize
        @store =
    class Graph
      def initialize(*edges)
        @store =
        @max = 0
        for e in edges
          e[0], e[1] = e[1], e[0] if e[1] > e[0]
          @store[e[0],e[1]] = 1
          @max = [@max, e[0], e[1]].max
      def [](x,y)
        if x > y
        elsif x < y
      def []=(x,y,v)
        if x > y
        elsif x < y
      def edge? x,y
        x,y = y,x if x < y
      def add x,y
        @store[x,y] = 1
      def remove x,y
        x,y = y,x if x < y
        @store[x,y] = 0
        if (degree @max) == 0
          @max -= 1
      def vmax
      def degree x
        sum = 0
        0.upto @max do |i|
          sum += self[x,i]
      def each_vertex
        (0..@max).each {|v| yield v}
      def each_edge
        for v0 in 0..@max
          for v1 in 0..v0-1
            yield v0,v1 if self[v0,v1]==1
    mygraph =[1,0],[0,3],[2,1],[3,1],[3,2])
    # Print the degrees of all the vertices: 2 3 3 2
    mygraph.each_vertex {|v| puts}
    # Print the list of edges
    mygraph.each_edge do |a,b|
      puts "(#{a},#{b})"       
    # Remove a single edge
    mygraph.remove 1,3
    # Print the degrees of all the vertices: 2 2 2 2
    mygraph.each_vertex {|v| p v}

3.5.2 Determining Whether a Graph is Fully Connected

Not all graphs are fully connected. That is, sometimes "you can't get there from here"; there may be vertices that are unreachable from other vertices no matter what path you try. Connectivity is an important property of a graph to be able to assess, telling whether the graph is "of one piece." If it is, then every node is ultimately reachable from every other node.

We won't explain the algorithm; the interested reader can refer to any discrete math book. But we offer the Ruby method in Listing 3.22.

Listing 3.22: Is the Graph Fully Connected?

    class Graph
      def connected?
        x = vmax
        k = [x]
        l = [x]
        for i in 0..@max
          l << i if self[x,i]==1
        while !k.empty?
          y = k.shift
          # Now find all edges (y,z)
          self.each_edge do |a,b|
            if a==y || b==y
              z = a==y ? b : a
              if !l.include? z
                l << z
                k << z
        if l.size < @max
    mygraph =[0,1], [1,2], [2,3], [3,0], [1,3])
    puts mygraph.connected?     # true
    puts mygraph.euler_path?    # true
    mygraph.remove 1,2
    mygraph.remove 0,3
    mygraph.remove 1,3
    puts mygraph.connected?     # false
    puts mygraph.euler_path?    # false

A refinement of this algorithm could be used to determine the set of all connected components (or cliques) in a graph that is not overall fully connected. We won't do this here.

3.5.3 Determining Whether a Graph has an Euler Circuit
There is no branch of mathematics, however abstract, which may not some day be applied to phenomena of the real world.
— Nikolai Lobachevsky

Sometimes we want to know whether a graph has an Euler circuit. This term comes from the mathematician Leonhard Euler who essentially founded the field of topology by dealing with a particular instance of this question. (A graph of this nature is sometimes called a unicursive graph, since it can be drawn without lifting the pen from the paper or retracing.)

In the German town of Königsberg, there was an island in the middle of the river (near where the river split into two parts). Seven bridges crisscrossed at various places between opposite shores and the island. The townspeople wondered whether it was possible to make a walking tour of the city in such a way that you would cross each bridge exactly once and return to your starting place. In 1735, Euler proved that it was impossible. This, then, is not just a classic problem, but the original graph theory problem.

And, as with many things in life, once you know the answer, it is easy. It turns out that for a graph to have an Euler circuit, it must possess only vertices with even degree. Here we add a little method to check that property.

    class Graph
      def euler_circuit?
        return false if !connected?
        for i in 0..@max
          return false if degree(i) % 2 != 0
    mygraph =[1,0],[0,3],[2,1],[3,1],[3,2])
    flag1 =  mygraph.euler_circuit?    # false
    mygraph.remove 1,3
    flag2 =  mygraph.euler_circuit?    # true

3.5.4 Determining Whether a Graph has an Euler Path

An Euler path is not quite the same as an Euler circuit. The word "circuit" implies that you must return to your starting point; with a "path," we are really only concerned with visiting each edge exactly once. The code fragment below illustrates the difference.

    class Graph
      def euler_path?
        return false if !connected?
        each_vertex do |x| 
          if degree(x) % 2 == 1
            odd += 1
        odd <= 2
    mygraph =[0,1],[1,2],[1,3],[2,3],[3,0])
    flag1 =  mygraph.euler_circuit?    # false
    flag2 =  mygraph.euler_path?       # true

3.5.5 Hints for More Complex Graphs

It would be possible to write an entire book about graph algorithms. There are many good ones out there already, and we are certainly not going to range that far outside our realm of expertise.

But we will offer a few hints for dealing with more sophisticated graphs. They should get you started if you need to tackle a more advanced problem.

Suppose you want a directed graph rather than an undirected one. Just because vertex x points to vertex y doesn't mean the converse is true. You should no longer use a lower triangular matrix form, but a full-fledged two-dimensional array (see section 3.1.11, "Using Multidimensional Arrays"). You may still find the ZArray useful (see section 3.5.1, "Establishing a Default Value for New Array Elements"). You will likely want to implement not just a degree method, but a pair of them; in a directed graph, a vertex has an in-degree and an out-degree.

Suppose you have a directed graph in which a node or vertex is allowed to point to itself. Now you have potential nonzero numbers in the diagonal of your matrix rather than just zeroes. Be sure your code doesn't disallow access to the diagonal (as we did in section 3.1.7).

Suppose you want a weighted graph, where each edge has a weight associated with it. Now you would store the weight itself in the array rather than just a 1 or 0 (present or absent).

What about a multigraph, in which there can be multiple connections (edges) between the same pair of vertices? If it is undirected, a lower triangular matrix will suffice, and you can store the number of edges in each element (rather than just a 1 or 0). If it is directed, you will need a two-dimensional array, and you can still store the number of edges in each respective element.

What about bizarre combinations of these? For example, it is certainly conceivable to have a weighted directed multigraph (and if you have a valid everyday need for one, let us know about your application). In this case, you would need a more complex data structure. One possibility would be to store a small array in each element of the matrix.

For example, suppose vertex 3 has five edges connecting it with vertex 4; then element 3,4 of the adjacency matrix might store an array containing the associated weights.

The possibilities are endless and are beyond the scope of this book.

3.6 Summary

We've taken a good look here at arrays, hashes, and more complex data structures. We've seen some similarities between arrays and hashes (many of which are due to the fact that both mix in Enumerable) as well as some differences. We've looked at converting between arrays and hashes, and we've seen some interesting ways of extending their standard behavior.

Where more advanced data structures are concerned, we've seen examples of inheriting from an existing class and examples of limited delegation by encapsulating an instance of another class. We've seen ways to store data creatively, ways to make use of various data structures, and we've seen how to create iterators for these classes.

In the next chapter, we are again looking at the manipulation of data. But where we have so far been concerned with objects stored in memory, we will now be looking at secondary storage— working with files (and I/O in general), databases, and persistent objects.