import java.util.List;
import java.util.ArrayList;

class PerceptronLearning {
	
	//---------- our current weight vector - weights[0] is the (negative) threshhold
	//weights must have the same lengths as the input patterns!
	static int[] weights = {1,0,0,0};
	
	//---------- the patterns
	//the first int indicates if the result should be negative (-1) or positive (1)
	static int[][] patterns = {{-1, 3,2,5}, {1,1,-1,2}, {1,2,0,-4}, {-1,5,1,1}};
	//this would be the XOR - problem:
	//static int[][] patterns = {{-1,0,0}, {1,0,1}, {1,1,0}, {-1,1,1}};
	
	//contains old weights for the cycle check 
	static List<int[]> old_weights;
	
	//indicates if the cycle check was positive
	static boolean cycle_detected = false;
	
	public static void main(String[] args) {
		old_weights = new ArrayList<int[]>();
		System.out.print("\nThe start weight vector is: ");
		printVector(weights, 0);
		
		System.out.println("\n\npattern\t\t\tclassification\tupdate\t\tweight vector");
		System.out.println("--------------------------------------------------------------------");
		while(!round() && !cycle_detected);	//just do it
		
		if (!cycle_detected) {
			System.out.print("done - a good weight vector is: ");
			printVector(weights, 0);
		}else {
			System.out.print("There is no hyper plane that can solve this problem!");
		}
		System.out.println("");System.out.println("");
	}
	
	/*
		performs a training "round" with all the given pattern sets,
		@return true when all returned the desired results,
		false if some pattern is still falsly classified or a cycle occured
	*/
	private static boolean round() {
		boolean allgood = true;
		for (int i = 0; i < patterns.length; i++) {
			if (!step(i)) allgood = false;
			if (cycle_detected) return false;
		}
		System.out.println("--------------------------------------------------------------------");
		return allgood;
	}
	
	/*
		performs a training step with the pattern inicated by index,
		prints out the computed values
		returns if the result was good.
	*/
	private static boolean step(int index) {
		int[] tmp = patterns[index];
		boolean positive;			//true if result is >= 0
		boolean is_true = false; 	//always expect the worst :-)
		
		int result = weights[0];	//first, add w0
		
		printVector(tmp, 1);
		System.out.print(" el. "); 
		if (tmp[0] == 1) System.out.print("P"); else System.out.print("N");
		
		for (int i = 1; i < tmp.length; i++) {	//starts at 1 because a pattern 
									//has a leading classification (see above)
			result += tmp[i] * weights[i];
		}
		System.out.print(" =>"+ result + " ");
		if (result >= 0) positive = true; else positive = false;
		if (tmp[0] == -1 && !positive) {	//true negative
			is_true = true;
			System.out.print("\ttrue negative\t  -  \t\t  -  ");
		}else if (tmp[0] == 1 && positive) {	//true positive
			is_true = true;
			System.out.print("\ttrue positive\t  -  \t\t  -  ");
		}else {
			//a vector with a leading 1 to calc with and to print it
			int[] tmp2 = new int[tmp.length];
			tmp2[0] = 1;
			for (int i = 1; i < tmp.length; i++) tmp2[i] = tmp[i];
			//update weights
			if (tmp[0] == -1 && positive) {	//false positive
				System.out.print("\tfalse positive\t-");printVector(tmp2, 0);
				for (int i = 0; i < weights.length; i++) {
					weights[i] -= tmp2[i];	
				}
				System.out.print("\t");printVector(weights, 0);
			}
			if (tmp[0] == 1 && !positive) {	//false negative
				System.out.print("\tfalse negative\t+");printVector(tmp2, 0);
				for (int i = 0; i < weights.length; i++) {
					weights[i] += tmp2[i];	
				}
				System.out.print("\t");printVector(weights, 0);
			}
			
			//weights were updated - let's make a cycle check
			//do cycle check - store weights for later cycle checks
			int[] old = new int[weights.length];
			for (int j = 0; j < weights.length; j++) old[j] = weights[j];
			cycleCheck();
			old_weights.add(old);
		}
		System.out.print("\n");

		return is_true;
	}
	
	private static void cycleCheck() {
		for (int i = 0; i < old_weights.size(); i++) {
			//compare vectors
			int[] old_weight_v = (int[]) old_weights.get(i);
			boolean found_match = false;
			for (int j = 0; j < weights.length; j++) {
				if (old_weight_v[j] != weights[j]) break;
				//if we're still here, we matched an old vector
				if (j == weights.length-1) found_match = true;
			}
			if (found_match) {
				System.out.print("\n\n");
				System.out.println("I found a cycle!");
				cycle_detected = true;
			}
		}
	}
	
	//print vector from position p
	private static void printVector(int[] v, int p) {
		System.out.print("(");
		for (int i = p; i < v.length; i++) {
			System.out.print(v[i]);
			if (i < (v.length-1)) System.out.print(",");
		}
		System.out.print(")");
	}
}