public class PartialSolution {

    int totalNumber;
    int num;        // the number of users still to be assigned
    int lower;
    int upper;
    int[][] friends; // the friends
    int csf;        // cost so far
    int currentUser;  // the user most recently decided aout it, either yes or no
    boolean[] choices;  // the choices that have been made in this partial solution
    boolean[] dominated;  // which vertices are currently dominated (including self-domination)
    int numDominated;
    

    public PartialSolution(int n, int[][] f, boolean[] ch, boolean[] dom, int pc, int cu) {
        /*
         * called with PartialSolution p = new PartialSolution(numOfUsers, friends, chosen, dominated, csf, mostrecentperson);
            
        
         * 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;
        
        friends = f;
        choices = ch;
        dominated = dom;
        numDominated = 0;
        for (int i = 0; i < totalNumber; i++) if (dominated[i]) numDominated++;
        //if (numDominated == totalNumber) System.out.println("##################### Full solution generated");
        csf = pc;        
        currentUser = cu;     
        lower = computeLower();
        upper = computeUpper();
        System.out.print("Partial solution created with choices : ");
        for (int i = 0; i <= currentUser; i++) 
            if (choices[i]) System.out.print(i + " yes\t");
            else System.out.print(i + " no\t");
        System.out.print("\tLower = " + lower);
        System.out.print("\tUpper = " + upper);
        System.out.println();
    }
    
    boolean isFullSolution() {return currentUser == totalNumber - 1;}
    
    int getLower() {return lower;}
    
    int getUpper() {return upper;}
    
    int computeLower() {
        int l = csf;
        // if there is any vertex already skipped over that cannot be dominated, the solution is infeasible
        boolean feasible = true;
        boolean canStillBeDominated = false;
        for (int i = 0; i <= currentUser; i++) {
            canStillBeDominated = true;
            if (!dominated[i]) {
                canStillBeDominated = false;
                for (int j = currentUser+1; j < totalNumber; j++) if (friends[i][j] == 1) canStillBeDominated = true;
            }
            if (!canStillBeDominated) feasible = false;
        }
        if (!feasible) {
            //System.out.println("computeLower - rejecting infeasible solution");
            return totalNumber + 1;  // this assures the partial solution will be rejected
        }
        
        // if there are any vertices not yet dominated, we will need at least one more vertex in the set (yes it is lame)
        boolean needMore = false;
        for (int i = 0; i < totalNumber; i++) if (!dominated[i]) needMore = true;
        if (needMore) l++;
        return l;
    }
    
    int computeUpper() {
        int u = csf;
        // choose more vertices until everything is dominated
        int domCount = 0;
        for (int i = 0; i < totalNumber; i++) if (dominated[i]) domCount++;
        boolean[] tempDom = new boolean[totalNumber];
        for (int i = 0; i < totalNumber; i++) tempDom[i] = dominated[i];
        int nextUser = currentUser;
        while ((domCount < totalNumber) && (nextUser < totalNumber-1)) {
            nextUser++;
            if (!tempDom[nextUser]) {
                tempDom[nextUser] = true;
                domCount++;
            }
            u++;
            for (int i = 0; i < totalNumber; i++) 
                if ((friends[nextUser][i] == 1) && (!tempDom[i])) {
                    tempDom[i] = true;
                    domCount++;
                }
        }
        if (domCount != totalNumber) {
            u = totalNumber + 1;       // no possible solution from this partial solution
            //System.out.println("computeUpper detects infeasible partial solution");
        }
        return u;
    }
    
    
    void printChoices() {
        
        for (int i = 0; i <= currentUser; i++) {
            if (choices[i]) System.out.println("User " + i + " is chosen to spy");
            
        }
        System.out.println("Cost = " + csf);
        System.out.println();
    } // printChoices
    
    int expand(PartialSolutionHeap S, int globalU) {
        int nextUser = currentUser+1;
        if (nextUser < totalNumber) {
            boolean[] newChoices;
            boolean[] newDominated;
        
            // choose the next user
            newChoices = new boolean[totalNumber];
            newDominated = new boolean[totalNumber];
            for (int i = 0; i < totalNumber; i++) {
                newChoices[i] = choices[i];
                newDominated[i] = dominated[i];
            }
            newChoices[nextUser] = true;
            newDominated[nextUser] = true;
            for (int i = 0; i < totalNumber; i++) newDominated[i] = newDominated[i] || (friends[nextUser][i] == 1);
            
            PartialSolution p = new PartialSolution(totalNumber, friends, newChoices, newDominated, csf + 1, nextUser);
            if (p.getLower() <= globalU) S.insert(p);
            if (p.getUpper() < globalU) {
                globalU = p.getUpper();
                System.out.println("Updating global upper bound to " + globalU);
            }
            
            // or don't ...
            
            newChoices = new boolean[totalNumber];
            newDominated = new boolean[totalNumber];
            for (int i = 0; i < totalNumber; i++) {
                newChoices[i] = choices[i];
                newDominated[i] = dominated[i];
            }
            p = new PartialSolution(totalNumber, friends, newChoices, newDominated, csf, nextUser);
            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

    

} // class