package com.xqbase.apool.util;

import java.util.Collection;
import java.util.Iterator;

/**
 * This class provides the ability to remove the arbitrary interior element (
 * neither head nor tail) from the queue in O(1) time.
 *
 * Adding to and removing from head or tail also run in O(1) time, as expected.
 *
 * This is not thread safe.
 *
 * @author Tony He
 */
public class LinkedDeque<T> extends AbstractDeque<T> {

    /**
     * Internal Node Class
     */
    public static class Node<T> {

        private final T value;
        private Node<T> next;
        private Node<T> prev;

        public Node(T value) {
            this.value = value;
        }
    }

    private Node<T> head;
    private Node<T> tail;
    private int size;

    /**
     * Construct a new instance.
     */
    public LinkedDeque() {
        super();
    }

    /**
     * Construct a new instance, adding all objects in the specified collection.
     *
     * @param collection a {@link Collection} of objects to be added.
     */
    public LinkedDeque(Collection<T> collection) {
        super();
        addAll(collection);
    }

    /**
     * Add a new item at the head of the queue.
     *
     * @param item the item to be added.
     * @return the {@link Node} of the newly added item.
     */
    public Node<T> addFirstNode(T item) {
        return addBeforeNode(head, item);
    }

    /**
     * Add a new item at the tail of the queue.
     *
     * @param item the item to be added.
     * @return the {@link Node} of the newly added item.
     */
    public Node<T> addLastNode(T item) {
        return addBeforeNode(null, item);
    }

    /**
     * Add a new item before the specified node.
     *
     * @param before before the {@link Node} before which the item should be added.
     * @param item the item to be added.
     * @return the {@link Node} of the newly added item.
     */
    public Node<T> addBeforeNode(Node<T> before, T item) {
        if (item == null) {
            throw new NullPointerException();
        }

        if (before != null && before != head && before.next == null && before.prev == null) {
            throw new IllegalStateException("node does not exist");
        }

        Node<T> node = new Node<>(item);
        if (before == null) {
            // add to tail
            node.next = null;
            node.prev = tail;
            if (tail != null) {
                tail.next = node;
            }
            tail = node;
            if (head == null) {
                head = node;
            }
        } else {
            node.next = before;
            node.prev = before.prev;
            before.prev = node;
            if (before == head) {
                head = node;
            }
        }
        size ++;
        return node;
    }

    @Override
    public boolean offerFirst(T t) {
        return false;
    }

    @Override
    public boolean offerLast(T t) {
        return false;
    }

    @Override
    public T peekFirst() {
        return null;
    }

    @Override
    public T peekLast() {
        return null;
    }

    @Override
    public Iterator<T> descendingIterator() {
        return null;
    }

    @Override
    public T pollFirst() {
        return null;
    }

    @Override
    public T pollLast() {
        return null;
    }

    @Override
    public Iterator<T> iterator() {
        return null;
    }

    @Override
    public int size() {
        return 0;
    }
}

@@ -489,24 +489,65 @@
  Node%3CT%3E %7B%0A%0A
+        private final LinkedDeque queue;%0A
         priv
@@ -650,18 +650,69 @@
 ode(
-T value) %7B
+LinkedDeque queue, T value) %7B%0A            this.queue = queue;
 %0A   
@@ -2333,16 +2333,22 @@
  Node%3C%3E(
+this, 
 item);%0A 
@@ -2885,32 +2885,878 @@
 rn node;%0A    %7D%0A%0A
+    /**%0A     * Remove the specified node from the queue.%0A     *%0A     * @param node the Node to be removed.%0A     * @return the item contained in the Node which was removed.%0A     */%0A    public T removeNode(Node%3CT%3E node) %7B%0A        if (node.queue != this) %7B%0A            throw new IllegalArgumentException(%22node does not belong to this queue%22);%0A        %7D%0A%0A        if (node != head && node.next == null && node.prev == null) %7B%0A            return null;%0A        %7D%0A%0A        if (head == node) %7B%0A            head = node.next;%0A        %7D%0A        if (node.prev != null) %7B%0A            node.prev.next = node.next;%0A        %7D%0A%0A        if (tail == node) %7B%0A            tail = node.prev;%0A        %7D%0A        if (node.next != null) %7B%0A            node.next.prev = node.prev;%0A        %7D%0A        node.next = null;%0A        node.prev = null;%0A        return node.value;%0A    %7D%0A%0A
     @Override%0A  

add removeNode method...