# Generated from the published Markdown; run scripts/build_language_examples.py to refresh.
# Independent examples may reuse top-level names. Python remains the explanation language.


# topics/linear-structures/sequence-adt.md
class ArraySequence:
    def __init__(self, values=()):
        self._items = list(values)

    def __len__(self):
        return len(self._items)

    def size(self):
        return len(self)

    def is_empty(self):
        return len(self) == 0

    def _check_index(self, i, allow_end=False):
        if type(i) is not int:
            raise TypeError("index must be an integer")
        upper = len(self) if allow_end else len(self) - 1
        if not 0 <= i <= upper:
            raise IndexError("index out of range")

    def get(self, i):
        self._check_index(i)
        return self._items[i]

    def set(self, i, item):
        self._check_index(i)
        self._items[i] = item

    def insert(self, i, item):
        self._check_index(i, allow_end=True)
        self._items.insert(i, item)

    def append(self, item):
        self._items.append(item)

    def remove_at(self, i):
        self._check_index(i)
        return self._items.pop(i)

# topics/linear-structures/stacks.md
class Stack:
    def __init__(self):
        self._items = []

    def push(self, item):
        self._items.append(item)

    def pop(self):
        if self.is_empty():
            raise IndexError("pop from empty stack")
        return self._items.pop()

    def peek(self):
        if self.is_empty():
            raise IndexError("peek at empty stack")
        return self._items[-1]

    def __len__(self):
        return len(self._items)

    def size(self):
        return len(self)

    def is_empty(self):
        return not self._items

# topics/linear-structures/stacks.md
def brackets_balanced(text):
    openers = []
    matching = {')': '(', ']': '[', '}': '{'}
    for symbol in text:
        if symbol in '([{':
            openers.append(symbol)
        elif symbol in matching:
            if not openers or openers.pop() != matching[symbol]:
                return False
    return not openers

# topics/linear-structures/queues-and-deques.md
from collections import deque

class Queue:
    def __init__(self):
        self._items = deque()

    def __len__(self):
        return len(self._items)

    def size(self):
        return len(self)

    def is_empty(self):
        return len(self) == 0

    def enqueue(self, item):
        self._items.append(item)

    def front(self):
        if self.is_empty():
            raise IndexError("front of empty queue")
        return self._items[0]

    def dequeue(self):
        if self.is_empty():
            raise IndexError("dequeue from empty queue")
        return self._items.popleft()

# topics/linear-structures/deques.md
from collections import deque

items = deque()
items.append("B")
items.appendleft("A")
items.append("C")
assert items.pop() == "C"
items.appendleft("X")
assert items.popleft() == "X"
assert list(items) == ["A", "B"]

# topics/linear-structures/deques.md
from collections import deque

class Deque:
    def __init__(self):
        self._items = deque()

    def __len__(self):
        return len(self._items)

    def size(self):
        return len(self)

    def is_empty(self):
        return len(self) == 0

    def add_first(self, item):
        self._items.appendleft(item)

    def add_last(self, item):
        self._items.append(item)

    def peek_first(self):
        if self.is_empty():
            raise IndexError("first of empty deque")
        return self._items[0]

    def peek_last(self):
        if self.is_empty():
            raise IndexError("last of empty deque")
        return self._items[-1]

    def remove_first(self):
        if self.is_empty():
            raise IndexError("remove first from empty deque")
        return self._items.popleft()

    def remove_last(self):
        if self.is_empty():
            raise IndexError("remove last from empty deque")
        return self._items.pop()

# topics/linear-structures/deques.md
window = deque([12, 15, 14, 18])
window.append(20)
if len(window) > 4:
    window.popleft()
assert list(window) == [15, 14, 18, 20]

# topics/linear-structures/deques.md
def is_palindrome(sequence):
    remaining = deque(sequence)
    while len(remaining) > 1:
        if remaining.popleft() != remaining.pop():
            return False
    return True

# topics/linear-structures/arrays.md
route = ["A", "B", "C", "D"]
route.insert(1, "X")
assert route == ["A", "X", "B", "C", "D"]
assert route.pop(1) == "X"
route[1] = "Y"
assert route == ["A", "Y", "C", "D"]

# topics/linear-structures/linked-structures.md
class Node:
    def __init__(self, value, next_node=None):
        self.value = value
        self.next = next_node

c = Node("C")
b = Node("B", c)
head = Node("A", b)

# topics/linear-structures/linked-structures.md
def linked_values(head):
    values = []
    current = head
    while current is not None:
        values.append(current.value)
        current = current.next
    return values

assert linked_values(head) == ["A", "B", "C"]

# topics/linear-structures/linked-structures.md
new = Node("X")
new.next = b.next
b.next = new
assert linked_values(head) == ["A", "B", "X", "C"]

# topics/linear-structures/linked-structures.md
def remove_after(node):
    if node.next is None:
        raise IndexError("no successor to remove")
    removed = node.next
    node.next = removed.next
    removed.next = None
    return removed.value

assert remove_after(b) == "X"
assert linked_values(head) == ["A", "B", "C"]

# topics/linear-structures/circular-queues.md
class CircularQueue:
    def __init__(self, capacity):
        if type(capacity) is not int or capacity <= 0:
            raise ValueError("capacity must be a positive integer")
        self._data = [None] * capacity
        self._front = 0
        self._size = 0

    def __len__(self):
        return self._size

    def size(self):
        return len(self)

    def is_empty(self):
        return self._size == 0

    def enqueue(self, item):
        if self._size == len(self._data):
            raise OverflowError("queue is full")
        back = (self._front + self._size) % len(self._data)
        self._data[back] = item
        self._size += 1

    def front(self):
        if self.is_empty():
            raise IndexError("front of empty queue")
        return self._data[self._front]

    def dequeue(self):
        item = self.front()
        self._data[self._front] = None
        self._front = (self._front + 1) % len(self._data)
        self._size -= 1
        return item

# topics/linear-structures/linked-queues.md
class LinkedQueue:
    def __init__(self):
        self._head = None
        self._tail = None
        self._size = 0

    def __len__(self):
        return self._size

    def size(self):
        return len(self)

    def is_empty(self):
        return self._size == 0

    def enqueue(self, item):
        new = Node(item)
        if self.is_empty():
            self._head = new
        else:
            self._tail.next = new
        self._tail = new
        self._size += 1

    def front(self):
        if self.is_empty():
            raise IndexError("front of empty queue")
        return self._head.value

    def dequeue(self):
        if self.is_empty():
            raise IndexError("dequeue from empty queue")
        removed = self._head
        self._head = removed.next
        self._size -= 1
        if self._head is None:
            self._tail = None
        removed.next = None
        return removed.value