cp_library/alg/iter/icoord_compress_fn.py

• View this file on GitHub
• Last update: 2025-05-06 22:58:43+09:00

Depends on

• cp_library/bit/pack_sm_fn.py

Required by

• cp_library/ds/wavelet_matrix_cls.py

Verified with

• test/library-checker/data-structure/range_kth_smallest.test.py
• test/library-checker/data-structure/static_range_frequency_wavelet_matrix.test.py

Code

import cp_library.__header__
import cp_library.alg.__header__
import cp_library.alg.iter.__header__

def icoord_compress(A: list[int]):
    s, m = pack_sm((N := len(A))-1)
    R, V = [0]*N, [0]*N
    for i,a in enumerate(A): A[i] = a<<s|i
    A.sort()
    r = p = -1
    for ai in A:
        a, i = pack_dec(ai, s, m)
        if a != p: V[r:=r+1] = p = a
        R[i] = r
    del V[r+1:]
    return R, V

from cp_library.bit.pack_sm_fn import pack_dec, pack_sm

'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''



def icoord_compress(A: list[int]):
    s, m = pack_sm((N := len(A))-1)
    R, V = [0]*N, [0]*N
    for i,a in enumerate(A): A[i] = a<<s|i
    A.sort()
    r = p = -1
    for ai in A:
        a, i = pack_dec(ai, s, m)
        if a != p: V[r:=r+1] = p = a
        R[i] = r
    del V[r+1:]
    return R, V



def pack_sm(N: int):
    s = N.bit_length()
    return s, (1<<s)-1

def pack_enc(a: int, b: int, s: int):
    return a << s | b
    
def pack_dec(ab: int, s: int, m: int):
    return ab >> s, ab & m

def pack_indices(A, s):
    return [a << s | i for i,a in enumerate(A)]

Back to top page