cumulate

[Doug Lea]

On 12/21/12 16:31, Brian Goetz wrote:
> It's gone.  (Well, not gone.  Mercurial history is still there.)
>
> I propose this as the replacement:
>
> In Arrays:
>    void parallelPrefix(T[], int offset, int length, BinaryOperator<T>);
>    void parallelPrefix(int[], int offset, int length, IntBinaryOperator);
>    void parallelPrefix(long[], int offset, int length, LongBinaryOperator);
>    void parallelPrefix(double[], int offset, int length, DoubleBinaryOperator);
>

Actually, to be consistent with Arrays.sort (and other in-place methods
in Arrays), it should use fromIndex, toIndex. The "T" and long versions
pasted below. After Brian grabs and commits some stuff, it should all be in
place....

-Doug



     /**
      * Cumulates in parallel each element of the given array in place,
      * using the supplied function. For example if the array initially
      * holds {@code [2, 1, 0, 3]} and the operation performs addition,
      * then upon return the array holds {@code [2, 3, 3, 6]}.
      * Parallel prefix computation is usually more efficient than
      * sequential loops for large arrays.
      *
      * @param array the array, which is modified in-place by this method
      * @param op the function to perform cumulations. The function
      * must be amenable to left-to-right application through the
      * elements of the array, as well as possible left-to-right
      * application across segments of the array.
      */
     public static <T> void parallelPrefix(T[] array, BinaryOperator<T> op) {
         if (array.length > 0)
             new ArrayPrefixUtil.CumulateTask<T>
                 (null, op, array, 0, array.length).invoke();
     }

     /**
      * Performs {@link #parallelPrefix(Object[], BinaryOperator)}
      * for the given subrange of the array.
      *
      * @param array the array
      * @param fromIndex the index of the first element, inclusive
      * @param toIndex the index of the last element, exclusive
      * @param op the function to perform cumulations.
      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
      * @throws ArrayIndexOutOfBoundsException
      *     if {@code fromIndex < 0} or {@code toIndex > array.length}
      */
     public static <T> void parallelPrefix(T[] array, int fromIndex,
                                           int toIndex, BinaryOperator<T> op) {
         checkFromToBounds(array.length, fromIndex, toIndex);
         if (fromIndex < toIndex)
             new ArrayPrefixUtil.CumulateTask
                 (null, op, array, fromIndex, toIndex).invoke();
     }


     /**
      * Cumulates in parallel each element of the given array in place,
      * using the supplied function. For example if the array initially
      * holds {@code [2, 1, 0, 3]} and the operation performs addition,
      * then upon return the array holds {@code [2, 3, 3, 6]}.
      * Parallel prefix computation is usually more efficient than
      * sequential loops for large arrays.
      *
      * @param array the array, which is modified in-place by this method
      * @param op the function to perform cumulations. The function
      * must be amenable to left-to-right application through the
      * elements of the array, as well as possible left-to-right
      * application across segments of the array.
      */
     public static void parallelPrefix(long[] array, LongBinaryOperator op) {
         if (array.length > 0)
             new ArrayPrefixUtil.LongCumulateTask
                 (null, op, array, 0, array.length).invoke();
     }

... and others similarly...