// Created May 2007
import java.io.*;
import java.util.*;




public class DB {
    protected Item [] V;
    protected LinkedList<int []> E;
    protected int n;  	// Total number of items
    protected int m;  	// Total number of transactions
    protected int totalDegree;

    public DB(int size) { 
	V = new Item[size];
	for(int z=0; z!=size; z++) V[z] = new Item(z+1);
	E = new LinkedList<int []>();
	n = size;
	m = 0;
	totalDegree=0;
    }


    // Quicksort
    private static int partition (int [] A, int p, int r) {
	int pivot = A[r];
	int i = p-1;
	
	for ( int j = p ; j <= r-1 ; j++ )
	    if ( A[j] <= pivot ) {
		i++;
		int t = A[j];
		A[j] = A[i];
		A[i] = t;
	    }
	int t = A[i+1];
	A[i+1] = pivot;
	A[r] = t;
	
	return i+1;
    }

    private void qsort (int [] A, int p, int r) {
	if (p<r) {
	    int mid = partition(A,p,r);
	    qsort(A,p,mid-1);
	    qsort(A,mid+1,r);
	}
    }

    private void sort (int [] A) { qsort(A,0,A.length-1); }

    public void random ( Random src,
			 // edge size parameters
			 double mu,     
			 double sigma, 
			 // transaction type params
			 double alpha,
			 double pn, 
			 double po, 
			 // number of edges
			 int h ) {
	int x;
	int [] e;
	
	// Initial setting: one vertex, one edge with two copies of vertex 0
	V = new Item[1];
	V[0] = new Item(1); 
	e = new int[2]; 
	e[0] = e[1] = 0; 
	V[0].setDegree(2);
	E = new LinkedList<int []>();	E.addFirst(e);
	n=1; m=1; totalDegree = 2;

	for ( int t  = 1 ; t <= h ; t++ ) {
	    // Select the size  from a "folded" normal distribution
	    x = (int) Math.ceil(Math.abs(sigma*src.nextGaussian()+mu));
	    
	    if (x>0) {
		// Set e to the empty transaction
		e = new int [x];
		
		if ( src.nextDouble() <= alpha ) {
		    // NEW procedure
		    
		    // Expand V adding a new vertex  v
		    Item [] U = new Item [n+1];
		    for ( int i = 0 ; i < n ; i++ ) 
			U[i] = new Item(V[i].getLabel(),
					V[i].getDegree());
		    U[n] = new Item(n+1,1);
		    V = U;
		    n++;
		    
		    // Add  v  to the new edge
		    e[0] = n-1;
		    
		    // Then behave like in the OLD procedure w.r.t. the other vertices
		    for ( int i = 0 ; i < x-1 ; i++ ) {
			// choose e[i] from 1..x  with prob p_C(e[i],t)
			if (src.nextDouble() <= pn ) { 
			    // select by pref attachment
			    
			    // choose between 1 and \sum degrees.
			    int choice = src.nextInt(totalDegree) + 1;
			    
			    // find the right vertex.
			    int partial = 0;
			    for ( int y = 0 ; y < n ; y++ ) {
				partial += getDegree(y);
				if ( choice <= partial ) {
				    e[i] = y;
				    break; 
				}
			    }
			    
			    // increment deg(v[choice])
			    V[e[i]].setDegree(V[e[i]].getDegree() + 1);
			}
			else { 
			    // select uniformly at random
			    
			    // choose between 0 and n-1
			    int choice = src.nextInt(n);
			    
			    e[i] = choice;
			    
			    // increment deg(v[choice])
			    V[e[i]].setDegree(V[e[i]].getDegree() + 1);
			}		    
		    }
		}
		else { 
		    // OLD procedure

		    for ( int i = 0 ; i < x ; i++ ) {
			// choose e[i] from 1..x  with prob p_C(e[i],t)
			if ( src.nextDouble() <= po ) { 
			    // select by pref attachment
			    
			    // choose between 1 and \sum degrees.
			    int choice = src.nextInt(totalDegree) + 1;
			    
			    // find the right vertex.
			    int partial = 0;
			    for ( int y = 0 ; y < n ; y++ ) {
				partial += getDegree(y);
				if ( choice <= partial ) {
				    e[i] = y;
				    break; 
				}
			    }
			    
			    // increment deg(v[choice])
			    V[e[i]].setDegree(V[e[i]].getDegree() + 1);
			}
			else { 
			    // select uniformly at random
			    
			    // choose between 0 and n-1
			    int choice = src.nextInt(n);
			    
			    e[i] = choice;
			    
			    // increment deg(v[choice])
			    V[e[i]].setDegree(V[e[i]].getDegree() + 1);
			}		    
		    }
		}
		
		sort(e);
		E.addFirst(e);
		m++;
		totalDegree += x;
	    }
	}
	    
    }

    public int getDegree(int v) {
	if (v>=0&&v<n) return V[v].getDegree();
	else {
	    System.out.println("Graph.getDegree: Illegal vertex label.");
	    return -1;
	}
    }

    public void printGraph (String choice) {

	System.out.println("[DB.printGraph]");
	System.out.println("There's " + n + " items.");
	System.out.println("Total degree is " + totalDegree);
	if (choice.equals("basic")) {
	    System.out.println("Edges"); 
	    for ( int i = 0 ; i < E.size() ; i++ ) {
		for ( int j = 0 ; j < E.get(i).length ; j++ )
		    System.out.print(E.get(i)[j] + " ");
		System.out.println();
	    }
	    
	    System.out.println("Degrees");
	    int [] degrees = new int [n];
	    for ( int i = 0 ; i < n ; i++ ) degrees[i] = V[i].getDegree();
	    sort(degrees);
	    for ( int i = 0 ; i < n ; i++ ) 
		System.out.print(degrees[i] + " ");
	    System.out.println();
	}
	else if (choice.equals("deg-dist")||choice.equals("log-log-deg-dist")) {
	    int[] degree = new int[n];
	    short[] degree_sequence = new short[totalDegree];
	    int max_degree = 0;
	    
	    // initialisations (initially every item has degree zero)
	    for ( int i = 0 ; i < totalDegree ; i++ )  { 
		if ( i < n ) degree[i] = 0;
		degree_sequence[i] = (i==0 ? (short) n : 0);
	    }
	    
	    for ( int i = 0 ; i < E.size() ; i++ ) 
		// scan each element of a transaction
		for ( int j = 0 ; j < E.get(i).length ; j++ ) {
		    // increase its degree
		    degree[E.get(i)[j]]++;
		    // retrieve the maximum degree
		    if (degree[E.get(i)[j]]>max_degree) 
			max_degree = degree[E.get(i)[j]];
		    // modify the degree sequence
		    degree_sequence[degree[E.get(i)[j]]-1]--;
		    degree_sequence[degree[E.get(i)[j]]]++;
		}

	    int tot1 = 0;
	    double tot2 = 0.0;

	    for ( int i = 1 ; i <= max_degree ; i++ ) {
		if ( choice.equals("log-log-deg-dist") && 
		     degree_sequence[i]>0 )
		    System.out.println(Math.log(i) + " " + 
				       Math.log(degree_sequence[i]));
		else if (choice.equals("deg-dist"))
		    System.out.println(i + " " + degree_sequence[i]);

		tot1 += (i*degree_sequence[i]);
		tot2 += (double) degree_sequence[i]/n;
	    }
	}	    
    }
    
}