pub. Sams Publishing, 2001

Sample Chapter

DRAFT VERSION: May change

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.1 Creating and Initializing an Array

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 = Array.new # Create an empty array e = Array.new(3) # [nil, nil, nil] f = Array.new(3, "blah") # ["blah", "blah", "blah"]

3.1.2 Accessing and Assigning Array Elements

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

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]

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 is slightly tricky. If you do it at all, you should do it with caution.

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

And 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`

) since 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 `<`

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

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 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, e.g., sorting on multiple keys or sorting on keys that are computed at runtime.

3.1.6 Selecting from an Array by Criteria

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

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

3.1.9 Using Arrays as Mathematical Sets

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

).

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. 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 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 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 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, 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 2^{n} 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 = 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]]

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=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 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, 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 2.xxx).

3.1.11 Using Multidimensional Arrays

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.

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

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]

3.1.14 Removing `nil`

Values from an Array

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

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.clear # x is now []

3.1.16 Concatenating and Appending onto Arrays

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

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

3.1.18 Iterating over an Array

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}" end # 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} 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.)

3.1.19 Interposing Delimiters to Form a String

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"

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

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

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

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.

3.1.24 Inverting an Array to Form a Hash

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}

3.1.25 Synchronized Sorting of Multiple Arrays

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

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

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 = Hash.new # Create an empty hash e = Hash.new(99) # Create an empty hash f = Hash.new("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

a = Hash.new("missing") # default value object is "missing" a["hello"] # "missing" a.default="nothing" 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

a = {} a["flat"] = 3 # {"flat"=>3} a.[]=("curved",2) # {"flat"=>3,"curved"=>2} a.store("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={} end 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=Hash.new(99) a[2] # 99 a # {} a[2] ||= 5 # 99 a # {} b=Hash.new 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={} b[2] # nil b[3]=nil b # {3=>nil} b[2].nil? # true b[3].nil? # true b[nil]=5 b # {3=>nil,nil=>5} b[nil] # 5 b[b[3]] # 5

3.2.4 Deleting Key-value Pairs

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.

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

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; end {"a"=>3,"b"=>2}.each_value do |value| print "val = #{value};" # Prints: val = 3; val = 2; end

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

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

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

names = {"fred"=>"jones","jane"=>"tucker", "joe"=>"tucker","mary"=>"SMITH"} # 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.

names.select {|k,v| v=="tucker" } # [["joe", "tucker"], ["jane", "tucker"]] names.find_all {|k,v| k.count("r")>0} # [["mary", "SMITH"], ["fred", "jones"]]

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

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

3.2.12 Creating a Hash from an Array

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

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} diff={} difference.each {|k| diff[k]=c[k] } # diff is {"a"=>1, "b"=>2}

3.2.14 Using a Hash as a Sparse Matrix

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

values = Hash.new(0) 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 = Hash.new(0) 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

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] else @store[key] = [keyval.shift] end end end end def store(k,v) if @store.has_key?(k) @store[k] += [v] else @store[k] = [v] end end def [](key) @store[key] end def []=(key,value) self.store(key,value) end def to_s @store.to_s end def to_a @store.to_a end def inspect @store.inspect end def keys result=[] @store.each do |k,v| result += ([k]*v.size) end result end def values @store.values.flatten end def each @store.each {|k,v| v.each {|y| yield k,y}} end alias each_pair each def each_key self.keys.each {|k| yield k} end def each_value self.values.each {|v| yield v} end def has_key? k self.keys.include? k end def has_value? v self.values.include? v end def length self.values.size end alias size length def delete k val = @store[k] @store.delete k val end def delete k,v @store[k] -= [v] if @store[k] v end # Other methods omitted here... end # 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 = HashDup.new(1,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

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

3.3.1 Implementing a Stricter Stack

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

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

Listing 3.11: Infix to Postfix

# Define level of precedence def level(opr) case opr when "*", "/" 2 when "+", "-" 1 when "(" 0 end end # "Main" infix = "(a+b)*(c-d)/(e-(f-g))" postfix = "" stack = Stack.new 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 else postfix += stack.pop end end stack.push sym when ")" while stack.peek != "(" postfix += stack.pop end stack.pop # Get rid of paren on stack end end while !stack.empty? postfix += stack.pop end puts postfix # Prints "ab+cd-*efg--/"

3.3.3 Detecting Unbalanced Punctuation in Expressions

Listing 3.12: Detecting Unbalanced Punctuation

def paren_match str stack = Stack.new lsym = "{[(<" rsym = "}])>" str.each_byte do |byte| sym = byte.chr if lsym.include? sym stack.push(sym) elsif rsym.include? sym top = stack.peek if lsym.index(top) != rsym.index(sym) return false else stack.pop end # Ignore non-grouped characters... end end # Ensure stack is empty... return stack.empty? end 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

Listing 3.13: Detecting Unbalanced Tags

def balanced_tags list stack = Stack.new 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 stack.push(word) elsif closing.include? word top = stack.peek if closing.index(top) != opening.index(word) return false else stack.pop end # Ignore other words end end # Ensure stack is empty... return stack.empty? end 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

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

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}" else towers(n-1, src, aux, dst) towers(1, src, dst, aux) towers(n-1, aux, dst, src) end end 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

Listing 3.14: A Stricter Queue

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

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

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 = Array.new(4) 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 = Array.new(4) waiting[NORTH] = Queue.new waiting[SOUTH] = Queue.new waiting[EAST] = Queue.new waiting[WEST] = Queue.new 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... time=0 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] end # Record queue lengths, counts if change for dir in NORTH..SOUTH lengths[dir] += waiting[dir].length greens[dir] += 1 end change = false end # 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 end end end for time in time..time+2 # Yellow/red # Nothing happens... end 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] end # Record queue lengths, counts if change for dir in EAST..WEST lengths[dir] += waiting[dir].length greens[dir] += 1 end change = false end # 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 end end end for time in time..time+2 # Yellow/red # Nothing happens... end end # Display results... puts "Average queue lengths:" for dir in NORTH..WEST printf " %-5s %6.1f\n", dirs[dir], lengths[dir]/greens[dir].to_f end puts "Max wait times:" for dir in NORTH..WEST printf " %-5s %4d\n", dirs[dir], maxtime[dir] end puts "Average wait times:" for dir in NORTH..WEST printf " %-5s %6.1f\n", dirs[dir], times[dir]/ncars[dir].to_f end

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.

I think that I shall never see A poem as lovely as a tree... |
||

— "Trees," [Alfred] Joyce Kilmer |

3.4.1 Implementing a Binary Tree

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 end def insert(x) list = [] if @data == nil @data = x elsif @left == nil @left = Tree.new(x) elsif @right == nil @right = Tree.new(x) else list << @left list << @right loop do node = list.shift if node.left == nil node.insert(x) break else list << node.left end if node.right == nil node.insert(x) break else list << node.right end end end end def traverse() list = [] yield @data list << @left if @left != nil list << @right if @right != nil loop do break if list.empty? node = list.shift yield node.data list << node.left if node.left != nil list << node.right if node.right != nil end end end items = [1, 2, 3, 4, 5, 6, 7] tree = Tree.new 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

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 = Tree.new x else @left.insert x end else if @right == nil @right = Tree.new x else @right.insert x end end end def inorder() @left.inorder {|y| yield y} if @left != nil yield @data @right.inorder {|y| yield y} if @right != nil end def preorder() yield @data @left.preorder {|y| yield y} if @left != nil @right.preorder {|y| yield y} if @right != nil end def postorder() @left.postorder {|y| yield y} if @left != nil @right.postorder {|y| yield y} if @right != nil yield @data end end items = [50, 20, 80, 10, 30, 70, 90, 5, 14, 28, 41, 66, 75, 88, 96] tree = Tree.new 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

Listing 3.18: Searching a Binary Tree

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

3.4.4 Converting a Tree to a String or Array

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 + "]" end def to_a temp = [] temp += left.to_a if left temp << data temp += right.to_a if right temp end end items = %w[bongo grimace monoid jewel plover nexus synergy] tree = Tree.new 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

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? @left.data yield "(" if flag @left.infix {|y| yield y} yield ")" if flag end yield @data if @right != nil flag = %w[* / + -].include? @right.data yield "(" if flag @right.infix {|y| yield y} if @right != nil yield ")" if flag end end end def addnode(nodes) node = nodes.shift tree = Tree.new node if %w[* / + -].include? node tree.left = addnode nodes tree.right = addnode nodes end tree end 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

3.5.1 Implementing a Graph as an Adjacency Matrix

Listing 3.21: Adjacency Matrix

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

3.5.2 Determining Whether a Graph is Fully Connected

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 end 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 end end end end if l.size < @max false else true end end end mygraph = Graph.new([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 |

class Graph def euler_circuit? return false if !connected? for i in 0..@max return false if degree(i) % 2 != 0 end true end end mygraph = Graph.new([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

class Graph def euler_path? return false if !connected? odd=0 each_vertex do |x| if degree(x) % 2 == 1 odd += 1 end end odd <= 2 end end mygraph = Graph.new([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

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