# Copyright (C) 2022 Exaloop Inc. <https://exaloop.io>

import internal.gc as gc

@extend
class List:
    def __init__(self):
        self.arr = Array[T](10)
        self.len = 0

    def __init__(self, it: Generator[T]):
        self.arr = Array[T](10)
        self.len = 0
        for i in it:
            self.append(i)

    def __init__(self, other: List[T]):
        self.arr = Array[T](other.len)
        self.len = 0
        for i in other:
            self.append(i)

    def __init__(self, capacity: int):
        self.arr = Array[T](capacity)
        self.len = 0

    def __init__(self, dummy: bool, other):
        """Dummy __init__ used for list comprehension optimization"""
        if hasattr(other, "__len__"):
            self.__init__(other.__len__())
        else:
            self.__init__()

    def __init__(self, arr: Array[T], len: int):
        self.arr = arr
        self.len = len

    def _get(self, idx: int):
        return self.arr.ptr[idx]

    def _set(self, idx: int, val: T):
        self.arr.ptr[idx] = val

    def __len__(self) -> int:
        return self.len

    def __bool__(self) -> bool:
        return self.__len__() > 0

    def __getitem__(self, idx: int) -> T:
        if idx < 0:
            idx += self.__len__()
        self._idx_check(idx, "list index out of range")
        return self._get(idx)

    def __setitem__(self, idx: int, val: T):
        if idx < 0:
            idx += self.__len__()
        self._idx_check(idx, "list assignment index out of range")
        self._set(idx, val)

    def __delitem__(self, idx: int):
        if idx < 0:
            idx += self.__len__()
        self._idx_check(idx, "list assignment index out of range")
        while idx < self.len - 1:
            self._set(idx, self._get(idx + 1))
            idx += 1
        self.len -= 1

    def __eq__(self, other: List[T]) -> bool:
        if self.__len__() != other.__len__():
            return False
        for i in range(self.__len__()):
            if self._get(i) != other._get(i):
                return False
        return True

    def __ne__(self, other: List[T]) -> bool:
        return not (self == other)

    def __getitem__(self, s: Slice) -> List[T]:
        if s.start is None and s.stop is None and s.step is None:
            return self.__copy__()
        if s.step is None:
            start, stop, step, length = s.adjust_indices(self.__len__())
            return List[T](self._copy_arr(start, stop, length), length)
        else:
            start, stop, step, length = s.adjust_indices(self.__len__())
            other = List[T](length)
            for i in range(start, stop, step):
                other.append(self._get(i))
            return other

    def __setitem__(self, s: Slice, other):
        if s.start is None and s.stop is None and s.step is None:
            self.clear()
            for a in other:
                self.append(a)
            return

        start, stop, step, length = s.adjust_indices(self.__len__())
        if s.step is None or step == 1:
            if isinstance(other, List[T]):
                if other is self:
                    other = other.__copy__()
                self._assign_slice(start, stop, other.arr.ptr, other.__len__())
            else:
                items = [a for a in other]
                self._assign_slice(start, stop, items.arr.ptr, items.__len__())
        else:
            if (step < 0 and start < stop) or (step > 0 and start > stop):
                stop = start

            seq: Optional[List[T]] = None
            if isinstance(other, List[T]):
                if other is self:
                    seq = other.__copy__()
                else:
                    seq = other
            else:
                seq = [a for a in other]

            seq_len = seq.__len__()
            if seq_len != length:
                raise ValueError(
                    f"attempt to assign sequence of size {seq_len} to extended slice of size {length}"
                )

            if length == 0:
                return

            cur = start
            i = 0
            while i < length:
                self._set(cur, seq._get(i))
                cur += step
                i += 1

    def __delitem__(self, s: Slice):
        if s.start is None and s.stop is None and s.step is None:
            self.clear()
        else:
            start, stop, step, length = s.adjust_indices(self.__len__())
            if s.step is None or step == 1:
                self._assign_slice(start, stop, Ptr[T](), 0)
            else:
                if length < 0:
                    return

                if step < 0:
                    stop = start + 1
                    start = stop + step * (length - 1) - 1
                    step = -step

                cur = start
                i = 0
                while cur < stop:
                    lim = step - 1
                    if cur + step > self.__len__():
                        lim = self.__len__() - cur - 1
                    str.memmove(
                        (self.arr.ptr + (cur - i)).as_byte(),
                        (self.arr.ptr + (cur + 1)).as_byte(),
                        lim * gc.sizeof(T),
                    )
                    cur += step
                    i += 1

                cur = start + length * step
                if cur < self.__len__():
                    str.memmove(
                        (self.arr.ptr + (cur - length)).as_byte(),
                        (self.arr.ptr + cur).as_byte(),
                        (self.__len__() - cur) * gc.sizeof(T),
                    )

                self.len -= length
                # self._resize(self.__len__())

    def __contains__(self, x: T) -> bool:
        for a in self:
            if a == x:
                return True
        return False

    def __copy__(self) -> List[T]:
        return List[T](self.arr.__copy__(), self.len)

    def __deepcopy__(self) -> List[T]:
        return [l.__deepcopy__() for l in self]

    def __iter__(self) -> Generator[T]:
        i = 0
        N = self.len
        p = self.arr.ptr
        while i < N:
            yield p[i]
            i += 1

    def __reversed__(self) -> Generator[T]:
        i = self.len - 1
        while i >= 0:
            yield self._get(i)
            i -= 1

    def __add__(self, other: List[T]) -> List[T]:
        n = self.len + other.len
        v = List[T](n)
        v.len = n
        p = v.arr.ptr
        str.memcpy(p.as_byte(),
                   self.arr.ptr.as_byte(),
                   self.len * gc.sizeof(T))
        str.memcpy((p + self.len).as_byte(),
                   other.arr.ptr.as_byte(),
                   other.len * gc.sizeof(T))
        return v

    def __iadd__(self, other: List[T]) -> List[T]:
        n = self.len + other.len
        if self.arr.len < n:
            self._resize(n)
        str.memcpy((self.arr.ptr + self.len).as_byte(),
                   other.arr.ptr.as_byte(),
                   other.len * gc.sizeof(T))
        self.len = n
        return self

    def __mul__(self, n: int) -> List[T]:
        if n <= 0:
            return List[T]()

        new_len = self.len * n
        v = List[T](new_len)
        i = 0
        while i < n:
            j = 0
            while j < self.len:
                v.append(self._get(j))
                j += 1
            i += 1
        return v

    def __imul__(self, n: int) -> List[T]:
        if n == 1:
            return self

        if n <= 0:
            self.clear()
            return self

        len0 = self.__len__()
        new_cap = n * len0
        if self.arr.len < new_cap:
            p = Ptr[T](gc.realloc(self.arr.ptr.as_byte(),
                                  new_cap * gc.sizeof(T),
                                  self.arr.len * gc.sizeof(T)))
            self.arr = Array[T](p, new_cap)

        idx = len0
        i = 0
        while i < n - 1:
            j = 0
            while j < len0:
                self._set(idx, self._get(j))
                idx += 1
                j += 1
            i += 1

        self.len = new_cap
        return self

    def __repr__(self) -> str:
        n = self.__len__()
        if n == 0:
            return "[]"
        else:
            buf = _strbuf()
            buf.append("[")
            buf.append(self._get(0).__repr__())
            for i in range(1, n):
                buf.append(", ")
                buf.append(self._get(i).__repr__())
            buf.append("]")
            return buf.__str__()

    # Helper functions

    def append(self, x: T):
        self._resize_if_full()
        self._set(self.len, x)
        self.len += 1

    def extend(self, itr: Generator[T]):
        for a in itr:
            self.append(a)

    def insert(self, idx: int, x: T):
        n = self.__len__()
        if idx < 0:
            idx += n
            if idx < 0:
                idx = 0
        if idx > n:
            idx = n
        self._resize_if_full()
        i = n
        while i > idx:
            self._set(i, self._get(i - 1))
            i -= 1
        self._set(idx, x)
        self.len += 1

    def pop(self, idx: int = -1) -> T:
        if self.__len__() == 0:
            raise IndexError("pop from empty list")
        if idx < 0:
            idx += self.__len__()
        self._idx_check(idx, "pop index out of range")
        x = self._get(idx)
        del self[idx]
        return x

    def remove(self, x: T) -> bool:
        i = 0
        for a in self:
            if a == x:
                del self[i]
                return True
            i += 1
        return False

    def clear(self):
        self.len = 0

    def index(self, x: T) -> int:
        i = 0
        for a in self:
            if a == x:
                return i
            i += 1
        return -1

    def count(self, x: T) -> int:
        count = 0
        for a in self:
            if a == x:
                count += 1
        return count

    def reverse(self):
        i = 0
        while i < self.len // 2:
            j = self.len - i - 1
            x = self._get(i)
            self._set(i, self._get(j))
            self._set(j, x)
            i += 1

    def copy(self) -> List[T]:
        return self.__copy__()

    # Internal helpers

    def _idx_check(self, idx: int, msg: str):
        if idx >= self.len or idx < 0:
            raise IndexError(msg)

    def _resize(self, new_cap: int):
        p = Ptr[T](gc.realloc(self.arr.ptr.as_byte(),
                              new_cap * gc.sizeof(T),
                              self.arr.len * gc.sizeof(T)))
        self.arr = Array[T](p, new_cap)

    def _resize_if_full(self):
        if self.len == self.arr.len:
            new_cap = (1 + 3 * self.len) // 2
            self._resize(new_cap)

    def __hash__(self) -> int:
        # https://www.boost.org/doc/libs/1_35_0/doc/html/boost/hash_combine_id241013.html
        seed = 0
        for v in self:
            seed ^= v.__hash__() + 0x9E3779B9 + (seed << 6) + (seed >> 2)
        return seed

    def _assign_slice(self, ilow: int, ihigh: int, v: Ptr[T], n: int):
        a = self
        L = a.len

        if ilow < 0:
            ilow = 0
        elif ilow > L:
            ilow = L

        if ihigh < ilow:
            ihigh = ilow
        elif ihigh > L:
            ihigh = L

        norig = ihigh - ilow
        assert norig >= 0
        d = n - norig
        if L + d == 0:
            a.clear()
            return

        if d < 0:
            tail = L - ihigh
            str.memmove(
                (a.arr.ptr + (ihigh + d)).as_byte(),
                (a.arr.ptr + ihigh).as_byte(),
                tail * gc.sizeof(T),
            )
            a._resize(L + d)
        elif d > 0:
            k = L
            a._resize(k + d)
            str.memmove(
                (a.arr.ptr + (ihigh + d)).as_byte(),
                (a.arr.ptr + ihigh).as_byte(),
                (k - ihigh) * gc.sizeof(T),
            )

        k = 0
        while k < n:
            a._set(ilow, v[k])
            k += 1
            ilow += 1
        a.len += d

    def _copy_arr(self, start: int, stop: int, length: int) -> Array[T]:
        if length <= 0:
            return Array[T](Ptr[T](), 0)
        return self.arr.slice(start, stop).__copy__()

    def _cmp(self, other: List[T]):
        n1 = self.__len__()
        n2 = other.__len__()
        nmin = n1 if n1 < n2 else n2
        for i in range(nmin):
            a = self._get(i)
            b = other._get(i)

            if a < b:
                return -1
            elif a == b:
                continue
            else:
                return 1
        if n1 < n2:
            return -1
        elif n1 == n2:
            return 0
        else:
            return 1

    def __lt__(self, other: List[T]):
        return self._cmp(other) < 0

    def __gt__(self, other: List[T]):
        return self._cmp(other) > 0

    def __le__(self, other: List[T]):
        return self._cmp(other) <= 0

    def __ge__(self, other: List[T]):
        return self._cmp(other) >= 0

list = List
