public class Array<E>{
  private E[] data; //开辟一个数组
  private int size; //指向第一个没有元素的索引，也代表数组中有多少个有效的元素

  /**
   * 有参构造函数
   * @param capacity 数组的容量
   */

  public Array(int capacity){
      data = (E[])new Object[capacity];
      size = 0;
  }

  /**
   * 默认构造函数,默认容量给10
   */
  public Array(){
      this(10);
  }

  /**
   * 获取数组中的元素个数
   * @return元素个数
   */

  public int getSize(){
      return size;
  }

  /**
   * 获取数组的容量
   * @return数组的大小
   */

  public int getCapacity(){
      return data.length;
  }

  /**
   * 返回数组是否为空
   * @return 数组是否为空
   */

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

  /**
   * 插入新元素
   * @param index 在index插入
   * @param e 新元素的值
   */
  public void add(int index, E e){

      //index不能为负,index如果大于size说明数组不是紧密排列的,则不合法
      if(index < 0 || index > size){
          throw new IllegalArgumentException("add() failed. Require index >= 0 && index <= size");
      }
      if(size == data.length){ //如果此时元素个数等于数组长度，则进行动态扩容
          resize(2 * data.length);
      }
      //将元素往后挪动
      for(int i = size-1 ; i >= index ; i-- ){
          data[i+1] = data[i];
      }
      data[index] = e;
      size ++;
  }

  /**
   * 向所有元素后添加一个新元素
   * @param e 要插入的元素
   */

  public void addLast(E e){
     add(size,e);
  }


  /**
   * 在数组头部插入一个元素
   * @param index
   * @return 元素位置
   */
  public void addFirst(E e){
      add(0,e);
  }

  /**
   * 获取index位置的元素
   * @param index 要获取的元素的索引
   * @return 元素值
   */

  public E get(int index){
      if(index < 0 || index >= size){
          throw new IllegalArgumentException("Get failed,Index is illegal");
      }
      return data[index];
  }

  /**
   * 获取最后一个元素
   * @return 最后一个元素
   */
  public E getLast(){
      return get(size - 1);
  }

  /**
   * 获取第一个元素
   * @return 第一个元素
   */
  public E getFirst(){
      return get(0);
  }

  /**
   * 修改Index索引位置的元素为e
   * @param index 要修改的元素的索引
   * @param e 要修改的元素的值
   */

  void set(int index,E e){
      if(index < 0 || index >= size){
          throw new IllegalArgumentException("Set failed,Index is illegal");
      }
      data[index] = e;
  }

  /**
   *查找数组中是否含有元素e
   * @param e 要查找的元素的值
   * @return true or false
   */

  public boolean contains(E e){
      for(int i = 0 ; i < size ; i++){
          if(data[i].equals(e))
              return true;
      }
      return false;
  }

  /**
   * 查找数组中元素e所在的索引,如果不存在则返回-1
   * @param e 要查找的元素的值
   * @return 返回索引或者-1
   */

  public int find(E e){
      for(int i = 0 ; i < size ; i++){
          if(data[i].equals(e))
              return i;
      }
      return -1;
  }

  /**
   * 从数组中删除第一个元素elem
   * @param elem
   * @return true or false
   */
  public boolean removeElement(E elem){
      int index = find(elem);
      if(index != -1){
          remove(index);
          return true;
      }
      return false;
  }

  /**
   * 删除Index位置的元素,返回index位置的元素
   * @param index 要删除的索引位置的值
   * @return 返回删除的元素的值
   */

  public E remove(int index){
      if(index < 0 || index >= size){
          throw new IllegalArgumentException("Remove failed.Index is illegal");
      }
      E temp = data[index];
      for(int i = index + 1  ; i < size ; i++){
          data[i - 1] = data[i];
      }
      size --;
      data[size] = null; // loitering objects. 释放size位置的内容(非必须，因为访问不到)

      if(size == data.length / 4 && data.length / 2 != 0){ //如果删除元素过多，少于四分之一则数组缩小容量
          resize(data.length / 2);
      }
      return temp;
  }

  /**
   * 删除第一个元素
   * @return
   */

  public E removeFirst(){
      return remove(0);
  }

  /**
   * 删除数组中最后一个元素
   * @return
   */

  public E removeLast(){
      return remove(size-1);
  }

  /**
   * 覆盖父类的方法,定义本类在打印输出时打印的信息
   * @return 打印输出数组字符串
   */
  @Override
  public String toString(){
      StringBuilder res = new StringBuilder();
      res.append(String.format("Array: size = %d,capacity = %d\n",size,data.length));
      res.append('[');
      for(int i = 0 ; i < size ; i ++){
          res.append(data[i]);
          if(i != size - 1)
              res.append(",");
      }
      res.append(']');
      return res.toString();
  }

  /**
   * 扩容数组
   * @param newCapacity 新的数组的大小
   */

  private void resize(int newCapacity){
      E[] newData =(E[]) new Object[newCapacity];
      for(int i = 0 ;i < size ; i++) {
          newData[i] = data[i];
      }
      data = newData;
  }
}