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         newValue = shortProfile.add(key, value);
  90       } catch (ArithmeticException e) {
  91         handleOverflow();
  92         newValue = intProfile.add(key, value);
  93       }
  94     }
  95     return newValue;
  96   }
  97
  98   /**
  99    * Switch from counting shorts to counting ints
 100    */
 101   synchronized void handleOverflow()
 102   {
 103     int size = shortProfile.size();
 104     intProfile = new SparseIntArray(size);
 105     for (int i = 0; i < size; i++)
 106     {
 107       short key = shortProfile.keyAt(i);
 108       short value = shortProfile.valueAt(i);
 109       intProfile.put(key, value);
 110     }
 111     shortProfile = null;
 112     useInts = true;
 113   }
 114
 115   /**
 116    * Returns the size of the profile (number of distinct items counted)
 117    *
 118    * @return
 119    */
 120   public int size()
 121   {
 122     return useInts ? intProfile.size() : shortProfile.size();
 123   }
 124
 125   /**
 126    * Returns the value for the key (zero if no such key)
 127    *
 128    * @param key
 129    * @return
 130    */
 131   public int get(int key)
 132   {
 133     return useInts ? intProfile.get(key) : shortProfile.get(key);
 134   }
 135
 136   /**
 137    * Sets the value for the given key
 138    *
 139    * @param key
 140    * @param value
 141    */
 142   public void put(int key, int value)
 143   {
 144     if (useInts)
 145     {
 146       intProfile.put(key, value);
 147     }
 148     else
 149     {
 150       shortProfile.put(key, value);
 151     }
 152   }
 153
 154   public int keyAt(int k)
 155   {
 156     return useInts ? intProfile.keyAt(k) : shortProfile.keyAt(k);
 157   }
 158
 159   public int valueAt(int k)
 160   {
 161     return useInts ? intProfile.valueAt(k) : shortProfile.valueAt(k);
 162   }
 163
 164   /**
 165    * Answers true if this object wraps arrays of int values, false if using
 166    * short values
 167    *
 168    * @return
 169    */
 170   boolean isUsingInt()
 171   {
 172     return useInts;
 173   }
 174 }