package ru.vsu.cs.solution;

import java.util.ArrayList;
import java.util.List;

import static java.lang.Long.compare;

public class MyList {


private MyListItem<Integer> head = null;
private MyListItem<Integer> tail = null;
private int count = 0;

public static MyList<java.lang.Integer> convertLinkedListToArray(int[] arr) throws Exception {
    MyList<java.lang.Integer> list = new MyList<>();
    for (int i = 0; i < arr.length; i++) {
        list.add(arr[i]);
    }
    return list;
}

private static int myComparator(int a, int b) {
    return compare(a, b);
}

public void del() {
    if (head == null || head.next == head) {
        return;
    }
    while ((int) head.value % 2 == 0 && (int) head.next.value % 2 == 0) {
        removeFirst();
        if (head == null) {
            return;
        }
    }
    MyListItem<Integer> curr = head;
    MyListItem<Integer> next = head.next;
    int del = 0;
    while (curr.next != head) {
        if ((int) curr.next.value % 2 == 0) {
            if (del == 0) {
                next = curr;
            }
            del += 1;
            curr = curr.next;
        } else if ((int) curr.next.value % 2 == 1) {
            if (del > 1) {
                next.next = curr;
                count -= del;
            }
            curr = curr.next;
        }
        if (del > 1) {
            next.next = curr;
            count -= del;
        }
    }
    tail = curr;
}

public int[] convert() {
    return convertLinkedListToArray();
}

private int[] convertLinkedListToArray() {
    List<java.lang.Integer> list = new ArrayList<>();
    if (head == null) return new int[]{};

    MyListItem<Integer> current = head;
    do {
        list.add((java.lang.Integer) current.value);
        current = current.next;
    } while (current != head);

    int[] array = new int[list.size()];
    for (int i = 0; i < list.size(); i++) {
        array[i] = list.get(i);
    }
    return array;
}

private void checkEmpty() throws Exception {
    if (isEmpty()) {
        throw new Exception("List is empty");
    }
}

public Integer getFirst() throws Exception {
    checkEmpty();
    return head.value;
}

private void setFirst(Integer value) {
    head.value = value;
}

public Integer getLast() throws Exception {
    checkEmpty();
    return tail.value;
}

private void setLast(Integer value) {
    tail.value = value;
}

private void addLast(Integer value) {
    MyListItem<Integer> newNode = new MyListItem<>(value, head);
    if (tail == null) {
        head = tail = newNode;
        tail.next = head;
    } else {
        tail.next = newNode;
        tail = newNode;
    }
    count++;
}

public void clear() {
    head = tail = null;
    count = 0;
}

public int size() {
    return count;
}

public boolean isEmpty() {
    return size() == 0;
}

public void add(int index, Integer value) throws Exception {
    if (index < 0 || index > count) {
        throw new Exception("Incorrect index");
    }
    if (index == 0) {
        addLast(value);
    } else {
        MyListItem<Integer> prev = getItem(index - 1);
        MyListItem<Integer> newNode = new MyListItem<>(value, prev.next);
        prev.next = newNode;
        if (newNode.next == head) {
            tail = newNode;
        }
        count++;
    }
}

public void set(int index, Integer value) throws Exception {
    if (index < 0 || index >= count) {
        throw new Exception("Incorrect index");
    }
    MyListItem<Integer> node = getItem(index);
    node.value = value;
}

public void add(Integer value) throws Exception {
    addLast(value);
}

public void sorted() throws Exception {
    for (int i = 1; i < count; i++) {
        Integer value = get(i);
        int j;
        for (j = i - 1; j >= 0 && myComparator((java.lang.Integer) get(j), (java.lang.Integer) value) > 0; j--) {
            set(j + 1, get(j)); // shift element right
        }
        set(j + 1, value);
    }
}

public Integer get(int index) throws Exception {
    return getItem(index).value;
}

private MyListItem<Integer> getItem(int index) throws Exception {
    if (index < 0 || index >= size()) {
        throw new Exception("Incorrect index");
    } else {
        MyListItem<Integer> curr = head;
        for (int i = 0; i < index; i++) {
            curr = curr.next;
        }
        return curr;
    }
}

public void removeFirst() {
    if (head == null) return;
    if (head == tail) {
        head = tail = null;
    } else {
        head = head.next;
        tail.next = head;
    }
    count--;
}

public void removeLast() throws Exception {
    checkEmpty();

    if (head == tail) {
        removeFirst();
    } else {
        MyListItem<Integer> curr = head;
        while (curr.next != tail) {
            curr = curr.next;
        }
        curr.next = head;
        tail = curr;
        count--;
    }
}

public void remove(int index) throws Exception {
    if (index < 0 || index >= size()) {
        throw new Exception("Incorrect index");
    }
    if (index == 0) {
        removeFirst();
    } else {
        MyListItem<Integer> prev = getItem(index - 1);
        prev.next = prev.next.next;
        if (index == size()) {
            tail = prev;
        }
        count--;
    }
}

public void deleteUneven(MyList<java.lang.Integer> list) throws Exception {
    MyListItem<Integer> curr = head;
    for (int i = 0; i < size(); i++) {
        if ((int) curr.value % 2 == 1) {
            remove(i);
            i--;
        } else {
            curr = curr.next;
        }
    }
}

public void deletePovtor() {
    if (head == null) return;

    MyListItem<Integer> curr = head;
    do {
        while (curr.next != head && curr.value.equals(curr.next.value)) {
            curr.next = curr.next.next;
            count--;
        }
        curr = curr.next;
    } while (curr != head);
}

public void deleteElementForKToTail(int k) {
    if (head == null || k >= size()) {
        clear();
        return;
    }

    MyListItem<Integer> curr = head;
    for (int i = 0; i < k - 1; i++) {
        curr = curr.next;
    }
    curr.next = head;
    tail = curr;
    count = k;
}

private class MyListItem<Integer> {
    public Integer value;
    public MyListItem<Integer> next;

    public MyListItem(Integer value, MyListItem<Integer> next) {
        this.value = value;
        this.next = next;
    }

    public MyListItem(Integer value) {
        this(value, null);
    }
}
}на основе моего кода реализуй функцию быстрой сортировки моего листа (функцию назови werryWellQuick sort). сортировка должна быть на основе ссылочного типа данных