Programming Ruby

The Pragmatic Programmer's Guide
Previous < Contents ^
Next >

Containers, Blocks, and Iterators


A jukebox with one song is unlikely to be popular (except perhaps in some very, very scary bars), so pretty soon we'll have to start thinking about producing a catalog of available songs and a playlist of songs waiting to be played. Both of these are containers: objects that hold references to one or more other objects.

Both the catalog and the playlist need a similar set of methods: add a song, remove a song, return a list of songs, and so on. The playlist may perform additional tasks, such as inserting advertising every so often or keeping track of cumulative play time, but we'll worry about these things later. In the meantime, it seems like a good idea to develop some kind of generic SongList class, which we can specialize into catalogs and playlists.

Containers

Before we start implementing, we'll need to work out how to store the list of songs inside a SongList object. We have three obvious choices. We could use the Ruby Array type, use the Ruby Hash type, or create our own list structure. Being lazy, for now we'll look at arrays and hashes, and choose one of these for our class.

Arrays

The class Array holds a collection of object references. Each object reference occupies a position in the array, identified by a non-negative integer index.

You can create arrays using literals or by explicitly creating an Array object. A literal array is simply a list of objects between square brackets.

a = [ 3.14159, "pie", 99 ]
a.type » Array
a.length » 3
a[0] » 3.14159
a[1] » "pie"
a[2] » 99
a[3] » nil
b = Array.new
b.type » Array
b.length » 0
b[0] = "second"
b[1] = "array"
b » ["second", "array"]

Arrays are indexed using the [] operator. As with most Ruby operators, this is actually a method (in class Array) and hence can be overridden in subclasses. As the example shows, array indices start at zero. Index an array with a single integer, and it returns the object at that position or returns nil if nothing's there. Index an array with a negative integer, and it counts from the end. This is shown in Figure 4.1 on page 35.

Figure not available...

a = [ 1, 3, 5, 7, 9 ]
a[-1] » 9
a[-2] » 7
a[-99] » nil

You can also index arrays with a pair of numbers, [start, count]. This returns a new array consisting of references to count objects starting at position start.

a = [ 1, 3, 5, 7, 9 ]
a[1, 3] » [3, 5, 7]
a[3, 1] » [7]
a[-3, 2] » [5, 7]

Finally, you can index arrays using ranges, in which start and end positions are separated by two or three periods. The two-period form includes the end position, while the three-period form does not.

a = [ 1, 3, 5, 7, 9 ]
a[1..3] » [3, 5, 7]
a[1...3] » [3, 5]
a[3..3] » [7]
a[-3..-1] » [5, 7, 9]

The [] operator has a corresponding []= operator, which lets you set elements in the array. If used with a single integer index, the element at that position is replaced by whatever is on the right-hand side of the assignment. Any gaps that result will be filled with nil.

a = [ 1, 3, 5, 7, 9 ] » [1, 3, 5, 7, 9]
a[1] = 'bat' » [1, "bat", 5, 7, 9]
a[-3] = 'cat' » [1, "bat", "cat", 7, 9]
a[3] = [ 9, 8 ] » [1, "bat", "cat", [9, 8], 9]
a[6] = 99 » [1, "bat", "cat", [9, 8], 9, nil, 99]

If the index to []= is two numbers (a start and a length) or a range, then those elements in the original array are replaced by whatever is on the right-hand side of the assignment. If the length is zero, the right-hand side is inserted into the array before the start position; no elements are removed. If the right-hand side is itself an array, its elements are used in the replacement. The array size is automatically adjusted if the index selects a different number of elements than are available on the right-hand side of the assignment.

a = [ 1, 3, 5, 7, 9 ] » [1, 3, 5, 7, 9]
a[2, 2] = 'cat' » [1, 3, "cat", 9]
a[2, 0] = 'dog' » [1, 3, "dog", "cat", 9]
a[1, 1] = [ 9, 8, 7 ] » [1, 9, 8, 7, "dog", "cat", 9]
a[0..3] = [] » ["dog", "cat", 9]
a[5] = 99 » ["dog", "cat", 9, nil, nil, 99]

Arrays have a large number of other useful methods. Using these, you can treat arrays as stacks, sets, queues, dequeues, and fifos. A complete list of array methods starts on page 278.

Hashes

Hashes (sometimes known as associative arrays or dictionaries) are similar to arrays, in that they are indexed collectives of object references.

However, while you index arrays with integers, you can index a hash with objects of any type: strings, regular expressions, and so on. When you store a value in a hash, you actually supply two objects---the key and the value. You can subsequently retrieve the value by indexing the hash with the same key. The values in a hash can be any objects of any type. The example that follows uses hash literals: a list of key => value pairs between braces.

h = { 'dog' => 'canine', 'cat' => 'feline', 'donkey' => 'asinine' }
h.length » 3
h['dog'] » "canine"
h['cow'] = 'bovine'
h[12]    = 'dodecine'
h['cat'] = 99
h » {"cow"=>"bovine", "cat"=>99, 12=>"dodecine", "donkey"=>"asinine", "dog"=>"canine"}

Compared with arrays, hashes have one significant advantage: they can use any object as an index. However, they also have a significant disadvantage: their elements are not ordered, so you cannot easily use a hash as a stack or a queue.

You'll find that hashes are one of the most commonly used data structures in Ruby. A full list of the methods implemented by class Hash starts on page 317.

Implementing a SongList Container

After that little diversion into arrays and hashes, we're now ready to implement the jukebox's SongList. Let's invent a basic list of methods we need in our SongList. We'll want to add to it as we go along, but it will do for now.

append( aSong ) » list
Append the given song to the list.
deleteFirst() » aSong
Remove the first song from the list, returning that song.
deleteLast() » aSong
Remove the last song from the list, returning that song.
[ anIndex } » aSong
Return the song identified by anIndex, which may be an integer index or a song title.

This list gives us a clue to the implementation. The ability to append songs at the end, and remove them from both the front and end, suggests a dequeue---a double-ended queue---which we know we can implement using an Array. Similarly, the ability to return a song at an integer position in the list is supported by arrays.

However, there's also the need to be able to retrieve songs by title, which might suggest using a hash, with the title as a key and the song as a value. Could we use a hash? Well, possibly, but there are problems. First a hash is unordered, so we'd probably need to use an ancillary array to keep track of the list. A bigger problem is that a hash does not support multiple keys with the same value. That would be a problem for our playlist, where the same song might be queued up for playing multiple times. So, for now we'll stick with an array of songs, searching it for titles when needed. If this becomes a performance bottleneck, we can always add some kind of hash-based lookup later.

We'll start our class with a basic initialize method, which creates the Array we'll use to hold the songs and stores a reference to it in the instance variable @songs. 

class SongList
  def initialize
    @songs = Array.new
  end
end

The SongList#append method adds the given song to the end of the @songs array. It also returns self, a reference to the current SongList object. This is a useful convention, as it lets us chain together multiple calls to append. We'll see an example of this later. 

class SongList
  def append(aSong)
    @songs.push(aSong)
    self
  end
end

Then we'll add the deleteFirst and deleteLast methods, trivially implemented using Array#shift and Array#pop , respectively. 

class SongList
  def deleteFirst
    @songs.shift
  end
  def deleteLast
    @songs.pop
  end
end

At this point, a quick test might be in order. First, we'll append four songs to the list. Just to show off, we'll use the fact that append returns the SongList object to chain together these method calls. 

list = SongList.new
list.
  append(Song.new('title1', 'artist1', 1)).
  append(Song.new('title2', 'artist2', 2)).
  append(Song.new('title3', 'artist3', 3)).
  append(Song.new('title4', 'artist4', 4))

Then we'll check that songs are taken from the start and end of the list correctly, and that nil is returned when the list becomes empty.

list.deleteFirst » Song: title1--artist1 (1)
list.deleteFirst » Song: title2--artist2 (2)
list.deleteLast » Song: title4--artist4 (4)
list.deleteLast » Song: title3--artist3 (3)
list.deleteLast » nil

So far so good. Our next method is [], which accesses elements by index. If the index is a number (which we check using Object#kind_of? ), we just return the element at that position. 

class SongList
  def [](key)
    if key.kind_of?(Integer)
      @songs[key]
    else
      # ...
    end
  end
end

Again, testing this is pretty trivial.

list[0] » Song: title1--artist1 (1)
list[2] » Song: title3--artist3 (3)
list[9] » nil