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;
     }

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[ ].

The following shows how the cross-out procedure proceeds:

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 T_i,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 X_i 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[ ].

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.