/* Copyright 1989, 1990 by James Aspnes, David Applegate, and Bennet Yee */
/* See the file COPYING for distribution information */
#include "db.h"
#include "config.h"
#include "globals.h"
#include "externs.h"

int no_delays = 0;

/* elements in delay heap */
struct thunk {
  datum thing;
  datum time;
};

static struct thunk *delay_heap = 0;
static int delay_heap_size = 0;
int delay_heap_top = 0;

/* inserts 'me' into the delay heap at specified time */
datum delay (datum t)
{
  datum current_time;
  int i;                        /* for scanning up the delay heap */
  int parent;

  /* only WIZARD objects can delay when blocked */
  if (no_delays && !flag_set (me, F_WIZARD))
    return 0;

  /* can't schedule into the past */
  current_time = time (0);
  if (current_time > t)
    t = current_time;

  /* get the place to put it in */
  i = delay_heap_top++;

  /* make sure there is enough room */
  if (delay_heap_size == 0) {
    delay_heap = (struct thunk *) malloc (sizeof (struct thunk));
    delay_heap_size = 1;
  } else if (delay_heap_top >= delay_heap_size) {
    delay_heap_size *= 2;
    delay_heap = (struct thunk *)
      realloc ((void *) delay_heap, sizeof (struct thunk) * delay_heap_size);
  }

  /* find the spot for the new thing, floating other thunks down */
  while (i > 0 && t < delay_heap[parent = (i - 1) / 2].time) {
    delay_heap[i] = delay_heap[parent];
    i = parent;
  }

  /* insert new thunk */
  delay_heap[i].thing = me;
  delay_heap[i].time = t;

  return 1;
}

/* removes the heap element at position i */
static void delete_heap_element (int i)
{
  int left;                     /* twice i, left child */
  int winner;                   /* earlier child of left & left+1 */

  if (i >= delay_heap_top)
    return;

  delay_heap_top--;             /* cut off the last element */

  while ((left = i + i + 1) < delay_heap_top) {
    /* find earlier child */
    if (left + 1 >= delay_heap_top
      || delay_heap[left].time < delay_heap[left + 1].time) {
      winner = left;
    } else {
      winner = left + 1;
    }

    /* do we keep going? */
    if (delay_heap[delay_heap_top].time <= delay_heap[winner].time)
      break;

    /* yes, we keep going */
    delay_heap[i] = delay_heap[winner];
    i = winner;
  }

  /* stuff the last node into place */
  delay_heap[i] = delay_heap[delay_heap_top];
}

/* returns thing in heap scheduled for earliest time <= t, if any */
/* and deletes it from the heap */
datum undelay (datum t)
{
  datum thing;

  /* check to see if we're going to return anything at all */
  if (delay_heap_top == 0 || delay_heap[0].time > t)
    return NOTHING;

  /* else there's something there */
  /* save the thing */
  thing = delay_heap[0].thing;

  delete_heap_element (0);      /* kill the root */

  /* return what we found up top */
  return thing;
}

/* removes all pending delays for an object */
void remove_delays (datum victim)
{
  int i;

  i = 0;
  while (i < delay_heap_top) {
    if (delay_heap[i].thing == victim) {
      delete_heap_element (i);
      /* believe it or not, this actually works! */
      /* why?  well, when we float the min down from position i */
      /* we are only affecting the array for positions >= i */
      /* thus we don't have to worry about skipping some other */
      /* heap element we want to delete, since if it's < i we will */
      /* have processed it already */

      /* (it only looks like we are being stupid) */
    } else {
      i++;                      /* try the next position */
    }
  }
}

unsigned long next_event_time (void)
{
  if (delay_heap_top > 0) {
    return delay_heap[0].time;
  } else {
    return 0;
  }
}