"""任务 4 · 计数排序的值域：0 到 999 能用，0 到 10^9 不能用

课件第四件事：把数据换成 0 到 999 之间的整数，比较计数排序与 `sorted` 的耗时；
再把值域改成 0 到 10^9，说明计数排序为什么不能用了，实际跑一次看它会怎样。

为什么不能用，是一件**能算出来**的事：计数排序开头那一行要开一张长度 maxv + 1 的表
（`cnt = [0] * (maxv + 1)`）。值域 0..999 是 1000 个位置；值域 0..10^9 是 10^9 + 1 个位置 ——
Python 的列表一个位置 8 字节（一个指针），那是 8000 MB 上下，
先不说快不快，一个进程根本开不出来。

所以这一段判的是三个确定量（一个都不读秒数）：

  1. **表的账目**：那一行「需要 N 个位置，约 X MB」里的两个数都能算出来，
     判分会拿它自己的值域再算一遍；
  2. **值域的分类**：'tiny' / 'small' / 'large' / 'huge' 四档，
     由表的长度 maxv + 1 落在哪一段决定 —— 计数排序能不能用看的就是这个；
  3. **机制**：值域小的时候计数排序的结果与 sorted 逐字相同；值域大到开不出表时，
     **另起一个进程**真的去开那张表，那个进程是什么下场由判分分别核对。
     （判分**不核**它抛的是 MemoryError 还是解释器直接退出 —— 那要看机器有多少内存。）

带 print 的行是判分接口，别改；要写的是标着 TODO 的那几段。

跑： py task4_counting_range.py
判： py run_tests.py
"""

from tools import (
    make_small, show, show_bytes, attempt, timed,
    counting_sort_canonical, counting_ops_measured, counting_slots,
    counting_bytes, table_of_slots, range_class, isolated_run,
)

# 这一段的两档值域（都是「最大值」）与规模，判分会换成别的数再算一遍。
SMALL_MAX = 999                      # 0..999：1000 个位置的表
HUGE_MAX = 10 ** 9                   # 0..10^9：10^9 + 1 个位置，约 8000 MB
SIZE = 3000
DATA_SEED = 444777

# 「另起一个进程」那两条要核对的名字：模块名（子进程按名字 import 这个文件）
# 与函数名（子进程按名字去调它）。模块名要写成**字面量**：本文件单跑时
# `__name__` 是 '__main__'，拿它去 import 是找不到这个文件的。
MODULE_NAME = 'task4_counting_range'
ISOLATED_FUNC = 'open_table_here'


def small_values(maxv=SMALL_MAX, n=SIZE):
    """0..maxv 之间的 n 个整数（确定性）。"""
    return []


def huge_values(maxv=HUGE_MAX, n=SIZE):
    """值域开到 10^9 的 n 个整数（确定性）。"""
    return []


# ══ TODO 1 ═════════════════════════════════════════════════
# 写 table_slots(maxv)：计数排序要开多少个位置。
#
#   return counting_slots(maxv)        # 就是 maxv + 1
#
# 要点：这一格与「有多少个元素」无关，只由**值域**决定 —— 这就是它不能用的原因，
# 也是它与「比较类排序」最不一样的地方（比较类排序一个额外的位置都不用开）。
def table_slots(maxv):
    return 0


# ══ TODO 2 ═════════════════════════════════════════════════
# 写 table_bytes(maxv)：那张表大约多少字节。
#
#   return counting_bytes(maxv)        # Python 的列表一个位置 8 字节
#
# 值域 10^9 时算出来是 8 * (10^9 + 1) 字节，也就是 8000 MB 上下。
# 打印那一行的「约 X MB」用的就是这个数（换 MB 是除以 1048576）。
def table_bytes(maxv):
    return 0


# ══ TODO 3 ═════════════════════════════════════════════════
# 写 value_range_of(maxv)：按表的长度交回 'tiny' / 'small' / 'large' / 'huge'。
#
#   return range_class(maxv)
#
# 四档的界线（tools.range_class 里写好了）：表的长度 < 10^4 是 tiny、< 10^6 是 small、
# < 10^9 是 large、比这更大是 huge。判分会换几个 maxv 再问一遍。
def value_range_of(maxv):
    return ''


# ══ TODO 4 ═════════════════════════════════════════════════
# 写 digest_of(a, maxv)：把计数排序的**操作账目**数出来，交回 (清点次数, 写回位置数)。
#
#   return counting_ops_measured(a, maxv)
#
# 交回的两个数与值域的账：清点次数 = len(a)（每个元素清点一次），
# 写回位置数 = maxv + 1（走了一遍 0..maxv 那张表）。它一个元素都不比较。
# 注意它只**数**、不开那张表 —— 所以值域 10^9 它也能随口交回两个数来。
def digest_of(a, maxv):
    return 0, 0


# ══ TODO 5 ═════════════════════════════════════════════════
# 写 run_at_range(a, maxv)：在**给定的值域**上真的跑一次计数排序，把结果交回来。
#
#   ca = attempt(counting_sort_canonical, a, maxv)
#   return (ca.ok, ca.value, ca.error)
#
# 三个格依次是：跑成功了吗、排出来的表（失败时是 None）、报错类型名（成功时是 None）。
# 为什么要用 attempt：值域开到 10^9 时，`[0] * (10**9 + 1)` 这一步在内存不够的机器上
# 会抛 MemoryError，甚至让解释器直接退出 —— 这一段要把报错接住、只把类型名交出来，
# 不能让整个脚本崩掉。接不住的写法，就是「没接住异常」。
#
# 注意：判分不核「值域 10^9 到底抛的是哪个错」（那要看机器的内存），
# 它核的是「值域小的时候结果与 sorted 逐字相同」+「值域大的时候这一段接得住」。
def run_at_range(a, maxv):
    return None, None, None


# ══ TODO 6 ═════════════════════════════════════════════════
# 写 open_table_here(maxv)：**真的去开那张表**，把「开出来了还是没开出来」交回来。
#
#   ca = attempt(table_of_slots, maxv)
#   return (ca.ok, ca.value, ca.error)
#
# 三个格：开出来了吗、表长多少个位置（没开出来时是 None）、报错类型名（成功时是 None）。
# tools.table_of_slots 里那一行 `[0] * (maxv + 1)` 就是计数排序开头那一步，
# 它**故意不做任何保护**：值域 999 时随手就开；值域 10^9 时这一行要一次要 8000 MB。
#
# 为什么单独写这一个函数：值域大到开不出来时，靠的就是「另起一个进程」那条路 ——
# 子进程里怎么死都伤不到这份脚本，而这份脚本自己要把那次报错接住。
def open_table_here(maxv):
    return None, None, None


def isolated_open_table(maxv):
    """**另起一个进程**去开那张表（给好的，别改）→ 一个词。

    交回的词是 ok（开出来了）/ error:类型（抛了异常）/ missing（没这个名字）/
    hard-crash（解释器直接退出 —— 内存不够时最常见的样子）/ timeout（超时）。

    判分不核它落到哪一个词上（那要看机器有多少内存），它核的是**这条路走得通**：
    子进程真的被起起来、按名字找到了函数、并且没有把你这份脚本带走。
    """
    return ''


# ── 给好的部分：主块与打印（别改）───────────────────────────────────────
if __name__ == '__main__':
    print('任务 4 · 计数排序的值域：0 到 999 能用，0 到 10^9 不能用')

    CASES = (
        (1, '值域0..999', SMALL_MAX, small_values),
        (2, '值域0..10^9', HUGE_MAX, huge_values),
    )

    for index, name, maxv, maker in CASES:
        data = maker(maxv)
        want = sorted(data)

        ok, value, error = run_at_range(data, maxv)
        # bool(ok) and ... ：ok 是 None（还没写）时也稳稳交回 0，这一段不打 Traceback。
        same = int(bool(ok) and value == want)

        counted, written = digest_of(data, maxv)
        show('一致', index, name, same)
        show('操作', index, name, counted)
        show('操作', index + 2, name + '表', written)
        show_bytes('表大小', index, name + '_' + str(maxv), table_slots(maxv),
                   table_bytes(maxv))
        show('值域', index, name, value_range_of(maxv))

    # 那一行「开表」单独看：值域小的时候真的开出来了，值域大的时候接住了报错。
    for index, (name, maxv) in enumerate((('值域0..999', SMALL_MAX),
                                          ('值域0..10^9', HUGE_MAX)), 1):
        opened, length, error = open_table_here(maxv)
        show('开表', index, name, '开出来了' if opened else '没开出来')
        show('开表', index + 2, name + '表长',
             length if opened else (error or '未知'))

    # 大值域那一档在**另一个进程**里是什么下场（这个进程自己不会被带走）。
    show('进程', 1, '值域0..10^9', isolated_open_table(HUGE_MAX))

    # ── 耗时（照量、照打印；判分一条都不读它）────────────────────────────
    small = small_values()
    t_count = timed(counting_sort_canonical, list(small), SMALL_MAX)[1]
    t_sorted = timed(sorted, list(small))[1]
    print('耗时 01 计数 值域0..999 n=' + str(SIZE) + ' ' + f'{t_count:.6f}'
          + ' 秒（参考，判分不读）')
    print('耗时 02 sorted 值域0..999 n=' + str(SIZE) + ' ' + f'{t_sorted:.6f}'
          + ' 秒（参考，判分不读）')