C Standard Library Extensions  1.1.1
Functions
Double-ended queue.

Functions

cx_deque * cx_deque_new (void)
 Create a new deque without any elements. More...
 
void cx_deque_delete (cx_deque *deque)
 Destroy a deque. More...
 
void cx_deque_destroy (cx_deque *deque, cx_free_func deallocate)
 Destroy a deque and all its elements. More...
 
cxsize cx_deque_size (const cx_deque *deque)
 Get the actual number of deque elements. More...
 
cxbool cx_deque_empty (const cx_deque *deque)
 Check whether a deque is empty. More...
 
cxsize cx_deque_max_size (const cx_deque *deque)
 Get the maximum number of deque elements possible. More...
 
void cx_deque_swap (cx_deque *deque, cx_deque *other)
 Swap the data of two deques. More...
 
cxptr cx_deque_assign (cx_deque *deque, cx_deque_iterator position, cxptr data)
 Assign data to a deque element. More...
 
cxptr cx_deque_front (const cx_deque *deque)
 Get the first element of a deque. More...
 
cxptr cx_deque_back (const cx_deque *deque)
 Get the last element of a deque. More...
 
cxptr cx_deque_get (const cx_deque *deque, cx_deque_const_iterator position)
 Retrieve an element from a deque. More...
 
cx_deque_iterator cx_deque_begin (const cx_deque *deque)
 Get an iterator for the first deque element. More...
 
cx_deque_iterator cx_deque_end (const cx_deque *deque)
 Get an iterator for the position after the last deque element. More...
 
cx_deque_iterator cx_deque_next (const cx_deque *deque, cx_deque_const_iterator position)
 Get an iterator for the next deque element. More...
 
cx_deque_iterator cx_deque_previous (const cx_deque *deque, cx_deque_const_iterator position)
 Get an iterator for the previous deque element. More...
 
void cx_deque_push_front (cx_deque *deque, cxcptr data)
 Insert data at the beginning of a deque. More...
 
cxptr cx_deque_pop_front (cx_deque *deque)
 Remove the first deque element. More...
 
void cx_deque_push_back (cx_deque *deque, cxcptr data)
 Append data at the end of a deque. More...
 
cxptr cx_deque_pop_back (cx_deque *deque)
 Remove the last deque element. More...
 
cx_deque_iterator cx_deque_insert (cx_deque *deque, cx_deque_iterator position, cxcptr data)
 Insert data into a deque at a given iterator position. More...
 
cx_deque_iterator cx_deque_erase (cx_deque *deque, cx_deque_iterator position, cx_free_func deallocate)
 Erase a deque element. More...
 
void cx_deque_clear (cx_deque *deque)
 Remove all elements from a deque. More...
 
cxptr cx_deque_extract (cx_deque *deque, cx_deque_iterator position)
 Extract a deque element. More...
 
void cx_deque_remove (cx_deque *deque, cxcptr data)
 Remove all elements with a given value from a deque. More...
 
void cx_deque_unique (cx_deque *deque, cx_compare_func compare)
 Remove duplicates of consecutive elements. More...
 
void cx_deque_splice (cx_deque *deque, cx_deque_iterator position, cx_deque *other, cx_deque_iterator first, cx_deque_iterator last)
 Move a range of elements in front of a given position. More...
 
void cx_deque_merge (cx_deque *deque, cx_deque *other, cx_compare_func compare)
 Merge two sorted deques. More...
 
void cx_deque_sort (cx_deque *deque, cx_compare_func compare)
 Sort all elements of a deque using the given comparison function. More...
 
void cx_deque_reverse (cx_deque *deque)
 Reverse the order of all deque elements. More...
 

Detailed Description

The module implements a double-ended queue. This is a linear list which is optimized for insertions and deletions that are made at the ends of the list.

Synopsis:
#include <cxdeque.h>

Function Documentation

cxptr cx_deque_assign ( cx_deque *  deque,
cx_deque_iterator  position,
cxptr  data 
)

Assign data to a deque element.

Parameters
dequeA deque.
positionPosition of the deque element where the data will be stored.
dataData to store.
Returns
Handle to the previously stored data object.

The function assigns the data object reference data to the iterator position position of the deque deque.

cxptr cx_deque_back ( const cx_deque *  deque)

Get the last element of a deque.

Parameters
dequeThe deque to query.
Returns
Handle to the data object stored in the last deque element.

The function returns a reference to the last data item in the deque deque.

cx_deque_iterator cx_deque_begin ( const cx_deque *  deque)

Get an iterator for the first deque element.

Parameters
dequeA deque.
Returns
Iterator for the first element in the deque or cx_deque_end() if the deque is empty.

The function returns a handle to the first element of deque. The handle cannot be used directly to access the element data, but only through the appropriate functions.

void cx_deque_clear ( cx_deque *  deque)

Remove all elements from a deque.

Parameters
dequeDeque to be cleared.
Returns
Nothing.

The deque deque is cleared, i.e. all elements are removed from the deque. The removed data objects are left untouched, in particular they are not deallocated. It is the responsibility of the caller to ensure that there are still other references to the removed data objects. After calling cx_deque_clear() the deque deque is empty.

void cx_deque_delete ( cx_deque *  deque)

Destroy a deque.

Parameters
dequeThe deque to delete.
Returns
Nothing.

The function deallocates the deque object, but not the data objects currently stored in the deque.

References cx_deque_empty(), and cx_free().

void cx_deque_destroy ( cx_deque *  deque,
cx_free_func  deallocate 
)

Destroy a deque and all its elements.

Parameters
dequeDeque container to destroy.
deallocateData deallocator.
Returns
Nothing.

The function deallocates all data objects referenced by deque using the data deallocation function deallocate and finally deallocates the deque object itself.

References cx_free().

cxbool cx_deque_empty ( const cx_deque *  deque)

Check whether a deque is empty.

Parameters
dequeA deque.
Returns
The function returns TRUE if the deque is empty, and FALSE otherwise.

The function tests if the deque deque contains data.

Referenced by cx_deque_delete().

cx_deque_iterator cx_deque_end ( const cx_deque *  deque)

Get an iterator for the position after the last deque element.

Parameters
dequeA deque.
Returns
Iterator for the end of the deque.

The function returns an iterator for the position one past the last element of the deque deque. The handle cannot be used to directly access the element data, but only through the appropriate functions.

cx_deque_iterator cx_deque_erase ( cx_deque *  deque,
cx_deque_iterator  position,
cx_free_func  deallocate 
)

Erase a deque element.

Parameters
dequeThe deque to update.
positionDeque iterator position.
deallocateData deallocator.
Returns
The iterator for the deque position after position.

The function removes the data object stored at position position from the deque deque. The data object itself is deallocated by calling the data deallocator deallocate.

cxptr cx_deque_extract ( cx_deque *  deque,
cx_deque_iterator  position 
)

Extract a deque element.

Parameters
dequeA deque.
positionDeque iterator position.
Returns
Handle to the previously stored data object.

The function removes a data object from the deque deque located at the iterator position position without destroying the data object.

See Also
cx_deque_erase(), cx_deque_remove()
cxptr cx_deque_front ( const cx_deque *  deque)

Get the first element of a deque.

Parameters
dequeThe deque to query.
Returns
Handle to the data object stored in the first deque element.

The function returns a reference to the first data item in the deque deque.

cxptr cx_deque_get ( const cx_deque *  deque,
cx_deque_const_iterator  position 
)

Retrieve an element from a deque.

Parameters
dequeThe deque to query.
positionThe position of the element to get.
Returns
A handle to the data object.

The function returns a reference to the data item stored in the deque deque at the iterator position position.

cx_deque_iterator cx_deque_insert ( cx_deque *  deque,
cx_deque_iterator  position,
cxcptr  data 
)

Insert data into a deque at a given iterator position.

Parameters
dequeThe deque to update.
positionList iterator position.
dataData item to insert.
Returns
Deque iterator position of the inserted data item.

The function inserts the data object reference data into the deque deque at the position given by the deque iterator position.

References cx_deque_push_back().

cxsize cx_deque_max_size ( const cx_deque *  deque)

Get the maximum number of deque elements possible.

Parameters
dequeA deque.
Returns
The maximum number of elements that can be stored in the deque.

Retrieves the deques capacity, i.e. the maximum possible number of data items a deque can hold.

void cx_deque_merge ( cx_deque *  deque,
cx_deque *  other,
cx_compare_func  compare 
)

Merge two sorted deques.

Parameters
dequeTarget deque of the merge operation.
otherThe deque to merge into the target.
compareFunction comparing the deque elements.
Returns
Nothing.

The function combines the two deques deque and other by moving all elements from other into deque, so that all elements are still sorted. The function requires that both input deques are already sorted. The sorting order in which the elements of other are inserted into deque is determined by the comparison function compare. The comparison function compare must return an integer less than, equal or greater than zero if the first argument passed to it is found, respectively, to be less than, match, or be greater than the second argument.

The deque other is consumed by this process, i.e. after the successful merging of the two deques, deque other will be empty.

cx_deque* cx_deque_new ( void  )

Create a new deque without any elements.

Returns
Handle to the newly allocated deque.

The function allocates memory for a deque object and initializes it to an empty deque.

References cx_malloc().

cx_deque_iterator cx_deque_next ( const cx_deque *  deque,
cx_deque_const_iterator  position 
)

Get an iterator for the next deque element.

Parameters
dequeA deque.
positionCurrent iterator position.
Returns
Iterator for the next deque element.

The function returns an iterator for the next element in the deque deque with respect to the current iterator position position. If the deque deque is empty or position points to the deque end the function returns cx_deque_end().

cxptr cx_deque_pop_back ( cx_deque *  deque)

Remove the last deque element.

Parameters
dequeThe deque to update.
Returns
Handle to the data object previously stored as the last deque element.

The function removes the last element from the deque deque returning a handle to the previously stored data.

It is equivalent to the statement

cxptr cx_deque_pop_front ( cx_deque *  deque)

Remove the first deque element.

Parameters
dequeThe deque to update.
Returns
Handle to the data object previously stored as the first deque element.

The function removes the first element from the deque deque returning a handle to the previously stored data.

It is equivalent to the statement

cx_deque_iterator cx_deque_previous ( const cx_deque *  deque,
cx_deque_const_iterator  position 
)

Get an iterator for the previous deque element.

Parameters
dequeA deque.
positionCurrent iterator position.
Returns
Iterator for the previous deque element.

The function returns an iterator for the previous element in the deque deque with respect to the current iterator position position. If the deque deque is empty or position points to the beginning of the deque the function returns cx_deque_end().

void cx_deque_push_back ( cx_deque *  deque,
cxcptr  data 
)

Append data at the end of a deque.

Parameters
dequeThe deque to update.
dataData to append.
Returns
Nothing.

The data data is inserted into the deque deque after the last element, so that it becomes the new deque tail.

It is equivalent to the statement

cx_deque_insert(deque, cx_deque_end(deque), data);

Referenced by cx_deque_insert().

void cx_deque_push_front ( cx_deque *  deque,
cxcptr  data 
)

Insert data at the beginning of a deque.

Parameters
dequeThe deque to update.
dataData to add to the deque.
Returns
Nothing.

The data data is inserted into the deque deque before the first element of the deque, so that it becomes the new deque head.

It is equivalent to the statement

cx_deque_insert(deque, cx_deque_begin(deque), data);
void cx_deque_remove ( cx_deque *  deque,
cxcptr  data 
)

Remove all elements with a given value from a deque.

Parameters
dequeA deque.
dataData to remove.
Returns
Nothing.

The value data is searched in the deque deque. If the data is found it is removed from the deque. The data object itself is not deallocated.

void cx_deque_reverse ( cx_deque *  deque)

Reverse the order of all deque elements.

Parameters
dequeThe deque to reverse.
Returns
Nothing.

The order of the elements of the deque deque is reversed.

cxsize cx_deque_size ( const cx_deque *  deque)

Get the actual number of deque elements.

Parameters
dequeA deque.
Returns
The current number of elements the deque contains, or 0 if the deque is empty.

Retrieves the number of elements currently stored in the deque deque.

void cx_deque_sort ( cx_deque *  deque,
cx_compare_func  compare 
)

Sort all elements of a deque using the given comparison function.

Parameters
dequeThe deque to sort.
compareFunction comparing the deque elements.
Returns
Nothing.

The input deque deque is sorted using the comparison function compare to determine the order of two deque elements. The comparison function compare must return an integer less than, equal or greater than zero if the first argument passed to it is found, respectively, to be less than, equal, or be greater than the second argument. This function uses the stdlib function qsort().

void cx_deque_splice ( cx_deque *  deque,
cx_deque_iterator  position,
cx_deque *  other,
cx_deque_iterator  first,
cx_deque_iterator  last 
)

Move a range of elements in front of a given position.

Parameters
dequeTarget deque.
positionTarget iterator position.
otherSource deque.
firstPosition of the first element to move.
lastPosition of the last element to move.
Returns
Nothing.

The range of deque elements from the iterator position first to last, but not including last, is moved from the source deque other in front of the position position of the target deque deque. Target and source deque may be identical, provided that the target position position does not fall within the range of deque elements to move.

void cx_deque_swap ( cx_deque *  deque,
cx_deque *  other 
)

Swap the data of two deques.

Parameters
dequeThe first deque.
otherThe second deque.
Returns
Nothing.

The contents of the deque other will be moved to the deque deque, while the contents of deque is moved to other.

void cx_deque_unique ( cx_deque *  deque,
cx_compare_func  compare 
)

Remove duplicates of consecutive elements.

Parameters
dequeA deque.
compareFunction comparing the deque elements.
Returns
Nothing.

The function removes duplicates of consecutive deque elements, i.e. deque elements with the same value, from the deque deque. The equality of the deque elements is checked using the comparison function compare. The comparison function compare must return an integer less than, equal or greater than zero if the first argument passed to it is found, respectively, to be less than, match, or be greater than the second argument.