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 (find the contents of) an array element, use curly bracket notation, that is, ${variable[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 o.k.
  12 
  13 
  14 echo -n "area[11] = "
  15 echo ${area[11]}    #  {curly brackets} needed
  16 
  17 echo -n "area[13] = "
  18 echo ${area[13]}
  19 
  20 echo "Contents of area[51] are ${area[51]}."
  21 
  22 # Contents of uninitialized array variable print blank.
  23 echo -n "area[43] = "
  24 echo ${area[43]}
  25 echo "(area[43] unassigned)"
  26 
  27 echo
  28 
  29 # Sum of two array variables assigned to third
  30 area[5]=`expr ${area[11]} + ${area[13]}`
  31 echo "area[5] = area[11] + area[13]"
  32 echo -n "area[5] = "
  33 echo ${area[5]}
  34 
  35 area[6]=`expr ${area[11]} + ${area[51]}`
  36 echo "area[6] = area[11] + area[51]"
  37 echo -n "area[6] = "
  38 echo ${area[6]}
  39 # This fails because adding an integer to a string is not permitted.
  40 
  41 echo; echo; echo
  42 
  43 # -----------------------------------------------------------------
  44 # Another array, "area2".
  45 # Another way of assigning array variables...
  46 # array_name=( XXX YYY ZZZ ... )
  47 
  48 area2=( zero one two three four )
  49 
  50 echo -n "area2[0] = "
  51 echo ${area2[0]}
  52 # Aha, zero-based indexing (first element of array is [0], not [1]).
  53 
  54 echo -n "area2[1] = "
  55 echo ${area2[1]}    # [1] is second element of array.
  56 # -----------------------------------------------------------------
  57 
  58 echo; echo; echo
  59 
  60 # -----------------------------------------------
  61 # Yet another array, "area3".
  62 # Yet another way of assigning array variables...
  63 # array_name=([xx]=XXX [yy]=YYY ...)
  64 
  65 area3=([17]=seventeen [24]=twenty-four)
  66 
  67 echo -n "area3[17] = "
  68 echo ${area3[17]}
  69 
  70 echo -n "area3[24] = "
  71 echo ${area3[24]}
  72 # -----------------------------------------------
  73 
  74 exit 0

Note

Bash permits array operations on variables, even if the variables are not explicitly declared as arrays.
   1 string=abcABC123ABCabc
   2 echo ${string[@]}               # abcABC123ABCabc
   3 echo ${string[*]}               # abcABC123ABCabc 
   4 echo ${string[0]}               # abcABC123ABCabc
   5 echo ${string[1]}               # No output!
   6                                 # Why?
   7 echo ${#string[@]}              # 1
   8                                 # One element in the array.
   9                                 # The string itself.
  10 
  11 # Thank you, Michael Zick, for pointing this out.
Once again this demonstrates that Bash variables are untyped.


Example 26-2. Formatting a poem

   1 #!/bin/bash
   2 # poem.sh: Pretty-prints one of the 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 
  11 # Attribution.
  12 Attrib[1]=" Wallace Stevens"
  13 Attrib[2]="\"Thirteen Ways of Looking at a Blackbird\""
  14 # Above poem is in the Public Domain (copyright expired).
  15 
  16 for index in 1 2 3 4 5    # Five lines.
  17 do
  18   printf "     %s\n" "${Line[index]}"
  19 done
  20 
  21 for index in 1 2          # Two attribution lines.
  22 do
  23   printf "          %s\n" "${Attrib[index]}"
  24 done
  25 
  26 exit 0

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

   1 array=( zero one two three four five )
   2 
   3 echo ${array[0]}       #  zero
   4 echo ${array:0}        #  zero
   5                        #  Parameter expansion of first element.
   6 echo ${array:1}        #  ero
   7                        #  Parameter expansion of first element,
   8                        #+ starting at position #1 (2nd character).
   9 
  10 echo ${#array}         #  4
  11                        #  Length of first element of array.
  12 
  13 
  14 
  15 array2=( [0]="first element" [1]="second element" [3]="fourth element" )
  16 
  17 echo ${array2[0]}      # first element
  18 echo ${array2[1]}      # second element
  19 echo ${array2[2]}      #
  20                        # Skipped in initialization, therefore null.
  21 echo ${array2[3]}      # fourth element

Command substitution can construct the individual elements of an array.


Example 26-3. 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 " -- "    # Use " -- " as a field separator.
  18 done
  19 
  20 echo
  21 
  22 exit 0
  23 
  24 # Exercise:
  25 # --------
  26 #  Modify this script so it lists itself
  27 #+ in its original format,
  28 #+ 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-4. Some special properties of arrays

   1 #!/bin/bash
   2 
   3 declare -a colors
   4 # Permits declaring an array without specifying its size.
   5 
   6 echo "Enter your favorite colors (separated from each other by a space)."
   7 
   8 read -a colors    # Enter at least 3 colors to demonstrate features below.
   9 #  Special option to 'read' command,
  10 #+ allowing assignment of elements in an array.
  11 
  12 echo
  13 
  14 element_count=${#colors[@]}
  15 # Special syntax to extract number of elements in array.
  16 #     element_count=${#colors[*]} works also.
  17 #
  18 #  The "@" variable allows word splitting within quotes
  19 #+ (extracts variables separated by whitespace).
  20 
  21 index=0
  22 
  23 while [ "$index" -lt "$element_count" ]
  24 do    # List all the elements in the array.
  25   echo ${colors[$index]}
  26   let "index = $index + 1"
  27 done
  28 # Each array element listed on a separate line.
  29 # If this is not desired, use  echo -n "${colors[$index]} "
  30 #
  31 # Doing it with a "for" loop instead:
  32 #   for i in "${colors[@]}"
  33 #   do
  34 #     echo "$i"
  35 #   done
  36 # (Thanks, S.C.)
  37 
  38 echo
  39 
  40 # Again, list all the elements in the array, but using a more elegant method.
  41   echo ${colors[@]}          # echo ${colors[*]} also works.
  42 
  43 echo
  44 
  45 # The "unset" command deletes elements of an array, or entire array.
  46 unset colors[1]              # Remove 2nd element of array.
  47                              # Same effect as   colors[1]=
  48 echo  ${colors[@]}           # List array again, missing 2nd element.
  49 
  50 unset colors                 # Delete entire array.
  51                              #  unset colors[*] and
  52                              #+ unset colors[@] also work.
  53 echo; echo -n "Colors gone."			   
  54 echo ${colors[@]}            # List array again, now empty.
  55 
  56 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-5. 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 for extending it.
   6 
   7 
   8 # An empty array is not the same as an array with empty elements.
   9 
  10 array0=( first second third )
  11 array1=( '' )   # "array1" has one empty element.
  12 array2=( )      # No elements... "array2" is empty.
  13 
  14 echo
  15 ListArray()
  16 {
  17 echo
  18 echo "Elements in array0:  ${array0[@]}"
  19 echo "Elements in array1:  ${array1[@]}"
  20 echo "Elements in array2:  ${array2[@]}"
  21 echo
  22 echo "Length of first element in array0 = ${#array0}"
  23 echo "Length of first element in array1 = ${#array1}"
  24 echo "Length of first element in array2 = ${#array2}"
  25 echo
  26 echo "Number of elements in array0 = ${#array0[*]}"  # 3
  27 echo "Number of elements in array1 = ${#array1[*]}"  # 1  (surprise!)
  28 echo "Number of elements in array2 = ${#array2[*]}"  # 0
  29 }
  30 
  31 # ===================================================================
  32 
  33 ListArray
  34 
  35 # Try extending those arrays
  36 
  37 # Adding an element to an array.
  38 array0=( "${array0[@]}" "new1" )
  39 array1=( "${array1[@]}" "new1" )
  40 array2=( "${array2[@]}" "new1" )
  41 
  42 ListArray
  43 
  44 # or
  45 array0[${#array0[*]}]="new2"
  46 array1[${#array1[*]}]="new2"
  47 array2[${#array2[*]}]="new2"
  48 
  49 ListArray
  50 
  51 # When extended as above; arrays are 'stacks'
  52 # The above is the 'push'
  53 # The stack 'height' is:
  54 height=${#array2[@]}
  55 echo
  56 echo "Stack height for array2 = $height"
  57 
  58 # The 'pop' is:
  59 unset array2[${#array2[@]}-1]	# Arrays are zero based
  60 height=${#array2[@]}
  61 echo
  62 echo "POP"
  63 echo "New stack height for array2 = $height"
  64 
  65 ListArray
  66 
  67 # List only 2nd and 3rd elements of array0
  68 from=1		# Zero based numbering
  69 to=2		#
  70 declare -a array3=( ${array0[@]:1:2} )
  71 echo
  72 echo "Elements in array3:  ${array3[@]}"
  73 
  74 # Works like a string (array of characters)
  75 # Try some other "string" forms
  76 
  77 # Replacement
  78 declare -a array4=( ${array0[@]/second/2nd} )
  79 echo
  80 echo "Elements in array4:  ${array4[@]}"
  81 
  82 # Replace all matching wildcarded string
  83 declare -a array5=( ${array0[@]//new?/old} )
  84 echo
  85 echo "Elements in array5:  ${array5[@]}"
  86 
  87 # Just when you are getting the feel for this...
  88 declare -a array6=( ${array0[@]#*new} )
  89 echo # This one might surprise you
  90 echo "Elements in array6:  ${array6[@]}"
  91 
  92 declare -a array7=( ${array0[@]#new1} )
  93 echo # After array6 this should not be a surprise
  94 echo "Elements in array7:  ${array7[@]}"
  95 
  96 # Which looks a lot like...
  97 declare -a array8=( ${array0[@]/new1/} )
  98 echo
  99 echo "Elements in array8:  ${array8[@]}"
 100 
 101 #  So what can one say about this?
 102 
 103 #  The string operations are performed on
 104 #+ each of the elements in var[@] in succession.
 105 #  Therefore : BASH supports string vector operations
 106 #  If the result is a zero length string, that
 107 #+ element disappears in the resulting assignment.
 108 
 109 #  Question, are those strings hard or soft quotes?
 110 
 111 zap='new*'
 112 declare -a array9=( ${array0[@]/$zap/} )
 113 echo
 114 echo "Elements in array9:  ${array9[@]}"
 115 
 116 # Just when you thought you where still in Kansas...
 117 declare -a array10=( ${array0[@]#$zap} )
 118 echo
 119 echo "Elements in array10:  ${array10[@]}"
 120 
 121 # Compare array7 with array10
 122 # Compare array8 with array9
 123 
 124 # Answer, must be soft quotes.
 125 
 126 exit 0

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 # Adding an element to an array.
   7 array=( "${array[@]}" "new element" )
   8 # or
   9 array[${#array[*]}]="new element"
  10 
  11 # 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" | tr '\n' ' '`)  # Loads contents
  14                                            # of $filename into array1.
  15 #         list file to stdout.
  16 #                           change linefeeds in file to spaces. 
  17 
  18 echo ${array1[@]}            # List the array.
  19 #                              1 a b c 2 d e fg
  20 #
  21 #  Each whitespace-separated "word" in the file
  22 #+ has been assigned to an element of the array.
  23 
  24 element_count=${#array1[*]}
  25 echo $element_count          # 8

Clever scripting makes it possible to add array operations.


Example 26-6. 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

--

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-7. An old friend: 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"
  69   done # End of inner loop
  70   
  71 
  72 let "comparisons -= 1" #  Since "heaviest" element bubbles to bottom,
  73                        #+ we need do one less comparison each pass.
  74 
  75 echo
  76 echo "$count: ${Countries[@]}"  # Print resultant array at end of each pass.
  77 echo
  78 let "count += 1"                # Increment pass count.
  79 
  80 done                            # End of outer loop
  81                                 # All done.
  82 
  83 exit 0

--

Is it possible to nest arrays within arrays?

   1 #!/bin/bash
   2 # Nested array.
   3 
   4 # Michael Zick provided this example.
   5 
   6 AnArray=( $(ls --inode --ignore-backups --almost-all \
   7 	--directory --full-time --color=none --time=status \
   8 	--sort=time -l ${PWD} ) )  # Commands and options.
   9 
  10 # Spaces are significant . . . and don't quote anything in the above.
  11 
  12 SubArray=( ${AnArray[@]:11:1}  ${AnArray[@]:6:5} )
  13 # Array has two elements, each of which is in turn an array.
  14 
  15 echo "Current directory and date of last status change:"
  16 echo "${SubArray[@]}"
  17 
  18 exit 0

--

Embedded arrays in combination with indirect references create some fascinating possibilities


Example 26-8. 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-9. Complex array application: Sieve of Eratosthenes

   1 #!/bin/bash
   2 # sieve.sh
   3 
   4 # Sieve of Eratosthenes
   5 # Ancient algorithm for finding prime numbers.
   6 
   7 # This runs a couple of orders of magnitude
   8 # slower than the equivalent C program.
   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.
  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 # Invoke the functions sequentially.
  93 initialize
  94 sift
  95 print_primes
  96 # This is what they call structured programming.
  97 
  98 echo
  99 
 100 exit 0
 101 
 102 
 103 
 104 # ----------------------------------------------- #
 105 # Code below line will not execute.
 106 
 107 # This improved version of the Sieve, by Stephane Chazelas,
 108 # executes somewhat faster.
 109 
 110 # Must invoke with command-line argument (limit of primes).
 111 
 112 UPPER_LIMIT=$1                  # From command line.
 113 let SPLIT=UPPER_LIMIT/2         # Halfway to max number.
 114 
 115 Primes=( '' $(seq $UPPER_LIMIT) )
 116 
 117 i=1
 118 until (( ( i += 1 ) > SPLIT ))  # Need check only halfway.
 119 do
 120   if [[ -n $Primes[i] ]]
 121   then
 122     t=$i
 123     until (( ( t += i ) > UPPER_LIMIT ))
 124     do
 125       Primes[t]=
 126     done
 127   fi  
 128 done  
 129 echo ${Primes[*]}
 130 
 131 exit 0

Compare this array-based prime number generator with an alternative that does not use arrays, Example A-17.

--

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


Example 26-10. 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 local 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 
  91 
  92 # Exercises:
  93 # ---------
  94 
  95 # 1)  Modify the "push()" function to permit pushing
  96 #   + multiple element on the stack with a single function call.
  97 
  98 # 2)  Modify the "pop()" function to permit popping
  99 #   + multiple element from the stack with a single function call.
 100 
 101 # 3)  Using this script as a jumping-off point,
 102 #   + write a stack-based 4-function calculator.
 103 
 104 exit 0

--

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

--

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


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

   1 #!/bin/bash
   2 # Simulating a two-dimensional array.
   3 
   4 # A two-dimensional array stores rows sequentially.
   5 
   6 Rows=5
   7 Columns=5
   8 
   9 declare -a alpha     # char alpha [Rows] [Columns];
  10                      # Unnecessary declaration.
  11 
  12 load_alpha ()
  13 {
  14 local rc=0
  15 local index
  16 
  17 
  18 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
  19 do
  20   local row=`expr $rc / $Columns`
  21   local column=`expr $rc % $Rows`
  22   let "index = $row * $Rows + $column"
  23   alpha[$index]=$i   # alpha[$row][$column]
  24   let "rc += 1"
  25 done  
  26 
  27 # Simpler would be
  28 #   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 )
  29 # but this somehow lacks the "flavor" of a two-dimensional array.
  30 }
  31 
  32 print_alpha ()
  33 {
  34 local row=0
  35 local index
  36 
  37 echo
  38 
  39 while [ "$row" -lt "$Rows" ]   # Print out in "row major" order -
  40 do                             # columns vary
  41                                # while row (outer loop) remains the same.
  42   local column=0
  43   
  44   while [ "$column" -lt "$Columns" ]
  45   do
  46     let "index = $row * $Rows + $column"
  47     echo -n "${alpha[index]} "  # alpha[$row][$column]
  48     let "column += 1"
  49   done
  50 
  51   let "row += 1"
  52   echo
  53 
  54 done  
  55 
  56 # The simpler equivalent is
  57 #   echo ${alpha[*]} | xargs -n $Columns
  58 
  59 echo
  60 }
  61 
  62 filter ()     # Filter out negative array indices.
  63 {
  64 
  65 echo -n "  "  # Provides the tilt.
  66 
  67 if [[ "$1" -ge 0 &&  "$1" -lt "$Rows" && "$2" -ge 0 && "$2" -lt "$Columns" ]]
  68 then
  69     let "index = $1 * $Rows + $2"
  70     # Now, print it rotated.
  71     echo -n " ${alpha[index]}"  # alpha[$row][$column]
  72 fi    
  73 
  74 }
  75   
  76 
  77 
  78 
  79 rotate ()  # Rotate the array 45 degrees
  80 {          # ("balance" it on its lower lefthand corner).
  81 local row
  82 local column
  83 
  84 for (( row = Rows; row > -Rows; row-- ))  # Step through the array backwards.
  85 do
  86 
  87   for (( column = 0; column < Columns; column++ ))
  88   do
  89 
  90     if [ "$row" -ge 0 ]
  91     then
  92       let "t1 = $column - $row"
  93       let "t2 = $column"
  94     else
  95       let "t1 = $column"
  96       let "t2 = $column + $row"
  97     fi  
  98 
  99     filter $t1 $t2   # Filter out negative array indices.
 100   done
 101 
 102   echo; echo
 103 
 104 done 
 105 
 106 # Array rotation inspired by examples (pp. 143-146) in
 107 # "Advanced C Programming on the IBM PC", by Herbert Mayer
 108 # (see bibliography).
 109 
 110 }
 111 
 112 
 113 #-----------------------------------------------------#
 114 load_alpha     # Load the array.
 115 print_alpha    # Print it out.  
 116 rotate         # Rotate it 45 degrees counterclockwise.
 117 #-----------------------------------------------------#
 118 
 119 
 120 # This is a rather contrived, not to mention kludgy simulation.
 121 #
 122 # Exercises:
 123 # ---------
 124 # 1)  Rewrite the array loading and printing functions
 125 #   + in a more intuitive and elegant fashion.
 126 #
 127 # 2)  Figure out how the array rotation functions work.
 128 #     Hint: think about the implications of backwards-indexing an array.
 129 
 130 exit 0

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