#!/usr/bin/env python3
"""Exact small-state implementations; explicit checks survive python -O."""
from collections import Counter,deque
from itertools import product,combinations
from pathlib import Path
import json,random

def check(x,msg):
    if not x:raise AssertionError(msg)

class QuotientFilter:
    """Fingerprint MULTISET; p=q+r fixed, at least one physical empty slot."""
    def __init__(self,q,r):
        if type(q) is not int or type(r) is not int or q<1 or r<1:raise ValueError('positive q and r')
        self.q=q;self.r=r;self.m=1<<q;self.n=0
        self.remainder=[0]*self.m;self.occupied=[False]*self.m
        self.continuation=[False]*self.m;self.shifted=[False]*self.m
    def parts(self,f):
        if type(f) is not int or not 0<=f<1<<(self.q+self.r):raise ValueError('fingerprint range')
        return f>>self.r,f&((1<<self.r)-1)
    def empty(self,j):return not(self.occupied[j] or self.continuation[j] or self.shifted[j])
    def run_start(self,q):
        # Caller has set occupied[q] when creating a new run.
        b=q
        while self.shifted[b]:b=(b-1)%self.m
        s=b
        while b!=q:
            s=(s+1)%self.m
            while self.continuation[s]:s=(s+1)%self.m
            b=(b+1)%self.m
            while not self.occupied[b]:b=(b+1)%self.m
        return s
    def find(self,f):
        q,r=self.parts(f)
        if not self.occupied[q]:return None
        j=self.run_start(q)
        while True:
            if self.remainder[j]==r:return j
            if self.remainder[j]>r:return None
            j=(j+1)%self.m
            if not self.continuation[j]:return None
    def contains(self,f):return self.find(f) is not None
    def insert(self,f):
        q,r=self.parts(f)
        if self.n>=self.m-1:return False
        if self.empty(q):
            self.remainder[q]=r;self.occupied[q]=True;self.n+=1;return True
        old=self.occupied[q];self.occupied[q]=True
        start=self.run_start(q);pos=start
        if old:
            while self.remainder[pos]<r:
                nxt=(pos+1)%self.m
                if not self.continuation[nxt]:pos=nxt;break
                pos=nxt
            cont=pos!=start
            if pos==start:self.continuation[start]=True
        else:cont=False
        carry=(r,cont,pos!=q)
        # Empty status must be tested before overwriting any carried record.
        while not self.empty(pos):
            previous=(self.remainder[pos],self.continuation[pos],True)
            self.remainder[pos],self.continuation[pos],self.shifted[pos]=carry
            carry=previous;pos=(pos+1)%self.m
        self.remainder[pos],self.continuation[pos],self.shifted[pos]=carry
        self.n+=1;return True
    def delete(self,f):
        q,r=self.parts(f);pos=self.find(f)
        if pos is None:return False
        first=not self.continuation[pos];nxt=(pos+1)%self.m
        same_next=self.continuation[nxt]
        if first and not same_next:self.occupied[q]=False
        run=q;hole=pos;initial=True
        while not self.empty(nxt) and self.shifted[nxt]:
            old_cont=self.continuation[nxt]
            if not old_cont:
                run=(run+1)%self.m
                while not self.occupied[run]:run=(run+1)%self.m
            new_cont=False if initial and first and same_next else old_cont
            self.remainder[hole]=self.remainder[nxt]
            self.continuation[hole]=new_cont;self.shifted[hole]=hole!=run
            hole=nxt;nxt=(nxt+1)%self.m;initial=False
        check(not self.occupied[hole],'final hole must have no canonical run')
        self.remainder[hole]=0;self.continuation[hole]=False;self.shifted[hole]=False
        self.n-=1;return True
    def decode(self):
        """Independent linear decoder via physical run order, not run_start/find."""
        empty=next((j for j in range(self.m) if self.empty(j)),None)
        check(empty is not None,'one empty slot')
        out=[];home=None;last_r=None
        for d in range(1,self.m+1):
            j=(empty+d)%self.m
            if self.empty(j):home=None;last_r=None;continue
            if not self.shifted[j]:
                check(not self.continuation[j] and self.occupied[j],'unshifted run head')
                home=j;last_r=None
            elif not self.continuation[j]:
                check(home is not None,'shifted record needs earlier run')
                home=(home+1)%self.m
                while not self.occupied[home]:home=(home+1)%self.m
                last_r=None
            check(home is not None and self.shifted[j]==(j!=home),'record home/shift bit')
            r=self.remainder[j];check(last_r is None or last_r<=r,'sorted remainder run');last_r=r
            out.append((home<<self.r)|r)
        check(len(out)==self.n,'physical count')
        check({x>>self.r for x in out}=={j for j in range(self.m) if self.occupied[j]},'canonical occupied bits')
        return out

def qf_regression():
    rng=random.Random(5005);steps=0
    for q in range(1,6):
        for _ in range(100):
            obj=QuotientFilter(q,3);truth=Counter()
            for j in range(100):
                f=rng.randrange(1<<(q+3))
                if rng.random()<.55:
                    ok=obj.insert(f);check(ok==(sum(truth.values())<obj.m-1),'capacity result')
                    if ok:truth[f]+=1
                else:
                    if truth and rng.random()<.8:f=rng.choice(list(truth.elements()))
                    ok=obj.delete(f);check(ok==(truth[f]>0),'delete result')
                    if ok:
                        truth[f]-=1
                        if not truth[f]:del truth[f]
                check(Counter(obj.decode())==truth,('QF decode',q,j,f,obj.__dict__,truth))
                for x in range(1<<(q+3)):check(obj.contains(x)==(truth[x]>0),'QF fingerprint membership')
                steps+=1
    return steps


class SimpleTabulation:
    def __init__(self,tables,r):
        if type(r) is not int or r<1 or not tables or not tables[0]:raise ValueError('nonempty tables and positive output bits')
        sigma=len(tables[0])
        if any(len(t)!=sigma or any(type(v) is not int or not 0<=v<1<<r for v in t) for t in tables):raise ValueError('table shape / range')
        self.tables=tuple(tuple(t) for t in tables);self.r=r;self.sigma=sigma
    def __call__(self,key):
        if len(key)!=len(self.tables) or any(type(x) is not int or not 0<=x<self.sigma for x in key):raise ValueError('fixed character tuple')
        y=0
        for table,char in zip(self.tables,key):y^=table[char]
        return y

class RobinHood:
    def __init__(self,m,home):
        if type(m) is not int or m<2:raise ValueError('capacity >=2')
        self.m=m;self.home=home;self.table=[None]*m;self.n=0;self.moves=[]
    def bucket(self,k):
        h=self.home(k)
        if type(h) is not int or not 0<=h<self.m:raise ValueError('home range')
        return h
    def find(self,k):
        j=self.bucket(k);d=0
        while self.table[j] is not None:
            x,v,dx=self.table[j]
            if x==k:return j
            if dx<d:return None
            j=(j+1)%self.m;d+=1
        return None
    def get(self,k):
        j=self.find(k);return (False,None) if j is None else (True,self.table[j][1])
    def put(self,k,v):
        self.moves=[];at=self.find(k)
        if at is not None:self.table[at]=(k,v,self.table[at][2]);return True
        if self.n==self.m-1:return False
        j=self.bucket(k);carry=(k,v,0)
        while self.table[j] is not None:
            if carry[2]>self.table[j][2]:
                self.moves.append({'at':j,'incoming':carry[0],'displaced':self.table[j][0]})
                carry,self.table[j]=self.table[j],carry
            carry=(carry[0],carry[1],carry[2]+1);j=(j+1)%self.m
        self.table[j]=carry;self.n+=1;return True
    def delete(self,k):
        self.moves=[];j=self.find(k)
        if j is None:return False,None
        v=self.table[j][1];hole=j;nextj=(j+1)%self.m
        while self.table[nextj] is not None and self.table[nextj][2]>0:
            x,w,d=self.table[nextj];self.table[hole]=(x,w,d-1)
            self.moves.append({'key':x,'from':nextj,'to':hole,'new_distance':d-1})
            hole=nextj;nextj=(nextj+1)%self.m
        self.table[hole]=None;self.n-=1;return True,v
    def verify(self):
        pairs=[]
        for j,slot in enumerate(self.table):
            if slot is None:continue
            k,v,d=slot;h=self.bucket(k);check(d==(j-h)%self.m,'Robin distance')
            for t in range(d):
                earlier=self.table[(h+t)%self.m]
                check(earlier is not None and earlier[2]>=t,'Robin prior-probe certificate')
            pairs.append((k,v))
        check(len(pairs)==self.n<len(self.table),'Robin count/vacancy')
        check(len({k for k,v in pairs})==len(pairs),'Robin no duplicate keys')
        return dict(pairs)

class Hopscotch:
    def __init__(self,m,H,home):
        if type(m) is not int or type(H) is not int or not 1<=H<=m:raise ValueError('1<=H<=m')
        self.m=m;self.H=H;self.home=home;self.table=[None]*m;self.hop=[0]*m;self.n=0;self.moves=[]
    def bucket(self,k):
        b=self.home(k)
        if type(b) is not int or not 0<=b<self.m:raise ValueError('home range')
        return b
    def find(self,k):
        h=self.bucket(k)
        for d in range(self.H):
            if self.hop[h]>>d&1:
                j=(h+d)%self.m
                if self.table[j][0]==k:return j
        return None
    def get(self,k):
        j=self.find(k);return (False,None) if j is None else (True,self.table[j][1])
    def put(self,k,v):
        self.moves=[];j=self.find(k)
        if j is not None:self.table[j]=(k,v);return True
        h=self.bucket(k)
        hole=next((d for d in range(self.m) if self.table[(h+d)%self.m] is None),None)
        if hole is None:return False
        while hole>=self.H:
            chosen=None
            # Unwrapped offsets from h; every move strictly decreases hole.
            for b in range(hole-self.H+1,hole):
                home=(h+b)%self.m
                for d in range(hole-b):
                    if self.hop[home]>>d&1:chosen=(b,d,home);break
                if chosen is not None:break
            if chosen is None:return False
            b,d,home=chosen;old=b+d;src=(h+old)%self.m;dst=(h+hole)%self.m
            key,value=self.table[src];self.table[dst]=self.table[src];self.table[src]=None
            self.hop[home]^=(1<<d)|(1<<(hole-b))
            self.moves.append({'key':key,'home':home,'from':src,'to':dst,'old_hole_offset':hole,'new_hole_offset':old})
            hole=old
        self.table[(h+hole)%self.m]=(k,v);self.hop[h]|=1<<hole;self.n+=1;return True
    def delete(self,k):
        self.moves=[];j=self.find(k)
        if j is None:return False,None
        v=self.table[j][1];h=self.bucket(k);d=(j-h)%self.m
        self.hop[h]&=~(1<<d);self.table[j]=None;self.n-=1;return True,v
    def verify(self):
        expected=[0]*self.m;pairs=[]
        for j,slot in enumerate(self.table):
            if slot is None:continue
            k,v=slot;h=self.bucket(k);d=(j-h)%self.m
            check(d<self.H,'Hop neighborhood');expected[h]|=1<<d;pairs.append((k,v))
        check(expected==self.hop,'Hop bitmap belongs to home')
        check(len(pairs)==self.n and len({k for k,v in pairs})==self.n,'Hop unique count')
        return dict(pairs)

class XorFilter:
    """Build from a fixed position graph and fingerprints, with exact edge IDs.
    Probability claims concern independent random functions, not this deterministic API.
    On nonpeelable input build returns None; never expose an unfinished array.
    """
    @staticmethod
    def build(edges,b,r):
        if type(b) is not int or type(r) is not int or b<1 or r<1:raise ValueError('positive b/r')
        keys=set();m=3*b;degree=[0]*m;which=[0]*m
        for i,(key,vertices,fp) in enumerate(edges):
            if key in keys:raise ValueError('deduplicate original keys before construction')
            keys.add(key)
            if len(vertices)!=3 or any(type(v) is not int or not j*b<=v<(j+1)*b for j,v in enumerate(vertices)):raise ValueError('one vertex from each range')
            if type(fp) is not int or not 0<=fp<1<<r:raise ValueError('fingerprint range')
            for v in vertices:degree[v]+=1;which[v]^=i
        queue=deque(v for v in range(m) if degree[v]==1);removed=[False]*len(edges);order=[]
        while queue:
            v=queue.popleft()
            if degree[v]!=1:continue
            e=which[v]
            check(not removed[e] and v in edges[e][1],'unique edge ID recovery')
            removed[e]=True;order.append((e,v))
            for w in edges[e][1]:
                degree[w]-=1;which[w]^=e
                if degree[w]==1:queue.append(w)
        if len(order)!=len(edges):return None
        data=[0]*m
        for e,pivot in reversed(order):
            vertices,fp=edges[e][1:];value=fp
            for v in vertices:
                if v!=pivot:value^=data[v]
            data[pivot]=value
        for key,vertices,fp in edges:check(data[vertices[0]]^data[vertices[1]]^data[vertices[2]]==fp,'Xor inserted-key equation')
        return {'b':b,'r':r,'data':data,'order':order}
    @staticmethod
    def may_contain(built,vertices,fp):
        return built['data'][vertices[0]]^built['data'][vertices[1]]^built['data'][vertices[2]]==fp

def dictionary_regression():
    rng=random.Random(51905);counts={'Robin':0,'Hop':0};failed_with_moves=0
    for name,constructor in [('Robin',lambda m:RobinHood(m,lambda k:k%m)),('Hop',lambda m:Hopscotch(m,min(m,4),lambda k:k%m))]:
        for msize in range(2,15):
            for trial in range(40):
                obj=constructor(msize);truth={}
                for step in range(150):
                    k=rng.randrange(3*msize);v=rng.choice([None,-1,0,10]);op=rng.randrange(3)
                    if op==0:
                        ok=obj.put(k,v)
                        if ok:truth[k]=v
                        elif name=='Robin':check(k not in truth and len(truth)==msize-1,'Robin failure capacity')
                        elif obj.moves:failed_with_moves+=1
                    elif op==1:
                        expected=(k in truth,truth.get(k));check(obj.delete(k)==expected,'delete return');truth.pop(k,None)
                    else:check(obj.get(k)==(k in truth,truth.get(k)),'lookup return')
                    check(obj.verify()==truth,'dictionary abstract state')
                    for x in range(3*msize):check(obj.get(x)==(x in truth,truth.get(x)),'all-key query')
                    counts[name]+=1
    return {'operation_counts':counts,'hop_failed_after_valid_moves':failed_with_moves}

def tabulation_regression():
    triples=Counter();quadruples=Counter()
    for cells in product(range(4),repeat=4):
        h=SimpleTabulation([cells[:2],cells[2:]],2)
        vals=tuple(h(k) for k in ((0,0),(0,1),(1,0),(1,1)))
        triples[vals[:3]]+=1;quadruples[vals]+=1;check(vals[0]^vals[1]^vals[2]^vals[3]==0,'rectangle identity')
    check(len(triples)==64 and set(triples.values())=={4},'three-wise exact distribution')
    check(len(quadruples)==64 and set(quadruples.values())=={4},'not four independent')
    return {'random_tables_enumerated':256,'three_outputs':len(triples),'each_triple_count':4,'possible_quadruples':64,'independent_quadruples_would_be':256}

def xor_regression():
    rng=random.Random(52005);peelable=0;stuck=0;equations=0
    for b in range(1,15):
        for trial in range(250):
            n=rng.randrange(0,3*b+2);edges=[(i,tuple(j*b+rng.randrange(b) for j in range(3)),rng.randrange(16)) for i in range(n)]
            built=XorFilter.build(edges,b,4)
            if built is None:stuck+=1;continue
            peelable+=1
            # Reference peeling recomputes active incidence sets from scratch.
            active=set(range(n))
            for e,v in built['order']:
                incident={i for i in active if v in edges[i][1]};check(incident=={e},'independent peel certificate');active.remove(e)
            check(not active,'peel complete')
            for key,vertices,fp in edges:check(XorFilter.may_contain(built,vertices,fp),'Xor no false negative');equations+=1
    same=[('a',(0,1,2),5),('b',(0,1,2),5)];different=[('a',(0,1,2),5),('b',(0,1,2),6)]
    check(XorFilter.build(same,1,3) is None and XorFilter.build(different,1,3) is None,'two-edge cores')
    satisfying=sum(1 for values in product(range(8),repeat=3) if values[0]^values[1]^values[2]==5)
    check(satisfying==64,'peel failure can remain algebraically satisfiable')
    # A fixed absent query's independently uniform fingerprint accepts one value.
    built=XorFilter.build([('a',(0,2,4),3),('b',(1,2,5),5)],2,3)
    accepts=[fp for fp in range(8) if XorFilter.may_contain(built,(0,3,5),fp)]
    check(len(accepts)==1,'exact independent fingerprint false-positive law')
    return {'graphs':3500,'peeled':peelable,'stuck':stuck,'verified_member_equations':equations,'consistent_unpeeled_core_solutions':satisfying,'absent_uniform_fp_accepts':accepts,'absent_uniform_fp_choices':8}

def examples():
    rh=RobinHood(8,lambda k:k%8);rhtrace=[]
    for k in (0,1,8,16,2):
        rh.put(k,k*10);rhtrace.append({'insert':k,'slots':list(rh.table),'swaps':list(rh.moves)})
    rh.delete(8);rhdelete={'slots':list(rh.table),'moves':list(rh.moves)}
    nonmonotone=RobinHood(8,lambda k:k%8)
    for k in (0,8,16,2):nonmonotone.put(k,k)
    hop=Hopscotch(8,3,lambda k:k%8)
    for k in (0,1,2,3,4):check(hop.put(k,k*10),'Hop demo setup')
    check(hop.put(8,80),'Hop demo insert')
    hoptrace={'slots':list(hop.table),'bitmap':[format(x,'03b') for x in hop.hop],'moves':list(hop.moves)}
    failed=Hopscotch(8,3,lambda k:k%8)
    for k in (0,8,16):check(failed.put(k,k),'Hop tight setup')
    check(not failed.put(24,24),'four keys cannot fit 3-home neighborhood')
    qf=QuotientFilter(3,3);qftrace=[]
    # fingerprint values are quotient*8+remainder.
    for f in (9,11,18,10,58,59,1):
        check(qf.insert(f),'QF demo capacity');qftrace.append({'insert':f,'remainders':list(qf.remainder),'O':list(qf.occupied),'C':list(qf.continuation),'S':list(qf.shifted),'decoded':qf.decode()})
    check(qf.delete(10),'QF demo delete');qfdelete={'remainders':qf.remainder,'O':qf.occupied,'C':qf.continuation,'S':qf.shifted,'decoded':qf.decode()}
    duplicate=QuotientFilter(2,2);duplicate.insert(3);duplicate.insert(3);duplicate.delete(3);check(duplicate.contains(3) and duplicate.n==1,'retain full collision multiplicity')
    edges=[('a',(0,3,6),1),('b',(0,4,6),2),('c',(1,3,7),4),('d',(1,4,8),3)]
    built=XorFilter.build(edges,3,3);check(built is not None,'Xor demo peel')
    return {'robin_insertions':rhtrace,'robin_delete_8':rhdelete,'robin_not_globally_monotone':[x[2] for x in nonmonotone.table if x is not None],'hop_two_moves':hoptrace,'hop_capacity_failure_with_empty_slots':True,'quotient_insertions':qftrace,'quotient_delete_10':qfdelete,'duplicate_fingerprint_retained':True,'xor_edges':edges,'xor_build':built}

def main():
    report={'result':'PASS','examples':examples(),'tabulation':tabulation_regression(),'dictionaries':dictionary_regression(),'quotient_random_operations':qf_regression(),'xor':xor_regression()}
    output=Path(__file__).with_name('algorithms-hash-membership-results.json')
    output.write_text(json.dumps(report,ensure_ascii=False,indent=2)+'\n')
    print(json.dumps({k:v for k,v in report.items() if k!='examples'},ensure_ascii=False,indent=2))
if __name__=='__main__':main()