07 — Lists & Tuples

import sys

# ── List over-allocation: lists pre-grow to amortize append to O(1) ──
# A list of N elements has capacity > N — the underlying PyObject*[] array
# is over-allocated by ~(N/8 + 3) slots, so most appends don't trigger a realloc.

def show_capacity(n: int):
    """Build a list of n elements, show its actual byte size and over-allocation."""
    lst = []
    for i in range(n):
        lst.append(i)
    # sys.getsizeof reports the list object size, NOT the pointed-to objects
    # Each slot is 8 bytes (a pointer) on 64-bit CPython
    size = sys.getsizeof(lst)
    slots = (size - sys.getsizeof([])) // 8   # subtract list header, divide by pointer size
    print(f"len={len(lst):>6}  sizeof={size:>6}  capacity≈{slots:>6}  overalloc={slots - len(lst):>4}")

show_capacity(0)      # len=     0  capacity≈     0  — empty list, no pointer array
show_capacity(10)     # len=    10  capacity≈    16  — 6 spare slots
show_capacity(100)    # len=   100  capacity≈   116  — ~16% over-allocated
show_capacity(1000)   # len=  1000  capacity≈  1030  — ~3% over-allocated (ratio shrinks)

# ── Tuple: no over-allocation (immutable, no growth needed) → smaller footprint ──
lst = [1, 2, 3, 4, 5]
tup = (1, 2, 3, 4, 5)
print(f"list sizeof: {sys.getsizeof(lst)}")   # ~120 bytes — header + 8 spare pointer slots
print(f"tuple sizeof: {sys.getsizeof(tup)}")  # ~64 bytes — header + exactly 5 slots, no spare

# Tuples of constants can be folded into the code object's co_consts at compile time
# (a "constant tuple" optimization) — the tuple is created once, reused on each access

# ── Production: building a 2D matrix correctly ──
# The #1 Python gotcha — shared inner references in list multiplication

# ANTI-PATTERN: [[0] * cols] * rows — all rows are the SAME list object
def bad_matrix(rows, cols):
    return [[0] * cols] * rows    # inner [0]*cols is created ONCE, referenced `rows` times

board = bad_matrix(3, 3)
board[0][0] = 1
print(board)   # [[1, 0, 0], [1, 0, 0], [1, 0, 0]] — ALL rows changed! same inner list object

# CORRECT: comprehension creates a fresh inner list per row
def good_matrix(rows, cols):
    return [[0] * cols for _ in range(rows)]   # [0]*cols evaluated fresh each iteration

board = good_matrix(3, 3)
board[0][0] = 1
print(board)   # [[1, 0, 0], [0, 0, 0], [0, 0, 0]] — only row 0 changed

# ── Production: in-place filtering without allocation ──
# Remove items matching a predicate WITHOUT creating a new list (memory-constrained environments)
def filter_inplace(lst: list, predicate):
    """Remove items where predicate(item) is True — O(n), no second allocation."""
    lst[:] = [x for x in lst if not predicate(x)]   # slice assignment mutates in place
    # `lst[:] = ...` replaces the CONTENTS of lst, keeping the same object identity
    # All external references to `lst` see the update (unlike `lst = [...]` which rebinds)

data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
ref = data   # external reference
filter_inplace(data, lambda x: x % 3 == 0)
print(data)   # [1, 2, 4, 5, 7, 8, 10] — filtered
print(ref is data)   # True — same object, ref sees the change too

nums = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

print(nums[2:5])       # [2, 3, 4]
print(nums[:3])          # [0, 1, 2]
print(nums[7:])            # [7, 8, 9]
print(nums[-3:])              # [7, 8, 9]
print(nums[::2])                # [0, 2, 4, 6, 8]
print(nums[::-1])                 # [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]  — reverse
print(nums[100:200])                # []  — never raises, clamps silently

# Slices are shallow copies — a NEW list object
sub = nums[2:5]
sub.append(999)
print(nums)              # unaffected — [0, 1, ..., 9]

nums = [0, 1, 2, 3, 4]
nums[1:3] = [10, 20, 30]      # replace a slice with a differently-sized list
print(nums)                      # [0, 10, 20, 30, 3, 4]

nums[1:4] = []                     # delete a range via empty-slice assignment
print(nums)                           # [0, 3, 4]

nums[1:1] = [100, 200]                  # insert without replacing anything
print(nums)                                # [0, 100, 200, 3, 4]

del nums[0]                                  # del also works with slices
print(nums)                                     # [100, 200, 3, 4]

squares = [x ** 2 for x in range(10)]
print(squares)   # [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

evens = [x for x in range(20) if x % 2 == 0]
print(evens)       # [0, 2, 4, ..., 18]

# Nested comprehension — flatten a matrix
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
flat = [num for row in matrix for num in row]
print(flat)   # [1, 2, 3, 4, 5, 6, 7, 8, 9]

# Conditional expression INSIDE the comprehension (ternary, not filter)
labels = ["even" if x % 2 == 0 else "odd" for x in range(5)]
print(labels)   # ['even', 'odd', 'even', 'odd', 'even']

point = (3, 4)
print(point[0], point[1])   # 3 4

# point[0] = 10   # TypeError: 'tuple' object does not support item assignment

# Parentheses are optional — the COMMA makes it a tuple
also_a_tuple = 1, 2, 3
print(type(also_a_tuple))   # <class 'tuple'>

single = (42,)          # trailing comma REQUIRED for a 1-element tuple
not_a_tuple = (42)         # this is just an int in parentheses!
print(type(single), type(not_a_tuple))   # <class 'tuple'> <class 'int'>

empty = ()
print(type(empty))   # <class 'tuple'>

# Packing
coordinates = 10, 20, 30

# Unpacking
x, y, z = coordinates
print(x, y, z)   # 10 20 30

# Swap without a temp variable — packs a tuple on the right, unpacks on the left
a, b = 1, 2
a, b = b, a
print(a, b)   # 2 1

# Star-unpacking for "the rest"
first, *middle, last = [1, 2, 3, 4, 5]
print(first, middle, last)   # 1 [2, 3, 4] 5

first, second, *rest = range(10)
print(first, second, rest)   # 0 1 [2, 3, 4, 5, 6, 7, 8, 9]

# Ignoring values with _
_, _, third = (1, 2, 3)
print(third)   # 3

def divide_with_remainder(a, b):
    return a // b, a % b     # implicitly packs a 2-tuple

quotient, remainder = divide_with_remainder(17, 5)
print(quotient, remainder)   # 3 2

# Tuples as dict keys — impossible with lists
distances = {}
distances[(0, 0)] = 0
distances[(1, 1)] = 1.41

# lst = [0, 0]
# distances[lst] = 0   # TypeError: unhashable type: 'list'

print(distances[(1, 1)])   # 1.41

import copy

original = [[1, 2], [3, 4]]

# Assignment is NOT a copy — same object
alias = original
alias[0].append(99)
print(original)   # [[1, 2, 99], [3, 4]] — original changed too, same object

# Shallow copy — a NEW outer list, but inner lists are SHARED
shallow = original.copy()          # or: list(original), or original[:]
shallow.append([100])                 # adding to the OUTER list doesn't affect original
print(original)                          # unaffected by the .append([100]) above

shallow[0].append(999)                     # but mutating a SHARED inner list DOES affect original
print(original)                               # [[1, 2, 99, 999], [3, 4]] — leaked through!

# Deep copy — recursively copies EVERYTHING, no shared references at any depth
deep = copy.deepcopy(original)
deep[0].append(-1)
print(original)   # unaffected — [[1, 2, 99, 999], [3, 4]]
print(deep)          # [[1, 2, 99, 999, -1], [3, 4]]

# Shallow copy is FINE for flat lists of immutables
flat = [1, 2, 3]
shallow_flat = flat.copy()
shallow_flat.append(4)
print(flat)   # [1, 2, 3] — no shared mutable elements to leak through

# But dangerous for nested/mutable structures — always deepcopy those
nested = [{"count": 0}, {"count": 0}]
shallow_nested = nested.copy()
shallow_nested[0]["count"] += 1
print(nested)   # [{'count': 1}, {'count': 0}] — leaked!

from collections import deque

queue = deque()
queue.append("task1")
queue.append("task2")
queue.appendleft("urgent_task")   # O(1), unlike list.insert(0, ...)
print(queue.popleft())              # 'urgent_task' — O(1), unlike list.pop(0)

board = [[None] * 3] * 3
board[0][0] = "X"
print(board)