Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package linkedlist;
- public class Set {
- private Item tail;
- private int start, end;
- private class Item{ // Элемент списка
- private int val; // Храним число множества
- private Item next; // Указатель на следующий
- private Item(int val){
- this.val = val;
- }
- private Item(int val, Item next){
- this.val = val;
- this.next = next;
- }
- private Item(Item B){
- val = B.val;
- }
- private void insertAfter(Item B){ // Метод вставляет элемент после текущего
- B.next = next;
- next = B;
- }
- private void deleteAfter(){
- next = next.next;
- }
- @Override
- public String toString() {
- return String.valueOf(val);
- }
- }
- public Set(int start, int end) {
- this.start = start;
- this.end = end;
- }
- public Set(Set A){ // Копирующий конструктор
- start = A.start;
- end = A.end;
- tail = copylist(A.tail);
- }
- private Set(int start, int end, Set B){
- this.start = start;
- this.end = end;
- this.tail = copylist(B.tail);
- }
- // TODO в ASSIGN нужен
- private Item copylist(Item reftail){ // Метод формирует копию входного кольцевого списка и возвращает хвост
- Item newtail = new Item(reftail);
- newtail.next = newtail;
- // Проходом по кольцевому списку копируем
- Item fir = newtail, sec = reftail.next; // Указатели по текущему и образцу
- while (sec != reftail){ // Проход пока не дойдём до хвоста
- fir.insertAfter(new Item(sec));
- fir = fir.next;
- sec = sec.next;
- }
- return newtail;
- }
- private boolean isInSet(int x){ // Проверка находится ли элемент в множестве если оно состоит из более чем 1го элемента
- if (tail.val == x) return true; // Если элемент в хвосте
- Item prev = findPrevItem(tail, x); // Иначе ищем предыдущий
- // Если следующий элемент и есть искомое число то оно содержится в множестве
- return prev.next.val == x;
- }
- private Item findPrevItem(Item start, int x){ // Поиск элемента перед потенциальным местом x если он точно идёт до хвоста посик начинается с заданного элемента
- Item fir = start, sec = start.next; // Указатели по текущему и образцу
- while (sec.val < x){ // Пока мы не дойдём до хвоста либо до элемента значение которого больше или равно искомому
- if (sec == tail) break;
- fir = fir.next;
- sec = sec.next;
- }
- return fir; // Если дошли до хвоста, то будет возвращён предпоследний
- }
- public boolean isCrossing(Set B) { // Доп метод проверяет пересекаются множества или нет
- if (start > B.end || B.start > end) // случай когда она не пересекаются по границам они либо пустые, тогда не пересекаются либо не пустые и тогда не пересекаются
- return false;
- if (B==this) // Если указатели совпадают то множества пересекаются
- return true;
- Item a = tail.next, b = B.tail.next;// проход с головы каждого
- //пока не дойдём до конца хоть одного из списков если нашли совпадающие return true
- while (a != tail && b != B.tail){
- if (a.val == b.val) return true;
- // Двигаем указатель с минимальным числом
- if (a.val < b.val)
- a = a.next;
- else
- b = b.next;
- }
- if (a == tail){ // Если дошли до хвоста в первом списке
- while (b != B.tail){ // Проверяем остаток второго списка на наличие в нём хвоста первого
- if (a.val == b.val) return true;
- b = b.next;
- }
- // Сравниваем хвосты
- if (a.val == b.val) return true;
- } else { // Дошли до хвоста во втором списке
- while (a != tail){ // Проверяем остаток первого списка на наличие в нём хвоста второго
- if (a.val == b.val) return true;
- a = a.next;
- }
- // Сравниваем хвосты
- if (a.val == b.val) return true;
- }
- return false;
- }
- private Set union(Set B) { // TODO либо делать на основе копии либо разруливать первые
- /*// Создать пустой список с временным хвостом
- Item restail = new Item(0);
- restail.next = restail;
- Item r = restail; // указатель r по новому списку
- // Результирующие границы итогового множества
- int resStart = (start < B.start ? start : B.start);
- int resEnd = (end>B.end ? end : B.end);
- Item a = tail.next, b = B.tail.next; // Указатели для прохода по спискам
- while (a != tail && b != B.tail) {
- if (a.val == b.val) { // если значения совпадают, добавляем в результат и идём дальше в обоих
- r.insertAfter(new Item(a));
- a = a.next;
- b = b.next;
- } else if (a.val < b.val) { // если в А число меньше, добавляем его в результат и идём дальше в первом
- r.insertAfter(new Item(a));
- a = a.next;
- } else { // иначе добавляем второе и идём дальше во втором
- r.insertAfter(new Item(b));
- b = b.next;
- }
- r = r.next;
- }
- r = unionTail(r, a, b, B.tail); // Вызвать метод который объединит хвост и последний элемент, вернёт указатель в списке резулоьтате
- r.next = restail.next; // Отвязываем временный хвост
- return new Set(resStart, resEnd, r);
- */
- // Результирующие границы итогового множества
- int resStart = (start < B.start ? start : B.start);
- int resEnd = (end>B.end ? end : B.end);
- Set RES = new Set(resStart, resEnd, this); // Копия первого множества с объединёнными границами
- Item b = B.tail.next, prev = RES.tail; // Указатели на элементы второго множества и поиска по результату
- while (b!= B.tail && b.val < RES.tail.val){ // Проход по всем элементам множества B которые меньше хвоста A
- prev = findPrevItem(prev, b.val); // Ищем элемент в результирующем множестве перед потенциальным местом вставки
- if (prev.next.val != b.val) // Если такого элемента нет, вставляем
- prev.insertAfter(new Item(b));
- b = b.next; // Идём дальше во втором
- prev = prev.next; // Следующий поиск начнём с вставленного или существующего элемента
- }
- unionTail(RES, prev, b, B.tail);// Вызываем метод объединения хвостов множеств
- return RES;
- }
- // Метод завершает объединение множеств, вызывается в случае когда в одном из множеств дошли до хвоста
- // Модифицирует результирующее множество
- private void unionTail(Set RES, Item prev, Item b, Item tailB){
- /*if (a == tail && b == tailB) { // Если дошли до хвостов в обоих множествах, вставляем в порядке возрастания
- if (a.val < b.val) {
- r.insertAfter(new Item(a));
- r = r.next;
- r.insertAfter(new Item(b));
- } else if (a.val > b.val) {
- r.insertAfter(new Item(b));
- r = r.next;
- r.insertAfter(new Item(a));
- } else { // Если равны
- r.insertAfter(new Item(a));
- }
- r = r.next;
- return r;
- }
- // Переставляем указатели так чтобы дошли до конца в первом
- Item secTail = tailB, temp;
- if (b == tailB) {
- temp = a;
- a = b;
- b = temp;
- secTail = tail;
- }
- while (b != secTail && b.val < a.val){ // доходим до неменьшего элемента второго списка (или конца)
- r.insertAfter(new Item(b));
- r = r.next;
- b = b.next;
- }
- r.insertAfter(new Item(a)); // Вставляем хвост первого списка
- r = r.next;
- if (a.val == b.val) // если во втором списке элемент равен хвосту первого, пропускаем его
- b = b.next;
- while (b != secTail){ // проходим до конца второго списка и вставляем
- r.insertAfter(new Item(b));
- r = r.next;
- b = b.next;
- }
- r.insertAfter(new Item(b)); // Вставляем хвост второго списка
- r = r.next;
- return r;
- */
- // Если дошли до обоих хвостов
- if (b == tailB && prev.next == RES.tail){
- if (b.val < RES.tail.val){
- prev.insertAfter(new Item(b));
- } else if (b.val > RES.tail.val) {
- RES.tail.insertAfter(new Item(b));
- RES.tail = RES.tail.next;
- }
- return;
- }
- // Если дошли до конца второго, но не до хвоста первого
- if (b == tailB){
- if (prev.next.val != b.val) // Если хвоста второго нет в первом, добавляем
- prev.insertAfter(new Item(b));
- return;
- }
- // Если не дошли до хвоста второго но прошли хвост первого
- if (b.val == RES.tail.val) //Если элемент второго равен хвосту первого, пропускаем его
- b = b.next;
- while (b != tailB) { // Добавляем после хвоста
- RES.tail.insertAfter(new Item(b));
- RES.tail = RES.tail.next; // Двигаем хвост
- b = b.next;
- }
- RES.tail.insertAfter(new Item(b)); // Вставляем хвост второго множества в конец
- RES.tail = RES.tail.next; // Двигаем хвост
- }
- public Set UNION(Set B) {
- // если один из них пустой или указатели совпадают то вернуть копию текущего или другого
- if (B == null || B.tail == null || B == this) return new Set(this);
- if (tail == null) return new Set(B);
- // вызываем union
- return union(B);
- }
- public Set INTERSECTION(Set B) { // при удалении проверять хвост ли это
- if (B == this) return new Set(this); // если указатели совпадают то вернуть копию текущего
- if (B == null || B.tail == null || tail == null) return new Set(start, end); // если хоть один пустой вернуть пустую копию текущего
- // Результирующие границы итогового множества
- int resStart = (start < B.start ? start : B.start);
- int resEnd = (end>B.end ? end : B.end);
- // Создать пустое множество
- Set RES = new Set(resStart, resEnd);
- Item a = tail.next, b = B.tail.next; // Указатели для прохода по спискам
- while (a != tail && b != B.tail && a.val != b.val){ // Ищем первое пересечение
- if (a.val < b.val){ // если в А число меньше идём дальше в первом
- a = a.next;
- } else
- b = b.next; // иначе идём дальше во втором
- }
- if (a == tail || b == B.tail) {
- if (a.val == b.val) {
- RES.tail = new Item(a); // Вставляем первый элемент
- RES.tail.next = RES.tail;
- } return RES;
- }
- RES.tail = new Item(a); // Вставляем первый элемент
- RES.tail.next = RES.tail; //
- a=a.next;
- b=b.next;
- Item r = RES.tail;
- while (a != tail && b != B.tail){ // Вставка пока не дошли до одного из хвостов
- if (a.val == b.val){
- r.insertAfter(new Item(a));
- r = r.next;
- a=a.next;
- b=b.next;
- }
- if (a.val < b.val){ // если в А число меньше идём дальше в первом
- a = a.next;
- } else
- b = b.next; // иначе идём дальше во втором
- }
- if (a == tail && b == B.tail) { // Если дошли до хвостов в обоих множествах, вставляем если совпадают
- if (a.val == b.val) {
- r.insertAfter(new Item(a));
- r = r.next;
- }
- RES.tail = r; // Переставляем хвост в конец
- return RES;
- }
- // Переставляем указатели так чтобы дошли до конца в первом
- Item secTail = B.tail, temp;
- if (b == B.tail) {
- temp = a;
- a = b;
- b = temp;
- secTail = tail;
- }
- while (b != secTail && b.val < a.val) // доходим до неменьшего элемента второго списка (или конца)
- b = b.next;
- if (a.val == b.val) { // если во втором списке элемент равен хвосту второго, вставляем
- r.insertAfter(new Item(b));
- r = r.next;
- }
- RES.tail = r; // Переставляем хвост в конец
- return RES;
- }
- public Set DIFFERENCE(Set B){
- if (B == null || B.tail == null) return new Set(this); // если второй пустой вернуть копию текущего
- if (B == this || tail == null) return new Set(start, end); // если указатели совпадают то вернуть пустую копию текущего
- Item a = tail.next; // Указатели для прохода по спискам
- Item Bprev = findPrevItem(B.tail, a.val); // Первый неменьший элемент второго
- if (Bprev.next == B.tail && Bprev.next.val != a.val) // Если во втором todo хвост второго в первом
- return new Set(this);
- Item b = Bprev.next;
- // Создать пустое множество
- Set RES = new Set(start, end);
- while (a.val == b.val && a != tail && b != B.tail){ // Ищем первое непересечение
- a = a.next;
- Bprev = findPrevItem(b, a.val); // Доходим до неменьшего во втором
- b = Bprev.next; // Сдвигаем во втором до найденного
- }
- if (a == tail || b == B.tail) { // Если дошли до конца одного из списков
- if (a.val != b.val) { // Если они элементы не совпадают
- RES.tail = new Item(a); // Вставляем первый элемент
- RES.tail.next = RES.tail;
- } return RES; // Возвращаем либо пустой, либо с одним элементом
- }
- RES.tail = new Item(a); // Вставляем первый элемент
- RES.tail.next = RES.tail; //
- a=a.next;
- Bprev = findPrevItem(b, a.val); // Доходим до неменьшего во втором
- b = Bprev.next; // Сдвигаем во втором до найденного
- Item r = RES.tail;
- while (a != tail && b != B.tail){
- if (a.val == b.val){ // если значения совпадают, идём дальше
- a = a.next;
- Bprev = findPrevItem(b, a.val); // Доходим до неменьшего во втором
- b = Bprev.next; // Сдвигаем во втором до найденного
- }
- else { // Иначе добавляем элемент первого
- r.insertAfter(new Item(a));
- a = a.next;
- r = r.next;
- }
- }
- // Дошли до конца в первом списке (если оба дошли до хвоста то тоже работает)
- if (a == tail){
- if (a.val != b.val){ // если хвост первого списка не находится во втором добавляем его
- r.insertAfter(new Item(a));
- r = r.next;
- }
- } else { // Иначе дошли до конца во втором списке
- while (a != tail) { // Копируем хвост первого списка в результат
- if (b.val != a.val) { // Если хвост второго списка не совпадает с элементом то добавляем этот элемент
- r.insertAfter(new Item(a));
- r = r.next;
- }
- a = a.next; // двигаемся дальше в списке
- }
- r.insertAfter(new Item(a)); // Вставка хвоста первого
- r = r.next;
- }
- RES.tail = r; // Перемещаем хвост в конец
- return RES;
- }
- public Set MERGE(Set B){
- // если один из них пустой или указатели совпадают то вернуть копию текущего или другого
- if (B == null || B.tail == null || B == this) return new Set(this);
- // вызываем union
- return union(B);
- }
- public boolean MEMBER(int x){
- // проверка лежит ли х в промежутке
- if (x < start || x > end) return false;
- // вызвать проверку
- return isInSet(x);
- }
- public void MAKENULL(){
- tail = null;
- }
- public void INSERT(int x){
- //проверка что х в границах
- if (x < start || x > end) return;
- //вставка если список пустой
- if (tail == null) {
- tail = new Item(x);
- tail.next = tail;
- return;
- }
- // Если вставка перед головой
- if (tail.next.val > x)
- tail.insertAfter(new Item(x));
- // если элемент вставляется после хвоста
- if (tail.val < x){
- tail.insertAfter(new Item(x));
- tail = tail.next; // Двигаем хвост
- }
- //найти элемент предыдущий потенциальному местонахождению искомого
- Item prev = findPrevItem(tail, x);
- //если искомого элемента нет, вставляем
- if (prev.next.val != x) prev.insertAfter(new Item(x));
- //иначе ничего не делаем
- }
- public void DELETE(int x){
- // проверка что х в границах
- if (x < start || x > end) return;
- // Если искомый элемент должен быть после хвоста или до головы то его нет в списке
- if (tail.val < x || tail.next.val > x) return;
- // если удаляем хвост
- if (tail.val == x){
- if (tail.next == tail) tail = null; // Был один элемент
- else{
- Item prev = findPrevItem(tail, x);
- tail = prev; // Двигаем хвост назад
- prev.deleteAfter();
- }
- return;
- }
- //найти элемент предыдущий потенциальному местонахождению искомого
- Item prev = findPrevItem(tail, x);
- // Если после найденного есть такой элемент
- if (prev.next.val == x) prev.deleteAfter();
- // Иначе ничего не делаем
- }
- public void ASSIGN(Set A){
- // если один и тот же объект или дан пустой
- if (A == null || A == this) return;
- // Скопировать границы
- start = A.start;
- end = A.end;
- // Скопировать элементы
- tail = copylist(A.tail);
- }
- public int MIN(){
- if (tail == null) throw new SetException("Множество пустое, нет минимального элемента"); // Если список пустой
- return tail.next.val; // Иначе смотрим в голову
- }
- public int MAX(){
- if (tail == null) throw new SetException("Множество пустое, нет максимального элемента"); // Если список пустой
- return tail.val; // Иначе смотрим в хвост
- }
- public boolean EQUAL(Set B) {// Если границы разные но элементы совпадают то всё равно true
- if (tail.val != B.tail.val) return false; // Если в хвостах различные элементы
- // a, b указатели прохода по спискам
- Item a = tail.next, b = B.tail.next;
- //пока не дойдём до конца хоть одного из списков проверяем что все равны
- while (a != tail && b != B.tail){
- if (a.val != b.val) return false;
- a = a.next;
- b = b.next;
- }
- //если после прохода хоть один из указателей не дошёл до хвоста или они разные вернуть ложь
- if (!(a == tail && b == tail))
- return false;
- return true;
- }
- public Set FIND(Set B, int x){
- // если множества пересекаются бросить исключение
- if (isCrossing(B)) return null;
- // Проверяем на каждом множестве если оно содержит х
- 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(){
- if (tail == null) return;
- // Проходом по кольцевому списку выводим
- for (Item fir = tail.next; fir != tail; fir = fir.next)
- System.out.printf("%d ", fir.val);
- System.out.println(tail.val); // Выводим последний
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement