Chapter 26. Arrays

Newer versions of Bash support one-dimensional arrays. Array elements may be initialized with the variable[xx] notation. Alternatively, a script may introduce the entire array by an explicit declare -a variable statement. To dereference (retrieve the contents of) an array element, use curly bracket notation, that is, ${element[xx]}.


Example 26-1. Simple array usage

   1 #!/bin/bash
   2 
   3 
   4 area[11]=23
   5 area[13]=37
   6 area[51]=UFOs
   7 
   8 #  Array members need not be consecutive or contiguous.
   9 
  10 #  Some members of the array can be left uninitialized.
  11 #  Gaps in the array are okay.
  12 #  In fact, arrays with sparse data ("sparse arrays")
  13 #+ are useful in spreadsheet-processing software.
  14 
  15 
  16 echo -n "area[11] = "
  17 echo ${area[11]}    #  {curly brackets} needed.
  18 
  19 echo -n "area[13] = "
  20 echo ${area[13]}
  21 
  22 echo "Contents of area[51] are ${area[51]}."
  23 
  24 # Contents of uninitialized array variable print blank (null variable).
  25 echo -n "area[43] = "
  26 echo ${area[43]}
  27 echo "(area[43] unassigned)"
  28 
  29 echo
  30 
  31 # Sum of two array variables assigned to third
  32 area[5]=`expr ${area[11]} + ${area[13]}`
  33 echo "area[5] = area[11] + area[13]"
  34 echo -n "area[5] = "
  35 echo ${area[5]}
  36 
  37 area[6]=`expr ${area[11]} + ${area[51]}`
  38 echo "area[6] = area[11] + area[51]"
  39 echo -n "area[6] = "
  40 echo ${area[6]}
  41 # This fails because adding an integer to a string is not permitted.
  42 
  43 echo; echo; echo
  44 
  45 # -----------------------------------------------------------------
  46 # Another array, "area2".
  47 # Another way of assigning array variables...
  48 # array_name=( XXX YYY ZZZ ... )
  49 
  50 area2=( zero one two three four )
  51 
  52 echo -n "area2[0] = "
  53 echo ${area2[0]}
  54 # Aha, zero-based indexing (first element of array is [0], not [1]).
  55 
  56 echo -n "area2[1] = "
  57 echo ${area2[1]}    # [1] is second element of array.
  58 # -----------------------------------------------------------------
  59 
  60 echo; echo; echo
  61 
  62 # -----------------------------------------------
  63 # Yet another array, "area3".
  64 # Yet another way of assigning array variables...
  65 # array_name=([xx]=XXX [yy]=YYY ...)
  66 
  67 area3=([17]=seventeen [24]=twenty-four)
  68 
  69 echo -n "area3[17] = "
  70 echo ${area3[17]}
  71 
  72 echo -n "area3[24] = "
  73 echo ${area3[24]}
  74 # -----------------------------------------------
  75 
  76 exit 0

As we have seen, a convenient way of initializing an entire array is the array=( element1 element2 ... elementN ) notation.


Example 26-2. Formatting a poem

   1 #!/bin/bash
   2 # poem.sh: Pretty-prints one of the document author's favorite poems.
   3 
   4 # Lines of the poem (single stanza).
   5 Line[1]="I do not know which to prefer,"
   6 Line[2]="The beauty of inflections"
   7 Line[3]="Or the beauty of innuendoes,"
   8 Line[4]="The blackbird whistling"
   9 Line[5]="Or just after."
  10 # Note that quoting permits embedding whitespace.
  11 
  12 # Attribution.
  13 Attrib[1]=" Wallace Stevens"
  14 Attrib[2]="\"Thirteen Ways of Looking at a Blackbird\""
  15 # This poem is in the Public Domain (copyright expired).
  16 
  17 echo
  18 
  19 tput bold   # Bold print.
  20 
  21 for index in 1 2 3 4 5    # Five lines.
  22 do
  23   printf "     %s\n" "${Line[index]}"
  24 done
  25 
  26 for index in 1 2          # Two attribution lines.
  27 do
  28   printf "          %s\n" "${Attrib[index]}"
  29 done
  30 
  31 tput sgr0   # Reset terminal.
  32             # See 'tput' docs.
  33 
  34 echo
  35 
  36 exit 0
  37 
  38 # Exercise:
  39 # --------
  40 # Modify this script to pretty-print a poem from a text data file.

Array variables have a syntax all their own, and even standard Bash commands and operators have special options adapted for array use.


Example 26-3. Various array operations

   1 #!/bin/bash
   2 # array-ops.sh: More fun with arrays.
   3 
   4 
   5 array=( zero one two three four five )
   6 # Element 0   1   2    3     4    5
   7 
   8 echo ${array[0]}       #  zero
   9 echo ${array:0}        #  zero
  10                        #  Parameter expansion of first element,
  11                        #+ starting at position # 0 (1st character).
  12 echo ${array:1}        #  ero
  13                        #  Parameter expansion of first element,
  14                        #+ starting at position # 1 (2nd character).
  15 
  16 echo "--------------"
  17 
  18 echo ${#array[0]}      #  4
  19                        #  Length of first element of array.
  20 echo ${#array}         #  4
  21                        #  Length of first element of array.
  22                        #  (Alternate notation)
  23 
  24 echo ${#array[1]}      #  3
  25                        #  Length of second element of array.
  26                        #  Arrays in Bash have zero-based indexing.
  27 
  28 echo ${#array[*]}      #  6
  29                        #  Number of elements in array.
  30 echo ${#array[@]}      #  6
  31                        #  Number of elements in array.
  32 
  33 echo "--------------"
  34 
  35 array2=( [0]="first element" [1]="second element" [3]="fourth element" )
  36 #            ^     ^       ^     ^      ^       ^     ^      ^       ^
  37 # Quoting permits embedding whitespace within individual array elements.
  38 
  39 echo ${array2[0]}      # first element
  40 echo ${array2[1]}      # second element
  41 echo ${array2[2]}      #
  42                        # Skipped in initialization, and therefore null.
  43 echo ${array2[3]}      # fourth element
  44 echo ${#array2[0]}     # 13    (length of first element)
  45 echo ${#array2[*]}     # 3     (number of elements in array)
  46 
  47 exit

Many of the standard string operations work on arrays.


Example 26-4. String operations on arrays

   1 #!/bin/bash
   2 # array-strops.sh: String operations on arrays.
   3 
   4 # Script by Michael Zick.
   5 # Used in ABS Guide with permission.
   6 # Fixups: 05 May 08, 04 Aug 08.
   7 
   8 #  In general, any string operation using the ${name ... } notation
   9 #+ can be applied to all string elements in an array,
  10 #+ with the ${name[@] ... } or ${name[*] ...} notation.
  11 
  12 
  13 arrayZ=( one two three four five five )
  14 
  15 echo
  16 
  17 # Trailing Substring Extraction
  18 echo ${arrayZ[@]:0}     # one two three four five five
  19 #                ^        All elements.
  20 
  21 echo ${arrayZ[@]:1}     # two three four five five
  22 #                ^        All elements following element[0].
  23 
  24 echo ${arrayZ[@]:1:2}   # two three
  25 #                  ^      Only the two elements after element[0].
  26 
  27 echo "---------"
  28 
  29 
  30 # Substring Removal
  31 
  32 # Removes shortest match from front of string(s).
  33 
  34 echo ${arrayZ[@]#f*r}   # one two three five five
  35 #               ^       # Applied to all elements of the array.
  36                         # Matches "four" and removes it.
  37 
  38 # Longest match from front of string(s)
  39 echo ${arrayZ[@]##t*e}  # one two four five five
  40 #               ^^      # Applied to all elements of the array.
  41                         # Matches "three" and removes it.
  42 
  43 # Shortest match from back of string(s)
  44 echo ${arrayZ[@]%h*e}   # one two t four five five
  45 #               ^       # Applied to all elements of the array.
  46                         # Matches "hree" and removes it.
  47 
  48 # Longest match from back of string(s)
  49 echo ${arrayZ[@]%%t*e}  # one two four five five
  50 #               ^^      # Applied to all elements of the array.
  51                         # Matches "three" and removes it.
  52 
  53 echo "----------------------"
  54 
  55 
  56 # Substring Replacement
  57 
  58 # Replace first occurrence of substring with replacement.
  59 echo ${arrayZ[@]/fiv/XYZ}   # one two three four XYZe XYZe
  60 #               ^           # Applied to all elements of the array.
  61 
  62 # Replace all occurrences of substring.
  63 echo ${arrayZ[@]//iv/YY}    # one two three four fYYe fYYe
  64                             # Applied to all elements of the array.
  65 
  66 # Delete all occurrences of substring.
  67 # Not specifing a replacement defaults to 'delete' ...
  68 echo ${arrayZ[@]//fi/}      # one two three four ve ve
  69 #               ^^          # Applied to all elements of the array.
  70 
  71 # Replace front-end occurrences of substring.
  72 echo ${arrayZ[@]/#fi/XY}    # one two three four XYve XYve
  73 #                ^          # Applied to all elements of the array.
  74 
  75 # Replace back-end occurrences of substring.
  76 echo ${arrayZ[@]/%ve/ZZ}    # one two three four fiZZ fiZZ
  77 #                ^          # Applied to all elements of the array.
  78 
  79 echo ${arrayZ[@]/%o/XX}     # one twXX three four five five
  80 #                ^          # Why?
  81 
  82 echo "-----------------------------"
  83 
  84 
  85 replacement() {
  86     echo -n "!!!"
  87 }
  88 
  89 echo ${arrayZ[@]/%e/$(replacement)}
  90 #                ^  ^^^^^^^^^^^^^^
  91 # on!!! two thre!!! four fiv!!! fiv!!!
  92 # The stdout of replacement() is the replacement string.
  93 # Q.E.D: The replacement action is, in effect, an 'assignment.'
  94 
  95 echo "------------------------------------"
  96 
  97 #  Accessing the "for-each":
  98 echo ${arrayZ[@]//*/$(replacement optional_arguments)}
  99 #                ^^ ^^^^^^^^^^^^^
 100 # !!! !!! !!! !!! !!! !!!
 101 
 102 #  Now, if Bash would only pass the matched string
 103 #+ to the function being called . . .
 104 
 105 echo
 106 
 107 exit 0
 108 
 109 #  Before reaching for a Big Hammer -- Perl, Python, or all the rest --
 110 #  recall:
 111 #    $( ... ) is command substitution.
 112 #    A function runs as a sub-process.
 113 #    A function writes its output (if echo-ed) to stdout.
 114 #    Assignment, in conjunction with "echo" and command substitution,
 115 #+   can read a function's stdout.
 116 #    The name[@] notation specifies (the equivalent of) a "for-each"
 117 #+   operation.
 118 #  Bash is more powerful than you think!

Command substitution can construct the individual elements of an array.


Example 26-5. Loading the contents of a script into an array

   1 #!/bin/bash
   2 # script-array.sh: Loads this script into an array.
   3 # Inspired by an e-mail from Chris Martin (thanks!).
   4 
   5 script_contents=( $(cat "$0") )  #  Stores contents of this script ($0)
   6                                  #+ in an array.
   7 
   8 for element in $(seq 0 $((${#script_contents[@]} - 1)))
   9   do                #  ${#script_contents[@]}
  10                     #+ gives number of elements in the array.
  11                     #
  12                     #  Question:
  13                     #  Why is  seq 0  necessary?
  14                     #  Try changing it to seq 1.
  15   echo -n "${script_contents[$element]}"
  16                     # List each field of this script on a single line.
  17 # echo -n "${script_contents[element]}" also works because of ${ ... }.
  18   echo -n " -- "    # Use " -- " as a field separator.
  19 done
  20 
  21 echo
  22 
  23 exit 0
  24 
  25 # Exercise:
  26 # --------
  27 #  Modify this script so it lists itself
  28 #+ in its original format,
  29 #+ complete with whitespace, line breaks, etc.

In an array context, some Bash builtins have a slightly altered meaning. For example, unset deletes array elements, or even an entire array.


Example 26-6. Some special properties of arrays

   1 #!/bin/bash
   2 
   3 declare -a colors
   4 #  All subsequent commands in this script will treat
   5 #+ the variable "colors" as an array.
   6 
   7 echo "Enter your favorite colors (separated from each other by a space)."
   8 
   9 read -a colors    # Enter at least 3 colors to demonstrate features below.
  10 #  Special option to 'read' command,
  11 #+ allowing assignment of elements in an array.
  12 
  13 echo
  14 
  15 element_count=${#colors[@]}
  16 # Special syntax to extract number of elements in array.
  17 #     element_count=${#colors[*]} works also.
  18 #
  19 #  The "@" variable allows word splitting within quotes
  20 #+ (extracts variables separated by whitespace).
  21 #
  22 #  This corresponds to the behavior of "$@" and "$*"
  23 #+ in positional parameters. 
  24 
  25 index=0
  26 
  27 while [ "$index" -lt "$element_count" ]
  28 do    # List all the elements in the array.
  29   echo ${colors[$index]}
  30   #    ${colors[index]} also works because it's within ${ ... } brackets.
  31   let "index = $index + 1"
  32   # Or:
  33   #    index+=1
  34   # if running Bash, version 3.1 or later.
  35 done
  36 # Each array element listed on a separate line.
  37 # If this is not desired, use  echo -n "${colors[$index]} "
  38 #
  39 # Doing it with a "for" loop instead:
  40 #   for i in "${colors[@]}"
  41 #   do
  42 #     echo "$i"
  43 #   done
  44 # (Thanks, S.C.)
  45 
  46 echo
  47 
  48 # Again, list all the elements in the array, but using a more elegant method.
  49   echo ${colors[@]}          # echo ${colors[*]} also works.
  50 
  51 echo
  52 
  53 # The "unset" command deletes elements of an array, or entire array.
  54 unset colors[1]              # Remove 2nd element of array.
  55                              # Same effect as   colors[1]=
  56 echo  ${colors[@]}           # List array again, missing 2nd element.
  57 
  58 unset colors                 # Delete entire array.
  59                              #  unset colors[*] and
  60                              #+ unset colors[@] also work.
  61 echo; echo -n "Colors gone."			   
  62 echo ${colors[@]}            # List array again, now empty.
  63 
  64 exit 0

As seen in the previous example, either ${array_name[@]} or ${array_name[*]} refers to all the elements of the array. Similarly, to get a count of the number of elements in an array, use either ${#array_name[@]} or ${#array_name[*]}. ${#array_name} is the length (number of characters) of ${array_name[0]}, the first element of the array.


Example 26-7. Of empty arrays and empty elements

   1 #!/bin/bash
   2 # empty-array.sh
   3 
   4 #  Thanks to Stephane Chazelas for the original example,
   5 #+ and to Michael Zick, Omair Eshkenazi, for extending it.
   6 #  And to Nathan Coulter for clarifications and corrections.
   7 
   8 
   9 # An empty array is not the same as an array with empty elements.
  10 
  11   array0=( first second third )
  12   array1=( '' )   # "array1" consists of one empty element.
  13   array2=( )      # No elements . . . "array2" is empty.
  14   array3=(   )    # What about this array?
  15 
  16 
  17 echo
  18 ListArray()
  19 {
  20 echo
  21 echo "Elements in array0:  ${array0[@]}"
  22 echo "Elements in array1:  ${array1[@]}"
  23 echo "Elements in array2:  ${array2[@]}"
  24 echo "Elements in array3:  ${array3[@]}"
  25 echo
  26 echo "Length of first element in array0 = ${#array0}"
  27 echo "Length of first element in array1 = ${#array1}"
  28 echo "Length of first element in array2 = ${#array2}"
  29 echo "Length of first element in array3 = ${#array3}"
  30 echo
  31 echo "Number of elements in array0 = ${#array0[*]}"  # 3
  32 echo "Number of elements in array1 = ${#array1[*]}"  # 1  (Surprise!)
  33 echo "Number of elements in array2 = ${#array2[*]}"  # 0
  34 echo "Number of elements in array3 = ${#array3[*]}"  # 0
  35 }
  36 
  37 # ===================================================================
  38 
  39 ListArray
  40 
  41 # Try extending those arrays.
  42 
  43 # Adding an element to an array.
  44 array0=( "${array0[@]}" "new1" )
  45 array1=( "${array1[@]}" "new1" )
  46 array2=( "${array2[@]}" "new1" )
  47 array3=( "${array3[@]}" "new1" )
  48 
  49 ListArray
  50 
  51 # or
  52 array0[${#array0[*]}]="new2"
  53 array1[${#array1[*]}]="new2"
  54 array2[${#array2[*]}]="new2"
  55 array3[${#array3[*]}]="new2"
  56 
  57 ListArray
  58 
  59 # When extended as above, arrays are 'stacks' ...
  60 # Above is the 'push' ...
  61 # The stack 'height' is:
  62 height=${#array2[@]}
  63 echo
  64 echo "Stack height for array2 = $height"
  65 
  66 # The 'pop' is:
  67 unset array2[${#array2[@]}-1]   #  Arrays are zero-based,
  68 height=${#array2[@]}            #+ which means first element has index 0.
  69 echo
  70 echo "POP"
  71 echo "New stack height for array2 = $height"
  72 
  73 ListArray
  74 
  75 # List only 2nd and 3rd elements of array0.
  76 from=1		    # Zero-based numbering.
  77 to=2
  78 array3=( ${array0[@]:1:2} )
  79 echo
  80 echo "Elements in array3:  ${array3[@]}"
  81 
  82 # Works like a string (array of characters).
  83 # Try some other "string" forms.
  84 
  85 # Replacement:
  86 array4=( ${array0[@]/second/2nd} )
  87 echo
  88 echo "Elements in array4:  ${array4[@]}"
  89 
  90 # Replace all matching wildcarded string.
  91 array5=( ${array0[@]//new?/old} )
  92 echo
  93 echo "Elements in array5:  ${array5[@]}"
  94 
  95 # Just when you are getting the feel for this . . .
  96 array6=( ${array0[@]#*new} )
  97 echo # This one might surprise you.
  98 echo "Elements in array6:  ${array6[@]}"
  99 
 100 array7=( ${array0[@]#new1} )
 101 echo # After array6 this should not be a surprise.
 102 echo "Elements in array7:  ${array7[@]}"
 103 
 104 # Which looks a lot like . . .
 105 array8=( ${array0[@]/new1/} )
 106 echo
 107 echo "Elements in array8:  ${array8[@]}"
 108 
 109 #  So what can one say about this?
 110 
 111 #  The string operations are performed on
 112 #+ each of the elements in var[@] in succession.
 113 #  Therefore : Bash supports string vector operations.
 114 #  If the result is a zero length string,
 115 #+ that element disappears in the resulting assignment.
 116 #  However, if the expansion is in quotes, the null elements remain.
 117 
 118 #  Michael Zick: Question, are those strings hard or soft quotes?
 119 #  Nathan Coulter: There is no such thing as "soft quotes."
 120 #  What's really happening is that
 121 #+ the pattern matching happens after all the other expansions of [word]
 122 #+ in cases like ${parameter#word}.
 123 
 124 
 125 zap='new*'
 126 array9=( ${array0[@]/$zap/} )
 127 echo
 128 echo "Number of elements in array9:  ${#array9[@]}"
 129 array9=( "${array0[@]/$zap/}" )
 130 echo "Elements in array9:  ${array9[@]}"
 131 # This time the null elements remain.
 132 echo "Number of elements in array9:  ${#array9[@]}"
 133 
 134 
 135 # Just when you thought you were still in Kansas . . .
 136 array10=( ${array0[@]#$zap} )
 137 echo
 138 echo "Elements in array10:  ${array10[@]}"
 139 # But, the asterisk in zap won't be interpreted if quoted.
 140 array10=( ${array0[@]#"$zap"} )
 141 echo
 142 echo "Elements in array10:  ${array10[@]}"
 143 # Well, maybe we _are_ still in Kansas . . .
 144 # (Revisions to above code block by Nathan Coulter.)
 145 
 146 
 147 #  Compare array7 with array10.
 148 #  Compare array8 with array9.
 149 
 150 #  Reiterating: No such thing as soft quotes!
 151 #  Nathan Coulter explains:
 152 #  Pattern matching of 'word' in ${parameter#word} is done after
 153 #+ parameter expansion and *before* quote removal.
 154 #  In the normal case, pattern matching is done *after* quote removal.
 155  
 156 exit

The relationship of ${array_name[@]} and ${array_name[*]} is analogous to that between $@ and $*. This powerful array notation has a number of uses.

   1 # Copying an array.
   2 array2=( "${array1[@]}" )
   3 # or
   4 array2="${array1[@]}"
   5 #
   6 #  However, this fails with "sparse" arrays,
   7 #+ arrays with holes (missing elements) in them,
   8 #+ as Jochen DeSmet points out.
   9 # ------------------------------------------
  10   array1[0]=0
  11 # array1[1] not assigned
  12   array1[2]=2
  13   array2=( "${array1[@]}" )       # Copy it?
  14 
  15 echo ${array2[0]}      # 0
  16 echo ${array2[2]}      # (null), should be 2
  17 # ------------------------------------------
  18 
  19 
  20 
  21 # Adding an element to an array.
  22 array=( "${array[@]}" "new element" )
  23 # or
  24 array[${#array[*]}]="new element"
  25 
  26 # Thanks, S.C.

Tip

The array=( element1 element2 ... elementN ) initialization operation, with the help of command substitution, makes it possible to load the contents of a text file into an array.

   1 #!/bin/bash
   2 
   3 filename=sample_file
   4 
   5 #            cat sample_file
   6 #
   7 #            1 a b c
   8 #            2 d e fg
   9 
  10 
  11 declare -a array1
  12 
  13 array1=( `cat "$filename"`)                #  Loads contents
  14 #         List file to stdout              #+ of $filename into array1.
  15 #
  16 #  array1=( `cat "$filename" | tr '\n' ' '`)
  17 #                            change linefeeds in file to spaces. 
  18 #  Not necessary because Bash does word splitting,
  19 #+ changing linefeeds to spaces.
  20 
  21 echo ${array1[@]}            # List the array.
  22 #                              1 a b c 2 d e fg
  23 #
  24 #  Each whitespace-separated "word" in the file
  25 #+ has been assigned to an element of the array.
  26 
  27 element_count=${#array1[*]}
  28 echo $element_count          # 8

Clever scripting makes it possible to add array operations.


Example 26-8. Initializing arrays

   1 #! /bin/bash
   2 # array-assign.bash
   3 
   4 #  Array operations are Bash-specific,
   5 #+ hence the ".bash" in the script name.
   6 
   7 # Copyright (c) Michael S. Zick, 2003, All rights reserved.
   8 # License: Unrestricted reuse in any form, for any purpose.
   9 # Version: $ID$
  10 #
  11 # Clarification and additional comments by William Park.
  12 
  13 #  Based on an example provided by Stephane Chazelas
  14 #+ which appeared in an earlier version of the
  15 #+ Advanced Bash Scripting Guide.
  16 
  17 # Output format of the 'times' command:
  18 # User CPU <space> System CPU
  19 # User CPU of dead children <space> System CPU of dead children
  20 
  21 #  Bash has two versions of assigning all elements of an array
  22 #+ to a new array variable.
  23 #  Both drop 'null reference' elements
  24 #+ in Bash versions 2.04 and later.
  25 #  An additional array assignment that maintains the relationship of
  26 #+ [subscript]=value for arrays may be added to newer versions.
  27 
  28 #  Constructs a large array using an internal command,
  29 #+ but anything creating an array of several thousand elements
  30 #+ will do just fine.
  31 
  32 declare -a bigOne=( /dev/* )  # All the files in /dev . . .
  33 echo
  34 echo 'Conditions: Unquoted, default IFS, All-Elements-Of'
  35 echo "Number of elements in array is ${#bigOne[@]}"
  36 
  37 # set -vx
  38 
  39 
  40 
  41 echo
  42 echo '- - testing: =( ${array[@]} ) - -'
  43 times
  44 declare -a bigTwo=( ${bigOne[@]} )
  45 # Note parens:    ^              ^
  46 times
  47 
  48 
  49 echo
  50 echo '- - testing: =${array[@]} - -'
  51 times
  52 declare -a bigThree=${bigOne[@]}
  53 # No parentheses this time.
  54 times
  55 
  56 #  Comparing the numbers shows that the second form, pointed out
  57 #+ by Stephane Chazelas, is faster.
  58 #
  59 #  As William Park explains:
  60 #+ The bigTwo array assigned element by element (because of parentheses),
  61 #+ whereas bigThree assigned as a single string.
  62 #  So, in essence, you have:
  63 #                   bigTwo=( [0]="..." [1]="..." [2]="..." ... )
  64 #                   bigThree=( [0]="... ... ..." )
  65 #
  66 #  Verify this by:  echo ${bigTwo[0]}
  67 #                   echo ${bigThree[0]}
  68 
  69 
  70 #  I will continue to use the first form in my example descriptions
  71 #+ because I think it is a better illustration of what is happening.
  72 
  73 #  The reusable portions of my examples will actual contain
  74 #+ the second form where appropriate because of the speedup.
  75 
  76 # MSZ: Sorry about that earlier oversight folks.
  77 
  78 
  79 #  Note:
  80 #  ----
  81 #  The "declare -a" statements in lines 32 and 44
  82 #+ are not strictly necessary, since it is implicit
  83 #+ in the  Array=( ... )  assignment form.
  84 #  However, eliminating these declarations slows down
  85 #+ the execution of the following sections of the script.
  86 #  Try it, and see.
  87 
  88 exit 0

Note

Adding a superfluous declare -a statement to an array declaration may speed up execution of subsequent operations on the array.


Example 26-9. Copying and concatenating arrays

   1 #! /bin/bash
   2 # CopyArray.sh
   3 #
   4 # This script written by Michael Zick.
   5 # Used here with permission.
   6 
   7 #  How-To "Pass by Name & Return by Name"
   8 #+ or "Building your own assignment statement".
   9 
  10 
  11 CpArray_Mac() {
  12 
  13 # Assignment Command Statement Builder
  14 
  15     echo -n 'eval '
  16     echo -n "$2"                    # Destination name
  17     echo -n '=( ${'
  18     echo -n "$1"                    # Source name
  19     echo -n '[@]} )'
  20 
  21 # That could all be a single command.
  22 # Matter of style only.
  23 }
  24 
  25 declare -f CopyArray                # Function "Pointer"
  26 CopyArray=CpArray_Mac               # Statement Builder
  27 
  28 Hype()
  29 {
  30 
  31 # Hype the array named $1.
  32 # (Splice it together with array containing "Really Rocks".)
  33 # Return in array named $2.
  34 
  35     local -a TMP
  36     local -a hype=( Really Rocks )
  37 
  38     $($CopyArray $1 TMP)
  39     TMP=( ${TMP[@]} ${hype[@]} )
  40     $($CopyArray TMP $2)
  41 }
  42 
  43 declare -a before=( Advanced Bash Scripting )
  44 declare -a after
  45 
  46 echo "Array Before = ${before[@]}"
  47 
  48 Hype before after
  49 
  50 echo "Array After = ${after[@]}"
  51 
  52 # Too much hype?
  53 
  54 echo "What ${after[@]:3:2}?"
  55 
  56 declare -a modest=( ${after[@]:2:1} ${after[@]:3:2} )
  57 #                    ---- substring extraction ----
  58 
  59 echo "Array Modest = ${modest[@]}"
  60 
  61 # What happened to 'before' ?
  62 
  63 echo "Array Before = ${before[@]}"
  64 
  65 exit 0


Example 26-10. More on concatenating arrays

   1 #! /bin/bash
   2 # array-append.bash
   3 
   4 # Copyright (c) Michael S. Zick, 2003, All rights reserved.
   5 # License: Unrestricted reuse in any form, for any purpose.
   6 # Version: $ID$
   7 #
   8 # Slightly modified in formatting by M.C.
   9 
  10 
  11 # Array operations are Bash-specific.
  12 # Legacy UNIX /bin/sh lacks equivalents.
  13 
  14 
  15 #  Pipe the output of this script to 'more'
  16 #+ so it doesn't scroll off the terminal.
  17 #  Or, redirect output to a file.
  18 
  19 
  20 declare -a array1=( zero1 one1 two1 )
  21 # Subscript packed.
  22 declare -a array2=( [0]=zero2 [2]=two2 [3]=three2 )
  23 # Subscript sparse -- [1] is not defined.
  24 
  25 echo
  26 echo '- Confirm that the array is really subscript sparse. -'
  27 echo "Number of elements: 4"        # Hard-coded for illustration.
  28 for (( i = 0 ; i < 4 ; i++ ))
  29 do
  30     echo "Element [$i]: ${array2[$i]}"
  31 done
  32 # See also the more general code example in basics-reviewed.bash.
  33 
  34 
  35 declare -a dest
  36 
  37 # Combine (append) two arrays into a third array.
  38 echo
  39 echo 'Conditions: Unquoted, default IFS, All-Elements-Of operator'
  40 echo '- Undefined elements not present, subscripts not maintained. -'
  41 # # The undefined elements do not exist; they are not being dropped.
  42 
  43 dest=( ${array1[@]} ${array2[@]} )
  44 # dest=${array1[@]}${array2[@]}     # Strange results, possibly a bug.
  45 
  46 # Now, list the result.
  47 echo
  48 echo '- - Testing Array Append - -'
  49 cnt=${#dest[@]}
  50 
  51 echo "Number of elements: $cnt"
  52 for (( i = 0 ; i < cnt ; i++ ))
  53 do
  54     echo "Element [$i]: ${dest[$i]}"
  55 done
  56 
  57 # Assign an array to a single array element (twice).
  58 dest[0]=${array1[@]}
  59 dest[1]=${array2[@]}
  60 
  61 # List the result.
  62 echo
  63 echo '- - Testing modified array - -'
  64 cnt=${#dest[@]}
  65 
  66 echo "Number of elements: $cnt"
  67 for (( i = 0 ; i < cnt ; i++ ))
  68 do
  69     echo "Element [$i]: ${dest[$i]}"
  70 done
  71 
  72 # Examine the modified second element.
  73 echo
  74 echo '- - Reassign and list second element - -'
  75 
  76 declare -a subArray=${dest[1]}
  77 cnt=${#subArray[@]}
  78 
  79 echo "Number of elements: $cnt"
  80 for (( i = 0 ; i < cnt ; i++ ))
  81 do
  82     echo "Element [$i]: ${subArray[$i]}"
  83 done
  84 
  85 #  The assignment of an entire array to a single element
  86 #+ of another array using the '=${ ... }' array assignment
  87 #+ has converted the array being assigned into a string,
  88 #+ with the elements separated by a space (the first character of IFS).
  89 
  90 # If the original elements didn't contain whitespace . . .
  91 # If the original array isn't subscript sparse . . .
  92 # Then we could get the original array structure back again.
  93 
  94 # Restore from the modified second element.
  95 echo
  96 echo '- - Listing restored element - -'
  97 
  98 declare -a subArray=( ${dest[1]} )
  99 cnt=${#subArray[@]}
 100 
 101 echo "Number of elements: $cnt"
 102 for (( i = 0 ; i < cnt ; i++ ))
 103 do
 104     echo "Element [$i]: ${subArray[$i]}"
 105 done
 106 echo '- - Do not depend on this behavior. - -'
 107 echo '- - This behavior is subject to change - -'
 108 echo '- - in versions of Bash newer than version 2.05b - -'
 109 
 110 # MSZ: Sorry about any earlier confusion folks.
 111 
 112 exit 0

--

Arrays permit deploying old familiar algorithms as shell scripts. Whether this is necessarily a good idea is left to the reader to decide.


Example 26-11. The Bubble Sort

   1 #!/bin/bash
   2 # bubble.sh: Bubble sort, of sorts.
   3 
   4 # Recall the algorithm for a bubble sort. In this particular version...
   5 
   6 #  With each successive pass through the array to be sorted,
   7 #+ compare two adjacent elements, and swap them if out of order.
   8 #  At the end of the first pass, the "heaviest" element has sunk to bottom.
   9 #  At the end of the second pass, the next "heaviest" one has sunk next to bottom.
  10 #  And so forth.
  11 #  This means that each successive pass needs to traverse less of the array.
  12 #  You will therefore notice a speeding up in the printing of the later passes.
  13 
  14 
  15 exchange()
  16 {
  17   # Swaps two members of the array.
  18   local temp=${Countries[$1]} #  Temporary storage
  19                               #+ for element getting swapped out.
  20   Countries[$1]=${Countries[$2]}
  21   Countries[$2]=$temp
  22   
  23   return
  24 }  
  25 
  26 declare -a Countries  #  Declare array,
  27                       #+ optional here since it's initialized below.
  28 
  29 #  Is it permissable to split an array variable over multiple lines
  30 #+ using an escape (\)?
  31 #  Yes.
  32 
  33 Countries=(Netherlands Ukraine Zaire Turkey Russia Yemen Syria \
  34 Brazil Argentina Nicaragua Japan Mexico Venezuela Greece England \
  35 Israel Peru Canada Oman Denmark Wales France Kenya \
  36 Xanadu Qatar Liechtenstein Hungary)
  37 
  38 # "Xanadu" is the mythical place where, according to Coleridge,
  39 #+ Kubla Khan did a pleasure dome decree.
  40 
  41 
  42 clear                      # Clear the screen to start with. 
  43 
  44 echo "0: ${Countries[*]}"  # List entire array at pass 0.
  45 
  46 number_of_elements=${#Countries[@]}
  47 let "comparisons = $number_of_elements - 1"
  48 
  49 count=1 # Pass number.
  50 
  51 while [ "$comparisons" -gt 0 ]          # Beginning of outer loop
  52 do
  53 
  54   index=0  # Reset index to start of array after each pass.
  55 
  56   while [ "$index" -lt "$comparisons" ] # Beginning of inner loop
  57   do
  58     if [ ${Countries[$index]} \> ${Countries[`expr $index + 1`]} ]
  59     #  If out of order...
  60     #  Recalling that \> is ASCII comparison operator
  61     #+ within single brackets.
  62 
  63     #  if [[ ${Countries[$index]} > ${Countries[`expr $index + 1`]} ]]
  64     #+ also works.
  65     then
  66       exchange $index `expr $index + 1`  # Swap.
  67     fi  
  68     let "index += 1"  # Or,   index+=1   on Bash, ver. 3.1 or newer.
  69   done # End of inner loop
  70 
  71 # ----------------------------------------------------------------------
  72 # Paulo Marcel Coelho Aragao suggests for-loops as a simpler altenative.
  73 #
  74 # for (( last = $number_of_elements - 1 ; last > 0 ; last-- ))
  75 ##                     Fix by C.Y. Hunt          ^   (Thanks!)
  76 # do
  77 #     for (( i = 0 ; i < last ; i++ ))
  78 #     do
  79 #         [[ "${Countries[$i]}" > "${Countries[$((i+1))]}" ]] \
  80 #             && exchange $i $((i+1))
  81 #     done
  82 # done
  83 # ----------------------------------------------------------------------
  84   
  85 
  86 let "comparisons -= 1" #  Since "heaviest" element bubbles to bottom,
  87                        #+ we need do one less comparison each pass.
  88 
  89 echo
  90 echo "$count: ${Countries[@]}"  # Print resultant array at end of each pass.
  91 echo
  92 let "count += 1"                # Increment pass count.
  93 
  94 done                            # End of outer loop
  95                                 # All done.
  96 
  97 exit 0

--

Is it possible to nest arrays within arrays?

   1 #!/bin/bash
   2 # "Nested" array.
   3 
   4 #  Michael Zick provided this example,
   5 #+ with corrections and clarifications by William Park.
   6 
   7 AnArray=( $(ls --inode --ignore-backups --almost-all \
   8 	--directory --full-time --color=none --time=status \
   9 	--sort=time -l ${PWD} ) )  # Commands and options.
  10 
  11 # Spaces are significant . . . and don't quote anything in the above.
  12 
  13 SubArray=( ${AnArray[@]:11:1}  ${AnArray[@]:6:5} )
  14 #  This array has six elements:
  15 #+     SubArray=( [0]=${AnArray[11]} [1]=${AnArray[6]} [2]=${AnArray[7]}
  16 #      [3]=${AnArray[8]} [4]=${AnArray[9]} [5]=${AnArray[10]} )
  17 #
  18 #  Arrays in Bash are (circularly) linked lists
  19 #+ of type string (char *).
  20 #  So, this isn't actually a nested array,
  21 #+ but it's functionally similar.
  22 
  23 echo "Current directory and date of last status change:"
  24 echo "${SubArray[@]}"
  25 
  26 exit 0

--

Embedded arrays in combination with indirect references create some fascinating possibilities


Example 26-12. Embedded arrays and indirect references

   1 #!/bin/bash
   2 # embedded-arrays.sh
   3 # Embedded arrays and indirect references.
   4 
   5 # This script by Dennis Leeuw.
   6 # Used with permission.
   7 # Modified by document author.
   8 
   9 
  10 ARRAY1=(
  11         VAR1_1=value11
  12         VAR1_2=value12
  13         VAR1_3=value13
  14 )
  15 
  16 ARRAY2=(
  17         VARIABLE="test"
  18         STRING="VAR1=value1 VAR2=value2 VAR3=value3"
  19         ARRAY21=${ARRAY1[*]}
  20 )       # Embed ARRAY1 within this second array.
  21 
  22 function print () {
  23         OLD_IFS="$IFS"
  24         IFS=$'\n'       #  To print each array element
  25                         #+ on a separate line.
  26         TEST1="ARRAY2[*]"
  27         local ${!TEST1} # See what happens if you delete this line.
  28         #  Indirect reference.
  29 	#  This makes the components of $TEST1
  30 	#+ accessible to this function.
  31 
  32 
  33         #  Let's see what we've got so far.
  34         echo
  35         echo "\$TEST1 = $TEST1"       #  Just the name of the variable.
  36         echo; echo
  37         echo "{\$TEST1} = ${!TEST1}"  #  Contents of the variable.
  38                                       #  That's what an indirect
  39                                       #+ reference does.
  40         echo
  41         echo "-------------------------------------------"; echo
  42         echo
  43 
  44 
  45         # Print variable
  46         echo "Variable VARIABLE: $VARIABLE"
  47 	
  48         # Print a string element
  49         IFS="$OLD_IFS"
  50         TEST2="STRING[*]"
  51         local ${!TEST2}      # Indirect reference (as above).
  52         echo "String element VAR2: $VAR2 from STRING"
  53 
  54         # Print an array element
  55         TEST2="ARRAY21[*]"
  56         local ${!TEST2}      # Indirect reference (as above).
  57         echo "Array element VAR1_1: $VAR1_1 from ARRAY21"
  58 }
  59 
  60 print
  61 echo
  62 
  63 exit 0
  64 
  65 #   As the author of the script notes,
  66 #+ "you can easily expand it to create named-hashes in bash."
  67 #   (Difficult) exercise for the reader: implement this.

--

Arrays enable implementing a shell script version of the Sieve of Eratosthenes. Of course, a resource-intensive application of this nature should really be written in a compiled language, such as C. It runs excruciatingly slowly as a script.


Example 26-13. The Sieve of Eratosthenes

   1 #!/bin/bash
   2 # sieve.sh (ex68.sh)
   3 
   4 # Sieve of Eratosthenes
   5 # Ancient algorithm for finding prime numbers.
   6 
   7 #  This runs a couple of orders of magnitude slower
   8 #+ than the equivalent program written in C.
   9 
  10 LOWER_LIMIT=1       # Starting with 1.
  11 UPPER_LIMIT=1000    # Up to 1000.
  12 # (You may set this higher . . . if you have time on your hands.)
  13 
  14 PRIME=1
  15 NON_PRIME=0
  16 
  17 let SPLIT=UPPER_LIMIT/2
  18 # Optimization:
  19 # Need to test numbers only halfway to upper limit (why?).
  20 
  21 
  22 declare -a Primes
  23 # Primes[] is an array.
  24 
  25 
  26 initialize ()
  27 {
  28 # Initialize the array.
  29 
  30 i=$LOWER_LIMIT
  31 until [ "$i" -gt "$UPPER_LIMIT" ]
  32 do
  33   Primes[i]=$PRIME
  34   let "i += 1"
  35 done
  36 #  Assume all array members guilty (prime)
  37 #+ until proven innocent.
  38 }
  39 
  40 print_primes ()
  41 {
  42 # Print out the members of the Primes[] array tagged as prime.
  43 
  44 i=$LOWER_LIMIT
  45 
  46 until [ "$i" -gt "$UPPER_LIMIT" ]
  47 do
  48 
  49   if [ "${Primes[i]}" -eq "$PRIME" ]
  50   then
  51     printf "%8d" $i
  52     # 8 spaces per number gives nice, even columns.
  53   fi
  54   
  55   let "i += 1"
  56   
  57 done
  58 
  59 }
  60 
  61 sift () # Sift out the non-primes.
  62 {
  63 
  64 let i=$LOWER_LIMIT+1
  65 # We know 1 is prime, so let's start with 2.
  66 
  67 until [ "$i" -gt "$UPPER_LIMIT" ]
  68 do
  69 
  70 if [ "${Primes[i]}" -eq "$PRIME" ]
  71 # Don't bother sieving numbers already sieved (tagged as non-prime).
  72 then
  73 
  74   t=$i
  75 
  76   while [ "$t" -le "$UPPER_LIMIT" ]
  77   do
  78     let "t += $i "
  79     Primes[t]=$NON_PRIME
  80     # Tag as non-prime all multiples.
  81   done
  82 
  83 fi  
  84 
  85   let "i += 1"
  86 done  
  87 
  88 
  89 }
  90 
  91 
  92 # ==============================================
  93 # main ()
  94 # Invoke the functions sequentially.
  95 initialize
  96 sift
  97 print_primes
  98 # This is what they call structured programming.
  99 # ==============================================
 100 
 101 echo
 102 
 103 exit 0
 104 
 105 
 106 
 107 # -------------------------------------------------------- #
 108 # Code below line will not execute, because of 'exit.'
 109 
 110 #  This improved version of the Sieve, by Stephane Chazelas,
 111 #+ executes somewhat faster.
 112 
 113 # Must invoke with command-line argument (limit of primes).
 114 
 115 UPPER_LIMIT=$1                  # From command line.
 116 let SPLIT=UPPER_LIMIT/2         # Halfway to max number.
 117 
 118 Primes=( '' $(seq $UPPER_LIMIT) )
 119 
 120 i=1
 121 until (( ( i += 1 ) > SPLIT ))  # Need check only halfway.
 122 do
 123   if [[ -n $Primes[i] ]]
 124   then
 125     t=$i
 126     until (( ( t += i ) > UPPER_LIMIT ))
 127     do
 128       Primes[t]=
 129     done
 130   fi  
 131 done  
 132 echo ${Primes[*]}
 133 
 134 exit $?


Example 26-14. The Sieve of Eratosthenes, Optimized

   1 #!/bin/bash
   2 # Optimized Sieve of Eratosthenes
   3 # Script by Jared Martin, with very minor changes by ABS Guide author.
   4 # Used in ABS Guide with permission (thanks!).
   5 
   6 # Based on script in Advanced Bash Scripting Guide.
   7 # http://tldp.org/LDP/abs/html/arrays.html#PRIMES0 (ex68.sh).
   8 
   9 # http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf (reference)
  10 # Check results against http://primes.utm.edu/lists/small/1000.txt
  11 
  12 # Necessary but not sufficient would be, e.g.,
  13 #     (($(sieve 7919 | wc -w) == 1000)) && echo "7919 is the 1000th prime"
  14 
  15 UPPER_LIMIT=${1:?"Need an upper limit of primes to search."}
  16 
  17 Primes=( '' $(seq ${UPPER_LIMIT}) )
  18 
  19 typeset -i i t
  20 Primes[i=1]='' # 1 is not a prime.
  21 until (( ( i += 1 ) > (${UPPER_LIMIT}/i) ))  # Need check only ith-way.
  22   do                                         # Why?
  23     if ((${Primes[t=i*(i-1), i]}))
  24     # Obscure, but instructive, use of arithmetic expansion in subscript.
  25     then
  26       until (( ( t += i ) > ${UPPER_LIMIT} ))
  27         do Primes[t]=; done
  28     fi
  29   done
  30 
  31 # echo ${Primes[*]}
  32 echo   # Change to original script for pretty-printing (80-col. display).
  33 printf "%8d" ${Primes[*]}
  34 echo; echo
  35 
  36 exit $?

Compare these array-based prime number generators with alternatives that do not use arrays, Example A-16, and Example 15-46.

--

Arrays lend themselves, to some extent, to emulating data structures for which Bash has no native support.


Example 26-15. Emulating a push-down stack

   1 #!/bin/bash
   2 # stack.sh: push-down stack simulation
   3 
   4 #  Similar to the CPU stack, a push-down stack stores data items
   5 #+ sequentially, but releases them in reverse order, last-in first-out.
   6 
   7 BP=100            #  Base Pointer of stack array.
   8                   #  Begin at element 100.
   9 
  10 SP=$BP            #  Stack Pointer.
  11                   #  Initialize it to "base" (bottom) of stack.
  12 
  13 Data=             #  Contents of stack location.  
  14                   #  Must use global variable,
  15                   #+ because of limitation on function return range.
  16 
  17 declare -a stack
  18 
  19 
  20 push()            # Push item on stack.
  21 {
  22 if [ -z "$1" ]    # Nothing to push?
  23 then
  24   return
  25 fi
  26 
  27 let "SP -= 1"     # Bump stack pointer.
  28 stack[$SP]=$1
  29 
  30 return
  31 }
  32 
  33 pop()                    # Pop item off stack.
  34 {
  35 Data=                    # Empty out data item.
  36 
  37 if [ "$SP" -eq "$BP" ]   # Stack empty?
  38 then
  39   return
  40 fi                       #  This also keeps SP from getting past 100,
  41                          #+ i.e., prevents a runaway stack.
  42 
  43 Data=${stack[$SP]}
  44 let "SP += 1"            # Bump stack pointer.
  45 return
  46 }
  47 
  48 status_report()          # Find out what's happening.
  49 {
  50 echo "-------------------------------------"
  51 echo "REPORT"
  52 echo "Stack Pointer = $SP"
  53 echo "Just popped \""$Data"\" off the stack."
  54 echo "-------------------------------------"
  55 echo
  56 }
  57 
  58 
  59 # =======================================================
  60 # Now, for some fun.
  61 
  62 echo
  63 
  64 # See if you can pop anything off empty stack.
  65 pop
  66 status_report
  67 
  68 echo
  69 
  70 push garbage
  71 pop
  72 status_report     # Garbage in, garbage out.      
  73 
  74 value1=23; push $value1
  75 value2=skidoo; push $value2
  76 value3=FINAL; push $value3
  77 
  78 pop              # FINAL
  79 status_report
  80 pop              # skidoo
  81 status_report
  82 pop              # 23
  83 status_report    # Last-in, first-out!
  84 
  85 #  Notice how the stack pointer decrements with each push,
  86 #+ and increments with each pop.
  87 
  88 echo
  89 
  90 exit 0
  91 
  92 # =======================================================
  93 
  94 
  95 # Exercises:
  96 # ---------
  97 
  98 # 1)  Modify the "push()" function to permit pushing
  99 #   + multiple element on the stack with a single function call.
 100 
 101 # 2)  Modify the "pop()" function to permit popping
 102 #   + multiple element from the stack with a single function call.
 103 
 104 # 3)  Add error checking to the critical functions.
 105 #     That is, return an error code, depending on
 106 #   + successful or unsuccessful completion of the operation,
 107 #   + and take appropriate action.
 108 
 109 # 4)  Using this script as a starting point,
 110 #   + write a stack-based 4-function calculator.

--

Fancy manipulation of array "subscripts" may require intermediate variables. For projects involving this, again consider using a more powerful programming language, such as Perl or C.


Example 26-16. Complex array application: Exploring a weird mathematical series

   1 #!/bin/bash
   2 
   3 # Douglas Hofstadter's notorious "Q-series":
   4 
   5 # Q(1) = Q(2) = 1
   6 # Q(n) = Q(n - Q(n-1)) + Q(n - Q(n-2)), for n>2
   7 
   8 #  This is a "chaotic" integer series with strange
   9 #+ and unpredictable behavior.
  10 #  The first 20 terms of the series are:
  11 #  1 1 2 3 3 4 5 5 6 6 6 8 8 8 10 9 10 11 11 12 
  12 
  13 #  See Hofstadter's book, _Goedel, Escher, Bach: An Eternal Golden Braid_,
  14 #+ p. 137, ff.
  15 
  16 
  17 LIMIT=100     # Number of terms to calculate.
  18 LINEWIDTH=20  # Number of terms printed per line.
  19 
  20 Q[1]=1        # First two terms of series are 1.
  21 Q[2]=1
  22 
  23 echo
  24 echo "Q-series [$LIMIT terms]:"
  25 echo -n "${Q[1]} "             # Output first two terms.
  26 echo -n "${Q[2]} "
  27 
  28 for ((n=3; n <= $LIMIT; n++))  # C-like loop expression.
  29 do   # Q[n] = Q[n - Q[n-1]] + Q[n - Q[n-2]]  for n>2
  30 #    Need to break the expression into intermediate terms,
  31 #+   since Bash doesn't handle complex array arithmetic very well.
  32 
  33   let "n1 = $n - 1"        # n-1
  34   let "n2 = $n - 2"        # n-2
  35   
  36   t0=`expr $n - ${Q[n1]}`  # n - Q[n-1]
  37   t1=`expr $n - ${Q[n2]}`  # n - Q[n-2]
  38   
  39   T0=${Q[t0]}              # Q[n - Q[n-1]]
  40   T1=${Q[t1]}              # Q[n - Q[n-2]]
  41 
  42 Q[n]=`expr $T0 + $T1`      # Q[n - Q[n-1]] + Q[n - Q[n-2]]
  43 echo -n "${Q[n]} "
  44 
  45 if [ `expr $n % $LINEWIDTH` -eq 0 ]    # Format output.
  46 then   #      ^ modulo
  47   echo # Break lines into neat chunks.
  48 fi
  49 
  50 done
  51 
  52 echo
  53 
  54 exit 0
  55 
  56 #  This is an iterative implementation of the Q-series.
  57 #  The more intuitive recursive implementation is left as an exercise.
  58 #  Warning: calculating this series recursively takes a VERY long time
  59 #+ via a script. C/C++ would be orders of magnitude faster.

--

Bash supports only one-dimensional arrays, though a little trickery permits simulating multi-dimensional ones.


Example 26-17. Simulating a two-dimensional array, then tilting it

   1 #!/bin/bash
   2 # twodim.sh: Simulating a two-dimensional array.
   3 
   4 # A one-dimensional array consists of a single row.
   5 # A two-dimensional array stores rows sequentially.
   6 
   7 Rows=5
   8 Columns=5
   9 # 5 X 5 Array.
  10 
  11 declare -a alpha     # char alpha [Rows] [Columns];
  12                      # Unnecessary declaration. Why?
  13 
  14 load_alpha ()
  15 {
  16 local rc=0
  17 local index
  18 
  19 for i in A B C D E F G H I J K L M N O P Q R S T U V W X Y
  20 do     # Use different symbols if you like.
  21   local row=`expr $rc / $Columns`
  22   local column=`expr $rc % $Rows`
  23   let "index = $row * $Rows + $column"
  24   alpha[$index]=$i
  25 # alpha[$row][$column]
  26   let "rc += 1"
  27 done  
  28 
  29 #  Simpler would be
  30 #+   declare -a alpha=( A B C D E F G H I J K L M N O P Q R S T U V W X Y )
  31 #+ but this somehow lacks the "flavor" of a two-dimensional array.
  32 }
  33 
  34 print_alpha ()
  35 {
  36 local row=0
  37 local index
  38 
  39 echo
  40 
  41 while [ "$row" -lt "$Rows" ]   #  Print out in "row major" order:
  42 do                             #+ columns vary,
  43                                #+ while row (outer loop) remains the same.
  44   local column=0
  45 
  46   echo -n "       "            #  Lines up "square" array with rotated one.
  47   
  48   while [ "$column" -lt "$Columns" ]
  49   do
  50     let "index = $row * $Rows + $column"
  51     echo -n "${alpha[index]} "  # alpha[$row][$column]
  52     let "column += 1"
  53   done
  54 
  55   let "row += 1"
  56   echo
  57 
  58 done  
  59 
  60 # The simpler equivalent is
  61 #     echo ${alpha[*]} | xargs -n $Columns
  62 
  63 echo
  64 }
  65 
  66 filter ()     # Filter out negative array indices.
  67 {
  68 
  69 echo -n "  "  # Provides the tilt.
  70               # Explain how.
  71 
  72 if [[ "$1" -ge 0 &&  "$1" -lt "$Rows" && "$2" -ge 0 && "$2" -lt "$Columns" ]]
  73 then
  74     let "index = $1 * $Rows + $2"
  75     # Now, print it rotated.
  76     echo -n " ${alpha[index]}"
  77     #           alpha[$row][$column]
  78 fi    
  79 
  80 }
  81   
  82 
  83 
  84 
  85 rotate ()  #  Rotate the array 45 degrees --
  86 {          #+ "balance" it on its lower lefthand corner.
  87 local row
  88 local column
  89 
  90 for (( row = Rows; row > -Rows; row-- ))
  91   do       # Step through the array backwards. Why?
  92 
  93   for (( column = 0; column < Columns; column++ ))
  94   do
  95 
  96     if [ "$row" -ge 0 ]
  97     then
  98       let "t1 = $column - $row"
  99       let "t2 = $column"
 100     else
 101       let "t1 = $column"
 102       let "t2 = $column + $row"
 103     fi  
 104 
 105     filter $t1 $t2   # Filter out negative array indices.
 106                      # What happens if you don't do this?
 107   done
 108 
 109   echo; echo
 110 
 111 done 
 112 
 113 #  Array rotation inspired by examples (pp. 143-146) in
 114 #+ "Advanced C Programming on the IBM PC," by Herbert Mayer
 115 #+ (see bibliography).
 116 #  This just goes to show that much of what can be done in C
 117 #+ can also be done in shell scripting.
 118 
 119 }
 120 
 121 
 122 #--------------- Now, let the show begin. ------------#
 123 load_alpha     # Load the array.
 124 print_alpha    # Print it out.  
 125 rotate         # Rotate it 45 degrees counterclockwise.
 126 #-----------------------------------------------------#
 127 
 128 exit 0
 129 
 130 # This is a rather contrived, not to mention inelegant simulation.
 131 
 132 # Exercises:
 133 # ---------
 134 # 1)  Rewrite the array loading and printing functions
 135 #     in a more intuitive and less kludgy fashion.
 136 #
 137 # 2)  Figure out how the array rotation functions work.
 138 #     Hint: think about the implications of backwards-indexing an array.
 139 #
 140 # 3)  Rewrite this script to handle a non-square array,
 141 #     such as a 6 X 4 one.
 142 #     Try to minimize "distortion" when the array is rotated.

A two-dimensional array is essentially equivalent to a one-dimensional one, but with additional addressing modes for referencing and manipulating the individual elements by row and column position.

For an even more elaborate example of simulating a two-dimensional array, see Example A-10.

--

For more interesting scripts using arrays, see: