"""Original tiny HLL register/union contract; not HLL++ or error benchmark."""
import hashlib,math,json
PROFILE='sha256-first64be-utf8-p4-m16-v1'
def sketch(items):
 if not isinstance(items,list) or len(items)>256 or any(type(s)!=str or not 1<=len(s.encode('utf8'))<=64 for s in items):raise ValueError('bounded nonempty UTF8 tokens, max256')
 regs=[0]*16;trace=[]
 for s in items:
  bits=int.from_bytes(hashlib.sha256(s.encode('utf8')).digest()[:8],'big');j=bits>>60;w=bits&((1<<60)-1);rank=61-w.bit_length() if w else 61;regs[j]=max(regs[j],rank);trace.append({'token':s,'index':j,'rho':rank})
 return {'profile':PROFILE,'registers':regs,'trace':trace}
def estimate(s):
 if s.get('profile')!=PROFILE or not isinstance(s.get('registers'),list) or len(s['registers'])!=16 or any(type(v)!=int or not 0<=v<=61 for v in s['registers']):raise ValueError('matching profile and valid registers')
 r=s['registers'];raw=.673*16**2/sum(2.**(-v) for v in r);zeros=r.count(0);small=16*math.log(16/zeros) if zeros and raw<=40 else raw
 return {'raw':raw,'zero_registers':zeros,'small_corrected':small}
def merge(a,b):
 estimate(a);estimate(b);return {'profile':PROFILE,'registers':[max(x,y) for x,y in zip(a['registers'],b['registers'])]}
def rank(w):
 if type(w)!=int or not 0<=w<1<<60:raise ValueError('60bit suffix')
 return 61-w.bit_length() if w else 61
def demo():
 a=[str(i) for i in range(10)];b=[str(i) for i in range(6,20)];sa=sketch(a);sb=sketch(b);union=merge(sa,sb);direct=sketch(a+b);assert union['registers']==direct['registers'] and len(set(a+b))==20 and len(a)+len(b)==24
 assert sketch(a*2)['registers']==sa['registers'] and merge(sa,sa)['registers']==sa['registers'];assert merge(sb,sa)==union;assert merge(union,sketch([]))==union
 bounds={str(v):rank(v) for v in [0,1,1<<59,(1<<60)-1]};assert list(bounds.values())==[61,60,1,1]
 # Independent literal binary-string first1 oracle over all12bit tails embedded in60bits.
 for v in range(4096):
  text=f'{v:060b}';oracle=text.index('1')+1 if '1' in text else 61;assert rank(v)==oracle
 empty=estimate(sketch([]));assert empty['small_corrected']==0 and empty['raw']>0
 bad=[]
 for label,fn in [('oversize',lambda:sketch(['x']*257)),('empty_token',lambda:sketch([''])),('wrong_type',lambda:sketch([1])),('mismatched_profile',lambda:merge(sa,{'profile':'other','registers':[0]*16})),('bad_rank',lambda:estimate({'profile':PROFILE,'registers':[62]*16})),('bad_suffix',lambda:rank(-1))]:
  try:fn()
  except ValueError:bad.append(label)
  else:raise AssertionError(label)
 return {'A_tokens':a,'B_tokens':b,'A':sa,'B':sb,'merged_registers':union,'union_estimate':estimate(union),'A_estimate':estimate(sa),'B_estimate':estimate(sb),'exact_union_cardinality':20,'wrong_sum_exact_input_cardinalities':24,'empty':empty,'rank_boundaries':bounds,'rank_binary_string_oracles':4096,'invalid_cases_rejected':bad,'scope':'fixed16 registers and SHA256first64, no large-range correction, HLL++ or membership/identity/privacy guarantee. Fixed-hash observations not uniform-hash proof or error-rate experiment; raw/small estimates not exactset counts.'}
if __name__=='__main__':print(json.dumps(demo(),indent=2))