package assignment1;

/**
 * Interface for List ADT
 *
 * @autor Abuzyar Tazetdinov
 */
interface List<T> {
    /**
     * Check list is empty or not
     *
     * @return true if list is empty, otherwise - false
     */
    boolean isEmpty();

    /**
     * Add element to list in place, provided by index
     *
     * @param i - index in list
     * @param e - element
     */
    void add(int i, T e);

    /**
     * Add element to head of the list
     *
     * @param e - element
     */
    void addFirst(T e);

    /**
     * Add element to tail of the list
     *
     * @param e - element
     */
    void addLast(T e);

    /**
     * Delete all elements in list with value e if it exists in list
     *
     * @param e - element
     */
    void delete(T e);

    /**
     * Delete element in index
     *
     * @param i - index
     */
    void delete(int i);

    /**
     * Delete element from list head
     */
    void deleteFirst();

    /**
     * Delete element from list tail
     */
    void deleteLast();

    /**
     * Set element for i'th index
     *
     * @param i - index
     * @param e - element
     */
    void set(int i, T e);

    /**
     * Return element in particular index
     *
     * @param i - index
     * @return - element
     */
    T get(int i);
}


/**
 * Implementation of List ADT using Array
 *
 * @author Abuzyar Tazetdinov
 */
class DynamicArray<T> implements List<T> {
    /**
     * Count of elements in list
     */
    private int count = 0;

    /**
     * Storage array for elements
     */
    private Object[] elements = new Object[1];

    /**
     * Returns quantity of elements
     * Time complexity - O(1)
     */
    public int size() {
        return count;
    }

    /**
     * Check list is empty or not
     *
     * @return true if list is empty, otherwise - false
     * Time complexity - O(1)
     */
    @Override
    public boolean isEmpty() {
        return count == 0;
    }

    /**
     * Add element to list in place, provided by index
     * Time complexity - O(n)
     *
     * @param i - index in list
     * @param e - element
     */
    @Override
    public void add(int i, T e) {
        if (i < 0 || i > elements.length) {
            throw new IndexOutOfBoundsException();
        }
        if (count == elements.length) {
            doubleSize();
        }
        System.arraycopy(elements, i, elements, i + 1, count - i);
        elements[i] = (T) e;
        count++;
    }

    /**
     * Increase size of array by x2
     * Time complexity - O(n)
     */
    private void doubleSize() {
        Object[] newElements = new Object[elements.length * 2];
        System.arraycopy(elements, 0, newElements, 0, elements.length);
        elements = newElements;
    }

    /**
     * Add element to head of the list
     * Time complexity - O(n)
     *
     * @param e - element
     */
    @Override
    public void addFirst(T e) {
        add(0, e);
    }

    /**
     * Add element to tail of the list
     * Time complexity - O(1)
     *
     * @param e - element
     */
    @Override
    public void addLast(T e) {
        add(count, e);
    }

    /**
     * Delete all elements in list with value e if it exists in list
     * Time complexity - O(n)
     *
     * @param e - element
     */
    @Override
    public void delete(T e) {
        int i = 0;
        while (i < count) {
            if (elements[i] == e) {
                delete(i);
            } else {
                i++;
            }
        }
    }


    /**
     * Delete element in index
     * Time complexity - O(n)
     *
     * @param i - index
     */
    @Override
    public void delete(int i) {
        if (i < 0 || i > elements.length) {
            throw new IndexOutOfBoundsException();
        }
        System.arraycopy(elements, i + 1, elements, i, count - i);
        count--;
    }

    /**
     * Delete element from list head
     * Time complexity - O(n)
     */
    @Override
    public void deleteFirst() {
        delete(0);
    }

    /**
     * Delete element from list tail
     * Time complexity - O(1)
     */
    @Override
    public void deleteLast() {
        elements[count - 1] = null;
        count--;
    }

    /**
     * Set element for i'th index
     * Time complexity - O(1)
     *
     * @param i - index
     * @param e - element
     */
    @Override
    public void set(int i, T e) {
        if (i < 0 || i > elements.length) {
            throw new IndexOutOfBoundsException();
        }
        elements[i] = e;
    }

    /**
     * Return element in particular index
     * Time complexity - O(1)
     *
     * @param i - index
     * @return - element
     */
    @Override
    public T get(int i) {
        return (T) elements[i];
    }
}

/**
 * Implementation of List ADT using Nodes with double links (to next and previous element)
 *
 * @author Abuzyar Tazetdinov
 */
class DoublyLinkedList<T> implements List<T> {
    /**
     * Head of the list
     */
    Node<T> head = new Node<>();

    /**
     * Tail of the list
     */
    Node<T> tail = head;

    /**
     * Quantity of elements in list
     */
    int count = 0;

    /**
     * Check list is empty or not
     * Time complexity - O(1)
     *
     * @return true if list is empty, otherwise - false
     */
    @Override
    public boolean isEmpty() {
        return count == 0;
    }

    /**
     * Returns quantity of elements
     * Time complexity - O(1)
     */
    public int size() {
        return count;
    }

    /**
     * Time complexity - O(n)
     *
     * @param i - index
     * @return - reference to node
     */
    private Node<T> getNodeByIndex(int i) {
        Node<T> current;
        if (count / 2 < i) { // from tail
            current = tail;
            for (int j = count - 1; j > i; j--) {
                current = current.prev;
            }
        } else { // from head
            current = head;
            for (int j = 0; j < i; j++) {
                current = current.next;
            }
        }
        return current;
    }

    /**
     * Add element to list in place, provided by index
     * Time complexity - O(n)
     *
     * @param i - index in list
     * @param e - element
     */
    @Override
    public void add(int i, T e) {
        if (i < 0 || i > count) {
            throw new IndexOutOfBoundsException();
        }
        if (i == 0) {
            addFirst(e);
        } else if (i == count) {
            addLast(e);
        } else {
            Node<T> current = getNodeByIndex(i);
            Node<T> newNode = new Node<>(e);
            newNode.next = current.next;
            newNode.next.prev = newNode;
            newNode.prev = current;
            current.next = newNode;
            count++;
        }
    }

    /**
     * Add element to head of the list
     * Time complexity - O(1)
     *
     * @param e - element
     */
    @Override
    public void addFirst(T e) {
        if (count == 0) {
            head.value = e;
        } else {
            Node<T> newHead = new Node<>(e);
            head.prev = newHead;
            newHead.next = head;
            head = newHead;
        }
        count++;
    }

    /**
     * Add element to tail of the list
     * Time complexity - O(1)
     *
     * @param e - element
     */
    @Override
    public void addLast(T e) {
        if (count == 0) {
            tail.value = e;
        } else {
            Node<T> newTail = new Node<>(e);
            newTail.prev = tail;
            tail.next = newTail;
            tail = newTail;
        }
        count++;
    }

    /**
     * Time complexity - O(1)
     *
     * @param current - node to delete
     */
    private void deleteNode(Node<T> current) {
        current.next.prev = current.prev;
        current.prev.next = current.next;
        count--;
    }

    /**
     * Delete all elements in list with value e if it exists in list
     * Time complexity - O(n)
     *
     * @param e - element's value
     */
    @Override
    public void delete(T e) {
        Node<T> current = head;
        while (current != null) {
            if (current.value == e) {
                if (current.prev == null) {
                    current = current.next;
                    deleteFirst();
                } else if (current.next == null) {
                    current = null;
                    deleteLast();
                } else {
                    current = current.next;
                    deleteNode(current.prev);
                }
            } else {
                current = current.next;
            }
        }
    }

    /**
     * Delete element in index
     * Time complexity - O(n)
     *
     * @param i - index
     */
    @Override
    public void delete(int i) {
        if (i < 0 || i > count) {
            throw new IndexOutOfBoundsException();
        }
        if (i == 0) {
            deleteFirst();
        } else if (count - 1 == i) {
            deleteLast();
        } else {
            deleteNode(getNodeByIndex(i));
        }
    }

    /**
     * Delete element from list head
     * Time complexity - O(1)
     */
    @Override
    public void deleteFirst() {
        if (head.next != null) {
            head = head.next;
            head.prev = null;
        } else {
            head.value = null;
        }
        count--;
    }

    /**
     * Delete element from list tail
     * Time complexity - O(1)
     */
    @Override
    public void deleteLast() {
        if (tail.prev != null) {
            tail = tail.prev;
            tail.next = null;
        } else {
            tail.value = null;
        }
        count--;
    }

    /**
     * Set element for i'th index
     * Time complexity - O(n)
     *
     * @param i - index
     * @param e - element
     */
    @Override
    public void set(int i, T e) {
        if (i < 0 || i > count) {
            throw new IndexOutOfBoundsException();
        }
        if (i == 0) {
            head.value = e;
        } else if (count == i - 1) {
            tail.value = e;
        } else {
            getNodeByIndex(i).value = e;
        }
    }

    /**
     * Return element in particular index
     * Time complexity - O(n)
     *
     * @param i - index
     * @return - element
     */
    @Override
    public T get(int i) {
        if (i < 0 || i > count || count == 0) {
            throw new IndexOutOfBoundsException();
        }
        if (i == 0) {
            return head.value;
        } else if (count - 1 == i) {
            return tail.value;
        }
        return getNodeByIndex(i).value;
    }
}

/**
 * Class for Node in Doubly Linked List
 *
 * @autor Abuzyar Tazetdinov
 */
class Node<T> {
    /**
     * Reference to previous element
     */
    public Node<T> prev = null;

    /**
     * Reference to next element
     */
    public Node<T> next = null;

    /**
     * Node's value
     */
    public T value = null;

    public Node() {
    }

    public Node(T v) {
        value = v;
    }
}