"""Owned finite 1D cell index with fixed centroids, compared to exact nearest neighbors; not Faiss/HNSW."""
from fractions import Fraction as F
import json
POINTS={'P0':F(0),'P1':F(49,10),'P2':F(6),'P3':F(10)}
CENTERS={'C0':F(0),'C1':F(10)}
def d2(a,b):return (a-b)**2
def demo():
    cells={c:[] for c in CENTERS}
    for pid,x in POINTS.items():cells[min(CENTERS,key=lambda c:(d2(x,CENTERS[c]),c))].append(pid)
    rows=[]
    for q in [F(1),F(51,10),F(9)]:
        exact=min(POINTS,key=lambda p:(d2(q,POINTS[p]),p));probes=[]
        for nprobe in [1,2]:
            selected=sorted(CENTERS,key=lambda c:(d2(q,CENTERS[c]),c))[:nprobe]
            candidates=[p for c in selected for p in cells[c]]
            found=min(candidates,key=lambda p:(d2(q,POINTS[p]),p))
            probes.append({'nprobe':nprobe,'selected_cells':selected,'candidate_ids':candidates,'database_distance_calculations':len(candidates),'centroid_distance_calculations':len(CENTERS),'returned_id':found,'returned_squared_distance':str(d2(q,POINTS[found])),'exact_id_recovered':found==exact})
        rows.append({'query':str(q),'exact_top1_id':exact,'exact_top1_squared_distance':str(d2(q,POINTS[exact])),'probes':probes})
    recall={str(k):str(F(sum(r['probes'][k-1]['exact_id_recovered'] for r in rows),len(rows))) for k in [1,2]}
    assert recall=={'1':'2/3','2':'1'}
    assert rows[1]['exact_top1_id']=='P1' and rows[1]['probes'][0]['returned_id']=='P2'
    return {'authored_points':{p:str(x) for p,x in POINTS.items()},'fixed_centroids_not_trained':{c:str(x) for c,x in CENTERS.items()},'cells':cells,'metric':'squared Euclidean in this one-dimensional authored space','tie_break':'lexicographic id','rows':rows,'recall_at1_on_three_authored_queries':recall,'exact_scan_database_distances_per_query':4,'wall_clock_speed_or_semantic_relevance_measured':False,'faiss_HNSW_or_IVF_library_executed':False}
if __name__=='__main__':print(json.dumps(demo(),ensure_ascii=False,indent=2))