// IMeasure
private int factor;
private int numberofCalls;

BinarySearch() {
    factor = 2;
    numberofCalls = 0;
}

public void setFactor(int factor) {
    this.factor = factor;
}

public int getNumberofCalls() {
    return numberofCalls;
}

public Value find(List<Unit<Key, Value>> haystack, Key needle) {
    numberofCalls = 0;
    return findRec(haystack, needle, 0, haystack.size());
}

private Value findRec(List<Unit<Key, Value>> haystack, Key needle, int begin, int end) {
    numberofCalls++; // IMeasure
    if (begin == end) {
        return null;
    }
    int middle = begin + (end - begin) / factor;
    Unit<Key, Value> middleThing = haystack.get(middle);
    int match = needle.compareTo(middleThing.key);
    if (match == 0) {
        return middleThing.value;
    } else if (match < 0) {
        return findRec(haystack, needle, begin, middle);
    } else {
        return findRec(haystack, needle, middle + 1, end);
    }
}

static final int[] keys = {3, 7, 17, 25, 33, 47, 56, 62, 65, 66, 68, 70,
        78, 89, 92};

static ArrayList<Unit<Integer, Integer>> numbers;

private static void createKeys() {
    numbers = new ArrayList<Unit<Integer, Integer>>();
    for (int key : keys) {
        numbers.add(new Unit<Integer, Integer>(key, key));
    }
}

// Suche nach allen vorhandenen Zahlen
private static void measure1(int factor) {
    BinarySearch<Integer, Integer> search = new BinarySearch<Integer, Integer>();
    search.setFactor(factor);

    int sumCalls = 0;

    for (int key : keys) {
        search.find(numbers, key);
        sumCalls += search.getNumberofCalls();
    }

    double result = ((double) sumCalls) / keys.length;

    System.out.println(String.format("Messung Frage 1, Faktor: %d, mittlere Suchtiefe: %.2f", factor, result));
}

// Suche nach allen Zahlen von 0 bis 99
private static void measure2(int factor) {
    BinarySearch<Integer, Integer> search = new BinarySearch<Integer, Integer>();
    search.setFactor(factor);

    int sumCalls = 0;

    for (int i = 0; i < 100; i++) {
        search.find(numbers, i);
        sumCalls += search.getNumberofCalls();
    }

    double result = ((double) sumCalls) / 100;

    System.out.println(String.format("Messung Frage 2, Faktor: %d, mittlere Suchtiefe: %.2f", factor, result));
}

// Suche nach allen Zahlen von 0 bis 9
private static void measure3(int factor) {
    BinarySearch<Integer, Integer> search = new BinarySearch<Integer, Integer>();
    search.setFactor(factor);

    int sumCalls = 0;

    for (int i = 0; i < 10; i++) {
        search.find(numbers, i);
        sumCalls += search.getNumberofCalls();
    }

    double result = ((double) sumCalls) / 10;

    System.out.println(String.format("Messung Frage 3, Faktor: %d, mittlere Suchtiefe: %.2f", factor, result));

}

public class BruteForce implements IRucksack {
    public Selection findBest(ArrayList<Integer> values, ArrayList<Integer> weights, int maxWeight) {
        if (values.size() != weights.size())
            throw new IllegalArgumentException("sizes of values and weights vectors are not equal");

        Selection bestSelection = null;
        int maxValue = -1;
        
        final int max = (int) Math.pow(2, values.size());
        for (int i = 0; i < max; i++) {
            Selection selection = new Selection(values.size(), i);
            if (selection.sum(weights) <= maxWeight) {
                int value = selection.sum(values);
                if (value >= maxValue) {
                    bestSelection = selection;
                    maxValue = value;
                }
            }
        }
        return bestSelection;
    }
}

private Selection find(Selection selection, int weight, ArrayList<Integer> values,
                            ArrayList<Integer> weights, int maxWeight) {
    
    final int depth = selection.size();
    if (depth == values.size()) {
        return selection;
    }

    Selection without = new Selection(depth + 1, selection.bits());
    without.set(depth, false);
    Selection resultWithout = find(without, weight, values, weights, maxWeight);

    if (weight + weights.get(depth) <= maxWeight) {
        Selection with = new Selection(depth + 1, selection.bits());
        with.set(depth, true);

        Selection resultWith = find(with, weight + weights.get(depth), values,
                                        weights, maxWeight);
        if (resultWith.sum(values) > resultWithout.sum(values)) {
            return resultWith;
        }
    }
    return resultWithout;
}

public Selection findBest(ArrayList<Integer> values, ArrayList<Integer> weights,
                            int maxWeight) {
    if (values.size() != weights.size())
        throw new IllegalArgumentException("sizes of values and weights vectors are not equal");

    Selection result = find(new Selection(0), 0, values, weights, maxWeight);
    return result;
}

class BestMove {
  /**
   * The coordinates of the proposed next move
   */
  public Coordinates coord;
  
  /**
   * The value of the proposed next move according to the min-max analysis
   */
  public int value;
  
  public BestMove(int value, Coordinates coord) {
    this.value = value;
    this.coord = coord;
  }
}

 private BestMove max(int maxDepth, long timeout, GameBoard gb, int depth) throws Timeout {
	if (time is up){
    	throw new Timeout();
    }
    
    if(depth == maxDepth){
    	//TODO: use eval() to determine the value of this position
    }
    
    for (all possible moves)
        clone board;
        make move on clone;
        temp_move = min(maxDepth, timeout, cloned_board, depth+1);
        save in best_move if best move so far;
    return best_move
}