seqset)
{
if (node == null)
{
return tmp;
}
SequenceNode left = (SequenceNode) node.left();
SequenceNode right = (SequenceNode) node.right();
if ((left == null) && (right == null))
{
if (!node.isPlaceholder() && (node.element() != null))
{
if (node.element() instanceof SequenceI)
{
if (!tmp.contains(node.element())) // && (seqset==null ||
// seqset.size()==0 ||
// seqset.contains(tmp)))
{
tmp.add((SequenceI) node.element());
}
}
}
return tmp;
}
else
{
_sortByTree(left, tmp, seqset);
_sortByTree(right, tmp, seqset);
}
return tmp;
}
// Ordering Objects
// Alignment.sortBy(OrderObj) - sequence of sequence pointer refs in
// appropriate order
//
/**
* recover the order of sequences given by the safe numbering scheme introducd
* SeqsetUtils.uniquify.
*/
public static void recoverOrder(SequenceI[] alignment)
{
float[] ids = new float[alignment.length];
for (int i = 0; i < alignment.length; i++)
{
ids[i] = (Float.valueOf(alignment[i].getName().substring(8)))
.floatValue();
}
jalview.util.QuickSort.sort(ids, alignment);
}
/**
* Sort sequence in order of increasing score attribute for annotation with a
* particular scoreLabel. Or reverse if same label was used previously
*
* @param scoreLabel
* exact label for sequence associated AlignmentAnnotation scores to
* use for sorting.
* @param alignment
* sequences to be sorted
*/
public static void sortByAnnotationScore(String scoreLabel,
AlignmentI alignment)
{
SequenceI[] seqs = alignment.getSequencesArray();
boolean[] hasScore = new boolean[seqs.length]; // per sequence score
// presence
int hasScores = 0; // number of scores present on set
double[] scores = new double[seqs.length];
double min = 0, max = 0;
for (int i = 0; i < seqs.length; i++)
{
AlignmentAnnotation[] scoreAnn = seqs[i].getAnnotation(scoreLabel);
if (scoreAnn != null)
{
hasScores++;
hasScore[i] = true;
scores[i] = scoreAnn[0].getScore(); // take the first instance of this
// score.
if (hasScores == 1)
{
max = min = scores[i];
}
else
{
if (max < scores[i])
{
max = scores[i];
}
if (min > scores[i])
{
min = scores[i];
}
}
}
else
{
hasScore[i] = false;
}
}
if (hasScores == 0)
{
return; // do nothing - no scores present to sort by.
}
if (hasScores < seqs.length)
{
for (int i = 0; i < seqs.length; i++)
{
if (!hasScore[i])
{
scores[i] = (max + i + 1.0);
}
}
}
jalview.util.QuickSort.sort(scores, seqs);
AlignmentSorter as = getInstance();
if (as.lastSortByAnnotation != scoreLabel)
{
as.lastSortByAnnotation = scoreLabel;
setOrder(alignment, seqs);
}
else
{
setReverseOrder(alignment, seqs);
}
}
/**
* Sort sequences by feature score or density, optionally restricted by
* feature types, feature groups, or alignment start/end positions.
*
* If the sort is repeated for the same combination of types and groups, sort
* order is reversed.
*
* @param featureTypes
* a list of feature types to include (or null for all)
* @param groups
* a list of feature groups to include (or null for all)
* @param startCol
* start column position to include (base zero)
* @param endCol
* end column position to include (base zero)
* @param alignment
* the alignment to be sorted
* @param method
* either "average_score" or "density" ("text" not yet implemented)
*/
public static void sortByFeature(List featureTypes,
List groups, final int startCol, final int endCol,
AlignmentI alignment, String method)
{
if (method != FEATURE_SCORE && method != FEATURE_LABEL
&& method != FEATURE_DENSITY)
{
String msg = String.format(
"Implementation Error - sortByFeature method must be either '%s' or '%s'",
FEATURE_SCORE, FEATURE_DENSITY);
System.err.println(msg);
return;
}
flipFeatureSortIfUnchanged(method, featureTypes, groups, startCol,
endCol);
SequenceI[] seqs = alignment.getSequencesArray();
boolean[] hasScore = new boolean[seqs.length]; // per sequence score
// presence
int hasScores = 0; // number of scores present on set
double[] scores = new double[seqs.length];
int[] seqScores = new int[seqs.length];
Object[][] feats = new Object[seqs.length][];
double min = 0d;
double max = 0d;
for (int i = 0; i < seqs.length; i++)
{
/*
* get sequence residues overlapping column region
* and features for residue positions and specified types
*/
String[] types = featureTypes == null ? null
: featureTypes.toArray(new String[featureTypes.size()]);
List sfs = seqs[i].findFeatures(startCol + 1,
endCol + 1, types);
seqScores[i] = 0;
scores[i] = 0.0;
Iterator it = sfs.listIterator();
while (it.hasNext())
{
SequenceFeature sf = it.next();
/*
* accept all features with null or empty group, otherwise
* check group is one of the currently visible groups
*/
String featureGroup = sf.getFeatureGroup();
if (groups != null && featureGroup != null
&& !"".equals(featureGroup)
&& !groups.contains(featureGroup))
{
it.remove();
}
else
{
float score = sf.getScore();
if (FEATURE_SCORE.equals(method) && !Float.isNaN(score))
{
if (seqScores[i] == 0)
{
hasScores++;
}
seqScores[i]++;
hasScore[i] = true;
scores[i] += score;
// take the first instance of this score // ??
}
}
}
feats[i] = sfs.toArray(new SequenceFeature[sfs.size()]);
if (!sfs.isEmpty())
{
if (method == FEATURE_LABEL)
{
// order the labels by alphabet (not yet implemented)
String[] labs = new String[sfs.size()];
for (int l = 0; l < sfs.size(); l++)
{
SequenceFeature sf = sfs.get(l);
String description = sf.getDescription();
labs[l] = (description != null ? description : sf.getType());
}
QuickSort.sort(labs, feats[i]);
}
}
if (hasScore[i])
{
// compute average score
scores[i] /= seqScores[i];
// update the score bounds.
if (hasScores == 1)
{
min = scores[i];
max = min;
}
else
{
max = Math.max(max, scores[i]);
min = Math.min(min, scores[i]);
}
}
}
boolean doSort = false;
if (FEATURE_SCORE.equals(method))
{
if (hasScores == 0)
{
return; // do nothing - no scores present to sort by.
}
// pad score matrix
if (hasScores < seqs.length)
{
for (int i = 0; i < seqs.length; i++)
{
if (!hasScore[i])
{
scores[i] = (max + 1 + i);
}
else
{
// int nf = (feats[i] == null) ? 0
// : ((SequenceFeature[]) feats[i]).length;
// // System.err.println("Sorting on Score: seq " +
// seqs[i].getName()
// + " Feats: " + nf + " Score : " + scores[i]);
}
}
}
doSort = true;
}
else if (FEATURE_DENSITY.equals(method))
{
for (int i = 0; i < seqs.length; i++)
{
int featureCount = feats[i] == null ? 0
: ((SequenceFeature[]) feats[i]).length;
scores[i] = featureCount;
// System.err.println("Sorting on Density: seq "+seqs[i].getName()+
// " Feats: "+featureCount+" Score : "+scores[i]);
}
doSort = true;
}
if (doSort)
{
QuickSort.sortByDouble(scores, seqs,
getInstance().sortByFeatureAscending);
}
setOrder(alignment, seqs);
}
/**
* Builds a string hash of criteria for sorting, and if unchanged from last
* time, reverse the sort order
*
* @param method
* @param featureTypes
* @param groups
* @param startCol
* @param endCol
*/
protected static void flipFeatureSortIfUnchanged(String method,
List featureTypes, List groups,
final int startCol, final int endCol)
{
StringBuilder sb = new StringBuilder(64);
sb.append(startCol).append(method).append(endCol);
if (featureTypes != null)
{
Collections.sort(featureTypes);
sb.append(featureTypes.toString());
}
if (groups != null)
{
Collections.sort(groups);
sb.append(groups.toString());
}
String scoreCriteria = sb.toString();
/*
* if resorting on the same criteria, toggle sort order
*/
AlignmentSorter as = getInstance();
if (as.sortByFeatureCriteria == null
|| !scoreCriteria.equals(as.sortByFeatureCriteria))
{
as.sortByFeatureAscending = true;
}
else
{
as.sortByFeatureAscending = !as.sortByFeatureAscending;
}
as.sortByFeatureCriteria = scoreCriteria;
}
/**
* Set the alignment's sequences list to contain the sequences from a
* temporary list, first adding all the elements from the tmp list, then adding all sequences in the alignment that
* are not in the list. Option to do the final sort either in order or in reverse order.
*
* @param align The alignment being sorted
* @param tmp
* the temporary sequence list
* @param ascending
* false for reversed order; only sequences already in
* the alignment will be used (which is actually already guaranteed
* by vectorSubsetToArray)
*/
private static void set(AlignmentI align, List tmp,
boolean ascending)
{
set(align, vectorSubsetToArray(align.getSequences(), tmp), ascending);
}
/**
* Set the alignment's sequences list to contain these sequences, either in
* this order or its reverse.
*
* @param align
* @param seqs
* the new sequence array
* @param ascending
* false for reversed order; if ascending, only sequences already in
* the alignment will be used; if descending, then a direct 1:1
* replacement is made
*/
private static void set(AlignmentI align, SequenceI[] seqs,
boolean ascending)
{
if (ascending)
{
setOrder(align, seqs);
}
else
{
setReverseOrder(align, seqs);
}
}
/**
* Replace the alignment's sequences with values in an array, clearing the
* alignment's sequence list and filtering for sequences that are actually in
* the alignment already.
*
* @param align
* the Alignment
* @param seqs
* the array of replacement values, of any length
*/
public static void setOrder(AlignmentI align, SequenceI[] seqs)
{
// NOTE: DO NOT USE align.setSequenceAt() here - it will NOT work
List seqList = align.getSequences();
synchronized (seqList)
{
List tmp = new ArrayList<>();
for (int i = 0; i < seqs.length; i++)
{
if (seqList.contains(seqs[i]))
{
tmp.add(seqs[i]);
}
}
seqList.clear();
// User may have hidden seqs, then clicked undo or redo
for (int i = 0; i < tmp.size(); i++)
{
seqList.add(tmp.get(i));
}
}
}
/**
* Replace the alignment's sequences or a subset of those sequences with
* values in an array in reverse order. All sequences are replaced; no check
* is made that these sequences are in the alignment already.
*
* @param align
* the Alignment
* @param seqs
* the array of replacement values, length must be less than or equal
* to Alignment.sequences.size()
*/
private static void setReverseOrder(AlignmentI align, SequenceI[] seqs)
{
int nSeq = seqs.length;
int len = (nSeq + (nSeq % 2)) / 2;
// int len = 0;
//
// if ((nSeq % 2) == 0)
// {
// len = nSeq / 2;
// }
// else
// {
// len = (nSeq + 1) / 2;
// }
// NOTE: DO NOT USE align.setSequenceAt() here - it will NOT work
List seqList = align.getSequences();
synchronized (seqList)
{
for (int i = 0; i < len; i++)
{
// SequenceI tmp = seqs[i];
seqList.set(i, seqs[nSeq - i - 1]);
seqList.set(nSeq - i - 1, seqs[i]);
}
}
}
/**
* Create and array of reordered sequences in order first from tmp that are
* present in seqList already, then, after that, any remaining sequences in
* seqList not in tmp. Any sequences in tmp that are not in seqList already
* are discarded.
*
* @param seqList
* thread safe collection of sequences originally in the alignment
* @param tmp
* thread safe collection of sequences or subsequences possibly in
* seqList
*
* @return intersect(tmp,seqList)+intersect(complement(tmp),seqList)
*/
private static SequenceI[] vectorSubsetToArray(List seqList,
List tmp)
{
ArrayList seqs = new ArrayList<>();
int n = seqList.size();
BitSet bs = new BitSet(n);
bs.set(0, n);
for (int i = 0, nt = tmp.size(); i < nt; i++)
{
SequenceI sq = tmp.get(i);
int idx = seqList.indexOf(sq);
if (idx >= 0 && bs.get(idx))
{
seqs.add(sq);
bs.clear(idx);
}
}
for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i + 1))
{
seqs.add(seqList.get(i));
}
return seqs.toArray(new SequenceI[seqs.size()]);
}
}