cache.java

发布/订阅系统路由重配算法,可应用于ad hoc环境

/*
 * Created on May 9, 2005
 *
 * To change the template for this generated file go to
 * Window>Preferences>Java>Code Generation>Code and Comments
 */

package broker;

import com.Notification;

import util.*;

/**
 * @author parzy
 *
 * To change the template for this generated type comment go to
 * Window>Preferences>Java>Code Generation>Code and Comments
 */
public class Cache {
	
	/**
	 * The array to store notification IDs.
	 */
	private ID[] cache;
	
	/**
	 * Pointer to the first entry after a broadcast.
	 */
	private int first = 0;
	
	/**
	 * Pointer to the next cache entry.
	 */
	private int next = 0;
	
	/**
	 * Creates a new cache of the given size.
	 * @param cacheSize the cache's size.
	 */	
	public Cache(int cacheSize){
		this.cache = new ID[cacheSize];
	}
	
	/**
	 * Stores the notification ID.
	 * @param notification the notification.
	 */
	public void add(Notification notification){
		// store notification ID
		cache[next] = notification.getID();
		next = (next+1)%cache.length;

		// cache is full
		if(next == first){
			first = (first+1)%cache.length;
		}
	}
	
	public boolean contains(Notification notification){
		ID id = notification.getID();
		for(int i=0; i<cache.length; i++){
			if(id.equals(cache[i])){
				return true;
			}
		}
		return false;
	}
	
	
	/**
	 * Returns a Bloom filter containing all cache elements,
	 * which have been added since the previous Bloom filter was returned.
	 * @param size the Bloom filter's ensured capacity.
	 * @param numberOfHashs the number of used hash functions.
	 * @return a Bloom filter containing the last added elements.
	 */
	public BloomFilter getBloomFilter(int capacity, int numberOfHashs){

		BloomFilter f;  // the Bloom filter to return
		
		// create the Bloom Filter
		f = new BloomFilter(capacity, numberOfHashs);
		for(int i=first; i != next; i=(i+1)%cache.length){
			f.add(cache[i]);
		}
		
		// reset first
		first = next;
		return f;
	}
	
	/**
	 * Counts the common elements of the cache and the Bloom filter.
	 * @param bloomFilter the specified Bloom filter.
	 * @return the number of common elements.
	 */
	public double countHits(BloomFilter bloomFilter){

		double hits; // common entries
		
		hits = 0;
		for(int i=0; i<cache.length; i++){
			if(cache[i] != null){
				if( bloomFilter.contains(cache[i]) ){
					hits += 1;
				}
			}
		}
		return hits;
	}

	/**
	 * Determines the number of equal cache entries.
	 * @param c another cache.
	 * @return the number of equal cache entries.
	 */
	public double countHits(Cache c){
		
		double hits; // equal entries
		
		hits = 0;
		for(int i=0; i<cache.length; i++){
			for(int j=0; j<c.cache.length; j++){
				if(cache[i] == null){
					break;
				}
				if(cache[i] == c.cache[j]){
					hits += 1;
					break;
				}
			}
		}
		return hits;
	}
	
	public void clear(){
		first = next;
	}
	
	public int getFillState() {
		return next < first ? next+cache.length-first : next - first; 
	}
	
//	// TODO: Klasse implementieren aufpassen auf Cache Synchronität
//	private ID[] cache;
//	private int first;
//	private int next; // Zeiger aus nächste, dort immer null
//	private int filterSize;
//	private int cacheSize; // TODO: Brauch ich den?
//	private HashFunction[] hashs;
//	private double prob = 1.0;
//	private Broker local = null;
//	
//	// TODO: addNotification implementieren
//	public void addNotification(Notification n){
//		
//		if((next+1) % cacheSize == first){
//			throw new CacheFullException();
//		}
//		cache[next] = n.getId();
//		next = (next+1) % cacheSize;
//		cache[next] = null;
//	}
//	
//	
//	public BloomFilter getBloomFilter(){
//		BloomFilter f;
//		
//		f = new BloomFilter(filterSize, hashs);
//		for(int i = first; cache[i] != null; i =  (i+1)%cacheSize){
//			f.add(cache[i].hashCode());
//		}
//		first = next;
//		return f;
//	}
//	
//	public double countCommonEvents(BloomFilter f){
//		double p1;
//		double p2;
//		double count = 0;
//		p1 = this.prob;
//		p2 = f.getProbability();
//		
//		for(int i=0; i<cacheSize; i++){
//			if(cache[i] != null){
//				count += (1.0d/(p1*p2)) * (f.contains(cache[i].hashCode()) ? 1.0d : 0.0d);  
//			}
//		}
//		return count;
//	}
//
//	public boolean isFull(){
//		return (next+1) % cacheSize == first;
//	}
	
}