rust_coinselect/algorithms/
fifo.rs

1use crate::{
2    types::{CoinSelectionOpt, OutputGroup, SelectionError, SelectionOutput, WasteMetric},
3    utils::{calculate_fee, calculate_fee_and_waste, insufficient_funds, prepare_output_groups},
4};
5
6/// Performs coin selection using the First-In-First-Out (FIFO) algorithm.
7///
8/// Oldest UTXOs (by `creation_sequence`) are spent first; inputs without a sequence are appended
9/// last in their original order.
10pub fn select_coin_fifo(
11    inputs: &[OutputGroup],
12    options: &CoinSelectionOpt,
13) -> Result<SelectionOutput, SelectionError> {
14    let insufficient_funds_error = insufficient_funds(inputs, options);
15    let inputs = prepare_output_groups(inputs, options)?;
16    let mut accumulated_value: u64 = 0;
17    let mut accumulated_weight: u64 = 0;
18    let mut selected_inputs: Vec<usize> = Vec::new();
19    let base_fee = calculate_fee(
20        options.base_weight + options.change_weight,
21        options.target_feerate,
22    )
23    .max(options.min_absolute_fee);
24    // Effective values already net out per-input fees, so the target only needs the base fee.
25    let target = options.target_value + base_fee;
26
27    // Sorting the inputs vector based on creation_sequence
28    let mut sorted_inputs: Vec<_> = inputs
29        .iter()
30        .filter(|og| og.creation_sequence.is_some())
31        .collect();
32
33    sorted_inputs.sort_by(|a, b| a.creation_sequence.cmp(&b.creation_sequence));
34
35    let inputs_without_sequence: Vec<_> = inputs
36        .iter()
37        .filter(|og| og.creation_sequence.is_none())
38        .collect();
39
40    sorted_inputs.extend(inputs_without_sequence);
41
42    for input in sorted_inputs {
43        accumulated_value += input.value;
44        accumulated_weight += input.weight;
45        selected_inputs.push(input.index);
46
47        if accumulated_value >= target {
48            break;
49        }
50    }
51
52    if accumulated_value < target {
53        Err(insufficient_funds_error)
54    } else {
55        let (fee, waste) = calculate_fee_and_waste(options, accumulated_value, accumulated_weight)?;
56        Ok(SelectionOutput {
57            selected_inputs,
58            waste: WasteMetric(waste),
59            fee,
60        })
61    }
62}
63
64#[cfg(test)]
65mod test {
66
67    use crate::{
68        algorithms::fifo::select_coin_fifo,
69        types::{
70            basic_output_group, CoinSelectionOpt, ExcessStrategy, OutputGroup, SelectionError,
71        },
72    };
73
74    fn setup_basic_output_groups() -> Vec<OutputGroup> {
75        vec![
76            basic_output_group(1000, 100),
77            basic_output_group(2000, 200),
78            basic_output_group(3000, 300),
79        ]
80    }
81    fn setup_output_groups_withsequence() -> Vec<OutputGroup> {
82        let mut inputs = vec![
83            basic_output_group(1000, 100),
84            basic_output_group(2000, 200),
85            basic_output_group(3000, 300),
86            basic_output_group(1500, 150),
87        ];
88        inputs[0].creation_sequence = Some(1);
89        inputs[1].creation_sequence = Some(5000);
90        inputs[2].creation_sequence = Some(1001);
91        inputs
92    }
93
94    fn setup_options(target_value: u64) -> CoinSelectionOpt {
95        CoinSelectionOpt {
96            target_value,
97            target_feerate: 0.4, // Simplified feerate
98            long_term_feerate: Some(0.4),
99            min_absolute_fee: 0,
100            base_weight: 10,
101            change_weight: 50,
102            change_cost: 10,
103            min_change_value: 500,
104            excess_strategy: ExcessStrategy::ToChange,
105        }
106    }
107
108    fn test_successful_selection() {
109        let mut inputs = setup_basic_output_groups();
110        let mut options = setup_options(2500);
111        let mut result = select_coin_fifo(&inputs, &options);
112        assert!(result.is_ok());
113        let mut selection_output = result.unwrap();
114        assert!(!selection_output.selected_inputs.is_empty());
115
116        inputs = setup_output_groups_withsequence();
117        options = setup_options(500);
118        result = select_coin_fifo(&inputs, &options);
119        assert!(result.is_ok());
120        selection_output = result.unwrap();
121        assert!(!selection_output.selected_inputs.is_empty());
122    }
123
124    fn test_insufficient_funds() {
125        let inputs = setup_basic_output_groups();
126        let options = setup_options(7000); // Set a target value higher than the sum of all inputs
127        let result = select_coin_fifo(&inputs, &options);
128        assert!(matches!(
129            result,
130            Err(SelectionError::InsufficientFunds { .. })
131        ));
132    }
133
134    #[test]
135    fn test_fifo() {
136        test_successful_selection();
137        test_insufficient_funds();
138    }
139}
rust_coinselect/algorithms/fifo.rs

rust_coinselect/algorithms/
fifo.rs
