cp_library/alg/iter/coord_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
• cp_library/ds/elist_fn.py

Code

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

def coord_compress(A: list[int], distinct = False):
    s, m = pack_sm((N := len(A))-1)
    R, V, S = [0]*N, elist(N), [a<<s|i for i,a in enumerate(A)]; S.sort()
    r = p = -1
    for ai in S:
        a, i = pack_dec(ai, s, m)
        if a != p or distinct: r, p = r+1, a; V.append(a)
        R[i] = r
    return R, V

from cp_library.ds.elist_fn import elist
from cp_library.bit.pack_sm_fn import pack_dec, pack_sm

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



def coord_compress(A: list[int], distinct = False):
    s, m = pack_sm((N := len(A))-1)
    R, V, S = [0]*N, elist(N), [a<<s|i for i,a in enumerate(A)]; S.sort()
    r = p = -1
    for ai in S:
        a, i = pack_dec(ai, s, m)
        if a != p or distinct: r, p = r+1, a; V.append(a)
        R[i] = r
    return R, V



def elist(est_len: int) -> list: ...
try:
    from __pypy__ import newlist_hint
except:
    def newlist_hint(hint):
        return []
elist = newlist_hint
    


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