import java.util.Iterator;

/**
 * A list of bodies implemented as a linked list.
 * The number of elements of the list is not limited.
 */
public class BodyLinkedList implements Iterable<Body> {
    private int size = 0;
    private Item first;
    private Item last;

    /**
     * Initializes 'this' as an empty list.
     */
    public BodyLinkedList() {
        first = null;
        last = null;
    }

    /**
     * Initializes 'this' as an independent copy of the specified list 'list'.
     * Calling methods of this list will not affect the specified list 'list'
     * and vice versa.
     * Precondition: list != null.
     */
    public BodyLinkedList(BodyLinkedList list) {
        this.size = 0;
        for (Body b : list) {
            this.addLast(b);
        }
    }

    /**
     * Inserts the specified element 'body' at the beginning of this list.
     */
    public void addFirst(Body body) {
        if (first == null) {
            first = new Item(body);
            last = first;
        } else {
            first.setPrev(new Item(body));
            first = first.prev;
        }
        size++;
    }

    /**
     * Appends the specified element 'body' to the end of this list.
     */
    public void addLast(Body body) {
        if (last == null) {
            last = new Item(body);
            first = last;
        } else {
            last.setNext(new Item(body));
            last = last.next;
        }
        size++;
    }

    /**
     * Returns the last element in this list.
     * Returns 'null' if the list is empty.
     */
    public Body getLast() {
        return (last != null) ? last.body : null;
    }

    /**
     * Returns the first element in this list.
     * Returns 'null' if the list is empty.
     */
    public Body getFirst() {
        return (first != null) ? first.body : null;
    }

    /**
     * Retrieves and removes the first element in this list.
     * Returns 'null' if the list is empty.
     */
    public Body pollFirst() {
        if (first == null) {
            return null;
        }
        Body b = first.body;
        first = first.next;
        if (first != null) first.setPrev(null);
        size--;
        return b;
    }

    /**
     * Retrieves and removes the last element in this list.
     * Returns 'null' if the list is empty.
     */
    public Body pollLast() {
        if (last == null) {
            return null;
        }
        Body b = last.body;
        last = last.prev;
        if (last != null) last.setNext(null);
        size--;
        return b;
    }

    /**
     * Inserts the specified element 'body' at the specified position in this list.
     * Precondition: i >= 0 && i <= size().
     */
    public void add(int i, Body body) {
        if (first == null || i == 0) {
            addFirst(body);
            return;
        } else if (i == size) {
            addLast(body);
            return;
        }

        Item item = first;
        for (int j = 0; j < i; j++) {
            item = item.next;
        }

        item.prev.setNext(new Item(body));
        item.setPrev(item.prev.next);
        size++;
    }

    private Body removeItem(Item item) {
        if (item == first) {
            first = item.next;
            if (first != null) first.setPrev(null);
        } else if (item == last) {
            last = item.prev;
            if (last != null) last.setNext(null);
        } else {
            item.next.setPrev(item.prev);
        }
        size--;
        return item.body;
    }

    /**
     * Returns the element at the specified position in this list.
     * Precondition: i >= 0 && i < size().
     */
    public Body get(int i) {
        Item item;
        if (i < size / 2) {
            item = first;
            for (int j = 0; j < i; j++) {
                item = item.next;
            }
        } else {
            item = last;
            for (int j = size - 1; j > i; j--) {
                item = item.prev;
            }
        }
        return item.body;
    }

    /**
     * Returns the index of the first occurrence of the specified element in this list, or -1 if
     * this list does not contain the element.
     */
    public int indexOf(Body body) {
        if (first == null) {
            return -1;
        }

        Item item = first;
        for (int i = 0; i < size; i++, item = item.next) {
            if (item.body == body) return i;
        }

        return -1;
    }

    /**
     * Removes all bodies of this list, which are colliding with the specified
     * body. Returns a list with all the removed bodies.
     */
    public BodyLinkedList removeCollidingWith(Body body) {
        BodyLinkedList removed = new BodyLinkedList();
        for (Item item = first; item != null; item = item.next) {
            if (body != item.body && body.collidesWith(item.body)) {
                removed.addLast(this.removeItem(item));
            }
        }
        return removed;
    }

    /**
     * Returns the number of bodies in this list.
     */
    public int size() {
        return size;
    }

    @Override
    public Iterator<Body> iterator() {
        return new Iterator<>() {
            Item ptr = first;
            boolean yieldedFirst = false;

            @Override
            public boolean hasNext() {
                return ptr != null && (!yieldedFirst || ptr.next != null);
            }

            @Override
            public Body next() {
                if (!yieldedFirst) {
                    yieldedFirst = true;
                } else {
                    ptr = ptr.next;
                }
                return ptr.body;
            }
        };
    }

    private static class Item {
        private final Body body;
        private Item prev;
        private Item next;

        public Item(Body body) {
            this.body = body;
            this.prev = null;
            this.next = null;
        }

        public void setPrev(Item prev) {
            this.prev = prev;
            if (prev != null) prev.next = this;
        }

        public void setNext(Item next) {
            this.next = next;
            if (next != null) next.prev = this;
        }
    }
}
