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

/* APriorityQueue, fixed maximum size, minimal use of dynamic memory. */

/* As it stands, this priority queue implementation just stores data items
   of the type "example_data_item", which is defined in this file,
   and is only capable of holding a single integer. It is here as
   as example only. When you have defined your own data objects that
   are to be stored in the queue, delete the two lines below that say
   "typedef ... example_data_item", and in the following "#define" line,
   replace the name "example_data_item" with your own data object's type.
   Also delete the create_item function, which will be useless. This
   otherwise worthless section is only here so that an example will work.

   because priority queues need to know the priority of each item they hold,
   the data type must support a function "priority_of" which takes a pointer
   to the data type as its parameter and returns a float as its result. When
   you have your own "priority_of" function, remove the example one from below. */

typedef struct                                /* remove this */
{ int value; } example_data_item;

float priority_of(example_data_item *it)      /* replace this */
{ return ((float)(it->value)); }

#define item example_data_item                /* replace this */

item *create_item(int v)                      /* remove this */
{ item *x;
  x=(item *)malloc(sizeof(item));
  x->value=v;
  return (x); }

/* Sometimes you need to search an area of storage to see if it contains
   a data item that matches in some way another data item that you have.
   (for example, searching the closed set to see if a similar state is
   already there) The function "search_for" searches through the priority 
   queue looking for a data item similar to one you provide as a pattern. If
   one is found, it returns a pointer to that item; if none are found
   it returns NULL. To use search_for, you must define a function that
   tests two items to see if they are similar enough; the search_for
   function is called with 3 parameters: the priority queue, your is_similar
   function, and the item to be used as a pattern in the search. The
   is_similar function below illustrates how such a function could be
   written. For a use, see the example at the end. */

int is_similar(item *a, item *b)      /* remove or replace this */
{ int diff=a->value-b->value;
  if (diff<0) diff=-diff;
  if (diff<=1)
    return 1;
  else
    return 0; }

/*
   This kind of set is only suitable for storing structured data (defined
   using a "struct" definition in C) like the "example_data_item" above.
   Data items in the set are referred to through pointers.

   This implementation uses an array to store the data. This saves a lot on
   memory use and processor time if you have a reasonable idea of the maximum
   number of data items to be added.

   If you haven't got any idea of the maximum, use a "dpriorityqueue" instead.

   to create an aset, call "new_apriorityqueue" with the maximum capacity as a
   parameter; store the returned result in a variable of type "apriorityqueue *",
   and use it to refer to the set in all further calls.

   the only things you can do to a priorityqueue are add an item, remove the item
   that currently has the lowest priority, and find the total number of items held.
   All three functions refer to the set and the item through pointers.

   There is a small example below.

   When you have completely finished with an apriorityqueue, you should call
   "delete_apriorityqueue" to return its memory to the system, unless the whole
   program is about to terminate. */

typedef struct
{ int size, max;
  item **data; } apriorityqueue;

apriorityqueue *new_apriorityqueue(int max_number_of_entries)
{ apriorityqueue *a=(apriorityqueue *)malloc(sizeof(apriorityqueue));
  a->size=0;
  a->max=max_number_of_entries;
  a->data=(item **)malloc(a->max*sizeof(item *));
  return (a); }

void delete_apriorityqueue(apriorityqueue *a)
{ free((void *)a->data);
  free((void *)a); }

int is_apriorityqueue_full(apriorityqueue *a)
{ return (a->size>=a->max); }

int is_apriorityqueue_empty(apriorityqueue *a)
{ return (a->size<=0); }

int items_in_apriorityqueue(apriorityqueue *a)
{ return (a->size); }

void add_to_apriorityqueue(apriorityqueue *a, item *i)
{ int current;
  if (a->size>=a->max)
  { fprintf(stderr,"add_to_apriorityqueue() when full\n");
    exit(1); }
  a->data[a->size]=i;
  current=a->size;
  a->size+=1;
  while (current>0)
  { item *currentitem, *parentitem;
    int parent;
    parent=(current-1)/2;
    currentitem=a->data[current];
    parentitem=a->data[parent];
    if (priority_of(currentitem)>=priority_of(parentitem))
      break;
    a->data[current]=parentitem;
    a->data[parent]=currentitem;
    current=parent; } }

item *remove_from_apriorityqueue(apriorityqueue *a)
{ item *it;
  int current, left;
  if (a->size<=0)
  { fprintf(stderr,"remove_from_apriorityqueue() when empty\n");
    exit(1); }
  it=a->data[0];
  a->size-=1;
  a->data[0]=a->data[a->size];
  current=0;
  left=2*current+1;
  while (left<a->size)
  { int right, smallest;
    item *currentitem, *childitem, *smallestitem;
    right=left+1;
    currentitem=a->data[current];
    smallest=current;
    smallestitem=currentitem;
    childitem=a->data[left];
    if (priority_of(childitem)<priority_of(smallestitem))
    { smallestitem=childitem;
      smallest=left; }
    if (right<a->size)
    { childitem=a->data[right];
      if (priority_of(childitem)<priority_of(smallestitem))
      { smallestitem=childitem;
        smallest=right; } }
    if (smallest==current)
      break;
    a->data[current]=smallestitem;
    a->data[smallest]=currentitem;
    current=smallest;
    left=2*current+1; }
  return (it); }

typedef int comparer(item *, item *);

item *search_apriorityqueue_for(apriorityqueue *a, comparer *fn, item *pattern)
{ int i;
  for (i=0; i<a->size; i+=1)
    if (fn(a->data[i],pattern))
      return (a->data[i]);
  return NULL; }

/* the following "main" function is just to illustrate the use of an apriorityqueue.
   It should not be included in any useful programs. */

void main(void)
{ apriorityqueue *as=new_apriorityqueue(100);
  example_data_item *x, *y;

  x=create_item(17);
  printf("adding %d to priorityqueue\n", x->value);
  add_to_apriorityqueue(as,x);
  x=create_item(5);
  printf("adding %d to priorityqueue\n", x->value);
  add_to_apriorityqueue(as,x);
  x=create_item(6666666);
  printf("adding %d to priorityqueue\n", x->value);
  add_to_apriorityqueue(as,x);
  x=create_item(1);
  printf("adding %d to priorityqueue\n", x->value);
  add_to_apriorityqueue(as,x);
  x=create_item(54321);
  printf("adding %d to priorityqueue\n", x->value);
  add_to_apriorityqueue(as,x);
  x=create_item(8274);
  printf("adding %d to priorityqueue\n", x->value);
  add_to_apriorityqueue(as,x);

  y=create_item(6);
  printf("\nsearching for something similar to %d\n", y->value);
  x=search_apriorityqueue_for(as,is_similar,y);
  if (x==NULL)
    printf("  Nothing similar found\n\n");
  else
    printf("  Found %d, which is close enough\n\n", x->value);

  while (!is_apriorityqueue_empty(as))
  { printf("removing an item from the priorityqueue ");
    x=remove_from_apriorityqueue(as);
    printf("it was %d\n", x->value); }
  printf("The priorityqueue is now empty.\n");

  delete_apriorityqueue(as); }