+/EE360P
distributed systems
git clone https://git.julia.blue/+/EE360P
73bc9bb
master
1// UT-EID=jkj858 2// UT-EID=jbr2558 3 4import java .util .*; 5import java .util .concurrent .*; 6 7class Slice { 8int []arr ; 9int start ; 10int end ; 11 12public Slice (int []arr ,int start ,int end ) { 13this .arr =arr ; 14this .start =start ; 15this .end =end ; 16 } 17 18@ Override 19public String toString () { 20return Arrays .toString (Arrays .copyOfRange (arr ,start ,end )); 21 } 22} 23 24public class PMerge extends RecursiveTask <int []> { 25Slice a ; 26Slice b ; 27 28public PMerge (Slice a ,Slice b ) { 29this .a =a ; 30this .b =b ; 31 } 32 33public static void parallelMerge (int []A ,int []B ,int []C , 34int numThreads ) { 35ForkJoinPool pool =new ForkJoinPool (numThreads ); 36Slice a =new Slice (A ,0 ,A .length ); 37Slice b =new Slice (B ,0 ,B .length ); 38 39PMerge p =new PMerge (a ,b ); 40int []sorted =pool .invoke (p ); 41 42for (int i =0 ;i <sorted .length ;i ++) { 43C [sorted .length -1 -i ] =sorted [i ]; 44 } 45 } 46 47@ Override 48protected int []compute () { 49int aLength =a .end -a .start ; 50int bLength =b .end -b .start ; 51//System.out.println(aLength + " " + bLength); 52 53// Base case: if one of the arrays are empty or both arrays are of length 1 swap accordingly 54if (aLength ==0 ) { 55return Arrays .copyOfRange (b .arr ,b .start ,b .end ); 56 }else if (bLength ==0 ) { 57return Arrays .copyOfRange (a .arr ,a .start ,a .end ); 58 }else if (aLength ==1 &&bLength ==1 ) { 59int []c =new int [2 ]; 60if (a .arr [a .start ] <b .arr [b .start ]) { 61c [0 ] =a .arr [a .start ]; 62c [1 ] =b .arr [b .start ]; 63 }else { 64c [0 ] =b .arr [b .start ]; 65c [1 ] =a .arr [a .start ]; 66 } 67 68return c ; 69 } 70 71// Always have larger array as a 72if (bLength >aLength ) { 73Slice temp =a ; 74a =b ; 75b =temp ; 76 } 77 78int midIndex =a .start +aLength /2 ; 79 80// Find index for value of middle element in array b 81int bIndex =Arrays .binarySearch (b .arr ,b .start ,b .end ,a .arr [midIndex ]); 82if (bIndex <0 )bIndex = (bIndex * -1 ) -1 ; 83 84// Slice arrays into new segments and call next level 85Slice a1 =new Slice (a .arr ,a .start ,midIndex ); 86Slice a2 =new Slice (a .arr ,midIndex ,a .end ); 87 88Slice b1 =new Slice (b .arr ,b .start ,bIndex ); 89Slice b2 =new Slice (b .arr ,bIndex ,b .end ); 90 91PMerge p1 =new PMerge (a1 ,b1 ); 92p1 .fork (); 93PMerge p2 =new PMerge (a2 ,b2 ); 94 95int []newB =p2 .compute (); 96int []newA =p1 .join (); 97 98//System.out.println("A: " + Arrays.toString(newA)); 99//System.out.println("B: " + Arrays.toString(newB)); 100 101// Merge two sorted arrays 102int []c =Arrays .copyOf (newA ,newA .length +newB .length ); 103for (int i =0 ;i <newB .length ;i ++) { 104c [i +newA .length ] =newB [i ]; 105 } 106 107return c ; 108 } 109}