uni/inf2440/hw4/Parallel.java

class Parallel extends Oblig4 {
	int nThreads = Math.min(
		Runtime.getRuntime().availableProcessors(),
		16);

	Parallel(int[] x, int[] y, int n) {
		super(x, y, n);
		name = "Parallel";
	}

	@Override
	void solve() {
		MinMaxXY minmax = findMinMax();
		MAX_X = x[minmax.maxX];
		MAX_Y = y[minmax.maxY];

		IntList indexes = new IntList(n);
		for (int i = 0; i < n; ++i)
			indexes.add(i);

		PointsRightOfWorker w1 = new PointsRightOfWorker(
			minmax.maxX, minmax.minX, indexes, 1);
		w1.start();
		PointsRightOfWorker w2 = new PointsRightOfWorker(
			minmax.minX, minmax.maxX, indexes, 1);
		w2.start();

		try { w1.join(); } catch (InterruptedException ex) {}
		try { w2.join(); } catch (InterruptedException ex) {}

		coHull = w1.result;
		coHull.append(w2.result);
	}

	class MinMaxXY {
		int minX, maxX, maxY;
	}

	class FindMinMaxWorker extends Thread {
		int start, end;
		int minX, maxX, maxY;
		FindMinMaxWorker(int start, int end) {
			this.start = start;
			this.end = end;
			this.minX = start;
			this.maxX = start;
			this.maxY = start;
		}

		public void run() {
			for (int i = start + 1; i < end; ++i) {
				if (x[i] < x[minX])
					minX = i;
				if (x[i] > x[maxX])
					maxX = i;
				if (y[i] > y[maxY])
					maxY = i;
			}
		}
	}

	MinMaxXY findMinMax() {
		FindMinMaxWorker[] workers = new FindMinMaxWorker[nThreads];

		int d = n / nThreads;
		for (int i = 0; i < nThreads; ++i) {
			workers[i] = new FindMinMaxWorker(
				d * i,
				(i == nThreads - 1
					? n - 1
					: d * (i + 1)));
			workers[i].start();
		}

		MinMaxXY minmax = new MinMaxXY();
		for (FindMinMaxWorker w: workers) {
			try { w.join(); } catch (InterruptedException ex) {}

			if (x[w.minX] < x[minmax.minX])
				minmax.minX = w.minX;
			if (x[w.maxX] > x[minmax.maxX])
				minmax.maxX = w.maxX;
			if (y[w.maxY] > y[minmax.maxY])
				minmax.maxY = w.maxY;
		}

		return minmax;
	}

	class PointsRightOfWorker extends Thread {
		int p1, p2;
		IntList indexes;
		int depth;
		IntList result;

		PointsRightOfWorker(int p1, int p2, IntList indexes, int depth) {
			this.p1 = p1;
			this.p2 = p2;
			this.indexes = indexes;
			this.depth = depth;
		}

		public void run() {
			result = pointsRightOf(p1, p2, indexes, depth);
		}
	}

	IntList pointsRightOf(int p1, int p2, IntList indexes, int depth) {
		int p3 = -1;
		double p3dist = 0;

		int a = lineA(p1, p2);
		int b = lineB(p1, p2);
		int c = lineC(p1, p2);

		IntList nwIndexes = new IntList();

		for (int i = 0; i < indexes.size(); ++i) {
			int idx = indexes.get(i);
			if (idx == p1 || idx == p2)
				continue;

			double line = lineEquation(a, b, c, idx);
			if (line > 0)
				continue;

			nwIndexes.add(idx);

			double dist = Math.abs(dist(line, a, b));
			if (dist > p3dist) {
				p3dist = dist;
				p3 = idx;
			}
		}

		if (p3 == -1) {
			IntList l = addPointsOnLine(nwIndexes, a, b, c, p1);
			l.add(p2);

			return l;
		}

		if (Math.pow(2, depth) >= nThreads) {
			IntList l = pointsRightOf(p1, p3, nwIndexes, depth);
			l.append(pointsRightOf(p3, p2, nwIndexes, depth));
			return l;
		} else {
			PointsRightOfWorker w1 = new PointsRightOfWorker(p1, p3, nwIndexes, depth + 1);
			w1.start();
			PointsRightOfWorker w2 = new PointsRightOfWorker(p3, p2, nwIndexes, depth + 1);
			w2.start();

			try { w1.join(); } catch (InterruptedException ex) {}
			try { w2.join(); } catch (InterruptedException ex) {}

			IntList l = w1.result;
			l.append(w2.result);
			return l;
		}
	}
}