/////////////////////////////////////////////////////////////////
//  CS 3711 (Fall 2005), Assignment #4, Question #1            //
//  Program File Name: InstanceSC.java                         //
//       Student Name: Todd Wareham                            //
//         Login Name: harold                                  //
//              MUN #: 8008765                                 //
/////////////////////////////////////////////////////////////////


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



/*
 *  Class InstanceSC
 *   Stores variables associated with an instance of the minimum
 *    set-cover problem.
 *
 *      set	Set of subsets over the item-set
 *
 *   Note that the item-set I is assumed to be the integers
 *    {1, 2, ..., numItems}, where numItems is the length of each
 *    set-array in SET.
 */

class InstanceSC {

    private static Random rand = new Random();

    private boolean[][] set;


/*
 *  Construct a random minimum set-cover instance consisting of M 
 *   subsets over a set of N items, where each subset has between 
 *   1 and N/2 items. Note that this instance is not gauranteed to
 *   contain a set cover.
 */

    public InstanceSC(int n, int m) {
	int i, j, cpos, maxs, curs;

	set = new boolean[m][0];
	for (i = 0; i < m; i++) {
	    set[i] = new boolean[n];
	    for (j = 0; j < n; j++)
		set[i][j] = false;
	}

	maxs = n / 2;
	for (i = 0; i < m; i++) {
	    curs = (Math.abs(rand.nextInt()) % maxs) + 1;
	    for (j = 0; j < curs; j++) {
	        cpos = Math.abs(rand.nextInt()) % n;
	        set[i][cpos] = true;
	    }
	}

    }  // End of InstanceSC constructor


    public int numSets(){
        return(set.length);
    }  // End of method numSets


    public int numItems(){
        return(set[0].length);
    }  // End of method numItems


    public boolean ItemInSet(int i, int s){
        return(set[s][i]);
    }  // End of method numItems


}  // End of class InstanceSC