/*
Select a coin which is exactly twice the value of the payment
This makes the two outputs identical, making it impossible to guess which is the payment and which is
the change. Variations: select two or more coins that total exactly twice the payment amount; select
one coin which is approximately twice the payment amount (this will result in two outputs which are close
in value, and as shown above you cannot reliably guess which is the payment)
*/

// Look for a coin that is within 10% of twice the right size
bool SelectCoins1Conf(int64 nTargetValue, int nConfMine, int nConfTheirs, set<CWalletTx*>& setCoinsRet)
{
setCoinsRet.clear();

CRITICAL_BLOCK(cs_mapWallet)
{
vector<CWalletTx*> vCoins;
vCoins.reserve(mapWallet.size());

for (map<uint256, CWalletTx>::iterator it = mapWallet.begin(); it != mapWallet.end(); ++it)
vCoins.push_back(&(*it).second);
random_shuffle(vCoins.begin(), vCoins.end(), GetRandInt);

foreach(CWalletTx * pcoin, vCoins)
{
if (!pcoin->IsFinal() || pcoin->fSpent || !pcoin->IsConfirmed())
continue;

int nDepth = pcoin->GetDepthInMainChain();

if (nDepth < (pcoin->IsFromMe() ? nConfMine : nConfTheirs))
continue;

int64 n = pcoin->GetCredit();

if (n <= 0)
continue;

if (n == nTargetValue)
{
setCoinsRet.insert(pcoin);
return(true);
}else if ((n == (2 * nTargetValue)) ||
 (n >= (1.9 * nTargetValue)) ||
 (n <= (2.1 * nTargetValue)))
{
setCoinsRet.insert(pcoin);
return(true);
}
}
}

return(false);
}

/*
Select two coins such that either (a) the value of each input is less than the payment amount and
sums to greater than (but NOT equal to) the payment amount, or (b) the value of each input is greater
than the payment amount

Example:
A=4, B=2, O1=5, O2=1

A tracker looking at this transaction cannot tell if it satisfies condition (a) or condition
(b), therefore they cannot determine which is the payment and which is the change.
For condition (a), O1 is the payment, and for condition (b) O2 is the payment.
*/
bool SelectCoins2Conf(int64 nTargetValue, int nConfMine, int nConfTheirs, set<CWalletTx*>& setCoinsRet)
{
setCoinsRet.clear();

CRITICAL_BLOCK(cs_mapWallet)
{
vector<CWalletTx*> vCoins;
vCoins.reserve(mapWallet.size());

size_t pCount = 0;

for (map<uint256, CWalletTx>::iterator it = mapWallet.begin(); it != mapWallet.end(); ++it)
{
vCoins.push_back(&(*it).second);
++pCount;
}
random_shuffle(vCoins.begin(), vCoins.end(), GetRandInt);

CWalletTx* pfoundlargercoin1 = NULL;

CWalletTx* smaller_coins[pCount];
size_t smaller_count = 0;
int64 smaller_value = 0;

foreach(CWalletTx * pcoin, vCoins)
{
if (!pcoin->IsFinal() || pcoin->fSpent || !pcoin->IsConfirmed())
continue;

int nDepth = pcoin->GetDepthInMainChain();

if (nDepth < (pcoin->IsFromMe() ? nConfMine : nConfTheirs))
continue;

int64 n = pcoin->GetCredit();

if (n <= 0)
continue;

if (n > nTargetValue)
{
if (pfoundlargercoin1 == NULL)
{
pfoundlargercoin1 = pcoin;
continue;
} else
{
setCoinsRet.insert(pfoundlargercoin1);
setCoinsRet.insert(pcoin);
return(true);
}
} else if (n < nTargetValue)
{
smaller_coins[smaller_count++] = pcoin;
smaller_value += n;
}
}
if (smaller_value < nTargetValue ||
smaller_value == nTargetValue && smaller_count < 2)
return(false);
for (int iLoop1 = 0; iLoop1 < smaller_count; ++iLoop1)
{
for (int iLoop2 = iLoop1; iLoop2 < smaller_count; ++iLoop2)
{
if (smaller_coins[iLoop1]->GetCredit() + smaller_coins[iLoop2]->GetCredit() >= nTargetValue)
{
setCoinsRet.insert(smaller_coins[iLoop1]);
setCoinsRet.insert(smaller_coins[iLoop2]);
return(true);
}
}
}
}

return(false);
}

/*
Select two coins: one whose value exactly matches the payment, and another coin at random.
Example:
A=5, B=2; O1=5, O2=2

It's rather obvious what we're doing here, but since we (and the tracker) know the payment and
change are randomized, a tracker cannot know which is the payment and which is the change.
*/
bool SelectCoins3Conf(int64 nTargetValue, int nConfMine, int nConfTheirs, set<CWalletTx*>& setCoinsRet)
{
setCoinsRet.clear();

CRITICAL_BLOCK(cs_mapWallet)
{
vector<CWalletTx*> vCoins;
vCoins.reserve(mapWallet.size());

size_t pCount = 0;

for (map<uint256, CWalletTx>::iterator it = mapWallet.begin(); it != mapWallet.end(); ++it)
{
vCoins.push_back(&(*it).second);
++pCount;
}
random_shuffle(vCoins.begin(), vCoins.end(), GetRandInt);

CWalletTx* smaller_coins[pCount];
size_t smaller_count = 0;
int64 smaller_value = 0;

CWalletTx* pfrandomcoin = NULL;
CWalletTx* pexactcoin = NULL;

foreach(CWalletTx * pcoin, vCoins)
{
if (!pcoin->IsFinal() || pcoin->fSpent || !pcoin->IsConfirmed())
continue;

int nDepth = pcoin->GetDepthInMainChain();

if (nDepth < (pcoin->IsFromMe() ? nConfMine : nConfTheirs))
continue;

int64 n = pcoin->GetCredit();

if (n <= 0)
continue;

if (n == nTargetValue)
{
pexactcoin = pcoin;

}
else
pfrandomcoin = pcoin;

if (pexactcoin != NULL && pfrandomcoin != NULL)
{
setCoinsRet.insert(pexactcoin);
setCoinsRet.insert(pfrandomcoin);
return(true);
}
}
}

return(false);
}
/*
A special variation on (1) (I call this one the "In yo face!" selection): Select multiple coins adding
to more than the payment amount, and if possible ensure at least one coin is redundant.
Example:
A=2, B=3, C=1, D=1, E=2, O1=4, O2=5

It's clear from examining this transaction that several combinations of the coins could satisfy either
O1 or O2, so the tracker cannot tell which is the payment and which is the change. Note that this algorithm,
unlike the others, is guaranteed to find a set of coins that can be used.
*/
bool SelectCoins4Conf(int64 nTargetValue, int nConfMine, int nConfTheirs, set<CWalletTx*>& setCoinsRet)
{
setCoinsRet.clear();

CRITICAL_BLOCK(cs_mapWallet)
{
vector<CWalletTx*> vCoins;
vCoins.reserve(mapWallet.size());

size_t pCount = 0;

for (map<uint256, CWalletTx>::iterator it = mapWallet.begin(); it != mapWallet.end(); ++it)
{
vCoins.push_back(&(*it).second);
++pCount;
}
random_shuffle(vCoins.begin(), vCoins.end(), GetRandInt);

CWalletTx* smaller_coins[pCount];

CWalletTx* pfoundlargercoin1 = NULL;
size_t smaller_count = 0;
int64 smaller_value = 0;

foreach(CWalletTx * pcoin, vCoins)
{
if (!pcoin->IsFinal() || pcoin->fSpent || !pcoin->IsConfirmed())
continue;

int nDepth = pcoin->GetDepthInMainChain();

if (nDepth < (pcoin->IsFromMe() ? nConfMine : nConfTheirs))
continue;

int64 n = pcoin->GetCredit();

if (n <= 0)
continue;

if (n > nTargetValue)
{
if (pfoundlargercoin1 == NULL)
{
pfoundlargercoin1 = pcoin;
continue;
} else
{
setCoinsRet.insert(pfoundlargercoin1);
setCoinsRet.insert(pcoin);
return(true);
}
} else if (n < nTargetValue)
{
smaller_coins[smaller_count++] = pcoin;
smaller_value += n;
}
}
if (smaller_value < nTargetValue ||
smaller_value == nTargetValue && smaller_count < 2)
return(false);
for (int iLoop1 = 0; iLoop1 < smaller_count; ++iLoop1)
{
for (int iLoop2 = iLoop1; iLoop2 < smaller_count; ++iLoop2)
{
if (smaller_coins[iLoop1]->GetCredit() + smaller_coins[iLoop2]->GetCredit() >= nTargetValue)
{
setCoinsRet.insert(smaller_coins[iLoop1]);
setCoinsRet.insert(smaller_coins[iLoop2]);
return(true);
}
}
}
}

return(false);
}

bool SelectCoins(int64 nTargetValue, set<CWalletTx*>& setCoinsRet)
{
return (SelectCoins2Conf(nTargetValue, 1, 6, setCoinsRet) ||
SelectCoins1Conf(nTargetValue, 1, 6, setCoinsRet) ||
SelectCoins3Conf(nTargetValue, 1, 6, setCoinsRet) ||
SelectCoinsMinConf(nTargetValue, 1, 6, setCoinsRet) ||
SelectCoins2Conf(nTargetValue, 1, 1, setCoinsRet) ||
SelectCoins1Conf(nTargetValue, 1, 1, setCoinsRet) ||
SelectCoins3Conf(nTargetValue, 1, 1, setCoinsRet) ||
SelectCoinsMinConf(nTargetValue, 1, 1, setCoinsRet) ||
SelectCoins2Conf(nTargetValue, 0, 1, setCoinsRet) ||
SelectCoins1Conf(nTargetValue, 0, 1, setCoinsRet) ||
SelectCoins3Conf(nTargetValue, 0, 1, setCoinsRet) ||
SelectCoinsMinConf(nTargetValue, 0, 1, setCoinsRet));
}