package pas.hybriddeque;

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * Doubly-linked-list implementation of the java.util.Deque interface. This
 * implementation is more space-efficient than Java's LinkedList class for large
 * collections because each node contains a block of elements instead of only
 * one. This reduces the overhead required for next and previous node
 * references.
 *
 * This implementation does not allow null's to be added to the collection.
 * Adding a null will result in a NullPointerException.
 *
 * @author TODO
 * @version TODO
 *
 */
public class HybridDeque<E> extends AbstractDeque<E> {

  /*
   * IMPLEMENTATION NOTES ----------------------------------
   *
   * The list of blocks is never empty, so leftBlock and rightBlock are never
   * equal to null. The list is not circular.
   *
   * A deque's first element is at leftBlock.elements[leftIndex]
   * and its last element is at rightBlock.elements[rightIndex].
   *
   * The indices, leftIndex and rightIndex are always in the range:
   *     0 <= index < BLOCK_SIZE
   *
   * And their exact relationship is:
   *     (leftIndex + size - 1) % BLOCK_SIZE == rightIndex
   *
   * Whenever leftBlock == rightBlock, then:
   *     leftIndex + size - 1 == rightIndex
   *
   * However, when leftBlock != rightBlock, the leftIndex and rightIndex become
   * indices into distinct blocks and either may be larger than the other.
   *
   * 
   * For an EMPTY Deque, all of the following must be true:
   *     size == 0
   *     leftBlock == rightBlock
   *     leftIndex == CENTER + 1
   *     rightIndex == CENTER
   *
   * Checking for size == 0 is the intended way to see whether the Deque is empty.
   *
   *
   * (Comments above are a lightly modified version of comments in Python's deque
   * implementation:
   * https://github.com/python/cpython/blob/v3.11.2/Modules/_collectionsmodule.c
   * https://docs.python.org/3.11/license.html)
   *
   */

  private static int BLOCK_SIZE = 64;
  private static int CENTER = (BLOCK_SIZE - 1) / 2;

  private Cursor leftCursor;
  private Cursor rightCursor;
  private int size;


  /**
   * DO NOT MODIFY THIS METHOD. This will be used in grading/testing to modify the
   * default block size..
   *
   * @param blockSize The new block size
   */
  protected static void setBlockSize(int blockSize) {
    HybridDeque.BLOCK_SIZE = blockSize;
    HybridDeque.CENTER = (blockSize - 1) / 2;
  }


  /**
   * Doubly linked list node (or block) containing an array with space for
   * multiple elements.
   */
  private class Block {
    private E[] elements;
    private Block next;
    private Block prev;

    /**
     * Block Constructor.
     *
     * @param prev Reference to previous block, or null if this is the first
     * @param next Reference to next block, or null if this is the last
     */
    @SuppressWarnings("unchecked")
    public Block(Block prev, Block next) {
      this.elements = (E[]) (new Object[BLOCK_SIZE]);
      this.next = next;
      this.prev = prev;
    }

  }

  /**
   * Many of the complications of implementing this Deque class are related to the
   * fact that there are two pieces of information that need to be maintained to
   * track a position in the deque: a block reference and the index within that
   * block. This class combines those two pieces of information and provides the
   * logic for moving forward and backward through the deque structure.
   *
   * NOTE: The provided cursor class is *immutable*: once a Cursor object is
   * created, it cannot be modified. Incrementing forward or backward involves
   * creating new Cursor objects at the required location. Immutable objects can
   * be cumbersome to work with, but they prevent coding errors caused by
   * accidentally aliasing mutable objects.
   */
  private class Cursor {
    private final Block block;
    private final int index;

    public Cursor(HybridDeque<E>.Block block, int index) {
      this.block = block;
      this.index = index;
    }

    /**
     * Increment the cursor, crossing a block boundary if necessary.
     *
     * @return A new cursor at the next position, or null if there are no more valid
     *         positions.
     */
    private Cursor next() {

      if (index == BLOCK_SIZE - 1) { // We need to cross a block boundary
        if (block.next == null) {
          return null;
        } else {
          return new Cursor(block.next, 0);
        }
      } else { // Just move one spot forward in the current block
        return new Cursor(block, index + 1);
      }
    }

    /**
     * Decrement the cursor, crossing a block boundary if necessary.
     *
     * @return A new cursor at the previous position, or null if there is no
     *         previous position.
     */
    private Cursor prev() {
      if (index == 0) { // We need to cross a block boundary
        if (block.prev == null) {
          return null;
        } else {
          return new Cursor(block.prev, BLOCK_SIZE - 1);
        }
      } else { // Just move one spot back in the current block.
        return new Cursor(block, index - 1);
      }
    }

    /**
     * Two cursors are equal if they refer to the same index in the same block.
     */
    public boolean equals(Object other) {
      if (!(other instanceof HybridDeque.Cursor)) {
        return false;
      }
      @SuppressWarnings("unchecked")
      Cursor otherCursor = (Cursor) other;
      return otherCursor.block == block && otherCursor.index == index;
    }

    /**
     * Return the element stored at this cursor.
     */
    public E get() {
      return block.elements[index];
    }

    /**
     * Set the element at this cursor.
     */
    public void set(E item) {
      block.elements[index] = item;
    }

  }

  // ----------------------------------------------------
  // ADD UNIMPLEMENTED DEQUE METHODS HERE.
  // (You Don't need to provide JavaDoc comments for inherited methods. They
  // will inherit appropriate comments from Deque.)

  // -------------------------------------------------
  // METHODS THAT NEED TO BE IMPLEMENTED FOR PART 1:
  //
  // constructor
  // size
  // clear
  // offerLast
  // offerFirst
  // peekFirst
  // peekLast
  // pollFirst
  // pollLast
  // equals
  // iterator (without removal)
  // descendingIterator (without removal)

  // -------------------------------------------------
  // METHODS THAT NEED TO BE IMPLEMENTED FOR PART 2:
  //
  // removeFirstOccurrence
  // removeLastOccurrence
  // remove methods for iterators


}