1
2
3
4
5
6
7
8
9
10
11
12
13
14 package eu.fbk.rdfpro.util;
15
16 import java.util.Arrays;
17 import java.util.concurrent.ForkJoinPool;
18 import java.util.concurrent.RecursiveAction;
19
20 final class Sorting {
21
22 private Sorting() {
23 }
24
25 public static <T> void sort(final ArrayComparator<T> comparator, final T[] array) {
26 sort(comparator, array, 0, array.length);
27 }
28
29 public static <T> void sort(final ArrayComparator<T> comparator, final T[] array,
30 final int lo, final int hi) {
31 ForkJoinPool.commonPool().invoke(new SortTask<T>(comparator, array, lo, hi));
32 }
33
34 public interface ArrayComparator<T> {
35
36 int size();
37
38 int compare(T[] leftArray, int leftIndex, T[] rightArray, int rightIndex);
39
40 }
41
42 private static class SortTask<T> extends RecursiveAction {
43
44 private static final long serialVersionUID = 1;
45
46 private static final int PARALELLSORT_THRESHOLD = 1000;
47
48 private static final int INSERTIONSORT_THRESHOLD = 7;
49
50 private final ArrayComparator<T> comparator;
51
52 private final T[] data;
53
54 private final int lo;
55
56 private final int hi;
57
58 SortTask(final ArrayComparator<T> comparator, final T[] data, final int lo, final int hi) {
59 this.comparator = comparator;
60 this.data = data;
61 this.lo = lo;
62 this.hi = hi;
63 }
64
65 @Override
66 protected void compute() {
67 final int size = this.comparator.size();
68 if (this.hi - this.lo < PARALELLSORT_THRESHOLD * size) {
69 final T[] aux = Arrays.copyOfRange(this.data, this.lo, this.hi);
70 mergeSort(this.comparator, aux, this.data, this.lo, this.hi, -this.lo);
71 } else {
72 final int mid = (this.lo / size + this.hi / size >>> 1) * size;
73 invokeAll(new SortTask<T>(this.comparator, this.data, this.lo, mid),
74 new SortTask<T>(this.comparator, this.data, mid, this.hi));
75 final T[] buffer = Arrays.copyOfRange(this.data, this.lo, mid);
76 int leftIndex = 0;
77 int rightIndex = mid;
78 int outIndex = this.lo;
79 while (leftIndex < buffer.length) {
80 if (rightIndex == this.hi
81 || this.comparator.compare(buffer, leftIndex, this.data, rightIndex) < 0) {
82 System.arraycopy(buffer, leftIndex, this.data, outIndex, size);
83 leftIndex += size;
84 } else {
85 System.arraycopy(this.data, rightIndex, this.data, outIndex, size);
86 rightIndex += size;
87 }
88 outIndex += size;
89 }
90 }
91 }
92
93 private static <T> void mergeSort(final ArrayComparator<T> comparator, final T[] src,
94 final T[] dest, final int destLo, final int destHi, final int off) {
95
96 final int size = comparator.size();
97
98 if (destHi - destLo < INSERTIONSORT_THRESHOLD) {
99 for (int i = destLo; i < destHi; i += size) {
100 for (int j = i; j > destLo && comparator.compare(dest, j - size, dest, j) > 0; j -= size) {
101 for (int k = 0; k < size; ++k) {
102 final T temp = dest[j + k];
103 dest[j + k] = dest[j + k - size];
104 dest[j + k - size] = temp;
105 }
106 }
107 }
108 return;
109 }
110
111 final int srcLo = destLo + off;
112 final int srcHi = destHi + off;
113 final int srcMid = (srcLo >>> 2) + (srcHi >>> 2) >>> 1 << 2;
114 mergeSort(comparator, dest, src, srcLo, srcMid, -off);
115 mergeSort(comparator, dest, src, srcMid, srcHi, -off);
116
117 int destIndex = destLo;
118 int srcLeftIndex = srcLo;
119 int srcRightIndex = srcMid;
120
121 while (destIndex < destHi) {
122 if (srcRightIndex >= srcHi || srcLeftIndex < srcMid
123 && comparator.compare(src, srcLeftIndex, src, srcRightIndex) <= 0) {
124 System.arraycopy(src, srcLeftIndex, dest, destIndex, 4);
125 srcLeftIndex += 4;
126 } else {
127 System.arraycopy(src, srcRightIndex, dest, destIndex, 4);
128 srcRightIndex += 4;
129 }
130 destIndex += 4;
131 }
132 }
133
134 }
135
136 }