import java.io.*;
import java.util.*;

public class PLGraph extends Graph {
	static private int StopGap = 10;
	public class PLNode extends Node {
		private int maxEdges;
		PLNode (int ID, int maxEdges) {
			super(ID);
			this.maxEdges = maxEdges;
		}
		public int emptyEdges() {
			return maxEdges-edges();
		}
		public int maxEdges() {
			return maxEdges;
		}
	}
    PLGraph (int N, double gamma, int K, 
					 boolean random, boolean topdown, boolean complete) {
		this((new PowerLawList(N, gamma, K)).degreeHist(), 
			 K, random, topdown, complete);
    };
    PLGraph (int [] degreeHist, int K, 
					 boolean random, boolean topdown, boolean complete) {
		super();
		int nodeSum = 0;
		for (int i=degreeHist.length-1; i>=0; i--) {
			int iNodes = degreeHist[i];		//nodes @ i
			int iEdges = i+K;				//edges @ i
			for (int j=0; j<iNodes; j++)
				nodes.add(new PLNode(j+nodeSum,iEdges));
			nodeSum += iNodes;
		}
		if (random && topdown)
			connectEdgesRandomly(complete);
		else if (random && !topdown)
			connectNodesRandomly(complete);
		else
			connectTopDown(topdown, complete);
		sortByDegree(true);
    };
    public void connectEdgesRandomly(boolean complete) {
		ArrayList list = new ArrayList();
		for (Iterator it = nodes.iterator(); it.hasNext();){
			PLNode n = (PLNode)it.next();
			for (int i=0; i<n.emptyEdges(); i++)
				list.add(n);
		}
		randShuffle(list); 
		int gap = 0; do {
			int r1 = randInt(list.size());
			int r2 = randInt(list.size());
			if (r1>r2) { // make ordered so remove() works.
				int rtemp=r1; r1=r2; r2=rtemp;
			}
			PLNode n1 = (PLNode)list.get(r1);
			PLNode n2 = (PLNode)list.get(r2);
			gap++;
			if (n1 != n2 && !n1.edgeList().contains(n2)){
				gap = 0;
				n1.addEdge(n2);
				n2.addEdge(n1);
				list.remove(r2);
				list.remove(r1);
			}
		} while (gap<StopGap && list.size()>0);

		if (list.size()>0) {
			System.out.print("!Unconnected nodes left:"+list.size());
			for (Iterator it=list.iterator(); it.hasNext();) {
				PLNode n = (PLNode)it.next();
				System.out.print("\t"+n.ID()+":"+n.emptyEdges());
			}
			System.out.println();
		}

		if (complete && list.size()>0) {
			gap = 0; do {
				PLNode n1 = (PLNode)list.get(randInt(list.size()));
				Node n2 = (Node)nodes.get(randInt(nodes.size()));
				gap++;
				if (n1 != n2 && !n1.edgeList().contains(n2)){
					gap = 0;
					n1.addEdge(n2);
					n2.addEdge(n1);
					if (n1.emptyEdges()<=0)
						list.remove(list.indexOf(n1));
				}
			} while (gap<StopGap && list.size()>0);
			if(list.size()!=0)
				System.out.print("!Unconnected nodes left: "+list.size());
		}
	}
    public void connectNodesRandomly(boolean complete) {
		ArrayList list = new ArrayList(nodes);
		randShuffle(list); 
		int gap = 0; do {
			int r1 = randInt(list.size());
			int r2 = randInt(list.size());
			if (r1>r2) {
				int rtemp=r1; r1=r2; r2=rtemp;
			}
			PLNode n1 = (PLNode)list.get(r1);
			PLNode n2 = (PLNode)list.get(r2);
			gap++;
			if (n1 != n2 && !n1.edgeList().contains(n2)){
				gap = 0;
				n1.addEdge(n2);
				n2.addEdge(n1);
				if (n2.emptyEdges()<=0)
					list.remove(r2);
				if (n1.emptyEdges()<=0)
					list.remove(r1);
			}
		} while (gap<StopGap && list.size()>0);

		if (list.size()>0) {
			System.out.print("!Unconnected nodes left:"+list.size());
			for (Iterator it=list.iterator(); it.hasNext();) {
				PLNode n = (PLNode)it.next();
				System.out.print("\t"+n.ID()+":"+n.emptyEdges());
			}
			System.out.println();
		}

		if (complete && list.size()>0) {
			gap = 0; do {
				PLNode n1 = (PLNode)list.get(randInt(list.size()));
				Node n2 = (Node)nodes.get(randInt(nodes.size()));
				gap++;
				if (n1 != n2 && !n1.edgeList().contains(n2)){
					gap = 0;
					n1.addEdge(n2);
					n2.addEdge(n1);
					if (n1.emptyEdges()<=0)
						list.remove(list.indexOf(n1));
				}
			} while (gap<StopGap && list.size()>0);
			if(list.size()!=0)
				System.out.print("!Unconnected nodes left: "+list.size());
		}
	}
    public void connectTopDown(boolean topdown, boolean complete) {
		int fixedConx = 0, fixedEdges = 0;
		ArrayList list = new ArrayList(nodes);
		if (!topdown)
			randShuffle(list); 
		for (int i=0; i<list.size(); i++) {
			PLNode node = (PLNode)list.get(i);
			if (node.edges()==0 && i>0 && topdown) {//fix tpdn isolated links.
				PLNode fix = (PLNode)list.get(i-1);
				fix.addEdge(node);
				node.addEdge(fix);
				fixedConx++;
			}
			int emptyEdges = node.emptyEdges();
			PLNode nextNode;
			for (int j=i+1; j<list.size() && emptyEdges>0; j++) {
				nextNode = (PLNode)list.get(j);
				if (nextNode.emptyEdges()>0) {
					nextNode.addEdge(node);
					node.addEdge(nextNode);
					emptyEdges--;
				}
			}
			if (emptyEdges > 0 && complete) {
				fixedEdges += emptyEdges;
				int r = -1;
				while (emptyEdges>0) {
					r++;
					nextNode = (PLNode)list.get(r);
					if (nextNode!=node && !nextNode.edgeList().contains(node)){
						nextNode.addEdge(node);
						node.addEdge(nextNode);
						emptyEdges--;
					}
				}
			}
		}
		if (fixedConx>0)
			System.out.println("!Fixed "+fixedConx+" unconnected links");
		if (fixedEdges>0)
			System.out.println("!Fixed "+fixedEdges+" edges");
    }
	// ---------------- Test Program
    public static void main (String args[]) {
		boolean print = false;
		int N=Integer.parseInt(arg(args, 0, "100"));
		if (N<=100) { // print graph if <= 100 or neg
			N=Math.abs(N);
			print=true;
		}
		int K=Integer.parseInt(arg(args, 1, "3"));
		double gamma=-Double.parseDouble(arg(args, 2, "2.5"));
		boolean random=Boolean.valueOf(arg(args, 3, "false")).booleanValue();
		boolean topdown=Boolean.valueOf(arg(args, 4, "true")).booleanValue();
		boolean complete=Boolean.valueOf(arg(args, 5, "true")).booleanValue();
		String style=(random?"Random":"TopDown")
			+(topdown?(random?"-Edges":"-Linear"):(random?"-Nodes":"-Shuffle"))
			+(complete?"-Complete":"-Incomplete");
		String name=(random?"Rd":"Td")
			+(topdown?(random?"E":"L"):(random?"N":"S"))
			+(complete?"+":"-")
			+N+"-"+K+"-"+(Math.abs(gamma));
		System.out.println(name+": "+style+" N="+N+" K="+K+" G="+gamma);
		assert(N > K, "N <= K: N="+N+" K="+K);

		PLGraph g = new PLGraph(N,gamma,K,random,topdown,complete);
		if (print)
			g.printByLevel();
		g.printHist("Edge Histogram");
		g.printLevels("Levels Histogram");
    }
}