package graphs.freshcode;

//exported project

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.security.KeyStore.Entry;
import java.util.*;

import org.jgrapht.Graphs;
import org.jgrapht.graph.*;

public class PageRankGraph extends BaseGraph<Integer, DefaultWeightedEdge>
{

	private static final long serialVersionUID = 1L;


	public PageRankGraph()
    {
		super(DefaultWeightedEdge.class);
    } // ensure non-instantiability.


//	// START OF PAGERANK CODE
//

	public Integer getRandomLink(Integer v) {



		Random r = new Random();
		//iterators for weight and outward vert
		Iterator iterWeight = outgoingEdgesOf(v).iterator();
		Iterator iterVertex = outgoingEdgesOf(v).iterator();

		int totalWeight = 0;
		int x = 0;
		int i = 0;
		while(iterWeight.hasNext()) {
			totalWeight+=(int) this.getEdgeWeight((DefaultWeightedEdge) iterWeight.next());
			x+=getWeight(i);

		}
		int count = 0;

		Integer vertRandom = r.nextInt(totalWeight)+1; //random generator

		//redeclare iters
		iterWeight = outgoingEdgesOf(v).iterator();
		iterVertex = outgoingEdgesOf(v).iterator();

		int greaterComparator = 1;
		int lessComparator = 0;

		Integer vertID = -1; //defalt value
		while(iterWeight.hasNext()) {

			lessComparator = greaterComparator + (int) this.getEdgeWeight((DefaultWeightedEdge) iterWeight.next());

			if(vertRandom >= greaterComparator && vertRandom < lessComparator) {
				vertID = this.getEdgeTarget((DefaultWeightedEdge) iterVertex.next());
				return vertID;
			}

			iterVertex.next();
			greaterComparator = lessComparator;
			count++;
		}
		System.out.println("count from randomLink: "+count);
		return vertID; // TODO: REPLACE THIS WITH AN APPROPRIATE RETURN VALUE
	}


	public Integer surfWithJump(Integer v, Integer n, Double jumpThreshold) {
		// PRE: v is vertex to start surf; n >= 0; 0 <= jumpThreshold <= 1.0
		// POST: surfs the graph randomly for n moves,
		//       choosing adjacent vertex according to distribution of edge weights if random number is below jumpThreshold,
		//       choosing any vertex uniformly randomly otherwise;
		//       modifies # visits in vertices
		//       returns last visited vertex at end of surfing


		for(int i = 0; i < n; i++) {
			Random r = new Random();
			float feelingLucky = r.nextFloat();
			this.visitMap.put(v, getVisits(v)+1);


			if(jumpThreshold < feelingLucky|| this.outgoingEdgesOf(v).size() == 0) {

				v = r.nextInt(this.marked.size());//random number between 1-4

			}
			else {
				v = getRandomLink(v);
			}
		}
		return v;
	}


		 // TODO: REPLACE THIS WITH AN APPROPRIATE RETURN VALUE


	public ArrayList<Integer> topN(Integer N) {
		// PRE: none
		// POST: returns N vertices with highest number of visits, in order;
		//       returns all vertices if <N in the graph;
		//       returns vertices ranked 1,..,N,N+1,..,N+k if these k have the
		//         same number of visits as vertex N

		// TODO
		if(N == 0) {
			return null;
		}
		ArrayList<Integer> arr = new ArrayList<Integer>();

		int listSize = this.marked.size();


		for(Integer i = 0; i < listSize; i++) {//putting in array unsorted
			arr.add(i);
		}

		ArrayList<Integer> rankedList = new ArrayList<Integer>();
 		Integer smallest = 0; //holds smallest V
		for(Integer i = 0; i < arr.size()-1 && rankedList.size() < N; i++) {
			smallest = i;

			for(Integer j = i+1; j < arr.size(); j++) {
				if(this.getVisits(arr.get(smallest)) < this.getVisits(arr.get(j))) {
					smallest = j;
				}
			}
			Integer temp = arr.get(i);
			arr.set(i, smallest);
			arr.set(smallest, temp);
			rankedList.add(i, smallest);
		}

		return rankedList;
	}

	public void setVertexWeights () {
	// PRE: -
	// POST: set weights of each vertex v to be v.visits divided by
	//         the total of visits for all vertices
		int totalWeight = 0;
		for(int i = 0; i < this.marked.size(); i++) {//getting net visit
			totalWeight+=this.getVisits(i);
		}
		double vertexWeight;
		for(int i = 0; i < this.marked.size(); i++) {
			vertexWeight = (double)this.getVisits(i)/totalWeight;
			weightMap.put(i, vertexWeight);
		}
	}

	public void convergenceWeights(Integer dp, Double jumpThreshold) {
		// PRE: dp >= 0 representing number of decimal places
		// POST: web is surfed until all weights are constant to dp decimal places,
		//         for at least one iteration
		// TODO
	}

	public Integer surfWithJumpUntilHit(Integer v, Integer n, Double jumpThreshold) {
	// PRE: v is vertex to start surf; n >= 0; 0 <= jumpThreshold <= 1.0
	// POST: surfs the graph randomly until visit v for second time (maximum n moves),
	//       choosing adjacent vertex according to distribution of edge weights if random number is below jumpThreshold,
	//       choosing any vertex uniformly randomly otherwise;
	//       modifies # visits in vertices
	//       returns number of vertices visited
		Random r = new Random();
		int count = 0;
		this.marked.put(v, false);

		for(int i = 0; i < n && !isMarked(v); i++) {

			float feelingLucky = r.nextFloat();
			this.visitMap.put(v, getVisits(v)+1);
			this.setVertexWeights();
			if(i == 0) {
				this.setMarked(v);
			}
			if(feelingLucky < jumpThreshold) {
				v = getRandomLink(v);
			}
			else {
				v = r.nextInt(this.marked.size());//random number between 0-4
			}
			count++;
		}
		System.out.println("count from surfWithJump: "+count);
		return count;

}

	public Integer surfWithJumpUntilCover(Integer v, Integer n, Double jumpThreshold) {
		// PRE: v is vertex to start surf; n >= 0; 0 <= jumpThreshold <= 1.0
		// POST: surfs the graph randomly until all vertices visited (with maximum n vertices visited),
		//       choosing adjacent vertex according to distribution of edge weights if random number is below jumpThreshold,
		//       choosing any vertex uniformly randomly otherwise;
		//       modifies # visits in vertices
		//       returns number of vertices visited
			int verticesVisited = 0;
			Random r = new Random();
			int count = 0;
			int coverTime = 0;
			float feelingLucky = 0;

			for(int i = 0; i < n; i++) {

				feelingLucky = r.nextFloat();
				verticesVisited++;
				if(jumpThreshold < feelingLucky) {

					v = r.nextInt(this.marked.size());//random number between 1-4

				}
				else {
					v = getRandomLink(v);
				}
				visitMap.put(v,  getVisits(v)+1);

				count = 0; //resets count
				setMarked(v);

				for(int j = 0; j < marked.size(); j++) {//goes to all vertices

					if(isMarked(j)) {//checks if all has been visited once
						count++;
					}

				}

				if(count == marked.size()) {
					coverTime+= Double.valueOf(verticesVisited);

					unsetAllMarked();
					break;
				}

			}

			return verticesVisited;
	}




	public Double averageHittingTime(Integer v, Integer n, Integer maxHits, Double jumpThreshold) {
		// PRE: n >= 1 is number of iterations for averaging; maxHits >= 0; 0 <= jumpThreshold <= 1.0
		// POST: returns average number of vertices visited until hitting, across n iterations,
		//         (not including those which stopped because they reached maxHits)
		//       returns 0 if all iterations reached maxVisits
		// TODO

		double avrg = 0;
		double x = 0;
		for(int i = 1; i <= n; i++) {
			x = surfWithJumpUntilHit(v, maxHits, jumpThreshold);
			if(x == maxHits) {
				n--;
			}
			else {
				avrg+=x;
			}
		}
		System.out.println(Integer.valueOf(maxHits*n)+"   "+Integer.valueOf((int)avrg));
		if(Integer.valueOf(maxHits*n) - Integer.valueOf((int)avrg) == 0) {
			return 0.0;
		}

		return Double.valueOf(avrg/n);

	}


	public Double averageCoverTime(Integer n, Integer maxVisits, Double jumpThreshold) {
		// PRE: n >= 1 is number of iterations for averaging; maxVisits >= 0; 0 <= jumpThreshold <= 1.0
		// POST: returns average number of vertices visited until cover, across n iterations,
		//         (not including those which stopped because they reached maxVisits)
		//         randomly selecting start vertex each iteration
		//       returns 0 if all iterations reached maxVisits

		// TODO
		Random r = new Random();


		double coverTime = 0.0;
		Integer v = r.nextInt(marked.size());

		for(int i = 1; i <= n; i++) {
			coverTime+=surfWithJumpUntilCover(v, maxVisits, jumpThreshold);
			v = r.nextInt(marked.size());
		}

		if(Integer.valueOf(maxVisits*n) == Integer.valueOf((int)coverTime)) {
			return Double.valueOf(0);
		}

		return Double.valueOf(coverTime/n);
	}

	public Integer boostVertex(Integer v, Integer dp) {
		// PRE: v is a vertex in the graph
		// POST: returns a vertex v2 (!= v) such that when edge (v,v2,1.0) is added to the graph,
		//         the weight of v is larger than when edge (v,v3,1.0) is added to the graph
		//         (for any v3), when the graph is surfed to convergence
		//       if there is no such vertex v2 (i.e. v is already connected to all other vertices),
		//         return v
		//       edges are only added if they do not already exist in the graph

		// TODO

		return -1; // TODO: REPLACE THIS WITH AN APPROPRIATE RETURN VALUE

	}


	public void setWeightedIntFromFile(String fInName) throws IOException {
		// Reads list of edges from a file, one pair of integers plus weight per line
		BufferedReader fIn = new BufferedReader(
							 new FileReader(fInName));
		String s;
		Integer x, y;
		Double w;

		while ((s = fIn.readLine()) != null) {
			java.util.StringTokenizer line = new java.util.StringTokenizer(s);
			while (line.hasMoreTokens()) {
				x = Integer.parseInt(line.nextToken());
				y = Integer.parseInt(line.nextToken());
				w = Double.parseDouble(line.nextToken());
				this.addVertex(x);
				this.addVertex(y);
				DefaultWeightedEdge e = this.addEdge(x,y);
				this.setEdgeWeight(e, w);
			}
		}
		fIn.close();

		unsetAllMarked();
	}

	public static void main(String[] args) {
		PageRankGraph g = new PageRankGraph();

		try {
			String PATH =  "/home/evan/Desktop/assignment-sample-graphs/";
			g.setWeightedIntFromFile(PATH+"medium-weight.txt");
		}
		catch (IOException e) {
			System.out.println("in exception: " + e);
		}
		System.out.println(g.toString());
		g.print();


	}
}