#通過python實現動態(tài)數組
 
"""
數組特點：
  占用一段連續(xù)的內存空間，支持隨機（索引）訪問，且時間復雜度為O(1)
  添加元素時間復雜度：O(n)
  刪除元素時間復雜度：O(n)
"""
 
class Arr:
  def __init__(self, capacity=10):
    """
    構造函數
    :param capacity: 數組最大容量，不指定的話默認為10
    """
    self._capacity = capacity
    self._size = 0                 # 數組有效元素的數目，初始化為0
    self._data = [None] * self._capacity  # 由于python的list是動態(tài)擴展的，而我們要實現底層具有固定容量、占用一段連續(xù)的內存空間的數組，所以用None來作為無效元素的標識
 
  def __getitem__(self, item):
    """讓Arr類支持索引操作"""
    return self._data[item]
 
  def getSize(self):
    """返回數組有效元素的個數"""
    return self._size
 
  def getCapacity(self):
    """返回當前數組的容量"""
    return self._capacity
 
  def isEmpty(self):
    """判斷當前數組是否為空"""
    return self._size == 0
 
  def add(self, index, elem):
    """
    向數組中添加一個元素，注意數組占用的是一段連續(xù)的內存空間，所以在添加元素后，數組還是要保證這個特點的，因此需要將后面的元素都向后挪一個位置，而且要注意要先從
    尾部開始挪，防止元素之間的覆蓋
    時間復雜度：O(n)
    :param index:  添加的元素所在的索引
    :param elem:  所要添加的元素
    """
    if index < 0 or index > self._size:   # 插入的位置無效
      raise Exception('Add Filed. Require 0 <= index <= self._size')
    if self._size == self._capacity:    # 滿了
      self._resize(self._capacity * 2)  # 默認擴容當前容量的二倍。容量翻倍要比容量加上一個固定值要好，這樣做均攤復雜度為O(1)。具體請百度
 
    for i in range(self._size - 1, index - 1, -1): # 從尾部開始挪動元素，在index處騰出一個空間
                            # 一定要注意在步長為負數的情況下，區(qū)間是左開右閉區(qū)間，即(index, self._size - 1]，所以是index-1，與正常的左閉右開區(qū)間是相反的！
      self._data[i + 1] = self._data[i]
    self._data[index] = elem    # 將該位置賦值為elem
    self._size += 1         # 數組有效元素數加1
 
  def addLast(self, elem):
    """
    向數組尾部添加元素
    時間復雜度：O(1)
    :param elem: 所要添加的元素
    """
    self.add(self._size, elem) # 直接調用add方法，注意不用再次判定合法性了，因為add函數中已經判斷過了
 
  def addFirst(self, elem):
    """
    想數組頭部添加元素
    時間復雜度：O(n)
    :param elem: 所要添加的元素
    """
    self.add(0, elem)  # 同理直接調用add方法
 
  def get(self, index):
    """
    獲得索引index處的元素
    時間復雜度：O(1)
    :param index: 數組索引
    :return:   數組索引處的值
    """
    if index < 0 or index >= self._size:    # 判斷index的合法性
      raise Exception('Get failed. Index is illegal.')
    return self._data[index]
 
  def getFirst(self):
    """
    獲得數組首位置元素的值
    :return: 首位置元素的值
    """
    return self.get(0)   # 直接調用get函數，安全可靠
 
  def getLast(self):
    """
    獲得數組末尾元素的值
    :return: 末尾元素的值
    """
    return self.get(self._size - 1) # 直接調用get函數，安全可靠
 
  def set(self, index, elem):
    """
    將索引為index的元素的值設為elem
    時間復雜度：O(1)
    :param index: 索引
    :param elem:  新的值
    """
    if index < 0 or index >= self._size:    # 判斷index的合法性
      raise Exception('Sat failed. Index is illegal.')
    self._data[index] = elem
 
  def contains(self, elem):
    """
    查看數組中是否存在元素elem，最好不要傳入一個浮點數，你懂得。。
    時間復雜度：O(n)
    :param elem: 目標元素
    :return:   bool值，存在為真
    """
    for i in range(self._size):    # 遍歷
      if self._data[i] == elem:
        return True        # 找到了就返回True
    return False            # 遍歷完了還沒找到，就返回False
 
  def find(self, elem):
    """
    在數組中查找元素，并返回元素所在的索引。（如果數組中存在多個elem，只返回最左邊elem的索引）
    時間復雜度：O(n)
    :param elem: 目標元素
    :return:   元素所在的索引，沒找到則返回-1（無效值）
    """
    for i in range(self._size):     # 遍歷數組
      if self._data[i] == elem:
        return i          # 找到就返回索引
    return -1              # 沒找到返回-1
 
  def findAll(self, elem):
    """
    找到值為elem全部元素的索引
    :param elem: 目標元素
    :return:   一個列表，值為全部elem的索引
    """
    ret_list = Arr()        # 建立一個新的數組用于存儲索引值
    for i in range(self._size):   # 遍歷數組
      if self._data[i] == elem:
        ret_list.addLast(i)   # 找到就將索引添加進ret_list
    return ret_list
 
  def remove(self, index):
    """
    刪除索引為index的元素。index后面的元素都要向前移動一個位置
    時間復雜度：O(n)
    :param index: 目標索引
    :return:   位于該索引的元素的值
    """
    if index < 0 or index >= self._size:  # index合法性檢查
      raise Exception('Remove failed.Require 0 <= index < self._size')
    ret = self._data[index]         # 拷貝一下index處的元素，便于返回
    for i in range(index + 1, self._size): # index后面的元素都向前挪一個位置
      self._data[i - 1] = self._data[i]
    self._size -= 1     # 維護self._size
    self._data[self._size] = None  # 最后一個元素的垃圾回收
 
    if self._size and self._capacity // self._size == 4:  # 如果當前有效元素為總容量的四分之一且還存在有效元素，則將容量縮減為原來的一半
      self._resize(self._capacity // 2)
    return ret
 
  def removeFirst(self):
    """
    刪除數組首位置的元素
    時間復雜度：O(n)
    :return: 數組首位置的元素
    """
    return self.remove(0)  # 調用remove函數
 
  def removeLast(self):
    """
    刪除數組末尾的元素
    時間復雜度:O(1)
    :return: 數組末尾的元素
    """
    return self.remove(self._size - 1)   # 調用remove函數
 
  def removeElement(self, elem):
    """
    刪除數組中為elem的元素，如果數組中不存在elem，那么什么都不做。如果存在多個相同的elem，只刪除最左邊的那個
    時間復雜度：O(n)
    :param elem: 要刪除的目標元素
    """
    index = self.find(elem)     # 嘗試找到目標元素（最左邊的）的索引
    if index != -1:         # elem在數組中就刪除，否則什么都不做
      self.remove(index)     # 調用remove函數
 
  def removeAllElement(self, elem):
    """
    刪除數組內所有值為elem的元素，可以用遞歸來寫，這里用的迭代的方法。elem不存在就什么都不做
    :param elem: 要刪除的目標元素
    """
    while True:
      index = self.find(elem)   # 循環(huán)來找elem，如果還存在就繼續(xù)刪除
      if index != -1:       # 若存在
        self.remove(index)
      else:
        break
 
  def get_Max_index(self):
    """
    獲取數組中的最大元素的索引，返回最大元素的索引值，如果有多個最大值，默認返回最左邊那個的索引
    時間復雜度：O(n)
    :return: 最大元素的索引
    """
    if self.isEmpty():
      raise Exception('Error, array is Empty!')
    max_elem_index = 0  # 記錄最大值的索引，初始化為0 
    for i in range(1, self.getSize()):  # 從索引1開始遍歷，一直到數組尾部
      if self._data[i] > self._data[max_elem_index]:  # 如果當前索引的值大于最大值索引處元素的值
        max_elem_index = i   # 更新max_elem_index，這樣它還是當前最大值的索引
    return max_elem_index   # 遍歷完后，將數組的最大值的索引返回
 
  def removeMax(self):
    """
    刪除數組中的最大元素，返回最大元素的值，如果有多個最大值，默認值刪除最左邊那個
    時間復雜度：O(n)
    :return: 最大元素
    """
    return self.remove(self.get_Max_index())  # 直接調用remove函數刪除最大值
 
  def get_Min_index(self):
    """
    獲取數組中的最小元素的索引，返回最小元素的索引值，如果有多個最小值，默認返回最左邊那個的索引
    時間復雜度：O(n)
    :return: 最小元素的索引
    """
    if self.isEmpty():
      raise Exception('Error, array is Empty!')
    min_elem_index = 0  # 記錄最小值的索引，初始化為0 
    for i in range(1, self.getSize()):  # 從索引1開始遍歷，一直到數組尾部
      if self._data[i] < self._data[min_elem_index]:  # 如果當前索引的值小于最小值索引處元素的值
        min_elem_index = i   # 更新min_elem_index，這樣它還是當前最小值的索引
    return min_elem_index   # 遍歷完后，將數組的最小值的索引返回
 
  def removeMin(self):
    """
    刪除數組中的最小元素，返回最小元素的值，如果有多個最小值，默認值刪除最左邊那個
    時間復雜度：O(2n)，可以看成是O(n)的
    :return: 最小元素
    """
    return self.remove(self.get_Min_index())
 
  def swap(self, index1, index2):
    """
    交換分別位于索引index1和索引index2處的元素
    :param index1: 索引1
    :param index2: 索引2
    """ 
    if index1 < 0 or index2 < 0 or index1 >= self._size or index2 >= self._size:    # 合法性檢查
      raise Exception('Index is illegal')
    self._data[index1], self._data[index2] = self._data[index2], self._data[index1]   # 交換元素
 
  def printArr(self):
    """對數組元素進行打印"""
    for i in range(self._size):
      print(self._data[i], end=' ')
    print('\nSize: %d-----Capacity: %d' % (self.getSize(), self.getCapacity()))
 
  # private
  def _resize(self, new_capacity):
    """
    數組容量放縮至new_capacity，私有成員函數
    :param new_capacity: 新的容量
    """
    new_arr = Arr(new_capacity)     # 建立一個新的數組new_arr，容量為new_capacity
    for i in range(self._size):
      new_arr.addLast(self._data[i]) # 將當前數組的元素按當前順序全部移動到new_arr中
    self._capacity = new_capacity    # 數組容量變?yōu)閚ew_capacity
    self._data = new_arr._data     # 將new_arr._data賦值給self._data，從而完成數組的容量放縮操作

import Array 
import numpy as np
np.random.seed(7)
test = Array.Arr()
print(test.getSize())
print(test.getCapacity())
print(test.isEmpty())
for i in range(8):
  test.add(0, np.random.randint(5))
test.printArr()
test.addLast(2)
test.printArr()
print(test.get(3))
test.set(3, 10)
test.printArr()
print(test.contains(10))
print(test.find(4))
test.findAll(1).printArr()
test.remove(3)
test.printArr()
test.removeFirst()
test.removeLast()
test.printArr()
test.removeElement(4)
test.printArr()
test.removeAllElement(3)
test.printArr()
for i in range(30):
  test.addLast(np.random.randint(10))
test.printArr()
print(test[3])
test.swap(0, 1)
test.printArr()