minmax

minmax.java

package aufgabe1;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;
import java.util.concurrent.Callable;

public class MinMax<T extends Comparable<T>> {

	// Ich bin einfach ein bisschen Haskell-verdorben.
	public static class Maybe<V> {

		private final boolean isNothing;
		private final V value;

		public static <X> Maybe<X> just(final X value) {
			return new Maybe<>(value);
		}

		public static <X> Maybe<X> nothing() {
			return new Maybe<>();
		}

		public Maybe() {
			isNothing = true;
			value = null;
		}

		public Maybe(V value) {
			isNothing = false;
			this.value = value;
		}

		public boolean isJust() {
			return !isNothing;
		}

		public boolean isNothing() {
			return isNothing;
		}

		public V get() {
			return value;
		}
	}

	// Java hat leider keine Tupel... also bauen wir uns ein
	// Problem-spezifisches Tupel.
	public class MinMaxResult {
		private final T min;
		private final T max;

		public MinMaxResult(final T min, final T max) {
			this.min = min;
			this.max = max;
		}

		public T getMin() {
			return min;
		}

		public T getMax() {
			return max;
		}

		public String toString() {
			return String.format("Min: %s, Max: %s", min, max);
		}
	}

	private Maybe<MinMaxResult> checkList(final List<T> list) {
		if (list == null || list.isEmpty()) {
			return Maybe.just(null);
		}
		if (list.size() == 1) {
			return Maybe.just(new MinMaxResult(list.get(0), list.get(0)));
		}
		return Maybe.nothing();
	}

	public MinMaxResult findMinMaxSimple(final List<T> list) {

		for (final Maybe<MinMaxResult> result = checkList(list); result
				.isJust();) {
			return result.get();
		}

		if (list.size() == 1) {
			return new MinMaxResult(list.get(0), list.get(0));
		}
		T max = list.get(0);
		T min = list.get(0);
		for (int i = 1; i < list.size(); i++) {
			final T elem = list.get(i);
			if (elem.compareTo(min) < 0) {
				min = elem;
			}
			if (elem.compareTo(max) > 0) {
				max = elem;
			}
		}
		return new MinMaxResult(min, max);
	}

	public MinMaxResult findMinMaxUsingSort(final List<T> list) {

		for (Maybe<MinMaxResult> result = checkList(list); result.isJust();) {
			return result.get();
		}
		// Collections.sort arbeitet in-place, daher duplizieren wir die Liste
		// zunächst.
		final List<T> theList = new ArrayList<>(list.size());
		theList.addAll(list);

		Collections.sort(theList);

		return new MinMaxResult(theList.get(0), theList.get(theList.size() - 1));
	}

	private T findMin(final List<T> list) {
		int lowerLimit = list.size() % 2;
		for (int i = list.size() - 1; i > lowerLimit; i -= 2) {
			final T leftValue = list.get(i - 1);
			final T rightValue = list.get(i);

			if (leftValue.compareTo(rightValue) < 0) {
				list.remove(i);
			} else {
				list.remove(i - 1);
			}
		}
		if (list.size() > 1) {
			return findMin(list);
		}
		return list.get(0);
	}

	private T findMax(List<T> list) {
		int lowerLimit = list.size() % 2;
		for (int i = list.size() - 1; i > lowerLimit; i -= 2) {
			final T leftValue = list.get(i - 1);
			final T rightValue = list.get(i);

			if (leftValue.compareTo(rightValue) < 0) {
				list.remove(i - 1);
			} else {
				list.remove(i);
			}
		}
		if (list.size() > 1) {
			return findMax(list);
		}
		return list.get(0);
	}

	public MinMaxResult findMinMaxDivideAndConquer(final List<T> list) {

		for (final Maybe<MinMaxResult> result = checkList(list); result
				.isJust();) {
			return result.get();
		}
		final List<T> left = new ArrayList<>(list.size() / 2 + list.size() % 2);
		final List<T> right = new ArrayList<>(list.size() / 2);
		for (int i = 0; i < list.size() - list.size() % 2; i += 2) {
			final T leftValue = list.get(i);
			final T rightValue = list.get(i + 1);

			if (leftValue.compareTo(rightValue) < 1) {
				left.add(leftValue);
				right.add(rightValue);
			} else {
				left.add(rightValue);
				right.add(leftValue);
			}
		}
		if (list.size() % 2 == 1) {
			left.add(list.get(list.size() - 1));
		}
		T min = left.size() == 1 ? left.get(0) : findMin(left);
		T max = right.size() == 1 ? right.get(0) : findMax(right);

		return new MinMaxResult(min, max);
	}

	private static class TimedResult<T> {
		private final T result;
		private final long timeTaken;

		public TimedResult(final T result, final long timeTaken) {
			this.result = result;
			this.timeTaken = timeTaken;
		}

		public long getTimeTaken() {
			return timeTaken;
		}

		public T getResult() {
			return result;
		}
	}

	private static <T> TimedResult<T> timed(final Callable<T> callable)
			 {
		final long start = System.nanoTime();

		T result = null;
		try {
			result = callable.call();
		} catch (Exception e) {
			e.printStackTrace();
		}
		final long end = System.nanoTime();
		return new TimedResult<T>(result, end - start);
	}

	private static <T> void report(String title, TimedResult<T> result) {
		System.out.printf("%s:\n", title);
		System.out.printf("  Result: %s, Comparisons: %7d, Time taken: %fms\n",
				result.getResult(), ComplexObject.comparisons,
				result.getTimeTaken() / 1000000.0);
		ComplexObject.comparisons = 0;
	}

	private static class ComplexObject implements Comparable<ComplexObject> {

		private final long value;
		private static long comparisons = 0;
		private static long comparisonCost = 0;

		public ComplexObject(final long value) {
			this.value = value;
		}

		@Override
		public int compareTo(final ComplexObject o) {
			long devNull = 10;
			for (long i = 0; i < comparisonCost; i++) {
				devNull = devNull * 2;
			}
			comparisons++;
			return Long.compare(value, o.value);
		}

		public String toString() {
			return Long.toString(value);
		}
	}

	static int problemSize, comparisonCost;

	public static void main(String... args)  {

		final long seed = System.currentTimeMillis();

		test(comparisonCost = 0, problemSize = 1000, seed);
		test(comparisonCost = 0, problemSize = 10000, seed);
		test(comparisonCost = 25000, problemSize = 10000, seed);
		test(comparisonCost = 1250000, problemSize = 1000, seed);
	}

	public static void test(final long comparisonCost, final int problemSize,
			final long seed)  {
		ComplexObject.comparisonCost = comparisonCost;

		System.out.printf(
				"\nSeed: %d, problem size: %d, comparison cost: %d\n\n", seed,
				problemSize, comparisonCost);

		final MinMax<ComplexObject> minMax = new MinMax<>();

		final List<ComplexObject> theList = new ArrayList<ComplexObject>(
				problemSize);
		final Random sequence = new Random(seed);
		for (long i = 0; i < problemSize; i++) {
			theList.add(new ComplexObject(Math.abs(sequence.nextLong())));
		}
		Collections.shuffle(theList);

		report("simple",
				timed(new Callable<MinMax<ComplexObject>.MinMaxResult>() {
					@Override
					public MinMax<ComplexObject>.MinMaxResult call()
							 {
						return minMax.findMinMaxSimple(theList);
					}
				}));

		report("sort",
				timed(new Callable<MinMax<ComplexObject>.MinMaxResult>() {
					@Override
					public MinMax<ComplexObject>.MinMaxResult call()
							 {
						return minMax.findMinMaxUsingSort(theList);
					}
				}));

		report("divideAndConquer",
				timed(new Callable<MinMax<ComplexObject>.MinMaxResult>() {
					@Override
					public MinMax<ComplexObject>.MinMaxResult call()
							 {
						return minMax.findMinMaxDivideAndConquer(theList);
					}
				}));

	}
}