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.
  #
  
  @tuple
  class DynamicTuple:
      _ptr: Ptr[T]
      _len: int
      T: type
  
      def __new__(x: List[T]):
          from internal.gc import sizeof
          n = x.__len__()
          p = Ptr[T](n)
          str.memcpy(p.as_byte(), x.arr.ptr.as_byte(), n * sizeof(T))
          return DynamicTuple(p, n)
  
      def __new__(x: Generator[T]):
          from internal.gc import realloc, sizeof
          n = 0
          m = 0
          if hasattr(x, "__len__"):
              m = x.__len__()
          elif hasattr(x, "__length_hint__"):
              m = x.__length_hint__()
          else:
              m = 10
          p = Ptr[T](m)
          for a in x:
              if n == m:
                  new_m = (1 + 3*m) // 2
                  p = Ptr[T](realloc(p.as_byte(), new_m * sizeof(T), m * sizeof(T)))
                  m = new_m
              p[n] = a
              n += 1
  
          return DynamicTuple(p, n)
  
      def __new__():
          return DynamicTuple(Ptr[T](), 0)
  
      def __len__(self):
          return self._len
  
      def __bool__(self):
          return self._len > 0
  
      def _ensure_tuple(x):
          if not isinstance(x, Tuple):
              compile_error("expected tuple type")
  
      def __eq__(self, other):
          DynamicTuple._ensure_tuple(other)
  
          p = self._ptr
          n = self._len
  
          if staticlen(other) == 0:
              return n == 0
  
          if n != staticlen(other):
              return False
  
          for i in range(n):
              if p[i] != other[i]:
                  return False
  
          return True
  
      def __eq__(self, other: DynamicTuple[T]):
          p = self._ptr
          n = self._len
          q = other._ptr
          m = other._len
  
          if n != m:
              return False
  
          for i in range(n):
              if p[i] != q[i]:
                  return False
  
          return True
  
      def __ne__(self, other):
          DynamicTuple._ensure_tuple(other)
          return not (self == other)
  
      def __ne__(self, other: DynamicTuple[T]):
          return not (self == other)
  
      def _cmp(self, other):
          DynamicTuple._ensure_tuple(other)
          p = self._ptr
          n = self._len
  
          if staticlen(other) == 0:
              return (1 if n > 0 else 0)
  
          m = staticlen(other)
  
          for i in range(n if n < m else m):
              a = p[i]
              b = other[i]
  
              if a < b:
                  return -1
              elif a == b:
                  pass
              else:
                  return 1
  
          if n < m:
              return -1
          elif n == m:
              return 0
          else:
              return 1
  
      def _cmp(self, other: DynamicTuple[T]):
          p = self._ptr
          n = self._len
          q = other._ptr
          m = other._len
  
          for i in range(n if n < m else m):
              a = p[i]
              b = q[i]
  
              if a < b:
                  return -1
              elif a == b:
                  pass
              else:
                  return 1
  
          if n < m:
              return -1
          elif n == m:
              return 0
          else:
              return 1
  
      def __lt__(self, other):
          return self._cmp(other) < 0
  
      def __gt__(self, other):
          return self._cmp(other) > 0
  
      def __le__(self, other):
          return self._cmp(other) <= 0
  
      def __ge__(self, other):
          return self._cmp(other) >= 0
  
      def __lt__(self, other: DynamicTuple[T]):
          return self._cmp(other) < 0
  
      def __gt__(self, other: DynamicTuple[T]):
          return self._cmp(other) > 0
  
      def __le__(self, other: DynamicTuple[T]):
          return self._cmp(other) <= 0
  
      def __ge__(self, other: DynamicTuple[T]):
          return self._cmp(other) >= 0
  
      def __hash__(self):
          p = self._ptr
          n = self._len
          seed = 0
          for i in range(n):
              seed = seed ^ ((p[i].__hash__() + 2654435769) + ((seed << 6) + (seed >> 2)))
          return seed
  
      def __iter__(self):
          p = self._ptr
          n = self._len
          for i in range(n):
              yield p[i]
  
      def __contains__(self, item: T):
          p = self._ptr
          n = self._len
          for i in range(n):
              if p[i] == item:
                  return True
          return False
  
      def __getitem__(self, idx: int):
          p = self._ptr
          n = self._len
          if idx < 0:
              idx += n
          if idx < 0 or idx >= n:
              raise IndexError(f"tuple index {idx} out of range 0..{n}")
          return p[idx]
  
      def __getitem__(self, s: Slice):
          p = self._ptr
          n = self._len
  
          if s.start is None and s.stop is None and s.step is None:
              return self
          if s.step is None:
              start, stop, step, length = s.adjust_indices(n)
              return DynamicTuple(p + start, length)
          else:
              start, stop, step, length = s.adjust_indices(n)
              q = Ptr[T](length)
              n = 0
              for i in range(start, stop, step):
                  q[n] = self[i]
                  n += 1
              return DynamicTuple(q, length)
  
      def __repr__(self):
          return f"({', '.join(a.__repr__() for a in self)})"
  