//1.3.14

package com.qiusongde;

import java.util.Iterator;

import java.util.NoSuchElementException;

import edu.princeton.cs.algs4.StdIn;

import edu.princeton.cs.algs4.StdOut;

public class ResizingArrayQueue<Item> implements Iterable<Item> {

    private Item[] content;

    private int head;

    private int tail;

    private int n;

    public ResizingArrayQueue() {

        content = (Item[])new Object[1];

        n = head = tail = 0;

    }

    public int size() {

        return n;

    }

    public boolean isEmpty() {

        return n == 0;

    }

    private void resizeArray(int max) {

        if(max < n)

            throw new IllegalArgumentException("the size of new array must larger than the size of Queue");

        Item[] temp = (Item[]) new Object[max];

        for(int i = 0; i < n; i++) {

            temp[i] = content[(head + i) % content.length];

        }

        head = 0;

        tail = n;

        content = temp;

    }

    public void enqueue(Item item) {

        if(n == content.length) {//full

            resizeArray(content.length * 2);//double array

        }

        content[tail++] = item;

        if(tail == content.length) {

            tail = 0;//wrap around

        }

        n++;

    }

    public Item dequeue() {

        if(isEmpty()) {//empty

            throw new NoSuchElementException("Queue is empty");

        }

        Item item = content[head];

        content[head] = null;//avoid loitering

        head++;//next

        if(head == content.length) {

            head = 0;//wrap around

        }

        n--;

        if(n == content.length/4 && n > 0) {

            resizeArray(content.length/2);

        }

        return item;

    }

    @Override

    public String toString() {

        String s;

        s = "Size:" + n +  " ArrayLength:" + content.length + " head:" + head + " tail:" + tail +"\n";

        for(Item item : content) {

            s += item + " ";

        }

        s += "\n";

        return s;

    }

    @Override

    public Iterator<Item> iterator() {

        return new ResizingArrayQueueIterator();

    }

    private class ResizingArrayQueueIterator implements Iterator<Item> {

        private int number = n;//initialize

        private int start = head;//initialize

        @Override

        public boolean hasNext() {

            return number > 0;

        }

        @Override

        public Item next() {

            if(!hasNext())

                throw new NoSuchElementException("Queue is empty");

            Item item = content[start++];

            if(start == content.length)

                start = 0;//wrap around

            number--;

            return item;

        }

        @Override

        public void remove() {

            throw new UnsupportedOperationException();

        }

    }

    public static void main(String[] args) {

        ResizingArrayQueue<String> queue = new ResizingArrayQueue<String>();

        StdOut.println(queue);

        while (!StdIn.isEmpty()) {

            String item = StdIn.readString();

            if (!item.equals("-")) {

                queue.enqueue(item);

                StdOut.println("enqueue success:" + item);

                StdOut.println(queue);

            } else {

                if(queue.isEmpty())

                    StdOut.println("dequeue error, stack empty");

                else {

                    StdOut.println("dequeue success:" + queue.dequeue());

                    StdOut.println(queue);

                }

            }

        }

        StdOut.println("Left in the ResizingArrayQueue:");

        for(String s : queue) {

            StdOut.print(s + " ");

        }

        StdOut.println();

    }

}

Size:0 ArrayLength:1 head:0 tail:0

null 

to

enqueue success:to

Size:1 ArrayLength:1 head:0 tail:0

to 

or

enqueue success:or

Size:2 ArrayLength:2 head:0 tail:0

to or 

not

enqueue success:not

Size:3 ArrayLength:4 head:0 tail:3

to or not null 

to

enqueue success:to

Size:4 ArrayLength:4 head:0 tail:0

to or not to 

be

enqueue success:be

Size:5 ArrayLength:8 head:0 tail:5

to or not to be null null null 

-

dequeue success:to

Size:4 ArrayLength:8 head:1 tail:5

null or not to be null null null 

-

dequeue success:or

Size:3 ArrayLength:8 head:2 tail:5

null null not to be null null null 

-

dequeue success:not

Size:2 ArrayLength:4 head:0 tail:2

to be null null 

-

dequeue success:to

Size:1 ArrayLength:2 head:0 tail:1

be null 

-

dequeue success:be

Size:0 ArrayLength:2 head:1 tail:1

null null 

to

enqueue success:to

Size:1 ArrayLength:2 head:1 tail:0

null to 

be

enqueue success:be

Size:2 ArrayLength:2 head:1 tail:1

be to 

Left in the ResizingArrayQueue:

to be