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

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]

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

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

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.

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.

    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.

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.

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

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

    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.

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]

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

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]

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

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"

Note that a hash is returned. No pun intended.

    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

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]

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            # {}

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"

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

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.

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

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.

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

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

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

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.

    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

    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.

    # 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--/"

    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

    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

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.

    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.

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

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.

    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"

    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)

    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.

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

    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}

    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.