cp_library/ds/list/list2_cls.py

• View this file on GitHub
• Last update: 2025-08-24 20:27:05+09:00

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

Required by

• cp_library/ds/tree/bit/bit2_cls.py
• cp_library/ds/tree/seg/segtree2_cls.py
• perf/bit2.py
• perf/list2.py
• perf/segtree2.py

Verified with

• test/unittests/ds/list/list2_cls_test.py
• test/unittests/ds/tree/bit/bit2_cls_test.py
• test/unittests/ds/tree/seg/segtree2_cls_test.py

Code

import cp_library.__header__
from typing import Generic
from cp_library.misc.typing import _T1, _T2
from cp_library.alg.iter.sort.isort_parallel_fn import isort_parallel
import cp_library.ds.__header__
import cp_library.ds.list.__header__

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]

'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             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]

Back to top page