type_dequeue.h File Reference

Implementation of dequeues of unsigned integers. More...

#include <stdbool.h>
#include <stdio.h>
#include "type_basic.h"

Go to the source code of this file.

Classes
struct	dequeue
	Type used to represent a dequeue of unsigned integers. More...

Functions
dequeue *	create_dequeue (void)
	Creation of an empty dequeue.
void	delete_dequeue (dequeue *)
	Release of a dequeue.
uint	size_dequeue (dequeue *)
	Computes the size of a dequeue.
bool	isempty_dequeue (dequeue *)
	Tests whether a dequeue is empty.
void	makeempty_dequeue (dequeue *)
	Empties a dequeue.
void	lefins_dequeue (uint, dequeue *)
	Inserts a new value on the left of a dequeue.
void	rigins_dequeue (uint, dequeue *)
	Inserts a new value on the right of a dequeue.
uint	lefread_dequeue (dequeue *, uint)
	Read a value inside a dequeue without removing it (left-right version).
uint	rigread_dequeue (dequeue *, uint)
	Read a value inside a dequeue without removing it (right-left version).
uint	lefpull_dequeue (dequeue *)
	Removes the leftmost value of a dequeue.
uint	rigpull_dequeue (dequeue *)
	Removes the rightmost value of a dequeue.
void	copy_dequeue_right (dequeue *, dequeue *, uint)
	Copies all elements in a dequeue to the right of another dequeue. Shifts all values by an input number.
bool	mem_dequeue (uint, dequeue *)
	Tests if a value occurs inside a dequeue.
void	print_dequeue (dequeue *)
	Displays a dequeue on the standard output.
void	sort_dequeue_norepeat (dequeue *)
	Sorts a dequeue in increasing order and keeps only a single copy of each occuring value.
bool	mem_dequeue_sorted (uint, dequeue *, uint *)
	Tests if a value occurs inside a sorted dequeue with no repetition.
void	merge_sorted_dequeue (dequeue *, dequeue *)
	Merge of two sorted dequeues with no repetitions.
dequeue *	make_inter_sorted_dequeue (dequeue *, dequeue *)
	Intersection of two sorted dequeues with no repetitions.
dequeue *	make_inter_sorted_dequeue_array (dequeue *p, uint *arr, uint size)
bool	intersec_dequeue (dequeue *, dequeue *)
	Tests if two sorted dequeues with no repetitions have a nonempty intersection.
void	insert_dequeue (dequeue *, uint)
	Inserts a new value inside a sorted dequeue with no repetitions.
dequeue *	dequeue_to_indices (dequeue *, dequeue *)
	Takes two dequeues sorted in increasing order with no repetition as input such that the first one is a subset of the second one. Computes the list of indices at which elements of the first dequeue occur in the second one.
void	merge_array_sorted_dequeue (dequeue *, dequeue **, uint)
	Merges all dequeues in the array (all of them sorted with no repetitions) into a single dequeue (which is assumed to be empty).

Detailed Description

Implementation of dequeues of unsigned integers.

Function Documentation

copy_dequeue_right()

void copy_dequeue_right	(	dequeue *	incopy,
		dequeue *	tocopy,
		uint	lag )

Copies all elements in a dequeue to the right of another dequeue. Shifts all values by an input number.

Parameters

incopy	The dequeue inside which the values are copied.
tocopy	The dequeue being copied.
lag	The shift to apply.

create_dequeue()

dequeue * create_dequeue

(

void

)

Creation of an empty dequeue.

Returns

The dequeue.

delete_dequeue()

void delete_dequeue

(

dequeue *

p

)

Release of a dequeue.

Parameters

p	The dequeue.

dequeue_to_indices()

dequeue * dequeue_to_indices	(	dequeue *	main,
		dequeue *	sub )

Takes two dequeues sorted in increasing order with no repetition as input such that the first one is a subset of the second one. Computes the list of indices at which elements of the first dequeue occur in the second one.

Returns

The list of indices.

Parameters

main	The first dequeue (included in the second one).
sub	The second dequeue.

insert_dequeue()

void insert_dequeue	(	dequeue *	p1,
		uint	q )

Inserts a new value inside a sorted dequeue with no repetitions.

Returns

The dequeue remains sorted with no repetition.

Parameters

p1	The dequeue.
q	The value.

intersec_dequeue()

bool intersec_dequeue	(	dequeue *	p1,
		dequeue *	p2 )

Tests if two sorted dequeues with no repetitions have a nonempty intersection.

Returns

A Boolean indicating whether the two sorted dequeues with no repetitions have a nonempty intersection.

Parameters

p1	The first dequeue.
p2	The second dequeue.

isempty_dequeue()

bool isempty_dequeue

(

dequeue *

p

)

Tests whether a dequeue is empty.

Returns

. A Boolean indicating whether the dequeue is empty.

Parameters

p	The dequeue.

lefins_dequeue()

void lefins_dequeue	(	uint	val,
		dequeue *	p )

Inserts a new value on the left of a dequeue.

Parameters

val	The value.
p	The dequeue.

lefpull_dequeue()

uint lefpull_dequeue

(

dequeue *

p

)

Removes the leftmost value of a dequeue.

Returns

The removed value.

Parameters

p	The dequeue.

lefread_dequeue()

uint lefread_dequeue	(	dequeue *	p,
		uint	i )

Read a value inside a dequeue without removing it (left-right version).

Remarks

Values are indexed from left to right (the leftmost one has index 0).

Returns

The value.

Parameters

p	The dequeue.
i	The index of the value.

make_inter_sorted_dequeue()

dequeue * make_inter_sorted_dequeue	(	dequeue *	p1,
		dequeue *	p2 )

Intersection of two sorted dequeues with no repetitions.

Returns

A new sorted dequeue with no repetitions corresponding to the intersection.

Parameters

p1	The first dequeue.
p2	The second dequeue.

makeempty_dequeue()

void makeempty_dequeue

(

dequeue *

p

)

Empties a dequeue.

Parameters

p	The dequeue.

mem_dequeue()

bool mem_dequeue	(	uint	e,
		dequeue *	p )

Tests if a value occurs inside a dequeue.

Returns

A Boolean indicating whether the value occurs.

Parameters

e	The value.
p	The dequeue.

mem_dequeue_sorted()

bool mem_dequeue_sorted	(	uint	e,
		dequeue *	p,
		uint *	ind )

Tests if a value occurs inside a sorted dequeue with no repetition.

Returns

A Boolean indicating whether the value occurs.

Parameters

e	The value.
p	The dequeue.
ind	Returns the index at which the value occurs (from the left).

merge_array_sorted_dequeue()

void merge_array_sorted_dequeue	(	dequeue *	out,
		dequeue **	array,
		uint	size )

Merges all dequeues in the array (all of them sorted with no repetitions) into a single dequeue (which is assumed to be empty).

Parameters

out	The dequeue inside which the merge is done.
array	The array containing the dequques to merge
size	The size of the array.

merge_sorted_dequeue()

void merge_sorted_dequeue	(	dequeue *	p1,
		dequeue *	p2 )

Merge of two sorted dequeues with no repetitions.

Remarks

The first dequeue is modified: it contains the merge.

Attention

The merge is sorted with no repetition.

Parameters

p1	The first dequeue (modified)
p2	The second dequeue.

print_dequeue()

void print_dequeue

(

dequeue *

p

)

Displays a dequeue on the standard output.

Parameters

p	The dequeue.

rigins_dequeue()

void rigins_dequeue	(	uint	val,
		dequeue *	p )

Inserts a new value on the right of a dequeue.

Parameters

val	The value.
p	The dequeue.

rigpull_dequeue()

uint rigpull_dequeue

(

dequeue *

p

)

Removes the rightmost value of a dequeue.

Returns

The removed value.

Parameters

p	The dequeue.

rigread_dequeue()

uint rigread_dequeue	(	dequeue *	p,
		uint	i )

Read a value inside a dequeue without removing it (right-left version).

Remarks

Values are indexed from right to left (the rightmost one has index 0).

Returns

The value.

Parameters

p	The dequeue.
i	The index of the value.

size_dequeue()

uint size_dequeue

(

dequeue *

p

)

Computes the size of a dequeue.

Returns

The size.

Parameters

p	The dequeue.

sort_dequeue_norepeat()

void sort_dequeue_norepeat

(

dequeue *

p

)

Sorts a dequeue in increasing order and keeps only a single copy of each occuring value.

Parameters

p	The dequeue.