package 线性表.顺序表.普通数组;

 /**

  * ArrayList 顺序表

  * JAVA 3.0

  * 抛异常处理错误的下标

  * 使用泛型,当然如果要替换成Object也是可以替换

  */

 public class ArrayList<E> {

     private int capacity; //数组的总容量

     private int current;  //当前最后一个数组元素的下一个元素下标，从0开始，也是长度

     private E[] data = null; //所有数据

     public ArrayList(){

         this(10);

     }

     public ArrayList(int initialSize){

         init(initialSize);

     }

     /**

      * 初始化数组

      */

     @SuppressWarnings("unchecked")

     public void init(int initialSize){

         current = 0;

         data = (E[])new Object[initialSize];

         capacity = initialSize;

     }

     /**

      * 数组末尾插入元素*/

     public void add(E e){

         ensureCapacity();

         data[current] = e;

         current++;

     }

     /**

      * 在数组中插入元素*/

     public void insert(int index, E e){

         validateIndex(index);

         ensureCapacity();

         for(int i=current;i>=index;i--){

             data[i+1] = data[i];

         }

         data[index] = e;

         current++;

     }

     /**

      * 判断是否需要扩展数组

      * 如果需要将扩展为原来的两倍

      */

     @SuppressWarnings("unchecked")

     private void ensureCapacity(){

         if(current == capacity){

             capacity = capacity * 2;

             E[] newData = (E[])new Object[capacity];

             for(int index = 0; index < current; ++index) {

                 newData[index] = data[index];

             }

             data = newData;

         }

     }

     /**

      * 删除某个已经存在的对象

      * 如果T在数组中，则删除成功返回true，否则无这个元素返回false

      */

     public boolean remove(E e){

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

             if(data[i].equals(e)){

                 remove(i);

                 return true;

             }

         }

         return false;

     }

     /**

      * 删除特定下标的数组

      * @param index

      */

     public void remove(int index){

         validateIndex(index);

         for(int i=index;i<current;i++){

             data[i] = data[i+1];

         }

         data[current] = null;

         current--;

     }

     /**

      * 修改下标为index的值*/

     public void set(int index, E e){

         validateIndex(index);

         data[index] = e;

     }

     /**

      * 获取下标为index的值

      */

     public E get(int index){

         validateIndex(index);

         return data[index];

     }

     /**

      * 获取数组已使用的个数

      */

     public int size(){

         return current;

     }

     /**

      * 销毁数组所有元素

      */

     public void clear(){

 //      Arrays.fill(data, null);  可以替代下面的for循环

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

             data[i] = null;

         }

         capacity = 0;

         current = 0;

     }

     /**

      * 判断数组是否为空

      */

     public boolean isEmpty(){

         return current==0;

     }

     /**

      * 打印结构

      */

     public String toString() {  

         String str = "[ ";

         for (Object o : data) {

             if (o != null) {

                 str += o + " ";

             }

         }

         str += "]";

         return str;

     }

     /** 　　 * 判断index 是否越界　　 */

     private void validateIndex(int index) {  

         if (index < 0 || index >= current) {

             throw new IndexOutOfBoundsException("无效的下标：" + index);

         }

     }