from chapter2.fibonacci import Fib
from chapter2.myarray import Array

DEFULT_CAPACITY = 3


class Vecotr:
    """
    implement of vector by python
    """
    def __init__(self, source=0, lo=None, hi=None):
        if isinstance(source, int):
            self._capacity = source
            self._elem = Array(self._capacity)
            self._size = 0
        elif isinstance(source, Array):
            self = self._copyfrom(source, lo, hi)
        elif isinstance(source, Vecotr):
            if not lo and not hi:
                self = self._copyfrom(source._elem, 0, source._size)
            else:
                self = self._copyfrom(source._elem, lo, hi)

    def __setitem__(self, index, value):
        self._expand()
        assert 0 <= index < self._capacity
        assert self._size < self._capacity   # 向量大小应小于容量
        self._elem[index] = value
        if index >= self._size:
            self._size += 1

    def _expand(self):
        if self._size < self._capacity:
            return
        # 扩容操作
        self._capacity = max([self._capacity, DEFULT_CAPACITY])
        old_elem = self._elem
        self._capacity = self._capacity << 1
        self._elem = Array(self._capacity)
        for i in range(0, self._size):
            self._elem[i] = old_elem[i]

    def _shrink(self):
        """缩容操作"""
        tmp = self._capacity / 2
        if self._size <= tmp:
            self._capacity = int(tmp)

    def __getitem__(self, index):
        assert 0 <= index < self._size
        return self._elem[index]

    def __len__(self):
        return self._size

    def __iter__(self):
        return _IterVector(self)

    def __contains__(self, item):
        for i in range(0, self._size):
            if item == self[i]:
                return True
        return False

    def insert(self, index, value):
        self._expand()
        for i in range(self._size, index, -1):
            self._elem[i] = self._elem[i-1]
        self._elem[index] = value
        self._size += 1
        return index

    def remove(self, lo, hi):
        if lo == hi:
            return
        while hi < self._size:
            self._elem[lo] = self._elem[hi]
            lo += 1
            hi += 1
        self._size = lo
        self._shrink()
        return hi - lo

    def find(self, e, lo=0, hi=None):
        if not hi:
            hi = self._size
        while lo < hi:
            hi -= 1
            if e != self._elem[hi]:
                continue
            else:
                return hi

    def remove_single(self, r):
        tmp = self._elem[r]
        self.remove(r, r+1)
        return tmp

    def deduplicate(self):
        """
        无序向量去重
        :return:
        """
        old_size = self._size
        i = 1
        while i < self._size:
            existed = self.find(self._elem[i], 0, i)
            if existed != None:
                self.remove_single(i)
            else:
                i += 1
        return old_size - self._size

    def traverse(self, visit):
        """
        vector traverse
        :param vist: function name
        :return: None
        """
        for i in range(self._size):
            tmp = visit(self._elem[i])
            self._elem[i] = tmp

    @staticmethod
    def _copyfrom(array, lo, hi):
        """
        copy from array
        :param array: Array
        :param lo: int
        :param hi: int
        :return:
        """
        assert isinstance(lo, int)
        assert isinstance(hi, int)
        _elem = Vecotr(2 * (hi - lo))
        _elem._size = 0
        _size = 0
        while lo < hi:
            _elem[_size] = array[lo]
            _size += 1
            lo += 1
        return _elem


class OrderedVector(Vecotr):

    def disordered(self):
        """
        :return: the number of disordered pair
        """
        count = 0
        for i in range(1, self._size):
            if self._elem[i - 1] > self._elem[i]:
                count += 1
        return count

    def uniquify(self):
        """有序向量去重"""
        i, j = 0, 1
        while j < self._size:
            if self._elem[i] != self._elem[j]:
                i += 1
                self._elem[i] = self._elem[j]
            j += 1

        self._size = i + 1
        self._shrink()
        return j - i

    def fib_search(self, e, lo, hi):
        fib = Fib(hi -lo)
        while lo < hi:
            while hi - lo < fib.get():
                fib.prev()

            mi = lo + fib.get() - 1
            if e < self._elem[mi]:
                hi = mi
            elif self._elem[mi] < e:
                lo = mi + 1
            else:
                k = mi + 1
                while 1:
                    if self[mi] == self[k]:
                        mi = k
                        k += 1
                    else:
                        return mi
        return -1

    def bin_search_v1(self, e, lo, hi):
        """
        binary search version A
        :param self: ordered vector
        :param e: item to search
        :param lo: int
        :param hi: int
        :return: e or -1
        """
        while lo < hi:
            mi = (lo + hi) >> 1
            if e < self[mi]:
                hi = mi
            elif self[mi] < e:
                lo = mi + 1
            else:
                k = mi + 1
                while 1:
                    if self[mi] == self[k]:
                        mi = k
                        k += 1
                    else:
                        return mi
        return -1

    def bin_search_v2(self, e, lo, hi):
        """
        binary search version B
        """
        while 1 < hi - lo:
            mi = (lo + hi) >> 1
            if e < self._elem[mi]:
                hi = mi
            else:
                lo = mi
        return lo if e == self._elem[lo] else -1

    def bin_search_v3(self, e, lo, hi):
        """
        binary search version C
        """
        while lo < hi:
            mi = (lo + hi) >> 1
            if e < self._elem[mi]:
                hi = mi
            else:
                lo = mi + 1
        return lo - 1

    def __swap(self, p1, p2):
        tmp = self._elem[p2]
        self._elem[p2] = self._elem[p1]
        self._elem[p1] = tmp

    def bubble_sort(self, lo, hi):
        """bubble sort"""
        assert hi <= self._size
        assert lo >= 0
        while lo < hi:
            hi = self.__bubble(lo, hi)

    def __bubble(self, lo, hi):
        last = lo
        lo += 1
        while lo < hi:
            if self._elem[lo - 1] > self._elem[lo]:
                last = lo
                self.__swap(lo-1, lo)
            lo += 1
        return last

    def merge_sort(self, lo, hi):
        """merge sort"""
        if hi - lo < 2:
            return
        mi = (lo + hi) >> 1
        self.merge_sort(lo, mi)
        self.merge_sort(mi, hi)
        self.__merge(lo, mi, hi)

    def __merge(self, lo, mi, hi):
        A = Vecotr(3)
        for i in range(0, hi-lo):
            A[i] = self[i + lo]

        lb = mi - lo
        B = Vecotr(lb)
        for i in range(0, lb):
            B[i] = A[i]

        lc = hi - mi
        C = Vecotr(3)
        for i in range(0, lc):
            C[i] = self[i + mi]

        i, j, k = 0, 0, 0
        while (j < lb) or (k < lc):
            if (j < lb) and (lc <= k or B[j] <= C[k]):
                A[i] = B[j]
                i += 1
                j += 1
            if (k < lc) and (lb <= j or C[k] <= B[j]):
                A[i] = C[k]
                i += 1
                k += 1

        for i in range(lo, hi):
            self[i] = A[i-lo]


class _IterVector:
    def __init__(self, vector):
        self.vector = vector
        self.cnt = 0

    def __iter__(self):
        return self

    def __next__(self):
        if self.cnt < len(self.vector):
            entry = self.vector[self.cnt]
            self.cnt += 1
            return entry
        else:
            raise StopIteration