// Copyright 2012 Square, Inc.
package com.squareup.tape2;

import java.io.IOException;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.NoSuchElementException;

final class InMemoryObjectQueue<T> extends ObjectQueue<T> {
  // LinkedList can be used both as a List (for get(n)) and Queue (for peek() and remove()).
  @Private final LinkedList<T> entries;
  /**
   * The number of times this file has been structurally modified — it is incremented during {@link
   * #remove(int)} and {@link #add(Object)}. Used by {@link InMemoryObjectQueue.EntryIterator} to
   * guard against concurrent modification.
   */
  @Private int modCount = 0;
  private boolean closed;

  InMemoryObjectQueue() {
    entries = new LinkedList<T>();
  }

  @Override public QueueFile file() {
    return null;
  }

  @Override public void add(T entry) throws IOException {
    if (closed) throw new IOException("closed");
    modCount++;
    entries.add(entry);
  }

  @Override public T peek() throws IOException {
    if (closed) throw new IOException("closed");
    return entries.peek();
  }

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

  @Override public void remove(int n) throws IOException {
    if (closed) throw new IOException("closed");
    modCount++;
    for (int i = 0; i < n; i++) {
      entries.remove();
    }
  }

  /**
   * Returns an iterator over entries in this queue.
   *
   * <p>The iterator disallows modifications to the queue during iteration. Removing entries from
   * the head of the queue is permitted during iteration using{@link Iterator#remove()}.
   */
  @Override public Iterator<T> iterator() {
    return new EntryIterator();
  }

  @Override public void close() throws IOException {
    closed = true;
  }

  private final class EntryIterator implements Iterator<T> {
    /** Index of element to be returned by subsequent call to next. */
    int nextElementIndex = 0;

    /**
     * The {@link #modCount} value that the iterator believes that the backing QueueFile should
     * have. If this expectation is violated, the iterator has detected concurrent modification.
     */
    int expectedModCount = modCount;

    @Private EntryIterator() {

    }

    @Override public boolean hasNext() {
      checkForComodification();

      return nextElementIndex != size();
    }

    @Override public T next() {
      if (closed) throw new IllegalStateException("closed");
      checkForComodification();

      if (nextElementIndex >= size()) throw new NoSuchElementException();

      return entries.get(nextElementIndex++);
    }

    @Override public void remove() {
      if (closed) throw new IllegalStateException("closed");
      checkForComodification();

      if (size() == 0) throw new NoSuchElementException();
      if (nextElementIndex != 1) {
        throw new UnsupportedOperationException("Removal is only permitted from the head.");
      }

      try {
        InMemoryObjectQueue.this.remove();
      } catch (IOException e) {
        throw new RuntimeException("todo: throw a proper error", e);
      }

      expectedModCount = modCount;
      nextElementIndex--;
    }

    private void checkForComodification() {
      if (modCount != expectedModCount) throw new ConcurrentModificationException();
    }
  }
}
@@ -73,32 +73,89 @@
 io.IOException;%0A
+import java.util.ArrayDeque;%0Aimport java.util.ArrayList;%0A
 import java.util
@@ -180,32 +180,56 @@
 ationException;%0A
+import java.util.Deque;%0A
 import java.util
@@ -256,22 +256,16 @@
 va.util.
-Linked
 List;%0Aim
@@ -370,103 +370,9 @@
 %7B%0A  
-// LinkedList can be used both as a List (for get(n)) and Queue (for peek() and remove()).%0A  @P
+p
 riva
@@ -380,26 +380,21 @@
 e final 
-LinkedList
+Deque
 %3CT%3E entr
@@ -756,20 +756,19 @@
 new 
-LinkedList%3CT
+ArrayDeque%3C
 %3E();
@@ -971,16 +971,20 @@
 ries.add
+Last
 (entry);
@@ -1110,17 +1110,121 @@
 ies.peek
-(
+First();%0A  %7D%0A%0A  @Override public List%3CT%3E asList() throws IOException %7B%0A    return new ArrayList%3C%3E(entries
 );%0A  %7D%0A%0A
@@ -1457,32 +1457,37 @@
   entries.remove
+First
 ();%0A    %7D%0A  %7D%0A%0A 
@@ -1815,16 +1815,34 @@
 terator(
+entries.iterator()
 );%0A  %7D%0A%0A
@@ -1987,95 +1987,61 @@
     
-/** Index of element to be returned by subsequent call to next. */%0A    int nextElementI
+private final Iterator%3CT%3E delegate;%0A    private int i
 ndex
@@ -2260,16 +2260,24 @@
  */%0A    
+private 
 int expe
@@ -2329,20 +2329,71 @@
 terator(
-) %7B%0A
+Iterator%3CT%3E delegate) %7B%0A      this.delegate = delegate;
 %0A    %7D%0A%0A
@@ -2457,33 +2457,32 @@
 modification();%0A
-%0A
       return nex
@@ -2482,32 +2482,24 @@
 urn 
-nextElementIndex != size
+delegate.hasNext
 ();%0A
@@ -2642,119 +2642,46 @@
    i
-f (nextElementI
 ndex 
-%3E= size()) throw new NoSuchElementException();%0A%0A      return entries.get(nextElementIndex++
++= 1;%0A      return delegate.next(
 );%0A 
@@ -2886,28 +2886,17 @@
     if (
-nextElementI
+i
 ndex != 
@@ -3212,26 +3212,18 @@
     
-nextElementIndex--
+index -= 1
 ;%0A  

Switch in-memory queue to superior array-backed deque.