package com.chapter_one;

import java.util.Iterator;
import java.util.Random;

/***
 * API
 * 
 * @author LuodiJack RandomBag() 创建一个随机背包 boolean isEmpty() 判断随机背包是否为空 int
 *         size() 背包中元素数量 void add(Item item) 添加一个元素
 *         提示：用数组保存所有元素并在迭代器的构造函数中随机打乱它们的顺序。
 */
public class RandomBag<Item> implements Iterable<Item> {
    private int N = 0;// size
    private Item[] a;// entries
    private int last = 0;// the last element

    @SuppressWarnings("unchecked")
    public RandomBag() {
        a = (Item[]) new Object[5];
    }

    public boolean isEmpty() {
        return N == 0;
    }

    public int size() {
        return N;
    }

    private void resize(int len) {
        @SuppressWarnings("unchecked")
        Item[] tmp = (Item[]) new Object[len];
        for (int i = 0; i < a.length; i++) {
            tmp[i] = a[i];
        }
        a = tmp;
    }

    public void add(Item item) {
        if (last == a.length) {
            resize(2 * a.length);
        }
        a[last++] = item;
        N++;
    }

    public Iterator<Item> iterator() {
        return new RandomBagIterator();
    }

    private class RandomBagIterator implements Iterator<Item> {
        private int i = 0;
        @SuppressWarnings("unchecked")
        private Item[] tmp=(Item[])new Object[N];

        private void exchangeValue(int fir, int sec){
            Item item=a[fir];
            a[fir]=a[sec];
            a[sec]=item;
        }

        private void randomIndex(){
            Random randomIndex=new Random();
            int n=N;
            for(int j=0;j<N;j++){
                int index=randomIndex.nextInt(n);               
                tmp[j]=a[index];
                exchangeValue(n-1, index);
                n--;
            }

        }

        public RandomBagIterator() {
            randomIndex();
        }

        public boolean hasNext() {
            return i<N;
        }

        public Item next() {
            return tmp[i++];
        }
    }
}