linked

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); // Выводим последний
    }
}