import * as BN from 'bn.js' ; import * as utils from '../utils' ; import type { CoinSelectAlgorithm , CoinSelectInput } from '../index' ; const MAX_TRIES = 1000000 ; function calculateEffectiveValues ( utxos , feeRate ) { return utxos . map ( utxo => { const value = utils . bignumberOrNaN ( utxo . value ) ; if ( ! value ) { return { utxo , effectiveValue : new BN ( 0 ) , } ; } const effectiveFee = utils . inputBytes ( utxo ) * feeRate ; const effectiveValue = value . sub ( new BN ( effectiveFee ) ) ; return { utxo , effectiveValue , } ; } ) ; } function search ( effectiveUtxos , target , costOfChange ) { if ( effectiveUtxos . length === 0 ) { return null ; } let tries = MAX_TRIES ; const selected = [ ] ; let selectedAccum = new BN ( 0 ) ; let done = false ; let backtrack = false ; let remaining = effectiveUtxos . reduce ( ( a , x ) => x . effectiveValue . add ( a ) , new BN ( 0 ) ) ; const costRange = target . add ( new BN ( costOfChange ) ) ; let depth = 0 ; while ( ! done ) { if ( tries <= 0 ) { return null ; } if ( selectedAccum . gt ( costRange ) ) { backtrack = true ; } else if ( selectedAccum . gte ( target ) ) { done = true ; } else if ( depth >= effectiveUtxos . length ) { backtrack = true ; } else if ( selectedAccum . add ( remaining ) . lt ( target ) ) { if ( depth === 0 ) { return null ; } backtrack = true ; } else { remaining = remaining . sub ( effectiveUtxos [ depth ] . effectiveValue ) ; selected [ depth ] = true ; selectedAccum = selectedAccum . add ( effectiveUtxos [ depth ] . effectiveValue ) ; depth ++ ; } if ( backtrack ) { backtrack = false ; depth -- ; while ( ! selected [ depth ] ) { remaining = remaining . add ( effectiveUtxos [ depth ] . effectiveValue ) ; depth -- ; if ( depth < 0 ) { return null ; } } selected [ depth ] = false ; selectedAccum = selectedAccum . sub ( effectiveUtxos [ depth ] . effectiveValue ) ; depth ++ ; } tries -- ; } return selected ; } export function bnb ( factor ) { return ( utxos , outputs , feeRate , options ) => { if ( typeof utils . uintOrNaN ( feeRate ) !== 'number' ) return { fee : 0 } ; if ( options . baseFee ) return { fee : 0 } ; if ( utxos . find ( u => u . required ) ) return { fee : 0 } ; const costPerChangeOutput = utils . outputBytes ( { script : { length : utils . OUTPUT_SCRIPT_LENGTH [ options . txType ] , } , } ) * feeRate ; const costPerInput = utils . inputBytes ( { type : options . txType , script : { length : utils . INPUT_SCRIPT_LENGTH [ options . txType ] , } , } ) * feeRate ; const costOfChange = Math . floor ( ( costPerInput + costPerChangeOutput ) * factor ) ; const txBytes = utils . transactionBytes ( [ ] , outputs ) ; const bytesAndFee = feeRate * txBytes ; const outSum = utils . sumOrNaN ( outputs ) ; if ( ! outSum ) return { fee : 0 } ; const outAccum = outSum . add ( new BN ( bytesAndFee ) ) ; const effectiveUtxos = calculateEffectiveValues ( utxos , feeRate ) . filter ( x => x . effectiveValue . gt ( utils . ZERO ) ) . sort ( ( a , b ) => { const subtract = b . effectiveValue . sub ( a . effectiveValue ) . toNumber ( ) ; if ( subtract !== 0 ) { return subtract ; } return a . utxo . i - b . utxo . i ; } ) ; const selected = search ( effectiveUtxos , outAccum , costOfChange ) ; if ( selected !== null ) { const inputs = [ ] ; for ( let i = 0 ; i < effectiveUtxos . length ; i ++ ) { if ( selected [ i ] ) { inputs . push ( effectiveUtxos [ i ] . utxo ) ; } } return utils . finalize ( inputs , outputs , feeRate , options ) ; } return { fee : 0 } ; } ; }