Woolz Image Processing  Version 1.8.3
AlcCPQueue.c File Reference

An \(O(1)\) priority queue based on algorithms from: Brown R, 1988. Calendar Queues: A Fast {O}(1)Priority Queue Implementation for the Simulation Event Set Problem. Communications of the ACM 31(10), 1220-1227. The priority queue has an \(O(1)\) time for insertion unlinking and holding of queue items with a favorable constant when compared to tree based priority queue data structures such as splay trees. Results presented by Brown show that this data structure outperforms tree based implementations and that simple ordered linked lists with \(O(n)\) operations outperform both calendar queues and tree based queues when there are less than ten items in the queue. More...

Functions

AlcCPQQueueAlcCPQQueueNew (AlcErrno *dstErr)
 Creates a new priority queue. More...
 
AlcCPQItemAlcCPQItemNew (AlcCPQQueue *q, float priority, void *entry, AlcErrno *dstErr)
 Creates a new priority queue item. More...
 
AlcErrno AlcCPQQueueFree (AlcCPQQueue *q)
 Frees a priority queue. Queue item entries are not freed. More...
 
void AlcCPQItemFree (AlcCPQQueue *q, AlcCPQItem *item)
 Frees a priority queue item by putting it onto the freeItem list. The queue items entries are not freed. More...
 
AlcErrno AlcCPQEntryInsert (AlcCPQQueue *q, float priority, void *entry)
 Inserts an entry into the priority queue. This function calls AlcCPQItemNew() followed by AlcCPQItemInsert(). More...
 
AlcErrno AlcCPQItemInsert (AlcCPQQueue *q, AlcCPQItem *item)
 Inserts an item into the priority queue. More...
 
AlcCPQItemAlcCPQItemUnlink (AlcCPQQueue *q)
 Unlinks and returns the item with the highest priority from the given priority queue. More...
 

Detailed Description

An \(O(1)\) priority queue based on algorithms from: Brown R, 1988. Calendar Queues: A Fast {O}(1)Priority Queue Implementation for the Simulation Event Set Problem. Communications of the ACM 31(10), 1220-1227. The priority queue has an \(O(1)\) time for insertion unlinking and holding of queue items with a favorable constant when compared to tree based priority queue data structures such as splay trees. Results presented by Brown show that this data structure outperforms tree based implementations and that simple ordered linked lists with \(O(n)\) operations outperform both calendar queues and tree based queues when there are less than ten items in the queue.

Author
Bill Hill
Date
July 2003
Version
Id
7e4dd63d577f4c14efd8fb7481edbab613cc3672
Address: MRC Human Genetics Unit, MRC Institute of Genetics and Molecular Medicine, University of Edinburgh, Western General Hospital, Edinburgh, EH4 2XU, UK.
Copyright (C), [2012], The University Court of the University of Edinburgh, Old College, Edinburgh, UK.

This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

This program 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 General Public License for more details.

You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.