"""Original exact greedy NMS with explicit class and deterministic tie policy."""
from fractions import Fraction as F
from itertools import permutations,combinations
import json

def validate(rows,threshold,aware):
 if type(rows) is not list or len(rows)>8 or type(threshold) not in [int,F] or not 0<=threshold<=1 or type(aware) is not bool:raise ValueError('bounded boxes and exact threshold0..1')
 for r in rows:
  if type(r) is not dict or set(r)!=set(['id','box','score','class']) or type(r['id']) is not str or not r['id'] or type(r['box']) is not list or len(r['box'])!=4 or any(type(v) not in [int,F] or not 0<=v<=100 for v in r['box']) or not (r['box'][0]<r['box'][2] and r['box'][1]<r['box'][3]) or type(r['score']) not in [int,F] or not 0<=r['score']<=1 or type(r['class']) is not int:raise ValueError('id,positive-area xyxy,exact score,class required')
 if len({r['id'] for r in rows})!=len(rows):raise ValueError('unique IDs')

def iou(a,b):
 width=max(F(0),min(a[2],b[2])-max(a[0],b[0]));height=max(F(0),min(a[3],b[3])-max(a[1],b[1]));overlap=width*height;aa=(a[2]-a[0])*(a[3]-a[1]);bb=(b[2]-b[0])*(b[3]-b[1]);return F(overlap,aa+bb-overlap)

def rectangle_oracle(a,b):
 # Original fixture has integer coordinates: independent unit-cell set intersection.
 cells=lambda box:{(x,y) for x in range(box[0],box[2]) for y in range(box[1],box[3])}
 ca=cells(a);cb=cells(b);return F(len(ca&cb),len(ca|cb))

def nms(rows,threshold,aware=True):
 validate(rows,threshold,aware);remaining=sorted(rows,key=lambda r:(-r['score'],r['id']));kept=[];trace=[]
 while remaining:
  chosen=remaining[0];rest=[];tests=[];kept.append(chosen['id'])
  for r in remaining[1:]:
   overlap=iou(chosen['box'],r['box']);same=not aware or r['class']==chosen['class'];drop=same and overlap>threshold;tests.append({'candidate':r['id'],'IoU':str(overlap),'same_comparison_group':same,'suppressed':drop})
   if not drop:rest.append(r)
  trace.append({'selected':chosen['id'],'remaining_before':[r['id'] for r in remaining],'comparisons':tests});remaining=rest
 return kept,trace

def demo():
 rows=[{'id':'A','box':[1,0,3,2],'score':F(9,10),'class':1},{'id':'B','box':[0,0,2,2],'score':F(4,5),'class':1},{'id':'C','box':[2,0,4,2],'score':F(4,5),'class':1},{'id':'D','box':[1,0,3,2],'score':F(7,10),'class':2}];tau=F(3,10);aware,at=nms(rows,tau);agnostic,gt=nms(rows,tau,False);assert aware==['A','D'] and agnostic==['A']
 for a,b in combinations(rows,2):assert iou(a['box'],b['box'])==rectangle_oracle(a['box'],b['box'])
 for order in permutations(rows):assert nms(list(order),tau)[0]==aware
 boundary,bt=nms(rows[:3],F(1,3));assert boundary==['A','B','C']
 equal=[{'id':'z','box':[0,0,2,2],'score':F(1,2),'class':1},{'id':'a','box':[0,0,2,2],'score':F(1,2),'class':1}];assert nms(equal,0)[0]==['a']
 feasible=[]
 for n in range(4):
  for subset in combinations(rows[:3],n):
   if all(iou(a['box'],b['box'])<=tau for a,b in combinations(subset,2)):feasible.append({'ids':[r['id'] for r in subset],'score_sum':str(sum(r['score'] for r in subset))})
 best=max(feasible,key=lambda r:F(r['score_sum']));assert best=={'ids':['B','C'],'score_sum':'8/5'}
 rejected=[]
 bads=[('zero_area',[{**rows[0],'box':[1,0,1,2]}],tau),('reversed_box',[{**rows[0],'box':[3,0,1,2]}],tau),('duplicate_id',[rows[0],rows[0]],tau),('nonfinite_score',[{**rows[0],'score':float('inf')}],tau),('negative_threshold',rows,-1),('nonfinite_threshold',rows,float('nan')),('missing_category',[{k:v for k,v in rows[0].items() if k!='class'}],tau)]
 for label,rr,t in bads:
  try:nms(rr,t)
  except ValueError:rejected.append(label)
  else:raise AssertionError('expected rejection')
 assert nms([],tau)[0]==[]
 return {'authored_boxes':[{**r,'score':str(r['score'])} for r in rows],'threshold':str(tau),'aware':{'kept':aware,'trace':at},'agnostic':{'kept':agnostic,'trace':gt},'all24_input_orders_same':True,'threshold_equal_one_third':{'kept':boundary,'trace':bt},'equal_score_ID_tie_kept':'a','all_feasible_subsets_ABC':feasible,'different_objective_maximum_score_subset':best,'invalid_cases_rejected':rejected,'scope':'own exact greedy box-score fixture, no Torch/vendor CPU-GPU parity/model/image/confidence/mAP claim; IoU equality is not suppressed, tie-ID is local policy, greedy does not maximize subset score'}
if __name__=='__main__':print(json.dumps(demo(),ensure_ascii=True,indent=2))