<commit_before>package kex.heuristics;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

import kex.Graph;
import kex.Kattio;
import kex.Verify;
import kex.heuristics.selectors.GreedySelector;
import kex.heuristics.selectors.Selector;
import kex.heuristics.selectors.SelectorType;
import kex.heuristics.selectors.SimpleSelector;
import kex.stateinspectors.IndexedStateInspector;
import kex.stateinspectors.ProbabilisticStateInspector;
import kex.stateinspectors.StateInspector;
import kex.stateinspectors.StateInspectorType;

/**
 * Heuristics for The Monk problem.
 * @author <NAME>
 * @author <NAME>
 */
public class Heuristics {
	private static boolean DEBUG = false;
	
	/* 
	 * Read a graph from stdin and print a strategy to stdout.
	 */
	public static void main(String[] args) {
		/* Default values */
		InputStream is = System.in;
		
		/* Parse arguments */
		for (int i = 0; i < args.length; i++) {
			int argCount = 0; // expected number of arguments to follow a flag
			
			if (args[i++].equals("-f")) {
				//----------------- READ FROM FILE -----------------//
				argCount = 1;
				String arg = getArguments(args, argCount, i)[0];
				if (arg == null) {
					System.err.println("The flag -f requires one argument.");
					System.exit(1);
				} else {
					try {
						is = new FileInputStream(arg);
					} catch (FileNotFoundException e) {
						System.err.println("The file " + arg + " does not exist.");
						System.exit(1);
					}
				}
			} else if (args[i++].equals("-d")) {
				//--------------- ENABLE DEBUGGING ----------------//
				DEBUG = true;
			} else {
				//----------------- UNKNOWN FLAG -----------------//
				System.err.println("Unknown flag " + args[i]);
				System.exit(1);
			}
			
			i += argCount;
		}
		
		/* Read graph from stdin */
		Kattio io = new Kattio(is, System.out);
		int vertexCount = io.getInt();
		ArrayList<LinkedList<Integer>> adjacencyList = new ArrayList<LinkedList<Integer>>(vertexCount);
		for (int i = 0; i < vertexCount; i++) adjacencyList.add(new LinkedList<Integer>());
		while (io.hasMoreTokens()) {
			/* Read an edge u->v */
			int u = io.getInt();
			int v = io.getInt();
			adjacencyList.get(u).add(v);
		}
		
		/* Create graph from adjacency list */
		Graph graph = new Graph(adjacencyList);
		
		/* Decontaminate the graph */
		Heuristics heuristics = new Heuristics();
		Strategy strategy = heuristics.solve(graph);
		
		/* Print the vertices to be decontaminated at each day */
		io.println(strategy.toString());
		
		/* Print length of solution */
		io.println("Solution length: "+strategy.getLength());
		
		/* Verify the solution and print the result as a certificate */
		Verify verifier = new Verify(graph);
		if (verifier.verify(strategy)) {
			io.println("The solution is winning.");
		} else {
			io.println("The solution is not winning.");
			io.print(verifier.getStatesString());
		}
		
		io.close();
	}
	
	private Selector getSelector(SelectorType type) {
		if (type == SelectorType.SIMPLE) return new SimpleSelector();
		if (type == SelectorType.GREEDY) return new GreedySelector();
		
		return null;
	}
	
	private StateInspector getStateInspector(StateInspectorType type, int vertexCount) {
		if (type == StateInspectorType.BLOOM_FILTER) return new ProbabilisticStateInspector(vertexCount);
		if (type == StateInspectorType.ARRAY) return new IndexedStateInspector(vertexCount);
		
		return null;
	}
	
	/**
	 * Get count arguments from args starting at i.
	 * @return An array of arguments or null if out of bounds.
	 */
	private static String[] getArguments(String[] args, int i, int count) {
		assert(args.length != 0);
		assert(args != null);
		assert(count > 0);
		
		if (i + count > args.length) {
			return null;
		}
		
		String[] result = new String[count];<commit_msg>Added timing of graphsolving.<commit_after>package kex.heuristics;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

import kex.Graph;
import kex.Kattio;
import kex.Verify;
import kex.heuristics.selectors.GreedySelector;
import kex.heuristics.selectors.Selector;
import kex.heuristics.selectors.SelectorType;
import kex.heuristics.selectors.SimpleSelector;
import kex.stateinspectors.IndexedStateInspector;
import kex.stateinspectors.ProbabilisticStateInspector;
import kex.stateinspectors.StateInspector;
import kex.stateinspectors.StateInspectorType;

/**
 * Heuristics for The Monk problem.
 * @author <NAME>
 * @author <NAME>
 */
public class Heuristics {
	private static boolean DEBUG = false;
	
	/* 
	 * Read a graph from stdin and print a strategy to stdout.
	 */
	public static void main(String[] args) {
		/* Default values */
		InputStream is = System.in;
		
		/* Parse arguments */
		for (int i = 0; i < args.length; i++) {
			int argCount = 0; // expected number of arguments to follow a flag
			
			if (args[i++].equals("-f")) {
				//----------------- READ FROM FILE -----------------//
				argCount = 1;
				String arg = getArguments(args, argCount, i)[0];
				if (arg == null) {
					System.err.println("The flag -f requires one argument.");
					System.exit(1);
				} else {
					try {
						is = new FileInputStream(arg);
					} catch (FileNotFoundException e) {
						System.err.println("The file " + arg + " does not exist.");
						System.exit(1);
					}
				}
			} else if (args[i++].equals("-d")) {
				//--------------- ENABLE DEBUGGING ----------------//
				DEBUG = true;
			} else {
				//----------------- UNKNOWN FLAG -----------------//
				System.err.println("Unknown flag " + args[i]);
				System.exit(1);
			}
			
			i += argCount;
		}
		
		/* Read graph from stdin */
		Kattio io = new Kattio(is, System.out);
		int vertexCount = io.getInt();
		ArrayList<LinkedList<Integer>> adjacencyList = new ArrayList<LinkedList<Integer>>(vertexCount);
		for (int i = 0; i < vertexCount; i++) adjacencyList.add(new LinkedList<Integer>());
		while (io.hasMoreTokens()) {
			/* Read an edge u->v */
			int u = io.getInt();
			int v = io.getInt();
			adjacencyList.get(u).add(v);
		}
		
		/* Create graph from adjacency list */
		Graph graph = new Graph(adjacencyList);
		
		/* Decontaminate the graph */
		Heuristics heuristics = new Heuristics();
		long time = System.currentTimeMillis();
		Strategy strategy = heuristics.solve(graph);
		time = System.currentTimeMillis()-time;
		
		
		/* Print the vertices to be decontaminated at each day */
		io.println(strategy.toString());
		
		/* Print length of solution */
		io.println("Solution length: "+strategy.getLength());
		
		/* Verify the solution and print the result as a certificate */
		Verify verifier = new Verify(graph);
		if (verifier.verify(strategy)) {
			io.println("The solution is winning.");
		} else {
			io.println("The solution is not winning.");
			io.print(verifier.getStatesString());
		}
		
		io.println("Solution found in: "+time+" ms");
		io.close();
	}
	
	private Selector getSelector(SelectorType type) {
		if (type == SelectorType.SIMPLE) return new SimpleSelector();
		if (type == SelectorType.GREEDY) return new GreedySelector();
		
		return null;
	}
	
	private StateInspector getStateInspector(StateInspectorType type, int vertexCount) {
		if (type == StateInspectorType.BLOOM_FILTER) return new ProbabilisticStateInspector(vertexCount);
		if (type == StateInspectorType.ARRAY) return new IndexedStateInspector(vertexCount);
		
		return null;
	}
	
	/**
	 * Get count arguments from args starting at i.
	 * @return An array of arguments or null if out of bounds.
	 */
	private static String[] getArguments(String[] args, int i, int count) {
		assert(args.length != 0);
		assert(args != null);
		assert(count > 0);
		
		if (i + count > args.length) {
			return null;
		}
		
		String[] result = new String[count];
{'fraction_non_alphanumeric': 0.14976814137109914, 'fraction_numerical': 0.002506579771901241, 'mean_word_length': 3.134715025906736, 'pattern_counts': {'":': 0, '<': 21, '<?xml version=': 0, '>': 23, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7467759', 'n_tokens_mistral': 2845, 'n_tokens_neox': 2442, 'n_words': 678}