abce5105e2 2007-09-01 drh: /* abce5105e2 2007-09-01 drh: ** Copyright (c) 2007 D. Richard Hipp abce5105e2 2007-09-01 drh: ** abce5105e2 2007-09-01 drh: ** This program is free software; you can redistribute it and/or abce5105e2 2007-09-01 drh: ** modify it under the terms of the GNU General Public abce5105e2 2007-09-01 drh: ** License version 2 as published by the Free Software Foundation. abce5105e2 2007-09-01 drh: ** abce5105e2 2007-09-01 drh: ** This program is distributed in the hope that it will be useful, abce5105e2 2007-09-01 drh: ** but WITHOUT ANY WARRANTY; without even the implied warranty of abce5105e2 2007-09-01 drh: ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU abce5105e2 2007-09-01 drh: ** General Public License for more details. abce5105e2 2007-09-01 drh: ** abce5105e2 2007-09-01 drh: ** You should have received a copy of the GNU General Public abce5105e2 2007-09-01 drh: ** License along with this library; if not, write to the abce5105e2 2007-09-01 drh: ** Free Software Foundation, Inc., 59 Temple Place - Suite 330, abce5105e2 2007-09-01 drh: ** Boston, MA 02111-1307, USA. abce5105e2 2007-09-01 drh: ** abce5105e2 2007-09-01 drh: ** Author contact information: abce5105e2 2007-09-01 drh: ** drh@hwaci.com abce5105e2 2007-09-01 drh: ** http://www.hwaci.com/drh/ abce5105e2 2007-09-01 drh: ** abce5105e2 2007-09-01 drh: ******************************************************************************* abce5105e2 2007-09-01 drh: ** abce5105e2 2007-09-01 drh: ** This file contains code used to implement a priority queue. abce5105e2 2007-09-01 drh: ** A priority queue is a list of items order by a floating point abce5105e2 2007-09-01 drh: ** value. We can insert integers with each integer tied to its abce5105e2 2007-09-01 drh: ** value then extract the integer with the smallest value. abce5105e2 2007-09-01 drh: ** abce5105e2 2007-09-01 drh: ** The way this queue is used, we never expect it to contain more abce5105e2 2007-09-01 drh: ** than 2 or 3 elements, so a simple array is sufficient as the abce5105e2 2007-09-01 drh: ** implementation. This could give worst case O(N) insert times, abce5105e2 2007-09-01 drh: ** but because of the nature of the problem we expect O(1) performance. abce5105e2 2007-09-01 drh: */ abce5105e2 2007-09-01 drh: #include "config.h" abce5105e2 2007-09-01 drh: #include "pqueue.h" abce5105e2 2007-09-01 drh: #include <assert.h> abce5105e2 2007-09-01 drh: abce5105e2 2007-09-01 drh: abce5105e2 2007-09-01 drh: #if INTERFACE abce5105e2 2007-09-01 drh: /* abce5105e2 2007-09-01 drh: ** An integer can appear in the bag at most once. abce5105e2 2007-09-01 drh: ** Integers must be positive. abce5105e2 2007-09-01 drh: */ abce5105e2 2007-09-01 drh: struct PQueue { abce5105e2 2007-09-01 drh: int cnt; /* Number of entries in the queue */ abce5105e2 2007-09-01 drh: int sz; /* Number of slots in a[] */ abce5105e2 2007-09-01 drh: struct QueueElement { abce5105e2 2007-09-01 drh: int id; /* ID of the element */ abce5105e2 2007-09-01 drh: double value; /* Value of element. Kept in ascending order */ abce5105e2 2007-09-01 drh: } *a; abce5105e2 2007-09-01 drh: }; abce5105e2 2007-09-01 drh: #endif abce5105e2 2007-09-01 drh: abce5105e2 2007-09-01 drh: /* abce5105e2 2007-09-01 drh: ** Initialize a PQueue structure abce5105e2 2007-09-01 drh: */ abce5105e2 2007-09-01 drh: void pqueue_init(PQueue *p){ abce5105e2 2007-09-01 drh: memset(p, 0, sizeof(*p)); abce5105e2 2007-09-01 drh: } abce5105e2 2007-09-01 drh: abce5105e2 2007-09-01 drh: /* abce5105e2 2007-09-01 drh: ** Destroy a PQueue. Delete all of its content. abce5105e2 2007-09-01 drh: */ abce5105e2 2007-09-01 drh: void pqueue_clear(PQueue *p){ abce5105e2 2007-09-01 drh: free(p->a); abce5105e2 2007-09-01 drh: pqueue_init(p); abce5105e2 2007-09-01 drh: } abce5105e2 2007-09-01 drh: abce5105e2 2007-09-01 drh: /* abce5105e2 2007-09-01 drh: ** Change the size of the queue so that it contains N slots abce5105e2 2007-09-01 drh: */ abce5105e2 2007-09-01 drh: static void pqueue_resize(PQueue *p, int N){ abce5105e2 2007-09-01 drh: p->a = realloc(p->a, sizeof(p->a[0])*N); abce5105e2 2007-09-01 drh: p->sz = N; abce5105e2 2007-09-01 drh: } abce5105e2 2007-09-01 drh: abce5105e2 2007-09-01 drh: /* abce5105e2 2007-09-01 drh: ** Insert element e into the queue. abce5105e2 2007-09-01 drh: */ abce5105e2 2007-09-01 drh: void pqueue_insert(PQueue *p, int e, double v){ abce5105e2 2007-09-01 drh: int i, j; abce5105e2 2007-09-01 drh: if( p->cnt+1>p->sz ){ abce5105e2 2007-09-01 drh: pqueue_resize(p, p->cnt+5); abce5105e2 2007-09-01 drh: } abce5105e2 2007-09-01 drh: for(i=0; i<p->cnt; i++){ abce5105e2 2007-09-01 drh: if( p->a[i].value>v ){ abce5105e2 2007-09-01 drh: for(j=p->cnt; j>i; j--){ abce5105e2 2007-09-01 drh: p->a[j] = p->a[j-1]; abce5105e2 2007-09-01 drh: } abce5105e2 2007-09-01 drh: break; abce5105e2 2007-09-01 drh: } abce5105e2 2007-09-01 drh: } abce5105e2 2007-09-01 drh: p->a[i].id = e; abce5105e2 2007-09-01 drh: p->a[i].value = v; abce5105e2 2007-09-01 drh: p->cnt++; abce5105e2 2007-09-01 drh: } abce5105e2 2007-09-01 drh: abce5105e2 2007-09-01 drh: /* abce5105e2 2007-09-01 drh: ** Extract the first element from the queue (the element with abce5105e2 2007-09-01 drh: ** the smallest value) and return its ID. Return 0 if the queue abce5105e2 2007-09-01 drh: ** is empty. abce5105e2 2007-09-01 drh: */ abce5105e2 2007-09-01 drh: int pqueue_extract(PQueue *p){ abce5105e2 2007-09-01 drh: int e, i; abce5105e2 2007-09-01 drh: if( p->cnt==0 ){ abce5105e2 2007-09-01 drh: return 0; abce5105e2 2007-09-01 drh: } abce5105e2 2007-09-01 drh: e = p->a[0].id; abce5105e2 2007-09-01 drh: for(i=0; i<p->cnt-1; i++){ abce5105e2 2007-09-01 drh: p->a[i] = p->a[i+1]; abce5105e2 2007-09-01 drh: } abce5105e2 2007-09-01 drh: p->cnt--; abce5105e2 2007-09-01 drh: return e; abce5105e2 2007-09-01 drh: }
File Annotation