src/jalview/analysis/AnnotationSorter.java

   1 /*
   2  * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
   3  * Copyright (C) $$Year-Rel$$ The Jalview Authors
   4  *
   5  * This file is part of Jalview.
   6  *
   7  * Jalview is free software: you can redistribute it and/or
   8  * modify it under the terms of the GNU General Public License
   9  * as published by the Free Software Foundation, either version 3
  10  * of the License, or (at your option) any later version.
  11  *
  12  * Jalview is distributed in the hope that it will be useful, but
  13  * WITHOUT ANY WARRANTY; without even the implied warranty
  14  * of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE.  See the GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with Jalview.  If not, see <http://www.gnu.org/licenses/>.
  19  * The Jalview Authors are detailed in the 'AUTHORS' file.
  20  */
  21 package jalview.analysis;
  22
  23 import jalview.api.AlignViewportI;
  24 import jalview.datamodel.AlignmentAnnotation;
  25 import jalview.datamodel.AlignmentI;
  26 import jalview.datamodel.SequenceI;
  27
  28 import java.util.Arrays;
  29 import java.util.Comparator;
  30 import java.util.HashMap;
  31 import java.util.List;
  32 import java.util.Map;
  33
  34 /**
  35  * A helper class to sort all annotations associated with an alignment in
  36  * various ways.
  37  *
  38  * @author gmcarstairs
  39  *
  40  */
  41 public class AnnotationSorter
  42 {
  43   /**
  44    * A special comparator for use when reloading from project, that supports
  45    * reordering annotations to match their order in the project. It incorporates
  46    * special handling of autocalculated annotations, that are recreated on load:
  47    * <ul>
  48    * <li>these are matched based on autocalc flag and label ("Consensus") etc
  49    * rather than object identity</li>
  50    * <li>on successful match, visibility and height settings are applied from
  51    * those saved in the project</li>
  52    * </ul>
  53    */
  54   private final class ReloadComparator
  55           implements Comparator<AlignmentAnnotation>
  56   {
  57     private List<AlignmentAnnotation> order;
  58
  59     ReloadComparator(List<AlignmentAnnotation> theOrder)
  60     {
  61       order = theOrder;
  62     }
  63
  64     @Override
  65     public int compare(AlignmentAnnotation o1,
  66             AlignmentAnnotation o2)
  67     {
  68       int i1 = findPosition(o1);
  69       int i2 = findPosition(o2);
  70       return Integer.compare(i1, i2);
  71     }
  72
  73     /**
  74      * A helper method that returns the position of the annotation in the
  75      * {@code order} list, by object identity, or failing that, by matched
  76      * autocalc label ("Consensus" etc). Returns -1 if not found. This can
  77      * happen if, for example, Consensus was saved but since turned off in
  78      * Preferences.
  79      *
  80      * @param aa
  81      * @return
  82      */
  83     private int findPosition(AlignmentAnnotation aa)
  84     {
  85       int i = order.indexOf(aa);
  86       if (i == -1 && aa.autoCalculated && aa.label != null)
  87       {
  88         for (int j = 0; j < order.size(); j++)
  89         {
  90           AlignmentAnnotation ann = order.get(j);
  91           if (aa.label.equals(ann.label))
  92           {
  93             i = j;
  94             aa.visible = ann.visible;
  95             if (ann.graphHeight >= 0)
  96             {
  97               aa.graphHeight = ann.graphHeight;
  98             }
  99             break;
 100           }
 101         }
 102       }
 103       return i;
 104     }
 105   }
 106
 107   /**
 108    * enum for annotation sort options. The text description is used in the
 109    * Preferences drop-down options. The enum name is saved in the preferences
 110    * file.
 111    *
 112    * @author gmcarstairs
 113    *
 114    */
 115   public enum SequenceAnnotationOrder
 116   {
 117     // Text descriptions surface in the Preferences Sort by... options
 118     SEQUENCE_AND_LABEL("Sequence"), LABEL_AND_SEQUENCE("Label"),
 119     NONE("No sort"),
 120
 121     /**
 122      * custom is set if user drags to reorder annotations
 123      */
 124     CUSTOM("Customised");
 125
 126     private String description;
 127
 128     private SequenceAnnotationOrder(String s)
 129     {
 130       description = s;
 131     }
 132
 133     @Override
 134     public String toString()
 135     {
 136       return description;
 137     }
 138
 139     public static SequenceAnnotationOrder forDescription(String d)
 140     {
 141       for (SequenceAnnotationOrder order : values())
 142       {
 143         if (order.toString().equals(d))
 144         {
 145           return order;
 146         }
 147       }
 148       return null;
 149     }
 150   }
 151
 152   /*
 153    * the alignment with respect to which annotations are sorted
 154    */
 155   private final AlignmentI alignment;
 156
 157   /*
 158    * if true, autocalculated are sorted first, if false, last
 159    */
 160   private boolean showAutocalcAbove;
 161
 162   /*
 163    * working map of sequence index in alignment
 164    */
 165   private final Map<SequenceI, Integer> sequenceIndices = new HashMap<>();
 166
 167   /*
 168    * if true, sort only repositions auto-calculated annotation (to top or bottom)
 169    */
 170   private boolean autocalcOnly;
 171
 172   /**
 173    * Constructor
 174    *
 175    * @param av
 176    */
 177   public AnnotationSorter(AlignViewportI av)
 178   {
 179     this.alignment = av.getAlignment();
 180     this.showAutocalcAbove = av.isShowAutocalculatedAbove();
 181   }
 182
 183   /**
 184    * Default comparator sorts as follows by annotation type within sequence
 185    * order:
 186    * <ul>
 187    * <li>annotations with a reference to a sequence in the alignment are sorted
 188    * on sequence ordering</li>
 189    * <li>other annotations go 'at the end', with their mutual order
 190    * unchanged</li>
 191    * <li>within the same sequence ref, sort by label (non-case-sensitive)</li>
 192    * </ul>
 193    */
 194   private final Comparator<? super AlignmentAnnotation> bySequenceAndLabel = new Comparator<AlignmentAnnotation>()
 195   {
 196     @Override
 197     public int compare(AlignmentAnnotation o1, AlignmentAnnotation o2)
 198     {
 199       if (o1 == null && o2 == null)
 200       {
 201         return 0;
 202       }
 203       if (o1 == null)
 204       {
 205         return -1;
 206       }
 207       if (o2 == null)
 208       {
 209         return 1;
 210       }
 211
 212       // TODO how to treat sequence-related autocalculated annotation
 213       boolean o1auto = o1.autoCalculated && o1.sequenceRef == null;
 214       boolean o2auto = o2.autoCalculated && o2.sequenceRef == null;
 215       /*
 216        * Ignore label (keep existing ordering) for
 217        * Conservation/Quality/Consensus etc
 218        */
 219       if (o1auto && o2auto)
 220       {
 221         return 0;
 222       }
 223
 224       /*
 225        * Sort autocalculated before or after sequence-related.
 226        */
 227       if (o1auto)
 228       {
 229         return showAutocalcAbove ? -1 : 1;
 230       }
 231       if (o2auto)
 232       {
 233         return showAutocalcAbove ? 1 : -1;
 234       }
 235       if (autocalcOnly)
 236       {
 237         return 0; // don't reorder other annotations
 238       }
 239       int sequenceOrder = compareSequences(o1, o2);
 240       return sequenceOrder == 0 ? compareLabels(o1, o2) : sequenceOrder;
 241     }
 242
 243     @Override
 244     public String toString()
 245     {
 246       return "Sort by sequence and label";
 247     }
 248   };
 249
 250   /**
 251    * This comparator sorts as follows by sequence order within annotation type
 252    * <ul>
 253    * <li>annotations with a reference to a sequence in the alignment are sorted
 254    * on label (non-case-sensitive)</li>
 255    * <li>other annotations go 'at the end', with their mutual order
 256    * unchanged</li>
 257    * <li>within the same label, sort by order of the related sequences</li>
 258    * </ul>
 259    */
 260   private final Comparator<? super AlignmentAnnotation> byLabelAndSequence = new Comparator<AlignmentAnnotation>()
 261   {
 262     @Override
 263     public int compare(AlignmentAnnotation o1, AlignmentAnnotation o2)
 264     {
 265       if (o1 == null && o2 == null)
 266       {
 267         return 0;
 268       }
 269       if (o1 == null)
 270       {
 271         return -1;
 272       }
 273       if (o2 == null)
 274       {
 275         return 1;
 276       }
 277
 278       // TODO how to treat sequence-related autocalculated annotation
 279       boolean o1auto = o1.autoCalculated && o1.sequenceRef == null;
 280       boolean o2auto = o2.autoCalculated && o2.sequenceRef == null;
 281       /*
 282        * Ignore label (keep existing ordering) for
 283        * Conservation/Quality/Consensus etc
 284        */
 285       if (o1auto && o2auto)
 286       {
 287         return 0;
 288       }
 289
 290       /*
 291        * Sort autocalculated before or after sequence-related.
 292        */
 293       if (o1auto)
 294       {
 295         return showAutocalcAbove ? -1 : 1;
 296       }
 297       if (o2auto)
 298       {
 299         return showAutocalcAbove ? 1 : -1;
 300       }
 301       if (autocalcOnly)
 302       {
 303         return 0; // don't reorder other annotations
 304       }
 305       int labelOrder = compareLabels(o1, o2);
 306       return labelOrder == 0 ? compareSequences(o1, o2) : labelOrder;
 307     }
 308
 309     @Override
 310     public String toString()
 311     {
 312       return "Sort by label and sequence";
 313     }
 314   };
 315
 316   /**
 317    * noSort leaves sort order unchanged, within sequence- and autocalculated
 318    * annotations, but may switch the ordering of these groups. Note this is
 319    * guaranteed (at least in Java 7) as Arrays.sort() is guaranteed to be
 320    * 'stable' (not change ordering of equal items).
 321    */
 322   private Comparator<? super AlignmentAnnotation> noSort = new Comparator<AlignmentAnnotation>()
 323   {
 324     @Override
 325     public int compare(AlignmentAnnotation o1, AlignmentAnnotation o2)
 326     {
 327       // TODO how to treat sequence-related autocalculated annotation
 328       boolean o1auto = o1.autoCalculated && o1.sequenceRef == null;
 329       boolean o2auto = o2.autoCalculated && o2.sequenceRef == null;
 330       // TODO skip this test to allow customised ordering of all annotations
 331       // - needs a third option: place autocalculated first / last / none
 332       if (o1 != null && o2 != null)
 333       {
 334         if (o1auto && !o2auto)
 335         {
 336           return showAutocalcAbove ? -1 : 1;
 337         }
 338         if (!o1auto && o2auto)
 339         {
 340           return showAutocalcAbove ? 1 : -1;
 341         }
 342       }
 343       return 0;
 344     }
 345
 346     @Override
 347     public String toString()
 348     {
 349       return "No sort";
 350     }
 351   };
 352
 353   /**
 354    * Sorts by the specified ordering. If order is {@code CUSTOM}, meaning
 355    * annotations have been manually ordered by the user, no sort is performed.
 356    *
 357    * @param sortBy
 358    *          the sort order to apply
 359    * @param autoCalcOnly
 360    *          if true, only autocalculated annotations are repositioned (to top
 361    *          or bottom), others are left in their current order
 362    */
 363   public void sort(SequenceAnnotationOrder sortBy, boolean autoCalcOnly)
 364   {
 365     if (sortBy == null || sortBy == SequenceAnnotationOrder.CUSTOM)
 366     {
 367       return;
 368     }
 369
 370     this.autocalcOnly = autoCalcOnly;
 371
 372     /*
 373      * cache 'alignment sequence positions' if required for sorting
 374      */
 375     if (sortBy == SequenceAnnotationOrder.SEQUENCE_AND_LABEL
 376             || sortBy == SequenceAnnotationOrder.LABEL_AND_SEQUENCE)
 377     {
 378       saveSequenceIndices();
 379     }
 380
 381     Comparator<? super AlignmentAnnotation> comparator = getComparator(
 382             sortBy);
 383
 384     AlignmentAnnotation[] annotations = alignment.getAlignmentAnnotation();
 385     synchronized (annotations)
 386     {
 387       Arrays.sort(annotations, comparator);
 388     }
 389   }
 390
 391   /**
 392    * Calculates and saves in a temporary map the position of each annotation's
 393    * associated sequence (if it has one) in the alignment. Faster to do this
 394    * once than for every annotation comparison.
 395    */
 396   private void saveSequenceIndices()
 397   {
 398     sequenceIndices.clear();
 399
 400     Map<SequenceI, Integer> seqPositions = alignment.getSequencePositions();
 401
 402     AlignmentAnnotation[] alignmentAnnotations = alignment
 403             .getAlignmentAnnotation();
 404     for (AlignmentAnnotation ann : alignmentAnnotations)
 405     {
 406       SequenceI seq = ann.sequenceRef;
 407       if (seq != null)
 408       {
 409         Integer index = seqPositions.get(seq);
 410         if (index != null)
 411         {
 412           sequenceIndices.put(seq, index);
 413         }
 414       }
 415     }
 416   }
 417
 418   /**
 419    * Get the comparator for the specified sort order.
 420    *
 421    * @param order
 422    * @return
 423    */
 424   private Comparator<? super AlignmentAnnotation> getComparator(
 425           SequenceAnnotationOrder order)
 426   {
 427     if (order == null)
 428     {
 429       return noSort;
 430     }
 431     switch (order)
 432     {
 433     case NONE:
 434       return this.noSort;
 435     case SEQUENCE_AND_LABEL:
 436       return this.bySequenceAndLabel;
 437     case LABEL_AND_SEQUENCE:
 438       return this.byLabelAndSequence;
 439     default:
 440       throw new UnsupportedOperationException(order.toString());
 441     }
 442   }
 443
 444   /**
 445    * Non-case-sensitive comparison of annotation labels. Returns zero if either
 446    * argument is null.
 447    *
 448    * @param o1
 449    * @param o2
 450    * @return
 451    */
 452   private int compareLabels(AlignmentAnnotation o1, AlignmentAnnotation o2)
 453   {
 454     if (o1 == null || o2 == null)
 455     {
 456       return 0;
 457     }
 458     String label1 = o1.label;
 459     String label2 = o2.label;
 460     if (label1 == null && label2 == null)
 461     {
 462       return 0;
 463     }
 464     if (label1 == null)
 465     {
 466       return -1;
 467     }
 468     if (label2 == null)
 469     {
 470       return 1;
 471     }
 472     return label1.toUpperCase().compareTo(label2.toUpperCase());
 473   }
 474
 475   /**
 476    * Comparison based on position of associated sequence (if any) in the
 477    * alignment
 478    *
 479    * @param o1
 480    * @param o2
 481    * @return
 482    */
 483   private int compareSequences(AlignmentAnnotation o1,
 484           AlignmentAnnotation o2)
 485   {
 486     SequenceI seq1 = o1.sequenceRef;
 487     SequenceI seq2 = o2.sequenceRef;
 488     if (seq1 == null && seq2 == null)
 489     {
 490       return 0;
 491     }
 492
 493     /*
 494      * Sort non-sequence-related before or after sequence-related
 495      */
 496     if (seq1 == null)
 497     {
 498       return showAutocalcAbove ? -1 : 1;
 499     }
 500     if (seq2 == null)
 501     {
 502       return showAutocalcAbove ? 1 : -1;
 503     }
 504
 505     /*
 506      * else sort by associated sequence position
 507      */
 508     Integer index1 = sequenceIndices.get(seq1);
 509     Integer index2 = sequenceIndices.get(seq2);
 510     if (index1 == null)
 511     {
 512       return index2 == null ? 0 : -1;
 513     }
 514     if (index2 == null)
 515     {
 516       return 1;
 517     }
 518     return Integer.compare(index1.intValue(), index2.intValue());
 519   }
 520
 521   /**
 522    * Sort annotations to match the order of the provided list. This is intended
 523    * only for use when reloading a project, in order to set the saved order
 524    * after constructing a viewport (which might sort differently based on user
 525    * preferences for sort order).
 526    * <p>
 527    * There is some special handling specific to auto-calculated annotations.
 528    * These are saved in the project, to preserve their visibility and height
 529    * properties, but are recalculated when the viewport is reconstructed.
 530    * <ul>
 531    * <li>Autocalculated annotations are matched to the list by label
 532    * "Consensus/Quality/Conservation/Occupancy"</li>
 533    * <li>those that are matched have their visibility and height set</li>
 534    * </ul>
 535    *
 536    * @param addedAnnotation
 537    */
 538   public void sort(List<AlignmentAnnotation> annotations)
 539   {
 540     Arrays.sort(alignment.getAlignmentAnnotation(),
 541             new ReloadComparator(annotations));
 542   }
 543 }