problemreductions/rules/unitdiskmapping/ksg/
gadgets_weighted.rs

1//! KSG weighted square lattice gadgets for resolving crossings.
2//!
3//! This module contains weighted gadget implementations for the King's SubGraph (KSG)
4//! weighted mapping. Each weighted gadget implements the Pattern trait directly with
5//! actual weight methods, following Julia's formula: mis_overhead(weighted) = mis_overhead(unweighted) * 2.
6
7use super::super::grid::{CellState, MappingGrid};
8use super::super::traits::{apply_gadget, pattern_matches, Pattern, PatternCell};
9use super::gadgets::{KsgReflectedGadget, KsgRotatedGadget, Mirror};
10use crate::rules::unitdiskmapping::{mapping_integer_overflow, mapping_invalid};
11use crate::rules::ReductionError;
12use serde::{Deserialize, Serialize};
13use std::collections::HashMap;
14
15/// Type alias for weighted pattern factory function used in crossing gadget matching.
16type WeightedPatternFactory = Box<dyn Fn() -> Box<dyn WeightedKsgPatternBoxed>>;
17
18/// Type alias for source graph representation: (locations, pin_edges, source_pins).
19pub type SourceGraph = (Vec<(usize, usize)>, Vec<(usize, usize)>, Vec<usize>);
20
21// ============================================================================
22// Weighted Crossing Gadgets
23// ============================================================================
24
25/// Weighted crossing gadget for resolving two crossing copy-lines.
26///
27/// `WeightedKsgCross<true>`: connected crossing (edges share a vertex), size (3,3)
28/// `WeightedKsgCross<false>`: disconnected crossing, size (4,5)
29#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
30pub struct WeightedKsgCross<const CON: bool>;
31
32impl Pattern for WeightedKsgCross<true> {
33    fn size(&self) -> (usize, usize) {
34        (3, 3)
35    }
36
37    fn cross_location(&self) -> (usize, usize) {
38        (2, 2)
39    }
40
41    fn is_connected(&self) -> bool {
42        true
43    }
44
45    fn is_cross_gadget(&self) -> bool {
46        true
47    }
48
49    fn connected_nodes(&self) -> Vec<usize> {
50        vec![0, 5]
51    }
52
53    fn source_graph(&self) -> (Vec<(usize, usize)>, Vec<(usize, usize)>, Vec<usize>) {
54        let locs = vec![(2, 1), (2, 2), (2, 3), (1, 2), (2, 2), (3, 2)];
55        let edges = vec![(0, 1), (1, 2), (3, 4), (4, 5), (0, 5)];
56        let pins = vec![0, 3, 5, 2];
57        (locs, edges, pins)
58    }
59
60    fn mapped_graph(&self) -> (Vec<(usize, usize)>, Vec<usize>) {
61        let locs = vec![(2, 1), (2, 2), (2, 3), (1, 2), (3, 2)];
62        let pins = vec![0, 3, 4, 2];
63        (locs, pins)
64    }
65
66    fn mis_overhead(&self) -> i64 {
67        -2 // 2x unweighted value (-1 * 2)
68    }
69
70    fn source_weights(&self) -> Vec<i64> {
71        vec![2; 6]
72    }
73
74    fn mapped_weights(&self) -> Vec<i64> {
75        vec![2; 5]
76    }
77
78    fn mapped_entry_to_compact(&self) -> HashMap<usize, usize> {
79        [
80            (5, 5),
81            (12, 12),
82            (8, 0),
83            (1, 0),
84            (0, 0),
85            (6, 6),
86            (11, 11),
87            (9, 9),
88            (14, 14),
89            (3, 3),
90            (7, 7),
91            (4, 0),
92            (13, 13),
93            (15, 15),
94            (2, 0),
95            (10, 10),
96        ]
97        .into_iter()
98        .collect()
99    }
100
101    fn source_entry_to_configs(&self) -> HashMap<usize, Vec<Vec<bool>>> {
102        let mut map = HashMap::new();
103        map.insert(0, vec![vec![false, true, false, false, true, false]]);
104        map.insert(1, vec![vec![true, false, false, false, true, false]]);
105        map.insert(3, vec![vec![true, false, false, true, false, false]]);
106        map.insert(4, vec![vec![false, true, false, false, false, true]]);
107        map.insert(6, vec![vec![false, true, false, true, false, true]]);
108        map.insert(8, vec![vec![false, false, true, false, true, false]]);
109        map.insert(9, vec![vec![true, false, true, false, true, false]]);
110        map.insert(10, vec![vec![false, false, true, true, false, false]]);
111        map.insert(11, vec![vec![true, false, true, true, false, false]]);
112        map.insert(12, vec![vec![false, false, true, false, false, true]]);
113        map.insert(14, vec![vec![false, false, true, true, false, true]]);
114        map.insert(5, vec![]);
115        map.insert(7, vec![]);
116        map.insert(13, vec![]);
117        map.insert(15, vec![]);
118        map.insert(2, vec![vec![false, true, false, true, false, false]]);
119        map
120    }
121}
122
123impl Pattern for WeightedKsgCross<false> {
124    fn size(&self) -> (usize, usize) {
125        (4, 5)
126    }
127
128    fn cross_location(&self) -> (usize, usize) {
129        (2, 3)
130    }
131
132    fn is_connected(&self) -> bool {
133        false
134    }
135
136    fn is_cross_gadget(&self) -> bool {
137        true
138    }
139
140    fn source_graph(&self) -> (Vec<(usize, usize)>, Vec<(usize, usize)>, Vec<usize>) {
141        let locs = vec![
142            (2, 1),
143            (2, 2),
144            (2, 3),
145            (2, 4),
146            (2, 5),
147            (1, 3),
148            (2, 3),
149            (3, 3),
150            (4, 3),
151        ];
152        let edges = vec![(0, 1), (1, 2), (2, 3), (3, 4), (5, 6), (6, 7), (7, 8)];
153        let pins = vec![0, 5, 8, 4];
154        (locs, edges, pins)
155    }
156
157    fn mapped_graph(&self) -> (Vec<(usize, usize)>, Vec<usize>) {
158        let locs = vec![
159            (2, 1),
160            (2, 2),
161            (2, 3),
162            (2, 4),
163            (2, 5),
164            (1, 3),
165            (3, 3),
166            (4, 3),
167            (3, 2),
168            (3, 4),
169        ];
170        let pins = vec![0, 5, 7, 4];
171        (locs, pins)
172    }
173
174    fn mis_overhead(&self) -> i64 {
175        -2 // 2x unweighted value (-1 * 2)
176    }
177
178    fn source_weights(&self) -> Vec<i64> {
179        vec![2; 9]
180    }
181
182    fn mapped_weights(&self) -> Vec<i64> {
183        vec![2; 10]
184    }
185
186    fn mapped_entry_to_compact(&self) -> HashMap<usize, usize> {
187        [
188            (5, 4),
189            (12, 4),
190            (8, 0),
191            (1, 0),
192            (0, 0),
193            (6, 0),
194            (11, 11),
195            (9, 9),
196            (14, 2),
197            (3, 2),
198            (7, 2),
199            (4, 4),
200            (13, 13),
201            (15, 11),
202            (2, 2),
203            (10, 2),
204        ]
205        .into_iter()
206        .collect()
207    }
208
209    fn source_entry_to_configs(&self) -> HashMap<usize, Vec<Vec<bool>>> {
210        let mut map = HashMap::new();
211        map.insert(
212            0,
213            vec![
214                vec![false, true, false, true, false, false, false, true, false],
215                vec![false, true, false, true, false, false, true, false, false],
216            ],
217        );
218        map.insert(
219            2,
220            vec![vec![
221                false, true, false, true, false, true, false, true, false,
222            ]],
223        );
224        map.insert(
225            4,
226            vec![vec![
227                false, true, false, true, false, false, true, false, true,
228            ]],
229        );
230        map.insert(
231            9,
232            vec![
233                vec![true, false, true, false, true, false, false, true, false],
234                vec![true, false, true, false, true, false, true, false, false],
235            ],
236        );
237        map.insert(
238            11,
239            vec![vec![
240                true, false, true, false, true, true, false, true, false,
241            ]],
242        );
243        map.insert(
244            13,
245            vec![vec![
246                true, false, true, false, true, false, true, false, true,
247            ]],
248        );
249        for i in [1, 3, 5, 6, 7, 8, 10, 12, 14, 15] {
250            map.entry(i).or_insert_with(Vec::new);
251        }
252        map
253    }
254}
255
256/// Weighted turn gadget for 90-degree turns in copy-lines.
257#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
258pub struct WeightedKsgTurn;
259
260impl Pattern for WeightedKsgTurn {
261    fn size(&self) -> (usize, usize) {
262        (4, 4)
263    }
264    fn cross_location(&self) -> (usize, usize) {
265        (3, 2)
266    }
267    fn is_connected(&self) -> bool {
268        false
269    }
270
271    fn source_graph(&self) -> (Vec<(usize, usize)>, Vec<(usize, usize)>, Vec<usize>) {
272        let locs = vec![(1, 2), (2, 2), (3, 2), (3, 3), (3, 4)];
273        let edges = vec![(0, 1), (1, 2), (2, 3), (3, 4)];
274        let pins = vec![0, 4];
275        (locs, edges, pins)
276    }
277
278    fn mapped_graph(&self) -> (Vec<(usize, usize)>, Vec<usize>) {
279        let locs = vec![(1, 2), (2, 3), (3, 4)];
280        let pins = vec![0, 2];
281        (locs, pins)
282    }
283
284    fn mis_overhead(&self) -> i64 {
285        -2 // 2x unweighted value (-1 * 2)
286    }
287
288    fn source_weights(&self) -> Vec<i64> {
289        vec![2; 5]
290    }
291
292    fn mapped_weights(&self) -> Vec<i64> {
293        vec![2; 3]
294    }
295
296    fn mapped_entry_to_compact(&self) -> HashMap<usize, usize> {
297        [(0, 0), (2, 0), (3, 3), (1, 0)].into_iter().collect()
298    }
299
300    fn source_entry_to_configs(&self) -> HashMap<usize, Vec<Vec<bool>>> {
301        let mut map = HashMap::new();
302        map.insert(0, vec![vec![false, true, false, true, false]]);
303        map.insert(
304            1,
305            vec![
306                vec![true, false, true, false, false],
307                vec![true, false, false, true, false],
308            ],
309        );
310        map.insert(
311            2,
312            vec![
313                vec![false, true, false, false, true],
314                vec![false, false, true, false, true],
315            ],
316        );
317        map.insert(3, vec![vec![true, false, true, false, true]]);
318        map
319    }
320}
321
322/// Weighted W-shaped turn gadget.
323#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
324pub struct WeightedKsgWTurn;
325
326impl Pattern for WeightedKsgWTurn {
327    fn size(&self) -> (usize, usize) {
328        (4, 4)
329    }
330    fn cross_location(&self) -> (usize, usize) {
331        (2, 2)
332    }
333    fn is_connected(&self) -> bool {
334        false
335    }
336
337    fn source_graph(&self) -> (Vec<(usize, usize)>, Vec<(usize, usize)>, Vec<usize>) {
338        let locs = vec![(2, 3), (2, 4), (3, 2), (3, 3), (4, 2)];
339        let edges = vec![(0, 1), (0, 3), (2, 3), (2, 4)];
340        let pins = vec![1, 4];
341        (locs, edges, pins)
342    }
343
344    fn mapped_graph(&self) -> (Vec<(usize, usize)>, Vec<usize>) {
345        let locs = vec![(2, 4), (3, 3), (4, 2)];
346        let pins = vec![0, 2];
347        (locs, pins)
348    }
349
350    fn mis_overhead(&self) -> i64 {
351        -2 // 2x unweighted value (-1 * 2)
352    }
353
354    fn source_weights(&self) -> Vec<i64> {
355        vec![2; 5]
356    }
357
358    fn mapped_weights(&self) -> Vec<i64> {
359        vec![2; 3]
360    }
361
362    fn mapped_entry_to_compact(&self) -> HashMap<usize, usize> {
363        [(0, 0), (2, 0), (3, 3), (1, 0)].into_iter().collect()
364    }
365
366    fn source_entry_to_configs(&self) -> HashMap<usize, Vec<Vec<bool>>> {
367        let mut map = HashMap::new();
368        map.insert(0, vec![vec![true, false, true, false, false]]);
369        map.insert(
370            1,
371            vec![
372                vec![false, true, false, true, false],
373                vec![false, true, true, false, false],
374            ],
375        );
376        map.insert(
377            2,
378            vec![
379                vec![false, false, false, true, true],
380                vec![true, false, false, false, true],
381            ],
382        );
383        map.insert(3, vec![vec![false, true, false, true, true]]);
384        map
385    }
386}
387
388/// Weighted branch gadget for T-junctions.
389#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
390pub struct WeightedKsgBranch;
391
392impl Pattern for WeightedKsgBranch {
393    fn size(&self) -> (usize, usize) {
394        (5, 4)
395    }
396    fn cross_location(&self) -> (usize, usize) {
397        (3, 2)
398    }
399    fn is_connected(&self) -> bool {
400        false
401    }
402
403    fn source_graph(&self) -> (Vec<(usize, usize)>, Vec<(usize, usize)>, Vec<usize>) {
404        let locs = vec![
405            (1, 2),
406            (2, 2),
407            (3, 2),
408            (3, 3),
409            (3, 4),
410            (4, 3),
411            (4, 2),
412            (5, 2),
413        ];
414        let edges = vec![(0, 1), (1, 2), (2, 3), (3, 4), (3, 5), (5, 6), (6, 7)];
415        let pins = vec![0, 4, 7];
416        (locs, edges, pins)
417    }
418
419    fn mapped_graph(&self) -> (Vec<(usize, usize)>, Vec<usize>) {
420        let locs = vec![(1, 2), (2, 3), (3, 2), (3, 4), (4, 3), (5, 2)];
421        let pins = vec![0, 3, 5];
422        (locs, pins)
423    }
424
425    fn mis_overhead(&self) -> i64 {
426        -2 // 2x unweighted value (-1 * 2)
427    }
428
429    // Weighted version: node 3 (0-indexed) has weight 3, others have weight 2
430    fn source_weights(&self) -> Vec<i64> {
431        vec![2, 2, 2, 3, 2, 2, 2, 2]
432    }
433
434    // Weighted version: node 1 (0-indexed) has weight 3, others have weight 2
435    fn mapped_weights(&self) -> Vec<i64> {
436        vec![2, 3, 2, 2, 2, 2]
437    }
438
439    fn mapped_entry_to_compact(&self) -> HashMap<usize, usize> {
440        [
441            (0, 0),
442            (4, 0),
443            (5, 5),
444            (6, 6),
445            (2, 0),
446            (7, 7),
447            (3, 3),
448            (1, 0),
449        ]
450        .into_iter()
451        .collect()
452    }
453
454    fn source_entry_to_configs(&self) -> HashMap<usize, Vec<Vec<bool>>> {
455        let mut map = HashMap::new();
456        map.insert(
457            0,
458            vec![vec![false, true, false, true, false, false, true, false]],
459        );
460        map.insert(
461            3,
462            vec![
463                vec![true, false, true, false, true, false, true, false],
464                vec![true, false, true, false, true, true, false, false],
465            ],
466        );
467        map.insert(
468            5,
469            vec![vec![true, false, true, false, false, true, false, true]],
470        );
471        map.insert(
472            6,
473            vec![
474                vec![false, false, true, false, true, true, false, true],
475                vec![false, true, false, false, true, true, false, true],
476            ],
477        );
478        map.insert(
479            7,
480            vec![vec![true, false, true, false, true, true, false, true]],
481        );
482        for i in [1, 2, 4] {
483            map.insert(i, vec![]);
484        }
485        map
486    }
487}
488
489/// Weighted branch fix gadget for simplifying branches.
490#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
491pub struct WeightedKsgBranchFix;
492
493impl Pattern for WeightedKsgBranchFix {
494    fn size(&self) -> (usize, usize) {
495        (4, 4)
496    }
497    fn cross_location(&self) -> (usize, usize) {
498        (2, 2)
499    }
500    fn is_connected(&self) -> bool {
501        false
502    }
503
504    fn source_graph(&self) -> (Vec<(usize, usize)>, Vec<(usize, usize)>, Vec<usize>) {
505        let locs = vec![(1, 2), (2, 2), (2, 3), (3, 3), (3, 2), (4, 2)];
506        let edges = vec![(0, 1), (1, 2), (2, 3), (3, 4), (4, 5)];
507        let pins = vec![0, 5];
508        (locs, edges, pins)
509    }
510
511    fn mapped_graph(&self) -> (Vec<(usize, usize)>, Vec<usize>) {
512        let locs = vec![(1, 2), (2, 2), (3, 2), (4, 2)];
513        let pins = vec![0, 3];
514        (locs, pins)
515    }
516
517    fn mis_overhead(&self) -> i64 {
518        -2 // 2x unweighted value (-1 * 2)
519    }
520
521    fn source_weights(&self) -> Vec<i64> {
522        vec![2; 6]
523    }
524
525    fn mapped_weights(&self) -> Vec<i64> {
526        vec![2; 4]
527    }
528
529    fn mapped_entry_to_compact(&self) -> HashMap<usize, usize> {
530        [(0, 0), (2, 2), (3, 1), (1, 1)].into_iter().collect()
531    }
532
533    fn source_entry_to_configs(&self) -> HashMap<usize, Vec<Vec<bool>>> {
534        let mut map = HashMap::new();
535        map.insert(
536            0,
537            vec![
538                vec![false, true, false, true, false, false],
539                vec![false, true, false, false, true, false],
540                vec![false, false, true, false, true, false],
541            ],
542        );
543        map.insert(1, vec![vec![true, false, true, false, true, false]]);
544        map.insert(2, vec![vec![false, true, false, true, false, true]]);
545        map.insert(
546            3,
547            vec![
548                vec![true, false, false, true, false, true],
549                vec![true, false, true, false, false, true],
550            ],
551        );
552        map
553    }
554}
555
556/// Weighted T-connection gadget.
557#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
558pub struct WeightedKsgTCon;
559
560impl Pattern for WeightedKsgTCon {
561    fn size(&self) -> (usize, usize) {
562        (3, 4)
563    }
564    fn cross_location(&self) -> (usize, usize) {
565        (2, 2)
566    }
567    fn is_connected(&self) -> bool {
568        true
569    }
570    fn connected_nodes(&self) -> Vec<usize> {
571        vec![0, 1]
572    }
573
574    fn source_graph(&self) -> (Vec<(usize, usize)>, Vec<(usize, usize)>, Vec<usize>) {
575        let locs = vec![(1, 2), (2, 1), (2, 2), (3, 2)];
576        let edges = vec![(0, 1), (0, 2), (2, 3)];
577        let pins = vec![0, 1, 3];
578        (locs, edges, pins)
579    }
580
581    fn mapped_graph(&self) -> (Vec<(usize, usize)>, Vec<usize>) {
582        let locs = vec![(1, 2), (2, 1), (2, 3), (3, 2)];
583        let pins = vec![0, 1, 3];
584        (locs, pins)
585    }
586
587    fn mis_overhead(&self) -> i64 {
588        0 // 2x unweighted value (0 * 2)
589    }
590
591    // Weighted version: node 1 (0-indexed) has weight 1, others have weight 2
592    fn source_weights(&self) -> Vec<i64> {
593        vec![2, 1, 2, 2]
594    }
595
596    // Weighted version: node 1 (0-indexed) has weight 1, others have weight 2
597    fn mapped_weights(&self) -> Vec<i64> {
598        vec![2, 1, 2, 2]
599    }
600
601    fn mapped_entry_to_compact(&self) -> HashMap<usize, usize> {
602        [
603            (0, 0),
604            (4, 0),
605            (5, 5),
606            (6, 6),
607            (2, 2),
608            (7, 7),
609            (3, 3),
610            (1, 0),
611        ]
612        .into_iter()
613        .collect()
614    }
615
616    fn source_entry_to_configs(&self) -> HashMap<usize, Vec<Vec<bool>>> {
617        let mut map = HashMap::new();
618        map.insert(0, vec![vec![false, false, true, false]]);
619        map.insert(1, vec![vec![true, false, false, false]]);
620        map.insert(2, vec![vec![false, true, true, false]]);
621        map.insert(4, vec![vec![false, false, false, true]]);
622        map.insert(5, vec![vec![true, false, false, true]]);
623        map.insert(6, vec![vec![false, true, false, true]]);
624        map.insert(3, vec![]);
625        map.insert(7, vec![]);
626        map
627    }
628}
629
630/// Weighted trivial turn gadget for simple diagonal turns.
631#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
632pub struct WeightedKsgTrivialTurn;
633
634impl Pattern for WeightedKsgTrivialTurn {
635    fn size(&self) -> (usize, usize) {
636        (2, 2)
637    }
638    fn cross_location(&self) -> (usize, usize) {
639        (2, 2)
640    }
641    fn is_connected(&self) -> bool {
642        true
643    }
644    fn connected_nodes(&self) -> Vec<usize> {
645        vec![0, 1]
646    }
647
648    fn source_graph(&self) -> (Vec<(usize, usize)>, Vec<(usize, usize)>, Vec<usize>) {
649        let locs = vec![(1, 2), (2, 1)];
650        let edges = vec![(0, 1)];
651        let pins = vec![0, 1];
652        (locs, edges, pins)
653    }
654
655    fn mapped_graph(&self) -> (Vec<(usize, usize)>, Vec<usize>) {
656        let locs = vec![(1, 2), (2, 1)];
657        let pins = vec![0, 1];
658        (locs, pins)
659    }
660
661    fn mis_overhead(&self) -> i64 {
662        0 // 2x unweighted value (0 * 2)
663    }
664
665    // Weighted version: both nodes have weight 1
666    fn source_weights(&self) -> Vec<i64> {
667        vec![1, 1]
668    }
669
670    // Weighted version: both nodes have weight 1
671    fn mapped_weights(&self) -> Vec<i64> {
672        vec![1, 1]
673    }
674
675    fn mapped_entry_to_compact(&self) -> HashMap<usize, usize> {
676        [(0, 0), (2, 2), (3, 3), (1, 1)].into_iter().collect()
677    }
678
679    fn source_entry_to_configs(&self) -> HashMap<usize, Vec<Vec<bool>>> {
680        let mut map = HashMap::new();
681        map.insert(0, vec![vec![false, false]]);
682        map.insert(1, vec![vec![true, false]]);
683        map.insert(2, vec![vec![false, true]]);
684        map.insert(3, vec![]);
685        map
686    }
687}
688
689/// Weighted end turn gadget for line terminations.
690#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
691pub struct WeightedKsgEndTurn;
692
693impl Pattern for WeightedKsgEndTurn {
694    fn size(&self) -> (usize, usize) {
695        (3, 4)
696    }
697    fn cross_location(&self) -> (usize, usize) {
698        (2, 2)
699    }
700    fn is_connected(&self) -> bool {
701        false
702    }
703
704    fn source_graph(&self) -> (Vec<(usize, usize)>, Vec<(usize, usize)>, Vec<usize>) {
705        let locs = vec![(1, 2), (2, 2), (2, 3)];
706        let edges = vec![(0, 1), (1, 2)];
707        let pins = vec![0];
708        (locs, edges, pins)
709    }
710
711    fn mapped_graph(&self) -> (Vec<(usize, usize)>, Vec<usize>) {
712        let locs = vec![(1, 2)];
713        let pins = vec![0];
714        (locs, pins)
715    }
716
717    fn mis_overhead(&self) -> i64 {
718        -2 // 2x unweighted value (-1 * 2)
719    }
720
721    // Weighted version: node 2 (0-indexed) has weight 1, others have weight 2
722    fn source_weights(&self) -> Vec<i64> {
723        vec![2, 2, 1]
724    }
725
726    // Weighted version: node 0 (0-indexed) has weight 1
727    fn mapped_weights(&self) -> Vec<i64> {
728        vec![1]
729    }
730
731    fn mapped_entry_to_compact(&self) -> HashMap<usize, usize> {
732        [(0, 0), (1, 1)].into_iter().collect()
733    }
734
735    fn source_entry_to_configs(&self) -> HashMap<usize, Vec<Vec<bool>>> {
736        let mut map = HashMap::new();
737        map.insert(0, vec![vec![false, false, true], vec![false, true, false]]);
738        map.insert(1, vec![vec![true, false, true]]);
739        map
740    }
741}
742
743/// Weighted alternate branch fix gadget.
744#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
745pub struct WeightedKsgBranchFixB;
746
747impl Pattern for WeightedKsgBranchFixB {
748    fn size(&self) -> (usize, usize) {
749        (4, 4)
750    }
751    fn cross_location(&self) -> (usize, usize) {
752        (2, 2)
753    }
754    fn is_connected(&self) -> bool {
755        false
756    }
757
758    fn source_graph(&self) -> (Vec<(usize, usize)>, Vec<(usize, usize)>, Vec<usize>) {
759        let locs = vec![(2, 3), (3, 2), (3, 3), (4, 2)];
760        let edges = vec![(0, 2), (1, 2), (1, 3)];
761        let pins = vec![0, 3];
762        (locs, edges, pins)
763    }
764
765    fn mapped_graph(&self) -> (Vec<(usize, usize)>, Vec<usize>) {
766        let locs = vec![(3, 2), (4, 2)];
767        let pins = vec![0, 1];
768        (locs, pins)
769    }
770
771    fn mis_overhead(&self) -> i64 {
772        -2 // 2x unweighted value (-1 * 2)
773    }
774
775    // Weighted version: node 0 (0-indexed) has weight 1, others have weight 2
776    fn source_weights(&self) -> Vec<i64> {
777        vec![1, 2, 2, 2]
778    }
779
780    // Weighted version: node 0 (0-indexed) has weight 1, node 1 has weight 2
781    fn mapped_weights(&self) -> Vec<i64> {
782        vec![1, 2]
783    }
784
785    fn mapped_entry_to_compact(&self) -> HashMap<usize, usize> {
786        [(0, 0), (2, 2), (3, 3), (1, 1)].into_iter().collect()
787    }
788
789    fn source_entry_to_configs(&self) -> HashMap<usize, Vec<Vec<bool>>> {
790        let mut map = HashMap::new();
791        map.insert(
792            0,
793            vec![
794                vec![false, false, true, false],
795                vec![false, true, false, false],
796            ],
797        );
798        map.insert(1, vec![vec![true, true, false, false]]);
799        map.insert(2, vec![vec![false, false, true, true]]);
800        map.insert(3, vec![vec![true, false, false, true]]);
801        map
802    }
803}
804
805/// Weighted dangling leg simplifier pattern.
806#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
807pub struct WeightedKsgDanglingLeg;
808
809impl Pattern for WeightedKsgDanglingLeg {
810    fn size(&self) -> (usize, usize) {
811        (4, 3)
812    }
813    fn cross_location(&self) -> (usize, usize) {
814        (2, 1)
815    }
816    fn is_connected(&self) -> bool {
817        false
818    }
819
820    fn source_graph(&self) -> (Vec<(usize, usize)>, Vec<(usize, usize)>, Vec<usize>) {
821        let locs = vec![(2, 2), (3, 2), (4, 2)];
822        let edges = vec![(0, 1), (1, 2)];
823        let pins = vec![2];
824        (locs, edges, pins)
825    }
826
827    fn mapped_graph(&self) -> (Vec<(usize, usize)>, Vec<usize>) {
828        let locs = vec![(4, 2)];
829        let pins = vec![0];
830        (locs, pins)
831    }
832
833    fn mis_overhead(&self) -> i64 {
834        -2 // 2x unweighted value (-1 * 2)
835    }
836
837    // Weighted version: node 0 (0-indexed) has weight 1, others have weight 2
838    fn source_weights(&self) -> Vec<i64> {
839        vec![1, 2, 2]
840    }
841
842    // Weighted version: node 0 (0-indexed) has weight 1
843    fn mapped_weights(&self) -> Vec<i64> {
844        vec![1]
845    }
846
847    fn mapped_entry_to_compact(&self) -> HashMap<usize, usize> {
848        [(0, 0), (1, 1)].into_iter().collect()
849    }
850
851    fn source_entry_to_configs(&self) -> HashMap<usize, Vec<Vec<bool>>> {
852        let mut map = HashMap::new();
853        map.insert(0, vec![vec![true, false, false], vec![false, true, false]]);
854        map.insert(1, vec![vec![true, false, true]]);
855        map
856    }
857}
858
859// ============================================================================
860// WeightedKsgPattern Enum for Dynamic Dispatch
861// ============================================================================
862
863/// Enum wrapping all weighted KSG square lattice patterns for dynamic dispatch during unapply.
864#[derive(Debug, Clone)]
865pub enum WeightedKsgPattern {
866    CrossFalse(WeightedKsgCross<false>),
867    CrossTrue(WeightedKsgCross<true>),
868    Turn(WeightedKsgTurn),
869    WTurn(WeightedKsgWTurn),
870    Branch(WeightedKsgBranch),
871    BranchFix(WeightedKsgBranchFix),
872    TCon(WeightedKsgTCon),
873    TrivialTurn(WeightedKsgTrivialTurn),
874    EndTurn(WeightedKsgEndTurn),
875    BranchFixB(WeightedKsgBranchFixB),
876    DanglingLeg(WeightedKsgDanglingLeg),
877    RotatedTCon1(KsgRotatedGadget<WeightedKsgTCon>),
878    ReflectedCrossTrue(KsgReflectedGadget<WeightedKsgCross<true>>),
879    ReflectedTrivialTurn(KsgReflectedGadget<WeightedKsgTrivialTurn>),
880    ReflectedRotatedTCon1(KsgReflectedGadget<KsgRotatedGadget<WeightedKsgTCon>>),
881    DanglingLegRot1(KsgRotatedGadget<WeightedKsgDanglingLeg>),
882    DanglingLegRot2(KsgRotatedGadget<KsgRotatedGadget<WeightedKsgDanglingLeg>>),
883    DanglingLegRot3(KsgRotatedGadget<KsgRotatedGadget<KsgRotatedGadget<WeightedKsgDanglingLeg>>>),
884    DanglingLegReflX(KsgReflectedGadget<WeightedKsgDanglingLeg>),
885    DanglingLegReflY(KsgReflectedGadget<WeightedKsgDanglingLeg>),
886}
887
888impl WeightedKsgPattern {
889    /// Get pattern from tape index.
890    pub fn from_tape_idx(idx: usize) -> Option<Self> {
891        match idx {
892            0 => Some(Self::CrossFalse(WeightedKsgCross::<false>)),
893            1 => Some(Self::Turn(WeightedKsgTurn)),
894            2 => Some(Self::WTurn(WeightedKsgWTurn)),
895            3 => Some(Self::Branch(WeightedKsgBranch)),
896            4 => Some(Self::BranchFix(WeightedKsgBranchFix)),
897            5 => Some(Self::TCon(WeightedKsgTCon)),
898            6 => Some(Self::TrivialTurn(WeightedKsgTrivialTurn)),
899            7 => Some(Self::RotatedTCon1(KsgRotatedGadget::new(
900                WeightedKsgTCon,
901                1,
902            ))),
903            8 => Some(Self::ReflectedCrossTrue(KsgReflectedGadget::new(
904                WeightedKsgCross::<true>,
905                Mirror::Y,
906            ))),
907            9 => Some(Self::ReflectedTrivialTurn(KsgReflectedGadget::new(
908                WeightedKsgTrivialTurn,
909                Mirror::Y,
910            ))),
911            10 => Some(Self::BranchFixB(WeightedKsgBranchFixB)),
912            11 => Some(Self::EndTurn(WeightedKsgEndTurn)),
913            12 => Some(Self::ReflectedRotatedTCon1(KsgReflectedGadget::new(
914                KsgRotatedGadget::new(WeightedKsgTCon, 1),
915                Mirror::Y,
916            ))),
917            100 => Some(Self::DanglingLeg(WeightedKsgDanglingLeg)),
918            101 => Some(Self::DanglingLegRot1(KsgRotatedGadget::new(
919                WeightedKsgDanglingLeg,
920                1,
921            ))),
922            102 => Some(Self::DanglingLegRot2(KsgRotatedGadget::new(
923                KsgRotatedGadget::new(WeightedKsgDanglingLeg, 1),
924                1,
925            ))),
926            103 => Some(Self::DanglingLegRot3(KsgRotatedGadget::new(
927                KsgRotatedGadget::new(KsgRotatedGadget::new(WeightedKsgDanglingLeg, 1), 1),
928                1,
929            ))),
930            104 => Some(Self::DanglingLegReflX(KsgReflectedGadget::new(
931                WeightedKsgDanglingLeg,
932                Mirror::X,
933            ))),
934            105 => Some(Self::DanglingLegReflY(KsgReflectedGadget::new(
935                WeightedKsgDanglingLeg,
936                Mirror::Y,
937            ))),
938            _ => None,
939        }
940    }
941
942    /// Apply map_config_back_pattern for this pattern.
943    pub(crate) fn map_config_back(
944        &self,
945        gi: usize,
946        gj: usize,
947        config: &mut [Vec<usize>],
948    ) -> Result<(), ReductionError> {
949        match self {
950            Self::CrossFalse(p) => map_config_back_pattern(p, gi, gj, config),
951            Self::CrossTrue(p) => map_config_back_pattern(p, gi, gj, config),
952            Self::Turn(p) => map_config_back_pattern(p, gi, gj, config),
953            Self::WTurn(p) => map_config_back_pattern(p, gi, gj, config),
954            Self::Branch(p) => map_config_back_pattern(p, gi, gj, config),
955            Self::BranchFix(p) => map_config_back_pattern(p, gi, gj, config),
956            Self::TCon(p) => map_config_back_pattern(p, gi, gj, config),
957            Self::TrivialTurn(p) => map_config_back_pattern(p, gi, gj, config),
958            Self::EndTurn(p) => map_config_back_pattern(p, gi, gj, config),
959            Self::BranchFixB(p) => map_config_back_pattern(p, gi, gj, config),
960            Self::DanglingLeg(p) => map_config_back_pattern(p, gi, gj, config),
961            Self::RotatedTCon1(p) => map_config_back_pattern(p, gi, gj, config),
962            Self::ReflectedCrossTrue(p) => map_config_back_pattern(p, gi, gj, config),
963            Self::ReflectedTrivialTurn(p) => map_config_back_pattern(p, gi, gj, config),
964            Self::ReflectedRotatedTCon1(p) => map_config_back_pattern(p, gi, gj, config),
965            Self::DanglingLegRot1(p) => map_config_back_pattern(p, gi, gj, config),
966            Self::DanglingLegRot2(p) => map_config_back_pattern(p, gi, gj, config),
967            Self::DanglingLegRot3(p) => map_config_back_pattern(p, gi, gj, config),
968            Self::DanglingLegReflX(p) => map_config_back_pattern(p, gi, gj, config),
969            Self::DanglingLegReflY(p) => map_config_back_pattern(p, gi, gj, config),
970        }
971    }
972}
973
974// ============================================================================
975// Weighted Tape Entry and Apply Functions
976// ============================================================================
977
978/// A tape entry recording a weighted gadget application.
979#[derive(Debug, Clone, serde::Serialize, serde::Deserialize)]
980pub struct WeightedKsgTapeEntry {
981    pub pattern_idx: usize,
982    pub row: usize,
983    pub col: usize,
984}
985
986/// Calculate MIS overhead for a weighted tape entry.
987pub fn weighted_tape_entry_mis_overhead(
988    entry: &WeightedKsgTapeEntry,
989) -> Result<i64, ReductionError> {
990    Ok(match entry.pattern_idx {
991        0 => WeightedKsgCross::<false>.mis_overhead(),
992        1 => WeightedKsgTurn.mis_overhead(),
993        2 => WeightedKsgWTurn.mis_overhead(),
994        3 => WeightedKsgBranch.mis_overhead(),
995        4 => WeightedKsgBranchFix.mis_overhead(),
996        5 => WeightedKsgTCon.mis_overhead(),
997        6 => WeightedKsgTrivialTurn.mis_overhead(),
998        7 => KsgRotatedGadget::new(WeightedKsgTCon, 1).mis_overhead(),
999        8 => KsgReflectedGadget::new(WeightedKsgCross::<true>, Mirror::Y).mis_overhead(),
1000        9 => KsgReflectedGadget::new(WeightedKsgTrivialTurn, Mirror::Y).mis_overhead(),
1001        10 => WeightedKsgBranchFixB.mis_overhead(),
1002        11 => WeightedKsgEndTurn.mis_overhead(),
1003        12 => KsgReflectedGadget::new(KsgRotatedGadget::new(WeightedKsgTCon, 1), Mirror::Y)
1004            .mis_overhead(),
1005        100..=105 => WeightedKsgDanglingLeg.mis_overhead(),
1006        _ => {
1007            return Err(mapping_invalid(
1008                "tape contains an unknown weighted KSG gadget index",
1009            ))
1010        }
1011    })
1012}
1013
1014/// Trait for boxed weighted pattern operations.
1015pub trait WeightedKsgPatternBoxed {
1016    fn size_boxed(&self) -> (usize, usize);
1017    fn cross_location(&self) -> (usize, usize);
1018    fn source_matrix(&self) -> Vec<Vec<PatternCell>>;
1019    fn mapped_matrix(&self) -> Vec<Vec<PatternCell>>;
1020    fn source_graph_boxed(&self) -> SourceGraph;
1021    fn mapped_graph_boxed(&self) -> (Vec<(usize, usize)>, Vec<usize>);
1022    fn source_weights_boxed(&self) -> Vec<i64>;
1023    fn mapped_weights_boxed(&self) -> Vec<i64>;
1024    fn pattern_matches_boxed(&self, grid: &MappingGrid, i: usize, j: usize) -> bool;
1025    fn apply_gadget_boxed(&self, grid: &mut MappingGrid, i: usize, j: usize);
1026    fn apply_weighted_gadget_boxed(&self, grid: &mut MappingGrid, i: usize, j: usize);
1027}
1028
1029impl<P: Pattern> WeightedKsgPatternBoxed for P {
1030    fn size_boxed(&self) -> (usize, usize) {
1031        self.size()
1032    }
1033    fn cross_location(&self) -> (usize, usize) {
1034        Pattern::cross_location(self)
1035    }
1036    fn source_matrix(&self) -> Vec<Vec<PatternCell>> {
1037        Pattern::source_matrix(self)
1038    }
1039    fn mapped_matrix(&self) -> Vec<Vec<PatternCell>> {
1040        Pattern::mapped_matrix(self)
1041    }
1042    fn source_graph_boxed(&self) -> SourceGraph {
1043        Pattern::source_graph(self)
1044    }
1045    fn mapped_graph_boxed(&self) -> (Vec<(usize, usize)>, Vec<usize>) {
1046        Pattern::mapped_graph(self)
1047    }
1048    fn source_weights_boxed(&self) -> Vec<i64> {
1049        Pattern::source_weights(self)
1050    }
1051    fn mapped_weights_boxed(&self) -> Vec<i64> {
1052        Pattern::mapped_weights(self)
1053    }
1054    fn pattern_matches_boxed(&self, grid: &MappingGrid, i: usize, j: usize) -> bool {
1055        pattern_matches(self, grid, i, j)
1056    }
1057    fn apply_gadget_boxed(&self, grid: &mut MappingGrid, i: usize, j: usize) {
1058        apply_gadget(self, grid, i, j);
1059    }
1060    fn apply_weighted_gadget_boxed(&self, grid: &mut MappingGrid, i: usize, j: usize) {
1061        apply_weighted_gadget(self, grid, i, j);
1062    }
1063}
1064
1065/// Apply a weighted gadget pattern at position (i, j) with proper weights.
1066/// Uses mapped_graph locations and mapped_weights for each node.
1067#[allow(clippy::needless_range_loop)]
1068pub fn apply_weighted_gadget<P: Pattern>(pattern: &P, grid: &mut MappingGrid, i: usize, j: usize) {
1069    let (m, n) = pattern.size();
1070    let (mapped_locs, _) = pattern.mapped_graph();
1071    let mapped_weights = pattern.mapped_weights();
1072
1073    // First clear the gadget area
1074    for r in 0..m {
1075        for c in 0..n {
1076            let grid_r = i + r;
1077            let grid_c = j + c;
1078            grid.set(grid_r, grid_c, CellState::Empty);
1079        }
1080    }
1081
1082    // Build a map of (row, col) -> accumulated weight for doubled nodes
1083    let mut weight_map: HashMap<(usize, usize), i64> = HashMap::new();
1084    for (idx, &(r, c)) in mapped_locs.iter().enumerate() {
1085        let weight = mapped_weights[idx];
1086        *weight_map.entry((r, c)).or_insert(0) += weight;
1087    }
1088
1089    // Count occurrences to detect doubled nodes
1090    let mut count_map: HashMap<(usize, usize), usize> = HashMap::new();
1091    for &(r, c) in &mapped_locs {
1092        *count_map.entry((r, c)).or_insert(0) += 1;
1093    }
1094
1095    // Set cells with proper weights
1096    for (&(r, c), &total_weight) in &weight_map {
1097        let grid_r = i + r - 1; // Convert 1-indexed to 0-indexed
1098        let grid_c = j + c - 1;
1099        let count = count_map[&(r, c)];
1100
1101        let state = if count > 1 {
1102            CellState::Doubled {
1103                weight: total_weight,
1104            }
1105        } else {
1106            CellState::Occupied {
1107                weight: total_weight,
1108            }
1109        };
1110        grid.set(grid_r, grid_c, state);
1111    }
1112}
1113
1114/// Apply all weighted crossing gadgets to the grid.
1115pub fn apply_weighted_crossing_gadgets(
1116    grid: &mut MappingGrid,
1117    copylines: &[super::super::copyline::CopyLine],
1118) -> Vec<WeightedKsgTapeEntry> {
1119    let mut tape = Vec::new();
1120    let n = copylines.len();
1121
1122    for j in 0..n {
1123        for i in 0..n {
1124            let (cross_row, cross_col) = crossat(grid, copylines, i, j);
1125            if let Some((pattern_idx, row, col)) =
1126                try_match_and_apply_weighted_crossing(grid, cross_row, cross_col)
1127            {
1128                tape.push(WeightedKsgTapeEntry {
1129                    pattern_idx,
1130                    row,
1131                    col,
1132                });
1133            }
1134        }
1135    }
1136    tape
1137}
1138
1139/// Calculate crossing point for two copylines.
1140fn crossat(
1141    grid: &MappingGrid,
1142    copylines: &[super::super::copyline::CopyLine],
1143    v: usize,
1144    w: usize,
1145) -> (usize, usize) {
1146    let line_v = copylines.get(v);
1147    let line_w = copylines.get(w);
1148
1149    match (line_v, line_w) {
1150        (Some(lv), Some(lw)) => {
1151            let (line_first, line_second) = if lv.vslot < lw.vslot {
1152                (lv, lw)
1153            } else {
1154                (lw, lv)
1155            };
1156            grid.cross_at(line_first.vslot, line_second.vslot, line_first.hslot)
1157        }
1158        _ => (0, 0),
1159    }
1160}
1161
1162fn try_match_and_apply_weighted_crossing(
1163    grid: &mut MappingGrid,
1164    cross_row: usize,
1165    cross_col: usize,
1166) -> Option<(usize, usize, usize)> {
1167    // Try each pattern in order
1168    let patterns: Vec<(usize, WeightedPatternFactory)> = vec![
1169        (0, Box::new(|| Box::new(WeightedKsgCross::<false>))),
1170        (1, Box::new(|| Box::new(WeightedKsgTurn))),
1171        (2, Box::new(|| Box::new(WeightedKsgWTurn))),
1172        (3, Box::new(|| Box::new(WeightedKsgBranch))),
1173        (4, Box::new(|| Box::new(WeightedKsgBranchFix))),
1174        (5, Box::new(|| Box::new(WeightedKsgTCon))),
1175        (6, Box::new(|| Box::new(WeightedKsgTrivialTurn))),
1176        (
1177            7,
1178            Box::new(|| Box::new(KsgRotatedGadget::new(WeightedKsgTCon, 1))),
1179        ),
1180        (
1181            8,
1182            Box::new(|| Box::new(KsgReflectedGadget::new(WeightedKsgCross::<true>, Mirror::Y))),
1183        ),
1184        (
1185            9,
1186            Box::new(|| Box::new(KsgReflectedGadget::new(WeightedKsgTrivialTurn, Mirror::Y))),
1187        ),
1188        (10, Box::new(|| Box::new(WeightedKsgBranchFixB))),
1189        (11, Box::new(|| Box::new(WeightedKsgEndTurn))),
1190        (
1191            12,
1192            Box::new(|| {
1193                Box::new(KsgReflectedGadget::new(
1194                    KsgRotatedGadget::new(WeightedKsgTCon, 1),
1195                    Mirror::Y,
1196                ))
1197            }),
1198        ),
1199    ];
1200
1201    for (idx, make_pattern) in patterns {
1202        let pattern = make_pattern();
1203        let cl = pattern.cross_location();
1204        if cross_row + 1 >= cl.0 && cross_col + 1 >= cl.1 {
1205            let x = cross_row + 1 - cl.0;
1206            let y = cross_col + 1 - cl.1;
1207            let matches = pattern.pattern_matches_boxed(grid, x, y);
1208            if matches {
1209                pattern.apply_weighted_gadget_boxed(grid, x, y);
1210                return Some((idx, x, y));
1211            }
1212        }
1213    }
1214    None
1215}
1216
1217/// Apply weighted simplifier gadgets (WeightedKsgDanglingLeg variants).
1218pub fn apply_weighted_simplifier_gadgets(
1219    grid: &mut MappingGrid,
1220    nrepeat: usize,
1221) -> Vec<WeightedKsgTapeEntry> {
1222    let mut tape = Vec::new();
1223    let (rows, cols) = grid.size();
1224
1225    let patterns = rotated_and_reflected_weighted_danglingleg();
1226
1227    for _ in 0..nrepeat {
1228        for (pattern_idx, pattern) in patterns.iter().enumerate() {
1229            for j in 0..cols {
1230                for i in 0..rows {
1231                    if pattern_matches_weighted(pattern.as_ref(), grid, i, j) {
1232                        pattern.apply_weighted_gadget_boxed(grid, i, j);
1233                        tape.push(WeightedKsgTapeEntry {
1234                            pattern_idx: 100 + pattern_idx,
1235                            row: i,
1236                            col: j,
1237                        });
1238                    }
1239                }
1240            }
1241        }
1242    }
1243
1244    tape
1245}
1246
1247/// Check if a weighted KsgDanglingLeg pattern matches.
1248/// For weighted mode, the center node must have weight 1.
1249fn pattern_matches_weighted(
1250    pattern: &dyn WeightedKsgPatternBoxed,
1251    grid: &MappingGrid,
1252    i: usize,
1253    j: usize,
1254) -> bool {
1255    // First check basic pattern match
1256    if !pattern.pattern_matches_boxed(grid, i, j) {
1257        return false;
1258    }
1259
1260    // Check that source weights match the grid weights
1261    let (locs, _, _) = pattern.source_graph_boxed();
1262    let source_weights = pattern.source_weights_boxed();
1263
1264    for (idx, (loc_r, loc_c)) in locs.iter().enumerate() {
1265        let grid_r = i + loc_r - 1;
1266        let grid_c = j + loc_c - 1;
1267        if let Some(cell) = grid.get(grid_r, grid_c) {
1268            let expected_weight = source_weights[idx];
1269            if cell.weight() != expected_weight {
1270                return false;
1271            }
1272        }
1273    }
1274
1275    true
1276}
1277
1278fn rotated_and_reflected_weighted_danglingleg() -> Vec<Box<dyn WeightedKsgPatternBoxed>> {
1279    vec![
1280        Box::new(WeightedKsgDanglingLeg),
1281        Box::new(KsgRotatedGadget::new(WeightedKsgDanglingLeg, 1)),
1282        Box::new(KsgRotatedGadget::new(WeightedKsgDanglingLeg, 2)),
1283        Box::new(KsgRotatedGadget::new(WeightedKsgDanglingLeg, 3)),
1284        Box::new(KsgReflectedGadget::new(WeightedKsgDanglingLeg, Mirror::X)),
1285        Box::new(KsgReflectedGadget::new(WeightedKsgDanglingLeg, Mirror::Y)),
1286    ]
1287}
1288
1289/// Map configuration back through a single gadget.
1290pub(crate) fn map_config_back_pattern<P: Pattern>(
1291    pattern: &P,
1292    gi: usize,
1293    gj: usize,
1294    config: &mut [Vec<usize>],
1295) -> Result<(), ReductionError> {
1296    let (m, n) = pattern.size();
1297    let (mapped_locs, mapped_pins) = pattern.mapped_graph();
1298    let (source_locs, _, _) = pattern.source_graph();
1299
1300    // Step 1: Extract config at mapped locations
1301    let mapped_config: Vec<usize> = mapped_locs
1302        .iter()
1303        .map(|&(r, c)| {
1304            let row = gi + r - 1;
1305            let col = gj + c - 1;
1306            config
1307                .get(row)
1308                .and_then(|row_vec| row_vec.get(col))
1309                .copied()
1310                .ok_or(mapping_invalid(
1311                    "weighted KSG gadget lies outside the configuration grid",
1312                ))
1313        })
1314        .collect::<Result<_, _>>()?;
1315
1316    // Step 2: Compute boundary config
1317    let bc = {
1318        let mut result = 0usize;
1319        for (i, &pin_idx) in mapped_pins.iter().enumerate() {
1320            if *mapped_config.get(pin_idx).ok_or(mapping_invalid(
1321                "weighted KSG gadget contains an invalid mapped pin index",
1322            ))? > 0
1323            {
1324                result |= 1 << i;
1325            }
1326        }
1327        result
1328    };
1329
1330    // Step 3: Look up source config
1331    let d1 = pattern.mapped_entry_to_compact();
1332    let d2 = pattern.source_entry_to_configs();
1333
1334    let compact = d1.get(&bc).copied().ok_or(mapping_invalid(
1335        "weighted KSG boundary configuration has no source equivalent",
1336    ))?;
1337    let new_config =
1338        d2.get(&compact)
1339            .and_then(|configs| configs.first())
1340            .ok_or(mapping_invalid(
1341                "weighted KSG compact state has no source configuration",
1342            ))?;
1343    if new_config.len() != source_locs.len() {
1344        return Err(mapping_invalid(
1345            "weighted KSG source configuration has the wrong length",
1346        ));
1347    }
1348
1349    // Step 4: Clear gadget area
1350    for row in gi..gi + m {
1351        for col in gj..gj + n {
1352            *config
1353                .get_mut(row)
1354                .and_then(|row_vec| row_vec.get_mut(col))
1355                .ok_or(mapping_invalid(
1356                    "weighted KSG gadget lies outside the configuration grid",
1357                ))? = 0;
1358        }
1359    }
1360
1361    // Step 5: Write source config
1362    for (k, &(r, c)) in source_locs.iter().enumerate() {
1363        let row = gi + r - 1;
1364        let col = gj + c - 1;
1365        let cell = config
1366            .get_mut(row)
1367            .and_then(|row_vec| row_vec.get_mut(col))
1368            .ok_or(mapping_invalid(
1369                "weighted KSG source position lies outside the configuration grid",
1370            ))?;
1371        *cell = cell
1372            .checked_add(usize::from(new_config[k]))
1373            .ok_or(mapping_integer_overflow(
1374                "accumulating a weighted KSG source configuration",
1375            ))?;
1376    }
1377
1378    Ok(())
1379}
1380
1381#[cfg(test)]
1382#[path = "../../../unit_tests/rules/unitdiskmapping/ksg/gadgets_weighted.rs"]
1383mod tests;
problemreductions/rules/unitdiskmapping/ksg/gadgets_weighted.rs

problemreductions/rules/unitdiskmapping/ksg/
gadgets_weighted.rs
