00001 /* Part of the culibs project, <http://www.eideticdew.org/culibs/>. 00002 * Copyright (C) 2002--2009 Petter Urkedal <urkedal@nbi.dk> 00003 * 00004 * This program is free software: you can redistribute it and/or modify 00005 * it under the terms of the GNU General Public License as published by 00006 * the Free Software Foundation, either version 3 of the License, or 00007 * (at your option) any later version. 00008 * 00009 * This program is distributed in the hope that it will be useful, 00010 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00011 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00012 * GNU General Public License for more details. 00013 * 00014 * You should have received a copy of the GNU General Public License 00015 * along with this program. If not, see <http://www.gnu.org/licenses/>. 00016 */ 00017 00018 #ifndef CUCON_PRIQ_H 00019 #define CUCON_PRIQ_H 00020 00021 /** \defgroup cucon_priq_h cucon/priq.h: Array-Based Priority Queue 00022 ** @{ \ingroup cucon_misc_mod 00023 ** 00024 ** This is an implementation of priority queues based on a pyramid-like array. 00025 ** It guarantees that the front element \a x fulfils <tt>prior(x, y)</tt> for 00026 ** all other \c y in the queue. */ 00027 00028 #include <cucon/fwd.h> 00029 #include <cu/clos.h> 00030 #include <stdio.h> 00031 00032 CU_BEGIN_DECLARATIONS 00033 00034 /** The priority queue struct. */ 00035 struct cucon_priq 00036 { 00037 cu_clop(prior, cu_bool_t, void *, void *); 00038 size_t count; 00039 size_t capacity; 00040 void **arr; 00041 }; 00042 00043 /** Construct \a q as a priority queue of elements with priority relation \a 00044 ** prior. */ 00045 void cucon_priq_init(cucon_priq_t q, cu_clop(prior, cu_bool_t, void *, void *)); 00046 00047 /** Return a priority queue with the priority relation \a prior. */ 00048 cucon_priq_t cucon_priq_new(cu_clop(prior, cu_bool_t, void *, void *)); 00049 00050 /** Construct \a q as a copy of \a src. */ 00051 void cucon_priq_init_copy(cucon_priq_t q, cucon_priq_t src); 00052 00053 /** Return the prior-relation, as passed to \c cucon_priq_init. */ 00054 #define cucon_priq_prior(q) (CU_MARG(cucon_priq_t, q)->prior) 00055 00056 /** Enqueue \a key. */ 00057 void cucon_priq_insert(cucon_priq_t q, void *key); 00058 00059 /** Pop off and return the front element of the queue. */ 00060 void *cucon_priq_pop_front(cucon_priq_t q); 00061 00062 /** The front element of the queue. */ 00063 CU_SINLINE void *cucon_priq_front(cucon_priq_t q) { return q->arr[0]; } 00064 00065 /** True iff the queue is empty. */ 00066 CU_SINLINE cu_bool_t cucon_priq_is_empty(cucon_priq_t q) 00067 { return q->count == 0; } 00068 00069 /** Return the number of elements in the queue. */ 00070 CU_SINLINE size_t cucon_priq_count(cucon_priq_t q) { return q->count; } 00071 00072 /** Debug dump. */ 00073 void cucon_priq_dump(cucon_priq_t q, 00074 cu_clop(print_key_fn, void, void *key, FILE *out), 00075 FILE *out); 00076 00077 /** @} */ 00078 CU_END_DECLARATIONS 00079 00080 #endif