import java.util.Random;


public class QAlgorithm {

    public static int[] tagRN;
    public static int[] tagReaderRN;
    public static int collisions = 0;
    public static int tagsCollided = 0;
    public static boolean allMarked(int[] array) {
        for (int i = 0; i < array.length; i++) {
            if (array[i] != -1)
                return false;
        }
        return true;
    }

    // return all index that has 0 as Reader Random Number
    public static int[] getZeroIndex(int[] array) {
        int size = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] == 0)size++;
        }
        int v[] = new int[size];
        for (int i = 0, q=0; i < array.length; i++) {
            if (array[i] == 0){
                v[q]= i;
                q++;
            }
        }
        return v;
    }

    public static void decrease(int[] array){
        for (int i = 0; i < array.length; i++) {
            array[i]--;
        }
    }

    public static void qAlgorithm(int q, int numberOfTags) {
        Random random = new Random();
        // reader ask the tags to generate two random numbers
        tagRN = new int[numberOfTags];// RN that identify each tag
        tagReaderRN = new int[numberOfTags]; // RN that is used by reader to choose which of them will be chosen

        for (int i = 0; i < numberOfTags; i++) {
            tagRN[i] = random.nextInt(65535); //give all tag a "id" number that wasn't used
            tagReaderRN[i] = random.nextInt(((int) Math.pow(2, q)) - 1);//give all tag a RN 0-(2^q -1)
        }
        while (!allMarked(tagReaderRN)) {
            // now, ask if any tag chose 0 as its second random number
            int v[] = getZeroIndex(tagReaderRN);
            int t = v.length;
            if (t > 1) {
                collisions++;
                tagsCollided+=t;
                for (int i = 0; i < t; i++) {//if more than 1 tag has 0 as RRN, we choose another RRN
                    tagReaderRN[v[i]] = random.nextInt(((int) Math.pow(2, q)) - 1);
                }
            } else if (t == 1) {
                tagReaderRN[v[0]] = -1;//tag is marked as read
            }else{
                decrease(tagReaderRN); //no tag has 0 as ReaderRN
            }
        }
    }

}