bitmask

package bitmask;

public class Set {
    private int start, end;
    private int[] bits;

    public Set(int start, int end){
        // если start > end то переставить местами
        if (start > end){
            this.end = start;
            this.start = end;
        } else {
            this.start = start;
            this.end = end;
        }

        // определение числа в котором будет находиться первый и последний бит
        int startEl = getElementNum(this.start), endEl = getElementNum(this.end);

        // определение длины отрезка от startEl до endEl и выделение такого количества чисел в массиве (endEl-startEl+1)
        bits = new int[endEl-startEl+1];
    }

    public Set(Set B){
        start = B.start;
        end = B.end;
        bits = getarraycopy(B.bits);
    }
    // Закрытый конструктор выделяет память под массив и копирует элементы полученного множества
    private Set(int start, int end, Set set){ // todo добавил
        this.start = start;
        this.end = end;

        // Выделение памяти под массив чисел
        int startEl = getElementNum(this.start), endEl = getElementNum(this.end);
        bits = new int[endEl-startEl+1];

        // смещение элемента где в текущем массиве начинается переданное множество
        int offset = getElementNum(set.start) - startEl;

        // копирование значений из array со сдвигом на offset
        for (int i=0; i<set.bits.length; i++)
            bits[i+offset] = set.bits[i];
    }

    private static int[] getarraycopy(int[] a){ //Метод возвращает копию массива
        int[] out = new int[a.length];

        for (int i=0; i<a.length; i++)
            out[i] = a[i];

        return out;
    }

    private int getElementNum(int x){ // определение номера битового поля в котором будет находиться бит числа х (-64; -33) -> -2 (-32; -1
        if (x>=0) return x/32; //т.к. в каждом числе 32 бита
        return -((-x-1)/32)-1; // Если отрицательный то смещается на 1 в большую сторону
    }

    public int getInMaskPos(int x){
        return (x<0? 32-((-x-1)%32)-1: x%32);
    }

    private boolean isInSet(int x){ // проверка находится ли бит во множестве
        // вычисления номера первого числа в массиве getElementNum(start)
        // вычисление индекса числа в массиве где должен находиться х getElementNum(x) - getElementNum(start)
        return isInMask(getElementNum(x) - getElementNum(start), getInMaskPos(x)); // отбрасываем минус у отрицательного числа
    }

    private boolean isInMask(int ind, int x){ // метод проверяет является ли бит на х месте единицей в элементе ind массива
        // побитовое и числа из массива с 1 << (31-x%32) смещаем 1 на n=x%32 бит справа
        return (bits[ind] & (1 << (31-x))) != 0;
        // если число не ноль то x есть в множестве.
    }

    public boolean isCrossing(Set B){ // Доп метод проверяет пересекаются множества или нет
        if (start > B.end || B.start > end) // случай когда она не пересекаются по границам они либо пустые, тогда не пересекаются либо не пустые и тогда не пересекаются
            return false;

        if (B == this) {
            return true; // Если ссылки одинаковые то пересекаются
        }

        //Нахождение позиций начала и конца каждого из множеств
        int AStartEl = getElementNum(start), BStartEl = getElementNum(B.start), AEndEl = getElementNum(end), BEndEl = getElementNum(B.end);

        // определение числа в котором будет находиться первый и последний бит
        int startP = (AStartEl > BStartEl)? AStartEl: BStartEl; // Максимальная позиция начала
        int endP = (AEndEl < BEndEl)? AEndEl: BEndEl; // Минимальная позиция конца

        for (int p = startP; p<=endP; p++) // Проход по числам пересечения и их побитовое И
            if ((bits[p - AStartEl] & B.bits[p - BStartEl]) != 0) return true; // если побитовое И не нулевое то есть перечесение вернуть истину

        return false; // если дошли до конца вернуть ложь
    }

    private Set union(Set B){ // Закрытый метод выполняет объединение todo сделать на копировании первого и добавление второго

        int startRES = (start < B.start)? start: B.start; // Старт результирующего множества
        int endRES = (end > B.end)? end: B.end; // Конец результирующего множества

        // Создание копии первого множества с объединёнными границами и копией значений текущего массива со сдвигом
        Set RES = new Set(startRES, endRES, this);

        //Нахождение позиций начала и конца второго множества
        int BStartEl = getElementNum(B.start), BEndEl = getElementNum(B.end);
        int RESStartEl = getElementNum(startRES); // Позиция начала результирующего множества

        // Добавление в множество элементов второго множества на нужные места
        for (int el = BStartEl; el <= BEndEl; el++)
            RES.bits[el - RESStartEl] |= B.bits[el - BStartEl];

        return RES;
    }

    public Set UNION(Set B){
        // если один из них пустой или указатели совпадают то вернуть копию текущего или другого
        if (B == null || B == this) return new Set(this);
        // вызываем union
        return union(B);
    }

    public Set INTERSECTION(Set B) {
        if (B == this) return new Set(this); // Если это одни и те же указатели
        //проверка пересекаются ли множества если нет или B пустое вернуть пустую копию текущего множества
        if (B == null || !isCrossing(B)) return new Set(start, end);
        //A и B Ссылки на множества, если надо, переставить так чтобы A.start <= B.start
        Set A = this;
        if (A.start>B.start){ // если второе начинается раньше, перетсавляем
            A=B; B=this;
        }
        //создание нового множества с пересечением границ RES = new Set(...)
        Set RES = new Set(B.start, A.end);

        //Нахождение позиций нулей и концов каждого из множеств --> AStartEl BStartEl AEndEl BEndEl
        int AStartEl = getElementNum(A.start), BStartEl = getElementNum(B.start), AEndEl = getElementNum(A.end), BEndEl = getElementNum(B.end);
        int endP = (AEndEl < BEndEl)? AEndEl: BEndEl; // Минимальная позиция конца

        // Применяем побитовое и для чисел на позициях начиная с BStartEl заканчивая BEndEl
        for (int pos = BStartEl; pos <= endP; pos++)
            RES.bits[pos - BStartEl] = A.bits[pos-AStartEl] & B.bits[pos-BStartEl];

        return RES;
    }

    public Set DIFFERENCE(Set B){
        if (B == this) return new Set(start, end); // Если это одни и те же указатели то будет пустое множество с теми же границами
        //Если B пустое вернуть копию текущего множества
        if (B == null) return new Set(this);

        Set RES = new Set(this); // Формируем множество на основе текущего

        //Нахождение позиций начала и конца каждого из множеств
        int AStartEl = getElementNum(start), BStartEl = getElementNum(B.start), AEndEl = getElementNum(end), BEndEl = getElementNum(B.end);

        // определение позиций начала и конца пересечений
        int startP = (AStartEl > BStartEl)? AStartEl: BStartEl; // Максимальная позиция начала
        int endP = (AEndEl < BEndEl)? AEndEl: BEndEl; // Минимальная позиция конца


        for (int p = startP; p<=endP; p++) // Проход по числам пересечения и их побитовое вычитание Если границы не пересекаются то ничего не будет
            RES.bits[p - AStartEl] &= ~B.bits[p - BStartEl];

        return RES;
    }

    public Set MERGE(Set B){
        // если один из них пустой или указатели совпадают то вернуть копию текущего или другого
        if (B == null || B == this) return new Set(this);
        // вызываем union
        return union(B);
    }

    public boolean MEMBER(int x){ // Метод проверяет наличие
        // если х не находится в области определения вернуть ложь
        if (start>x || x>end) return false;
        // вызвать isInSet
        return isInSet(x);
    }

    public void MAKENULL(){
        // проход по массиву и зануление всех чисел
        for (int i=0; i<bits.length; i++)
            bits[i]=0;
    }

    public void INSERT(int x){
        //проверка что х в границах
        if (start>x || x>end) return;
        //Вычислить offset номер первого элемента массива вычислить в каком числе будет х
        int AStartEl = getElementNum(start), xEl = getElementNum(x);
        //побитовое или элемента массива[xEl-AStartEl] и 1 << (31-x%32)
        bits[xEl-AStartEl] |= 1 << (31-x%32);

    }

    public void DELETE(int x){
        //проверка что х в границах
        if (start>x || x>end) return;
        //Вычислить offset номер первого элемента массива вычислить в каком числе будет х
        int AStartEl = getElementNum(start), xEl = getElementNum(x);
        //побитовое и элемента массива[xEl-AStartEl] c -(1 << (31-x%32))
        bits[xEl-AStartEl] &= ~(1 << (31-x%32));
    }

    public void ASSIGN(Set B){
        // проверить ссылки различные
        if (this == B) return;
        // заменить границы
        start = B.start; end = B.end;
        // если массивы одной длинны то просто скопировать
        if (bits.length == B.bits.length)
            for (int i=0; i<bits.length; i++)
                bits[i] = B.bits[i];
        else
            // иначе создать новый массив
            bits = getarraycopy(B.bits);
    }

    public int MIN(){ // возвращает минимальный элемент содержащийся во множестве
        // пока элемент массива нулевой, дальше
        int i=0;
        while (i < bits.length && bits[i] == 0)
            i++;

        // Если прошли весь массив то в массиве нет элементов и выводим end+1
        if (i == bits.length) throw new SetException("Множество пустое, нет минимального элемента");

        int x=(i==0? getInMaskPos(start): 0);// если первый элемент ненулевой то начинаем проверку с start%32 бита
        int lastbit = (i+1==bits.length? getInMaskPos(end): 31); // если в последнем числе массива то идём до end


        // идём по битам пока они нулевые (число при этом точно не нулевое)
        while (!isInMask(i,x))
            x++;


        return (getElementNum(start)+i)*32+x; // вернуть хранимое число
    }
    public int MAX() { // аналогично MIN но с обратной стороны
        // пока элемент массива нулевой, дальше
        int i=bits.length-1;
        while (i >= 0 && bits[i] == 0)
            i--;

        // Если прошли весь массив то в массиве нет элементов и выводим start-1
        if (i == -1) throw new SetException("Множество пустое, нет максимального элемента");

        int firstbit=(i==0? getInMaskPos(start): 0);// если первый элемент ненулевой то начинаем проверку до start%32 бита
        int x = (i+1==bits.length? getInMaskPos(end): 31); // если в последнем числе массива то идём до end


        // идём по битам пока не дошли до конца и они нулевые
        while (x >= firstbit && !isInMask(i,x))
            x--;

        return (getElementNum(start)+i)*32+x; // вернуть хранимое число
    }

    public boolean EQUAL(Set B) {// Если границы разные но элементы совпадают то всё равно true
        if (this == B) return true; // Если ссылка на одно и то же множество

        //A и B Ссылки на множества, если надо, переставить так чтобы A.start <= B.start
        Set A = this;
        if (A.start>B.start){
            A=B; B=this;
        }

        //Нахождение позиций начала и конца каждого из множеств
        int AStartEl = getElementNum(A.start), BStartEl = getElementNum(B.start), AEndEl = getElementNum(A.end), BEndEl = getElementNum(B.end);
        int Aind = AStartEl, Bind = BStartEl; //индексы для прохода массивах множеств А и В

        //1) Все ли элементы до пересечения нулевые
        while (Aind < AEndEl && Aind != Bind)
            if (bits[Aind++ - AStartEl] != 0)
                return false;

        //2) Проверка все ли элементы пересечения совпадают, если нашли несовпадение false
        if (Aind == Bind) // Есть пересечение
            while (Aind < AEndEl && Bind < BEndEl) // Пока один из массивов не закончится
                if (A.bits[Aind++ - AStartEl] != B.bits[Bind++ - BStartEl])
                    return false;

        //3) Проверка оставшегося хвоста на пустоту
        while (Aind <= AEndEl)//то конец первого множества остался
            if (bits[Aind++ - AStartEl] != 0)
                return false;
        while (Bind <= BEndEl) // конец второго множества остался
            if (bits[Bind++ - BStartEl] != 0)
                return false;

        return true;

    }
    public Set FIND(Set B, int x){ // ВСЁ НОРМАЛЬНО ТУТ
        // Проверяем на каждом множестве если оно содержит х
        if (start<x && x<end && isInSet(x))
            return this;
        else if (B.start<x && x<B.end && B.isInSet(x))
            return B;

        return null; // Если ни в одном множестве нет этого элемента

    }

    public void PRINT(){

        for (int i=start; i<=end; i++) // Проход по всем возможным элементам множестве с проверкой есть ли они в нём
            if (isInSet(i)) System.out.printf("%d ", i);
        System.out.println();
    }

    public void DEBUG_PRINT(){
        StringBuilder out = new StringBuilder(bits.length*33);
        for (int i=0; i< bits.length; i++) {

            for (int j=0; j<32; j++) {
                if ((bits[i] & 1<<(31-j)) == 0)
                    out.append('0');
                else
                    out.append('1');

            }
            out.append(' ');
        }
        System.out.println(out);
    }

}