Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement