'''
数据结构起步----01----数组
'''
__author__ = 'ring04'
__date__ = '2020.11.14'

class Array:
    '''
    定义数组类
    '''
    def __init__(self, arr=None, capacity=10):
        if isinstance(arr, list):
            self._data = arr[:]
            # 默认数组容量
            self._size = len(arr)
        else:
            self._size = 0
            self._data = [None] * capacity
    def __getitem__(self, index):
        '''
        获取数组元素
        :param index:
        :return:
        '''
        return self._data[index]
    def __setitem__(self, key, value):
        '''
        设置数组元素
        :param key:
        :param value:
        :return:
        '''
        return  self.add_last(value)

    def get_capacity(self):
        '''
        获取数组容量
        :return:
        '''
        return len(self._data)

    def get_size(self):
        '''
        获取数组中元素个数
        :return:
        '''
        return self._size

    def is_empty(self):
        '''
        判断数组是否为空
        :return:
        '''
        return self._size == 0

    def add_last(self,value):
        '''
        在数组末尾插入元素
        :param value:
        :return:
        '''
        self.add(self._size,value)
    def add_first(self,value):
        '''
        在数组起始位置插入元素
        :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')

        # 数组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):
        '''
        设置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):
        '''
        查看数组中是否包含元素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在数组中的索引
        :param value:
        :return:
        '''
        for i in range(self._size):
            if self._data[i] == value:
                return i
        return -1

    def remove(self,index):
        '''
        从数组中删除索引为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

        # 如果数组元素小于容量的1/4，则缩小容量至现有的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):
        '''
        将数组空间容量变成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())