"""任务 5 · 合并两个有序数组：新列表版与从后往前的原地版

最后一个任务是把两个已经排好序的数组拼成一个有序数组。两个下标各管一个数组，
都从各自的头部出发：

    p 指向 a 中**还没被取走的最小元素**（a[p] 是 a 剩下的部分的最小值）；
    q 指向 b 中还没被取走的最小元素；
    已经放进结果列表的那一段，是「两个数组已取走的元素」合并后的有序前缀，
    且其中每一项都不大于 a[p] 与 b[q]。

移动条件是「谁小谁走」：比较 a[p] 与 b[q]，小的那个被取走、它所属的下标加一。
相等时取 a 的那一个（写 `<=`），这样结果里同值的相对次序与输入的先后一致（稳定）。

主循环走到某一个数组取空为止，剩下的那一个数组整体都比已取走的大，
所以后面两个 while 把它整段接上即可，不必逐个比较。

要求**原地**合并、并且第一个数组末尾已经留好空位时，还有第三个函数：从后往前写。
p、q 分别指向两个数组**没被取走的最大元素**，写入位置 w 从 m + n - 1 往前移，
每次把较大的那个写到 a[w]。从后往前写的好处是每个位置只被写一次、
不会覆盖还没读到的元素。

三个函数都要写：merge_sorted、merge_into、merge_sorted_short。

接口：函数名、造数据那几行、带 print 的行都是判分接口，别改；
要写的是标着 TODO 的三段。

跑： py task5_merge_sorted.py
判： py run_tests.py
"""

from tools import show_count


# ══ TODO 1 ═════════════════════════════════════════════════
# 写 merge_sorted(a, b)：用新列表把两个有序列表合并成一个有序列表。
#
# 要点：
#   p = 0;  q = 0;  out = []
#   while p < len(a) and q < len(b):      两个都还有元素
#       if a[p] <= b[q]:                  <= 是为了相等时先取 a（结果稳定）
#           out.append(a[p]);  p += 1     谁小谁走
#       else:
#           out.append(b[q]);  q += 1
#   最后两个 while 各接一段：
#       while p < len(a): out.append(a[p]); p += 1
#       while q < len(b): out.append(b[q]); q += 1
#   return out
#
# 两个收尾 while 的次序无所谓（那时另一个已经空了），但都要写——
# 漏掉一个，另一个数组的尾巴就丢了。
def merge_sorted(a, b):
    return []


# ══ TODO 2 ═════════════════════════════════════════════════
# 写 merge_into(a, m, b)：a 的前 m 项已排好、后面留了 len(b) 个空位（占位值不用管），
# 把 b **原地**合并进 a，交回 a。
#
# 要点（从后往前写）：
#   p = m - 1                  a 里没被取走的最大元素的下标
#   q = len(b) - 1             b 里没被取走的最大元素的下标
#   w = m + len(b) - 1         写入位置，从末尾往前移
#   while q >= 0:              只要 b 还有没取走的，就继续填
#       if p >= 0 and a[p] > b[q]:         a 那边更大，取 a 的
#           a[w] = a[p];  p -= 1
#       else:                             否则取 b 的（b 取完了就没得取了，不会走这里）
#           a[w] = b[q];  q -= 1
#       w -= 1
#   return a
#
# 为什么从后往前：每个位置只被写一次，而且写的位置总在还没读到的元素**右边**，
# 不会覆盖掉 p 还要读的那些值。往中间 insert 一次是 O(n)（第 3 课价格表），
# 从后往前写每次都是 O(1)。
# 循环条件是 q >= 0（不是 p >= 0）：b 取完就结束了，a 剩下那一段本来就在正确的位置上。
def merge_into(a, m, b):
    return a


# ══ TODO 3 ═════════════════════════════════════════════════
# 写 merge_sorted_short(a, b)：只取合并结果的前 k 项，一共有 k 个。
#
# 这是「现成写法用不上」的那种场合：题目只要前 k 项，所以不必把两个数组整个合并完——
# 一旦 out 已经有 k 项就停手，剩下的部分不用管。
#
# 要点：与 merge_sorted 一样的两指针主循环，只是每轮取完之后判一次
#   if len(out) == k:  return out
# （取满就交回）。两个收尾 while 里也一样要判，或者干脆不用它们——
# 取满 k 项就交回，取不满就说明两个数组加起来都不够 k 项。
def merge_sorted_short(a, b, k):
    return []


if __name__ == '__main__':                     # 别改：这层守卫让判分 import 它时不出声
    a1 = [1, 3, 5, 7]                          # 别改
    b1 = [2, 4, 6]                             # 别改
    print('第一组 合并', merge_sorted(a1, b1))                    # 别改：期望 [1, 2, 3, 4, 5, 6, 7]
    print('第一组 原数组没动', a1, b1)                             # 别改：期望 [1, 3, 5, 7] [2, 4, 6]

    a2 = [1, 2, 3]                             # 别改
    b2 = [2, 2, 9]                             # 别改
    print('第二组 合并', merge_sorted(a2, b2))                    # 别改：期望 [1, 2, 2, 2, 3, 9]
    print('第二组 原数组没动', a2, b2)                             # 别改

    cases = [([1, 3, 5, 7], [2, 4, 6]), ([1, 2, 3], [2, 2, 9]), ([], [1, 2]),
             ([1, 2], []), ([], []), ([5, 5], [5])]              # 别改
    ok = 0                                     # 别改
    for x, y in cases:                         # 别改
        got = merge_sorted(x, y)               # 别改
        ref = sorted(x + y)                    # 别改：现成的写法在这里当基准
        if got == ref:                         # 别改
            ok += 1                            # 别改
        print('数据', x, y, '合并', got, '与 sorted 一致', got == ref)     # 别改

    print('六组与基准一致', ok)                                    # 别改：期望 6

    # 原地版：a 的前 m 项已排好、后面留了空位
    c = [1, 4, 7, 0, 0, 0]                     # 别改
    print('原地 合并', merge_into(c, 3, [2, 5, 6]))               # 别改：期望 [1, 2, 4, 5, 6, 7]

    d = [1, 2, 3, 0, 0]                        # 别改
    print('原地 b 更短', merge_into(d, 3, [0, 4]))                # 别改：期望 [0, 1, 2, 3, 4]（0 排在最前面）

    e = [4, 5, 6, 0, 0, 0, 0]                  # 别改
    print('原地 b 更长', merge_into(e, 3, [1, 2, 3, 7]))          # 别改：期望 [1, 2, 3, 4, 5, 6, 7]

    f = [2, 3, 0, 0, 0]                        # 别改
    print('原地 有重复值', merge_into(f, 2, [1, 2, 3]))           # 别改：期望 [1, 2, 2, 3, 3]

    # 只取前 k 项：k 比两个数组加起来还大时，把能给的都给出来
    print('前 3 项', merge_sorted_short([1, 4, 5, 9, 11], [2, 3, 8], 3))     # 别改：期望 [1, 2, 3]
    print('前 10 项', merge_sorted_short([1, 4, 5, 9, 11], [2, 3, 8], 10))   # 别改：期望 [1, 2, 3, 4, 5, 8, 9, 11]

    show_count(1, '六组与基准一致', ok)                            # 别改：期望 6
    show_count(2, '原地第一组', merge_into([1, 4, 7, 0, 0, 0], 3, [2, 5, 6]) == [1, 2, 4, 5, 6, 7])   # 别改
    show_count(3, '原地 b 更长', merge_into([4, 5, 6, 0, 0, 0, 0], 3, [1, 2, 3, 7]) == [1, 2, 3, 4, 5, 6, 7])   # 别改
    show_count(4, '前 3 项', merge_sorted_short([1, 4, 5, 9, 11], [2, 3, 8], 3) == [1, 2, 3])   # 别改