package basictype;

import java.util.Iterator;

/**
 * A Queue which uses a rotating buffer for storing its elements.
 * The array is resized dynamically when it becomes too small 
 * for holding the elements of the queue.
 * 
 * @author Frederic Boulanger frederic.boulanger@supelec.fr
 *
 * @param <T> the type of elements in the queue
 */
public class BufferQueue<T> extends Queue<T> {
  private static final int initialCapacity = 5;
  
  private T[] buffer;
  private int queue_index;
  private int dequeue_index;
  private int size;
  private int capacity;
  
  public BufferQueue() {
    this(initialCapacity);
  }
  
  public BufferQueue(int capacity) {
    this.size = 0;
    this.queue_index = 0;
    this.dequeue_index = 0;
    this.capacity = 0;
    resize(capacity);
  }
  
  @Override
  public void enqueue(T item) {
    if (this.size == this.capacity) {
      grow();
    }
    this.buffer[this.queue_index]= item;
    this.queue_index = (this.queue_index + 1) % this.capacity;
    this.size++;
  }
  
  @Override
  public T dequeue() {
    T result = null;
    if (this.size > 0) {
      result = this.buffer[this.dequeue_index];
      this.dequeue_index = (this.dequeue_index + 1) % this.capacity;
      this.size--;
      shrink();
      return result;
    } else {
      throw new RuntimeException("Error: dequeue on empty queue.");
    }
  }
  
  @Override
  public int size() {
    return this.size;
  }
  
  @Override
  public Iterator<T> iterator() {
    return new BufferQueueIterator();
  }

  private void grow() {
    resize(this.capacity * 2);
  }
  
  private void shrink() {
    if ((this.size >= initialCapacity) && (this.capacity >= 2 * this.size)) {
      resize(this.size);
    }
  }
  
  @SuppressWarnings("unchecked")
  private void resize(int newCapacity) {
    T[] newBuffer = (T[]) new Object[newCapacity];
    for (int i = 0; i < this.size; i++) {
      newBuffer[i] = this.buffer[(this.dequeue_index + i) % this.capacity];
    }
    this.buffer = newBuffer;
    this.capacity = newCapacity;
    this.dequeue_index = 0;
    this.queue_index = this.size;
  }
  
  private class BufferQueueIterator implements Iterator <T> {
    private int currentIndex = BufferQueue.this.dequeue_index;
    private int items_to_go = BufferQueue.this.size;
    
    @Override
    public boolean hasNext() {
      return this.items_to_go > 0;
    }
    
    @Override
    public T next() {
      T result = BufferQueue.this.buffer[this.currentIndex];
      this.currentIndex = (this.currentIndex + 1) % BufferQueue.this.capacity;
      this.items_to_go--;
      return result;
    }

    @Override
    public void remove() {
      // Don't do anything, removing items from a queue is for dequeue() only!
    }
  }
  
  
  private static final String[] defaultArgs = {
    "un", "deux", "trois", "quatre", "cinq",
    "six", "sept", "huit", "neuf", "dix",
    "onze", "douze", "treize", "quatorze", "quinze"
  };

  public static void main(String[] args) {
    String[] test = args;
    if (test.length == 0) {
      test = defaultArgs;
    }
    
    Queue<String> q = new BufferQueue<String>();
    for (int i = 0; i < 5; i++) {
      q.enqueue(test[i]);
    }
    System.out.println(q.dequeue());
    for (int i = 5; i < 10; i++) {
      q.enqueue(test[i]);
    }
    System.out.println(q.dequeue());
    System.out.println(q.dequeue());
    for (int i = 10; i < 15; i++) {
      q.enqueue(test[i]);
    }
    
    System.out.println("# Iterate");
    System.out.println(q);
    
    System.out.println("# Dequeue");
    while (q.size() > 0) {
      System.out.println(q.dequeue());
    }
    
    // Should throw an exception
    // q.dequeue();
  }

}