+++ /dev/null
-/*
- * 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
