[NP] Сортирана двојно поврзана листа

import java.util.*;

class SortedLinkedList<T extends Comparable<T>> {

    private class Node<T extends Comparable<T>> implements Comparable<Node<T>> {
        T data;
        Node<T> previous;
        Node<T> next;

        public Node(T data, Node<T> previous, Node<T> next) {
            this.data = data;
            this.previous = previous;
            this.next = next;
        }

        @Override
        public String toString() {
            return data.toString();
        }

        @Override
        public int compareTo(Node<T> that) {
            return this.data.compareTo(that.data);
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Node<?> node = (Node<?>) o;

            return data != null ? data.equals(node.data) : node.data == null;
        }

        @Override
        public int hashCode() {
            return data != null ? data.hashCode() : 0;
        }
    }

    private class SortedLinkedListIterator<T extends Comparable<T>> implements Iterator<T> {

        private Node<T> previous, current, next;

        SortedLinkedListIterator() {
            current = (Node<T>) first;
            next = null;
        }

        @Override
        public boolean hasNext() {
            return next != null;
        }

        @Override
        public T next() {
            T data = current.data;
            current = next;
            next = next.next;
            return data;
        }
    }

    private Node<T> first;
    private Node<T> last;
    private int size;

    SortedLinkedList() {
        this.first = null;
        this.last = null;
        this.size = 0;
    }

    public int size() {
        return size;
    }

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

    public void add(T element) {
        /* Initial case*/
        if (first == null) {
            first = new Node<>(element, null, null);
            last = first;
            size++;
        }
        /* If element already exists, don't add it */
        else if (!contains(element)) {

            Node<T> current = this.getFirst();
            while (current.data.compareTo(element) < 0) {

                /* If it's the biggest, add it at the end */
                if (current.next == null) {

                    insertLast(element);
                    size++;
                    return;
                }
                current = current.next;
            }

            /* The while moved us to a position where all left of current are less than current */
            insertBefore(element, current);
            size++;

        }
    }

    public void insertFirst(T element) {
        Node<T> insert = new Node<>(element, null, first);
        if (first == null) {
            last = insert;
        } else {
            first.previous = insert;
        }
        first = insert;
    }

    public void insertLast(T element) {

        if (first == null) {
            insertFirst(element);
        } else {
            Node<T> insert = new Node<>(element, last, null);
            last.next = insert;
            last = insert;
        }
    }

    public void insertAfter(T element, Node<T> after) {

        if (after == last) {
            insertLast(element);
            return;
        }
        Node<T> insert = new Node<>(element, after, after.next);
        after.next.previous = insert;
        after.next = insert;
    }

    public void insertBefore(T element, Node<T> before) {

        if (before == first) {
            insertFirst(element);
            return;
        }
        Node<T> insert = new Node<>(element, before.previous, before);
        before.previous.next = insert;
        before.previous = insert;
    }

    public T deleteFirst() {
        if (first == null) return null;
        Node<T> current = first;
        first = first.next;
        if (first != null) {
            first.previous = null;
        }
        if (first == null) {
            last = null;
        }
        return current.data;
    }

    public T deleteLast() {
        if (first == null) return null;
        if (first.next == null) {
            return deleteFirst();
        } else {
            Node<T> temp = last;
            last = last.previous;
            last.next = null;
            return temp.data;
        }
    }

    public boolean remove(T element) {
        Node<T> current = this.getFirst();
        while (!current.data.equals(element)) {
            if (current.next == null) return false;
            current = current.next;
        }
        if (current == first) {
            deleteFirst();
        } else if (current == last) {
            deleteLast();
        } else {
            current.previous.next = current.next;
            current.next.previous = current.previous;
        }
        size--;
        return true;
    }

    public boolean contains(T element) {
        Node<T> current = this.getFirst();
        while (!current.data.equals(element)) {
            if (current.next == null) {
                return false;
            }
            current = current.next;
        }
        return true;
    }

    public Node<T> getFirst() {
        return first;
    }

    public Node<T> getLast() {
        return last;
    }

    public ArrayList<T> toArrayList() {
        ArrayList<T> arrayList = new ArrayList<>(size);
        Node<T> current = first;
        while (current != null) {
            arrayList.add(current.data);
            current = current.next;
        }
        return arrayList;
    }

    public void addAll(SortedLinkedList<? extends T> sortedLinkedList) {
        Node<? extends T> current = (Node<? extends T>) sortedLinkedList.getFirst();
        while (current != null) {
            this.add(current.data);
            current = current.next;
        }
        size += sortedLinkedList.size;
    }

    public boolean containsAll(SortedLinkedList<? extends T> sortedLinkedList) {
        Node<? extends T> current = (Node<? extends T>) sortedLinkedList.first;
        while (current != null) {
            if (!this.contains(current.data)) {
                return false;
            }
            current = current.next;
        }
        return true;
    }

    @Override
    public String toString() {
        if (first == null) return "Empty List!";
        StringBuffer sb = new StringBuffer();
        Node<T> current = this.getFirst();
        while (current != null) {
            sb.append(current.data + " ");
            current = current.next;
        }
        return sb.toString();
    }
}

public class SortedLinkedListTest {
    public static void main(String[] args) {
        Scanner jin = new Scanner(System.in);
        int k = jin.nextInt();
        System.out.println("Test#" + k);
        System.out.print("testing SortedLinkedList::toArrayList():ArrayList<T> ,");
        if (k == 0) {
            System.out.println(" SortedLinkedList::add(T), SortedLinkedList::isEmpty():boolean , SortedLinkedList::remove(T):boolean , SortedLinkedList::size():int , T is Integer");

            SortedLinkedList<Integer> list = new SortedLinkedList<Integer>();
            System.out.println("List is empty? " + list.isEmpty());
            System.out.println("Adding elements:");
            boolean flag = false;
            while (jin.hasNextInt()) {
                System.out.print(flag ? " " : "");
                int i = jin.nextInt();
                list.add(i);
                System.out.print(i);
                flag = true;
            }
            System.out.println();
            System.out.println("List size? " + list.size());
            jin.next();
            flag = false;
            System.out.println("Removing elements:");
            while (jin.hasNextInt()) {
                System.out.print(flag ? " " : "");
                int i = jin.nextInt();
                list.remove(i);
                System.out.print(i);
                flag = true;
            }
            System.out.println();
            System.out.println("List size? " + list.size());
            System.out.println("Final list: " + list.toArrayList());
        }
        if (k == 1) {
            System.out.println(" SortedLinkedList::add(T) , T is Integer");
            System.out.println("Adding elements:");
            SortedLinkedList<Integer> list = new SortedLinkedList<Integer>();
            boolean flag = false;
            while (jin.hasNextInt()) {
                System.out.print(flag ? " " : "");
                int i = jin.nextInt();
                list.add(i);
                System.out.print(i);
                flag = true;
            }
            System.out.println();
            System.out.print("Final list: ");
            System.out.println(list.toArrayList());
        }
        if (k == 2) {
            System.out.println(" SortedLinkedList::add(T) , SortedLinkedList::addAll(SortedLinkedList<? etends T>) , T is Integer");

            int num_testcases = jin.nextInt();
            for (int w = 0; w < num_testcases; ++w) {
                System.out.println("Subtest #" + (w + 1));
                SortedLinkedList<Integer> list = new SortedLinkedList<Integer>();
                while (jin.hasNextInt()) {
                    list.add(jin.nextInt());
                }
                SortedLinkedList<Integer> query = new SortedLinkedList<Integer>();
                jin.next();
                while (jin.hasNextInt()) {
                    query.add(jin.nextInt());
                }
                System.out.println("List a=" + list.toArrayList());
                System.out.println("List b=" + query.toArrayList());
                list.addAll(query);
                System.out.println("Add all elements from b to a");
                System.out.println("List a=" + list.toArrayList());
                jin.next();
            }
        }
        if (k == 3) {
            System.out.println(" SortedLinkedList::add(T) , SortedLinkedList::containsAll(SortedLinkedList<? etends T>) , T is Integer");
            int num_testcases = jin.nextInt();
            for (int w = 0; w < num_testcases; ++w) {
                System.out.println("Subtest #" + (w + 1));
                SortedLinkedList<Integer> list = new SortedLinkedList<Integer>();
                while (jin.hasNextInt()) {
                    list.add(jin.nextInt());
                }
                SortedLinkedList<Integer> query = new SortedLinkedList<Integer>();
                jin.next();
                while (jin.hasNextInt()) {
                    query.add(jin.nextInt());
                }
                System.out.println("List a=" + list.toArrayList());
                System.out.println("List b=" + query.toArrayList());
                System.out.println("List a contains all elements in list b? " + list.containsAll(query));
                jin.next();
            }
        }
        if (k == 4) {
            System.out.println(" SortedLinkedList::add(T) , SortedLinkedList::remove(T):boolean , SortedLinkedList::contains(T) , T is String");
            SortedLinkedList<String> list = new SortedLinkedList<String>();
            TreeSet<String> control_list = new TreeSet<String>();
            ArrayList<String> all = new ArrayList<String>();
            all.add("Sample");
            boolean same = true;
            for (int i = 0; i < 1000; ++i) {
                double rand = Math.random();
                if (rand > 0.3) {
                    String srand = randomString();
                    if (Math.random() < 0.1) {
                        srand = all.get((int) (Math.random() * all.size()));
                    }
                    control_list.add(srand);
                    list.add(srand);
                }
                if (rand >= 0.3 && rand < 0.8) {
                    String srand = randomString();
                    if (Math.random() < 0.6) {
                        srand = all.get((int) (Math.random() * all.size()));
                    }
                    same &= control_list.contains(srand) == list.contains(srand);
                }
                if (rand >= 0.8) {
                    String srand = randomString();
                    if (Math.random() < 0.8) {
                        srand = all.get((int) (Math.random() * all.size()));
                    }
                    control_list.remove(srand);
                    list.remove(srand);
                }
            }
            System.out.println("Your list outputs compared to the built in java structure were the same? " + same);

        }
        if (k == 5) {
            System.out.println(" SortedLinkedList::add(T) , SortedLinkedList::remove(T):boolean , T is Long");
            int n = jin.nextInt();
            SortedLinkedList<Long> list = new SortedLinkedList<Long>();
            ArrayList<Long> all = new ArrayList<Long>();
            all.add(684165189745L);
            for (int i = 0; i < n; ++i) {
                double rand = Math.random();
                if (rand < 0.7) {
                    Long srand = (long) (Math.random() * 45668948941984L);
                    if (Math.random() < 0.1) {
                        srand = all.get((int) (Math.random() * all.size()));
                    }
                    list.add(srand);
                }
                if (rand >= 0.7) {
                    Long srand = (long) (Math.random() * 45668948941984L);
                    if (Math.random() < 0.1) {
                        srand = all.get((int) (Math.random() * all.size()));
                    }
                    list.remove(srand);
                }
            }
            System.out.println("Your program was really fast. You are a great developer!");
        }
    }

    private static String randomString() {
        byte buf[] = new byte[(int) (Math.random() * 10) + 1];
        new Random().nextBytes(buf);
        return new String(buf);
    }

}