algos.h File Reference

Generic algorithms on the Queue ADT. More...

#include <stdbool.h>
#include "queue.h"

Go to the source code of this file.

Functions
Queue *	merge_queues (Queue *queue1, Queue *queue2, size_t elem_sz, bool(*compare)(void const *, void const *))
	Stable-merges two queues.

Detailed Description

Generic algorithms on the Queue ADT.

Author

KriztoferY (https://github.com/KriztoferY)

Version

0.1.0

Copyright

Copyright (c) 2023 KriztoferY. All rights reserved.

All algorithms are independent of the implementation of the Queue ADT.

Function Documentation

merge_queues()

Queue * merge_queues	(	Queue *	queue1,
		Queue *	queue2,
		size_t	elem_sz,
		bool(*)(void const *, void const *)	compare
	)

Stable-merges two queues.

Elements are compared using the binary predicate compare to determine the order in which they appear in the merged queue. Relative order of elements in the original queues are preserved. A new queue is created and returned if both queues to merge are not empty.

Parameters

[in]	queue1	A queue to merge.
[in]	queue2	Another queue to merge.
[in]	elem_sz	Size of each queue elements in bytes. [IMPORTANT] It's the caller's responsibility to ensure elem_sz is a proper positive integer.
[in]	compare	A binary predicate that determines the element order in the merged queue; it has not effect on the relative order of elements in the original queues.

Returns

The merged queue if both queues to merge are not empty, one of the queues to merge if the other is empty, NULL if both are empty. [IMPORTANT] In the first case, call Queue_destroy() when you're done with the merged queue to free the memory allocated to it.

Note

The complexity of the merge algorithm is O(n1 + n2) in both time and space, where n1 and n2 are the sizes of the two queues to merge.