package List;


import java.lang.reflect.Array;
import java.util.*;


public class HybridList<E>  {
    Class<E> type;
    private final int MAX_SIZE = 100_000;
    private int size;
    private Node<E> firstnode;      //Pointer to firstnode node.
    private Node<E> lastnode;       //Pointer to lastnode node.

    //Constructor empty list
    public HybridList(Class<E> type) {
        this.type = type;
    }

    //Check is List empty
    public boolean isEmpty(){
        return  firstnode == null && lastnode == null;
    }

    //Return size of list
    public int getSize() {
        return size;
    }

    //Add element  to the beginning
    public boolean addFirst(E element) {

        if (!contain(element) && checkSize()) {
            linkFirst(element);
            return true;
        }
        else
            return  false;
    }

    //Add element  in the end
    public boolean addLast(E element) {
        if (!contain(element) && checkSize()) {
            linkLast(element);
            return true;
        }
        else
            return  false;
    }

    //Return element  from the beginning
    public E getLastElement(){
        checkElementIndex(size-1);
        return node(size-1).item;

    }

    //Return element  from the end
    public E getFirstElement(){
        checkElementIndex(0);
        return node(0).item;
    }

    //Replace old element by new element
    public boolean changeValueofElement(E oldelement, E newelement){
        if (!contain(newelement)) {
            Node<E> x = firstnode;
            for (int i = 0; i < size; i++) {
                if (x.item.equals(oldelement)) {
                    x.item = newelement;
                    return true;
                }
                x = x.next;
            }
        }
        return  false;
    }

    //Set new element by index
    public  boolean changeValuebyIndex(int index, E newelement){
        checkElementIndex(index);
        return changeValueofElement(newelement,node(index).item);
    }

    //Check is this value exist in the List
    public boolean contain(E element){
        Node<E> x = firstnode; //идем сначала
        for (int i = 0; i < size; i++) {
            if ( x.item != null && x.item.equals(element) )
                return true;
            x = x.next;
        }
        return false;
    }

    //Delete element  from the beginning
    public E removeFirst()  {
        final Node<E> f = firstnode;
        if (f == null)                          //Есть ли ссылка на первый узел
            throw new NullPointerException();
        return removelinkFirst(f);
    }

    //Delete element  from the end
    public E removeLast()  {
        final Node<E> f = lastnode;
        if (f == null)                          //Есть ли ссылка на последний узел
            throw new NullPointerException();
        return removelinkLast(f);
    }

    //Add element to the end
    public E add(E element){
        addLast(element);
        return element;
    }

    //Add element by index
    public boolean add(int index, E element){
      if( !contain(element)){
          if (index == size)
              linkLast(element);
          else {
              checkElementIndex(index);
              linkBefore(element, node(index));
          }
      }
      return false;
    }

    //Get element by index
    public E get(int index) {
        checkElementIndex(index);
        Node<E> x = firstnode;
        for (int i = 0; i <= index; i++) {
            if(i==index)
                return x.item;
            x=x.next;
        }
        return  null;
    }

    //Delete element  from the end
    public E remove(){
        return removeLast();
    }

    //Delete element by index
    public E remove(int index){
        checkElementIndex(index);
        return   removeLinks(node(index));
    }


    public E[] toArray(){
        @SuppressWarnings("unchecked")
        E[] a = (E[]) Array.newInstance(type, this.size);
        Node<E> x = firstnode;
        for (int i = 0; i < size; i++) {
            a[i] = x.item;
            x=x.next;
        }
        return  a;
    }

    //Return TreeSet with all elements
    public TreeSet<E> toTreeSet(){
        TreeSet<E>  set  = new TreeSet<>();
        for (Node<E> x = firstnode; x != null; x = x.next){
            set.add(x.item);
        }
        return set;
    }
    //Return ArrayList with all elements
    public ArrayList<E> toArrayList(){
        ArrayList<E> arrayList = new ArrayList<>();
        for (Node<E> x = firstnode; x != null; x = x.next){
            arrayList.add(x.item);
        }
        return arrayList;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[ ");
        Node<E>  x = firstnode;
        for (int i = 0; i < size; i++) {
            sb.append(x.item+" ");
            x = x.next;
        }
        sb.append("]");
        return String.valueOf(sb);
    }
    // Class contains nodes with items
    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> last;
        Node(Node<E> last, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.last = last;
        }
    }
    private boolean checkSize(){
        return size <= MAX_SIZE;
    }
    private E removeLinks(Node<E> x) {
        // assert x != null;
        final E element = x.item;       //our object
        final Node<E> next1 = x.next;    //link for  obj after x
        final Node<E> last1 = x.last;    //link for  obj before x
        if (last1 == null) {             //obj is first
            firstnode = next1;
        } else {
            last1.next = next1;
            x.last = null;
        }
        if (next1 == null) {             //obj is last
            lastnode = last1;
        } else {
            next1.last = last1;
            x.next = null;
        }
        x.item = null;
        size--;
        return element;
    }
    private void linkBefore(E element, Node<E> succ) {  //Передали сам новый элемент и узел с нужным индексом
        // assert succ != null;
        final Node<E> pred = succ.last;         //Узел  = ссылка на предыдущий элемент
        final Node<E> newNode = new Node<>(pred, element, succ);
        succ.last = newNode;                    //Этот элемент с нужным индксом как-бы сдвигается вперед(ссылается на предыдущий новый)
        if (pred == null)                       //Иф по индексу 0
            firstnode = newNode;                //Становится первым элементом
        else
            pred.next = newNode;                //Предыдущий теперь ссылается на новый
        size++;
    }
    private void linkFirst(E elment) {
        final Node<E> f = firstnode;                                //узел = ссылка на предыдущий 1й существующий узел
        final Node<E> newNode = new Node<>(null, elment, f);    //create new node,when el add
        firstnode = newNode;                                        //Ссылка на первый узел равно новому узлу(т.е новому єлементу)
        if (f == null)                                              //Иф первые елемента не было
            lastnode = newNode;                                     //Ссылка на последний узел
        else
            f.last = newNode;                                       //иф был то ссылка на последний элемент = сущ
        size++;
    }
    private  void linkLast(E elment) {
        final Node<E> l = lastnode;             //узел = ссылка на предыдущий последний существующий узел
        final Node<E> newNode = new Node<>(l, elment, null);
        lastnode = newNode;
        if (l == null)
            firstnode = newNode;
        else
            l.next = newNode;
        size++;
    }
    private Node<E> node(int index) {           //возврат узла по индексу ??
        // assert isElementIndex(index);
        if (index < size/2 ) {                  //insert not in the 2nd part of list
            Node<E> x = firstnode;              //идем сначала
            for (int i = 0; i < index; i++)
                x = x.next;                     //доходим методом перебора
            return x;
        } else { //индекс
            Node<E> x = lastnode;               //идем с конца
            for (int i = size - 1; i > index; i--)
                x = x.last;
            return x;
        }
    }
    private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }
    private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException();
    }
    private E removelinkFirst(Node<E> f) {  //узел
        // assert f == first && f != null;
        final E element = f.item;           //считка значения для возврата
        final Node<E> next = f.next;        //узел хранящий ссылку на следущий элемент, кот станет первым
        f.item = null;                      // уничтожение значения узла
        f.next = null;                      //Уничтожение ссылки на следующий елемент(на предыдущий и так null)
        firstnode = next;                   //Ссылка на первый элемент теперь на след елементе
        if (next == null)                   //Элемент один был
            lastnode = null;                //ссылки на последний элемент не  будет
        else
            next.last = null;               //Ставший первым элемент не имеет ссылки на предыдущий
        size--;
        return element;
    }
    private E removelinkLast(Node<E> f) {   //узел
        // assert f == first && f != null;
        final E element = f.item;           //считка значения для возврата
        final Node<E> last = f.last;        //узел хранящий ссылку на следущий элемент, кот станет последним
        f.item = null;                      // уничтожение значения узла
        f.last = null;                      //Уничтожение ссылки на предыдущий елемент(на след и так null)
        lastnode = last;                    //Ссылка на последний элемент теперь на предыдущем элементе
        if (last == null)                   //Элемент один был
            firstnode = null;               //ссылки на последний элемент не  будет
        else
            last.next = null;               //Ставший последним элемент не имеет ссылки на след
        size--;
        return element;
    }
}