contrib/psg/src/peersim/util/IncrementalFreq.java

   1 /*
   2  * Copyright (c) 2003-2005 The BISON Project
   3  *
   4  * This program is free software; you can redistribute it and/or modify
   5  * it under the terms of the GNU Lesser General Public License version 2 as
   6  * published by the Free Software Foundation.
   7  *
   8  * This program is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  11  * GNU Lesser General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU Lesser General Public License
  14  * along with this program; if not, write to the Free Software
  15  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  16  *
  17  */
  18
  19 package peersim.util;
  20
  21 import java.io.PrintStream;
  22
  23 //XXX This implementation is very restricted, to be made more flexible
  24 // using hashtables.
  25 /**
  26 * A class that can collect frequency information on integer input.
  27 * right now it can handle only unsigned input. It simply ignores negative
  28 * numbers.
  29 */
  30 public class IncrementalFreq implements Cloneable {
  31
  32
  33 // ===================== fields ========================================
  34 // =====================================================================
  35
  36 /** The number of items inserted. */
  37 private int n;
  38
  39 /** freq[i] holds the frequency of i. primitive implementation, to be changed */
  40 private int[] freq = null;
  41
  42 /**
  43 * The capacity, if larger than 0. Added values larger than or equal to
  44 * this one will be ignored.
  45 */
  46 private final int N;
  47
  48
  49 // ====================== initialization ==============================
  50 // ====================================================================
  51
  52
  53 /**
  54 * @param maxvalue Values in the input set larger than this one will be ignored.
  55 * However, if it is negative, no values are ignored.
  56 */
  57 public IncrementalFreq(int maxvalue) {
  58
  59         N = maxvalue+1;
  60         reset();
  61 }
  62
  63 // --------------------------------------------------------------------
  64
  65 /** Calls <code>this(-1)</code>, that is, no values will be ignored.
  66 * @see #IncrementalFreq(int) */
  67 public IncrementalFreq() {
  68
  69         this(-1);
  70 }
  71
  72 // --------------------------------------------------------------------
  73
  74 /** Reset the state of the object. After calling this, all public methods
  75 * behave the same as they did after constructing the object.
  76 */
  77 public void reset() {
  78
  79         if( freq==null || N==0 ) freq = new int[0];
  80         else for(int i=0; i<freq.length; ++i) freq[i]=0;
  81         n = 0;
  82 }
  83
  84
  85 // ======================== methods ===================================
  86 // ====================================================================
  87
  88 /**
  89  * Adds item <code>i</code> to the input set.
  90  * It calls <code>add(i,1)</code>.
  91  * @see #add(int,int)
  92  */
  93 public final void add( int i ) { add(i,1); }
  94
  95
  96 // --------------------------------------------------------------------
  97
  98 /**
  99  * Adds item <code>i</code> to the input set <code>k</code> times.
 100  * That is, it increments counter <code>i</code> by <code>k</code>.
 101  * If, however, <code>i</code> is negative, or larger than the maximum defined
 102  * at construction time (if a maximum was set at all) the operation is ignored.
 103  */
 104 public void add( int i, int k ) {
 105
 106   if( N>0 && i>=N ) return;
 107   if( i<0 || k<=0 ) return;
 108
 109   // Increase number of items by k.
 110   n+=k;
 111
 112   // If index i is out of bounds for the current array of counters,
 113   // increase the size of the array to i+1.
 114   if( i>=freq.length )
 115   {
 116     int tmp[] = new int[i+1];
 117     System.arraycopy(freq, 0, tmp, 0, freq.length);
 118     freq=tmp;
 119   }
 120
 121   // Finally, increase counter i by k.
 122   freq[i]+=k;
 123 }
 124
 125 // --------------------------------------------------------------------
 126
 127 /** Returns number of processed data items.
 128 * This is the number of items over which the class holds statistics.
 129 */
 130 public int getN() { return n; }
 131
 132 // --------------------------------------------------------------------
 133
 134 /** Returns the number of occurrences of the given integer. */
 135 public int getFreq(int i) {
 136
 137         if( i>=0 && i<freq.length ) return freq[i];
 138         else return 0;
 139 }
 140
 141 // --------------------------------------------------------------------
 142
 143
 144 /**
 145  * Performs an element-by-element vector subtraction of the
 146  * frequency vectors. If <code>strict</code> is true, it
 147  * throws an IllegalArgumentException if <code>this</code> is
 148  * not strictly larger than <code>other</code> (element by element)
 149  * (Note that both frequency vectors are positive.)
 150  * Otherwise just sets those elements in <code>this</code> to zero
 151  * that are smaller than those of <code>other</code>.
 152  * @param other The instance of IncrementalFreq to subtract
 153  * @param strict See above explanation
 154  */
 155 public void remove(IncrementalFreq other, boolean strict) {
 156
 157         // check if other has non-zero elements in non-overlapping part
 158         if(strict && other.freq.length>freq.length)
 159         {
 160                 for(int i=other.freq.length-1; i>=freq.length; --i)
 161                 {
 162                         if (other.freq[i]!=0)
 163                                 throw new IllegalArgumentException();
 164                 }
 165         }
 166
 167         final int minLength = Math.min(other.freq.length, freq.length);
 168         for (int i=minLength-1; i>=0; i--)
 169         {
 170                 if (strict && freq[i] < other.freq[i])
 171                         throw new IllegalArgumentException();
 172                 final int remove = Math.min(other.freq[i], freq[i]);
 173                 n -= remove;
 174                 freq[i] -= remove;
 175         }
 176 }
 177
 178 // ---------------------------------------------------------------------
 179
 180 /**
 181 * Prints current frequency information. Prints a separate line for
 182 * all values from 0 to the capacity of the internal representation using the
 183 * format
 184 * <pre>
 185 * value occurrences
 186 * </pre>
 187 * That is, numbers with zero occurrences will also be printed.
 188 */
 189 public void printAll( PrintStream out ) {
 190
 191         for(int i=0; i<freq.length; ++i)
 192         {
 193                 out.println(i+" "+freq[i]);
 194         }
 195 }
 196
 197 // ---------------------------------------------------------------------
 198
 199 /**
 200 * Prints current frequency information. Prints a separate line for
 201 * all values that have a number of occurrences different from zero using the
 202 * format
 203 * <pre>
 204 * value occurrences
 205 * </pre>
 206 */
 207 public void print( PrintStream out ) {
 208
 209         for(int i=0; i<freq.length; ++i)
 210         {
 211                 if(freq[i]!=0) out.println(i+" "+freq[i]);
 212         }
 213 }
 214
 215 // ---------------------------------------------------------------------
 216
 217 public String toString() {
 218
 219         StringBuilder result=new StringBuilder("");
 220         for(int i=0; i<freq.length; ++i)
 221         {
 222                 if (freq[i] != 0)
 223                         result.append(" (").append(i).append(","
 224                         ).append(freq[i]).append(")");
 225         }
 226         return result.toString();
 227 }
 228
 229 // ---------------------------------------------------------------------
 230
 231 /** An alternative method to convert the object to String */
 232 public String toArithmeticExpression() {
 233
 234         StringBuilder result=new StringBuilder("");
 235         for (int i=freq.length-1; i>=0; i--)
 236         {
 237                 if (freq[i] != 0)
 238                         result.append(freq[i]).append(
 239                         "*").append(i).append("+");
 240         }
 241
 242         if (result.length()==0)
 243                 return "(empty)";
 244         else
 245                 return result.substring(0, result.length()-1);
 246 }
 247
 248 // ---------------------------------------------------------------------
 249
 250 public Object clone() throws CloneNotSupportedException {
 251
 252         IncrementalFreq result = (IncrementalFreq)super.clone();
 253         if( freq != null ) result.freq = freq.clone();
 254         return result;
 255 }
 256
 257 // ---------------------------------------------------------------------
 258
 259 /**
 260 * Tests equality between two IncrementalFreq instances.
 261 * Two objects are equal if both hold the same set of numbers that have
 262 * occurred non-zero times and the number of occurrences is also equal for
 263 * these numbers.
 264 */
 265 public boolean equals(Object obj) {
 266
 267         if( !( obj instanceof IncrementalFreq) ) return false;
 268         IncrementalFreq other = (IncrementalFreq)obj;
 269         final int minlength = Math.min(other.freq.length, freq.length);
 270
 271         for (int i=minlength-1; i>=0; i--)
 272                 if (freq[i] != other.freq[i])
 273                         return false;
 274
 275         if( freq.length > minlength ) other=this;
 276         for (int i=minlength; i<other.freq.length; i++)
 277                 if( other.freq[i] != 0 )
 278                         return false;
 279
 280         return true;
 281 }
 282
 283 // ---------------------------------------------------------------------
 284
 285 /**
 286 * Hashcode (consistent with {@link #equals}). Probably you will never want to
 287 * use this, but since we have {@link #equals}, we must implement it.
 288 */
 289 public int hashCode() {
 290
 291         int sum = 0;
 292         for(int i=0; i<freq.length; ++i) sum += freq[i]*i;
 293         return sum;
 294 }
 295
 296 // ---------------------------------------------------------------------
 297
 298 /*
 299 public static void main(String[] pars) {
 300
 301         IncrementalFreq ifq = new IncrementalFreq(Integer.parseInt(pars[0]));
 302         for(int i=1; i<pars.length; ++i)
 303         {
 304                 ifq.add(Integer.parseInt(pars[i]));
 305         }
 306         ifq.print(System.out);
 307         System.out.println(ifq);
 308 }
 309 */
 310 }
 311
 312