///GetSimplerNewicks creates simpler, derived Newicks from a binary Newick.
///From http://www.richelbilderbeek.nl/CppGetSimplerNewicks.htm
const std::vector<std::vector<int> > GetSimplerNewicks(const std::vector<int>& n)
{
assert(IsNewick(n));
assert(IsBinaryNewick(n));
//If newick is simple (by counting the number of opening brackets),
//there are no simpler Newicks
if (std::count( n.begin(),n.end(),
static_cast<int>(BinaryNewickVector::bracket_open))==1)
{
//Simple newicks do not need to be simplified
return std::vector<std::vector<int> >();
}
//newick is complex
//Generate other Newicks and their coefficients
std::vector<std::vector<int> > newicks;
const int sz = n.size();
for (int i=0; i!=sz; ++i)
{
const int x = n[i];
if (x < 0) //x is not a digit
{
continue;
}
if (x == 1)
{
//If x is not next to a digit, there is no simplification
if (n[i-1]<0 && n[i+1]<1) continue;
//If next to the x in a digit, merge these and remove their brackets
if (n[i-1]==BinaryNewickVector::bracket_open)
{
assert(n[i+1] > 0);
const int new_value = n[i+1] + 1;
std::vector<int> next(n.begin(),n.begin() + i - 1);
next.push_back(new_value);
assert(n[i+2] < 0);
std::copy(n.begin() + i + 3,n.end(),std::back_inserter(next));
newicks.push_back(next);
}
else
{
assert(n[i-1] > 0);
const int new_value = n[i-1] + 1;
std::vector<int> next(n.begin(),n.begin()+i-3);
next.push_back(new_value);
assert(n[i+1] < 0);
std::copy(n.begin() + i + 2,n.end(),std::back_inserter(next));
newicks.push_back(next);
}
}
else
{
std::vector<int> next = n;
--next[i];
newicks.push_back(next);
}
}
return newicks;
}
|
