public class PartialSolution {

    int totalNumber;
    int num;        // the number of workers still to be assigned
    int lower;
    int upper;
    int[][] costs; // the cost matrix - the first row contains the id numbers of the tasks
    int csf;        // cost so far
    int currentWorker;  // the worker who has most recently been assigned a task
    int[] assignments;  // the jobs assigned to workers so far in this partial solution
    

    public PartialSolution(int n, int[][] cm, int pc, int cw, int[] as) {
        /*
         * the partial solution is given information about its structure.  It computes its own
         * lower and upper bounds, and has methods that return these values.  If the values are
         * acceptable, the calling method will add this partial solution to the set.
         */
        totalNumber = n;
        num = cm.length - 1 ;   // cm has an extra row
        if (num == 0) System.out.println("##################### Full solution generated");
        costs = cm;
        csf = pc;               
        currentWorker = cw;     
        lower = computeLower();
        upper = computeUpper();
        assignments = as;
        System.out.print("Partial solution assignments : ");
        for (int i = 0; i <= currentWorker; i++) System.out.print(assignments[i] + "\t");
        System.out.print("\tLower = " + lower);
        System.out.println();
    }
    
    boolean isFullSolution() {return num == 0;}
    
    int getLower() {return lower;}
    
    int getUpper() {return upper;}
    
    int computeLower() {
        int l = csf;
        //System.out.println("Dimensions of cost matrix: " + costs.length + " , " + costs[0].length);
        for (int row = 1; row <= num; row++) {
                // find the minimum cost for the worker in row row
                //System.out.println("Locating min cost in row " + row);
                int minc = costs[row][0];
                for (int col = 1; col < num; col++) if (costs[row][col] < minc) minc = costs[row][col];
                l += minc;            
        }
        return l;
    }
    
    int computeUpper() {
        int u = csf;
        for (int row = 1; row <= num; row++) 
            for (int col = 0; col < num; col++)
                u += costs[row][col];
            
        return u;
    }
    
    
    void printChoices() {
        //System.out.println("Optimal solution : ");
        for (int i = 0; i < assignments.length; i++) {
            
            System.out.println("Worker " + i + " is assigned to job " + assignments[i]);
            
        }
        System.out.println("Cost = " + csf);
        System.out.println();
    } // printChoices
    
    int expand(PartialSolutionHeap S, int globalU) {
        int nextWorker = currentWorker+1;
        int[] newAssigs;
        int[][] newCosts = new int[num][num-1];
        
        
        
        for (int j = 0; j < num; j++) { // assign each remaining job to the next worker
            newAssigs = new int[totalNumber];
            for (int i = 0; i < totalNumber; i++) newAssigs[i] = assignments[i];        
            newAssigs[nextWorker] = costs[0][j];
            /*
            int tc = -1;
            for (int c=0; c < num-1; c++) {
                if (c == j) tc += 2;
                else tc += 1;
                newCosts[0][c] = costs[0][tc];                
            }
            
            for (int r = 1; r < num; r++) {
                tc = -1;
                for (int c = 0; c < num-1; c++) {
                    if (c == j) tc += 2;
                    else tc += 1;
                    newCosts[r][c] = costs[r+1][tc];
                }
            }
            */
            
            newCosts = reduceMatrix(costs, 1, j);
            
            PartialSolution p = new PartialSolution(totalNumber, newCosts, csf + costs[1][j], currentWorker+1, newAssigs);
            if (p.getLower() <= globalU) S.insert(p);
            if (p.getUpper() < globalU) {

                globalU = p.getUpper();
                System.out.println("Updating global upper bound to " + globalU);
            }
            
        }
        
        return globalU;
    } // expand

    static int[][] reduceMatrix(int[][] m, int r, int c){
        //returns the matrix with row r and column c removed
        int mrows = m.length;
        int mcols = m[0].length;
        int[][] newM = new int[mrows-1][mcols-1];
        for (int row = 0; row < mrows - 1; row++) {
            int sourcerow;
            if (row < r) sourcerow = row;
            else sourcerow = row+1;
            for (int col = 0; col < mcols - 1; col++) {
                int sourcecol;
                if (col < c) sourcecol = col;
                else sourcecol = col+1;
                // copy the appropriate value into this location of newM
                newM[row][col] = m[sourcerow][sourcecol];
            }
        }
        return newM;
    } //reduceMatrix

} // class