Multi Maps

## Typedefs

typedef cx_tree | cx_multimap
| The multimap datatype.
typedef cx_tree_iterator | cx_multimap_iterator
| The multimap iterator datatype.
typedef cx_tree_const_iterator | cx_multimap_const_iterator
| The multimap constant iterator datatype.
typedef cx_tree_compare_func | cx_multimap_compare_func
| The multimap's key comparison operator function.

## Functions

cx_multimap_iterator | cx_multimap_begin (const cx_multimap *multimap)
| Get an iterator to the first pair in a multimap.
cx_multimap_iterator | cx_multimap_end (const cx_multimap *multimap)
| Get an iterator for the position after the last pair in the multimap.
cx_multimap_iterator | cx_multimap_next (const cx_multimap *multimap, cx_multimap_const_iterator position)
| Get an iterator for the next pair in the multimap.
cx_multimap_iterator | cx_multimap_previous (const cx_multimap *multimap, cx_multimap_const_iterator position)
| Get an iterator for the previous pair in the multimap.
void | cx_multimap_clear (cx_multimap *multimap)
| Remove all pairs from a multimap.
cxbool | cx_multimap_empty (const cx_multimap *multimap)
| Check whether a multimap is empty.
cx_multimap * | cx_multimap_new (cx_multimap_compare_func compare, cx_free_func key_destroy, cx_free_func value_destroy)
| Create a new multimap without any elements.
void | cx_multimap_delete (cx_multimap *multimap)
| Destroy a multimap and all its elements.
cxsize | cx_multimap_size (const cx_multimap *multimap)
| Get the actual number of pairs in the multimap.
cxsize | cx_multimap_max_size (const cx_multimap *multimap)
| Get the maximum number of pairs possible.
cx_multimap_compare_func | cx_multimap_key_comp (const cx_multimap *multimap)
| Retrieve a multimap's key comparison function.
void | cx_multimap_swap (cx_multimap *multimap1, cx_multimap *multimap2)
| Swap the contents of two multimaps.
cxptr | cx_multimap_assign (cx_multimap *multimap, cx_multimap_iterator position, cxcptr data)
| Assign data to an iterator position.
cxptr | cx_multimap_get_key (const cx_multimap *multimap, cx_multimap_const_iterator position)
| Get the key from a given iterator position.
cxptr | cx_multimap_get_value (const cx_multimap *multimap, cx_multimap_const_iterator position)
| Get the data from a given iterator position.
cx_multimap_iterator | cx_multimap_find (const cx_multimap *multimap, cxcptr key)
| Locate an element in the multimap.
cx_multimap_iterator | cx_multimap_lower_bound (const cx_multimap *multimap, cxcptr key)
| Find the beginning of a subsequence matching a given key.
cx_multimap_iterator | cx_multimap_upper_bound (const cx_multimap *multimap, cxcptr key)
| Find the end of a subsequence matching a given key.
void | cx_multimap_equal_range (const cx_multimap *multimap, cxcptr key, cx_multimap_iterator *begin, cx_multimap_iterator *end)
| Find a subsequence matching a given key.
cxsize | cx_multimap_count (const cx_multimap *multimap, cxcptr key)
| Get the number of elements matching a key.
cx_multimap_iterator | cx_multimap_insert (cx_multimap *multimap, cxcptr key, cxcptr data)
| Insert data into a multimap.
void | cx_multimap_erase_position (cx_multimap *multimap, cx_multimap_iterator position)
| Erase an element from a multimap.
void | cx_multimap_erase_range (cx_multimap *multimap, cx_multimap_iterator begin, cx_multimap_iterator end)
| Erase a range of elements from a multimap.
cxsize | cx_multimap_erase (cx_multimap *multimap, cxcptr key)
| Erase an element from a multimap according to the provided key.

## Detailed Description

The module implements a map data type, i.e. a container managing key/value pairs as elements. Their elements are automatically sorted according to a sorting criterion used for the key. The container is optimized for lookup operations. Contrary to ordinary maps a multimap is not restricted to unique keys, but may contain multiple duplicate keys.

Synopsis:
  #include "cxmultimap.h"

## Typedef Documentation

## cx_multimap

typedef cx_tree cx_multimap

The multimap datatype.

The internal representation of a mutimap is, as for ordinary maps too, a balanced binary tree. For this reason cx_multimap is just an alias for cx_tree.

## cx_multimap_compare_func

typedef cx_tree_compare_func cx_multimap_compare_func

The multimap's key comparison operator function.

This type of function is used internally by a multimap when key comparisons are necessary. It must return `TRUE` if the comparison of its first argument with the second argument succeeds, and `FALSE` otherwise. It is actually an alias for cx_tree_compare_func.

See also
  cx_tree_compare_func

## cx_multimap_const_iterator

typedef cx_tree_const_iterator cx_multimap_const_iterator

The multimap constant iterator datatype.

The multimap constant iterator is just an alias for the cx_tree_const_iterator datatype.

## cx_multimap_iterator

typedef cx_tree_iterator cx_multimap_iterator

The multimap iterator datatype.

The multimap iterator is just an alias for the cx_tree_iterator datatype.

## Function Documentation

## cx_multimap_assign()

cxptr cx_multimap_assign | ( | cx_multimap * | multimap,
|  | cx_multimap_iterator | position,
|  | cxcptr | data )

Assign data to an iterator position.

Parameters

  multimap | A multimap.
  position | Iterator positions where the data will be stored.
  data | Data to store.

Returns
  Handle to the previously stored data object.

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

References cx_tree_assign().

## cx_multimap_begin()

cx_multimap_iterator cx_multimap_begin | ( | const cx_multimap * | multimap | ) |

Get an iterator to the first pair in a multimap.

Parameters

  multimap | The multimap to query.

Returns
  Iterator for the first pair or cx_multimap_end() if the multimap is empty.

The function returns a handle for the first pair in the multimap multimap. The returned iterator cannot be used directly to access the value field of the key/value pair, but only through the appropriate methods.

References cx_tree_begin().

## cx_multimap_clear()

void cx_multimap_clear | ( | cx_multimap * | multimap | ) |

Remove all pairs from a multimap.

Parameters

  multimap | Multimap to be cleared.

Returns
  Nothing.

The multimap multimap is cleared, i.e. all pairs are removed from the multimap. Keys and values are destroyed using the key and value destructors set up during multimap creation. After calling this function the multimap is empty.

References cx_tree_clear().

## cx_multimap_count()

cxsize cx_multimap_count | ( | const cx_multimap * | multimap,
|  | cxcptr | key )

Get the number of elements matching a key.

Parameters

  multimap | A multimap.
  key | Key of the (key, value) pair(s) to locate.

Returns
  The number of elements with the specified key.

Counts all elements of the multimap multimap matching the key key.

References cx_tree_count().

## cx_multimap_delete()

void cx_multimap_delete | ( | cx_multimap * | multimap | ) |

Destroy a multimap and all its elements.

Parameters

  multimap | The multimap to destroy.

Returns
  Nothing.

The multimap multimap is deallocated. All data values and keys are deallocated using the multimap's key and value destructor. If no key and/or value destructor was set when the multimap was created the keys and the stored data values are left untouched. In this case the key and value deallocation is the responsibility of the user.

See also
  cx_multimap_new()

References cx_tree_delete().

## cx_multimap_empty()

cxbool cx_multimap_empty | ( | const cx_multimap * | multimap | ) |

Check whether a multimap is empty.

Parameters

  multimap | A multimap.

Returns
  The function returns `TRUE` if the multimap is empty, and `FALSE` otherwise.

The function checks if the multimap contains any pairs. Calling this function is equivalent to the statement:

return (cx_multimap_size(multimap) == 0);
cx_multimap_size
cxsize cx_multimap_size(const cx_multimap *multimap)
Get the actual number of pairs in the multimap.
Definition cxmultimap.c:253

References cx_tree_empty().

## cx_multimap_end()

cx_multimap_iterator cx_multimap_end | ( | const cx_multimap * | multimap | ) |

Get an iterator for the position after the last pair in the multimap.

Parameters

  multimap | The multimap to query.

Returns
  Iterator for the end of the multimap.

The function returns an iterator for the position one past the last pair in the multimap multimap. The iteration is done in ascending order according to the keys. The returned iterator cannot be used directly to access the value field of the key/value pair, but only through the appropriate methods.

References cx_tree_end().

## cx_multimap_equal_range()

void cx_multimap_equal_range | ( | const cx_multimap * | multimap,
|  | cxcptr | key,
|  | cx_multimap_iterator * | begin,
|  | cx_multimap_iterator * | end )

Find a subsequence matching a given key.

Parameters

  multimap | A multimap.
  key | The key of the (key, value) pair(s) to be located.
  begin | First element with key key.
  end | Last element with key key.

Returns
  Nothing.

The function returns the beginning and the end of a subsequence of multimap elements with the key key through through the begin and end arguments. After calling this function begin possibly points to the first element of multimap matching the key key and end possibly points to the last element of the sequence. If key is not present in the multimap begin and end point to the next greater element or, if no such element exists, to cx_multimap_end().

References cx_tree_equal_range().

## cx_multimap_erase()

cxsize cx_multimap_erase | ( | cx_multimap * | multimap,
|  | cxcptr | key )

Erase an element from a multimap according to the provided key.

Parameters

  multimap | A multimap.
  key | Key of the element to be erased.

Returns
  The number of removed elements.

This function erases the element with the specified key key, from multimap. Key and value associated with the erased pair are deallocated using the multimap's key and value destructors, provided they have been set.

References cx_tree_erase().

## cx_multimap_erase_position()

void cx_multimap_erase_position | ( | cx_multimap * | multimap,
|  | cx_multimap_iterator | position )

Erase an element from a multimap.

Parameters

  multimap | A multimap.
  position | Iterator position of the element to be erased.

Returns
  Nothing.

This function erases an element, specified by the iterator position, from multimap. Key and value associated with the erased pair are deallocated using the multimap's key and value destructors, provided they have been set.

References cx_tree_erase_position().

## cx_multimap_erase_range()

void cx_multimap_erase_range | ( | cx_multimap * | multimap,
|  | cx_multimap_iterator | begin,
|  | cx_multimap_iterator | end )

Erase a range of elements from a multimap.

Parameters

  multimap | A multimap.
  begin | Iterator pointing to the start of the range to erase.
  end | Iterator pointing to the end of the range to erase.

Returns
  Nothing.

This function erases all elements in the range [begin, end) from the multimap multimap. Key and value associated with the erased pair(s) are deallocated using the multimap's key and value destructors, provided they have been set.

References cx_tree_erase_range().

## cx_multimap_find()

cx_multimap_iterator cx_multimap_find | ( | const cx_multimap * | multimap,
|  | cxcptr | key )

Locate an element in the multimap.

Parameters

  multimap | A multimap.
  key | Key of the (key, value) pair to locate.

Returns
  Iterator pointing to the sought-after element, or cx_multimap_end() if it was not found.

The function searches the multimap multimap for the first element with a key matching key. If the search was successful an iterator to the sought-after pair is returned. If the search did not succeed, i.e. key is not present in the multimap, a one past the end iterator is returned.

References cx_tree_find().

## cx_multimap_get_key()

cxptr cx_multimap_get_key | ( | const cx_multimap * | multimap,
|  | cx_multimap_const_iterator | position )

Get the key from a given iterator position.

Parameters

  multimap | A multimap.
  position | Iterator position the data is retrieved from.

Returns
  Reference for the key.

The function returns a reference to the key associated with the iterator position position in the multimap multimap.

Note
  One must not modify the key of position through the returned reference, since this might corrupt the multimap!

References cx_tree_get_key().

## cx_multimap_get_value()

cxptr cx_multimap_get_value | ( | const cx_multimap * | multimap,
|  | cx_multimap_const_iterator | position )

Get the data from a given iterator position.

Parameters

  multimap | A multimap.
  position | Iterator position the data is retrieved from.

Returns
  Handle for the data object.

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

References cx_tree_get_value().

## cx_multimap_insert()

cx_multimap_iterator cx_multimap_insert | ( | cx_multimap * | multimap,
|  | cxcptr | key,
|  | cxcptr | data )

Insert data into a multimap.

Parameters

  multimap | A multimap.
  key | Key used to store the data.
  data | Data to insert.

Returns
  An iterator that points to the inserted pair.

This function inserts a (key, value) pair into the multimap multimap. The same key may be inserted with different data values.

References cx_tree_insert_equal().

## cx_multimap_key_comp()

cx_multimap_compare_func cx_multimap_key_comp | ( | const cx_multimap * | multimap | ) |

Retrieve a multimap's key comparison function.

Parameters

  multimap | The multimap to query.

Returns
  Handle for the multimap's key comparison function.

The function retrieves the function used by the multimap methods for comparing keys. The key comparison function is set during multimap creation.

See also
  cx_multimap_new()

References cx_tree_key_comp().

## cx_multimap_lower_bound()

cx_multimap_iterator cx_multimap_lower_bound | ( | const cx_multimap * | multimap,
|  | cxcptr | key )

Find the beginning of a subsequence matching a given key.

Parameters

  multimap | A multimap.
  key | Key of the (key, value) pair(s) to locate.

Returns
  Iterator pointing to the first position where an element with key key would get inserted, i.e. the first element with a key greater or equal than key.

The function returns the first element of a subsequence of elements in the multimap that match the given key key. If key is not present in the multimap multimap an iterator pointing to the first element that has a greater key than key or cx_multimap_end() if no such element exists.

References cx_tree_lower_bound().

## cx_multimap_max_size()

cxsize cx_multimap_max_size | ( | const cx_multimap * | multimap | ) |

Get the maximum number of pairs possible.

Parameters

  multimap | A multimap.

Returns
  The maximum number of pairs that can be stored in the multimap.

Retrieves the multimap's capacity, i.e. the maximum possible number of pairs a multimap can manage.

References cx_tree_max_size().

## cx_multimap_new()

cx_multimap * cx_multimap_new | ( | cx_multimap_compare_func | compare,
|  | cx_free_func | key_destroy,
|  | cx_free_func | value_destroy )

Create a new multimap without any elements.

Parameters

  compare | Function used to compare keys.
  key_destroy | Destructor for the keys.
  value_destroy | Destructor for the value field.

Returns
  Handle for the newly allocated multimap.

Memory for a new multimap is allocated and the multimap is initialized to be a valid empty multimap.

The multimap's key comparison function is set to compare. It must return `TRUE` or `FALSE` if the comparison of the first argument passed to it with the second argument is found to be true or false respectively.

The destructors for a multimap node's key and value field are set to key_destroy and value_destroy. Whenever a multimap node is destroyed these functions are used to deallocate the memory used by the key and the value. Each of the destructors might be `NULL`, i.e. keys and values are not deallocated during destroy operations.

See also
  cx_multimap_compare_func()

References cx_tree_new().

## cx_multimap_next()

cx_multimap_iterator cx_multimap_next | ( | const cx_multimap * | multimap,
|  | cx_multimap_const_iterator | position )

Get an iterator for the next pair in the multimap.

Parameters

  multimap | A multimap.
  position | Current iterator position.

Returns
  Iterator for the pair immediately following position.

The function returns an iterator for the next pair in the multimap multimap with respect to the current iterator position position. Iteration is done in ascending order according to the keys. If the multimap is empty or position points to the end of the multimap the function returns cx_multimap_end().

References cx_tree_next().

## cx_multimap_previous()

cx_multimap_iterator cx_multimap_previous | ( | const cx_multimap * | multimap,
|  | cx_multimap_const_iterator | position )

Get an iterator for the previous pair in the multimap.

Parameters

  multimap | A multimap.
  position | Current iterator position.

Returns
  Iterator for the pair immediately preceding position.

The function returns an iterator for the previous pair in the multimap multimap with respect to the current iterator position position. Iteration is done in ascending order according to the keys. If the multimap is empty or position points to the beginning of the multimap the function returns cx_multimap_end().

References cx_tree_previous().

## cx_multimap_size()

cxsize cx_multimap_size | ( | const cx_multimap * | multimap | ) |

Get the actual number of pairs in the multimap.

Parameters

  multimap | A multimap.

Returns
  The current number of pairs, or 0 if the multimap is empty.

Retrieves the current number of pairs stored in the multimap.

References cx_tree_size().

## cx_multimap_swap()

void cx_multimap_swap | ( | cx_multimap * | multimap1,
|  | cx_multimap * | multimap2 )

Swap the contents of two multimaps.

Parameters

  multimap1 | First multimap.
  multimap2 | Second multimap.

Returns
  Nothing.

All pairs stored in the first multimap multimap1 are moved to the second multimap multimap2, while the pairs from multimap2 are moved to multimap1. Also the key comparison function, the key and the value destructor are exchanged.

References cx_tree_swap().

## cx_multimap_upper_bound()

cx_multimap_iterator cx_multimap_upper_bound | ( | const cx_multimap * | multimap,
|  | cxcptr | key )

Find the end of a subsequence matching a given key.

Parameters

  multimap | A multimap.
  key | Key of the (key, value) pair(s) to locate.

Returns
  Iterator pointing to the last position where an element with key key would get inserted, i.e. the first element with a key greater than key.

The function returns the last element of a subsequence of elements in the multimap that match the given key key. If key is not present in the multimap multimap an iterator pointing to the first element that has a greater key than key or cx_multimap_end() if no such element exists.

References cx_tree_upper_bound().