import choco.Problem;
import choco.mem.StoredInt;
import choco.mem.StoredLong;
import choco.mem.Environment;

//
// 

public class RList {  

    private StoredInt   length;    // the length of the list
    private StoredLong  tot;       // the total/sum of the list
    private RElement    start;     // an element with next pointing to start of list
    private RElement[]  elem;      // elements of the list
    private Environment e;         // whatever that is
    private int n;                 // initial length of list
    private StoredInt[][] adj;     // adjacency matrix, to get solution
    private int[] partition;       // the partition of a number: 0=left, 1=right

    public RList(Problem pb,long[] N) {
	n             = N.length;
	e             = pb.getEnvironment();
	length        = new StoredInt(e,n);
	tot           = new StoredLong(e,0);
	start         = new RElement(e,-1,0,0);
	elem          = new RElement[n + 1];
	adj           = new StoredInt[n][n];
	partition     = new int[n];
	for (int i=0;i<n;i++){
	    elem[i] = new RElement(e,i,N[i],i+1);
	    tot.add(N[i]);
	    for (int j=0;j<n;j++)
		adj[i][j] = new StoredInt(e,0);  // no edge
	    partition[i] = -1;                   // not known
	}
	elem[n] = new RElement(e,n,-999,-1); // the empty element
    }
    //
    // Given an array of numbers N sorted in non-increasing order
    //

    public int length(){return length.get();}                  // length of list
    public long tot(){return tot.get();}                       // sum of values in list
    public RElement first(){return elem[start.getNext()];}     // 1st element
    public RElement second(){return elem[first().getNext()];}  // 2nd element

    public long getDiff(){
	int l          = length();
	long largest   = first().getData();
	long remainder = tot()-largest;
	if (l == 1) return largest;
	else return largest - remainder;
    }

    public String toString(){
	String s = length.get() + " " + tot.get() + "\n";
	RElement x = first();
	while (!x.isEmpty()){
	    s = s + x;
	    x = elem[x.getNext()];
	}
	return s;
    }

    public void insert(RElement x){
	RElement w = start;
	RElement y = first();
	while (y.getData() > x.getData()){
	       w = y;
	       y = elem[y.getNext()];
	    }
	x.setNext(y.getLocn());
	w.setNext(x.getLocn());
    }
    //
    // insert element x into the list in order
    //	    

    public void sum(){
	RElement x = first();
	RElement y = second();
	y.setData(x.getData() + y.getData());
	x.setData(-1);
	start.setNext(y.getLocn());
	length.set(length.get() - 1);
	adj[x.getLocn()][y.getLocn()].set(+1); // set an edge that states sum/same partition
	adj[y.getLocn()][x.getLocn()].set(+1);
    }
    //
    // add the 1st and second elements of the list
    // removing the 1st element
    //

    public void diff(){
	RElement x = first();
	RElement y = second();
	tot.set(tot.get() - 2*y.getData());
	x.setData(x.getData() - y.getData());
	y.setData(-1);
	start.setNext(y.getNext());
	insert(x);
	length.set(length.get() - 1);
	adj[x.getLocn()][y.getLocn()].set(-1); // set an edge that states diff/different partition
	adj[y.getLocn()][x.getLocn()].set(-1);
    }

    private void dfs(int i){
	for (int j=0;j<n;j++)
	    if (adj[i][j].get() != 0 && partition[j] == -1){ // adjacent(i,j) & ¬coloured(j)
		if (adj[i][j].get() == -1) // different
		    partition[j] = 1 - partition[i];
		else
		    partition[j] = partition[i];
		dfs(j);
	    }
    }

    public int[] getPartition(){
	partition[0] = 0; 
	dfs(0); 
	return partition;
    }			
	

    public static void main(String[] args) {

	long[] N = {80,72,70,64,57,40,36,22,19,13,11};
	Problem pb = new Problem();
	RList L = new RList(pb,N);
	System.out.println(L);
	pb.worldPush();
	L.sum();
	System.out.println("add " + L);
	pb.worldPush();
	L.diff();
	System.out.println("diff " + L);
	pb.worldPush();
	L.diff();
	System.out.println("diff " + L);
	pb.worldPush();
	L.diff();
	System.out.println("diff " + L);
	pb.worldPop();
	System.out.println("pop " + L);
	pb.worldPop();
	System.out.println("pop " + L);
	pb.worldPop();
	System.out.println("pop " + L);
	pb.worldPop();
	System.out.println("pop " + L);

    }
}