`OldestFirstCoinSelection` selects `Utxo::Foreign`s first instead of last

[MaxFangX]

The OldestFirstCoinSelection algorithm actually selects foreign UTXOs first, contra the comment, as Option's Ord impl defines None as "less than" Some. This bug is on the master branch: https://github.com/bitcoindevkit/bdk_wallet/blob/master/wallet/src/wallet/coin_selection.rs

/// OldestFirstCoinSelection always picks the utxo with the smallest blockheight to add to the
/// selected coins next
///
/// This coin selection algorithm sorts the available UTXOs by blockheight and then picks them
/// starting from the oldest ones until the required amount is reached.
#[derive(Debug, Default, Clone, Copy)]
pub struct OldestFirstCoinSelection;

impl CoinSelectionAlgorithm for OldestFirstCoinSelection {
    fn coin_select<R: RngCore>(
        &self,
        required_utxos: Vec<WeightedUtxo>,
        mut optional_utxos: Vec<WeightedUtxo>,
        fee_rate: FeeRate,
        target_amount: Amount,
        drain_script: &Script,
        _: &mut R,
    ) -> Result<CoinSelectionResult, InsufficientFunds> {
        // We put the "required UTXOs" first and make sure the optional UTXOs are sorted from
        // oldest to newest according to blocktime
        // For utxo that doesn't exist in DB, they will have lowest priority to be selected
        let utxos = {
            optional_utxos.sort_unstable_by_key(|wu| match &wu.utxo {
                Utxo::Local(local) => Some(local.chain_position),
                Utxo::Foreign { .. } => None,
            });

            required_utxos
                .into_iter()
                .map(|utxo| (true, utxo))
                .chain(optional_utxos.into_iter().map(|utxo| (false, utxo)))
        };

        select_sorted_utxos(utxos, fee_rate, target_amount, drain_script)
    }
}

...

fn select_sorted_utxos(
    utxos: impl Iterator<Item = (bool, WeightedUtxo)>,
    fee_rate: FeeRate,
    target_amount: Amount,
    drain_script: &Script,
) -> Result<CoinSelectionResult, InsufficientFunds> {
    let mut selected_amount = Amount::ZERO;
    let mut fee_amount = Amount::ZERO;
    let selected = utxos
        .scan(
            (&mut selected_amount, &mut fee_amount),
            |(selected_amount, fee_amount), (must_use, weighted_utxo)| {
                if must_use || **selected_amount < target_amount + **fee_amount {
                    **fee_amount += fee_rate
                        * TxIn::default()
                            .segwit_weight()
                            .checked_add(weighted_utxo.satisfaction_weight)
                            .expect("`Weight` addition should not cause an integer overflow");
                    **selected_amount += weighted_utxo.utxo.txout().value;
                    Some(weighted_utxo.utxo)
                } else {
                    None
                }
            },
        )
        .collect::<Vec<_>>();

    let amount_needed_with_fees = target_amount + fee_amount;
    if selected_amount < amount_needed_with_fees {
        return Err(InsufficientFunds {
            needed: amount_needed_with_fees,
            available: selected_amount,
        });
    }

    let remaining_amount = selected_amount - amount_needed_with_fees;

    let excess = decide_change(remaining_amount, fee_rate, drain_script);

    Ok(CoinSelectionResult {
        selected,
        fee_amount,
        excess,
    })
}