Double-ended queue.

## Functions

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

## 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

## cx_deque_assign()

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

Assign data to a deque element.

Parameters

  deque | A deque.
  position | Position of the deque element where the data will be stored.
  data | Data 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.

## cx_deque_back()

cxptr cx_deque_back | ( | const cx_deque * | deque | ) |

Get the last element of a deque.

Parameters

  deque | The 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_begin()

cx_deque_iterator cx_deque_begin | ( | const cx_deque * | deque | ) |

Get an iterator for the first deque element.

Parameters

  deque | A 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.

## cx_deque_clear()

void cx_deque_clear | ( | cx_deque * | deque | ) |

Remove all elements from a deque.

Parameters

  deque | Deque 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.

## cx_deque_delete()

void cx_deque_delete | ( | cx_deque * | deque | ) |

Destroy a deque.

Parameters

  deque | The 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().

## cx_deque_destroy()

void cx_deque_destroy | ( | cx_deque * | deque,
|  | cx_free_func | deallocate )

Destroy a deque and all its elements.

Parameters

  deque | Deque container to destroy.
  deallocate | Data 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().

## cx_deque_empty()

cxbool cx_deque_empty | ( | const cx_deque * | deque | ) |

Check whether a deque is empty.

Parameters

  deque | A 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_end()

cx_deque_iterator cx_deque_end | ( | const cx_deque * | deque | ) |

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

Parameters

  deque | A 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_erase()

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

Erase a deque element.

Parameters

  deque | The deque to update.
  position | Deque iterator position.
  deallocate | Data 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.

## cx_deque_extract()

cxptr cx_deque_extract | ( | cx_deque * | deque,
|  | cx_deque_iterator | position )

Extract a deque element.

Parameters

  deque | A deque.
  position | Deque 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()

## cx_deque_front()

cxptr cx_deque_front | ( | const cx_deque * | deque | ) |

Get the first element of a deque.

Parameters

  deque | The 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.

## cx_deque_get()

cxptr cx_deque_get | ( | const cx_deque * | deque,
|  | cx_deque_const_iterator | position )

Retrieve an element from a deque.

Parameters

  deque | The deque to query.
  position | The 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_insert()

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

  deque | The deque to update.
  position | List iterator position.
  data | Data 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().

## cx_deque_max_size()

cxsize cx_deque_max_size | ( | const cx_deque * | deque | ) |

Get the maximum number of deque elements possible.

Parameters

  deque | A 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.

## cx_deque_merge()

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

Merge two sorted deques.

Parameters

  deque | Target deque of the merge operation.
  other | The deque to merge into the target.
  compare | Function 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_new()

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_next()

cx_deque_iterator cx_deque_next | ( | const cx_deque * | deque,
|  | cx_deque_const_iterator | position )

Get an iterator for the next deque element.

Parameters

  deque | A deque.
  position | Current 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().

## cx_deque_pop_back()

cxptr cx_deque_pop_back | ( | cx_deque * | deque | ) |

Remove the last deque element.

Parameters

  deque | The 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

cx_deque_extract(deque, cx_deque_previous(deque, cx_deque_end(deque)));
cx_deque_end
cx_deque_iterator cx_deque_end(const cx_deque *deque)
Get an iterator for the position after the last deque element.
Definition cxdeque.c:1021
cx_deque_previous
cx_deque_iterator cx_deque_previous(const cx_deque *deque, cx_deque_const_iterator position)
Get an iterator for the previous deque element.
Definition cxdeque.c:1067
cx_deque_extract
cxptr cx_deque_extract(cx_deque *deque, cx_deque_iterator position)
Extract a deque element.
Definition cxdeque.c:1321

## cx_deque_pop_front()

cxptr cx_deque_pop_front | ( | cx_deque * | deque | ) |

Remove the first deque element.

Parameters

  deque | The 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_extract(deque, cx_deque_begin(deque));
cx_deque_begin
cx_deque_iterator cx_deque_begin(const cx_deque *deque)
Get an iterator for the first deque element.
Definition cxdeque.c:1000

## cx_deque_previous()

cx_deque_iterator cx_deque_previous | ( | const cx_deque * | deque,
|  | cx_deque_const_iterator | position )

Get an iterator for the previous deque element.

Parameters

  deque | A deque.
  position | Current 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().

## cx_deque_push_back()

void cx_deque_push_back | ( | cx_deque * | deque,
|  | cxcptr | data )

Append data at the end of a deque.

Parameters

  deque | The deque to update.
  data | Data 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);
cx_deque_insert
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.
Definition cxdeque.c:1221

Referenced by cx_deque_insert().

## cx_deque_push_front()

void cx_deque_push_front | ( | cx_deque * | deque,
|  | cxcptr | data )

Insert data at the beginning of a deque.

Parameters

  deque | The deque to update.
  data | Data 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);

## cx_deque_remove()

void cx_deque_remove | ( | cx_deque * | deque,
|  | cxcptr | data )

Remove all elements with a given value from a deque.

Parameters

  deque | A deque.
  data | Data 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.

## cx_deque_reverse()

void cx_deque_reverse | ( | cx_deque * | deque | ) |

Reverse the order of all deque elements.

Parameters

  deque | The deque to reverse.

Returns
  Nothing.

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

## cx_deque_size()

cxsize cx_deque_size | ( | const cx_deque * | deque | ) |

Get the actual number of deque elements.

Parameters

  deque | A 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.

## cx_deque_sort()

void cx_deque_sort | ( | cx_deque * | deque,
|  | cx_compare_func | compare )

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

Parameters

  deque | The deque to sort.
  compare | Function 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().

## cx_deque_splice()

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

  deque | Target deque.
  position | Target iterator position.
  other | Source deque.
  first | Position of the first element to move.
  last | Position 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.

## cx_deque_swap()

void cx_deque_swap | ( | cx_deque * | deque,
|  | cx_deque * | other )

Swap the data of two deques.

Parameters

  deque | The first deque.
  other | The 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.

## cx_deque_unique()

void cx_deque_unique | ( | cx_deque * | deque,
|  | cx_compare_func | compare )

Remove duplicates of consecutive elements.

Parameters

  deque | A deque.
  compare | Function 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.