J
jacob navia
In computer science, a priority queue is an abstract data type which is
like a regular queue or stack data structure, but additionally, each
element is associated with a "priority".
Wikipedia
I have added this ADT to the containers library. I would like to discuss
with you the interface:
typedef struct _PQueue PQueue;
typedef struct tagPQueueInterface {
// Constructors
PQueue *(*Create)(size_t elementSize);
PQueue *(*CreateWithAllocator)(size_t elementSize,
ContainerMemoryManager *allocator);
// Returns the number of elements store
size_t (*Size)(PQueue *Q);
// Returns the number of bytes used
size_t (*Sizeof)(PQueue *Q);
// Adds a new element to the queue
int (*Push)(PQueue *Q,intptr_t key,void *Element);
// Erases all elements without erasing the queue
int (*Clear)(PQueue *Q);
// Destroys the queue
int (*Finalize)(PQueue *Q);
// Retrieves the element with the lowest priority
// and eliminates it from the queue. Returns the
// priority of the deleted element and its data in
// the "result" pointer
intptr_t (*Pop)(PQueue *Q,void *result);
// Retrieves the element with the lowest priority
// without erasing it from the queue
intptr_t (*Front)(PQueue *Q,void *result);
} PQueueInterface;
Note that this container doesn't have iterators, searching utility, and
other similar features. I thought that the interface should be kept to a
minimum, but I do not know if this is too small.
The type "intptr_t" is used for the key. This has several reasons:
1) Floating point comparisons are problematical
2) This type is the "bitness" of the underlying system: 32 bits in 32
bits systems, 64 bits in 64 bit systems.
3) Comparing elements of this type is very cheap.
The heap used to implement this container in the sample implementation
is the fibonacci heap.
jacob
like a regular queue or stack data structure, but additionally, each
element is associated with a "priority".
Wikipedia
I have added this ADT to the containers library. I would like to discuss
with you the interface:
typedef struct _PQueue PQueue;
typedef struct tagPQueueInterface {
// Constructors
PQueue *(*Create)(size_t elementSize);
PQueue *(*CreateWithAllocator)(size_t elementSize,
ContainerMemoryManager *allocator);
// Returns the number of elements store
size_t (*Size)(PQueue *Q);
// Returns the number of bytes used
size_t (*Sizeof)(PQueue *Q);
// Adds a new element to the queue
int (*Push)(PQueue *Q,intptr_t key,void *Element);
// Erases all elements without erasing the queue
int (*Clear)(PQueue *Q);
// Destroys the queue
int (*Finalize)(PQueue *Q);
// Retrieves the element with the lowest priority
// and eliminates it from the queue. Returns the
// priority of the deleted element and its data in
// the "result" pointer
intptr_t (*Pop)(PQueue *Q,void *result);
// Retrieves the element with the lowest priority
// without erasing it from the queue
intptr_t (*Front)(PQueue *Q,void *result);
} PQueueInterface;
Note that this container doesn't have iterators, searching utility, and
other similar features. I thought that the interface should be kept to a
minimum, but I do not know if this is too small.
The type "intptr_t" is used for the key. This has several reasons:
1) Floating point comparisons are problematical
2) This type is the "bitness" of the underlying system: 32 bits in 32
bits systems, 64 bits in 64 bit systems.
3) Comparing elements of this type is very cheap.
The heap used to implement this container in the sample implementation
is the fibonacci heap.
jacob