src/jalview/util/SparseCount.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.util;
  22
  23 import jalview.ext.android.SparseIntArray;
  24 import jalview.ext.android.SparseShortArray;
  25
  26 /**
  27  * A class to count occurrences of characters with minimal memory footprint.
  28  * Sparse arrays of short values are used to hold the counts, with automatic
  29  * promotion to arrays of int if any count exceeds the maximum value for a
  30  * short.
  31  *
  32  * @author gmcarstairs
  33  *
  34  */
  35 public class SparseCount
  36 {
  37   private static final int DEFAULT_PROFILE_SIZE = 2;
  38
  39   /*
  40    * array of keys (chars) and values (counts)
  41    * held either as shorts or (if shorts overflow) as ints
  42    */
  43   private SparseShortArray shortProfile;
  44
  45   private SparseIntArray intProfile;
  46
  47   /*
  48    * flag is set true after short overflow occurs
  49    */
  50   private boolean useInts;
  51
  52   /**
  53    * Constructor which initially creates a new sparse array of short values to
  54    * hold counts.
  55    *
  56    * @param profileSize
  57    */
  58   public SparseCount(int profileSize)
  59   {
  60     this.shortProfile = new SparseShortArray(profileSize);
  61   }
  62
  63   /**
  64    * Constructor which allocates an initial count array for only two distinct
  65    * values (the array will grow if needed)
  66    */
  67   public SparseCount()
  68   {
  69     this(DEFAULT_PROFILE_SIZE);
  70   }
  71
  72   /**
  73    * Adds the given value for the given key (or sets the initial value), and
  74    * returns the new value
  75    *
  76    * @param key
  77    * @param value
  78    */
  79   public int add(int key, int value)
  80   {
  81     int newValue = 0;
  82     if (useInts)
  83     {
  84       newValue = intProfile.add(key, value);
  85     }
  86     else
  87     {
  88       try
  89       {
  90         newValue = shortProfile.add(key, value);
  91       } catch (ArithmeticException e)
  92       {
  93         handleOverflow();
  94         newValue = intProfile.add(key, value);
  95       }
  96     }
  97     return newValue;
  98   }
  99
 100   /**
 101    * Switch from counting shorts to counting ints
 102    */
 103   synchronized void handleOverflow()
 104   {
 105     int size = shortProfile.size();
 106     intProfile = new SparseIntArray(size);
 107     for (int i = 0; i < size; i++)
 108     {
 109       short key = shortProfile.keyAt(i);
 110       short value = shortProfile.valueAt(i);
 111       intProfile.put(key, value);
 112     }
 113     shortProfile = null;
 114     useInts = true;
 115   }
 116
 117   /**
 118    * Returns the size of the profile (number of distinct items counted)
 119    *
 120    * @return
 121    */
 122   public int size()
 123   {
 124     return useInts ? intProfile.size() : shortProfile.size();
 125   }
 126
 127   /**
 128    * Returns the value for the key (zero if no such key)
 129    *
 130    * @param key
 131    * @return
 132    */
 133   public int get(int key)
 134   {
 135     return useInts ? intProfile.get(key) : shortProfile.get(key);
 136   }
 137
 138   /**
 139    * Sets the value for the given key
 140    *
 141    * @param key
 142    * @param value
 143    */
 144   public void put(int key, int value)
 145   {
 146     if (useInts)
 147     {
 148       intProfile.put(key, value);
 149     }
 150     else
 151     {
 152       shortProfile.put(key, value);
 153     }
 154   }
 155
 156   public int keyAt(int k)
 157   {
 158     return useInts ? intProfile.keyAt(k) : shortProfile.keyAt(k);
 159   }
 160
 161   public int valueAt(int k)
 162   {
 163     return useInts ? intProfile.valueAt(k) : shortProfile.valueAt(k);
 164   }
 165
 166   /**
 167    * Answers true if this object wraps arrays of int values, false if using
 168    * short values
 169    *
 170    * @return
 171    */
 172   boolean isUsingInt()
 173   {
 174     return useInts;
 175   }
 176 }