Can anyone decypher why this 'find unique values' process doesn't work as intended?

Question

The goal is that for a variable that is an array of:

typedef struct {
 GLuint vertex;
 GLuint normal;
} indice_pairs_t;

, we want to find all the pairs that are unique and put them in an appropriate order of appearance with unique pair indices intact.

For example: if initial pairs are

2 3
6 7
6 7
4 5

(the 2nd and 3rd pairs are same)

then the final order will be

0 1 1 2

('2 3' was 0, first '6 7' was 1 but also the second '6 7'; '4 5' was 2 and so on)

The following code attempts to do that but final order appears to be always '0 1 2 3 4 5' and so on. If 'break;' is removed, it becomes a mess; too many increments.

// First is always unique and first in order:
unique[0] = pairs[0];
order[0] = 0;
num_unique = 1;

// Skip first, we just did it:
for (i = 1; i < num_pairs; i++) {

 // Check if what we have is already the same
 for (y = 0; y < num_unique; y++) {

  if (unique[y].vertex == pairs[i].vertex&&unique[y].normal == pairs[i].normal) {
   /* A new pair was found to be the same; put the old unique index in order;
    keep num of unique items same: */
   order[i] = y;
  } else {
   /* A new pair was unique; copy it in unique pairs and increment number
    of unique items; put in order the new number */
   unique[num_unique] = pairs[i];
   order[i] = num_unique;
   num_unique++; // it follows since it was already incremented to 1.
   break;
  }

 }

}

Answer 1

It's a pretty inefficient algorithm. The complexity is O(n²). You could do better, by using a sorted sequence.

What you have is obviously buggy, but the idea seems clear. For every new value (next i) it is checked, if that value is already among unique values stored so far. That's what the inner loop is for. If the match is found, order[i] = y and the next i should be checked, so you can break. If the match is not found for current y however, you need to check next y. Only after all y were checked, you know the value is unique, so the part in the else clause should be moved outside the inner loop. I think the fixed version should look like this:

unique[0] = pairs[0];
order[0] = 0;
num_unique = 1;

// Skip first, we just did it:
for (i = 1; i < num_pairs; i++) {

    // Check if what we have is already the same
    for (y = 0; y < num_unique; y++) {

        if (unique[y].vertex == pairs[i].vertex && unique[y].normal == pairs[i].normal) {
            /*  A new pair was found to be the same; put the old unique index in order;
                keep num of unique items same: */
            order[i] = y;
            break;
        }
    }
    if(y == num_unique){
    /* No match was found in the inner loop,
       so y reached num_unique. You could use a flag
       to indicate this, which might be more readable*/

        /*  A new pair was unique; copy it in unique pairs and increment number
            of unique items; put in order the new number */
        unique[num_unique] = pairs[i];
        order[i] = num_unique;
        num_unique++; // it follows since it was already incremented to 1 in the beginning.
    }
}