src/jalview/datamodel/SecondaryStructureCount.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.datamodel;
  22
  23 import jalview.util.Comparison;
  24 import jalview.util.Format;
  25 import jalview.util.QuickSort;
  26 import jalview.util.SparseCount;
  27
  28 /**
  29  * A class to count occurrences of residues in a profile, optimised for speed
  30  * and memory footprint.
  31  *
  32  * @author gmcarstairs
  33  *
  34  */
  35 public class SecondaryStructureCount
  36 {
  37   /**
  38    * A data bean to hold the results of counting symbols
  39    */
  40   public class SymbolCounts
  41   {
  42     /**
  43      * the symbols seen (as char values), in no particular order
  44      */
  45     public final char[] symbols;
  46
  47     /**
  48      * the counts for each symbol, in the same order as the symbols
  49      */
  50     public final int[] values;
  51
  52     SymbolCounts(char[] s, int[] v)
  53     {
  54       symbols = s;
  55       values = v;
  56     }
  57   }
  58
  59   private static final int TOUPPERCASE = 'A' - 'a';
  60
  61   /*
  62    * nucleotide symbols to count (including N unknown)
  63    */
  64   private static final String SS_SYMBOLS = "HEC";
  65
  66
  67   static final int GAP_COUNT = 0;
  68
  69   /*
  70    * fast lookup tables holding the index into our count
  71    * arrays of each symbol; index 0 is reserved for gap counting
  72    */
  73   private static int[] SS_INDEX = new int[26];
  74
  75   static
  76   {
  77     for (int i = 0; i < SS_SYMBOLS.length(); i++)
  78     {
  79       SS_INDEX[SS_SYMBOLS.charAt(i) - 'A'] = i + 1;
  80     }
  81   }
  82
  83   /*
  84    * counts array, just big enough for the nucleotide or peptide
  85    * character set (plus gap counts in position 0)
  86    */
  87   private short[] counts;
  88
  89   /*
  90    * alternative array of int counts for use if any count
  91    * exceeds the maximum value of short (32767)
  92    */
  93   private int[] intCounts;
  94
  95   /*
  96    * flag set if we switch from short to int counts
  97    */
  98   private boolean useIntCounts;
  99
 100   /*
 101    * general-purpose counter, only for use for characters
 102    * that are not in the expected alphabet
 103    */
 104   private SparseCount otherData;
 105
 106   /*
 107    * keeps track of the maximum count value recorded
 108    * (if this class ever allows decrements, would need to
 109    * calculate this on request instead)
 110    */
 111   int maxCount;
 112
 113   /**
 114    * Constructor that allocates an array just big enough for the anticipated
 115    * characters, plus one position to count gaps
 116    */
 117   public SecondaryStructureCount()
 118   {
 119     //isSS = true;
 120     int charsToCount = SS_SYMBOLS.length();
 121     counts = new short[charsToCount + 1];
 122   }
 123
 124   /**
 125    * Increments the count for the given character. The supplied character may be
 126    * upper or lower case but counts are for the upper case only. Gap characters
 127    * (space, ., -) are all counted together.
 128    *
 129    * @param c
 130    * @return the new value of the count for the character
 131    */
 132   public int add(final char c)
 133   {
 134     char u = toUpperCase(c);
 135     int newValue = 0;
 136     int offset = getOffset(u);
 137
 138     /*
 139      * offset 0 is reserved for gap counting, so 0 here means either
 140      * an unexpected character, or a gap character passed in error
 141      */
 142     if (offset == 0)
 143     {
 144       if (Comparison.isGap(u))
 145       {
 146         newValue = addGap();
 147       }
 148       else
 149       {
 150         newValue = addOtherCharacter(u);
 151       }
 152     }
 153     else
 154     {
 155       newValue = increment(offset);
 156     }
 157     return newValue;
 158   }
 159
 160   /**
 161    * Increment the count at the specified offset. If this would result in short
 162    * overflow, promote to counting int values instead.
 163    *
 164    * @param offset
 165    * @return the new value of the count at this offset
 166    */
 167   int increment(int offset)
 168   {
 169     int newValue = 0;
 170     if (useIntCounts)
 171     {
 172       newValue = intCounts[offset];
 173       intCounts[offset] = ++newValue;
 174     }
 175     else
 176     {
 177       if (counts[offset] == Short.MAX_VALUE)
 178       {
 179         handleOverflow();
 180         newValue = intCounts[offset];
 181         intCounts[offset] = ++newValue;
 182       }
 183       else
 184       {
 185         newValue = counts[offset];
 186         counts[offset] = (short) ++newValue;
 187       }
 188     }
 189
 190     if (offset != GAP_COUNT)
 191     {
 192       // update modal residue count
 193       maxCount = Math.max(maxCount, newValue);
 194     }
 195     return newValue;
 196   }
 197
 198   /**
 199    * Switch from counting in short to counting in int
 200    */
 201   synchronized void handleOverflow()
 202   {
 203     intCounts = new int[counts.length];
 204     for (int i = 0; i < counts.length; i++)
 205     {
 206       intCounts[i] = counts[i];
 207     }
 208     counts = null;
 209     useIntCounts = true;
 210   }
 211
 212   /**
 213    * Returns this character's offset in the count array
 214    *
 215    * @param c
 216    * @return
 217    */
 218   int getOffset(char c)
 219   {
 220     int offset = 0;
 221     if ('A' <= c && c <= 'Z')
 222     {
 223       offset = SS_INDEX[c - 'A'];
 224     }
 225     return offset;
 226   }
 227
 228   /**
 229    * @param c
 230    * @return
 231    */
 232   protected char toUpperCase(final char c)
 233   {
 234     char u = c;
 235     if ('a' <= c && c <= 'z')
 236     {
 237       u = (char) (c + TOUPPERCASE);
 238     }
 239     return u;
 240   }
 241
 242   /**
 243    * Increment count for some unanticipated character. The first time this
 244    * called, a SparseCount is instantiated to hold these 'extra' counts.
 245    *
 246    * @param c
 247    * @return the new value of the count for the character
 248    */
 249   int addOtherCharacter(char c)
 250   {
 251     if (otherData == null)
 252     {
 253       otherData = new SparseCount();
 254     }
 255     int newValue = otherData.add(c, 1);
 256     maxCount = Math.max(maxCount, newValue);
 257     return newValue;
 258   }
 259
 260   /**
 261    * Set count for some unanticipated character. The first time this called, a
 262    * SparseCount is instantiated to hold these 'extra' counts.
 263    *
 264    * @param c
 265    * @param value
 266    */
 267   void setOtherCharacter(char c, int value)
 268   {
 269     if (otherData == null)
 270     {
 271       otherData = new SparseCount();
 272     }
 273     otherData.put(c, value);
 274   }
 275
 276   /**
 277    * Increment count of gap characters
 278    *
 279    * @return the new count of gaps
 280    */
 281   public int addGap()
 282   {
 283     int newValue = increment(GAP_COUNT);
 284     return newValue;
 285   }
 286
 287   /**
 288    * Answers true if we are counting ints (only after overflow of short counts)
 289    *
 290    * @return
 291    */
 292   boolean isCountingInts()
 293   {
 294     return useIntCounts;
 295   }
 296
 297   /**
 298    * Sets the count for the given character. The supplied character may be upper
 299    * or lower case but counts are for the upper case only.
 300    *
 301    * @param c
 302    * @param count
 303    */
 304   public void put(char c, int count)
 305   {
 306     char u = toUpperCase(c);
 307     int offset = getOffset(u);
 308
 309     /*
 310      * offset 0 is reserved for gap counting, so 0 here means either
 311      * an unexpected character, or a gap character passed in error
 312      */
 313     if (offset == 0)
 314     {
 315       if (Comparison.isGap(u))
 316       {
 317         set(0, count);
 318       }
 319       else
 320       {
 321         setOtherCharacter(u, count);
 322         maxCount = Math.max(maxCount, count);
 323       }
 324     }
 325     else
 326     {
 327       set(offset, count);
 328       maxCount = Math.max(maxCount, count);
 329     }
 330   }
 331
 332   /**
 333    * Sets the count at the specified offset. If this would result in short
 334    * overflow, promote to counting int values instead.
 335    *
 336    * @param offset
 337    * @param value
 338    */
 339   void set(int offset, int value)
 340   {
 341     if (useIntCounts)
 342     {
 343       intCounts[offset] = value;
 344     }
 345     else
 346     {
 347       if (value > Short.MAX_VALUE || value < Short.MIN_VALUE)
 348       {
 349         handleOverflow();
 350         intCounts[offset] = value;
 351       }
 352       else
 353       {
 354         counts[offset] = (short) value;
 355       }
 356     }
 357   }
 358
 359   /**
 360    * Returns the count for the given character, or zero if no count held
 361    *
 362    * @param c
 363    * @return
 364    */
 365   public int getCount(char c)
 366   {
 367     char u = toUpperCase(c);
 368     int offset = getOffset(u);
 369     if (offset == 0)
 370     {
 371       if (!Comparison.isGap(u))
 372       {
 373         // should have called getGapCount()
 374         return otherData == null ? 0 : otherData.get(u);
 375       }
 376     }
 377     return useIntCounts ? intCounts[offset] : counts[offset];
 378   }
 379
 380   public int getGapCount()
 381   {
 382     return useIntCounts ? intCounts[0] : counts[0];
 383   }
 384
 385   /**
 386    * Answers true if this object wraps a counter for unexpected characters
 387    *
 388    * @return
 389    */
 390   boolean isUsingOtherData()
 391   {
 392     return otherData != null;
 393   }
 394
 395   /**
 396    * Returns the character (or concatenated characters) for the symbol(s) with
 397    * the given count in the profile. Can be used to get the modal residue by
 398    * supplying the modal count value. Returns an empty string if no symbol has
 399    * the given count. The symbols are in alphabetic order of standard peptide or
 400    * nucleotide characters, followed by 'other' symbols if any.
 401    *
 402    * @return
 403    */
 404   public String getSSForCount(int count)
 405   {
 406     if (count == 0)
 407     {
 408       return "";
 409     }
 410
 411     /*
 412      * find counts for the given value and append the
 413      * corresponding symbol
 414      */
 415     StringBuilder modal = new StringBuilder();
 416     if (useIntCounts)
 417     {
 418       for (int i = 1; i < intCounts.length; i++)
 419       {
 420         if (intCounts[i] == count)
 421         {
 422           modal.append(
 423                   SS_SYMBOLS.charAt(i - 1));
 424         }
 425       }
 426     }
 427     else
 428     {
 429       for (int i = 1; i < counts.length; i++)
 430       {
 431         if (counts[i] == count)
 432         {
 433           modal.append(
 434                   SS_SYMBOLS.charAt(i - 1));
 435         }
 436       }
 437     }
 438     if (otherData != null)
 439     {
 440       for (int i = 0; i < otherData.size(); i++)
 441       {
 442         if (otherData.valueAt(i) == count)
 443         {
 444           modal.append((char) otherData.keyAt(i));
 445         }
 446       }
 447     }
 448     return modal.toString();
 449   }
 450
 451   /**
 452    * Returns the highest count for any symbol(s) in the profile (excluding gap)
 453    *
 454    * @return
 455    */
 456   public int getModalCount()
 457   {
 458     return maxCount;
 459   }
 460
 461   /**
 462    * Returns the number of distinct symbols with a non-zero count (excluding the
 463    * gap symbol)
 464    *
 465    * @return
 466    */
 467   public int size()
 468   {
 469     int size = 0;
 470     if (useIntCounts)
 471     {
 472       for (int i = 1; i < intCounts.length; i++)
 473       {
 474         if (intCounts[i] > 0)
 475         {
 476           size++;
 477         }
 478       }
 479     }
 480     else
 481     {
 482       for (int i = 1; i < counts.length; i++)
 483       {
 484         if (counts[i] > 0)
 485         {
 486           size++;
 487         }
 488       }
 489     }
 490
 491     /*
 492      * include 'other' characters recorded (even if count is zero
 493      * though that would be a strange use case)
 494      */
 495     if (otherData != null)
 496     {
 497       size += otherData.size();
 498     }
 499
 500     return size;
 501   }
 502
 503   /**
 504    * Returns a data bean holding those symbols that have a non-zero count
 505    * (excluding the gap symbol), with their counts.
 506    *
 507    * @return
 508    */
 509   public SymbolCounts getSymbolCounts()
 510   {
 511     int size = size();
 512     char[] symbols = new char[size];
 513     int[] values = new int[size];
 514     int j = 0;
 515
 516     if (useIntCounts)
 517     {
 518       for (int i = 1; i < intCounts.length; i++)
 519       {
 520         if (intCounts[i] > 0)
 521         {
 522           char symbol = SS_SYMBOLS.charAt(i - 1);
 523           symbols[j] = symbol;
 524           values[j] = intCounts[i];
 525           j++;
 526         }
 527       }
 528     }
 529     else
 530     {
 531       for (int i = 1; i < counts.length; i++)
 532       {
 533         if (counts[i] > 0)
 534         {
 535           char symbol = SS_SYMBOLS.charAt(i - 1);
 536           symbols[j] = symbol;
 537           values[j] = counts[i];
 538           j++;
 539         }
 540       }
 541     }
 542     if (otherData != null)
 543     {
 544       for (int i = 0; i < otherData.size(); i++)
 545       {
 546         symbols[j] = (char) otherData.keyAt(i);
 547         values[j] = otherData.valueAt(i);
 548         j++;
 549       }
 550     }
 551
 552     return new SymbolCounts(symbols, values);
 553   }
 554
 555   /**
 556    * Returns a tooltip string showing residues in descending order of their
 557    * percentage frequency in the profile
 558    *
 559    * @param normaliseBy
 560    *          the divisor for residue counts (may or may not include gapped
 561    *          sequence count)
 562    * @param percentageDecPl
 563    *          the number of decimal places to show in percentages
 564    * @return
 565    */
 566   public String getTooltip(int normaliseBy, int percentageDecPl)
 567   {
 568     SymbolCounts symbolCounts = getSymbolCounts();
 569     char[] ca = symbolCounts.symbols;
 570     int[] vl = symbolCounts.values;
 571
 572     /*
 573      * sort characters into ascending order of their counts
 574      */
 575     QuickSort.sort(vl, ca);
 576
 577     /*
 578      * traverse in reverse order (highest count first) to build tooltip
 579      */
 580     boolean first = true;
 581     StringBuilder sb = new StringBuilder(64);
 582     for (int c = ca.length - 1; c >= 0; c--)
 583     {
 584       final char residue = ca[c];
 585       // TODO combine residues which share a percentage
 586       // (see AAFrequency.completeCdnaConsensus)
 587       float tval = (vl[c] * 100f) / normaliseBy;
 588       sb.append(first ? "" : "; ").append(residue).append(" ");
 589       Format.appendPercentage(sb, tval, percentageDecPl);
 590       sb.append("%");
 591       first = false;
 592     }
 593     return sb.toString();
 594   }
 595
 596   /**
 597    * Returns a string representation of the symbol counts, for debug purposes.
 598    */
 599   @Override
 600   public String toString()
 601   {
 602     StringBuilder sb = new StringBuilder();
 603     sb.append("[ ");
 604     SymbolCounts sc = getSymbolCounts();
 605     for (int i = 0; i < sc.symbols.length; i++)
 606     {
 607       sb.append(sc.symbols[i]).append(":").append(sc.values[i]).append(" ");
 608     }
 609     sb.append("]");
 610     return sb.toString();
 611   }
 612 }