heap.java

peersim最新版1.0.4

/*
 * Copyright (c) 2001 The Anthill Team
 *
 * 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.edsim;

import peersim.core.Node;
import peersim.core.CommonState;
import peersim.config.Configuration;
import peersim.config.IllegalParameterException;

/**
 *  The Heap data structure used to maintain events "sorted" by 
 *  scheduled time and to obtain the next event to be executed.
 *  
 *  @author Alberto Montresor
 *  @version $Revision: 1.10 $
 */
public class Heap implements PriorityQ {

//--------------------------------------------------------------------------
// Constants
//--------------------------------------------------------------------------

/** 
 * This parameter specifies how many
 * bits are used to order events that occur at the same time. Defaults
 * to 8. A value smaller than 8 causes an IllegalParameterException.
 * Higher values allow for a better discrimination, but reduce
 * the maximal time steps that can be simulated.
 * @config 
 */	
private static final String PAR_PBITS = "pbits";
private static final String PAR_PBITS_LEGACY = "simulation.timebits";

/** 
 * Specifies the initial capacity of the heap. Defaults to 65536.
 * @config 
 */	
private static final String PAR_SIZE = "size";


//--------------------------------------------------------------------------
// Fields
//--------------------------------------------------------------------------

// The following arrays are four heaps ordered by time. The alternative
// approach (i.e. to store event objects) requires much more memory,
// and based on some tests that I've done is not really much faster.

/** Event component of the heap */
private Object[] events;

/** Time component of the heap */
private long[] times;

/** Node component of the heap */
private Node[] nodes;

/** Pid component of the heap */
private byte[] pids;

/** Number of elements */
private int size;

/** Singleton event object used to return (event, time, node, pid) tuples */
private final Event ev = new Event();

/** The number of bits reserved to order event with the same timestamp */
private final int pbits;

/** The mask to test whether the time value fits into the range we can
represent */
private final long overflowMask;

//--------------------------------------------------------------------------
// Contructor
//--------------------------------------------------------------------------

/**
 * Initializes a new heap using defaults.
 */
public Heap() {
	this(""); // "" is not a valid prefix for a component
}

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

/**
 * Initializes a new heap using the configuration.
 */
public Heap(String prefix) {

	int size = Configuration.getInt(prefix+"."+PAR_SIZE,65536);
	
	// some complex stuff to deal with legacy parameter names...
	if( !Configuration.contains(PAR_PBITS_LEGACY) )
		pbits = Configuration.getInt(prefix+"."+PAR_PBITS,8);
	else
	{
		pbits = Configuration.getInt(PAR_PBITS_LEGACY);
		if( Configuration.contains(prefix+"."+PAR_PBITS) )
			throw new IllegalParameterException(PAR_PBITS_LEGACY,
				"Your configuration file contains both "+
				prefix+"."+PAR_PBITS+ " and "+
				PAR_PBITS_LEGACY+"; please remove "+
				PAR_PBITS_LEGACY);
	}

	if (pbits < 8 || pbits >= 31) {
		throw new IllegalParameterException(prefix+"."+PAR_PBITS,
		"This parameter should be >= 8 or < 31");
	}
	overflowMask = ~maxTime();
	events = new Object[size];
	times = new long[size];
	nodes = new Node[size];
	pids = new byte[size];
}

//--------------------------------------------------------------------------
// Methods
//--------------------------------------------------------------------------

/**
 * Returns the current number of events in the system.
 */
public int size()
{
	return size;
}

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

/**
 * Add a new event, to be scheduled at the specified time.
 * 
 * @param time the time at which this event should be scheduled
 * @param event the object describing the event
 * @param node the node at which the event has to be delivered
 * @param pid the protocol that handles the event
 */
public void add(long time, Object event, Node node, byte pid) 
{
	add(time,event,node,pid,CommonState.r.nextInt(1 << pbits));
}

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

/**
 * Add a new event, to be scheduled at the specified time.
 * 
 * @param time the time at which this event should be scheduled
 * @param event the object describing the event
 * @param node the node at which the event has to be delivered
 * @param pid the protocol that handles the event
 */
public void add(long time, Object event, Node node, byte pid, long priority) 
{
	if( (time&overflowMask) != 0 ) throw new
		IllegalArgumentException("Time overflow: time="+time);
//XXX should we test priority overflow? How much does it cost?
	
	time = (time << pbits) | priority;
	
	size++;
	int pos = size;
	put(pos, time, event, node, pid);
	while (pos > 1 && getTime(pos / 2) > time) {
		swap(pos, pos / 2);
		pos = pos / 2;
	}
}

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

/**
 * Removes the first event in the heap and returns it.
 * Note that, to avoid garbage collection, a singleton instance of
 * the Event class is used. This means that data contained in the
 * returned event are overwritten when a new invocation of this
 * method is performed.
 * @return first event or null if size is zero
 */
public Event removeFirst() {
	
	if(size==0) return null;

	ev.time = times[0] >> pbits;
	ev.event = events[0];
	ev.node = nodes[0];
	ev.pid = pids[0];
	swap(1, size);
	size--;
	minHeapify(1);
	return ev;
}

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

public long maxTime() { return Long.MAX_VALUE >> pbits; }

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

public long maxPriority() { return (1L << pbits)-1; }

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

/** 
 *  Prints the time values contained in the heap.
 */
public String toString()
{
	StringBuffer buffer = new StringBuffer();
	buffer.append("[Size: " + size + " Times: ");
	for (int i=1; i <= size; i++) {
		buffer.append(getTime(i)+",");
	}
	buffer.append("]");
	return buffer.toString();
}


//--------------------------------------------------------------------------
// Private methods
//--------------------------------------------------------------------------

/**
 * 
 */
private void minHeapify(int index) 
{
	// The time to be placed of the current node
	long time = getTime(index);  
	// Left, right children of the current index
	int l,r; 
	// Their associated time
	long lt, rt;
	// The minimum time between val, lt, rt
	long mintime;
	// The index of the mininum time
	int minindex = index; 
	do {
		index = minindex;
		mintime = time;
		l = index << 1;
		r = l + 1;
		if (l <= size && (lt = getTime(l)) < mintime) {
			minindex = l;
			mintime = lt;
		}
		if (r <= size && (rt = getTime(r)) < mintime) {
			minindex = r;
			mintime = rt;
		}
		if (minindex != index) {
			swap(minindex, index);
		}
	} while (minindex != index);
}

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

/**
 * 
 */
private void swap(int i1, int i2) {
	
	i1--;
	i2--;
	
	Object te = events[i1];
	events[i1] = events[i2];
	events[i2] = te;
	
	long tt = times[i1];
	times[i1] = times[i2];
	times[i2] = tt;
	
	Node tn = nodes[i1];
	nodes[i1] = nodes[i2];
	nodes[i2] = tn;

	byte tp = pids[i1];
	pids[i1] = pids[i2];
	pids[i2] = tp;
}

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

/**
 * 
 */
private long getTime(int index) {
	/* Compute first and second index, and return the value */
	index--;
	return times[index];
}

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

/**
 * 
 */
private void put(int index, long time, Object event, Node node, byte pid) {
	
	index--;
	if (index >= events.length) {
		doubleCapacity();
	}
	events[index] = event;
	times[index] = time;
	nodes[index] = node;
	pids[index] = pid;
}

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

/**
 * 
 */
private void doubleCapacity() {
	int oldsize = events.length;
	int newsize = oldsize*2;
	Object[] te = new Object[newsize];
	System.arraycopy(events, 0, te, 0, oldsize);
	events = te;
	long[] tt = new long[newsize];
	System.arraycopy(times, 0, tt, 0, oldsize);
	times = tt;
	Node[] tn = new Node[newsize];
	System.arraycopy(nodes, 0, tn, 0, oldsize);
	nodes = tn;
	byte[] tp = new byte[newsize];
	System.arraycopy(pids, 0, tp, 0, oldsize);
	pids = tp;
}

//--------------------------------------------------------------------------
// Testing
//--------------------------------------------------------------------------

/*
public static void main(String[] args) {
	Random random = new Random();
	Heap heap = new Heap();
	int rep = 1000000;
	if( args.length > 0 ) rep = Integer.parseInt(args[0]);
	int[] values1 = new int[rep];
	long[] values2 = new long[rep];
	for (int i = 0; i < rep; i++) {
		values1[i] = random.nextInt(1000000000); 
	}
	
	long time1 = System.currentTimeMillis();
	for (int i = 0; i < rep; i++) {
		heap.add(values1[i], null, null, (byte) 1);
	}
	long time2 = System.currentTimeMillis();
	System.out.println("Inserting: " + (time2-time1));
	
	time1 = System.currentTimeMillis();
	for (int i = 0; i < rep; i++) {
		values2[i] = heap.removeFirst().time;
	}
	time2 = System.currentTimeMillis();
	System.out.println("Removing: " + (time2-time1));
	
	Arrays.sort(values1);
	for (int i=0; i<rep; i++) {
		if (values1[i] != values2[i])
			System.out.print("+");
	}
}
*/

} // END Heap