eheap.c File Reference

#include <stdlib.h>
#include "gts.h"

Include dependency graph for eheap.c:

Go to the source code of this file.

Defines
#define	PARENT(i)   ((i) >= 2 ? (i)/2 : 0)
#define	LEFT_CHILD(i)   (2*(i))
#define	RIGHT_CHILD(i)   (2*(i) + 1)
Functions
GtsEHeap *	gts_eheap_new (GtsKeyFunc key_func, gpointer data)
static void	sift_up (GtsEHeap *heap, guint i)
GtsEHeapPair *	gts_eheap_insert (GtsEHeap *heap, gpointer p)
GtsEHeapPair *	gts_eheap_insert_with_key (GtsEHeap *heap, gpointer p, gdouble key)
static void	sift_down (GtsEHeap *heap, guint i)
gpointer	gts_eheap_remove_top (GtsEHeap *heap, gdouble *key)
gpointer	gts_eheap_top (GtsEHeap *heap, gdouble *key)
void	gts_eheap_destroy (GtsEHeap *heap)
void	gts_eheap_thaw (GtsEHeap *heap)
void	gts_eheap_foreach (GtsEHeap *heap, GFunc func, gpointer data)
gpointer	gts_eheap_remove (GtsEHeap *heap, GtsEHeapPair *p)
void	gts_eheap_decrease_key (GtsEHeap *heap, GtsEHeapPair *p, gdouble new_key)
void	gts_eheap_freeze (GtsEHeap *heap)
guint	gts_eheap_size (GtsEHeap *heap)
void	gts_eheap_update (GtsEHeap *heap)
gdouble	gts_eheap_key (GtsEHeap *heap, gpointer p)
void	gts_eheap_randomized (GtsEHeap *heap, gboolean randomized)

---

Define Documentation

#define LEFT_CHILD

(

i

)

(2*(i))

Definition at line 24 of file eheap.c.

Referenced by sift_down().

#define PARENT

(

i

)

((i) >= 2 ? (i)/2 : 0)

Definition at line 23 of file eheap.c.

Referenced by gts_eheap_remove(), and sift_up().

#define RIGHT_CHILD

(

i

)

(2*(i) + 1)

Definition at line 25 of file eheap.c.

Referenced by sift_down().

---

Function Documentation

void gts_eheap_decrease_key	(	GtsEHeap *	heap,
		GtsEHeapPair *	p,
		gdouble	new_key
	)

gts_eheap_decrease_key: : a GtsEHeap. : a GtsEHeapPair. : the new value of the key for this element. Must be smaller than the current key.

Decreases the value of the key of the element at position .

Definition at line 357 of file eheap.c.

References _GtsEHeap::elts, _GtsEHeap::frozen, _GtsEHeapPair::key, _GtsEHeapPair::pos, and sift_up().

Referenced by decrease_key().

Here is the call graph for this function:

void gts_eheap_destroy

(

GtsEHeap *

heap

)

gts_eheap_destroy: : a GtsEHeap.

Free all the memory allocated for .

Definition at line 252 of file eheap.c.

References _GtsEHeap::elts, and TRUE.

Referenced by gts_delaunay_refine(), gts_graph_bfgg_bisection(), gts_graph_bisection_bkl_refine(), gts_graph_bisection_kl_refine(), gts_graph_ggg_bisection(), gts_psurface_new(), gts_surface_coarsen(), gts_surface_refine(), heap_destroy(), hsurface_destroy(), and route().

void gts_eheap_foreach	(	GtsEHeap *	heap,
		GFunc	func,
		gpointer	data
	)

gts_eheap_foreach: : a GtsEHeap. : the function to call for each element in the heap. : to pass to .

Definition at line 292 of file eheap.c.

References _GtsEHeap::elts.

Referenced by gts_delaunay_refine(), gts_graph_bisection_kl_refine(), gts_psurface_new(), gts_surface_coarsen(), heap_new(), and route().

void gts_eheap_freeze

(

GtsEHeap *

heap

)

gts_eheap_freeze: : a GtsEHeap.

Freezes the heap. Any subsequent operation will not preserve the heap property. Used in conjunction with gts_eheap_insert() and gts_eheap_thaw() to create a heap in O(n) time.

Definition at line 385 of file eheap.c.

References _GtsEHeap::frozen, and TRUE.

Referenced by gts_graph_bfgg_bisection(), gts_graph_bisection_bkl_refine(), gts_graph_bisection_kl_refine(), gts_graph_ggg_bisection(), gts_psurface_new(), gts_surface_coarsen(), and gts_surface_refine().

GtsEHeapPair* gts_eheap_insert	(	GtsEHeap *	heap,
		gpointer	p
	)

gts_eheap_insert: : a GtsEHeap. : a pointer to add to the heap.

Inserts a new element in the heap.

Returns: a GtsEHeapPair describing the position of the element in the heap. This pointer is necessary for gts_eheap_remove() and gts_eheap_decrease_key().

Definition at line 84 of file eheap.c.

References _GtsEHeap::data, _GtsEHeapPair::data, _GtsEHeap::elts, _GtsEHeap::frozen, _GtsEHeap::func, _GtsEHeapPair::key, _GtsEHeapPair::pos, and sift_up().

Referenced by add_neighbor(), add_seed(), build_bheap(), build_heap(), create_heap_refine(), gts_graph_bisection_kl_refine(), insert_entry_into_heap(), midvertex_insertion(), route(), and update_neighbors().

Here is the call graph for this function:

GtsEHeapPair* gts_eheap_insert_with_key	(	GtsEHeap *	heap,
		gpointer	p,
		gdouble	key
	)

gts_eheap_insert_with_key: : a GtsEHeap. : a pointer to add to the heap. : the value of the key associated to .

Inserts a new element in the heap.

Returns: a GtsEHeapPair describing the position of the element in the heap. This pointer is necessary for gts_eheap_remove() and gts_eheap_decrease_key().

Definition at line 115 of file eheap.c.

References _GtsEHeapPair::data, _GtsEHeap::elts, _GtsEHeap::frozen, _GtsEHeapPair::key, _GtsEHeapPair::pos, and sift_up().

Referenced by edge_collapse(), heap_surface_add_face(), and make_face_heap().

Here is the call graph for this function:

gdouble gts_eheap_key	(	GtsEHeap *	heap,
		gpointer	p
	)

gts_eheap_key: : a GtsEHeap. : a pointer to be tested;

Returns: the value of the key for pointer .

Definition at line 443 of file eheap.c.

References _GtsEHeap::data, and _GtsEHeap::func.

Referenced by heap_surface_add_face(), and make_face_heap().

GtsEHeap* gts_eheap_new	(	GtsKeyFunc	key_func,
		gpointer	data
	)

gts_eheap_new: : a GtsKeyFunc or NULL. : user data to be passed to .

Returns: a new GtsEHeap using as key.

Definition at line 35 of file eheap.c.

References _GtsEHeap::data, _GtsEHeap::elts, FALSE, _GtsEHeap::frozen, _GtsEHeap::func, and _GtsEHeap::randomized.

Referenced by gts_delaunay_refine(), gts_graph_bfgg_bisection(), gts_graph_bisection_bkl_refine(), gts_graph_bisection_kl_refine(), gts_graph_ggg_bisection(), gts_hsurface_new(), gts_psurface_new(), gts_surface_coarsen(), gts_surface_refine(), heap_new(), and route().

void gts_eheap_randomized	(	GtsEHeap *	heap,
		gboolean	randomized
	)

gts_eheap_randomized: : a GtsEHeap. : whether should be randomized.

Definition at line 456 of file eheap.c.

References _GtsEHeap::randomized.

gpointer gts_eheap_remove	(	GtsEHeap *	heap,
		GtsEHeapPair *	p
	)

gts_eheap_remove: : a GtsEHeap. : a GtsEHeapPair.

Removes element corresponding to from in O(log n).

Returns: the element just removed from .

Definition at line 316 of file eheap.c.

References _GtsEHeapPair::data, _GtsEHeap::elts, gts_eheap_remove_top(), PARENT, and _GtsEHeapPair::pos.

Referenced by add_neighbor(), gts_graph_bisection_kl_refine(), heap_remove(), heap_surface_remove_face(), and update_neighbors().

Here is the call graph for this function:

gpointer gts_eheap_remove_top	(	GtsEHeap *	heap,
		gdouble *	key
	)

gts_eheap_remove_top: : a GtsEHeap. : a pointer on a gdouble or NULL.

Removes the element at the top of the heap and optionally (if is not NULL) returns the value of its key.

Returns: the element at the top of the heap.

Definition at line 185 of file eheap.c.

References _GtsEHeapPair::data, _GtsEHeap::elts, _GtsEHeapPair::key, len, _GtsEHeapPair::pos, and sift_down().

Referenced by gts_delaunay_refine(), gts_eheap_remove(), gts_graph_bfgg_bisection(), gts_graph_bisection_bkl_refine(), gts_graph_bisection_kl_refine(), gts_graph_ggg_bisection(), gts_psurface_new(), gts_surface_coarsen(), gts_surface_refine(), and route().

Here is the call graph for this function:

guint gts_eheap_size

(

GtsEHeap *

heap

)

gts_eheap_size: : a GtsEHeap.

Returns: the number of items in .

Definition at line 398 of file eheap.c.

References _GtsEHeap::elts.

Referenced by gts_delaunay_refine(), gts_psurface_new(), gts_surface_coarsen(), gts_surface_refine(), heap_is_empty(), and route().

void gts_eheap_thaw

(

GtsEHeap *

heap

)

gts_eheap_thaw: : a GtsEHeap.

If has been frozen previously using gts_eheap_freeze(), reorder it in O(n) time and unfreeze it.

Definition at line 271 of file eheap.c.

References _GtsEHeap::elts, FALSE, _GtsEHeap::frozen, and sift_down().

Referenced by gts_eheap_update(), gts_graph_bfgg_bisection(), gts_graph_bisection_bkl_refine(), gts_graph_bisection_kl_refine(), gts_graph_ggg_bisection(), gts_psurface_new(), gts_surface_coarsen(), and gts_surface_refine().

Here is the call graph for this function:

gpointer gts_eheap_top	(	GtsEHeap *	heap,
		gdouble *	key
	)

gts_eheap_top: : a GtsEHeap. : a pointer on a gdouble or NULL.

Returns: the element at the top of the heap and optionally (if is not NULL) its key.

Definition at line 228 of file eheap.c.

References _GtsEHeapPair::data, _GtsEHeap::elts, and _GtsEHeapPair::key.

Referenced by gts_hsurface_foreach(), and heap_top().

void gts_eheap_update

(

GtsEHeap *

heap

)

gts_eheap_update: : a GtsEHeap.

Updates the key of each element of and reorders it.

Definition at line 411 of file eheap.c.

References _GtsEHeapPair::data, _GtsEHeap::data, _GtsEHeap::elts, _GtsEHeap::frozen, _GtsEHeap::func, gts_eheap_thaw(), _GtsEHeapPair::key, len, and TRUE.

Referenced by route().

Here is the call graph for this function:

static void sift_down	(	GtsEHeap *	heap,
		guint	i
	)		[static]

Definition at line 135 of file eheap.c.

References c, _GtsEHeap::elts, _GtsEHeapPair::key, LEFT_CHILD, len, _GtsEHeapPair::pos, and RIGHT_CHILD.

Referenced by gts_eheap_remove_top(), and gts_eheap_thaw().

static void sift_up	(	GtsEHeap *	heap,
		guint	i
	)		[static]

Definition at line 49 of file eheap.c.

References _GtsEHeap::elts, _GtsEHeapPair::key, PARENT, _GtsEHeapPair::pos, and _GtsEHeap::randomized.

Referenced by gts_eheap_decrease_key(), gts_eheap_insert(), and gts_eheap_insert_with_key().