/* 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"

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;
    }
}