Package extra166y

Class ParallelLongArray


  • public class ParallelLongArray
    extends ParallelLongArrayWithBounds
    An array of longs supporting parallel operations. This class provides methods supporting the same operations as ParallelArray, but specialized for scalar longs. It additionally provides a few methods specific to numerical values.

    Sample usages. Here is a complete (although naive) prime filter program:

     import java.math.BigInteger;
     import jsr166y.*;
     import static extra166y.Ops.*;
     import static extra166y.ParallelLongArray.*;
    
     public class Sieve {
       public static void main(String[] args) {
         int n = Integer.parseInt(args[0]);
         // create array of divisors
         ParallelLongArray a = create(n-1, defaultExecutor());
         a.replaceWithMappedIndex(add2);
         int i = 0;
         long p = 2;
         while (p * p < n) { // repeatedly filter
             a = a.withFilter(notDivisibleBy(p)).all();
             p = a.get(++i);
         }
         System.out.printf("sieve(%d) = %s%n", n, a);
         // check result
         if (!a.withFilter(notProbablePrime).isEmpty())
             throw new Error();
       }
       static IntToLong add2 = new IntToLong() {
         public long op(int i) { return i + 2; } };
       static LongPredicate notDivisibleBy(final long p) {
         return new LongPredicate() {
            public boolean op(long n) { return n <= p || (n % p) != 0; }
         }; }
       static LongPredicate notProbablePrime = new LongPredicate() {
         private static final int CERTAINTY = 8;
         public boolean op(long n) {
           return !BigInteger.valueOf(n).isProbablePrime(CERTAINTY);
         }
       };
     }
     
    • Method Detail

      • defaultExecutor

        public static jsr166y.ForkJoinPool defaultExecutor()
        Returns a common default executor for use in ParallelArrays. This executor arranges enough parallelism to use most, but not necessarily all, of the available processors on this system.
        Returns:
        the executor
      • create

        public static ParallelLongArray create​(int size,
                                               jsr166y.ForkJoinPool executor)
        Creates a new ParallelLongArray using the given executor and an array of the given size
        Parameters:
        size - the array size
        executor - the executor
      • createUsingHandoff

        public static ParallelLongArray createUsingHandoff​(long[] handoff,
                                                           jsr166y.ForkJoinPool executor)
        Creates a new ParallelLongArray initially using the given array and executor. In general, the handed off array should not be used for other purposes once constructing this ParallelLongArray. The given array may be internally replaced by another array in the course of methods that add or remove elements.
        Parameters:
        handoff - the array
        executor - the executor
      • createFromCopy

        public static ParallelLongArray createFromCopy​(long[] source,
                                                       jsr166y.ForkJoinPool executor)
        Creates a new ParallelLongArray using the given executor and initially holding copies of the given source elements.
        Parameters:
        source - the source of initial elements
        executor - the executor
      • createFromCopy

        public static ParallelLongArray createFromCopy​(int size,
                                                       long[] source,
                                                       jsr166y.ForkJoinPool executor)
        Creates a new ParallelLongArray using an array of the given size, initially holding copies of the given source truncated or padded with zeros to obtain the specified length.
        Parameters:
        source - the source of initial elements
        size - the array size
        executor - the executor
      • createEmpty

        public static ParallelLongArray createEmpty​(int size,
                                                    jsr166y.ForkJoinPool executor)
        Creates a new ParallelLongArray using the given executor and an array of the given size, but with an initial effective size of zero, enabling incremental insertion via asList() operations.
        Parameters:
        size - the array size
        executor - the executor
      • getExecutor

        public jsr166y.ForkJoinPool getExecutor()
        Returns the executor used for computations
        Returns:
        the executor
      • replaceWithGeneratedValue

        public ParallelLongArray replaceWithGeneratedValue​(Ops.LongGenerator generator)
        Replaces elements with the results of applying the given generator. For example, to fill the array with uniform random values, use replaceWithGeneratedValue(Ops.longRandom())
        Overrides:
        replaceWithGeneratedValue in class ParallelLongArrayWithFilter
        Parameters:
        generator - the generator
        Returns:
        this (to simplify use in expressions)
      • replaceWithMapping

        public ParallelLongArray replaceWithMapping​(Ops.BinaryLongOp combiner,
                                                    long[] other)
        Replaces elements with results of applying op(thisElement, otherElement)
        Overrides:
        replaceWithMapping in class ParallelLongArrayWithFilter
        Parameters:
        other - the other array
        combiner - the combiner
        Returns:
        this (to simplify use in expressions)
        Throws:
        java.lang.ArrayIndexOutOfBoundsException - if other array has fewer elements than this array.
      • indexOf

        public int indexOf​(long target)
        Returns the index of some element equal to given target, or -1 if not present
        Parameters:
        target - the element to search for
        Returns:
        the index or -1 if not present
      • binarySearch

        public int binarySearch​(long target)
        Assuming this array is sorted, returns the index of an element equal to given target, or -1 if not present. If the array is not sorted, the results are undefined.
        Parameters:
        target - the element to search for
        Returns:
        the index or -1 if not present
      • binarySearch

        public int binarySearch​(long target,
                                Ops.LongComparator comparator)
        Assuming this array is sorted with respect to the given comparator, returns the index of an element equal to given target, or -1 if not present. If the array is not sorted, the results are undefined.
        Parameters:
        target - the element to search for
        comparator - the comparator
        Returns:
        the index or -1 if not present
      • min

        public long min​(Ops.LongComparator comparator)
        Returns the minimum element, or Long.MAX_VALUE if empty
        Overrides:
        min in class ParallelLongArrayWithLongMapping
        Parameters:
        comparator - the comparator
        Returns:
        minimum element, or Long.MAX_VALUE if empty
      • min

        public long min()
        Returns the minimum element, or Long.MAX_VALUE if empty,
        Overrides:
        min in class ParallelLongArrayWithLongMapping
        Returns:
        minimum element, or Long.MAX_VALUE if empty
      • max

        public long max​(Ops.LongComparator comparator)
        Returns the maximum element, or Long.MIN_VALUE if empty
        Overrides:
        max in class ParallelLongArrayWithLongMapping
        Parameters:
        comparator - the comparator
        Returns:
        maximum element, or Long.MIN_VALUE if empty
      • max

        public long max()
        Returns the maximum element, or Long.MIN_VALUE if empty
        Overrides:
        max in class ParallelLongArrayWithLongMapping
        Returns:
        maximum element, or Long.MIN_VALUE if empty
      • cumulate

        public ParallelLongArray cumulate​(Ops.LongReducer reducer,
                                          long base)
        Replaces each element with the running cumulation of applying the given reducer. For example, if the contents are the numbers 1, 2, 3, and the reducer operation adds numbers, then after invocation of this method, the contents would be 1, 3, 6 (that is, 1, 1+2, 1+2+3);
        Parameters:
        reducer - the reducer
        base - the result for an empty array
        Returns:
        this (to simplify use in expressions)
      • precumulate

        public long precumulate​(Ops.LongReducer reducer,
                                long base)
        Replaces each element with the cumulation of applying the given reducer to all previous values, and returns the total reduction. For example, if the contents are the numbers 1, 2, 3, and the reducer operation adds numbers, then after invocation of this method, the contents would be 0, 1, 3 (that is, 0, 0+1, 0+1+2, and the return value would be 6 (that is, 1+2+3);
        Parameters:
        reducer - the reducer
        base - the result for an empty array
        Returns:
        the total reduction
      • sort

        public ParallelLongArray sort​(Ops.LongComparator comparator)
        Sorts the array. Unlike Arrays.sort, this sort does not guarantee that elements with equal keys maintain their relative position in the array.
        Parameters:
        comparator - the comparator to use
        Returns:
        this (to simplify use in expressions)
      • sort

        public ParallelLongArray sort()
        Sorts the array, assuming all elements are Comparable. Unlike Arrays.sort, this sort does not guarantee that elements with equal keys maintain their relative position in the array.
        Returns:
        this (to simplify use in expressions)
        Throws:
        java.lang.ClassCastException - if any element is not Comparable.
      • removeConsecutiveDuplicates

        public ParallelLongArray removeConsecutiveDuplicates()
        Removes consecutive elements that are equal, shifting others leftward, and possibly decreasing size. This method may be used after sorting to ensure that this ParallelLongArray contains a set of unique elements.
        Returns:
        this (to simplify use in expressions)
      • addAll

        public ParallelLongArray addAll​(long[] other)
        Equivalent to asList().addAll but specialized for array arguments and likely to be more efficient.
        Parameters:
        other - the elements to add
        Returns:
        this (to simplify use in expressions)
      • addAll

        public ParallelLongArray addAll​(ParallelLongArrayWithLongMapping other)
        Appends all (possibly bounded, filtered, or mapped) elements of the given ParallelDoubleArray, resizing and/or reallocating this array if necessary.
        Parameters:
        other - the elements to add
        Returns:
        this (to simplify use in expressions)
      • removeAll

        public ParallelLongArray removeAll​(Ops.LongPredicate selector)
        Removes from the array all elements for which the given selector holds.
        Parameters:
        selector - the selector
        Returns:
        this (to simplify use in expressions)
      • cumulateSum

        public ParallelLongArray cumulateSum()
        Replaces each element with the running sum
        Returns:
        this (to simplify use in expressions)
      • precumulateSum

        public long precumulateSum()
        Replaces each element with its prefix sum
        Returns:
        the total sum
      • withBounds

        public ParallelLongArrayWithBounds withBounds​(int firstIndex,
                                                      int upperBound)
        Returns an operation prefix that causes a method to operate only on the elements of the array between firstIndex (inclusive) and upperBound (exclusive).
        Parameters:
        firstIndex - the lower bound (inclusive)
        upperBound - the upper bound (exclusive)
        Returns:
        operation prefix
      • withFilter

        public ParallelLongArrayWithFilter withFilter​(Ops.LongPredicate selector)
        Returns an operation prefix that causes a method to operate only on the elements of the array for which the given selector returns true
        Parameters:
        selector - the selector
        Returns:
        operation prefix
      • withIndexedFilter

        public ParallelLongArrayWithFilter withIndexedFilter​(Ops.IntAndLongPredicate selector)
        Returns an operation prefix that causes a method to operate only on elements for which the given indexed selector returns true
        Parameters:
        selector - the selector
        Returns:
        operation prefix
      • withMapping

        public <U> ParallelLongArrayWithMapping<U> withMapping​(Ops.LongToObject<? extends U> op)
        Returns an operation prefix that causes a method to operate on mapped elements of the array using the given op.
        Parameters:
        op - the op
        Returns:
        operation prefix
      • withMapping

        public ParallelLongArrayWithLongMapping withMapping​(Ops.LongOp op)
        Returns an operation prefix that causes a method to operate on mapped elements of the array using the given op.
        Parameters:
        op - the op
        Returns:
        operation prefix
      • withMapping

        public ParallelLongArrayWithDoubleMapping withMapping​(Ops.LongToDouble op)
        Returns an operation prefix that causes a method to operate on mapped elements of the array using the given op.
        Parameters:
        op - the op
        Returns:
        operation prefix
      • withIndexedMapping

        public <U> ParallelLongArrayWithMapping<U> withIndexedMapping​(Ops.IntAndLongToObject<? extends U> mapper)
        Returns an operation prefix that causes a method to operate on mappings of this array using the given mapper that accepts as arguments an element's current index and value, and produces a new value.
        Parameters:
        mapper - the mapper
        Returns:
        operation prefix
      • withIndexedMapping

        public ParallelLongArrayWithDoubleMapping withIndexedMapping​(Ops.IntAndLongToDouble mapper)
        Returns an operation prefix that causes a method to operate on mappings of this array using the given mapper that accepts as arguments an element's current index and value, and produces a new value.
        Parameters:
        mapper - the mapper
        Returns:
        operation prefix
      • withIndexedMapping

        public ParallelLongArrayWithLongMapping withIndexedMapping​(Ops.IntAndLongToLong mapper)
        Returns an operation prefix that causes a method to operate on mappings of this array using the given mapper that accepts as arguments an element's current index and value, and produces a new value.
        Parameters:
        mapper - the mapper
        Returns:
        operation prefix
      • iterator

        public java.util.Iterator<java.lang.Long> iterator()
        Returns an iterator stepping through each element of the array up to the current limit. This iterator does not support the remove operation. However, a full ListIterator supporting add, remove, and set operations is available via asList().
        Returns:
        an iterator stepping through each element.
      • asList

        public java.util.List<java.lang.Long> asList()
        Returns a view of this ParallelLongArray as a List. This List has the same structural and performance characteristics as ArrayList, and may be used to modify, replace or extend the bounds of the array underlying this ParallelLongArray. The methods supported by this list view are not in general implemented as parallel operations. This list is also not itself thread-safe. In particular, performing list updates while other parallel operations are in progress has undefined (and surely undesired) effects.
        Returns:
        a list view
      • size

        public int size()
        Returns the effective size of the underlying array. The effective size is the current limit, if used (see setLimit(int)), or the length of the array otherwise.
        Overrides:
        size in class AbstractParallelAnyArray
        Returns:
        the effective size of array
      • getArray

        public long[] getArray()
        Returns the underlying array used for computations
        Returns:
        the array
      • get

        public long get​(int i)
        Returns the element of the array at the given index
        Parameters:
        i - the index
        Returns:
        the element of the array at the given index
      • set

        public void set​(int i,
                        long x)
        Sets the element of the array at the given index to the given value
        Parameters:
        i - the index
        x - the value
      • toString

        public java.lang.String toString()
        Equivalent to asList().toString()
        Overrides:
        toString in class java.lang.Object
        Returns:
        a string representation
      • setLimit

        public final void setLimit​(int newLimit)
        Ensures that the underlying array can be accessed up to the given upper bound, reallocating and copying the underlying array to expand if necessary. Or, if the given limit is less than the length of the underlying array, causes computations to ignore elements past the given limit.
        Parameters:
        newLimit - the new upper bound
        Throws:
        java.lang.IllegalArgumentException - if newLimit less than zero.