package com.ietree.basic.datastructure.Sequence;

import java.util.Arrays;

/**
 * 順序線性表
 * 
 * @param <T>
 * @author Dylan
 */
public class SequenceList<T> {

 private final int DEFAULT_SIZE = 16;
 // 保存數(shù)組的長(zhǎng)度
 private int capacity;
 // 定義一個(gè)數(shù)組用于保存順序線性表的元素
 private Object[] elementData;
 // 保存順序表中元素的當(dāng)前個(gè)數(shù)
 private int size = 0;
 
 // 以默認(rèn)數(shù)組長(zhǎng)度創(chuàng)建順序線性表
 public SequenceList() {
  capacity = DEFAULT_SIZE;
  elementData = new Object[capacity];
 }
 
 // 以一個(gè)初始化元素創(chuàng)建順序線性表
 public SequenceList(T element) {
  this();
  elementData[0] = element;
  size++;
 }
 
 /**
  * 以指定長(zhǎng)度的數(shù)組來(lái)創(chuàng)建順序線性表
  * @param element 指定順序線性表中第一個(gè)元素
  * @param initSize 指定順序線性表底層數(shù)組的長(zhǎng)度
  */
 public SequenceList(T element, int initSize) {
  capacity = 1;
  // 把capacity設(shè)為大于initSize的最小的2的n次方
  while (capacity < initSize) {
   capacity <<= 1;
  }
  elementData = new Object[capacity];
  elementData[0] = element;
  size++;
 }
 
 // 獲取順序線性表的大小
 public int length() {
  return size;
 }
 
 // 獲取順序線性表中索引為i處的元素
 public T get(int i) {
  if (i < 0 || i > size - 1) {
   throw new IndexOutOfBoundsException("線性表索引越界");
  }
  return (T) elementData[i];
 }
 
 // 查找順序線性表中指定元素的索引
 public int locate(T element) {
  for (int i = 0; i < size; i++) {
   if (elementData[i].equals(element)) {
    return i;
   }
  }
  return -1;
 }
 
 // 向順序線性表的指定位置插入一個(gè)元素
 public void insert(T element, int index) {
  if (index < 0 || index > size) {
   throw new IndexOutOfBoundsException("線性表索引越界");
  }
  ensureCapacity(size + 1);
  // 將指定索引處之后的所有元素向后移動(dòng)一格
  System.arraycopy(elementData, index, elementData, index + 1, size - index);
  elementData[index] = element;
  size++;
 }
 
 // 在插入元素之前需要確保順序線性表的長(zhǎng)度大于插入之后順序線性表的長(zhǎng)度
 private void ensureCapacity(int minCapacity) {
  
  // 如果數(shù)組的原有長(zhǎng)度小于目前所需的長(zhǎng)度
  if (minCapacity > capacity) {
   // 不斷地將capacity * 2，直到capacity大于minCapacity
   while (capacity < minCapacity) {
    capacity <<= 1;
   }
   elementData = Arrays.copyOf(elementData, capacity);
  }
 }
 
 // 在線性順序表的開(kāi)始處添加一個(gè)元素
 public void add(T element) {
  insert(element, size);
 }
 
 // 刪除順序線性表中指定索引處的元素
 public T delete(int index) {
  if (index < 0 || index > size - 1) {
   throw new IndexOutOfBoundsException("線性表索引越界");
  }
  T oldValue = (T) elementData[index];
  int numMoved = size - index - 1;
  if (numMoved > 0) {
   System.arraycopy(elementData, index + 1, elementData, index, numMoved);
  }
  // 清空最后一個(gè)元素
  elementData[--size] = null;
  return oldValue;
 }
 
 // 刪除順序線性表中最后一個(gè)元素
 public T remove() {
  return delete(size - 1);
 }
 
 // 判斷順序線性表是否為空表
 public boolean empty() {
  return size == 0;
 }
 
 // 清空線性表
 public void clear() {
  Arrays.fill(elementData, null);
  size = 0;
 }

 public String toString() {
  if (size == 0) {
   return "[]";
  } else {
   StringBuilder sb = new StringBuilder("[");
   for (int i = 0; i < size; i++) {
    sb.append(elementData[i].toString() + ",");
   }
   int len = sb.length();
   return sb.delete(len - 2, len).append("]").toString();
  }
 }

}

package com.ietree.basic.datastructure.Sequence;

/**
 * 測(cè)試類(lèi)
 * 
 * @author Dylan
 */
public class SequenceListTest {
 
 public static void main(String[] args) {
  SequenceList<String> list = new SequenceList<String>();
  list.add("aaa");
  list.add("bbb");
  list.add("ccc");
  list.add("ddd");
  list.insert("eee", 1);
  System.out.println(list);
  list.delete(2);
  System.out.println(list);
  System.out.println("ccc在順序線性表中的位置：" + list.locate("ccc"));
 }
}

[aaa,eee,bbb,ccc,dd]
[aaa,eee,ccc,dd]