cp-library
This documentation is automatically generated by online-judge-tools/verification-helper
test/unittests/ds/list/list2_cls_test.py
- View this file on GitHub
- Last update: 2025-08-24 20:27:05+09:00
- Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A
Depends on
- argsort
(cp_library/alg/iter/arg/argsort_fn.py)
- cp_library/alg/iter/sort/isort_parallel_fn.py
- cp_library/bit/pack/packer_cls.py
- cp_library/ds/list/list2_cls.py
- cp_library/test/unittest_helper.py
Code
# verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A
import pytest
import random
class TestList2:
def test_initialization(self):
"""Test basic initialization of list2"""
A1 = [1, 2, 3, 4, 5]
A2 = ['a', 'b', 'c', 'd', 'e']
lst = list2(A1, A2)
assert lst.A1 is A1
assert lst.A2 is A2
assert len(lst) == 5
def test_len(self):
"""Test __len__ method"""
lst = list2([1, 2, 3], ['a', 'b', 'c'])
assert len(lst) == 3
lst = list2([], [])
assert len(lst) == 0
lst = list2(list(range(100)), list(range(100)))
assert len(lst) == 100
def test_getitem(self):
"""Test __getitem__ method"""
lst = list2([10, 20, 30], ['x', 'y', 'z'])
assert lst[0] == (10, 'x')
assert lst[1] == (20, 'y')
assert lst[2] == (30, 'z')
# Test negative indexing
assert lst[-1] == (30, 'z')
assert lst[-2] == (20, 'y')
def test_setitem(self):
"""Test __setitem__ method"""
lst = list2([10, 20, 30], ['x', 'y', 'z'])
lst[0] = (15, 'a')
lst[1] = (25, 'b')
lst[2] = (35, 'c')
assert lst.A1 == [15, 25, 35]
assert lst.A2 == ['a', 'b', 'c']
assert lst[0] == (15, 'a')
assert lst[1] == (25, 'b')
assert lst[2] == (35, 'c')
def test_contains_not_implemented(self):
"""Test that __contains__ raises NotImplementedError"""
lst = list2([1, 2, 3], ['a', 'b', 'c'])
with pytest.raises(NotImplementedError):
(1, 'a') in lst
def test_index_not_implemented(self):
"""Test that index raises NotImplementedError"""
lst = list2([1, 2, 3], ['a', 'b', 'c'])
with pytest.raises(NotImplementedError):
lst.index((1, 'a'))
def test_reverse(self):
"""Test reverse method"""
lst = list2([1, 2, 3, 4, 5], ['a', 'b', 'c', 'd', 'e'])
lst.reverse()
assert lst.A1 == [5, 4, 3, 2, 1]
assert lst.A2 == ['e', 'd', 'c', 'b', 'a']
assert lst[0] == (5, 'e')
assert lst[4] == (1, 'a')
def test_sort(self):
"""Test sort method"""
lst = list2([3, 1, 4, 1, 5], ['c', 'a', 'd', 'b', 'e'])
lst.sort()
# Should sort by first element
assert lst.A1 == [1, 1, 3, 4, 5]
assert lst.A2 == ['a', 'b', 'c', 'd', 'e']
def test_sort_reverse(self):
"""Test sort method with reverse=True"""
lst = list2([3, 1, 4, 1, 5], ['c', 'a', 'd', 'b', 'e'])
lst.sort(reverse=True)
# Should sort by first element in reverse
assert lst.A1 == [5, 4, 3, 1, 1]
assert lst.A2 == ['e', 'd', 'c', 'a', 'b']
def test_pop(self):
"""Test pop method"""
lst = list2([1, 2, 3, 4, 5], ['a', 'b', 'c', 'd', 'e'])
popped = lst.pop()
assert popped == (5, 'e')
assert len(lst) == 4
assert lst.A1 == [1, 2, 3, 4]
assert lst.A2 == ['a', 'b', 'c', 'd']
popped = lst.pop()
assert popped == (4, 'd')
assert len(lst) == 3
def test_append(self):
"""Test append method"""
lst = list2([1, 2, 3], ['a', 'b', 'c'])
lst.append((4, 'd'))
assert len(lst) == 4
assert lst[3] == (4, 'd')
assert lst.A1 == [1, 2, 3, 4]
assert lst.A2 == ['a', 'b', 'c', 'd']
lst.append((5, 'e'))
assert len(lst) == 5
assert lst[4] == (5, 'e')
def test_empty_list(self):
"""Test operations on empty list2"""
lst = list2([], [])
assert len(lst) == 0
with pytest.raises(IndexError):
lst.pop()
lst.append((1, 'a'))
assert len(lst) == 1
assert lst[0] == (1, 'a')
def test_with_different_types(self):
"""Test list2 with different data types"""
# Integer and float
lst = list2([1, 2, 3], [1.1, 2.2, 3.3])
assert lst[0] == (1, 1.1)
assert lst[1] == (2, 2.2)
# String and boolean
lst = list2(['a', 'b', 'c'], [True, False, True])
assert lst[0] == ('a', True)
assert lst[1] == ('b', False)
# Mixed types
lst = list2([1, 'two', 3.0], [None, [1, 2], {'key': 'value'}])
assert lst[0] == (1, None)
assert lst[1] == ('two', [1, 2])
assert lst[2] == (3.0, {'key': 'value'})
def test_large_data_operations(self):
"""Test operations on larger datasets"""
n = 1000
A1 = list(range(n))
A2 = list(range(n, 2*n))
lst = list2(A1, A2)
assert len(lst) == n
assert lst[0] == (0, n)
assert lst[n-1] == (n-1, 2*n-1)
# Test pop on large dataset
popped = lst.pop()
assert popped == (n-1, 2*n-1)
assert len(lst) == n-1
# Test append on large dataset
lst.append((n, 2*n))
assert len(lst) == n
assert lst[n-1] == (n, 2*n)
def test_sort_stability(self):
"""Test that sort maintains parallel structure"""
# Create data where first elements have duplicates
lst = list2([3, 1, 2, 1, 3], ['a', 'b', 'c', 'd', 'e'])
lst.sort()
# After sorting by first element, check parallel structure
assert lst[0][0] == 1
assert lst[1][0] == 1
assert lst[2][0] == 2
assert lst[3][0] == 3
assert lst[4][0] == 3
# The corresponding second elements should be maintained
assert lst[0][1] == 'b'
assert lst[1][1] == 'd'
assert lst[2][1] == 'c'
assert lst[3][1] == 'a'
assert lst[4][1] == 'e'
def test_random_operations(self):
"""Test random operations for robustness"""
random.seed(42)
n = 100
A1 = list(range(n))
A2 = list(range(100, 100 + n))
lst = list2(A1, A2)
# Perform random operations
for _ in range(50):
op = random.choice(['read', 'write', 'append_pop'])
if op == 'read' and len(lst) > 0:
idx = random.randint(0, len(lst) - 1)
val = lst[idx]
assert val == (lst.A1[idx], lst.A2[idx])
elif op == 'write' and len(lst) > 0:
idx = random.randint(0, len(lst) - 1)
new_val1 = random.randint(1000, 2000)
new_val2 = random.randint(3000, 4000)
lst[idx] = (new_val1, new_val2)
assert lst.A1[idx] == new_val1
assert lst.A2[idx] == new_val2
elif op == 'append_pop':
if random.random() < 0.5 and len(lst) > 0:
# Store expected value before popping
expected = (lst.A1[-1], lst.A2[-1])
popped = lst.pop()
assert popped == expected
else:
val1 = random.randint(5000, 6000)
val2 = random.randint(7000, 8000)
lst.append((val1, val2))
assert lst[-1] == (val1, val2)
from cp_library.ds.list.list2_cls import list2
if __name__ == '__main__':
from cp_library.test.unittest_helper import run_verification_helper_unittest
run_verification_helper_unittest()# verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A
import pytest
import random
class TestList2:
def test_initialization(self):
"""Test basic initialization of list2"""
A1 = [1, 2, 3, 4, 5]
A2 = ['a', 'b', 'c', 'd', 'e']
lst = list2(A1, A2)
assert lst.A1 is A1
assert lst.A2 is A2
assert len(lst) == 5
def test_len(self):
"""Test __len__ method"""
lst = list2([1, 2, 3], ['a', 'b', 'c'])
assert len(lst) == 3
lst = list2([], [])
assert len(lst) == 0
lst = list2(list(range(100)), list(range(100)))
assert len(lst) == 100
def test_getitem(self):
"""Test __getitem__ method"""
lst = list2([10, 20, 30], ['x', 'y', 'z'])
assert lst[0] == (10, 'x')
assert lst[1] == (20, 'y')
assert lst[2] == (30, 'z')
# Test negative indexing
assert lst[-1] == (30, 'z')
assert lst[-2] == (20, 'y')
def test_setitem(self):
"""Test __setitem__ method"""
lst = list2([10, 20, 30], ['x', 'y', 'z'])
lst[0] = (15, 'a')
lst[1] = (25, 'b')
lst[2] = (35, 'c')
assert lst.A1 == [15, 25, 35]
assert lst.A2 == ['a', 'b', 'c']
assert lst[0] == (15, 'a')
assert lst[1] == (25, 'b')
assert lst[2] == (35, 'c')
def test_contains_not_implemented(self):
"""Test that __contains__ raises NotImplementedError"""
lst = list2([1, 2, 3], ['a', 'b', 'c'])
with pytest.raises(NotImplementedError):
(1, 'a') in lst
def test_index_not_implemented(self):
"""Test that index raises NotImplementedError"""
lst = list2([1, 2, 3], ['a', 'b', 'c'])
with pytest.raises(NotImplementedError):
lst.index((1, 'a'))
def test_reverse(self):
"""Test reverse method"""
lst = list2([1, 2, 3, 4, 5], ['a', 'b', 'c', 'd', 'e'])
lst.reverse()
assert lst.A1 == [5, 4, 3, 2, 1]
assert lst.A2 == ['e', 'd', 'c', 'b', 'a']
assert lst[0] == (5, 'e')
assert lst[4] == (1, 'a')
def test_sort(self):
"""Test sort method"""
lst = list2([3, 1, 4, 1, 5], ['c', 'a', 'd', 'b', 'e'])
lst.sort()
# Should sort by first element
assert lst.A1 == [1, 1, 3, 4, 5]
assert lst.A2 == ['a', 'b', 'c', 'd', 'e']
def test_sort_reverse(self):
"""Test sort method with reverse=True"""
lst = list2([3, 1, 4, 1, 5], ['c', 'a', 'd', 'b', 'e'])
lst.sort(reverse=True)
# Should sort by first element in reverse
assert lst.A1 == [5, 4, 3, 1, 1]
assert lst.A2 == ['e', 'd', 'c', 'a', 'b']
def test_pop(self):
"""Test pop method"""
lst = list2([1, 2, 3, 4, 5], ['a', 'b', 'c', 'd', 'e'])
popped = lst.pop()
assert popped == (5, 'e')
assert len(lst) == 4
assert lst.A1 == [1, 2, 3, 4]
assert lst.A2 == ['a', 'b', 'c', 'd']
popped = lst.pop()
assert popped == (4, 'd')
assert len(lst) == 3
def test_append(self):
"""Test append method"""
lst = list2([1, 2, 3], ['a', 'b', 'c'])
lst.append((4, 'd'))
assert len(lst) == 4
assert lst[3] == (4, 'd')
assert lst.A1 == [1, 2, 3, 4]
assert lst.A2 == ['a', 'b', 'c', 'd']
lst.append((5, 'e'))
assert len(lst) == 5
assert lst[4] == (5, 'e')
def test_empty_list(self):
"""Test operations on empty list2"""
lst = list2([], [])
assert len(lst) == 0
with pytest.raises(IndexError):
lst.pop()
lst.append((1, 'a'))
assert len(lst) == 1
assert lst[0] == (1, 'a')
def test_with_different_types(self):
"""Test list2 with different data types"""
# Integer and float
lst = list2([1, 2, 3], [1.1, 2.2, 3.3])
assert lst[0] == (1, 1.1)
assert lst[1] == (2, 2.2)
# String and boolean
lst = list2(['a', 'b', 'c'], [True, False, True])
assert lst[0] == ('a', True)
assert lst[1] == ('b', False)
# Mixed types
lst = list2([1, 'two', 3.0], [None, [1, 2], {'key': 'value'}])
assert lst[0] == (1, None)
assert lst[1] == ('two', [1, 2])
assert lst[2] == (3.0, {'key': 'value'})
def test_large_data_operations(self):
"""Test operations on larger datasets"""
n = 1000
A1 = list(range(n))
A2 = list(range(n, 2*n))
lst = list2(A1, A2)
assert len(lst) == n
assert lst[0] == (0, n)
assert lst[n-1] == (n-1, 2*n-1)
# Test pop on large dataset
popped = lst.pop()
assert popped == (n-1, 2*n-1)
assert len(lst) == n-1
# Test append on large dataset
lst.append((n, 2*n))
assert len(lst) == n
assert lst[n-1] == (n, 2*n)
def test_sort_stability(self):
"""Test that sort maintains parallel structure"""
# Create data where first elements have duplicates
lst = list2([3, 1, 2, 1, 3], ['a', 'b', 'c', 'd', 'e'])
lst.sort()
# After sorting by first element, check parallel structure
assert lst[0][0] == 1
assert lst[1][0] == 1
assert lst[2][0] == 2
assert lst[3][0] == 3
assert lst[4][0] == 3
# The corresponding second elements should be maintained
assert lst[0][1] == 'b'
assert lst[1][1] == 'd'
assert lst[2][1] == 'c'
assert lst[3][1] == 'a'
assert lst[4][1] == 'e'
def test_random_operations(self):
"""Test random operations for robustness"""
random.seed(42)
n = 100
A1 = list(range(n))
A2 = list(range(100, 100 + n))
lst = list2(A1, A2)
# Perform random operations
for _ in range(50):
op = random.choice(['read', 'write', 'append_pop'])
if op == 'read' and len(lst) > 0:
idx = random.randint(0, len(lst) - 1)
val = lst[idx]
assert val == (lst.A1[idx], lst.A2[idx])
elif op == 'write' and len(lst) > 0:
idx = random.randint(0, len(lst) - 1)
new_val1 = random.randint(1000, 2000)
new_val2 = random.randint(3000, 4000)
lst[idx] = (new_val1, new_val2)
assert lst.A1[idx] == new_val1
assert lst.A2[idx] == new_val2
elif op == 'append_pop':
if random.random() < 0.5 and len(lst) > 0:
# Store expected value before popping
expected = (lst.A1[-1], lst.A2[-1])
popped = lst.pop()
assert popped == expected
else:
val1 = random.randint(5000, 6000)
val2 = random.randint(7000, 8000)
lst.append((val1, val2))
assert lst[-1] == (val1, val2)
'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
https://kobejean.github.io/cp-library
'''
from typing import Generic
from typing import TypeVar
_S = TypeVar('S'); _T = TypeVar('T'); _U = TypeVar('U'); _T1 = TypeVar('T1'); _T2 = TypeVar('T2'); _T3 = TypeVar('T3'); _T4 = TypeVar('T4'); _T5 = TypeVar('T5'); _T6 = TypeVar('T6')
def argsort(A: list[int], reverse=False):
P = Packer(len(I := list(A))-1); P.ienumerate(I, reverse); I.sort(); P.iindices(I)
return I
class Packer:
__slots__ = 's', 'm'
def __init__(P, mx: int): P.s = mx.bit_length(); P.m = (1 << P.s) - 1
def enc(P, a: int, b: int): return a << P.s | b
def dec(P, x: int) -> tuple[int, int]: return x >> P.s, x & P.m
def enumerate(P, A, reverse=False): P.ienumerate(A:=list(A), reverse); return A
def ienumerate(P, A, reverse=False):
if reverse:
for i,a in enumerate(A): A[i] = P.enc(-a, i)
else:
for i,a in enumerate(A): A[i] = P.enc(a, i)
def indices(P, A: list[int]): P.iindices(A:=list(A)); return A
def iindices(P, A):
for i,a in enumerate(A): A[i] = P.m&a
def isort_parallel(*L: list, reverse=False):
inv, order = [0]*len(L[0]), argsort(L[0], reverse=reverse)
for i, j in enumerate(order): inv[j] = i
for i, j in enumerate(order):
for A in L: A[i], A[j] = A[j], A[i]
order[inv[i]], inv[j] = j, inv[i]
return L
class list2(Generic[_T1, _T2]):
__slots__ = 'A1', 'A2'
def __init__(lst, A1: list[_T1], A2: list[_T2]): lst.A1, lst.A2 = A1, A2
def __len__(lst): return len(lst.A1)
def __getitem__(lst, i: int): return lst.A1[i], lst.A2[i]
def __setitem__(lst, i: int, v: tuple[_T1, _T2]): lst.A1[i], lst.A2[i] = v
def __contains__(lst, v: tuple[_T1, _T2]): raise NotImplementedError
def index(lst, v: tuple[_T1, _T2]): raise NotImplementedError
def reverse(lst): lst.A1.reverse(); lst.A2.reverse()
def sort(lst, reverse=False): isort_parallel(lst.A1, lst.A2, reverse=reverse)
def pop(lst): return lst.A1.pop(), lst.A2.pop()
def append(lst, v: tuple[_T1, _T2]): v1, v2 = v; lst.A1.append(v1); lst.A2.append(v2)
def add(lst, i: int, v: tuple[_T1, _T2]): lst.A1[i] += v[0]; lst.A2[i] += v[1]
if __name__ == '__main__':
"""
Helper for making unittest files compatible with verification-helper.
This module provides a helper function to run a dummy Library Checker test
so that unittest files can be verified by oj-verify.
"""
def run_verification_helper_unittest():
"""
Run a dummy AOJ ITP1_1_A test for verification-helper compatibility.
This function should be called in the __main__ block of unittest files
that need to be compatible with verification-helper.
The function:
1. Prints "Hello World" (AOJ ITP1_1_A solution)
2. Runs pytest for the calling test file
3. Exits with the pytest result code
"""
import sys
# Print "Hello World" for AOJ ITP1_1_A problem
print("Hello World")
import io
from contextlib import redirect_stdout, redirect_stderr
# Capture all output during test execution
output = io.StringIO()
with redirect_stdout(output), redirect_stderr(output):
# Get the calling module's file path
frame = sys._getframe(1)
test_file = frame.f_globals.get('__file__')
if test_file is None:
test_file = sys.argv[0]
result = pytest.main([test_file])
if result != 0:
print(output.getvalue())
sys.exit(result)
run_verification_helper_unittest()