content: #
  # Copyright 2023 EA Authors.
  #
  # Licensed under the Apache License, Version 2.0 (the "License");
  # you may not use this file except in compliance with the License.
  # You may obtain a copy of the License at
  #
  #    https://www.apache.org/licenses/LICENSE-2.0
  #
  # Unless required by applicable law or agreed to in writing, software
  # distributed under the License is distributed on an "AS IS" BASIS,
  # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  # See the License for the specific language governing permissions and
  # limitations under the License.
  #
  
  import internal.gc as gc
  
  @extend
  class List:
      def __init__(self):
          self.arr = Array[T](10)
          self.len = 0
  
      def __init__(self, capacity: int):
          if capacity < 0:
              capacity = 0
          self.arr = Array[T](capacity)
          self.len = 0
  
      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, it: Generator[T]):
          self.arr = Array[T](10)
          self.len = 0
          for i in it:
              self.append(i)
  
      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 __rmul__(self, n: int) -> List[T]:
          return self.__mul__(n)
  
      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
          raise ValueError(f"{x} is not in list")
  
      def find(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
              if new_cap <= 0:
                  new_cap = 1
              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 addition optimization helpers
  
      def _list_add_opt_default_len(v: List[T]):
          return v.__len__()
  
      def _list_add_opt_default_append(ans: List[T], v: List[T]):
          from internal.gc import sizeof
          n = v.__len__()
          str.memcpy((ans.arr.ptr + ans.len).as_byte(), v.arr.ptr.as_byte(), n * sizeof(T))
          ans.len += n
  
      def _list_add_opt_slice_len(v: List[T], s: Slice):
          if s.start is None and s.stop is None and s.step is None:
              return v.__len__()
          start, stop, step, length = s.adjust_indices(v.__len__())
          return length
  
      def _list_add_opt_slice_append(ans: List[T], v: List[T], s: Slice):
          from internal.gc import sizeof
          if s.start is None and s.stop is None and s.step is None:
              n = v.__len__()
              str.memcpy((ans.arr.ptr + ans.len).as_byte(), v.arr.ptr.as_byte(), n * sizeof(T))
              ans.len += n
          elif s.step is None:
              start, stop, step, length = s.adjust_indices(v.__len__())
              n = stop - start
              str.memcpy((ans.arr.ptr + ans.len).as_byte(), (v.arr.ptr + start).as_byte(), n * sizeof(T))
              ans.len += n
          else:
              start, stop, step, length = s.adjust_indices(v.__len__())
              for i in range(start, stop, step):
                  ans.arr.ptr[ans.len] = v._get(i)
                  ans.len += 1
  
      def _list_add_opt_literal_append(ans: List[T], elem: T):
          ans.arr.ptr[ans.len] = elem
          ans.len += 1
  
      def _list_add_opt_opt_new(capacity: int):
          return List[T](capacity=capacity)
  
  list = List
  