Repository navigation
Expand file tree
/
Copy pathfallback.js
More file actions
4551 lines (4512 loc) · 341 KB
/
Copy pathfallback.js
File metadata and controls
4551 lines (4512 loc) · 341 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
import { canonicalIdentifier, jsonInteger, jsonSpelling } from './canonical-json.js';
import { appendContactBox, buildContactGraph, contactsAbove, contactsBelow } from './contact-graph.js';
import { CommerceInputError, compareCodePoints } from './commerce-model.js';
import { parsePolicy, policyRejection, provesUnplaceable, tagOccurrences } from './policy.js';
import { InvalidRequestError, ORIENTATION_TABLE, ROTATIONS, checkRequest, hullItemTypes, itemRotations, pointer, refuseOrientation } from './request-errors.js';
import { fabricate, solvingEnvelopes } from './made-to-measure.js';
import { achievedDimensions, billedDimensions, centringOffset, deckAlone, deckContactArea, deckSlab, declaredInner, movedPlacements, solvingFrame } from './pallet-overhang.js';
export { InvalidRequestError };
const LEN={mm:16000,millimeter:16000,millimeters:16000,cm:160000,m:16000000,in:406400,inch:406400,inches:406400,ft:4876800,tick:1,ticks:1};
const WT={g:8000000,kg:8000000000,mg:8000,lb:3628738960,lbs:3628738960,oz:226796185,tick:1,ticks:1};
// Each code's source axes and signs, and its index in the canonical table (the tie-break order).
const ROT=Object.fromEntries(ORIENTATION_TABLE.map(([code,axes])=>[code,axes])),ROT_SIGNS=Object.fromEntries(ORIENTATION_TABLE.map(([code,,signs])=>[code,signs]));
const ROT_INDEX=Object.fromEntries(ORIENTATION_TABLE.map(([code],index)=>[code,index]));
const SUPPORT_SCALE=1000000;
/** A ratio in parts per million by the published rule, `floor(ratio * 1000000 + 0.5)`, Python's
* `scaled_ratio`. */
const scaledRatio=(ratio)=>Math.floor(ratio*SUPPORT_SCALE+0.5);
/** A support ratio in parts per million, the one conversion the global, per-item, rebalance and
* validator paths share (S11). A positive ratio below half a ppm still demands contact: Python
* refuses an unsupported item there through its stability check, which this engine reads as
* the smallest ratio it can state. */
const supportPpm=(ratio)=>ratio>0?Math.max(1,scaledRatio(ratio)):0;
const MIN_CANDIDATE_POINTS=16;
const hasOwn=(value,key)=>Object.prototype.hasOwnProperty.call(value,key);
const isObject=value=>value!==null&&typeof value==='object'&&!Array.isArray(value);
const UNSUPPORTED={
// Top-level scope: a block describing the whole request rather than one item or
// container, which none of the per-entry loops below would ever see.
// `fixed_placements` left this list in 1.4.0, when this engine gained seeding, admission
// and the fixed-placement validator rule (docs/PLAN-REVISIONS.md).
request:[],
configuration:[],
// `hull_vertices`, `compression_ratio` and `max_compression_pressure_kpa` left this list
// in, the last engine to gain both the solver behaviour and the independent
// validation the staged rollout requires.
item:[],
// `access_directions` left this list in, which wired the reserved field through
// to the stop-accessibility rule in all four engines at once, and `pallet_overhang_limit`
// in, which did the same for the pallet deck.
container:[],
obstacle:[],
// `item.shape_type` values this engine does not implement. Presence is the
// wrong test for this one field: `rigid_cuboid` is the default and is implemented, so a
// caller that spells the default out must be served, not refused. What is unimplemented
// is a *value*, and the refusal names it -- packing a `convex_hull` item as its bounding
// box would return a plan that looks valid and does not physically fit.
// Empty since: this engine implements every value the schema defines. The guard
// stays because the next reserved value will need it.
shapeType:[],
};
// The admission boundary for staged public-field rollouts, exported so a test can assert
// that what the lists name is exactly what the guard refuses -- the counterpart of
// `ArrayCodec::UNSUPPORTED_FIELDS` in PHP and `UNSUPPORTED_FIELDS` in Python. Empty while
// this engine is current with the shared schema.
export const UNSUPPORTED_FIELDS=Object.freeze(Object.fromEntries(
Object.entries(UNSUPPORTED).map(([scope,fields])=>[scope,Object.freeze([...fields])])));
/**
* A carrier rate card, parsed once per container.
*
* `weight_brackets_g` is an ascending ladder of upper bounds in whole grams; the first
* bound the billed weight does not exceed sets the price. Validation is strict and
* up front because a malformed tariff misprices silently: a descending ladder would
* make an unreachable bracket look priced, and a length mismatch would pair a weight
* with someone else's price.
*/
function parseRateTable(raw){
if(raw==null)return null;
const brackets=raw.weight_brackets_g,prices=raw.prices_minor;
if(!Array.isArray(brackets)||!Array.isArray(prices)||!brackets.length)throw new RangeError('rate_table requires non-empty weight_brackets_g and prices_minor');
if(brackets.length!==prices.length)throw new RangeError('rate_table weight_brackets_g and prices_minor must have the same length');
for(let index=0;index<brackets.length;index++){
if(!Number.isSafeInteger(brackets[index])||brackets[index]<=0)throw new RangeError('rate_table weight_brackets_g must be positive safe integers');
if(index>0&&brackets[index]<=brackets[index-1])throw new RangeError('rate_table weight_brackets_g must be strictly ascending');
if(!Number.isSafeInteger(prices[index])||prices[index]<0)throw new RangeError('rate_table prices_minor must be non-negative safe integers');
}
const minimum=raw.minimum_charge_minor??0,fuel=raw.fuel_surcharge_permille??0;
if(!Number.isSafeInteger(minimum)||minimum<0)throw new RangeError('rate_table minimum_charge_minor must be a non-negative safe integer');
if(!Number.isSafeInteger(fuel)||fuel<0)throw new RangeError('rate_table fuel_surcharge_permille must be a non-negative safe integer');
return {brackets,prices,minimum,fuel}
}
// A made-to-measure container's machine in ticks, or null for a stock container.
function parseMachine(raw,unit,measures){
if(raw==null)return null;
const sides=value=>value==null?[0,0,0]:measures.sides(value,unit);
return {minimum:sides(raw.minimum),increment:sides(raw.increment),price:raw.cost_per_square_metre_minor??0,
tarePerSquareMetre:raw.tare_per_square_metre==null?0n:measures.weight(raw.tare_per_square_metre),allowance:sides(raw.outer_allowance)}
}
// Billed weight in whole grams, rounded up -- how a carrier reads a scale. A shipment
// fractionally over a bracket is in the next bracket; rounding down would price it
// below what the carrier charges.
const billedGrams=ticks=>Number((BigInt(ticks)+BigInt(WT.g)-1n)/BigInt(WT.g));
/** The charge for a billed weight, or `null` when the tariff does not price it. */
function chargeMinor(table,grams){
for(let index=0;index<table.brackets.length;index++)if(grams<=table.brackets[index]){
const base=Math.max(table.prices[index],table.minimum);
// base*fuel can pass 2^53 while the landed charge (held to 2^53-1 at admission) does not.
return base+Number((BigInt(base)*BigInt(table.fuel)+999n)/1000n)
}
return null
}
// A weight past the last bracket has no published price. Ranking it free would make the
// objective prefer exactly the packing the caller cannot ship, so it is ranked worst
// instead. Unlike a missing rate card -- rejected at admission, since that is a static
// property of the request -- this depends on how the search happened to fill the box,
// so it must lose a candidate rather than abort the run.
// Infinity, not a safe integer: the admission ceiling lets a real charge be exactly 2^53-1.
const UNPRICEABLE=Infinity;
// One wording for the refusal wherever it fires (outermost solve frame, rebalancing),
// so the four engines stay literally comparable.
const unpriceableRefusal=({id,grams,bound})=>new RangeError(`container ${JSON.stringify(id)} bills at ${grams} g, above its rate table's last bracket (${bound} g); the shipment has no published price`);
// An unpriceable total is still reported as the largest safe integer, as every engine does.
const reportedLanded=total=>total===UNPRICEABLE?Number.MAX_SAFE_INTEGER:total;
const addLanded=(total,template,billedTicks)=>{
if(total===UNPRICEABLE)return total;
const charge=template.rate==null?null:chargeMinor(template.rate,billedGrams(billedTicks));
return charge==null?UNPRICEABLE:total+charge
};
export class UnsupportedFeatureError extends Error{
constructor(fields){super(`unsupported_feature: JavaScript fallback does not yet implement ${fields.join(', ')}; the request was rejected instead of silently ignoring public fields`);this.name='UnsupportedFeatureError';this.code='unsupported_feature';this.fields=fields}
}
// The entries of a list that can carry a field at all. This guard runs before the request's
// shape is checked, so a list that is not one, or an entry that is not an object, is left for
// `checkRequest` to name rather than crashing here.
const objectsIn=value=>Array.isArray(value)?value.filter(isObject):[];
// D10: each combination reads a container dimension or position the fabricated box does
// not keep. Checked on the raw request, before any request error. O(containers + fixed placements).
function madeToMeasureCombinations(req){const fields=[],measured=new Set();
for(const raw of objectsIn(req.containers)){if(raw.made_to_measure==null)continue;
if(typeof raw.id==='string')measured.add(raw.id);
if(raw.axles!=null)fields.push('container.made_to_measure+axles');
if(Array.isArray(raw.obstacles)&&raw.obstacles.length)fields.push('container.made_to_measure+obstacles')}
if(objectsIn(req.fixed_placements).some(entry=>typeof entry.container_type==='string'&&measured.has(entry.container_type)))
fields.push('fixed_placements+container.made_to_measure');
return fields}
// Obstacles and axles are positioned in the declared frame the widened frame moves;
// doors and route corridors would need a wall the overhang crosses; a reserve is a share of a
// volume the limit leaves undefined; a made-to-measure box has no deck. A flat bag beside the
// limit is a request error instead. Checked on the raw request. O(items + containers).
function palletOverhangCombinations(req){const fields=[];let pallets=false;
for(const raw of objectsIn(req.containers)){if(raw.pallet_overhang_limit==null)continue;pallets=true;
if(Array.isArray(raw.access_directions)&&raw.access_directions.length)fields.push('container.pallet_overhang_limit+access_directions');
if(raw.axles!=null)fields.push('container.pallet_overhang_limit+axles');
if(raw.made_to_measure!=null)fields.push('container.pallet_overhang_limit+made_to_measure');
if(Array.isArray(raw.obstacles)&&raw.obstacles.length)fields.push('container.pallet_overhang_limit+obstacles');
if(typeof raw.void_fill_reserve_ratio==='number'&&raw.void_fill_reserve_ratio>0)fields.push('container.pallet_overhang_limit+void_fill_reserve_ratio')}
if(pallets&&objectsIn(req.items).some(item=>item.stop_index!=null))fields.push('container.pallet_overhang_limit+item.stop_index');
return fields}
function rejectUnsupported(req){const fields=[];
for(const key of UNSUPPORTED.request)if(hasOwn(req,key))fields.push(key);
for(const key of UNSUPPORTED.configuration)if(isObject(req.configuration)&&hasOwn(req.configuration,key))fields.push(`configuration.${key}`);
for(const raw of objectsIn(req.items))for(const key of UNSUPPORTED.item)if(hasOwn(raw,key))fields.push(`item.${key}`);
for(const raw of objectsIn(req.containers)){
for(const key of UNSUPPORTED.container)if(hasOwn(raw,key))fields.push(`container.${key}`);
for(const obstacle of objectsIn(raw.obstacles))for(const key of UNSUPPORTED.obstacle)if(hasOwn(obstacle,key))fields.push(`obstacle.${key}`);
}
for(const raw of objectsIn(req.items)){const shape=raw.shape_type;
if(typeof shape==='string'&&UNSUPPORTED.shapeType.includes(shape))fields.push(`item.shape_type=${shape}`)}
fields.push(...madeToMeasureCombinations(req),...palletOverhangCombinations(req));
if(fields.length)throw new UnsupportedFeatureError([...new Set(fields)].sort());
}
/**
* The request's fixed placements are malformed (`reason` `malformed`, `field` the bad value) or
* cannot all hold (`cannot_hold`, `field` `/fixed_placements`), so no search is attempted
* (docs/PLAN-REVISIONS.md). The message is `packvium.fixed_placements`' word for word, and names
* no field: it predates the field and is pinned across engines.
*/
export class FixedPlacementError extends InvalidRequestError{
static code='invalid_fixed_placement';
static describe(field,detail){return `${this.code}: ${detail}`}
constructor(detail,reason='cannot_hold',field='/fixed_placements'){super(reason,field,detail);this.name='FixedPlacementError'}
}
const malformed=(detail,field)=>new FixedPlacementError(detail,'malformed',field);
const FIXED_REQUIRED=['item_type','container_type','orientation'],FIXED_FIELDS=[...FIXED_REQUIRED,'container_instance','position','placement_id'],AXES=['x','y','z'];
const unknownKeys=(value,allowed)=>Object.keys(value).filter(key=>!allowed.includes(key)).sort(compareCodePoints);
/**
* The request's `fixed_placements` as JSON gave them, or a refusal naming the first entry
* that is not the schema's shape. Nothing is coerced: `"1"` and `true` are not instances, and
* a list is not a position. An absent or null field is no fixed placements. O(f).
*/
function requireFixedPlacementShapes(raw,u,hullTypes=new Set()){
if(raw==null)return [];
if(!Array.isArray(raw))throw malformed('fixed_placements is a list','/fixed_placements');
raw.forEach((entry,index)=>requireFixedEntryShape(entry,`fixed_placements[${index}]`,pointer('fixed_placements',index),u,hullTypes));
return raw
}
function requireFixedEntryShape(entry,where,field,u,hullTypes){
if(!isObject(entry))throw malformed(`${where} is an object`,field);
const unknown=unknownKeys(entry,FIXED_FIELDS);
if(unknown.length)throw malformed(`${where} cannot carry ${jsonSpelling(unknown)}`,field);
const missing=FIXED_REQUIRED.filter(name=>!hasOwn(entry,name));
if(missing.length)throw malformed(`${where} needs ${jsonSpelling(missing)}`,field);
for(const name of ['item_type','container_type'])
if(typeof entry[name]!=='string'||!entry[name])throw malformed(`${where}.${name} is a non-empty string`,`${field}/${name}`);
requireFixedOrientation(entry.orientation,hullTypes.has(entry.item_type),where,`${field}/orientation`);
const instance=fixedInstance(entry);
if(instance===null||instance<1)throw malformed(`${where}.container_instance counts from 1`,`${field}/container_instance`);
const position=hasOwn(entry,'position')?entry.position:{};
requirePointShape(position,`${where}.position`,`${field}/position`,malformed);
for(const axis of AXES)if(hasOwn(position,axis))requireCoordinate(position[axis],`${where}.position.${axis}`,`${field}/position/${axis}`,u);
const ticks=AXES.map(axis=>scalar(hasOwn(position,axis)?position[axis]:0,u,LEN));
requirePlacementId(entry.placement_id,`${entry.container_type}#${instance}`,ticks,entry.item_type,entry.orientation,where,field);
}
/**
* A placement's cross-language id (1.10), `packvium.models.placement_id`: the canonical JSON
* text of `[container id, x, y, z, item type, orientation]` with the physical position in
* ticks. A pure function of the placement, so every validator recomputes it. O(length of ids).
*/
const placementId=(containerId,[x,y,z],itemType,orientation)=>canonicalIdentifier([containerId,x,y,z,itemType,orientation]);
/** A fixed placement's optional `placement_id` (1.10) restates the id its result placement will
* carry; null is absent. A non-string is `malformed`; a string naming another placement is
* `invalid_value`. A coordinate past 2^53 - 1 has no canonical spelling and no container holds
* it, so admission refuses that entry as `outside_container` and the id is not judged. O(1). */
function requirePlacementId(value,containerId,ticks,itemType,orientation,where,field){
if(value==null)return;
const at=`${field}/placement_id`;
if(typeof value!=='string')throw malformed(`${where}.placement_id is a string`,at);
if(Math.max(...ticks)>Number.MAX_SAFE_INTEGER)return;
const expected=placementId(containerId,ticks,itemType,orientation);
if(value!==expected)throw new FixedPlacementError(`${where}.placement_id must be ${jsonSpelling(expected)}`,'invalid_value',at);
}
/** A fixed orientation from its item's vocabulary (1.10): an unknown code is `malformed` with the
* vocabulary listed -- six codes for a box, as in every release before -- and a signed code
* fixing a non-hull is `invalid_value`. Whether the item allows it is admission's rule. O(1). */
function requireFixedOrientation(value,hull,where,field){
refuseOrientation(value,hull,field,(reason,at,detail)=>new FixedPlacementError(detail,reason==='not_allowed'?'malformed':reason,at),`${where}.orientation`);
}
// Parsed here, before admission, so a coordinate the length parser cannot read is refused as
// the entry's own fault, naming the value, rather than surfacing later as a bare parse error.
function requireCoordinate(value,where,field,u){
try{scalar(value,u,LEN)}
catch(error){throw malformed(`${where} ${String(error?.message).includes('cannot be negative')?'cannot be negative':'is a measure'}`,field)}
}
const fixedInstance=entry=>jsonInteger(hasOwn(entry,'container_instance')?entry.container_instance:1);
/**
* A point is an object of `x`, `y` and `z` measures; what a measure may be is the length
* parser's to say, so only the values it would silently misread are refused here. `error`
* builds the refusal from its message and the JSON Pointer of the bad value.
*/
export function requirePointShape(point,where,field,error){
if(!isObject(point))throw error(`${where} is a point object`,field);
const unknown=unknownKeys(point,AXES);
if(unknown.length)throw error(`${where} cannot carry ${jsonSpelling(unknown)}`,field);
for(const axis of AXES)if(hasOwn(point,axis)&&(point[axis]===null||typeof point[axis]==='boolean'||Array.isArray(point[axis])))
throw error(`${where}.${axis} is a measure`,`${field}/${axis}`);
}
/**
* Resolve `req.fixed_placements` into the containers the solve opens first, or refuse the
* request. Fixed items take the first instances of their type in listed order, and each
* enters as a real placement, so every rule that reads a container's placement list holds
* for it with no rule of its own. The checks run in `admit_fixed_placements`' order because
* the refusal text is compared across engines.
*
* O(f log f) to resolve f entries, plus one pass of `fixedSetIssue`, O(f^2) in its pairwise
* collision sweep. It runs once per solve frame, before search.
*/
function admitFixedPlacements(req,{items,templates,u,clear}){
const entries=requireFixedPlacementShapes(req.fixed_placements,u,hullItemTypes(req.items));if(!entries.length)return [];
const rawItems=new Map((req.items??[]).map(raw=>[raw.id,raw])),byId=new Map(templates.map(t=>[t.id,t]));
const instances=new Map(items.map(item=>[item.id,item])),order=new Map((req.containers??[]).map((raw,index)=>[raw.id,index]));
const parsed=entries.map(entry=>{const point=hasOwn(entry,'position')?entry.position:{};
return {itemType:entry.item_type,containerType:entry.container_type,instance:fixedInstance(entry),orientation:entry.orientation,
position:AXES.map(axis=>scalar(hasOwn(point,axis)?point[axis]:0,u,LEN))}});
for(const entry of parsed){const raw=rawItems.get(entry.itemType);
if(raw===undefined)throw new FixedPlacementError(`unknown item type ${jsonSpelling(entry.itemType)}`);
if(!byId.has(entry.containerType))throw new FixedPlacementError(`unknown container type ${jsonSpelling(entry.containerType)}`);
if(!itemRotations(raw).includes(entry.orientation))
throw new FixedPlacementError(`${entry.itemType} may not be placed in orientation ${entry.orientation}`)}
const taken=new Map(),assigned=parsed.map(entry=>{const count=(taken.get(entry.itemType)??0)+1,quantity=rawItems.get(entry.itemType).quantity??1;taken.set(entry.itemType,count);
if(count>quantity)throw new FixedPlacementError(`${count} ${entry.itemType} fixed, ${quantity} requested`);
return instances.get(`${entry.itemType}#${count}`)});
const grouped=new Map();
parsed.forEach((entry,index)=>{const item=assigned[index],[px,py,pz]=entry.position;
// The clearance envelope must be inside the container, as for any placement; an item
// flush against a wall has an envelope that starts before it.
if(Math.min(px,py,pz)<clear)throw new FixedPlacementError(`outside_container: ${item.id}`);
const key=`${entry.containerType}\u0000${entry.instance}`,pd=rotate(item.d,entry.orientation);
if(!grouped.has(key))grouped.set(key,{tmpl:byId.get(entry.containerType),seq:entry.instance,placements:[]});
grouped.get(key).placements.push({x:px-clear,y:py-clear,z:pz-clear,pd,ed:grown(pd,2*clear),r:entry.orientation,item,fixed:true})});
const groups=[...grouped.values()].sort((a,b)=>order.get(a.tmpl.id)-order.get(b.tmpl.id)||a.seq-b.seq);
requireContiguousInstances(groups,req.configuration?.max_containers??null);
// Support is measured against every other fixed item in the container, not only the ones
// listed before it: the set is one arrangement, and listing order is not physics.
for(const group of groups)for(const placement of group.placements)placement.fixedSupport=placement.z===0?floorSupport(placement,group.tmpl.deck)
:[directSupporters(placement,group.placements).reduce((total,support)=>total+support.area,0),placement.ed[0]*placement.ed[1]];
const issue=fixedSetIssue(groups,req,clear);
if(issue!==null)throw new FixedPlacementError(issue);
return groups
}
function requireContiguousInstances(groups,maxContainers){
const named=new Map();for(const group of groups){if(!named.has(group.tmpl.id))named.set(group.tmpl.id,[]);named.get(group.tmpl.id).push(group.seq)}
for(const [id,sequences] of named){
if(sequences.some((sequence,index)=>sequence!==index+1))throw new FixedPlacementError(`${id} instances ${jsonSpelling(sequences)} are not numbered 1..${sequences.length}`);
const quantity=byTemplate(groups,id).quantity;
if(quantity!=null&&sequences.length>quantity)throw new FixedPlacementError(`${sequences.length} ${id} named, ${quantity} available`)}
if(maxContainers!=null&&groups.length>maxContainers)throw new FixedPlacementError(`${groups.length} containers hold fixed items, max_containers is ${maxContainers}`)
}
const byTemplate=(groups,id)=>groups.find(group=>group.tmpl.id===id).tmpl;
/**
* The first issue `IndependentSolutionValidator` reports for the fixed set alone, as
* `code: detail`, or null. Same rules, same order: collisions, then per placement bounds,
* obstacles, floor, eligibility, compatibility, tag counts, support and stacking, then per
* container load, axles, route, payload and item count, then groups. Item accounting is
* left out because the free items have not been placed yet.
*/
function fixedSetIssue(groups,req,clear){
const globalRatio=req.configuration?.minimum_support_ratio??0,globalPpm=supportPpm(globalRatio),located=new Map();
for(const group of groups){const {tmpl,placements}=group,cid=`${tmpl.id}#${group.seq}`,boxOf=p=>({x:p.x,y:p.y,z:p.z,d:p.ed});
for(let i=0;i<placements.length;i++)for(let j=i+1;j<placements.length;j++){const a=placements[i],b=placements[j];
if(intersects(boxOf(a),boxOf(b))&&!validNesting(a,b)&&solidsOverlap(placedHull(a),boxOf(a),placedHull(b),boxOf(b)))return `collision: ${a.item.id} with ${b.item.id}`}
const compatibility=placements.some(p=>p.item.tags.length||p.item.incompatible.length);
const support=globalRatio>0||placements.some(p=>p.item.supportPpm>0||(p.item.groundRule!=null&&p.item.groundRule!=='free'));
const stack=placements.some(p=>refusesLoad(p.item)||p.item.maxTop!=null||p.item.maxStacked!=null||p.item.maxCompressionKpa!=null);
const boxes=placements.map(constraintBox),graph=contactGraph(boxes);
for(let index=0;index<placements.length;index++){const p=placements[index],item=p.item,id=item.id,box=boxOf(p),others=placements.filter((_,k)=>k!==index);
if(p.x+p.ed[0]>tmpl.d[0]||p.y+p.ed[1]>tmpl.d[1]||p.z+p.ed[2]>tmpl.d[2])return `outside_container: ${id}`;
if(tmpl.obs.some(o=>intersects(box,o)&&solidsOverlap(placedHull(p),box,null,o)))return `obstacle_collision: ${id}`;
if(item.raw.must_be_on_floor&&p.z!==0)return `must_be_on_floor: ${id}: `;
if(item.eligibleTags.length&&!item.eligibleTags.some(tag=>(tmpl.tags??[]).includes(tag)))return `container_ineligible: ${id}`;
if(compatibility){const rule=compatibilityIssue(item,others,tmpl);if(rule!==null)return `${rule[0]}: ${id}: ${rule[1]}`}
if(support){const rule=supportIssue(p,others,globalRatio,globalPpm,tmpl.deck);if(rule!==null)return `${rule[0]}: ${id}: ${rule[1]}`}
if(stack){const lower=graph.supporters[index].find(([k])=>stackingRefusal(placements[k].item,item)!==null);
if(lower!==undefined)return `${stackingRefusal(placements[lower[0]].item,item)}: ${id}: ${placements[lower[0]].item.raw.id}`;
const upper=refusesLoad(item)?graph.children[index].find(k=>stackingRefusal(item,placements[k].item)!==null):undefined;
if(upper!==undefined)return `${stackingRefusal(item,placements[upper].item)}: ${id}: ${item.raw.id}`}}
const bearing=loadIssue(boxes,graph,placements,tmpl);if(bearing!==null)return `${bearing[0]}: ${cid}: ${bearing[1]}`;
const reaction=axleReactions(tmpl,placements);
if(reaction!=null){const [front,rear]=tmpl.axleSpec;
if(front.max!=null&&reaction.front>BigInt(front.max)*reaction.denominator)return `axle_overloaded: ${cid}: front`;
if(rear.max!=null&&reaction.rear>BigInt(rear.max)*reaction.denominator)return `axle_overloaded: ${cid}: rear`}
if(tmpl.bag&&!bagAdmits(tmpl,placements))return `bag_girth_exceeded: ${cid}`;
if(placements.some(p=>p.item.stopIndex!=null)){const stuck=routeStuck(placements,tmpl,clear);
if(stuck!==null)return `unloading_order_violation: ${cid}: stop ${stuck.stop} cannot be fully unloaded (${stuck.indices.map(k=>placements[k].item.id).join(', ')} still blocked)`}
if(tmpl.max!=null&&placements.reduce((total,p)=>total+p.item.w,0n)>tmpl.max)return `payload_exceeded: ${cid}`;
if(tmpl.max_items!=null&&placements.length>tmpl.max_items)return `max_items_exceeded: ${cid}`;
for(const p of placements)if(p.item.group!=null){if(!located.has(p.item.group))located.set(p.item.group,new Set());located.get(p.item.group).add(cid)}}
for(const group of [...located.keys()].sort(compareCodePoints)){const where=[...located.get(group)].sort(compareCodePoints);
if(where.length>1)return `group_split: ${group}: ${where.join(', ')}`}
return null
}
// `[max x2, max y2, max z2]` over the envelopes, and the girth rule over it.
function bagExtent(placements){let a=0,b=0,c=0;
for(const p of placements){a=Math.max(a,p.x+p.ed[0]);b=Math.max(b,p.y+p.ed[1]);c=Math.max(c,p.z+p.ed[2])}
return [a,b,c]}
// A bag's two loops of film round its package (1.10 side gusset G, bottom
// gusset K, 0 where none is declared): lying flat on `L x W`, 2(a + c) <= 2L + K along and
// b + c <= W + G across; standing in its `W x H x L` frame, 2(b + c) <= 2L + K and a + b <= W + G.
// Each loop is held as the axis its side bounds (`a <= L` lying flat, `c <= L` standing, by the
// rigid check that always runs first), the axis added to it, and that side. Null for a rigid
// container. O(1).
function bagGirth(boundary,declared,length){if(boundary==null)return null;
const standing=boundary.orientation==='standing';
return Object.freeze({standing,length:declared[0],width:declared[1],
side:boundary.side_gusset_depth==null?0:length(boundary.side_gusset_depth),
bottom:boundary.bottom_gusset_depth==null?0:length(boundary.bottom_gusset_depth),
along:standing?[2,1]:[0,2],across:standing?[0,1]:[1,2]})}
// The `W x H x L` frame a bag declared `L x W x H` stands in, and back.
const standingFrame=declared=>[declared[1],declared[2],declared[0]];
const declaredFrame=tmpl=>tmpl.girth?.standing?[tmpl.d[2],tmpl.d[0],tmpl.d[1]]:declaredInner(tmpl.d,tmpl.deck);
// Differences from the bounded side, not plain sums: every term stays a safe integer however
// long the sides, so 2(a + c) <= 2L + K reads exactly as 2((a - L) + c) <= K.
function girthAdmits(girth,extent){const [i,j]=girth.along,[p,q]=girth.across;
return 2*((extent[i]-girth.length)+extent[j])<=girth.bottom&&(extent[p]-girth.width)+extent[q]<=girth.side}
function bagAdmits(tmpl,placements){return girthAdmits(tmpl.girth,bagExtent(placements))}
function compatibilityIssue(item,others,tmpl){
if(item.tags.length||item.incompatible.length)for(const other of others)
if(item.incompatible.some(tag=>other.item.tags.includes(tag))||other.item.incompatible.some(tag=>item.tags.includes(tag)))
return ['incompatible_items',`${item.raw.id} is incompatible with ${other.item.raw.id}`];
for(const tag of item.tags.filter(tag=>tmpl.tagLimits[tag]!=null).sort(compareCodePoints)){
const limit=tmpl.tagLimits[tag],count=others.filter(other=>other.item.tags.includes(tag)).length;
if(count+1>limit)return ['tag_count_exceeded',`${tag}: limit ${limit}, would be ${count+1}`]}
return null
}
// On a pallet's floor the deck is the one supporter, judged by the ratio and centroid
// rule alone; the ground-contact rules name supporting items, and the floor is none.
function supportIssue(p,others,globalRatio,globalPpm,deck=null){
const rule=p.item.groundRule,required=Math.max(globalRatio,p.item.raw.minimum_support_ratio??0);
if(p.z===0)return deck==null||required<=0?null:ratioAndCentroidIssue(p,[deckSupport(deck,p)],required,globalPpm);
if((rule==null||rule==='free')&&required<=0)return null;
const supporters=directSupporters(p,others),count=supporters.length;
if(rule==='covered'){const surfaces=others.filter(o=>o.z+o.ed[2]===p.z),x2=p.x+p.ed[0],y2=p.y+p.ed[1];
if(![[p.x,p.y],[x2,p.y],[p.x,y2],[x2,y2]].every(([x,y])=>surfaces.some(s=>s.x<=x&&x<=s.x+s.ed[0]&&s.y<=y&&y<=s.y+s.ed[1])))
return ['ground_contact_violation',`covered: ${count} supporter(s), not all four corners touched`]}
if(rule==='single'&&count!==1)return ['ground_contact_violation',`single: rests on ${count} item(s)`];
if(rule==='multiple'&&count<2)return ['ground_contact_violation',`multiple: rests on ${count} item(s)`];
if(required<=0)return null;
return ratioAndCentroidIssue(p,supporters,required,globalPpm)
}
function ratioAndCentroidIssue(p,supporters,required,globalPpm){
const area=supporters.reduce((total,support)=>total+support.area,0),base=p.ed[0]*p.ed[1];
if(area<requiredArea(base,Math.max(globalPpm,p.item.supportPpm)))
return ['insufficient_support',`${area}/${base} < ${sixPlaces(...doubleFraction(required))}`];
if(area*2>base)return null;
const box={x:p.x,y:p.y,z:p.z,d:p.ed},hull=contactHull(box,supporters);
return pointInHull([BigInt(p.ed[0]),BigInt(p.ed[1])],hull)?null
:['centre_of_gravity_unsupported',`${area}/${base} met but centroid outside the ${hull.length}-point support hull`]
}
// The whole-container bearing pass, each rule reporting its first offender by instance id.
function loadIssue(boxes,graph,placements,tmpl){
const loads=topLoads(boxes,graph),label=index=>placements[index].item.id;
let index=boxes.findIndex((b,i)=>b.maxTop!=null&&loads[i]>BigInt(b.maxTop));if(index>=0)return ['top_load_exceeded',label(index)];
index=boxes.findIndex((b,i)=>b.maxCompressionKpa!=null&&pressureExceeds(appliedPressure(Number(loads[i]),b.d[0]*b.d[1]),b.maxCompressionKpa));
if(index>=0)return ['crush_violation',label(index)];
index=boxes.findIndex((b,root)=>{if(b.maxStacked==null)return false;const seen=new Set(),pending=[...graph.children[root]];
while(pending.length){const k=pending.pop();if(!seen.has(k)){seen.add(k);pending.push(...graph.children[k])}}return seen.size>b.maxStacked});
if(index>=0)return ['stacked_item_limit_exceeded',label(index)];
if(tmpl.maxStackDensity!=null){const squareMetre=16000000n*16000000n;
index=boxes.findIndex((b,i)=>(BigInt(b.w)+loads[i])*squareMetre>BigInt(tmpl.maxStackDensity)*BigInt(b.d[0])*BigInt(b.d[1]));
if(index>=0)return ['stack_density_exceeded',label(index)]}
return null
}
// `safe_route_removal_order` over the physical boxes: the first stop that cannot be emptied,
// with every placement still due there, or null.
function routeStuck(placements,tmpl,clear){
const boxes=placements.map(p=>({x:p.x+clear,y:p.y+clear,z:p.z+clear,d:{length:p.pd[0],width:p.pd[1],height:p.pd[2]}}));
const container={length:tmpl.d[0],width:tmpl.d[1],height:tmpl.d[2]},dependsOn=unloadingDependencies(boxes),present=new Set(boxes.map((_,k)=>k));
for(const stop of [...new Set(placements.map(p=>p.item.stopIndex).filter(s=>s!=null))].sort((a,b)=>a-b)){
let due=placements.map((p,k)=>k).filter(k=>placements[k].item.stopIndex===stop);
while(due.length){const removable=due.filter(k=>!dependsOn[k].some(d=>present.has(d))&&clearDirection(k,boxes,present,container,ALL_DIRECTIONS)!=null);
if(!removable.length)return {stop,indices:due};
const chosen=Math.min(...removable);present.delete(chosen);due=due.filter(k=>k!==chosen)}}
return null
}
// K1: the measure grammar of Python's `_fraction`, the reference: an optional sign and ASCII digits, a `.` with digits on both sides (at most 18 after it), `n/d`, or a mixed `w n/d`; nothing else.
// The classes spell Python's whitespace by hand, because JavaScript's `\s` and `trim` differ from it.
const PY_SPACE='\\t\\n\\v\\f\\r\\x1c-\\x1f \\x85\\xa0\\u1680\\u2000-\\u200a\\u2028\\u2029\\u202f\\u205f\\u3000',ASCII_SPACE='[ \\t\\n\\r\\f\\v]';
const MIXED_MEASURE=new RegExp(`^([+-]?[0-9]+)${ASCII_SPACE}+([0-9]+)${ASCII_SPACE}*/${ASCII_SPACE}*([0-9]+)$`),FRACTION_MEASURE=new RegExp(`^([+-]?[0-9]+)${ASCII_SPACE}*/${ASCII_SPACE}*([0-9]+)$`),DECIMAL_MEASURE=/^([+-]?)([0-9]+)(?:\.([0-9]+))?$/;
const MEASURE_SUFFIX=new RegExp(`^([^\\n]+?)[${PY_SPACE}]*(inches|ticks|inch|lbs|tick|mm|cm|ft|in|mg|kg|oz|lb|g|m)$`,'i'),PY_TRIM=new RegExp(`^[${PY_SPACE}]+|[${PY_SPACE}]+$`,'g');
function rat(s){if(typeof s==='number'&&!Number.isInteger(s))throw new RangeError('a fractional number is not a measure');
const text=String(s).replace(PY_TRIM,'').replace(/ /g,' '),mixed=MIXED_MEASURE.exec(text);
if(mixed){const d=BigInt(mixed[3]),whole=BigInt(mixed[1]),magnitude=(whole<0n?-whole:whole)*d+BigInt(mixed[2]);return [text.startsWith('-')?-magnitude:magnitude,d]}
const simple=FRACTION_MEASURE.exec(text);if(simple)return [BigInt(simple[1]),BigInt(simple[2])];
const decimal=DECIMAL_MEASURE.exec(text);if(decimal===null)throw new RangeError(`invalid decimal or fraction: ${text}`);
const places=decimal[3]??'';if(places.length>18)throw new RangeError('decimal has more fractional digits than a tick can distinguish');
const scale=10n**BigInt(places.length),magnitude=BigInt(decimal[2])*scale+BigInt(places===''?'0':places);return [decimal[1]==='-'?-magnitude:magnitude,scale]}
function round(n,d){const sg=n<0n?-1n:1n,a=n<0n?-n:n,q=a/d,r=a%d;const z=r*2n<d?q:r*2n>d?q+1n:q%2n===0n?q:q+1n;return sg*z}
function scalar(v,def,table){let raw=v,unit=def;if(v&&typeof v==='object'){raw=v.value;unit=v.unit??def}else if(typeof v==='string'){const m=MEASURE_SUFFIX.exec(v.replace(PY_TRIM,''));if(m){raw=m[1];unit=m[2]}}const[n,d]=rat(raw),exact=round(n*BigInt(table[unit.trim().toLowerCase()]),d),ticks=table===WT?exact:Number(exact);if(ticks<0)throw new RangeError(`${table===WT?'weight':'length'} cannot be negative`);return ticks}
// With no `output.length_unit`, the request's own `units.length` spelt as the schema's
// output code ("Inches" is `in`); a unit no output code names, the internal tick, gives `mm`.
/** A length measure in `unit`, and a weight measure in grams, as exact ticks: the request
* parser's own reading, for a module that builds a request rather than solving one. */
export const lengthTicks=(value,unit)=>scalar(value,unit,LEN);
export const weightTicks=value=>scalar(value,'g',WT);
function outputLengthUnit(unit){const multiplier=LEN[unit.trim().toLowerCase()];return ['mm','cm','m','in','ft'].find(code=>LEN[code]===multiplier)??'mm'}
function dims(v,u){return [scalar(v.length,u,LEN),scalar(v.width,u,LEN),scalar(v.height,u,LEN)]}
/**
* The ticks of every measure one request spells, parsed once. The request check parses
* each stated measure to refuse a bad one, through `checker`; `close` ends the filling before the
* bound and the first start read it, so every start reads the same values and none writes what
* another reads. A spelling the check did not parse is parsed on the spot and not kept; a literal
* 0 is 0 ticks in any unit the check has accepted. `O(1)` per read, `O(distinct spellings)`
* memory, for one request only.
*/
function requestMeasures(){
const tables=new Map([[LEN,new Map()],[WT,new Map()]]);let open=true;
const read=(table,value,unit)=>{
if(value===0)return table===WT?0n:0;
const byUnit=tables.get(table),known=byUnit.get(unit)?.get(value);
if(known!==undefined)return known;
const ticks=scalar(value,unit,table);
if(open){if(!byUnit.has(unit))byUnit.set(unit,new Map());byUnit.get(unit).set(value,ticks)}
return ticks};
const length=(value,unit)=>read(LEN,value,unit),weight=value=>read(WT,value,'g');
const sides=(value,unit)=>[length(value.length,unit),length(value.width,unit),length(value.height,unit)];
return {
checker:Object.freeze({length:{units:LEN,parse:length},weight:{units:WT,parse:(value,unit)=>read(WT,value,unit)}}),
close(){open=false;return Object.freeze({length,weight,sides})}};
}
// Three-element literals, not `Array.prototype.map`: an inlined `map` in optimised code builds
// a holey array where the baseline tiers build a packed one, so every consumer of a box's
// sides met two array maps and deoptimised on the second -- the hot candidate sweep included,
// each time costing it another optimising compile.
function rotate(d,r){const order=ROT[r];return [d[order[0]],d[order[1]],d[order[2]]]}
function grown(d,margin){return [d[0]+margin,d[1]+margin,d[2]+margin]}
function volume(d){return BigInt(d[0])*BigInt(d[1])*BigInt(d[2])}
function intersects(a,b){return a.x<b.x+b.d[0]&&a.x+a.d[0]>b.x&&a.y<b.y+b.d[1]&&a.y+a.d[1]>b.y&&a.z<b.z+b.d[2]&&a.z+a.d[2]>b.z}
// ---------------------------------------------------------------- irregular geometry
//
// The rule is fixed by docs/IRREGULAR-ITEMS.md. Every product here is a `BigInt`, and not for
// tidiness: a separating axis is a cross product of two edge vectors, so its components grow
// as the square of a coordinate and a projection grows as the cube. At the shared coordinate
// cap a cross product reaches 8e16 and a projection 2.4e25, while a JavaScript number is exact
// only to 2^53 ~ 9e15. Both would silently lose precision, and a collision predicate that
// rounds returns a plan that validates and does not fit. Rust carries the same arithmetic in
// `i128`; PHP needs a decimal-string fallback; here `BigInt` is already the house answer, used
// for load distribution since the first port.
/** Largest vertex coordinate a hull may carry, in ticks -- 6.25 m. Shared with every engine:
* they must refuse the same hulls or they disagree about which requests are legal. */
const MAX_HULL_COORDINATE=100000000;
const UNIT_AXES=[[1n,0n,0n],[0n,1n,0n],[0n,0n,1n]];
const sub3=(a,b)=>[a[0]-b[0],a[1]-b[1],a[2]-b[2]];
const cross3=(a,b)=>[a[1]*b[2]-a[2]*b[1],a[2]*b[0]-a[0]*b[2],a[0]*b[1]-a[1]*b[0]];
const dot3=(a,b)=>a[0]*b[0]+a[1]*b[1]+a[2]*b[2];
const big3=v=>[BigInt(v[0]),BigInt(v[1]),BigInt(v[2])];
function bigGcd(a,b){a=a<0n?-a:a;b=b<0n?-b:b;while(b){const t=a%b;a=b;b=t}return a}
/** Divide out the gcd and fix the sign, so parallel axes collapse to one entry. `null` for the
* zero vector: a cross product of parallel directions names no axis, an ordinary outcome. */
function primitiveAxis(v){
const g=bigGcd(bigGcd(v[0],v[1]),v[2]);
if(g===0n)return null;
const r=[v[0]/g,v[1]/g,v[2]/g];
const lead=r.find(x=>x!==0n);
return lead>0n?r:[-r[0],-r[1],-r[2]];
}
const axisKey=v=>`${v[0]},${v[1]},${v[2]}`;
/** Lexicographic order on the vertex vector itself. `axisKey` is for identity, never order. */
const compareVertices=(l,r)=>{
for(let i=0;i<3;i++)if(l[i]!==r[i])return l[i]<r[i]?-1:1;
return 0;
};
/** Canonicalise an authored vertex list or refuse a hull with no interior. A zero-volume hull
* is separated from everything on its own normal, so it would pass through every other item
* and still be reported as a valid placement. */
function hullValidate(vertices){
const points=vertices.map(v=>[Number(v[0]),Number(v[1]),Number(v[2])]);
if(points.length<4)throw new RangeError(`a convex hull needs at least 4 vertices, got ${points.length}`);
if(new Set(points.map(axisKey)).size!==points.length)throw new RangeError('convex hull vertices must be unique');
if(points.some(v=>v.some(c=>Math.abs(c)>MAX_HULL_COORDINATE)))
throw new RangeError(`convex hull coordinates must stay within ${MAX_HULL_COORDINATE} ticks`);
const b=points.map(big3);
for(let i=0;i<b.length;i++)for(let j=i+1;j<b.length;j++)for(let k=j+1;k<b.length;k++)for(let l=k+1;l<b.length;l++)
if(dot3(sub3(b[l],b[i]),cross3(sub3(b[j],b[i]),sub3(b[k],b[i])))!==0n)return points;
throw new RangeError('convex hull vertices are coplanar and enclose no volume');
}
/** Does the plane through `origin` with normal `axis` leave every vertex on one side? */
function isSupporting(points,origin,axis){
const offset=dot3(origin,axis);let above=false,below=false;
for(const v of points){const side=dot3(v,axis)-offset;
if(side>0n)above=true;else if(side<0n)below=true;
if(above&&below)return false}
return true;
}
/** Corners of one planar convex face, in cyclic order seen from outside.
*
* The vertices sharing a supporting plane are not all corners of the polygon they lie on: one
* can sit inside the face or part-way along an edge, and fanning over the raw set triangulates
* the wrong region -- the surface then fails to close and the volume is wrong. Gift-wrapping
* keeps only the corners, resolving collinear candidates to the farthest so an edge-interior
* vertex is walked past rather than doubled back through. */
function windFace(face,outward){
// By the vertex vector, never its decimal encoding: the walk is only correct because it
// starts from a corner, which it earns by starting from the smallest vertex under a genuine
// linear order. String order is not one -- "10,0,0" sorts before "9,0,0" -- so it can name a
// vertex lying inside the face and make the walk emit a segment that is not a hull edge.
const sorted=[...face].sort(compareVertices);
const ordered=[sorted[0]];let current=sorted[0];
for(let step=0;step<sorted.length;step++){
let next=null;
for(const candidate of sorted){
if(axisKey(candidate)===axisKey(current))continue;
if(next===null){next=candidate;continue}
const turn=dot3(cross3(sub3(next,current),sub3(candidate,current)),outward);
const reach=dot3(sub3(candidate,current),sub3(candidate,current));
const held=dot3(sub3(next,current),sub3(next,current));
if(turn<0n||(turn===0n&&reach>held))next=candidate;
}
if(next===null||axisKey(next)===axisKey(sorted[0]))break;
ordered.push(next);current=next;
}
return ordered;
}
/** Every face of the hull, each as its own corners in outward cyclic order.
*
* One walk, because the faces answer two questions at once: the volume needs them wound
* consistently, and the hull's edges are the consecutive corner pairs of the same walk. A
* plane carrying fewer than three vertices is an edge or a corner of the hull, not a face,
* and carries no edge its two adjoining faces do not already carry. */
function woundFaces(points,faceAxes){
const faces=[];
for(const axis of faceAxes)for(const outward of [axis,[-axis[0],-axis[1],-axis[2]]]){
let extreme=null;
for(const v of points){const value=dot3(v,outward);if(extreme===null||value>extreme)extreme=value}
const face=points.filter(v=>dot3(v,outward)===extreme);
if(face.length<3)continue;
faces.push(windFace(face,outward));
}
return faces;
}
/** Exact volume in cubic ticks, by the divergence theorem over the hull's own faces. */
function hullVolume(faces){
let six=0n;
for(const ordered of faces){
const apex=ordered[0];
for(let i=1;i+1<ordered.length;i++)six+=dot3(apex,cross3(ordered[i],ordered[i+1]));
}
const magnitude=six<0n?-six:six;
return magnitude/6n;
}
/** Directions of the hull's real edges, deduplicated and canonical.
*
* Every edge of a convex polyhedron is shared by exactly two faces, so walking each wound
* face and taking its consecutive corner pairs -- closing the cycle -- reaches all of them.
* The separating-axis theorem asks for exactly these, not for every vertex pair.
*
* The distinction is the whole cost of the predicate. A hull has at most `3v - 6` edges but
* `v(v - 1) / 2` vertex pairs, and the axis set is the *product* of two hulls' sets, so the
* gap squares: on a 20-vertex hull, 1351 candidate axes rather than 15616. Vertex pairs were
* never wrong, only a superset -- a pair that is not an edge names a direction no face can
* separate along, so it can add an axis but never remove one. */
function hullEdges(faces){
const edges=new Map();
for(const ordered of faces)for(let i=0;i<ordered.length;i++){
const axis=primitiveAxis(sub3(ordered[(i+1)%ordered.length],ordered[i]));
if(axis)edges.set(axisKey(axis),axis);
}
return [...edges.values()].sort(compareVertices);
}
/** A hull's separating axes and volume in its own local frame, computed once per shape. */
function hullShape(vertices){
const points=hullValidate(vertices).map(big3);
const faces=new Map();
for(let i=0;i<points.length;i++)for(let j=i+1;j<points.length;j++){
for(let k=j+1;k<points.length;k++){
// A triple whose plane cuts through the solid is not a face, and its normal separates
// nothing the real face normals do not.
const axis=primitiveAxis(cross3(sub3(points[j],points[i]),sub3(points[k],points[i])));
if(axis&&isSupporting(points,points[i],axis))faces.set(axisKey(axis),axis);
}
}
const faceAxes=[...faces.values()].sort(compareVertices);
const wound=woundFaces(points,faceAxes);
return {v:points,faces:faceAxes,edges:hullEdges(wound),volume:hullVolume(wound)};
}
/** A copied, string-exact view used only by this module's direct tests.
*
* `fallback.js` is an internal package file: package.json exposes only `index.js`, which does
* not re-export this function. Keeping the probe beside the algorithm lets the suite assert
* edge identity and ordering without widening `@packvium/engine`'s public API or handing a
* mutable cached shape to a caller. */
export function __inspectHullShapeForTests(vertices){
const shape=hullShape(vertices),copy=axes=>axes.map(axis=>axis.map(value=>value.toString()));
return {volume:shape.volume.toString(),faceAxes:copy(shape.faces),edgeDirections:copy(shape.edges)};
}
/** How many rotated hulls stay resident, before the memo is dropped and refilled. A request is
* bounded by its distinct hull items times the orientations they allow (at most 24), so this holds far more than
* any request the solver is sized for -- and bounded, rather than growing for the life of the
* process. */
const SHAPE_CACHE_ENTRIES=1024;
const shapeCache=new Map();
/** The rotated hull of one item in one orientation, built at most once.
*
* A hull depends on the item and the orientation and on nothing about where a candidate sits,
* but the collision predicate was rebuilding it on every call -- `O(v^4)` work inside an
* `O(n^2)` loop. Measured on the two-wedge fixture: 78 builds for two items, where twelve are
* the floor.
*
* Memoisation is safe here in the way it is not in general: the shape is never mutated after
* it is built, the key is the whole of what determines the value, and callers only project
* through it. Determinism is untouched -- this changes how often the answer is computed,
* never what it is. */
function shapeFor(vertices,rotation){
const key=rotation+'|'+vertices.map(v=>v.join(',')).join(';');
const found=shapeCache.get(key);
if(found!==undefined)return found;
const shape=hullShape(hullRotate(vertices,rotation));
if(shapeCache.size>=SHAPE_CACHE_ENTRIES)shapeCache.clear();
shapeCache.set(key,shape);
return shape;
}
/** A cuboid, built without searching for its own faces: both sets are the three unit axes. */
/** Lower bounds on the objective vector.
*
* The mathematics is fixed by docs/OPTIMALITY-CERTIFICATES.md. This is an independent
* implementation written from that document, and `conformance/scene/objective-bounds.json`
* holds it to the same vectors Python computes on 380 cases from the golden corpus.
*
* asks only for soundness -- the bound must never exceed the achieved objective --
* because this engine is not held to placement equality. That freedom does not extend to a
* bound: it is a function of the *request*, so there is no room for a legitimately different
* answer, and this port is held to equality because equality is achievable and stronger.
*
* `BigInt` throughout for volumes. A one-metre cube is 4.1e21 cubic ticks, past what a
* double represents exactly, and the widest intermediate multiplies a summed volume by 1e6.
* Counts, weights, costs and the parts-per-million keys come back to `Number` only once the
* arithmetic has reduced them to that scale.
*
* `O(n log n + c log c)` for `n` instances and `c` container types: one sort of the volumes,
* one of the weights, one of the per-unit costs. No geometry is touched. */
const BOUND_PPM=1000000n;
/** Every sum in the bound path must stay below this.
*
* Declared rather than inherited. This engine's `Number` stops being exact past 2^53, PHP's
* integers silently become doubles on overflow, Python's are unbounded and Rust's `i128`
* wraps -- so if each refused at its own limit the four would disagree about which requests
* are answerable. Keys 3 and 4 multiply a summed volume by `PPM`, so `10^30 * 10^6` sits
* about 170-fold inside an `i128`. Everything guarded here is `BigInt`, because a ceiling a
* representation cannot hold is a ceiling it cannot enforce. */
const MAX_BOUND_SUM=10n**30n;
// Results cross the JSON/Number boundary. Intermediates may use the wider ceiling above,
// but every returned key must fit exactly in every binding before it becomes a Number.
const MAX_BOUND_VALUE=2n**53n-1n;
/** A sum in the bound path exceeded the declared ceiling. Structured rather than a number:
* a bound that is quietly wrong is worse than none, because it will be believed. */
export class BoundOverflowError extends Error{
constructor(quantity,ceiling=MAX_BOUND_SUM,subject='sum'){
super(`${quantity} ${subject} is past the ${ceiling} ceiling the bound path declares`);
this.name='BoundOverflowError';
}
}
/** A billed objective's inventory cannot carry, at any price it lists, a packing that attains
* `L0`; no answer is compared against a bound then, so none is stated. */
class BoundWithheld extends Error{
constructor(reason){super(reason);this.name='BoundWithheld'}
}
function boundGuard(total,quantity){
if(total>MAX_BOUND_SUM)throw new BoundOverflowError(quantity);
return total;
}
function boundOutput(value,quantity){
if(value>MAX_BOUND_VALUE){
throw new BoundOverflowError(quantity,MAX_BOUND_VALUE,'bound');
}
return Number(value);
}
/** Can this item take up less room than its declared dimensions?
*
* Three ways, and each breaks the same argument -- that nominal volumes sum to something a
* solution must carry. A nested item sinks into the one below it; a `convex_hull` occupies
* its hull and leaves the rest of its bounding box free; a `compressible` item gives up
* height under load. The design document named only the first until a soundness test over
* the corpus found the omission. */
function occupiesLessThanItsBox(item){
if(item.nestingHeight!=null)return true;
return item.shapeType==='convex_hull'||item.shapeType==='compressible';
}
const boundCeilDiv=(a,b)=>(a+b-1n)/b;
const bigAscending=(a,b)=>a<b?-1:a>b?1:0;
/** Values sorted ascending, each with how many instances carry it, as `[value, count]` BigInt
* pairs. Formed per item type from a request, so a quantity of a million is one entry. */
function boundRuns(pairs){
return pairs.filter(([,count])=>count>0n).sort((a,b)=>bigAscending(a[0],b[0])||bigAscending(a[1],b[1]));
}
const runCount=runs=>runs.reduce((total,[,count])=>total+count,0n);
/** The sum of the `count` values a walk over the runs meets first. */
function runTake(runs,count){
let total=0n;
for(const [value,available] of runs){
if(count<=0n)break;
const taken=available<count?available:count;
total+=value*taken;count-=taken;
}
return total;
}
const runSmallest=(runs,count)=>runTake(runs,count);
const runLargest=(runs,count)=>runTake([...runs].reverse(),count);
/** The largest n such that the n smallest values sum to at most the capacity; all of them
* when it is unbounded. Smallest first is the whole soundness argument: the cheapest units
* maximise how many fit, so this over-estimates what any real packing achieves and the
* bound under-estimates. */
function boundFit(ascending,capacity){
if(capacity===null)return runCount(ascending);
let taken=0n,used=0n;
for(const [value,count] of ascending){
let room=count;
if(value!==0n){const fits=capacity>used?(capacity-used)/value:0n;if(fits<room)room=fits}
taken+=room;used+=value*room;
if(room<count)break;
}
return taken;
}
/** `Σ limit·quantity`, guarded, or null when the total is unbounded: some type declares no
* limit, or an unlimited quantity of a type whose limit is positive. A type that holds
* nothing adds nothing however many of it there are. Unboundedness is decided before
* anything is summed, so whether a request is refused never depends on type order, and an
* unbounded total is never guarded because no formula forms it (finding F4). */
function boundCapacity(containers,limit){
if(containers.some(c=>limit(c)===null||(c.quantity===null&&limit(c)>0n)))return null;
let total=0n;
for(const c of containers)if(c.quantity!==null)total+=limit(c)*c.quantity;
return boundGuard(total,'container capacity');
}
/** The largest declared limit, or null if any type declares none: one unlimited type makes
* the maximum unbounded and every term conditioned on it vacuous. */
function boundFiniteMax(values){
let best=null;
for(const value of values){
if(value===null)return null;
best=best===null||value>best?value:best;
}
return best;
}
const bigMax=values=>values.reduce((a,b)=>b>a?b:a,0n);
/** Every bound, in the default objective's order, from the numbers the formulas consume.
*
* The one refusal predicate of docs/OPTIMALITY-CERTIFICATES.md first: the instance volumes,
* the instance weights and each finite capacity total past MAX_BOUND_SUM, or any bound past
* MAX_BOUND_VALUE, refuse. Every later product is bounded by those totals times PPM, which
* `BigInt` carries exactly. Key 2 sorts the types by cost once and takes quantities
* greedily, the sum of the L1 cheapest per-unit costs without building that multiset (F6). */
function objectiveBoundsFromRuns(volumes,weights,shrinks,containers){
boundGuard(volumes.reduce((total,[value,count])=>total+value*count,0n),'instance volume');
boundGuard(weights.reduce((total,[value,count])=>total+value*count,0n),'instance weight');
const volumeCapacity=boundCapacity(containers,c=>c.usable);
const payloadCapacity=boundCapacity(containers,c=>c.payload);
const slotCapacity=boundCapacity(containers,c=>c.maxItems);
const count=runCount(volumes);
let placed=count;
const atMost=limit=>{if(limit<placed)placed=limit};
if(!shrinks)atMost(boundFit(volumes,volumeCapacity));
atMost(boundFit(weights,payloadCapacity));
if(slotCapacity!==null)atMost(slotCapacity);
const unpacked=count-placed;
let opened=0n;
if(placed>0n&&containers.length){
opened=1n;
const atLeast=limit=>{if(limit>opened)opened=limit};
if(!shrinks){
const largest=bigMax(containers.map(c=>c.usable));
if(largest>0n)atLeast(boundCeilDiv(runSmallest(volumes,placed),largest));
}
const payload=boundFiniteMax(containers.map(c=>c.payload));
if(payload!==null&&payload>0n)atLeast(boundCeilDiv(runSmallest(weights,placed),payload));
const slots=boundFiniteMax(containers.map(c=>c.maxItems));
if(slots!==null&&slots>0n)atLeast(boundCeilDiv(placed,slots));
}
let cost=0n,needed=opened;
for(const c of [...containers].sort((a,b)=>bigAscending(a.costMinor,b.costMinor))){
if(needed<=0n)break;
const taken=c.quantity===null||c.quantity>needed?needed:c.quantity;
cost+=c.costMinor*taken;needed-=taken;
}
let unused=0n;
if(!shrinks&&opened>0n&&containers.length){
const smallest=containers.map(c=>c.inner).reduce((a,b)=>b<a?b:a);
if(smallest>0n){
// In BigInt until it is clamped: the placed volume times PPM can reach 10^36, which a
// `Number` would round rather than carry.
const raw=opened*BOUND_PPM-boundCeilDiv(runLargest(volumes,placed)*BOUND_PPM,smallest)-(opened-1n);
unused=raw>0n?raw:0n;
}
}
let height=0n;
if(!shrinks&&opened>0n&&containers.length){
const widest=bigMax(containers.map(c=>c.baseArea)),tallest=bigMax(containers.map(c=>c.height));
if(widest>0n&&tallest>0n){
const raw=boundCeilDiv(runSmallest(volumes,placed),widest)*BOUND_PPM/tallest-(opened-1n);
height=raw>0n?raw:0n;
}
}
return [
boundOutput(unpacked,'unpacked count'),
boundOutput(opened,'container count'),
boundOutput(boundGuard(cost,'opening cost'),'opening cost'),
boundOutput(unused,'unused volume'),
boundOutput(height,'stack height'),
];
}
/** Every bound from reduced instances -- the shape the shared scene records, so this port is
* checked without reimplementing a request parser. `shrinks` is taken as given; whether this
* engine decides it correctly is asserted separately. */
function objectiveBounds(instances,containers){
return objectiveBoundsFromRuns(boundRuns(instances.map(i=>[i.volume,1n])),
boundRuns(instances.map(i=>[i.weight,1n])),instances.some(i=>i.shrinks),containers);
}
/** Where each covered objective reads its bounds: the position in the default-order vector of
* each of the objective's own score keys, or the name of the one key only that objective
* ranks by. Any other objective has no bound. */
const BOUND_ORDERS=new Map([['default',[0,1,2,3,4]],['lowest_cost',[0,2,1,3,4]],
['maximum_value',[0,'value_forgone',1,2,3]],['open_dimension_height',[0,'achieved_height',1,2,3]],
['maximum_volume',['unpacked_volume_ppm',0,1,2,3]],
['shipping_cost',[0,'billed_weight',1,3,4]],['lowest_landed_cost',[0,'landed_charge',1,3,4]]]);
/** The objectives whose own key is what a carrier bills, which needs the configuration's
* dimensional-weight divisor and units as well as the request. */
const BILLED_OBJECTIVES=new Set(['shipping_cost','lowest_landed_cost']);
/** The sum of the `count` smallest values of unsorted `[value, count]` runs, without sorting
* them: a max-heap holds only the runs the `count` smallest can still reach, and the run on
* top contributes just the part of it they need. The bound already paid for its only sorts
* (finding F6 doubled that cost once), so this is `O(t log k)` for the `k <= t` runs held. */
function runSmallestUnsorted(pairs,count){
if(count<=0n)return 0n;
const heap=[];let held=0n,total=0n;
const swap=(a,b)=>{const kept=heap[a];heap[a]=heap[b];heap[b]=kept};
const sink=()=>{for(let at=0;;){const l=2*at+1,r=l+1;let top=at;
if(l<heap.length&&heap[l][0]>heap[top][0])top=l;if(r<heap.length&&heap[r][0]>heap[top][0])top=r;
if(top===at)return;swap(at,top);at=top}};
for(const pair of pairs){
if(pair[1]<=0n||(held>=count&&pair[0]>=heap[0][0]))continue;
heap.push(pair);held+=pair[1];total+=pair[0]*pair[1];
for(let at=heap.length-1;at>0;){const parent=(at-1)>>1;if(heap[parent][0]>=heap[at][0])break;swap(at,parent);at=parent}
while(held-heap[0][1]>=count){const [value,taken]=heap[0];held-=taken;total-=value*taken;heap[0]=heap[heap.length-1];heap.pop();sink()}
}
return held>count?total-(held-count)*heap[0][0]:total;
}
/** The bound on the one key an objective ranks by and the default does not, each
* conditional on `L0` as the five are: the value and height terms hold for every packing that
* leaves exactly `unpacked` instances behind, and the volume term leads its objective and
* holds for every packing. Values are non-negative, so leaving the cheapest is the best any
* packing does; a container holding volume `v` on floor `A` stands at least `v / A` tall; and
* whatever is packed fits the usable inventory. An instance that occupies less than its box
* drops both volume terms. No term sorts: the volume runs are the ones the five bounds sorted,
* and the values are selected, so the bound stays `O(t log t + c log c)`; `BigInt` until
* `boundOutput`. */
function objectiveTerm(name,volumes,weights,values,shrinks,containers,[unpacked,opened]){
if(name==='value_forgone')return runSmallestUnsorted(values,unpacked);
const placed=runCount(volumes)-unpacked;
if(name==='billed_weight')return billedWeightBound(weights,containers,placed,opened);
if(name==='landed_charge')return landedChargeBound(weights,volumes,shrinks,containers,placed,opened);
if(shrinks)return 0n;
if(name==='achieved_height'){
const widest=bigMax(containers.map(c=>c.baseArea));
return placed>0n&&widest>0n?boundCeilDiv(runSmallest(volumes,placed),widest):0n;
}
const requested=volumes.reduce((total,[value,count])=>total+value*count,0n),capacity=boundCapacity(containers,c=>c.usable);
if(requested===0n||capacity===null)return 0n;
return boundCeilDiv((requested>capacity?requested-capacity:0n)*BOUND_PPM,requested);
}
/** The bound in a covered objective's score order. Throws `BoundOverflowError` where a
* ceiling withholds it -- the one refusal predicate's, or the objective's own term's, which
* withholds that objective's statement and no other's. */
function objectiveVector(order,volumes,weights,values,shrinks,containers){
const vector=objectiveBoundsFromRuns(volumes,weights,shrinks,containers);
return order.map(position=>typeof position==='number'?vector[position]
:boundOutput(objectiveTerm(position,volumes,weights,values,shrinks,containers,[BigInt(vector[0]),BigInt(vector[1])]),position));
}
/** What a carrier bills an opened container of this type at the least, `max(tare, dimensional)`
* in weight ticks: it is billed `max(tare + payload, dimensional)` whatever it carries. */
const billingFloor=c=>c.tare>c.dimensional?c.tare:c.dimensional;
/** The sum of the `count` smallest of `{value repeated quantity}` from `[value, quantity]`
* pairs, or null when the inventory holds fewer. Sorting the types and taking
* `min(quantity, still needed)` of each is `L2`'s rule, `O(c log c)`, without the multiset. */
function smallestFromInventory(pairs,count){
let total=0n,needed=count;
for(const [value,quantity] of [...pairs].sort((a,b)=>bigAscending(a[0],b[0]))){
if(needed<=0n)break;
const taken=quantity===null||quantity>needed?needed:quantity;
total+=value*taken;needed-=taken;
}
return needed>0n?null:total;
}
/** `shipping_cost`'s second key, summed billed weight in ticks.
*
* A packing that leaves exactly `L0` behind opens at least `opened` containers and carries at
* least the `placed` lightest instances. Each opened container is billed at least its floor
* and at least its tare plus what it carries, and a sum of maxima is at least either sum on
* its own, so the two are taken over different types. Every term is non-negative, so opening
* more only adds. `O(t + c log c)`. */
function billedWeightBound(weights,containers,placed,opened){
if(opened===0n)return 0n;
const floors=smallestFromInventory(containers.map(c=>[billingFloor(c),c.quantity]),opened);
const tares=smallestFromInventory(containers.map(c=>[c.tare,c.quantity]),opened);
if(floors===null||tares===null)throw new BoundWithheld('the inventory holds fewer containers than must be opened');
const carried=tares+runSmallest(weights,placed);
return floors>carried?floors:carried;
}
/** `lowest_landed_cost`'s second key, the summed carrier charge in minor units.
*
* Every opened container is billed in exactly one bracket and pays its charge. A container in
* bracket `[bound, charge]` weighs at most `bound`, so it is reachable only when its floor is
* within it, carries at most `bound - tare` of payload (and its `max_payload`), and at most as
* many instances as the lightest-first count under that payload, its usable volume and
* `max_items`. Three relaxations of that assignment hold and the largest is the bound: the
* cheapest reachable charge per container over `opened` containers; the least cost covering
* the placed weight; the least cost covering the placed count. Prices need not rise with
* weight, which is why a bracket is chosen rather than read off the floor. A type no bracket
* prices offers nothing: a packing that opens one is refused, never returned.
* `O(t + c b log t + c b log(c b))` for `t` runs and `b` brackets per type. */
function landedChargeBound(weights,volumes,shrinks,containers,placed,opened){
if(opened===0n||placed===0n)return 0n;
const payloadPrefix=runPrefix(weights),volumePrefix=shrinks?null:runPrefix(volumes);
const cheapest=[],offers=[];
for(const c of containers){
const floor=billingFloor(c),reachable=c.brackets.filter(([bound,charge])=>charge!==null&&floor<=bound);
if(!reachable.length)continue;
cheapest.push([reachable.reduce((least,[,charge])=>charge<least?charge:least,reachable[0][1]),c.quantity]);
const roomy=volumePrefix===null?null:prefixFit(volumePrefix,c.usable);
for(const [bound,charge] of reachable){
const carried=c.payload!==null&&c.payload<bound-c.tare?c.payload:bound-c.tare;
let count=prefixFit(payloadPrefix,carried);
if(roomy!==null&&roomy<count)count=roomy;
if(c.maxItems!==null&&c.maxItems<count)count=c.maxItems;
offers.push([charge,carried,count,c.quantity]);
}
}
const byCount=smallestFromInventory(cheapest,opened);
const byWeight=fractionalCover(offers.map(([charge,carried,,quantity])=>[charge,carried,quantity]),runSmallest(weights,placed));
const byItems=fractionalCover(offers.map(([charge,,count,quantity])=>[charge,count,quantity]),placed);
if(byCount===null||byWeight===null||byItems===null)throw new BoundWithheld('no priceable inventory carries a packing that attains L0');
return bigMax([byCount,byWeight,byItems]);
}
/** Each ascending run with the instance count and total reached at its end, so a fit is a
* binary search: `O(t)` once, `O(log t)` per question. */
function runPrefix(runs){
let count=0n,total=0n;
return runs.map(([value,taken])=>{count+=taken;total+=value*taken;return [value,count,total]});
}
/** `boundFit` over a `runPrefix`: how many of the lightest instances sum to at most `capacity`.
* The first run whose total passes it has a positive value, so it is taken in part. */
function prefixFit(prefix,capacity){
if(capacity<0n)return 0n;
let low=0,high=prefix.length;
while(low<high){const middle=(low+high)>>1;if(prefix[middle][2]>capacity)high=middle;else low=middle+1}
const [,count,total]=low===0?[0n,0n,0n]:prefix[low-1];