package mohibmir.linearsort;

import java.lang.reflect.Array;
import java.util.Vector;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.ForkJoinPool;

public class Main {

	public static void main(String[] args) {
		int[] list = new int[10_000_000];
		for(int i = 0; i < 9_999_999; i++){
			list[i] = ((int) (Math.random()*1_000_000));
		}

		long x = System.currentTimeMillis();
		LinearSearch linearsearch = new LinearSearch(list);
		linearsearch.search(list[34321], 0, 9_999_999);
		linearsearch.search(-5, 0, 9_999_999);
		long timeelapsed = System.currentTimeMillis() - x;

		System.out.println("Normal linear search took: " + timeelapsed + " milliseconds.");

		x = System.currentTimeMillis();
		LinearSearchMultithreaded ls = new LinearSearchMultithreaded(list);
		ls.search(21);
		ls.search(-21);
		timeelapsed = System.currentTimeMillis() - x;
		System.out.println("Multithreaded search took " + timeelapsed + " milliseconds.");

		x = System.currentTimeMillis();
		LinearSearchParallel lsp = new LinearSearchParallel(list);
		ls.search(51);

		timeelapsed = System.currentTimeMillis() - x;
		System.out.println("Multithreaded search took " + timeelapsed + " milliseconds.");

	}
}

class LinearSearch extends Thread{
	int[] list;
	int searchFor;
	boolean found;
	int ind;
	int start;
	int end;

	LinearSearch(int[] list){
		this.list = list;
		start = 0;
		end = list.length-1;
	}

	LinearSearch(int[] list, int searchFor){
		this.list = list;
		this.searchFor = searchFor;
		start = 0;
		end = list.length-1;
	}

	LinearSearch(int[] list, int searchFor, int start, int end){
		this.list = list;
		this.searchFor = searchFor;
		this.start = start;
		this.end = end;
	}


	public void run(){
		search(searchFor, start, end);
	}

	public int search(int x, int start, int end){
		if(list == null){
			return -1;
		}
		for(int i = start; i <= end; i++){
			if(list[i] == x){
				System.out.println(i);
				found = true;
				this.ind = i;
				return i;
			}
		}
		if(start == 0 && end == list.length){
			System.out.println(-1);
		}
		found = false;
		return -1;
	}

}

class LinearSearchMultithreaded{
	int[] list;

	LinearSearchMultithreaded(int[] list){
		this.list = list;
	}

	public void search(int x){
		int start = 0;
		int factor = (int) Math.ceil((double)(list.length/4));
		int end;

		ExecutorService exec = Executors.newFixedThreadPool(4);
		LinearSearch[] th = new LinearSearch[4];

		for(int i = 0; i < 4; i++){
			if(start + factor < list.length){
				end = start + factor;
			}else{
				end = list.length-1;
			}
			LinearSearch proc = new LinearSearch(list, x, start, end);
			th[i] = proc;
			exec.execute(proc);
			start += factor;
		}
		exec.shutdown();

		boolean found = false;

		while(!exec.isTerminated()){}

//		if(exec.isTerminated()){
//			for(int i = 0; i < 4; i++){
//				if(th[i].found){
//					found = true;
//				}
//			}
//
//			if(!found){
//				System.out.println("-1");
//			}
//		}

	}

	/*private int splitSearch(int[] list, int start, int end, int result){
		int[] v = new int[]();
		Runnable search = new Runnable(){

			int index = -1;
			public void run(){
				for(int i = start; i < end; i++){
					if(list.get(i) == result){
						index = i;
						v.add(index);
						break;
					}
				}

			}
		};

		if(v.isEmpty()){
			return -1;
		}else{
			return v.get(0);
		}
	}*/
}

class LinearSearchParallel {
	int[] list;

	LinearSearchParallel(int[] list){
		this.list = list;
	}



	public void search(int x){
		int start = 0;
		int factor = (int) Math.ceil((double)(list.length/4));
		int end;

		ForkJoinPool pool = new ForkJoinPool();
		LinearSearch[] threads = new LinearSearch[4];

		for(int i = 0; i < 4; i++){
			if(start + factor < list.length){
				end = start + factor;
			}else{
				end = list.length-1;
			}
			threads[i] = new LinearSearch(list, x, start, end);
			pool.execute(threads[i]);
			start += factor;
		}
		pool.shutdown();

	}

//	public static long parallelMergeSort(int[] list, int proc) {
//		24 long before = System.currentTimeMillis();
//		25 ForkJoinPool pool = new ForkJoinPool(proc);
//		26 pool.invoke(new SortTask(list));
//		27 pool.shutdown();
//		28 while (!pool.isTerminated()) {
//		29 Thread.yield();
//		30 }
//		31 long after = System.currentTimeMillis();
//		32 long time = after - before;
//		33 return time;
//		34 }
//		• Parallel Computing USC CSCI 201L 14/16
//		35 private static class SortTask extends RecursiveAction {
//		36 public static final long serialVersionUID = 1;
//		37 private int[] list;
//		38 SortTask(int[] list) {
//		39 this.list = list;
//		40 }
//		41
//		42 protected void compute() {
//		43 if (list.length < 2) return; // base case
//		44 // split into halves
//		45 int[] firstHalf = new int[list.length / 2];
//		46 System.arraycopy(list, 0, firstHalf, 0, list.length / 2);
//		47 int secondLength = list.length - list.length / 2;
//		48 int[] secondHalf = new int[secondLength];
//		49 System.arraycopy(list, list.length / 2, secondHalf, 0, secondLength);
//		50
//		51 // recursively sort the two halves
//		52 SortTask st1 = new SortTask(firstHalf);
//		53 SortTask st2 = new SortTask(secondHalf);
//		54 st1.fork();
//		55 st2.fork();
//		56 st1.join();
//		57 st2.join();
//		58 }
//		59 }
}