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

rust_coinselect/algorithms/
fifo.rs
