user/super/com/google/gwt/emul/java/util/LinkedList.java

/*
 * Copyright 2008 Google Inc.
 *
 * 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 java.util;

import static javaemul.internal.InternalPreconditions.checkElement;
import static javaemul.internal.InternalPreconditions.checkPositionIndex;
import static javaemul.internal.InternalPreconditions.checkState;

import java.io.Serializable;

/**
 * Linked list implementation. <a
 * href="http://java.sun.com/j2se/1.5.0/docs/api/java/util/LinkedList.html">[Sun
 * docs]</a>
 *
 * @param <E> element type.
 */
public class LinkedList<E> extends AbstractSequentialList<E> implements
    Cloneable, List<E>, Deque<E>, Serializable {
  /*
   * This implementation uses a doubly-linked list with a header/tail node.
   *
   * TODO(jat): add more efficient subList implementation.
   */

  private final class DescendingIteratorImpl implements Iterator<E> {
    private final ListIterator<E> itr = new ListIteratorImpl(size, tail);

    @Override
    public boolean hasNext() {
      return itr.hasPrevious();
    }

    @Override
    public E next() {
      return itr.previous();
    }

    @Override
    public void remove() {
      itr.remove();
    }
  }

  /**
   * Implementation of ListIterator for linked lists.
   */
  private final class ListIteratorImpl implements ListIterator<E> {

    /**
     * The index to the current position.
     */
    protected int currentIndex;

    /**
     * Current node, to be returned from next.
     */
    protected Node<E> currentNode;

    /**
     * The last node returned from next/previous, or null if deleted or never
     * called.
     */
    protected Node<E> lastNode = null;

    /**
     * @param index from the beginning of the list (0 = first node)
     * @param startNode the initial current node
     */
    public ListIteratorImpl(int index, Node<E> startNode) {
      currentNode = startNode;
      currentIndex = index;
    }

    @Override
    public void add(E o) {
      addNode(o, currentNode.prev, currentNode);
      ++currentIndex;
      lastNode = null;
    }

    @Override
    public boolean hasNext() {
      return currentNode != tail;
    }

    @Override
    public boolean hasPrevious() {
      return currentNode.prev != header;
    }

    @Override
    public E next() {
      checkElement(hasNext());

      lastNode = currentNode;
      currentNode = currentNode.next;
      ++currentIndex;
      return lastNode.value;
    }

    @Override
    public int nextIndex() {
      return currentIndex;
    }

    @Override
    public E previous() {
      checkElement(hasPrevious());

      lastNode = currentNode = currentNode.prev;
      --currentIndex;
      return lastNode.value;
    }

    @Override
    public int previousIndex() {
      return currentIndex - 1;
    }

    @Override
    public void remove() {
      checkState(lastNode != null);

      Node<E> nextNode = lastNode.next;
      removeNode(lastNode);
      if (currentNode == lastNode) {
        // We just did a previous().
        currentNode = nextNode;
      } else {
        // We just did a next().
        --currentIndex;
      }
      lastNode = null;
    }

    @Override
    public void set(E o) {
      checkState(lastNode != null);

      lastNode.value = o;
    }
  }

  /**
   * Internal class representing a doubly-linked list node.
   *
   * @param <E> element type
   */
  private static class Node<E> {
    public Node<E> next;
    public Node<E> prev;
    public E value;
  }

  /**
   * Ensures that RPC will consider type parameter E to be exposed. It will be
   * pruned by dead code elimination.
   */
  @SuppressWarnings("unused")
  private E exposeElement;

  /**
   * Header node - header.next is the first element of the list.
   */
  private final Node<E> header = new Node<E>();

  /**
   * Tail node - tail.prev is the last element of the list.
   */
  private final Node<E> tail = new Node<E>();

  /**
   * Number of nodes currently present in the list.
   */
  private int size;

  public LinkedList() {
    reset();
  }

  public LinkedList(Collection<? extends E> c) {
    reset();
    addAll(c);
  }

  @Override
  public boolean add(E o) {
    addLast(o);
    return true;
  }

  @Override
  public void addFirst(E o) {
    addNode(o, header, header.next);
  }

  @Override
  public void addLast(E o) {
    addNode(o, tail.prev, tail);
  }

  @Override
  public void clear() {
    reset();
  }

  private void reset() {
    header.next = tail;
    tail.prev = header;
    header.prev = tail.next = null;
    size = 0;
  }

  public Object clone() {
    return new LinkedList<E>(this);
  }

  @Override
  public Iterator<E> descendingIterator() {
    return new DescendingIteratorImpl();
  }

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

  @Override
  public E getFirst() {
    checkElement(size != 0);

    return header.next.value;
  }

  @Override
  public E getLast() {
    checkElement(size != 0);

    return tail.prev.value;
  }

  @Override
  public ListIterator<E> listIterator(final int index) {
    checkPositionIndex(index, size);

    Node<E> node;
    // start from the nearest end of the list
    if (index >= size >> 1) {
      node = tail;
      for (int i = size; i > index; --i) {
        node = node.prev;
      }
    } else {
      node = header.next;
      for (int i = 0; i < index; ++i) {
        node = node.next;
      }
    }

    return new ListIteratorImpl(index, node);
  }

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

  @Override
  public boolean offerFirst(E e) {
    addFirst(e);
    return true;
  }

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

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

  @Override
  public E peekFirst() {
    return size == 0 ? null : getFirst();
  }

  @Override
  public E peekLast() {
    return size == 0 ? null : getLast();
  }

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

  @Override
  public E pollFirst() {
    return size == 0 ? null : removeFirst();
  }

  @Override
  public E pollLast() {
    return size == 0 ? null : removeLast();
  }

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

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

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

  @Override
  public E removeFirst() {
    checkElement(size != 0);

    return removeNode(header.next);
  }

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

  @Override
  public E removeLast() {
    checkElement(size != 0);

    return removeNode(tail.prev);
  }

  @Override
  public boolean removeLastOccurrence(Object o) {
    for (Node<E> e = tail.prev; e != header; e = e.prev) {
      if (Objects.equals(e.value, o)) {
        removeNode(e);
        return true;
      }
    }
    return false;
  }

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

  private void addNode(E o, Node<E> prev, Node<E> next) {
    Node<E> node = new Node<E>();
    node.value = o;
    node.prev = prev;
    node.next = next;
    next.prev = prev.next = node;
    ++size;
  }

  private E removeNode(Node<E> node) {
    E oldValue = node.value;
    node.next.prev = node.prev;
    node.prev.next = node.next;
    node.next = node.prev = null;
    node.value = null;
    --size;
    return oldValue;
  }
}