package algorithm.datastructure.seqlist;

/*順序表
*
* 用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)各個(gè)元素，使得在邏輯結(jié)構(gòu)上相鄰的數(shù)據(jù)元素存儲(chǔ)在相鄰的物理存儲(chǔ)單元中的線性表
*
*/
public class SeqList {

  private int length;//順序表長(zhǎng)度
  private int[] list;//數(shù)組，連續(xù)的存儲(chǔ)空間

  //初始化，構(gòu)造一個(gè)空的線性表
  public SeqList(int listLength) {
    list = new int[listLength];
  }
  //銷毀表
  public void destroyList() {
    list = null;
    this.length = 0;
  }
  //將線性表置為空表
  public void clearList() {
    for (int i = 0; i < getLength(); i++) {
      list[i] = 0;
    }
  }

  //判斷線性表是否未空表
  public Boolean isEmpty() {
    return getLength() == 0;
  }

  //獲取線性表元素個(gè)數(shù)
  public int getLength() {
    return length;
  }

  //根據(jù)下標(biāo)獲取線性表元素
  public int getElem(int i) {
    if (i < 0 || i >= getLength()) {
      try {
        throw new Exception("線性表下標(biāo)越界");
      } catch (Exception e) {
        e.printStackTrace();
      }
    }
    return list[i];
  }


  //返回某元素(第一個(gè))的前驅(qū)
  public Integer priorElem(int element) {
    for (int i = 0; i < getLength(); i++) {
      if (element == list[i]) {
        if (i == 0) {
          return null;
        } else {
          return list[i - 1];
        }
      }
    }
    return null;
  }

  //獲取某元素(第一個(gè))的后繼
  public Integer nextElem(int element) {
    for (int i = 0; i < getLength(); i++) {
      if (element == list[i]) {
        if (i == getLength() - 1) {
          return null;
        } else {
          return list[i + 1];
        }
      }
    }
    return null;
  }

  //擴(kuò)容，這里設(shè)置容量變?yōu)樵瓉?lái)兩倍
  public void ensureCapacity(int capacity) {
    if (capacity >= list.length) {//擴(kuò)容
      int tempList[] = new int[list.length * 2];
      for (int i = 0; i < list.length; i++) {
        tempList[i] = list[i];
      }
      list = tempList;
    }
  }

  //在指定位置插入元素
  public Boolean insertElement(int index, int element) {
    if (index < 0 || index >= list.length) {
      try {
        throw new Exception("下標(biāo)錯(cuò)誤");
      } catch (Exception e) {
        e.printStackTrace();
      }
    }
    if (index == getLength()) {
      return insertTailElement(element);
    }
    for (int i = 0; i < getLength(); i++) {
      if (i == index) {
        ensureCapacity(getLength() + 1);
        //index位置后面的元素后移
        for (int j = getLength() - 1; j >= index; j--) {
          list[j + 1] = list[j];
        }
        list[index] = element;
        length++;
      }
    }
    return true;
  }

  //尾部插入元素
  public Boolean insertTailElement(int element) {
    ensureCapacity(length + 1);
    list[++length] = element;
    return true;
  }
  //刪除尾部元素
  public int deleteTailElement() {
    if (getLength() == 0) {
      try {
        throw new Exception("下標(biāo)錯(cuò)誤");
      } catch (Exception e) {
        e.printStackTrace();
      }
    }
    int tailElement = list[getLength() - 1];
    list[getLength() - 1] = 0;
    length--;
    return tailElement;
  }

  //刪除元素
  public int deleteElement(int index) {
    if (index < 0 || index >= list.length) {
      try {
        throw new Exception("下標(biāo)錯(cuò)誤");
      } catch (Exception e) {
        e.printStackTrace();
      }
    }
    if (index == getLength()) {
      return deleteTailElement();
    }
    for (int i = 0; i < getLength(); i++) {
      if (i == index) {
        int tailElement = list[index];
        //index位置后面的元素前移
        for (int j = index; j < getLength() - 1; j++) {
          list[j] = list[j + 1];
        }
        list[getLength() - 1] = 0;
        length--;
        return tailElement;
      }
    }
    return 0;
  }

  //遍歷順序表
  public void traverseList() {
    for (int i = 0; i < getLength(); i++) {
      System.out.println(list[i]);
    }
  }



  public static void main(String[] args) {
    //測(cè)試
    SeqList seqList = new SeqList(2);
    System.out.println(seqList.insertTailElement(1));
    System.out.println(seqList.insertTailElement(2));
    System.out.println(seqList.insertTailElement(3));
    System.out.println(seqList.insertTailElement(4));
    System.out.println(seqList.getElem(0));
    System.out.println(seqList.getElem(1));
    System.out.println(seqList.getElem(2));
    System.out.println(seqList.getElem(3));

    System.out.println(seqList.insertElement(0, 4));
    System.out.println(seqList.getElem(0));
    System.out.println(seqList.getElem(1));
    System.out.println(seqList.getElem(2));
    System.out.println(seqList.getElem(3));
    System.out.println(seqList.getElem(4));
    System.out.println(seqList.priorElem(3));
    System.out.println(seqList.priorElem(4));
    System.out.println(seqList.nextElem(4));
    System.out.println(seqList.nextElem(3));
//    System.out.println(seqList.deleteTailElement());
//    System.out.println(seqList.deleteTailElement());
//    System.out.println(seqList.deleteTailElement());
//    System.out.println(seqList.deleteTailElement());
//    System.out.println(seqList.deleteTailElement());
//    System.out.println(seqList.deleteTailElement());
    System.out.println(seqList.deleteElement(0));
    System.out.println(seqList.deleteElement(1));
    seqList.traverseList();
  }
}