问用二进制堆实现优先级队列的事件驱动模拟

EN

number_of_tasks = 0

while start_heap not empty
    if min_start_time < min_end_time
       pop min_start_time
       number_of_tasks += 1    
    else if min_end_time < min_start_time
       pop min_end_time
       number_of_tasks -= 1
    else 
       pop min_start_time
       pop min_end_time

while end_heap not empty
       pop min_end_time
       number_of_tasks -= 1

# User needs to type "gem install simplekit" on the command line to
# snag a copy of this library from the public gem repository
require 'simplekit' # contains a PriorityQueue implementation

# define an "event notice" structure which stores the tag for an event method,
# the time the event should occur, and what arguments are to be passed to it.
EVENT_NOTICE = Struct.new(:event, :time, :args) {
  include Comparable
  def <=>(other)    # define a comparison ordering based on my time vs other's time
    return time - other.time  # comparison of two times is positive, zero, or negative
  end
}

@pq = PriorityQueue.new    # @ makes globally shared (not really, but close enough for illustration purposes)
@num_tasks = 0      # number of tasks currently active
@clock = 0          # current time in the simulation

# define a report method
def report()
  puts "#{@clock}: #{@num_tasks}"  # print current simulation time & num_tasks
end

# define an event for starting a task, that increments the @num_tasks counter
# and uses the @clock and task duration to schedule when this task will end
# by pushing a suitable EVENT_NOTICE onto the priority queue.
def start_task(current_task)
  @num_tasks += 1
  @pq.push(EVENT_NOTICE.new(:end_task, @clock + current_task.duration, nil))
  report()
end

# define an event for ending a task, which decrements the counter
def end_task(_)   # _ means ignore any argument
  @num_tasks -= 1
  report()
end

# define a task as a suitable structure containing start time and duration
task = Struct.new(:start, :duration)

# Create a set of three tasks.  I've wired them in, but they could
# be read in or generated dynamically.
task_set = [task.new(2, 5), task.new(4, 23), task.new(7, 4)]

# Add each of the task's start_task event to the priority queue, ordered
# by time of occurrence (as specified in EVENT_NOTICE)
for t in task_set
  @pq.push(EVENT_NOTICE.new(:start_task, t.start, t))
end

report()
# Keep popping EVENT_NOTICE's off the priority queue until you run out. For
# each notice, update the @clock and invoke the event contained in the notice
until @pq.empty?
  current_event = @pq.pop
  @clock = current_event.time
  send(current_event.event, current_event.args)
end

0: 0
2: 1
4: 2
7: 1
7: 2
11: 1
27: 0

#include <stdio.h>
#include <stdlib.h>
#include "sim_engine.h"

// define a task as a suitable structure containing start time and duration
typedef struct {
  double start;
  double duration;
} task;

// stamp out new tasks on demand
task* new_task(double start, double duration) {
  task* t = (task*) calloc(1, sizeof(task));
  t->start = start;
  t->duration = duration;
  return t;
}

// create state variables
static int num_tasks;

// provide reporting
void report() {
  // print current simulation time & num_tasks
  printf("%8.3lf: %d\n", sim_time(), num_tasks);
}

// define an event for ending a task, which decrements the counter
void end_task(void* current_task) {
  --num_tasks;
  free(current_task);
  report();
}

// define an event for starting a task, that increments the num_tasks counter
// and uses the task duration to schedule when this task will end.
void start_task(void* current_task) {
  ++num_tasks;
  schedule(end_task, ((task*) current_task)->duration, current_task);
  report();
}

// all event graphs must supply an initialize event to kickstart the process.
void initialize() {
  num_tasks = 0;      // number of tasks currently active
  // Create an initial set of three tasks.  I've wired them in, but they could
  // be read in or generated dynamically.
  task* task_set[] = {
    new_task(2.0, 5.0), new_task(4.0, 23.0), new_task(7.0, 4.0)
  };
  // Add each of the task's start_task event to the priority queue, ordered
  // by time of occurrence.  In general, though, events can be scheduled
  // dynamically from trigger events.
  for(int i = 0; i < 3; ++i) {
    schedule(start_task, task_set[i]->start, task_set[i]);
  }
  report();
}

int main() {
  run_sim();
  return 0;
}

typedef void (*event_p)(void*);

void initialize();
void schedule(event_p event, double delay, void* args);
void run_sim();
double sim_time();

#include <stdlib.h>
#include "sim_engine.h"
#include "heap.h"

typedef struct {
  double time;
  event_p event;
  void* args;
} event_notice;

static heap_t *event_list;
static double sim_clock;

// return the current simulated time on demand
double sim_time() {
  return sim_clock;
}

// schedule the specified event to occur after the specified delay, with args
void schedule(event_p event, double delay, void* args) {
  event_notice* en = (event_notice*) calloc(1, sizeof(event_notice));
  en->time = sim_clock + delay;
  en->event = event;
  en->args = args;
  push(event_list, en->time, en);
}

// simulation executive loop.
void run_sim() {
  event_list = (heap_t *) calloc(1, sizeof(heap_t));
  sim_clock = 0.0;     // initialize time in the simulation

  initialize();

  // Keep popping event_notice's off the priority queue until you run out. For
  // each notice, update the clock, invoke the event contained in the notice,
  // and cleanup.
  while(event_list->len > 0) {
    event_notice* current_event = pop(event_list);
    sim_clock = current_event->time;
    current_event->event(current_event->args);
    free(current_event);
  }
}

typedef struct {
    double priority;
    void *data;
} node_t;

typedef struct {
    node_t *nodes;
    int len;
    int size;
} heap_t;

void push(heap_t *h, double priority, void *data);
void *pop(heap_t *h);

#include <stdlib.h>
#include "heap.h"

void push(heap_t *h, double priority, void *data) {
    if (h->len + 1 >= h->size) {
        h->size = h->size ? h->size * 2 : 4;
        h->nodes = (node_t *)realloc(h->nodes, h->size * sizeof (node_t));
    }
    int i = h->len + 1;
    int j = i / 2;
    while (i > 1 && h->nodes[j].priority > priority) {
        h->nodes[i] = h->nodes[j];
        i = j;
        j = j / 2;
    }
    h->nodes[i].priority = priority;
    h->nodes[i].data = data;
    h->len++;
}

void *pop(heap_t *h) {
    int i, j, k;
    if (!h->len) {
        return NULL;
    }
    void *data = h->nodes[1].data;

    h->nodes[1] = h->nodes[h->len];

    h->len--;

    i = 1;
    while (i!=h->len+1) {
        k = h->len+1;
        j = 2 * i;
        if (j <= h->len && h->nodes[j].priority < h->nodes[k].priority) {
            k = j;
        }
        if (j + 1 <= h->len && h->nodes[j + 1].priority < h->nodes[k].priority) {
            k = j + 1;
        }
        h->nodes[i] = h->nodes[k];
        i = k;
    }
    return data;
}