cp-library
This documentation is automatically generated by online-judge-tools/verification-helper
test/unittests/ds/view/csr6_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
- cp_library/alg/iter/arg/argsort_ranged_fn.py
- cp_library/alg/iter/sort/isort_ranged_fn.py
- cp_library/bit/pack/packer_cls.py
- cp_library/ds/view/csr6_cls.py
- cp_library/ds/view/view6_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
class TestCSR6:
def test_basic_operations(self):
"""Test basic CSR6 operations with 6 attributes"""
K = [1]
V1 = [2]
V2 = [20]
V3 = [200]
V4 = [2000]
V5 = [20000]
V6 = [200000]
csr = CSR6.bucketize(3, K, V1, V2, V3, V4, V5, V6)
assert len(csr) == 3
# Check edges
assert list(csr[0]) == []
assert list(csr[1]) == [(2, 20, 200, 2000, 20000, 200000)]
assert list(csr[2]) == []
def test_complete_graph(self):
"""Test CSR6 with complete graph (all pairs connected)"""
n = 3
K = []
V1, V2, V3, V4, V5, V6 = [], [], [], [], [], []
# Create all edges except self-loops
for i in range(n):
for j in range(n):
if i != j:
K.append(i)
V1.append(j)
V2.append(i*10 + j)
V3.append(i*100 + j*10)
V4.append(i*1000 + j*100)
V5.append(i*10000 + j*1000)
V6.append(i*100000 + j*10000)
csr = CSR6.bucketize(n, K, V1, V2, V3, V4, V5, V6)
# Each node should have n-1 neighbors
for i in range(n):
neighbors = list(csr[i])
assert len(neighbors) == n - 1
def test_view_append_operations(self):
"""Test view append operations"""
# Create CSR with space for appending
A1 = [1, 0, 0, 0]
A2 = [10, 0, 0, 0]
A3 = [100, 0, 0, 0]
A4 = [1000, 0, 0, 0]
A5 = [10000, 0, 0, 0]
A6 = [100000, 0, 0, 0]
O = [0, 1, 1, 1] # Node 0 has 1 edge initially
csr = CSR6(A1, A2, A3, A4, A5, A6, O)
# Get view and append
view0 = csr[0]
assert len(view0) == 1
# Append to view (view already at position 1)
view0.append((2, 20, 200, 2000, 20000, 200000))
assert len(view0) == 2
assert view0[1] == (2, 20, 200, 2000, 20000, 200000)
def test_set_and_direct_access(self):
"""Test set operation and direct access"""
K = [0, 0]
V1 = [1, 2]
V2 = [10, 20]
V3 = [100, 200]
V4 = [1000, 2000]
V5 = [10000, 20000]
V6 = [100000, 200000]
csr = CSR6.bucketize(3, K, V1, V2, V3, V4, V5, V6)
# Test initial values
assert csr(0, 0) == (1, 10, 100, 1000, 10000, 100000)
assert csr(0, 1) == (2, 20, 200, 2000, 20000, 200000)
# Modify
csr.set(0, 1, (9, 90, 900, 9000, 90000, 900000))
assert csr(0, 1) == (9, 90, 900, 9000, 90000, 900000)
from cp_library.ds.view.csr6_cls import CSR6
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
class TestCSR6:
def test_basic_operations(self):
"""Test basic CSR6 operations with 6 attributes"""
K = [1]
V1 = [2]
V2 = [20]
V3 = [200]
V4 = [2000]
V5 = [20000]
V6 = [200000]
csr = CSR6.bucketize(3, K, V1, V2, V3, V4, V5, V6)
assert len(csr) == 3
# Check edges
assert list(csr[0]) == []
assert list(csr[1]) == [(2, 20, 200, 2000, 20000, 200000)]
assert list(csr[2]) == []
def test_complete_graph(self):
"""Test CSR6 with complete graph (all pairs connected)"""
n = 3
K = []
V1, V2, V3, V4, V5, V6 = [], [], [], [], [], []
# Create all edges except self-loops
for i in range(n):
for j in range(n):
if i != j:
K.append(i)
V1.append(j)
V2.append(i*10 + j)
V3.append(i*100 + j*10)
V4.append(i*1000 + j*100)
V5.append(i*10000 + j*1000)
V6.append(i*100000 + j*10000)
csr = CSR6.bucketize(n, K, V1, V2, V3, V4, V5, V6)
# Each node should have n-1 neighbors
for i in range(n):
neighbors = list(csr[i])
assert len(neighbors) == n - 1
def test_view_append_operations(self):
"""Test view append operations"""
# Create CSR with space for appending
A1 = [1, 0, 0, 0]
A2 = [10, 0, 0, 0]
A3 = [100, 0, 0, 0]
A4 = [1000, 0, 0, 0]
A5 = [10000, 0, 0, 0]
A6 = [100000, 0, 0, 0]
O = [0, 1, 1, 1] # Node 0 has 1 edge initially
csr = CSR6(A1, A2, A3, A4, A5, A6, O)
# Get view and append
view0 = csr[0]
assert len(view0) == 1
# Append to view (view already at position 1)
view0.append((2, 20, 200, 2000, 20000, 200000))
assert len(view0) == 2
assert view0[1] == (2, 20, 200, 2000, 20000, 200000)
def test_set_and_direct_access(self):
"""Test set operation and direct access"""
K = [0, 0]
V1 = [1, 2]
V2 = [10, 20]
V3 = [100, 200]
V4 = [1000, 2000]
V5 = [10000, 20000]
V6 = [100000, 200000]
csr = CSR6.bucketize(3, K, V1, V2, V3, V4, V5, V6)
# Test initial values
assert csr(0, 0) == (1, 10, 100, 1000, 10000, 100000)
assert csr(0, 1) == (2, 20, 200, 2000, 20000, 200000)
# Modify
csr.set(0, 1, (9, 90, 900, 9000, 90000, 900000))
assert csr(0, 1) == (9, 90, 900, 9000, 90000, 900000)
'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
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_ranged(A: list[int], l: int, r: int, reverse=False):
P = Packer(r-l-1); I = [A[l+i] for i in range(r-l)]; P.ienumerate(I, reverse); I.sort()
for i in range(r-l): I[i] = (I[i] & P.m) + l
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_ranged(*L: list, l: int, r: int, reverse=False):
n = r - l
order = argsort_ranged(L[0], l, r, reverse=reverse)
inv = [0] * n
# order contains indices in range [l, r), need to map to [0, n)
for i in range(n): inv[order[i]-l] = i
for i in range(n):
j = order[i] - l # j is in range [0, n)
for A in L: A[l+i], A[l+j] = A[l+j], A[l+i]
order[inv[i]], order[inv[j]] = order[inv[j]], order[inv[i]]
inv[i], inv[j] = inv[j], inv[i]
return L
class view6(Generic[_T1, _T2, _T3, _T4, _T5, _T6]):
__slots__ = 'A1', 'A2', 'A3', 'A4', 'A5', 'A6', 'l', 'r'
def __init__(V, A1: list[_T1], A2: list[_T2], A3: list[_T3], A4: list[_T4], A5: list[_T5], A6: list[_T6], l: int = 0, r: int = 0):
V.A1, V.A2, V.A3, V.A4, V.A5, V.A6, V.l, V.r = A1, A2, A3, A4, A5, A6, l, r
def __len__(V): return V.r - V.l
def __getitem__(V, i: int):
if 0 <= i < V.r - V.l: return V.A1[V.l+i], V.A2[V.l+i], V.A3[V.l+i], V.A4[V.l+i], V.A5[V.l+i], V.A6[V.l+i]
else: raise IndexError
def __setitem__(V, i: int, v: tuple[_T1, _T2, _T3, _T4, _T5, _T6]): V.A1[V.l+i], V.A2[V.l+i], V.A3[V.l+i], V.A4[V.l+i], V.A5[V.l+i], V.A6[V.l+i] = v
def __contains__(V, v: tuple[_T1, _T2, _T3, _T4, _T5, _T6]): raise NotImplemented
def set_range(V, l: int, r: int): V.l, V.r = l, r
def index(V, v: tuple[_T1, _T2, _T3, _T4, _T5, _T6]): raise NotImplemented
def reverse(V):
l, r = V.l, V.r-1
while l < r:
V.A1[l], V.A1[r] = V.A1[r], V.A1[l]
V.A2[l], V.A2[r] = V.A2[r], V.A2[l]
V.A3[l], V.A3[r] = V.A3[r], V.A3[l]
V.A4[l], V.A4[r] = V.A4[r], V.A4[l]
V.A5[l], V.A5[r] = V.A5[r], V.A5[l]
V.A6[l], V.A6[r] = V.A6[r], V.A6[l]
l += 1; r -= 1
def sort(V, reverse=False): isort_ranged(V.A1, V.A2, V.A3, V.A4, V.A5, V.A6, l=V.l, r=V.r, reverse=reverse)
def pop(V): V.r -= 1; return V.A1[V.r], V.A2[V.r], V.A3[V.r], V.A4[V.r], V.A5[V.r], V.A6[V.r]
def append(V, v: tuple[_T1, _T2, _T3, _T4, _T5, _T6]): V.A1[V.r], V.A2[V.r], V.A3[V.r], V.A4[V.r], V.A5[V.r], V.A6[V.r] = v; V.r += 1
def popleft(V): V.l += 1; return V.A1[V.l-1], V.A2[V.l-1], V.A3[V.l-1], V.A4[V.l-1], V.A5[V.l-1], V.A6[V.l-1]
def appendleft(V, v: tuple[_T1, _T2, _T3, _T4, _T5, _T6]): V.l -= 1; V.A1[V.l], V.A2[V.l], V.A3[V.l], V.A4[V.l], V.A5[V.l], V.A6[V.l] = v
def validate(V): return 0 <= V.l <= V.r <= len(V.A1)
class CSR6(Generic[_T1, _T2, _T3, _T4, _T5, _T6]):
__slots__ = 'A1', 'A2', 'A3', 'A4', 'A5', 'A6', 'O'
def __init__(csr, A1: list[_T1], A2: list[_T2], A3: list[_T3], A4: list[_T4], A5: list[_T5], A6: list[_T6], O: list[int]):
csr.A1, csr.A2, csr.A3, csr.A4, csr.A5, csr.A6, csr.O = A1, A2, A3, A4, A5, A6, O
def __len__(csr): return len(csr.O)-1
def __getitem__(csr, i: int): return view6(csr.A1, csr.A2, csr.A3, csr.A4, csr.A5, csr.A6, csr.O[i], csr.O[i+1])
def __call__(csr, i: int, j: int): ij = csr.O[i]+j; return csr.A1[ij], csr.A2[ij], csr.A3[ij], csr.A4[ij], csr.A5[ij], csr.A6[ij]
def set(csr, i: int, j: int, v: tuple[_T1, _T2, _T3, _T4, _T5, _T6]): ij = csr.O[i]+j; csr.A1[ij], csr.A2[ij], csr.A3[ij], csr.A4[ij], csr.A5[ij], csr.A6[ij] = v
@classmethod
def bucketize(cls, N: int, K: list[int], V1: list[_T1], V2: list[_T2], V3: list[_T3], V4: list[_T4], V5: list[_T5], V6: list[_T6]):
A1: list[_T1] = [0]*len(K); A2: list[_T2] = [0]*len(K); A3: list[_T3] = [0]*len(K); A4: list[_T4] = [0]*len(K); A5: list[_T5] = [0]*len(K); A6: list[_T6] = [0]*len(K); O = [0]*(N+1)
for k in K: O[k] += 1
for i in range(N): O[i+1] += O[i]
for e in range(len(K)): k = K[~e]; O[k] -= 1; A1[O[k]] = V1[~e]; A2[O[k]] = V2[~e]; A3[O[k]] = V3[~e]; A4[O[k]] = V4[~e]; A5[O[k]] = V5[~e]; A6[O[k]] = V6[~e]
return cls(A1, A2, A3, A4, A5, A6, O)
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()