Problem: The First Positive Element of an Array

Given an array of integers, find the index of the first positive element in the array. For example, if the array contains the following five elements: -3, -1, 4, -5, 6. The first positive element is 4. Thus, the index is 2. This is a very simple problem and can be solved as follows:

posIndex = -1;
for (i = 0; i < n; i++)
     if (a[i] > 0) {
          posIndex = i;
          break;
     }
At the end, if variable posIndex is negative, all elements in array a[] are negative; otherwise, the value of posIndex is the desired index.

How can we solve this problem using multiple threads? In fact, a possible solution is very similar to the maximum finding problem. For any two different elements of the input array, say a[i] and a[j], where i < j, we have the following four cases to consider:

  1. Both a[i] and a[j] are positive. In this case, we can cross out a[j] because it cannot be the first positive element of array a[ ].
  2. Both a[i] and a[j] are negative. In this case, we can cross out both, because neither of them is a positive element of array a[ ].
  3. a[i] is positive and a[j] is negative. In this case, we can cross out a[j] because it cannot be the first positive element of a[ ].
  4. a[i] is negative and a[j] is positive. In this case, we can cross out a[i] because it cannot be the first positive element of array a[ ].
In this way, the element left will be the first positive element of array a[ ], because it survives all cross-out testings. Here is an example. Suppose the array contains

Index 0 1 2 3 4 5 6 7 8
Value -1 -3 5 -2 6 -7 -8 4 5

The following shows how the cross-out procedure proceeds:

i a[i] j a[j] Case Result
0 -1 1 -3 case (2) cross out both
2 5 case (4) cross out a[0]
3 -2 case (2) cross out both
4 6 case (4) cross out a[0]
5 -7 case (2) cross out both
6 -8 case (2) cross out both
7 4 case (4) cross out a[0]
8 5 case (4) cross out a[0]
1 -3 2 5 case (4) cross out a[1]
3 -2 case (2) cross out both
4 6 case (4) cross out a[1]
5 -7 case (2) cross out both
6 -8 case (2) cross out both
7 4 case (4) cross out a[1]
8 5 case (4) cross out a[1]
2 5 3 -2 case (3) cross out a[3]
4 6 case (1) cross out a[4]
5 -7 case (3) cross out a[5]
6 -8 case (3) cross out a[6]
7 4 case (1) cross out a[7]
8 5 case (1) cross out a[8]
3 -2 4 6 case (4) cross out a[3]
5 -7 case (2) cross out both
6 -8 case (2) cross out both
7 4 case (4) cross out a[3]
8 5 case (4) cross out a[3]
4 6 5 -7 case (3) cross out a[5]
6 -8 case (3) cross out a[6]
7 4 case (1) cross out a[7]
8 5 case (1) cross out a[8]
5 -7 6 -8 case (2) cross out both
7 4 case (4) cross out a[5]
8 5 case (4) cross out a[5]
6 -8 7 4 case (4) cross out a[6]
8 5 case (4) cross out a[6]
7 4 8 5 case (1) cross out a[8]

From the above, we learn that a[2] is never crossed out, and, hence the index is 2! That is, a[2] is the first positive element of array a[ ].

The following summarizes this cross-out algorithm:

  1. Suppose the input array a[ ] has n elements.
  2. Prepare an array w[ ] of n elements.
  3. Create n threads so that thread i writes a 1 into w[i], indicating that a[i] is not crossed-out.
  4. For every pair of i < j, create a thread Ti,j to handle elements a[i] and a[j]. Write 0 into w[i], w[j], or both based on the four cases stated above to indicate the corresponding element is crossed-out. Thus, we need n*(n-1)/2 threads.
  5. Up to this point, array w[ ] has all the information we want. Store -1 into variable p.
  6. For 0 <= i < n, create threads Xi to examine w[i]. If w[i] contains a 0, do nothing; otherwise, write the value of i into variable p.
  7. Thus, if the value of p is not negative, it is the desired index, and a[p] is the first positive element of a[ ]. Otherwise, there is no positive element in a[ ].
Thus, this algorithm takes less than five steps to find the first positive element of an array of n elements using n*(n-1)/2 threads. Each thread uses two comparisons to determine which case is applicable. The sequential version uses maximum n comparisons to compute the result.

Problem

Write a program that reads in an array of some integers and use the above algorithm to find its first positive element. Will you be able to simplify the above cases? Note that you should aim for maximum parallelism. More precisely, all created threads should run concurrently.