Manipulating Structured Data in Ruby

This chapter is from the book

Ruby Way, The

Learn More Buy

This chapter is from the book

This chapter is from the book 

Ruby Way, The

Learn More Buy

In this Chapter

• Working with Arrays
• Working with Hashes
• Working with Stacks and Queues
• Working with Trees
• Working with Graphs
• Summary

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 an array, a hash is an indexed collection of data items; unlike an array, it may be indexed by any arbitrary object. (In Ruby, as in most languages, array elements are accessed by a numerical index.)

Finally, in this chapter we will 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.

Working with Arrays

Arrays in Ruby are indexed by integers and are zero based, just like C arrays. The resemblance ends there, 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 Fixnum values.

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. Also, iterators are 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.

Creating and Initializing an Array

The special class method [] is used to create an array; the data items listed within the brackets are used to populate the array. The three ways of calling this method are shown here (note that 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]

Also, the class method new can take zero, one, or two 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. Here's an example:

  d = Array.new       # Create an empty array
  e = Array.new(3)      # [nil, nil, nil]
  f = Array.new(3, "blah")  # ["blah", "blah", "blah"]

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.

Also, the special instance method at works like a simple case of element reference. Because it can take only a single integer parameter, it is slightly faster. Here's an example:

  a = [1, 2, 3, 4, 5, 6]
  b = a[0]        # 1
  c = a.at(0)       # 1
  d = a[-2]        # 5
  e = a.at(-2)      # 5
  f = a[9]        # nil
  g = a.at(9)       # 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), as shown here:

  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. Here's an example:

  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 subarray. 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). The alias is called indexes. Here's an example:

  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]

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

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 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. (Therefore, 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.) Here's an example:

  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"
  end

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

  class Array

   def <=> other) 
    (self <=> other)== -1
   end

   def <=(other)
    (self < other) or (self == other)
   end

   def >(other)
    (self <=> other) == 1
   end

   def >=(other)
    (self > other) or (self == other)
   end

  end

Having defined them, we can use them as you would expect:

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

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) because the comparison 3 <=> "x" is problematic:

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

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"
  end

Finally, it is conceivable that two arrays containing mismatched data types will still compare with the < 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"
  end

Sorting an Array

The easiest way to sort an array is to use the built-in sort method, as shown here:

  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, such as [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. Therefore, to sort in descending order, we could simply swap the order of the comparison, like this:

  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. Listing 3.1 presents 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
   a.upcase!
   b.upcase!
   # Compare a and b
   a <=> b
  end

  # 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—for example, sorting on multiple keys or sorting on keys that are computed at runtime.

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. Here's an example:

  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. Here's an example:

  # Continuing the above example...
  x.find {|e| e % 2 == 0}      # 8
  x.find_all {|e| e % 2 == 0}    # [8, 12, 4, 30]
  x.select {|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. Because 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.) Here's an example:

  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 that 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. Here's an example:

  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 want 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, as shown here:

  # 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.

Using Specialized Indexing Functions

The internals of a language handle the mapping of array indexes 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
     super(index-1)
    else
     raise IndexError
    end
   end

   def []=(index,obj)
    if index>0
     super(index-1,obj)
    else
     raise IndexError
    end
   end

  end


  x = Array2.new

  x[1]=5
  x[2]=3
  x[0]=1 # Error
  x[-1]=1 # Error

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

A similar approach can be used to implement multidimensional arrays (as you'll see later in the section "Using Multidimensional Arrays").

It is also possible to implement something like a triangular matrix (see 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 needs to be stored). This is sometimes useful, for example, in storing an undirected graph (as you'll see toward the end of this chapter).

Listing 3.3 Triangular Matrix

  class TriMatrix

   def initialize
    @store = []
   end

   def [](x,y)
    if x > y
     index = (x*x+x)/2 + y
     @store[index]
    else
     raise IndexError
    end
   end

   def []=(x,y,v)
    if x > y
     index = (x*x+x)/2 + y
     @store[index] = v
    else
     raise IndexError
    end
   end

  end


  t = TriMatrix.new

  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 indexes 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 10 minutes with pencil and paper should convince anyone it is correct. Some enhancements could probably be made to this class to make it truly useful, but we will leave that to you, the reader.

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

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 has led people to seek indirect ways of implementing it.

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

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 an alternative.

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

Using Arrays As Mathematical Sets

Most languages do not directly implement sets (Pascal being one exception). However, 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 entries (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.) Here's an example:

  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 the section "Finding Elements in One Array but Not Another" for more information.) Here's an example:

  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, you can 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. Here's an example:

  class Array

   def ^(other)
    (self | other) - (self & other)
   end

  end

  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), like so:

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

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. However, if you are used to Pascal or Python (or you have ingrained mathematical inclinations), you may want to use a different way. We present two options here:

  class Object

   def in(other)
    other.include? self
   end

  end

  x = [1, 2, 3]
  if 2.in x
   puts "yes"   # Prints "yes"
  else
   puts "no"
  end

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 2.in x instead as 2 .in x or even 2. in x, should you 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 such as <= 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. However, 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 as demonstrated in Listing 3.4.

Listing 3.4 Subset and Superset

  class Array

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

   def superset?(other)
    other.subset?(self)
   end

  end

  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—that is, 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. Because in practical terms this will vary from one application or situation to another, the best way is the simplest—define the universe and then do a set difference, as shown here:

  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 feel 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 see how to iterate randomly, refer to the section "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, especially combinatorics, will see that there must be 2ⁿ of these subsets. We can generate the powerset as demonstrated in Listing 3.5.

Listing 3.5 Powerset of a Set

  class Array

   def powerset
    num = 2**size
    ps = Array.new(num, [])
    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]]
      end
      j += 1
     end
    end
    ps
   end

  end

  x = [1, 2, 3]
  y = x.powerset
  # y is now:
  #  [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

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 circumstances, such as presenting a list of questions to a user in a random order, in which we might use this.

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

 class Array

  def randomize
   arr=self.dup
   arr.collect { arr.slice!(rand arr.length) }
  end

  def randomize!
   arr=self.dup
   result = arr.collect { arr.slice!(rand arr.length) }
   self.replace result
  end

 end

 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 knowing 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
    self[rand(self.length)]
   end

  end

Finally, remember that any time you are using rand, you can generate a predictable sequence (for example, for testing) simply by seeding with a known seed using srand.

Using Multidimensional Arrays

If you want to use multidimensional arrays for numerical purposes, an excellent library in the Ruby Application Archive called NArray (by Masahiro Tanaka) is available. If you want to use matrixes, you can use the matrix.rb standard library, as mentioned in Chapter 2, "Simple Data Tasks."

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 = [[[]]]
   end

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

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

  end


  x = Array3.new
  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.

Finding Elements in One Array but Not Another

Finding elements in one array but not another 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"]

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). Here's an example:

  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 = x.map {|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]
  x.map! {|w| w.reverse}
  # x is now %w[AHPLA OVARB EILRAHC ATLED OHCE TORTXOF]

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]

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 the value was not found. Here's an example:

  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, though. 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, as shown here:

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

The delete_if method 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. Here's an example:

  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 it's marginally more efficient. Here's an example:

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

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 the section "Using an Array As a Stack or Queue" for more information.

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]

Using an Array As a Stack or Queue

The basic stack operations are push and pop, which add and remove items, respectively, 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 the section "Working with Stacks and Queues."

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. Here's an example:

  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 indexes, we can use each_index. Saying x.each_index is equivalent to saying (0..(x.size-1)).each (that is, iterating over the range of indexes).

The iterator each_with_index (mixed in from Comparable) will pass both the element and the index into the block, as shown here:

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

Suppose you wanted to iterate over an array in random order? The following example uses the iterator random_each (which simply invokes the randomize method from section "Randomizing an Array"):

  class Array

  # Assumes we have defined randomize

   def random_each
    temp = self.randomize
    temp.each {|x| yield x}
   end

  end

  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.)

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, like so:

  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"

Reversing an Array

To reverse the order of an array, use the reverse or reverse! method:

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

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

Interleaving Arrays

Suppose you want to take two arrays and "interleave" them so that the new array contains 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"]

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). Therefore, we've created one here:

  class Array

   def count
    k=Hash.new(0)
    self.each{|x| k[x]+=1 }
    k
   end

  end

  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.

Inverting an Array to Form a Hash

An array is used to associate an integer index with a piece of data. However, what if you want to invert that association (that is, associate the data with the index, thus producing a hash)? The following method will do just that:

  class Array

   def invert
    h={}
    self.each_with_index{|x,i| h[x]=i}
    h
   end

  end

  a = ["red","yellow","orange"]
  h = a.invert   # {"orange"=>2, "yellow"=>1, "red"=>0}

Synchronized Sorting of Multiple Arrays

Suppose you want to sort an array, but you have 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 indexes. The list of indexes (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
  d=[]
  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]}
  else
   d.sort.collect{|x| x[1]}
  end
 end

 def sort_by(ord=[])
  return nil if self.length!=ord.length
  self.indexes(*ord)
 end

end


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

Establishing a Default Value for New Array Elements

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

  a = Array.new
  a[0]="x"
  a[3]="y"
  # 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
      self[i]=0
     end
    end
    v = super(x)
   end

   def []=(x,v)
    max = size
    super(x,v)
    if size - max > 1
     (max..size-2).each do |i|
      self[i] = 0
     end
    end
   end

  end


  num = ZArray.new
  num[1] = 1
  num[2] = 4
  num[5] = 25
  # num is now [0, 1, 4, 0, 0, 25]