/**
 * Description 順序表
 * Date 2017-09-02
 * Author Edgar
 */
public class Sequence<E> {
    //存儲元素的數(shù)組
    private Object[] elem;
    //數(shù)組的容量
    private int capacity;
    //順序表的實際大小
    private int size;

    public Sequence(int capacity){
        if (capacity<0){
            throw new RuntimeException("初始容量不能小于0");
        }
        this.capacity=capacity;
        elem=new Object[capacity];
        size =0;
    }

    public Sequence(){
       this(10);
    }

    /**
     * 獲取指定位置的元素
     * @param index
     * @return
     */
    public E get(int index){
        checkIndexBounds(index);
        return (E) elem[index];
    }

    /**
     * 查找某元素在順序表中是否存在
     * @param e
     * @return 存在則返回下標若专，否則返回-1
     */
    public int find(E e){
        for (int i = 0; i < size; i++) {
            if (elem[i]==e){
                return i;
            }
        }
        return -1;
    }

    /**
     * 向指定位置添加元素
     * @param e
     * @param index
     * @return
     */
    public boolean add(E e,int index) {
        if (index<0 || index>size){
            return false;
        }
        checkCapacity();
        for (int i = size -1; i>=index; i--){
            elem[i+1]=elem[i];
        }
        elem[index]=e;
        size++;
        return true;
    }

    /**
     * 向順序表尾巴添加元素
     * @param e
     */
    public void add(E e){
        checkCapacity();
        elem[size++]=e;
    }

    /**
     * 移除指定位置的元素
     * @param index
     */
    public void remove(int index){
        checkIndexBounds(index);
        for (int i = index; i< size -1; i++){
            elem[i]=elem[i+1];
        }
        elem[--size]=null;
    }

    /**
     * 移除順序表中最后一個元素
     */
    public void remove(){
        elem[--size]=null;
    }

    /**
     * 修改指定位置上的元素
     * @param e
     * @param index
     */
    public void set(E e,int index){
        checkIndexBounds(index);
        elem[index]=e;
    }

    public int size(){
        return size;
    }

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

    /**
     * 若順序表大小超過數(shù)組容量棘街，則根據(jù)下面的增長策略增加數(shù)組容量脑题，并拷貝原來的數(shù)組
     */
    private void checkCapacity(){
        if (size>=capacity){
            capacity=capacity+(int) (capacity*0.5f);
            elem= Arrays.copyOf(elem,capacity);
        }
    }

    /**
     * 檢查數(shù)組下標是否越界
     * @param index
     */
    private void checkIndexBounds(int index){
        if (index<0 || index >= size){
            throw new IndexOutOfBoundsException();
        }
    }
}