incrementalfreq.java

peersim最新版1.0.4

/*
 * Copyright (c) 2003-2005 The BISON Project
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License version 2 as
 * published by the Free Software Foundation.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.	See the
 * GNU Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 *
 */
		
package peersim.util;

import java.io.PrintStream;

//XXX This implementation is very restricted, to be made more flexible
// using hashtables.
/**
* A class that can collect frequency information on integer input.
* right now it can handle only unsigned input. It simply ignores negative
* numbers.
*/
public class IncrementalFreq implements Cloneable {


// ===================== fields ========================================
// =====================================================================

/** The number of items inserted. */
private int n;

/** freq[i] holds the frequency of i. primitive implementation, to be changed */
private int[] freq = null; 

/**
* The capacity, if larger than 0. Added values larger than or equal to
* this one will be ignored.
*/
private final int N;


// ====================== initialization ==============================
// ====================================================================


/**
* @param maxvalue Values in the input set larger than this one will be ignored.
* However, if it is negative, no values are ignored.
*/
public IncrementalFreq(int maxvalue) {
	
	N = maxvalue+1;
	reset();
}

// --------------------------------------------------------------------

/** Calls <code>this(-1)</code>, that is, no values will be ignored.
* @see #IncrementalFreq(int) */
public IncrementalFreq() {
	
	this(-1);
}

// --------------------------------------------------------------------

/** Reset the state of the object. After calling this, all public methods
* behave the same as they did after constructing the object.
*/
public void reset() {

	if( freq==null || N==0 ) freq = new int[0];
	else for(int i=0; i<freq.length; ++i) freq[i]=0;
	n = 0;
}


// ======================== methods ===================================
// ====================================================================

/**
 * Adds item <code>i</code> to the input set.
 * It calls <code>add(i,1)</code>.
 * @see #add(int,int)
 */
public final void add( int i ) { add(i,1); }


// --------------------------------------------------------------------

/**
 * Adds item <code>i</code> to the input set <code>k</code> times.
 * That is, it increments counter <code>i</code> by <code>k</code>.
 * If, however, <code>i</code> is negative, or larger than the maximum defined
 * at construction time (if a maximum was set at all) the operation is ignored.
 */
public void add( int i, int k ) {
  
  if( N>0 && i>=N ) return;
  if( i<0 || k<=0 ) return;

  // Increase number of items by k.
  n+=k;

  // If index i is out of bounds for the current array of counters,
  // increase the size of the array to i+1.
  if( i>=freq.length )
  {
    int tmp[] = new int[i+1];
    System.arraycopy(freq, 0, tmp, 0, freq.length);
    freq=tmp;
  }

  // Finally, increase counter i by k.
  freq[i]+=k;
}

// --------------------------------------------------------------------

/** Returns number of processed data items.
* This is the number of items over which the class holds statistics.
*/
public int getN() { return n; }

// --------------------------------------------------------------------

/** Returns the number of occurrences of the given integer. */
public int getFreq(int i) {
	
	if( i>=0 && i<freq.length ) return freq[i];
	else return 0;
}

// --------------------------------------------------------------------
	

/**
 * Performs an element-by-element vector subtraction of the
 * frequency vectors. If <code>strict</code> is true, it
 * throws an IllegalArgumentException if <code>this</code> is
 * not strictly larger than <code>other</code> (element by element)
 * (Note that both frequency vectors are positive.)
 * Otherwise just sets those elements in <code>this</code> to zero
 * that are smaller than those of <code>other</code>.
 * @param other The instance of IncrementalFreq to subtract
 * @param strict See above explanation
 */
public void remove(IncrementalFreq other, boolean strict) {

	// check if other has non-zero elements in non-overlapping part
	if(strict && other.freq.length>freq.length)
	{
		for(int i=other.freq.length-1; i>=freq.length; --i)
		{
			if (other.freq[i]!=0)
				throw new IllegalArgumentException();
		}
	}
	
	final int minLength = Math.min(other.freq.length, freq.length);
	for (int i=minLength-1; i>=0; i--)
	{
		if (strict && freq[i] < other.freq[i])
			throw new IllegalArgumentException();
		final int remove = Math.min(other.freq[i], freq[i]);
		n -= remove;
		freq[i] -= remove;
	}
}

// ---------------------------------------------------------------------

/**
* Prints current frequency information. Prints a separate line for
* all values from 0 to the capacity of the internal representation using the
* format
* <pre>
* value occurrences
* </pre>
* That is, numbers with zero occurrences will also be printed. 
*/
public void printAll( PrintStream out ) {
	
	for(int i=0; i<freq.length; ++i)
	{
		out.println(i+" "+freq[i]);
	}
}

// ---------------------------------------------------------------------

/**
* Prints current frequency information. Prints a separate line for
* all values that have a number of occurrences different from zero using the 
* format
* <pre>
* value occurrences
* </pre>
*/
public void print( PrintStream out ) {

	for(int i=0; i<freq.length; ++i)
	{
		if(freq[i]!=0) out.println(i+" "+freq[i]);
	}
}

// ---------------------------------------------------------------------

public String toString() {
	
	StringBuilder result=new StringBuilder("");
	for(int i=0; i<freq.length; ++i)
	{
		if (freq[i] != 0)
			result.append(" (").append(i).append(","
			).append(freq[i]).append(")");
	}
	return result.toString();
}

// ---------------------------------------------------------------------

/** An alternative method to convert the object to String */
public String toArithmeticExpression() {

	StringBuilder result=new StringBuilder("");
	for (int i=freq.length-1; i>=0; i--)
	{
		if (freq[i] != 0)
			result.append(freq[i]).append(
			"*").append(i).append("+");
	}
	
	if (result.length()==0)
		return "(empty)";
	else
		return result.substring(0, result.length()-1);
}

// ---------------------------------------------------------------------

public Object clone() throws CloneNotSupportedException {

	IncrementalFreq result = (IncrementalFreq)super.clone();
	if( freq != null ) result.freq = freq.clone();
	return result;
}

// ---------------------------------------------------------------------

/**
* Tests equality between two IncrementalFreq instances.
* Two objects are equal if both hold the same set of numbers that have
* occurred non-zero times and the number of occurrences is also equal for
* these numbers.
*/
public boolean equals(Object obj) {

	if( !( obj instanceof IncrementalFreq) ) return false;
	IncrementalFreq other = (IncrementalFreq)obj;
	final int minlength = Math.min(other.freq.length, freq.length);
	
	for (int i=minlength-1; i>=0; i--)
		if (freq[i] != other.freq[i])
			return false;

	if( freq.length > minlength ) other=this;
	for (int i=minlength; i<other.freq.length; i++)
		if( other.freq[i] != 0 )
			return false;

	return true;
}

// ---------------------------------------------------------------------

/**
* Hashcode (consistent with {@link #equals}). Probably you will never want to
* use this, but since we have {@link #equals}, we must implement it.
*/
public int hashCode() {

	int sum = 0;
	for(int i=0; i<freq.length; ++i) sum += freq[i]*i;
	return sum;
}

// ---------------------------------------------------------------------

/*
public static void main(String[] pars) {
	
	IncrementalFreq ifq = new IncrementalFreq(Integer.parseInt(pars[0]));
	for(int i=1; i<pars.length; ++i)
	{
		ifq.add(Integer.parseInt(pars[i]));
	}
	ifq.print(System.out);
	System.out.println(ifq);
}
*/
}