/*
 * Copyright 2011 Google Inc. All Rights Reserved.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package mssql.googlecode.concurrentlinkedhashmap;

import java.util.AbstractCollection;
import java.util.Collection;
import java.util.Deque;
import java.util.Iterator;
import java.util.NoSuchElementException;

Linked list implementation of the Deque interface where the link pointers are tightly integrated with the element. Linked deques have no capacity restrictions; they grow as necessary to support usage. They are not thread-safe; in the absence of external synchronization, they do not support concurrent access by multiple threads. Null elements are prohibited. 

Most LinkedDeque operations run in constant time by assuming that the Linked parameter is associated with the deque instance. Any usage that violates this assumption will result in non-deterministic behavior. 

The iterators returned by this class are not fail-fast: If
the deque is modified at any time after the iterator is created, the iterator
will be in an unknown state. Thus, in the face of concurrent modification,
the iterator risks arbitrary, non-deterministic behavior at an undetermined
time in the future.
Author:
ben.manes@gmail.com (Ben Manes)
Type parameters:
<E> – the type of elements held in this collection
See Also:

 *      http://code.google.com/p/concurrentlinkedhashmap//**
 * Linked list implementation of the {@link Deque} interface where the link
 * pointers are tightly integrated with the element. Linked deques have no
 * capacity restrictions; they grow as necessary to support usage. They are not
 * thread-safe; in the absence of external synchronization, they do not support
 * concurrent access by multiple threads. Null elements are prohibited.
 * <p>
 * Most <tt>LinkedDeque</tt> operations run in constant time by assuming that
 * the {@link Linked} parameter is associated with the deque instance. Any usage
 * that violates this assumption will result in non-deterministic behavior.
 * <p>
 * The iterators returned by this class are <em>not</em> <i>fail-fast</i>: If
 * the deque is modified at any time after the iterator is created, the iterator
 * will be in an unknown state. Thus, in the face of concurrent modification,
 * the iterator risks arbitrary, non-deterministic behavior at an undetermined
 * time in the future.
 *
 * @author ben.manes@gmail.com (Ben Manes)
 * @param <E> the type of elements held in this collection
 * @see <a href="http://code.google.com/p/concurrentlinkedhashmap/">
 *      http://code.google.com/p/concurrentlinkedhashmap/</a>
 */
final class LinkedDeque<E extends Linked<E>> extends AbstractCollection<E> implements Deque<E> {

  // This class provides a doubly-linked list that is optimized for the virtual
  // machine. The first and last elements are manipulated instead of a slightly
  // more convenient sentinel element to avoid the insertion of null checks with
  // NullPointerException throws in the byte code. The links to a removed
  // element are cleared to help a generational garbage collector if the
  // discarded elements inhabit more than one generation.

  
Pointer to first node.
Invariant: (first == null && last == null) ||
           (first.prev == null)
/**
   * Pointer to first node.
   * Invariant: (first == null && last == null) ||
   *            (first.prev == null)
   */
  E first;

  
Pointer to last node.
Invariant: (first == null && last == null) ||
           (last.next == null)
/**
   * Pointer to last node.
   * Invariant: (first == null && last == null) ||
   *            (last.next == null)
   */
  E last;

  
Links the element to the front of the deque so that it becomes the first
element.
Params:
e – the unlinked element/**
   * Links the element to the front of the deque so that it becomes the first
   * element.
   *
   * @param e the unlinked element
   */
  void linkFirst(final E e) {
    final E f = first;
    first = e;

    if (f == null) {
      last = e;
    } else {
      f.setPrevious(e);
      e.setNext(f);
    }
  }

  
Links the element to the back of the deque so that it becomes the last
element.
Params:
e – the unlinked element/**
   * Links the element to the back of the deque so that it becomes the last
   * element.
   *
   * @param e the unlinked element
   */
  void linkLast(final E e) {
    final E l = last;
    last = e;

    if (l == null) {
      first = e;
    } else {
      l.setNext(e);
      e.setPrevious(l);
    }
  }

  
Unlinks the non-null first element. /** Unlinks the non-null first element. */
  E unlinkFirst() {
    final E f = first;
    final E next = f.getNext();
    f.setNext(null);

    first = next;
    if (next == null) {
      last = null;
    } else {
      next.setPrevious(null);
    }
    return f;
  }

  
Unlinks the non-null last element. /** Unlinks the non-null last element. */
  E unlinkLast() {
    final E l = last;
    final E prev = l.getPrevious();
    l.setPrevious(null);
    last = prev;
    if (prev == null) {
      first = null;
    } else {
      prev.setNext(null);
    }
    return l;
  }

  
Unlinks the non-null element. /** Unlinks the non-null element. */
  void unlink(E e) {
    final E prev = e.getPrevious();
    final E next = e.getNext();

    if (prev == null) {
      first = next;
    } else {
      prev.setNext(next);
      e.setPrevious(null);
    }

    if (next == null) {
      last = prev;
    } else {
      next.setPrevious(prev);
      e.setNext(null);
    }
  }

  @Override
  public boolean isEmpty() {
    return (first == null);
  }

  void checkNotEmpty() {
    if (isEmpty()) {
      throw new NoSuchElementException();
    }
  }

  
{@inheritDoc}

Beware that, unlike in most collections, this method is NOT a
constant-time operation.
/**
   * {@inheritDoc}
   * <p>
   * Beware that, unlike in most collections, this method is <em>NOT</em> a
   * constant-time operation.
   */
  @Override
  public int size() {
    int size = 0;
    for (E e = first; e != null; e = e.getNext()) {
      size++;
    }
    return size;
  }

  @Override
  public void clear() {
    for (E e = first; e != null;) {
      E next = e.getNext();
      e.setPrevious(null);
      e.setNext(null);
      e = next;
    }
    first = last = null;
  }

  @Override
  public boolean contains(Object o) {
    return (o instanceof Linked<?>) && contains((Linked<?>) o);
  }

  // A fast-path containment check
  boolean contains(Linked<?> e) {
    return (e.getPrevious() != null)
        || (e.getNext() != null)
        || (e == first);
  }

  
Moves the element to the front of the deque so that it becomes the first
element.
Params:
e – the linked element/**
   * Moves the element to the front of the deque so that it becomes the first
   * element.
   *
   * @param e the linked element
   */
  public void moveToFront(E e) {
    if (e != first) {
      unlink(e);
      linkFirst(e);
    }
  }

  
Moves the element to the back of the deque so that it becomes the last
element.
Params:
e – the linked element/**
   * Moves the element to the back of the deque so that it becomes the last
   * element.
   *
   * @param e the linked element
   */
  public void moveToBack(E e) {
    if (e != last) {
      unlink(e);
      linkLast(e);
    }
  }

  @Override
  public E peek() {
    return peekFirst();
  }

  @Override
  public E peekFirst() {
    return first;
  }

  @Override
  public E peekLast() {
    return last;
  }

  @Override
  public E getFirst() {
    checkNotEmpty();
    return peekFirst();
  }

  @Override
  public E getLast() {
    checkNotEmpty();
    return peekLast();
  }

  @Override
  public E element() {
    return getFirst();
  }

  @Override
  public boolean offer(E e) {
    return offerLast(e);
  }

  @Override
  public boolean offerFirst(E e) {
    if (contains(e)) {
      return false;
    }
    linkFirst(e);
    return true;
  }

  @Override
  public boolean offerLast(E e) {
    if (contains(e)) {
      return false;
    }
    linkLast(e);
    return true;
  }

  @Override
  public boolean add(E e) {
    return offerLast(e);
  }


  @Override
  public void addFirst(E e) {
    if (!offerFirst(e)) {
      throw new IllegalArgumentException();
    }
  }

  @Override
  public void addLast(E e) {
    if (!offerLast(e)) {
      throw new IllegalArgumentException();
    }
  }

  @Override
  public E poll() {
    return pollFirst();
  }

  @Override
  public E pollFirst() {
    return isEmpty() ? null : unlinkFirst();
  }

  @Override
  public E pollLast() {
    return isEmpty() ? null : unlinkLast();
  }

  @Override
  public E remove() {
    return removeFirst();
  }

  @Override
  @SuppressWarnings("unchecked")
  public boolean remove(Object o) {
    return (o instanceof Linked<?>) && remove((E) o);
  }

  // A fast-path removal
  boolean remove(E e) {
    if (contains(e)) {
      unlink(e);
      return true;
    }
    return false;
  }

  @Override
  public E removeFirst() {
    checkNotEmpty();
    return pollFirst();
  }

  @Override
  public boolean removeFirstOccurrence(Object o) {
    return remove(o);
  }

  @Override
  public E removeLast() {
    checkNotEmpty();
    return pollLast();
  }

  @Override
  public boolean removeLastOccurrence(Object o) {
    return remove(o);
  }

  @Override
  public boolean removeAll(Collection<?> c) {
    boolean modified = false;
    for (Object o : c) {
      modified |= remove(o);
    }
    return modified;
  }

  @Override
  public void push(E e) {
    addFirst(e);
  }

  @Override
  public E pop() {
    return removeFirst();
  }

  @Override
  public Iterator<E> iterator() {
    return new AbstractLinkedIterator(first) {
      @Override E computeNext() {
        return cursor.getNext();
      }
    };
  }

  @Override
  public Iterator<E> descendingIterator() {
    return new AbstractLinkedIterator(last) {
      @Override E computeNext() {
        return cursor.getPrevious();
      }
    };
  }

  abstract class AbstractLinkedIterator implements Iterator<E> {
    E cursor;

    
Creates an iterator that can can traverse the deque.
Params:
start – the initial element to begin traversal from/**
     * Creates an iterator that can can traverse the deque.
     *
     * @param start the initial element to begin traversal from
     */
    AbstractLinkedIterator(E start) {
      cursor = start;
    }

    @Override
    public boolean hasNext() {
      return (cursor != null);
    }

    @Override
    public E next() {
      if (!hasNext()) {
        throw new NoSuchElementException();
      }
      E e = cursor;
      cursor = computeNext();
      return e;
    }

    @Override
    public void remove() {
      throw new UnsupportedOperationException();
    }

    
Retrieves the next element to traverse to or null if there are
no more elements.
/**
     * Retrieves the next element to traverse to or <tt>null</tt> if there are
     * no more elements.
     */
    abstract E computeNext();
  }
}