I have implemented a simple array-based priority queue for glib.  I
submit it for your consideration for incorporation into future versions
of glib.

I know that there are problems with this first version, please let me
know.  In particular, I believe that the documentation is supposed to
be embedded in the code somehow, but I'm not clear how this is done.

In the absence of any explanation to the contrary, I'm just going to paste
the diffs into this browser window:

The three new files are located below the diffs:


? docs/reference/glib/tmpl/priority_queues.sgml
? glib/gpriq.c
? glib/gpriq.h
Index: ChangeLog
===================================================================
RCS file: /cvs/gnome/glib/ChangeLog,v
retrieving revision 1.1286
diff -u -r1.1286 ChangeLog
--- ChangeLog	26 Feb 2003 00:12:41 -0000	1.1286
+++ ChangeLog	26 Feb 2003 00:50:57 -0000
@@ -1,3 +1,15 @@
+2003-02-26  Robert Graham Merkel  <rgmerk@mira.net>
+
+	* glib/gpriq.{ch}: new files implementing a simple priority 
+	queue for glib.
+
+	* glib/glib.h: include gpriq.h
+
+	* glib/Makefile.am: build gpriq.o
+
+	* glib/docs/reference/glib/tmpl/priority_queues.sgml: documentation
+	for the priority queue.
+
 2003-02-26  Matthias Clasen  <maclas@gmx.de>
 
 	* glib/gstrfuncs.c (g_strdup_vprintf): Use g_strndup, not
Index: docs/reference/glib/tmpl/glib-unused.sgml
===================================================================
RCS file: /cvs/gnome/glib/docs/reference/glib/tmpl/glib-unused.sgml,v
retrieving revision 1.34
diff -u -r1.34 glib-unused.sgml
--- docs/reference/glib/tmpl/glib-unused.sgml	26 May 2002 22:46:24 -0000	1.34
+++ docs/reference/glib/tmpl/glib-unused.sgml	26 Feb 2003 00:50:57 -0000
@@ -1,3 +1,49 @@
+<!-- ##### SECTION ./tmpl/priority_queues.sgml:Long_Description ##### -->
+<para>
+The #GPriq structure and its associated functions provide a collection
+of key/value pairs designed for insertion in any order and in-order 
+removal.  For these operations, it is faster than #GTree and has
+a simpler interface.
+</para>
+<para>
+To create a new #GPriq use g_priq_new().
+</para>
+<para>
+To insert a key/value pair into a #GPriq use g_priq_insert().
+</para>
+<para>
+To check the smallest entry. in a #GPriq, use g_priq_minimum(), or
g_priq_minimum_extended().
+To check it and remove it from the queue, use g_priq_remove() or
g_priq_remove_extended()
+</para>
+<para>
+To find out the number of items in a #GTree, use g_priq_nnodes().
+</para>
+<para>
+To traverse a #GPriq, calling a function for each node visited in the
+traversal, use g_tree_foreach().  You can either to a fast traversal (in 
+arbitrary order) or a (slower) in-order traversal.
+</para>
+<para>
+To destroy a #GPriq, use g_priq_destroy().
+</para>
+
+
+<!-- ##### SECTION ./tmpl/priority_queues.sgml:See_Also ##### -->
+<para>
+#GTree
+</para>
+
+
+<!-- ##### SECTION ./tmpl/priority_queues.sgml:Short_Description ##### -->
+A data structure optimized for inserting items in any order, 
+and removing them one by one in sorted order, from the smallest
+to the largest.
+
+
+<!-- ##### SECTION ./tmpl/priority_queues.sgml:Title ##### -->
+Priority Queues
+
+
 <!-- ##### ENUM GChannelError ##### -->
 <para>
 
@@ -100,6 +146,13 @@
 @G_MATCH_EXACT: a pattern matching exactly one string.
 @G_MATCH_LAST: 
 
+<!-- ##### STRUCT GPriq ##### -->
+<para>
+The <structname>GPriq</structname> struct is an opaque data structure
representing a
+min-priority queue. It should be accessed only by using the following
functions.
+</para>
+
+
 <!-- ##### USER_FUNCTION GWarningFunc ##### -->
 <para>
 Specifies the type of function passed to g_set_warning_handler().
@@ -277,6 +330,79 @@
 </para>
 
 @mem: the memory to check.
+
+<!-- ##### FUNCTION g_priq_destroy ##### -->
+<para>
+Destroy a #GPriq, freeing all memory allocated for it.  
+If key and/or value destructors were specified using g_priq_new_full()
+when the queue was created, those destructors will be called on each
+key and/or value respectively.  The items will not be destroyed in 
+an arbitrary order.  If not, the programmer is responsible
+for deallocating that memory, if required.
+</para>
+
+@priq: The the #Gpriq to be destroyed.
+
+<!-- ##### FUNCTION g_priq_foreach ##### -->
+<para>
+Apply a function to each key/value pair in a #GPriq.  This 
+can either be performed in arbitrary order (faster) or in
+order (slower and requires a temporary copy of the priority
+queue to be made internally).  
+</para>
+
+@priq: The #GPriq to traverse.
+@inorder: If TRUE, the traversal will be in-order.  If FALSE, it
+will be in arbitrary order.
+@traverse_func: the function to apply to each key-value pair
+@user_data: pointer to data to be supplied to each invocation of
traverse_func.
+
+<!-- ##### FUNCTION g_priq_insert ##### -->
+<para>
+Insert a new key/value pair into a #GPriq.
+</para>
+
+@priq: The #GPriq in which to insert the pair.
+@key: The key.
+@value: The corresponding data.
+
+<!-- ##### FUNCTION g_priq_new ##### -->
+<para>
+Create a new #GPriq.  
+</para>
+
+@key_compare_func: Key comparison function.
+@Returns: A pointer to the newly allocated #GPriq.
+
+<!-- ##### FUNCTION g_priq_new_full ##### -->
+<para>
+Create a new #Gpriq, not only with a comparison function that takes
user-supplied data,
+but with keys and/or values destroyed by a user-supplied function when
they are removed from the
+queue or the queue is destroyed.  
+</para>
+
+@key_compare_func: The key comparison function.
+@key_compare_data: data supplied to the key function each time it is called
+@key_destroy_func: a function to destroy keys
+@value_destroy_func: a function to destroy data items.
+@Returns: A pointer to the newly allocated #GPriq.
+
+<!-- ##### FUNCTION g_priq_new_with_data ##### -->
+<para>
+Create a new #Gpriq, with a comparison function that takes additional
user-supplied data.
+</para>
+
+@key_compare_func: key comparison function.
+@key_compare_data: data supplied to the key comparison function each time
that it is used.
+@Returns: A pointer to the newly allocated #GPriq.
+
+<!-- ##### FUNCTION g_priq_nnodes ##### -->
+<para>
+Count the number of entries in a #GPriq
+</para>
+
+@priq: The #GPriq to count the number of nodes in.
+@Returns: The number of nodes in the #GPriq.
 
 <!-- ##### FUNCTION g_scanner_stat_mode ##### -->
 <para>
Index: glib/Makefile.am
===================================================================
RCS file: /cvs/gnome/glib/glib/Makefile.am,v
retrieving revision 1.105
diff -u -r1.105 Makefile.am
--- glib/Makefile.am	14 Feb 2003 15:08:45 -0000	1.105
+++ glib/Makefile.am	26 Feb 2003 00:50:57 -0000
@@ -67,6 +67,7 @@
 	gnode.c			\
 	gpattern.c		\
 	gprimes.c		\
+	gpriq.c                 \
 	gqsort.c		\
 	gqueue.c		\
 	grel.c			\
@@ -133,6 +134,7 @@
 	gnode.h		\
 	gpattern.h	\
 	gprimes.h	\
+	gpriq.h         \
 	gqsort.h	\
 	gquark.h	\
 	gqueue.h	\
Index: glib/glib.h
===================================================================
RCS file: /cvs/gnome/glib/glib/glib.h,v
retrieving revision 1.218
diff -u -r1.218 glib.h
--- glib/glib.h	5 Nov 2001 01:47:31 -0000	1.218
+++ glib/glib.h	26 Feb 2003 00:50:57 -0000
@@ -51,6 +51,7 @@
 #include <glib/gnode.h>
 #include <glib/gpattern.h>
 #include <glib/gprimes.h>
+#include <glib/gpriq.h>
 #include <glib/gqsort.h>
 #include <glib/gquark.h>
 #include <glib/gqueue.h>

*********************************************************************
/* GLIB - Library of useful routines for C programming
 * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA.
 */

/*
 * Modified by the GLib Team and others 1997-2000.  See the AUTHORS
 * file for a list of people on the GLib Team.  See the ChangeLog
 * files for a list of changes.  These files are distributed with
 * GLib at ftp://ftp.gtk.org/pub/gtk/.
 */

#include <glib.h>


#define g_heaparray_index(h, i) g_array_index(h, HeapEntry, i)

typedef struct _HeapEntry HeapEntry;

struct _HeapEntry
{
  gpointer key;
  gpointer data;
};

struct _GPriq
{
  GCompareDataFunc key_compare;
  gboolean       key_compare_func_data_p;	/* if FALSE, key_compare is a
GCompareFunc */
  gpointer       key_comp_data;
  GDestroyNotify key_destroy; /* pointer to a function that destroys  keys */
  GDestroyNotify data_destroy; /* pointer to a function that destroys
destroy data */
  GArray        *heap;
};

static inline guint
parent (guint index)
{
  return index / 2;
}

static inline guint
left (guint index)
{
  return index * 2;
}

static inline guint
right (guint index)
{
  return (index * 2) + 1;
}

static inline gint
compare (GPriq * priq, const HeapEntry * a, const HeapEntry * b)
{
  if (priq->key_compare_func_data_p)
    {
      return (priq->key_compare) (a->key, b->key, priq->key_comp_data);
    }
  else
    {
      return ((GCompareFunc) (priq->key_compare)) (a->key, b->key);
    }
}

static inline void
upheap (GPriq * priq, guint index)
{
  HeapEntry he = g_heaparray_index (priq->heap, index);
  while (index > 1 &&
	 compare (priq, &(g_array_index (priq->heap,
					 HeapEntry,
					 parent (index))), &he) > 0)
    {
      g_heaparray_index (priq->heap, index)
	= g_heaparray_index (priq->heap, parent (index));

      index = parent (index);
    }

  g_heaparray_index (priq->heap, index) = he;
  return;
}

static inline void
downheap (GPriq * priq, guint index)
{
  guint child;
  HeapEntry he = g_heaparray_index (priq->heap, index);
  while (index <= (priq->heap->len - 1) / 2)
    {

      if (left (index) < (priq->heap->len - 1)
	  && (compare (priq,
		       &(g_heaparray_index (priq->heap, left (index))),
		       &(g_heaparray_index (priq->heap, right (index)))) > 0))
	{
	  child = right (index);
	}
      else
	{
	  child = left (index);
	}

      if (compare (priq, &he, &(g_heaparray_index (priq->heap, child))) <= 0)
	{
	  break;
	}

      g_heaparray_index (priq->heap, index)
	= g_heaparray_index (priq->heap, child);

      index = child;
    }

  g_heaparray_index (priq->heap, index) = he;

  return;
}
static inline GPriq *
g_priq_new_full_real (GCompareDataFunc key_compare_func,
		      gboolean key_compare_func_has_data,
		      gpointer key_compare_data,
		      GDestroyNotify key_destroy_func,
		      GDestroyNotify data_destroy_func)
{
  HeapEntry he = { NULL, NULL };

  GPriq *priq;

  g_return_val_if_fail (key_compare_func != NULL, NULL);

  priq = g_new (GPriq, 1);
  priq->key_compare = key_compare_func;
  priq->key_compare_func_data_p = key_compare_func_has_data;
  priq->key_comp_data = key_compare_data;
  priq->key_destroy = key_destroy_func;
  priq->data_destroy = data_destroy_func;

  priq->heap = g_array_new (FALSE, FALSE, sizeof (HeapEntry));

  g_array_append_val (priq->heap, he);

  return priq;
}
static inline void
traverse_fast (GPriq * priq, GTraverseFunc traverse_func, gpointer user_data)
{
  int i;
  HeapEntry *he;

  for (i = 1; i < priq->heap->len; i++)
    {
      he = &g_heaparray_index (priq->heap, i);
      if (traverse_func (he->key, he->data, user_data))
	{
	  break;
	}
    }

  return;
}

/*
 * creating a quickie heap for doing an inorder traversal 
 * no copying of data, so we don't want to destroy it on
 * g_priq_remove
 */

static inline GPriq *
duplicate_no_destructors (GPriq * priq)
{
  int i;
  GPriq *dup = g_new (GPriq, 1);

  dup->key_compare = priq->key_compare;
  dup->key_comp_data = priq->key_comp_data;
  dup->key_compare_func_data_p = priq->key_compare_func_data_p;
  dup->key_destroy = NULL;
  dup->data_destroy = NULL;
  dup->heap = g_array_sized_new (FALSE,
				 FALSE, sizeof (HeapEntry), priq->heap->len);
  for (i = 0; i < priq->heap->len; i++)
    {
      g_array_append_val (dup->heap, g_heaparray_index (priq->heap, i));
    }

  return dup;
}

static inline void
traverse_inorder (GPriq * priq,
		  GTraverseFunc traverse_func, gpointer user_data)
{
  int i;
  gpointer key, data;

  GPriq *copy = duplicate_no_destructors (priq);


  for (i = g_priq_nnodes (copy); i > 0; i--)
    {
      g_priq_remove_extended (copy, &key, &data);

      if (traverse_func (key, data, user_data))
	{
	  break;
	}

    }

  g_priq_destroy (copy);
}

GPriq *
g_priq_new (GCompareFunc key_compare_func)
{
  return g_priq_new_full_real ((GCompareDataFunc) key_compare_func, FALSE,
			       NULL, NULL, NULL);
}

GPriq *
g_priq_new_with_data (GCompareDataFunc key_compare_func,
		      gpointer key_compare_data)
{
  return g_priq_new_full_real (key_compare_func, TRUE, key_compare_data, NULL,
			       NULL);
}

GPriq *
g_priq_new_full (GCompareDataFunc key_compare_func,
		 gpointer key_compare_data,
		 GDestroyNotify key_destroy, GDestroyNotify data_destroy)
{
  return g_priq_new_full_real (key_compare_func,
			       TRUE,
			       key_compare_data, key_destroy, data_destroy);
}


gint
g_priq_nnodes (GPriq * priq)
{
  g_return_val_if_fail (priq, 0);
  return (priq->heap->len) - 1;
}

void
g_priq_destroy (GPriq * priq)
{
  int i;

  if (priq->key_destroy)
    {
      for (i = 1; i < priq->heap->len; i++)
	{
	  (priq->key_destroy) ((g_array_index (priq->heap, HeapEntry, i)).
			       key);
	}
    }

  if (priq->data_destroy)
    {
      for (i = 1; i < priq->heap->len; i++)
	{
	  (priq->data_destroy) ((g_array_index (priq->heap, HeapEntry, i)).
				data);
	}
    }

  g_array_free (priq->heap, FALSE);
  return;
}

gpointer
g_priq_minimum (GPriq * priq)
{
  g_return_val_if_fail (priq->heap->len > 1, NULL);
  return (g_heaparray_index (priq->heap, 1)).data;
}

void
g_priq_minimum_extended (GPriq * priq, gpointer * key, gpointer * value)
{
  *key = NULL;
  *value = NULL;
  g_return_if_fail (priq->heap->len > 1);
  HeapEntry *he = &(g_heaparray_index (priq->heap, 1));
  *key = he->key;
  *value = he->data;
  return;
}

void
g_priq_remove_extended (GPriq * priq, gpointer * key, gpointer * value)
{
  HeapEntry min;
  *key = NULL;
  *value = NULL;
  g_return_if_fail (priq->heap->len > 1);

  min = g_heaparray_index (priq->heap, 1);

  g_heaparray_index (priq->heap, 1)
    = g_heaparray_index (priq->heap, priq->heap->len - 1);

  g_array_remove_index (priq->heap, priq->heap->len - 1);

  downheap (priq, 1);

  *key = min.key;
  *value = min.data;
  return;
}

gpointer
g_priq_remove (GPriq * priq)
{
  gpointer key, data;

  g_priq_remove_extended (priq, &key, &data);

  if (priq->key_destroy)
    {
      (priq->key_destroy) (key);
    }

  return data;
}

void
g_priq_insert (GPriq * priq, gpointer key, gpointer data)
{

  HeapEntry he;

  he.key = key;
  he.data = data;

  g_return_if_fail (priq);

  g_array_append_val (priq->heap, he);
  upheap (priq, priq->heap->len - 1);
  return;
}



void
g_priq_foreach (GPriq * priq,
		gboolean inorder,
		GTraverseFunc traverse_func, gpointer user_data)
{
  g_return_if_fail (priq && traverse_func);
  if (inorder)
    {
      traverse_inorder (priq, traverse_func, user_data);
    }
  {
    traverse_fast (priq, traverse_func, user_data);
  }
  return;
}

**************************************************************

#ifndef __G_PRIQ_H__
#define __G_PRIQ_H__

#include <glib/gtypes.h>
#include <glib/gtree.h>

G_BEGIN_DECLS

typedef struct _GPriq GPriq;

GPriq *g_priq_new            (GCompareFunc key_compare_func);

GPriq *g_priq_new_with_data  (GCompareDataFunc key_compare_func,
			      gpointer key_compare_data);

GPriq *g_priq_new_full       (GCompareDataFunc key_compare_func,
			      gpointer key_compare_data,
			      GDestroyNotify key_destroy_func,
			      GDestroyNotify data_destroy_func);

gint g_priq_nnodes           (GPriq * priq);

void g_priq_destroy          (GPriq * priq);

void g_priq_insert           (GPriq * priq, 
			      gpointer key, 
			      gpointer value);

gpointer g_priq_minimum      (GPriq * priq);

void g_priq_minimum_extended (GPriq * priq, 
			      gpointer * key, 
			      gpointer * value);

gpointer g_priq_remove       (GPriq * priq);

void g_priq_remove_extended  (GPriq * priq, 
			      gpointer * key, 
			      gpointer * value);

void g_priq_foreach          (GPriq * priq,
			      gboolean inorder,
			      GTraverseFunc traverse_func, 
			      gpointer user_data);


G_END_DECLS

#endif /* __G_PRIQ_H__ */

**************************************************************
<!-- ##### SECTION Title ##### -->
Priority Queues

<!-- ##### SECTION Short_Description ##### -->
A data structure optimized for inserting items in any order, 
and removing them one by one in sorted order, from the smallest
to the largest.

<!-- ##### SECTION Long_Description ##### -->
<para>
The #GPriq structure and its associated functions provide a collection
of key/value pairs designed for insertion in any order and in-order 
removal.  For these operations, it is faster than #GTree and has
a simpler interface.
</para>
<para>
To create a new #GPriq use g_priq_new().
</para>
<para>
To insert a key/value pair into a #GPriq use g_priq_insert().
</para>
<para>
To check the smallest entry. in a #GPriq, use g_priq_minimum(), or
g_priq_minimum_extended().
To check it and remove it from the queue, use g_priq_remove() or
g_priq_remove_extended()
</para>
<para>
To find out the number of items in a #GTree, use g_priq_nnodes().
</para>
<para>
To traverse a #GPriq, calling a function for each node visited in the
traversal, use g_tree_foreach().  You can either to a fast traversal (in 
arbitrary order) or a (slower) in-order traversal.
</para>
<para>
To destroy a #GPriq, use g_priq_destroy().
</para>

<!-- ##### SECTION See_Also ##### -->
<para>
#GTree
</para>

<!-- ##### STRUCT GPriq ##### -->
<para>
The <structname>GPriq</structname> struct is an opaque data structure
representing a
min-priority queue. It should be accessed only by using the following
functions.
</para>


<!-- ##### FUNCTION g_priq_new ##### -->
<para>
Create a new #GPriq.  
</para>
@key_compare_func: Key comparison function.
@Returns: A pointer to the newly allocated #GPriq.


<!-- ##### FUNCTION g_priq_new_with_data ##### -->
<para>
Create a new #Gpriq, with a comparison function that takes additional
user-supplied data.
</para>

@key_compare_func: key comparison function.
@key_compare_data: data supplied to the key comparison function each time
that it is used.
@Returns: A pointer to the newly allocated #GPriq.


<!-- ##### FUNCTION g_priq_new_full ##### -->
<para>
Create a new #Gpriq, not only with a comparison function that takes
user-supplied data,
but with keys and/or values destroyed by a user-supplied function when they
are removed from the
queue or the queue is destroyed.  
</para>

@key_compare_func: The key comparison function.
@key_compare_data: data supplied to the key function each time it is called
@key_destroy_func: a function to destroy keys
@value_destroy_func: a function to destroy data items.
@Returns: A pointer to the newly allocated #GPriq.


<!-- ##### FUNCTION g_priq_insert ##### -->
<para>
Insert a new key/value pair into a #GPriq.
</para>

@priq: The #GPriq in which to insert the pair.
@key: The key.
@value: The corresponding data.

 
<!-- ##### FUNCTION g_priq_nnodes ##### -->
<para>
Count the number of entries in a #GPriq
</para>

@priq: The #GPriq to count the number of nodes in.
@Returns: The number of nodes in the #GPriq.



<!-- ##### FUNCTION g_tree_lookup_extended ##### -->


@tree: 
@lookup_key: 
@orig_key: 
@value: 
@Returns: 


<!-- ##### FUNCTION g_priq_foreach ##### -->
<para>
Apply a function to each key/value pair in a #GPriq.  This 
can either be performed in arbitrary order (faster) or in
order (slower and requires a temporary copy of the priority
queue to be made internally).  
</para>

@priq: The #GPriq to traverse.
@inorder: If TRUE, the traversal will be in-order.  If FALSE, it
will be in arbitrary order.
@traverse_func: the function to apply to each key-value pair
@user_data: pointer to data to be supplied to each invocation of traverse_func.


<!-- ##### FUNCTION g_tree_traverse ##### -->
<para>

</para>

@tree: 
@traverse_func: 
@traverse_type: 
@user_data: 


<!-- ##### USER_FUNCTION GTraverseFunc ##### -->
<para>
Specifies the type of function passed to g_tree_traverse().
It is passed the key and value of each node, together with
the @user_data parameter passed to g_tree_traverse().
If the function returns %TRUE, the traversal is stopped.
</para>

@key: a key of a #GTree node.
@value: the value corresponding to the key.
@data: user data passed to g_tree_traverse().
@Returns: %TRUE to stop the traversal.


<!-- ##### ENUM GTraverseType ##### -->
<para>
Specifies the type of traveral performed by g_tree_traverse(),
g_node_traverse() and g_node_find().
</para>

@G_IN_ORDER: vists a node's left child first, then the node itself, then its
  right child. This is the one to use if you want the output sorted according
  to the compare function.
@G_PRE_ORDER: visits a node, then its children.
@G_POST_ORDER: visits the node's children, then the node itself.
@G_LEVEL_ORDER: is not implemented for
  <link linkend="glib-Balanced-Binary-Trees">Balanced Binary Trees</link>.
  For <link linkend="glib-N-ary-Trees">N-ary Trees</link>, it vists the root
  node first, then its children, then its grandchildren, and so on. Note that
  this is less efficient than the other orders.

<!-- ##### FUNCTION g_tree_search ##### -->
<para>

</para>

@tree: 
@search_func: 
@user_data: 
@Returns: 


<!-- ##### FUNCTION g_tree_remove ##### -->
<para>

</para>

@tree: 
@key: 


<!-- ##### FUNCTION g_tree_steal ##### -->
<para>

</para>

@tree: 
@key: 


<!-- ##### FUNCTION g_priq_destroy ##### -->
<para>
Destroy a #GPriq, freeing all memory allocated for it.  
If key and/or value destructors were specified using g_priq_new_full()
when the queue was created, those destructors will be called on each
key and/or value respectively.  The items will not be destroyed in 
an arbitrary order.  If not, the programmer is responsible
for deallocating that memory, if required.
</para>

@priq: The the #Gpriq to be destroyed.