37 |
37 |
38 /** |
38 /** |
39 * A recursive resultless {@link ForkJoinTask}. This class |
39 * A recursive resultless {@link ForkJoinTask}. This class |
40 * establishes conventions to parameterize resultless actions as |
40 * establishes conventions to parameterize resultless actions as |
41 * {@code Void} {@code ForkJoinTask}s. Because {@code null} is the |
41 * {@code Void} {@code ForkJoinTask}s. Because {@code null} is the |
42 * only valid value of type {@code Void}, methods such as join always |
42 * only valid value of type {@code Void}, methods such as {@code join} |
43 * return {@code null} upon completion. |
43 * always return {@code null} upon completion. |
44 * |
44 * |
45 * <p><b>Sample Usages.</b> Here is a sketch of a ForkJoin sort that |
45 * <p><b>Sample Usages.</b> Here is a simple but complete ForkJoin |
46 * sorts a given {@code long[]} array: |
46 * sort that sorts a given {@code long[]} array: |
47 * |
47 * |
48 * <pre> {@code |
48 * <pre> {@code |
49 * class SortTask extends RecursiveAction { |
49 * static class SortTask extends RecursiveAction { |
50 * final long[] array; final int lo; final int hi; |
50 * final long[] array; final int lo, hi; |
51 * SortTask(long[] array, int lo, int hi) { |
51 * SortTask(long[] array, int lo, int hi) { |
52 * this.array = array; this.lo = lo; this.hi = hi; |
52 * this.array = array; this.lo = lo; this.hi = hi; |
53 * } |
53 * } |
|
54 * SortTask(long[] array) { this(array, 0, array.length); } |
54 * protected void compute() { |
55 * protected void compute() { |
55 * if (hi - lo < THRESHOLD) |
56 * if (hi - lo < THRESHOLD) |
56 * sequentiallySort(array, lo, hi); |
57 * sortSequentially(lo, hi); |
57 * else { |
58 * else { |
58 * int mid = (lo + hi) >>> 1; |
59 * int mid = (lo + hi) >>> 1; |
59 * invokeAll(new SortTask(array, lo, mid), |
60 * invokeAll(new SortTask(array, lo, mid), |
60 * new SortTask(array, mid, hi)); |
61 * new SortTask(array, mid, hi)); |
61 * merge(array, lo, hi); |
62 * merge(lo, mid, hi); |
62 * } |
63 * } |
|
64 * } |
|
65 * // implementation details follow: |
|
66 * final static int THRESHOLD = 1000; |
|
67 * void sortSequentially(int lo, int hi) { |
|
68 * Arrays.sort(array, lo, hi); |
|
69 * } |
|
70 * void merge(int lo, int mid, int hi) { |
|
71 * long[] buf = Arrays.copyOfRange(array, lo, mid); |
|
72 * for (int i = 0, j = lo, k = mid; i < buf.length; j++) |
|
73 * array[j] = (k == hi || buf[i] < array[k]) ? |
|
74 * buf[i++] : array[k++]; |
63 * } |
75 * } |
64 * }}</pre> |
76 * }}</pre> |
65 * |
77 * |
66 * You could then sort {@code anArray} by creating {@code new |
78 * You could then sort {@code anArray} by creating {@code new |
67 * SortTask(anArray, 0, anArray.length-1) } and invoking it in a |
79 * SortTask(anArray)} and invoking it in a ForkJoinPool. As a more |
68 * ForkJoinPool. As a more concrete simple example, the following |
80 * concrete simple example, the following task increments each element |
69 * task increments each element of an array: |
81 * of an array: |
70 * <pre> {@code |
82 * <pre> {@code |
71 * class IncrementTask extends RecursiveAction { |
83 * class IncrementTask extends RecursiveAction { |
72 * final long[] array; final int lo; final int hi; |
84 * final long[] array; final int lo, hi; |
73 * IncrementTask(long[] array, int lo, int hi) { |
85 * IncrementTask(long[] array, int lo, int hi) { |
74 * this.array = array; this.lo = lo; this.hi = hi; |
86 * this.array = array; this.lo = lo; this.hi = hi; |
75 * } |
87 * } |
76 * protected void compute() { |
88 * protected void compute() { |
77 * if (hi - lo < THRESHOLD) { |
89 * if (hi - lo < THRESHOLD) { |