LPC heap data-structure implementation for LDMud 3.3.x+

heap.c

/*
 * LPC Heap w/ Structs
 * Paradox@DUNE
 *
 * A general heap data-structure[0] implemented in LPC using a struct type.
 * Closely modelled on the Go programming language's heap implementation[1].
 *
 * Example Integer Min-heap Usage:
 *   inherit __PATH__(0)"heap";
 *   struct Heap min_heap = new_heap(({ 10, 5 }), (: $1 < $2 :));
 *   heap_push(min_heap, 1);
 *   heap_push(min_heap, 30);
 *   int smallest = heap_peek(min_heap); // 1
 *
 * See 'heap_test.c' for a complete example of usage.
 *
 * [0]: https://en.wikipedia.org/wiki/Heap_(data_structure)
 * [1]: https://cs.opensource.google/go/go/+/refs/tags/go1.17.2:src/container/heap/heap.go
 *
 * Changelog:
 *   - 2021-10-08 Initial code.
 */
#pragma strict_types, rtt_checks, pedantic, no_clone

/* Heap Type */
protected struct Heap {
  mixed * heap;
  closure less;
};

/* External Heap API */
protected struct Heap new_heap(mixed * elements, closure less);
protected void heap_init(struct Heap h);
protected mixed heap_pop(struct Heap h);
protected void heap_push(struct Heap h, mixed x);
protected mixed heap_remove(struct Heap h, int i);

/* Internal Heap API */
private void heap_swap(struct Heap h, int i, int j);
private void heap_up(struct Heap h, int j);
private int heap_down(struct Heap h, int i0, int n);

/*
 * new_heap constructs a heap of mixed elements that uses the given closure to
 * decide whether an element is less than another.
 *
 * The "less" closure should be a function of the form:
 *
 *   public int less(mixed elementA, mixed elementB);
 *
 * It should return true when elementA is less than elementB according to some
 * measure. E.g. a trivial min heap for 3 integers could use:
 *
 *   new_heap(({ 10, 1, 8 }), (: $1 < $2 :));
 *
 * The complexity of new_heap is O(n) where n = sizeof(elements)
 */
protected struct Heap new_heap(mixed * elements, closure less) {
  elements ||= ({ });

  if(!closurep(less)) {
    return 0;
  }

  struct Heap h = (<Heap> heap: elements, less: less);
  heap_init(h);
  return h;
}

/*
 * heap_init establishes the heap invariants required by the other functions in
 * this file. It is idempotent with respect to the heap invariants and may be
 * called whenever the heap invariants may have been invalidated.
 *
 * The complexity is O(n) where n = sizeof(h->heap)
 */
protected void heap_init(struct Heap h) {
  int n = sizeof(h->heap);
  for(int i = n / 2 - 1; i >= 0; i--) {
    heap_down(h, i, n);
  }
}

/*
 * heap_push pushes the element x onto the heap.
 *
 * The complexity is O(log n) where n = sizeof(h->heap)
 */
protected void heap_push(struct Heap h, mixed x) {
  h->heap += ({ x });
  heap_up(h, sizeof(h->heap) - 1);
}

/*
 * heap_remove removes and returns the element at index i from the heap.
 *
 * The complexity is O(log n) where n = sizeof(h->heap).
 */
protected mixed heap_remove(struct Heap h, int i) {
  int n = sizeof(h->heap) - 1;
  if(n != i) {
    heap_swap(h, i, n);
    if(!heap_down(h, i, n)) {
      heap_up(h, i);
    }
  }
  return heap_pop(h);
}

/*
 * Peek returns the minimum element (according to Less) but does not remove it.
 *
 * The complexity is O(1).
 */
protected mixed heap_peek(struct Heap h) {
  return h->heap[0];
}

/*
 * Pop removes and returns the minimum element (according to Less) from the
 * heap. Pop is equivalent to heap_remove(h, 0).
 *
 * The complexity is O(log n) where n = sizeof(h->heap).
 */
protected mixed heap_pop(struct Heap h) {
  int n = sizeof(h->heap) - 1;
  heap_swap(h, 0, n);
  heap_down(h, 0, n);
  int element = h->heap[n];
  h->heap = h->heap[0 .. n - 1];
  return element;
}

// element swap
private void heap_swap(struct Heap h, int i, int j) {
  mixed temp = h->heap[i];
  h->heap[i] = h->heap[j];
  h->heap[j] = temp;
}

// upheap
private void heap_up(struct Heap h, int j) {
  do {
    int i = (j - 1) / 2; // parent
    if(i == j || !funcall(h->less, h->heap[j], h->heap[i])) {
      break;
    }
    heap_swap(h, i, j);
    j = i;
  } while(1);
}

// downheap
private int heap_down(struct Heap h, int i0, int n) {
  int i = i0;
  do {
    int j1 = 2 * i + 1;
    if(j1 >= n || j1 < 0) { // j1 < 0 after overflow
      break;
    }

    int j = j1; // left child
    int j2 = j1 + 1;
    if(j2 < n && funcall(h->less, h->heap[j2], h->heap[j1])) {
      j = j2; // = 2*i +2 // right child
    }
    if(!funcall(h->less, h->heap[j], h->heap[i])) {
      break;
    }
    heap_swap(h, i, j);
    i = j;
  } while(1);
  return i > i0;
}

heap_test.c

/*
 * LPC Heap Usage Example
 * Paradox@DUNE
 *
 * A quick demo showing a min/max heap for integers and a min heap for objects
 * based on idle time.
 *
 * Changelog:
 *   - 2021-10-08 Initial code.
 */
#pragma strict_types, rtt_checks, pedantic, no_clone, no_inherit

inherit __PATH__(0)"heap";

#if !__EFUN_DEFINED__(query_idle)
#include <sys/interactive_info.h>
private int query_idle(object o) {
  return (int) interactive_info(o, II_IDLE);
}
#endif

/*
 * Print an in-order heap traversal, emptying the provided heap.
 */
private void print_heap(struct Heap h, string min_label, closure printer) {
  printf("%s: %s\n", min_label, funcall(printer, heap_peek(h)));
  while (sizeof(h->heap)) {
    printf("%s ", funcall(printer, heap_pop(h)));
  }
  write("\n");
}

/*
 * Invoking main() should print something like:
 *   Initial list: 2 1 5
 *   Adding 3
 *   Min: 1
 *   1 2 3 5
 *
 *   Initial list: 2 1 5
 *   Adding 3
 *   Removed index 2 (5)
 *   Max: 3
 *   3 2 1
 *
 *   Least idle: :   Paradox - 0
 *
 *       Paradox - 0
 *       Badmother - 0
 *       Gilmau - 6
 *       Tegensis - 16
 *       Gaius - 2764
 *       Bebop - 5766
 *       Kuebiko - 7300
 *       Taze - 12748
 *       Bubbs - 14548
 *       Arfang - 15856
 *       Skimpy - 35716
 *       Sand - 35750
 *       Rawlin - 36014
 */
public void main() {
  // Some initial ints.
  int *initial = ({ 2, 1, 5 });
  printf("Initial list: %s\n", implode(map(initial, #'to_string), " "));

  /*
   * Construct a "min heap" of integers where the top of the heap is the
   * smallest element.
   */
  struct Heap min_heap = new_heap(copy(initial), (: $1 < $2 :));
  // Add another element
  write("Adding 3\n");
  heap_push(min_heap, 3);
  // Print the min, and then empty the heap in order.
  print_heap(min_heap, "Min: ", #'to_string);
  write("\n");

  /*
   * Now construct a "max heap" of integers where the top of the heap is the
   * largest element.
   */
  printf("Initial list: %s\n", implode(map(initial, #'to_string), " "));
  struct Heap max_heap = new_heap(copy(initial), (: $1 > $2 :));
  write("Adding 3\n");
  // Add another element
  heap_push(max_heap, 3);
  // Remove an element
  int removed = (int) heap_remove(max_heap, 2);
  printf("Removed index 2 (%d)\n", removed);
  // Print the max, and then empty the heap in order.
  print_heap(max_heap, "Max: ", #'to_string);
  write("\n");

  /*
   * Construct a "min heap" of users, ordered by idle time, where the top of the
   * heap is the least idle user.
   */
  struct Heap active_users = new_heap(users(), (: query_idle($1) < query_idle($2) :));
  // Print the least idle, and then empty the heap in order.
  print_heap(active_users, "Least idle: ", (: 
    sprintf("\t%s - %d\n", $1->query_name(), query_idle($1)) :));
}