'''
數(shù)據(jù)結(jié)構(gòu)起步----01----數(shù)組
'''
__author__ = 'ring04'
__date__ = '2020.11.14'

class Array:
    '''
    定義數(shù)組類
    '''
    def __init__(self, arr=None, capacity=10):
        if isinstance(arr, list):
            self._data = arr[:]
            # 默認數(shù)組容量
            self._size = len(arr)
        else:
            self._size = 0
            self._data = [None] * capacity
    def __getitem__(self, index):
        '''
        獲取數(shù)組元素
        :param index:
        :return:
        '''
        return self._data[index]
    def __setitem__(self, key, value):
        '''
        設(shè)置數(shù)組元素
        :param key:
        :param value:
        :return:
        '''
        return  self.add_last(value)

    def get_capacity(self):
        '''
        獲取數(shù)組容量
        :return:
        '''
        return len(self._data)

    def get_size(self):
        '''
        獲取數(shù)組中元素個數(shù)
        :return:
        '''
        return self._size

    def is_empty(self):
        '''
        判斷數(shù)組是否為空
        :return:
        '''
        return self._size == 0

    def add_last(self,value):
        '''
        在數(shù)組末尾插入元素
        :param value:
        :return:
        '''
        self.add(self._size,value)
    def add_first(self,value):
        '''
        在數(shù)組起始位置插入元素
        :param value:
        :return:
        '''
        self.add(0,value)

    def add(self,index,value):
        '''
        在索引為index的位置插入元素value
        :param index:
        :param value:
        :return:
        '''
        if index <0 or index > self._size:
            raise IndexError('Add failed,Required index >= 0 and index <= size')

        # 數(shù)組full搀擂，擴容
        if self._size == len(self._data):
            if self._size == 0:
                self._resize(1)
            else:
                self._resize(len(self._data) * 2)
        # index后元素后移一位
        for i in range(self._size - 1, index - 1, -1):
            self._data[i+1] = self._data[i]
        self._data[index] = value
        self._size += 1

    def get(self,index):
        '''
        獲取索引為index的元素
        :param index:
        :return:
        '''
        if index <0 or index >= self._size:
            raise IndexError("get failer,index >=0 or index < size")
        return self._data[index]

    def set(self,index,value):
        '''
        設(shè)置index索引值為value
        :param index:
        :param value:
        :return:
        '''
        if index <0 or index >= self._size:
            raise IndexError("set faile")

        self._data[index] = value

    def contains(self,value):
        '''
        查看數(shù)組中是否包含元素value
        :param value:
        :return:
        '''
        for i in range(self._size):
            if self._data[i] == value:
                return True
            else:
                return False

    def find_index(self, value):
        '''
        查找元素值value在數(shù)組中的索引
        :param value:
        :return:
        '''
        for i in range(self._size):
            if self._data[i] == value:
                return i
        return -1

    def remove(self,index):
        '''
        從數(shù)組中刪除索引為index的元素，并返回刪除元素值
        :param index:
        :return:
        '''
        if index <0 or index >= self._size:
            raise IndexError("remove failed")
        ret = self._data[index]
        #index元素之后的往前移動一位
        for i in range(index+1,self._size):
            self._data[i-1] = self._data[i]
        self._size -= 1

        # 如果數(shù)組元素小于容量的1/4卷玉，則縮小容量至現(xiàn)有的1/2
        if self._size < len(self._data) // 4 and len(self._data) // 2 != 0:
            self._resize(len(self._data) // 2)
        return ret

    def remove_first(self):
        self.remove(0)

    def remove_last(self):
        self.remove(self._size - 1)

    def remove_element(self,value):
        index = self.find_index(value)
        self.remove(index)

    def _resize(self,new_capacity):
        '''
        將數(shù)組空間容量變成new_capacity
        :param new_capacity:
        :return:
        '''
        new_data = [None] * new_capacity
        for i in range(self._size):
            new_data[i] = self._data[i]
        self._data = new_data

    def swap(self,i,j):
        '''
        交換索引為i和j兩個位置的值
        :param i:
        :param j:
        :return:
        '''
        if i <0 or i > self._size or j <0 or j > self._size:
            raise IndexError("index is illegal")
        self._data[i], self._data[j] = self._data[j],self._data[i]

if __name__ == "__main__":
    array = Array()
    for i in range(10):
        array.add_last(i)
    print("capacity: %d" % array.get_capacity())
    print("size: %d" % array.get_size())

    array.add_last(10)
    print("capacity: %d" % array.get_capacity())
    print("size: %d" % array.get_size())

    array.add(4, "ring04")

    print(array.find_index("ring04"))

    for i in range(array.get_size()):
        print(array.get(i))

    for i in range(8):
        array.remove_last()
    print("capacity: %d" % array.get_capacity())
    print("size: %d" % array.get_size())