rust_coinselect/algorithms/
fifo.rs

1use crate::{
2    types::{CoinSelectionOpt, OutputGroup, SelectionError, SelectionOutput, WasteMetric},
3    utils::{calculate_fee, calculate_waste},
4};
5
6/// Performs coin selection using the First-In-First-Out (FIFO) algorithm.
7///
8/// Returns `NoSolutionFound` if no solution is found.
9pub fn select_coin_fifo(
10    inputs: &[OutputGroup],
11    options: &CoinSelectionOpt,
12) -> Result<SelectionOutput, SelectionError> {
13    let mut accumulated_value: u64 = 0;
14    let mut accumulated_weight: u64 = 0;
15    let mut selected_inputs: Vec<usize> = Vec::new();
16    let mut estimated_fees: u64 = 0;
17
18    // Sorting the inputs vector based on creation_sequence
19    let mut sorted_inputs: Vec<_> = inputs
20        .iter()
21        .enumerate()
22        .filter(|(_, og)| og.creation_sequence.is_some())
23        .collect();
24
25    sorted_inputs.sort_by(|a, b| a.1.creation_sequence.cmp(&b.1.creation_sequence));
26
27    let inputs_without_sequence: Vec<_> = inputs
28        .iter()
29        .enumerate()
30        .filter(|(_, og)| og.creation_sequence.is_none())
31        .collect();
32
33    sorted_inputs.extend(inputs_without_sequence);
34
35    for (index, inputs) in sorted_inputs {
36        estimated_fees =
37            calculate_fee(accumulated_weight, options.target_feerate).unwrap_or_default();
38        if accumulated_value
39            >= (options.target_value
40                + estimated_fees.max(options.min_absolute_fee)
41                + options.min_change_value)
42        {
43            break;
44        }
45        accumulated_value += inputs.value;
46        accumulated_weight += inputs.weight;
47        selected_inputs.push(index);
48    }
49    if accumulated_value
50        < (options.target_value
51            + estimated_fees.max(options.min_absolute_fee)
52            + options.min_change_value)
53    {
54        Err(SelectionError::InsufficientFunds)
55    } else {
56        let waste: u64 = calculate_waste(
57            options,
58            accumulated_value,
59            accumulated_weight,
60            estimated_fees,
61        );
62        Ok(SelectionOutput {
63            selected_inputs,
64            waste: WasteMetric(waste),
65        })
66    }
67}
68
69#[cfg(test)]
70mod test {
71
72    use crate::{
73        algorithms::fifo::select_coin_fifo,
74        types::{CoinSelectionOpt, ExcessStrategy, OutputGroup, SelectionError},
75    };
76
77    fn setup_basic_output_groups() -> Vec<OutputGroup> {
78        vec![
79            OutputGroup {
80                value: 1000,
81                weight: 100,
82                input_count: 1,
83                creation_sequence: None,
84            },
85            OutputGroup {
86                value: 2000,
87                weight: 200,
88                input_count: 1,
89                creation_sequence: None,
90            },
91            OutputGroup {
92                value: 3000,
93                weight: 300,
94                input_count: 1,
95                creation_sequence: None,
96            },
97        ]
98    }
99    fn setup_output_groups_withsequence() -> Vec<OutputGroup> {
100        vec![
101            OutputGroup {
102                value: 1000,
103                weight: 100,
104                input_count: 1,
105                creation_sequence: Some(1),
106            },
107            OutputGroup {
108                value: 2000,
109                weight: 200,
110                input_count: 1,
111                creation_sequence: Some(5000),
112            },
113            OutputGroup {
114                value: 3000,
115                weight: 300,
116                input_count: 1,
117                creation_sequence: Some(1001),
118            },
119            OutputGroup {
120                value: 1500,
121                weight: 150,
122                input_count: 1,
123                creation_sequence: None,
124            },
125        ]
126    }
127
128    fn setup_options(target_value: u64) -> CoinSelectionOpt {
129        CoinSelectionOpt {
130            target_value,
131            target_feerate: 0.4, // Simplified feerate
132            long_term_feerate: Some(0.4),
133            min_absolute_fee: 0,
134            base_weight: 10,
135            change_weight: 50,
136            change_cost: 10,
137            avg_input_weight: 20,
138            avg_output_weight: 10,
139            min_change_value: 500,
140            excess_strategy: ExcessStrategy::ToChange,
141        }
142    }
143
144    fn test_successful_selection() {
145        let mut inputs = setup_basic_output_groups();
146        let mut options = setup_options(2500);
147        let mut result = select_coin_fifo(&inputs, &options);
148        assert!(result.is_ok());
149        let mut selection_output = result.unwrap();
150        assert!(!selection_output.selected_inputs.is_empty());
151
152        inputs = setup_output_groups_withsequence();
153        options = setup_options(500);
154        result = select_coin_fifo(&inputs, &options);
155        assert!(result.is_ok());
156        selection_output = result.unwrap();
157        assert!(!selection_output.selected_inputs.is_empty());
158    }
159
160    fn test_insufficient_funds() {
161        let inputs = setup_basic_output_groups();
162        let options = setup_options(7000); // Set a target value higher than the sum of all inputs
163        let result = select_coin_fifo(&inputs, &options);
164        assert!(matches!(result, Err(SelectionError::InsufficientFunds)));
165    }
166
167    #[test]
168    fn test_fifo() {
169        test_successful_selection();
170        test_insufficient_funds();
171    }
172}
rust_coinselect/algorithms/fifo.rs

rust_coinselect/algorithms/
fifo.rs
