// Created by Julio Tentor <jtentor@fi.unju.edu.ar>
//
import java.lang.Comparable;
import java.util.Iterator;

public class DoubleLinkedListIteratorComparable<ELEMENT extends Comparable<ELEMENT>> implements Iterable<ELEMENT> {

    private class Node {
        public ELEMENT item;
        public Node next;
        public Node prev;

        public Node() {
            this(null, null, null);
        }
        public Node(ELEMENT item) {
            this(item, null, null);
        }
        public Node(ELEMENT item, Node next) {
            this(item, next, null);
        }
        public Node(ELEMENT item, Node next, Node prev) {
            this.item = item;
            this.next = next;
            this.prev = prev;
        }

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

    private Node head;
    private int count;
    private Node tail;

    public int size() {
        return this.count;
    }

    public DoubleLinkedListIteratorComparable() {
        this.head = null;
        this.count = 0;
        this.tail = null;
    }

    public void addFirst(ELEMENT item) {
        Node temp = new Node(item, this.head, null);
        if (this.count == 0) {
            this.tail = temp;
        }
        else {
            this.head.prev = temp;
        }
        this.head = temp;
        ++this.count;
    }

    public void addLast(ELEMENT item) {
        Node temp = new Node(item, null, this.tail);
        if (this.count == 0) {
            this.head = temp;
        }
        else {
            this.tail.next = temp;
        }
        this.tail = temp;
        ++this.count;
    }

    public ELEMENT removeFirst() {
        if (this.count == 0) {
            throw new RuntimeException("La lista está vacía...");
        }
        ELEMENT item = this.head.item;
        this.head = this.head.next;
        if (this.head == null) {
            this.tail = null;
        }
        else {
            this.head.prev = null;
        }
        --this.count;
        return item;
    }

    public ELEMENT removeLast() {
        if (this.count == 0) {
            throw new RuntimeException("La lista está vacía...");
        }
        ELEMENT item = this.tail.item;
        if (this.head.next == null) {
            this.head = this.tail = null;
        } else {
            this.tail = this.tail.prev;
            this.tail.next = null;
        }
        --this.count;
        return item;
    }


    @Override
    public Iterator<ELEMENT> iterator() {
        return new MyIterator(this.head);
    }


    private class MyIterator implements Iterator<ELEMENT> {
        private Node current;

        public MyIterator(Node current) {
            this.current = current;
        }

        @Override
        public boolean hasNext() {
            return this.current != null;
        }

        @Override
        public ELEMENT next() {
            if (!this.hasNext()) {
                throw new RuntimeException("La lista está vacía...");
            }
            ELEMENT item = this.current.item;
            this.current = this.current.next;
            return item;
        }
    }


    public void addInOrder(ELEMENT item) {
        if (this.count == 0) {
            this.head = this.tail = new Node(item, null, null);
            ++this.count;
        }
        else {
            if (item.compareTo(this.head.item) <= 0) {
                this.addFirst(item);
            }
            else {
                if (item.compareTo(this.tail.item) > 0) {
                    this.addLast(item);
                }
                else {
                    Node skip = this.head;
                    while ((skip != null) && (item.compareTo(skip.item) > 0)) {
                        skip = skip.next;
                    }
                    if (skip == null) {
                        throw new RuntimeException("Algo está mal en el orden de los elementos de la lista...");
                    }
                    else {
                        Node temp = new Node(item, skip, skip.prev);
                        skip.prev.next = temp;
                        skip.prev = temp;
                        ++this.count;
                    }
                }
            }
        }
    }


    public boolean findAndRemove(ELEMENT item) {
        if (this.count == 0) {
            return false;
        }

        Node skip = this.head;
        while ((skip != null) && !(item.compareTo(skip.item) == 0)) {
            skip = skip.next;
        }
        if (skip == null) {
            return false;
        }
        else {
            if (skip.prev == null) {
                this.removeFirst();
                return true;
            }
            else {
                if (skip.next == null) {
                    this.removeLast();
                    return true;
                }
                else {
                    skip.prev.next = skip.next;
                    skip.next.prev = skip.prev;
                    skip.prev = skip.next = null;
                    return true;
                }
            }
        }
    }


}