Differences between revisions 2 and 3
Revision 2 as of 2018-04-07 22:30:02
Size: 1978
Editor: c-68-54-93-130
Comment: Mentioned BASH_ARGV. https://dylanaraps.com/2018/02/05/bash-tricks/
Revision 3 as of 2019-04-17 19:00:47
Size: 4448
Editor: GreyCat
Comment: reversing an array without printing, and some clean up
Deletions are marked like this. Additions are marked like this.
Line 2: Line 2:
== How do I print an array in reverse order? ==
First note that the concept of ''order'' applies only to [[BashFAQ/005|indexed arrays]], not associative arrays. The answer would be very simple if there were no sparse arrays, but bash's arrays ''can'' be sparse (non-sequential indices). So we have to introduce an extra step.
== How do I print the contents of an array in reverse order, or reverse an array? ==
First note that the concept of ''order'' applies only to [[BashFAQ/005|indexed arrays]], not associative arrays. The answers would be simpler if there were no sparse arrays, but bash's arrays ''can'' be sparse (non-sequential indices). So we have to introduce an extra step.

=== Printing ===
Line 20: Line 22:
In the ''degenerate case'' where we know the array isn't sparse, we could simply iterate over the original array backwards, starting at index ''length - 1'' and simply assuming that this is the last index. In the ''degenerate case'' where we know the array isn't sparse, we could simply iterate over the original array backwards, starting at index ''length - 1'' and ending at index 0. The next example will show this, so we won't duplicate it here.
Line 52: Line 54:

=== Reversing a list ===

If we think of an array as a ''list'' (ignoring the indices), then we may wish to create a new list which has the same elements, but in the reverse order. In this case, we are ''not'' going to try to preserve the original, possibly sparse, indices. The new list will simply be indexed sequentially from 0.

As above, we want to iterate over the elements of the original list in reverse order. This means we first need a list of the original ''indices''. We can iterate over those in reverse, and therefore retrieve the elements in reverse, and append them into our new list (array).

{{{
# bash 3.0
# Reverse the elements of array a into new array b.
idx=("${!a[@]}")
b=()
for (( i=${#idx[@]} - 1; i >= 0; i-- )); do
  j=${idx[i]}
  b+=("${a[j]}")
done
}}}

In practice, the input array is often going to be the positional parameters (`"$@"`) rather than a named array. Fortunately, bash has an [[BashFAQ/006|indirect indexing]] syntax that lets us retrieve positional parameters by number-stored-in-a-variable. We also know that the positional parameters are never going to be sparse, so we can skip the array-of-indices step.

{{{
# bash
# Reverse the positional parameters into new array rev.
rev=()
for (( i=$#; i >= 1; i-- )); do
  rev+=("${!i}")
done

# We can now use "${rev[@]}" to pass the reversed arguments on.
}}}

=== Reversing an array in place ===

In this section, we'll explore the idea of swapping the elements of a (possibly sparse) array with each other, rather than creating a new sequentially-indexed array. It's not clear how useful this actually is with a sparse array, since the ''meaning'' of the indices will be obliterated. With a non-sparse array, this makes much more sense. But either way, here we go.

The basic algorithm is that we keep two index-pointers, which begin at the start and end of the array respectively, and move them toward each other. Since the array is potentially sparse, we use the array-of-indices step as described above.

{{{
# bash 3.0
# Reverse array a in place.
idx=("${!a[@]}")
((i=0, j=${#idx[@]}-1))
while ((i < j)); do
  # Map from pointers in idx to indices in a.
  ii=${idx[i]}
  jj=${idx[j]}

  # Swap elements of a.
  t=${a[ii]}
  a[ii]=${a[jj]}
  a[jj]=$t

  # Move pointers toward each other.
  ((i++, j--))
done
}}}

How do I print the contents of an array in reverse order, or reverse an array?

First note that the concept of order applies only to indexed arrays, not associative arrays. The answers would be simpler if there were no sparse arrays, but bash's arrays can be sparse (non-sequential indices). So we have to introduce an extra step.

Printing

The first thing we need to do is obtain the indices of the array. We can do this with the ${!array[@]} syntax, introduced in bash 3.0. (Prior to bash 3.0, we would have to make a new copy of the entire array; see below.)

Once we have the list of indices, we can iterate over that list in reverse order. Then use the resulting indices, one by one, to reference the original array. Thus:

# bash 3.0 or higher
array=(world [13]=hello)
idx=("${!array[@]}")     # copy of INDICES
for (( i = ${#idx[@]} - 1; i >= 0; i-- )); do
  j=${idx[i]}
  printf "%s " "${array[j]}"
done
echo

In the degenerate case where we know the array isn't sparse, we could simply iterate over the original array backwards, starting at index length - 1 and ending at index 0. The next example will show this, so we won't duplicate it here.

If we need to print a (sparse) array in reverse in bash older than 3.0, then we can copy the entire array in order to remove the sparseness, and then iterate over the copy:

# bash 2.0 or higher; less efficient
array=(world [13]=hello)
tmp=("${array[@]}")      # copy of CONTENTS
i=$(( ${#tmp[@]} - 1 ))
while ((i >= 0)); do
  printf "%s " "${tmp[i]}"
  ((i--))
done
echo

When the array is to be passed to a function or when extdebug is already set, BASH_ARGV can be used to operate on array items in reverse order. (For most other cases, BASH_ARGV may not be as efficient as the examples above.)

reverse_array()
{
  shopt -s extdebug
  f()
  {
    printf "%s " "${BASH_ARGV[@]}";
  }
  f "$@"
  shopt -u extdebug
}
a=(1 2 3 4)
reverse_array "${a[@]}"

Reversing a list

If we think of an array as a list (ignoring the indices), then we may wish to create a new list which has the same elements, but in the reverse order. In this case, we are not going to try to preserve the original, possibly sparse, indices. The new list will simply be indexed sequentially from 0.

As above, we want to iterate over the elements of the original list in reverse order. This means we first need a list of the original indices. We can iterate over those in reverse, and therefore retrieve the elements in reverse, and append them into our new list (array).

# bash 3.0
# Reverse the elements of array a into new array b.
idx=("${!a[@]}")
b=()
for (( i=${#idx[@]} - 1; i >= 0; i-- )); do
  j=${idx[i]}
  b+=("${a[j]}")
done

In practice, the input array is often going to be the positional parameters ("$@") rather than a named array. Fortunately, bash has an indirect indexing syntax that lets us retrieve positional parameters by number-stored-in-a-variable. We also know that the positional parameters are never going to be sparse, so we can skip the array-of-indices step.

# bash
# Reverse the positional parameters into new array rev.
rev=()
for (( i=$#; i >= 1; i-- )); do
  rev+=("${!i}")
done

# We can now use "${rev[@]}" to pass the reversed arguments on.

Reversing an array in place

In this section, we'll explore the idea of swapping the elements of a (possibly sparse) array with each other, rather than creating a new sequentially-indexed array. It's not clear how useful this actually is with a sparse array, since the meaning of the indices will be obliterated. With a non-sparse array, this makes much more sense. But either way, here we go.

The basic algorithm is that we keep two index-pointers, which begin at the start and end of the array respectively, and move them toward each other. Since the array is potentially sparse, we use the array-of-indices step as described above.

# bash 3.0
# Reverse array a in place.
idx=("${!a[@]}")
((i=0, j=${#idx[@]}-1))
while ((i < j)); do
  # Map from pointers in idx to indices in a.
  ii=${idx[i]}
  jj=${idx[j]}

  # Swap elements of a.
  t=${a[ii]}
  a[ii]=${a[jj]}
  a[jj]=$t

  # Move pointers toward each other.
  ((i++, j--))
done

BashFAQ/118 (last edited 2019-04-17 19:00:47 by GreyCat)