Re: Bug on array manipulation?

[Aharon Robbins]

Greetings. Apologies for the delay in replying, but I have not had
much time lately for gawk.  I took a look at the program you sent.
There is no gawk bug. There is a logic bug.

> Date: Wed, 20 Dec 2006 09:27:21 -0200
> From: Joao Batista Souza de Oliveira <address@hidden>
> Subject: Bug on array manipulation?
> To: address@hidden
>
> Hi,
>
> I have found a rather strange behavior in gawk. It might be a bug, it
> might as well be arcane behavior due to access to arrays, but I do not
> have the expertise to judge. So I decided to report it.
>
> The code example attached shows the problem.
>
> First we make N = ARGV[1] to get an integer number.
>
> A vector Cl with N elements is initialized with elements from 1 to N.
> Thus, in the beginning all elements in Cl are different.
>
> The unify() function does the following:
>
>   - it chooses two values mi and mj from the vector Cl, assuring that
>     they are different.
>
>   - Next, it examines all elements in Cl and changes occurrences of mj
>     to mi. By doing so we are creating repeated values in Cl, and as
>     this goes on Cl should end up containing a unique value in all
>     indices.
>
>   - unify() returns 0 or 1 to inform if there are still several
>     different values in Cl or if we have a single value in all
>     positions, and we stop in this case.
>
> I inserted debug information in the code, to be read like the example
> below. This is one step of the output, it was run with ARGV[1] = 12
> and shows the problem.
>
> ################################
> Change all 7 to 9                                           <- The elements 
> in Cl to be changed
>    1    2    3    4    5    6    7    8    9   10   11   12 <- Indexes i of Cl
>    1    9    9    1    9  [ 7] [ 7] [ 7] [ 7]   9    9    9 <- Value of Cl[i],
>                                                                elements to be 
> changed are marked
>    1    9    9    1    9    9    9    7    7    9    9    9 <- Value after 
> changing all 7 to 9
>
> This is real output, and you see that not all 7 are changed to 9. I
> cannot explain the reasons for that, but in many cases only a few
> elements are changed.
>
> BTW, I solved the problem by copying the array Cl to another array
> Aux, using Aux to replace elements and copying it back to Cl, but this
> is not the best solution...
>
> thanks for any hint,
>
> joao batista
>
>
>
> #####################################################################################
> This Mail Was Scanned by 012.net AntiVirus Service4- Powered by TrendMicro 
> Interscan
> --XsQoSWH+UP9D9v3l
> Content-Type: text/plain; charset=iso-8859-1
> Content-Disposition: attachment; filename="xx.awk"
>
> #!/usr/bin/awk -f
>
> function unify( i, j, mi, mj ) {
>   mi = 1 + int( N * rand( ) );
>
> # Assure that two different elements are chosen
>   while ( 1 ) {
>     mj = 1 + int( N * rand( ) );
>     if ( Cl[ mj ] != Cl[ mi ] ) break;
>   }
>
>   print "################################";
>
> # Message
>   print "Change all " Cl[ mj ] " to " Cl[ mi ];
>
> # Print array indices and array elements
>   for ( j = 1; j <= N; j++ ) printf "%4d ", j;
>   print;
>
> # Print array elements
> # Highlight the ones to be changed
>   for ( j = 1; j <= N; j++ )
>     if ( Cl[ j ] == Cl[ mj ] )
>       printf " [%2d]", Cl[ j ];
>     else
>       printf "%4d ", Cl[ j ];
>   print;
>

The bug is here:

> # Change elements
>   for ( j = 1; j <= N; j++ )
>     if ( Cl[ j ] == Cl[ mj ] ) Cl[ j ] = Cl[ mi ];

It should be:

# Change elements
  for ( j = 1; j <= N; j++ )
    if ( j != mj && Cl[ j ] == Cl[ mj ] ) Cl[ j ] = Cl[ mi ];
  Cl[ j ] = Cl[ mi ];

You need to leave Cl[mj] untouched until you have completed the loop.

> # Print result after changing
>   for ( j = 1; j <= N; j++ ) printf "%4d ", Cl[ j ];
>   print;
>
> # Return value: 1 if there are at least two different values in Cl
> #               0 otherwise
>   for ( j = 1; j < N; j++ ) if ( Cl[j] != Cl[j+1] ) return 1;
>   return 0;
> }
>
> BEGIN {
>   srand();
>   N = ARGV[ 1 ];
>   for ( i = 1; i <= N; i++ ) Cl[ i ] = i;
>   while (unify());
>   }

Hope this helps,

Arnold