rust_coinselect/algorithms/
lowestlarger.rs

1use crate::{
2    types::{CoinSelectionOpt, OutputGroup, SelectionError, SelectionOutput, WasteMetric},
3    utils::{calculate_fee, calculate_waste, effective_value},
4};
5
6/// Performs coin selection using the Lowest Larger algorithm.
7///
8/// Returns `NoSolutionFound` if no solution exists.
9pub fn select_coin_lowestlarger(
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    let mut sorted_inputs: Vec<_> = inputs.iter().enumerate().collect();
22    sorted_inputs.sort_by_key(|(_, input)| effective_value(input, options.target_feerate));
23
24    let index = sorted_inputs.partition_point(|(_, input)| {
25        input.value
26            <= (target + calculate_fee(input.weight, options.target_feerate).unwrap_or_default())
27    });
28
29    for (idx, input) in sorted_inputs.iter().take(index).rev() {
30        accumulated_value += input.value;
31        accumulated_weight += input.weight;
32        estimated_fees = calculate_fee(accumulated_weight, options.target_feerate)?;
33        selected_inputs.push(*idx);
34
35        if accumulated_value >= (target + estimated_fees) {
36            break;
37        }
38    }
39
40    if accumulated_value < (target + estimated_fees) {
41        for (idx, input) in sorted_inputs.iter().skip(index) {
42            accumulated_value += input.value;
43            accumulated_weight += input.weight;
44            estimated_fees = calculate_fee(accumulated_weight, options.target_feerate)?;
45            selected_inputs.push(*idx);
46
47            if accumulated_value >= (target + estimated_fees.max(options.min_absolute_fee)) {
48                break;
49            }
50        }
51    }
52
53    if accumulated_value < (target + estimated_fees) {
54        Err(SelectionError::InsufficientFunds)
55    } else {
56        let waste: f32 = 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::lowestlarger::select_coin_lowestlarger,
74        types::{CoinSelectionOpt, ExcessStrategy, OutputGroup, SelectionError},
75    };
76
77    fn setup_lowestlarger_output_groups() -> Vec<OutputGroup> {
78        vec![
79            OutputGroup {
80                value: 100,
81                weight: 100,
82                input_count: 1,
83                creation_sequence: None,
84            },
85            OutputGroup {
86                value: 1500,
87                weight: 200,
88                input_count: 1,
89                creation_sequence: None,
90            },
91            OutputGroup {
92                value: 3400,
93                weight: 300,
94                input_count: 1,
95                creation_sequence: None,
96            },
97            OutputGroup {
98                value: 2200,
99                weight: 150,
100                input_count: 1,
101                creation_sequence: None,
102            },
103            OutputGroup {
104                value: 1190,
105                weight: 200,
106                input_count: 1,
107                creation_sequence: None,
108            },
109            OutputGroup {
110                value: 3300,
111                weight: 100,
112                input_count: 1,
113                creation_sequence: None,
114            },
115            OutputGroup {
116                value: 1000,
117                weight: 190,
118                input_count: 1,
119                creation_sequence: None,
120            },
121            OutputGroup {
122                value: 2000,
123                weight: 210,
124                input_count: 1,
125                creation_sequence: None,
126            },
127            OutputGroup {
128                value: 3000,
129                weight: 300,
130                input_count: 1,
131                creation_sequence: None,
132            },
133            OutputGroup {
134                value: 2250,
135                weight: 250,
136                input_count: 1,
137                creation_sequence: None,
138            },
139            OutputGroup {
140                value: 190,
141                weight: 220,
142                input_count: 1,
143                creation_sequence: None,
144            },
145            OutputGroup {
146                value: 1750,
147                weight: 170,
148                input_count: 1,
149                creation_sequence: None,
150            },
151        ]
152    }
153
154    fn setup_options(target_value: u64) -> CoinSelectionOpt {
155        CoinSelectionOpt {
156            target_value,
157            target_feerate: 0.4, // Simplified feerate
158            long_term_feerate: Some(0.4),
159            min_absolute_fee: 0,
160            base_weight: 10,
161            change_weight: 50,
162            change_cost: 10,
163            avg_input_weight: 20,
164            avg_output_weight: 10,
165            min_change_value: 500,
166            excess_strategy: ExcessStrategy::ToChange,
167        }
168    }
169
170    #[test]
171    fn test_lowestlarger_successful() {
172        let inputs = setup_lowestlarger_output_groups();
173        let options = setup_options(20000);
174        let result = select_coin_lowestlarger(&inputs, &options);
175        assert!(result.is_ok());
176        let selection_output = result.unwrap();
177        assert!(!selection_output.selected_inputs.is_empty());
178    }
179
180    #[test]
181    fn test_lowestlarger_insufficient() {
182        let inputs = setup_lowestlarger_output_groups();
183        let options = setup_options(40000);
184        let result = select_coin_lowestlarger(&inputs, &options);
185        assert!(matches!(result, Err(SelectionError::InsufficientFunds)));
186    }
187}
rust_coinselect/algorithms/lowestlarger.rs

rust_coinselect/algorithms/
lowestlarger.rs
