Maps

## Typedefs

typedef cx_tree | cx_map
| The map datatype.
typedef cx_tree_iterator | cx_map_iterator
| The map iterator datatype.
typedef cx_tree_const_iterator | cx_map_const_iterator
| The map constant iterator datatype.
typedef cx_tree_compare_func | cx_map_compare_func
| The map's key comparison operator function.

## Functions

cx_map_iterator | cx_map_begin (const cx_map *map)
| Get an iterator to the first pair in a map.
cx_map_iterator | cx_map_end (const cx_map *map)
| Get an iterator for the position after the last pair in the map.
cx_map_iterator | cx_map_next (const cx_map *map, cx_map_const_iterator position)
| Get an iterator for the next pair in the map.
cx_map_iterator | cx_map_previous (const cx_map *map, cx_map_const_iterator position)
| Get an iterator for the previous pair in the map.
void | cx_map_clear (cx_map *map)
| Remove all pairs from a map.
cxbool | cx_map_empty (const cx_map *map)
| Check whether a map is empty.
cx_map * | cx_map_new (cx_map_compare_func compare, cx_free_func key_destroy, cx_free_func value_destroy)
| Create a new map without any elements.
void | cx_map_delete (cx_map *map)
| Destroy a map and all its elements.
cxsize | cx_map_size (const cx_map *map)
| Get the actual number of pairs in the map.
cxsize | cx_map_max_size (const cx_map *map)
| Get the maximum number of pairs possible.
cx_map_compare_func | cx_map_key_comp (const cx_map *map)
| Retrieve a map's key comparison function.
void | cx_map_swap (cx_map *map1, cx_map *map2)
| Swap the contents of two maps.
cxptr | cx_map_assign (cx_map *map, cx_map_iterator position, cxcptr data)
| Assign data to an iterator position.
cxptr | cx_map_put (cx_map *map, cxcptr key, cxcptr data)
| Set the value of a pair matching the given key.
cxptr | cx_map_get_key (const cx_map *map, cx_map_const_iterator position)
| Get the key from a given iterator position.
cxptr | cx_map_get_value (const cx_map *map, cx_map_const_iterator position)
| Get the data from a given iterator position.
cxptr | cx_map_get (cx_map *map, cxcptr key)
| Get the data for a given key.
cx_map_iterator | cx_map_find (const cx_map *map, cxcptr key)
| Locate an element in the map.
cx_map_iterator | cx_map_lower_bound (const cx_map *map, cxcptr key)
| Find the beginning of a subsequence matching a given key.
cx_map_iterator | cx_map_upper_bound (const cx_map *map, cxcptr key)
| Find the end of a subsequence matching a given key.
void | cx_map_equal_range (const cx_map *map, cxcptr key, cx_map_iterator *begin, cx_map_iterator *end)
| Find a subsequence matching a given key.
cxsize | cx_map_count (const cx_map *map, cxcptr key)
| Get the number of elements matching a key.
cx_map_iterator | cx_map_insert (cx_map *map, cxcptr key, cxcptr data)
| Attempt to insert data into a map.
void | cx_map_erase_position (cx_map *map, cx_map_iterator position)
| Erase an element from a map.
void | cx_map_erase_range (cx_map *map, cx_map_iterator begin, cx_map_iterator end)
| Erase a range of elements from a map.
cxsize | cx_map_erase (cx_map *map, cxcptr key)
| Erase an element from a map 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. Maps are restriced to unique keys, i.e. a key can only appear once in a map.

Synopsis:
  #include "cxmap.h"

## Typedef Documentation

## cx_map

typedef cx_tree cx_map

The map datatype.

The internal representation of a map is a balanced binary tree. For this reason cx_map is just an alias for cx_tree.

## cx_map_compare_func

typedef cx_tree_compare_func cx_map_compare_func

The map's key comparison operator function.

This type of function is used internally by a map 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_map_const_iterator

typedef cx_tree_const_iterator cx_map_const_iterator

The map constant iterator datatype.

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

## cx_map_iterator

typedef cx_tree_iterator cx_map_iterator

The map iterator datatype.

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

## Function Documentation

## cx_map_assign()

cxptr cx_map_assign | ( | cx_map * | map,
|  | cx_map_iterator | position,
|  | cxcptr | data )

Assign data to an iterator position.

Parameters

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

References cx_tree_assign().

## cx_map_begin()

cx_map_iterator cx_map_begin | ( | const cx_map * | map | ) |

Get an iterator to the first pair in a map.

Parameters

  map | The map to query.

Returns
  Iterator for the first pair or cx_map_end() if the map is empty.

The function returns a handle for the first pair in the map map. 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_map_clear()

void cx_map_clear | ( | cx_map * | map | ) |

Remove all pairs from a map.

Parameters

  map | Map to be cleared.

Returns
  Nothing.

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

References cx_tree_clear().

## cx_map_count()

cxsize cx_map_count | ( | const cx_map * | map,
|  | cxcptr | key )

Get the number of elements matching a key.

Parameters

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

Returns
  The number of elements with the specified key.

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

References cx_tree_end(), and cx_tree_find().

## cx_map_delete()

void cx_map_delete | ( | cx_map * | map | ) |

Destroy a map and all its elements.

Parameters

  map | The map to destroy.

Returns
  Nothing.

The map map is deallocated. All data values and keys are deallocated using the map's key and value destructor. If no key and/or value destructor was set when the map 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_map_new()

References cx_tree_delete().

## cx_map_empty()

cxbool cx_map_empty | ( | const cx_map * | map | ) |

Check whether a map is empty.

Parameters

  map | A map.

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

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

return (cx_map_size(map) == 0);
cx_map_size
cxsize cx_map_size(const cx_map *map)
Get the actual number of pairs in the map.
Definition cxmap.c:250

References cx_tree_empty().

## cx_map_end()

cx_map_iterator cx_map_end | ( | const cx_map * | map | ) |

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

Parameters

  map | The map to query.

Returns
  Iterator for the end of the map.

The function returns an iterator for the position one past the last pair in the map map. 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_map_equal_range()

void cx_map_equal_range | ( | const cx_map * | map,
|  | cxcptr | key,
|  | cx_map_iterator * | begin,
|  | cx_map_iterator * | end )

Find a subsequence matching a given key.

Parameters

  map | A map.
  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 map elements with the key key through through the begin and end arguments. After calling this function begin possibly points to the first element of map matching the key key and end possibly points to the last element of the sequence. If key is not present in the map begin and end point to the next greater element or, if no such element exists, to cx_map_end().

References cx_tree_equal_range().

## cx_map_erase()

cxsize cx_map_erase | ( | cx_map * | map,
|  | cxcptr | key )

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

Parameters

  map | A map.
  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 map. Key and value associated with the erased pair are deallocated using the map's key and value destructors, provided they have been set.

Note
  For maps the the returned number should only be 0 or 1, due to the nature of maps.

References cx_tree_erase().

## cx_map_erase_position()

void cx_map_erase_position | ( | cx_map * | map,
|  | cx_map_iterator | position )

Erase an element from a map.

Parameters

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

Returns
  Nothing.

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

References cx_tree_erase_position().

## cx_map_erase_range()

void cx_map_erase_range | ( | cx_map * | map,
|  | cx_map_iterator | begin,
|  | cx_map_iterator | end )

Erase a range of elements from a map.

Parameters

  map | A map.
  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 map map. Key and value associated with the erased pair(s) are deallocated using the map's key and value destructors, provided they have been set.

References cx_tree_erase_range().

## cx_map_find()

cx_map_iterator cx_map_find | ( | const cx_map * | map,
|  | cxcptr | key )

Locate an element in the map.

Parameters

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

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

The function searches the map map for an 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 map, a one past the end iterator is returned.

References cx_tree_find().

## cx_map_get()

cxptr cx_map_get | ( | cx_map * | map,
|  | cxcptr | key )

Get the data for a given key.

Parameters

  map | A map.
  key | Key for which the data should be retrieved.

Returns
  Handle to the value of the (key, value) pair matching the key key.

The function looks for the key key in the map map and returns the data associated with this key. If key is not present in map it is inserted using `NULL` as the associated default value, which is then returned.

References cx_tree_end(), cx_tree_get_key(), cx_tree_get_value(), cx_tree_insert_unique(), cx_tree_key_comp(), and cx_tree_lower_bound().

## cx_map_get_key()

cxptr cx_map_get_key | ( | const cx_map * | map,
|  | cx_map_const_iterator | position )

Get the key from a given iterator position.

Parameters

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

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

References cx_tree_get_key().

## cx_map_get_value()

cxptr cx_map_get_value | ( | const cx_map * | map,
|  | cx_map_const_iterator | position )

Get the data from a given iterator position.

Parameters

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

References cx_tree_get_value().

## cx_map_insert()

cx_map_iterator cx_map_insert | ( | cx_map * | map,
|  | cxcptr | key,
|  | cxcptr | data )

Attempt to insert data into a map.

Parameters

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

Returns
  An iterator that points to the inserted pair, or `NULL` if the pair could not be inserted.

This function attempts to insert a (key, value) pair into the map map. The insertion fails if the key already present in the map, since a key may only occur once in a map.

References cx_tree_insert_unique().

## cx_map_key_comp()

cx_map_compare_func cx_map_key_comp | ( | const cx_map * | map | ) |

Retrieve a map's key comparison function.

Parameters

  map | The map to query.

Returns
  Handle for the map's key comparison function.

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

See also
  cx_map_new()

References cx_tree_key_comp().

## cx_map_lower_bound()

cx_map_iterator cx_map_lower_bound | ( | const cx_map * | map,
|  | cxcptr | key )

Find the beginning of a subsequence matching a given key.

Parameters

  map | A map.
  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 map that match the given key key. If key is not present in the map map an iterator pointing to the first element that has a greater key than key or cx_map_end() if no such element exists.

Note
  For maps, where a key can occur only once, is a call to this function equivalent to calling cx_map_find().

References cx_tree_lower_bound().

## cx_map_max_size()

cxsize cx_map_max_size | ( | const cx_map * | map | ) |

Get the maximum number of pairs possible.

Parameters

  map | A map.

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

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

References cx_tree_max_size().

## cx_map_new()

cx_map * cx_map_new | ( | cx_map_compare_func | compare,
|  | cx_free_func | key_destroy,
|  | cx_free_func | value_destroy )

Create a new map 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 map.

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

The map's key comparison function is set to compare. It must return `TRUE` if the comparison of its first argument with its second argument succeeds, and `FALSE` otherwise.

The destructors for a map node's key and value field are set to key_destroy and value_destroy. Whenever a map 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_map_compare_func()

References cx_tree_new().

## cx_map_next()

cx_map_iterator cx_map_next | ( | const cx_map * | map,
|  | cx_map_const_iterator | position )

Get an iterator for the next pair in the map.

Parameters

  map | A map.
  position | Current iterator position.

Returns
  Iterator for the pair immediately following position.

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

References cx_tree_next().

## cx_map_previous()

cx_map_iterator cx_map_previous | ( | const cx_map * | map,
|  | cx_map_const_iterator | position )

Get an iterator for the previous pair in the map.

Parameters

  map | A map.
  position | Current iterator position.

Returns
  Iterator for the pair immediately preceding position.

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

References cx_tree_previous().

## cx_map_put()

cxptr cx_map_put | ( | cx_map * | map,
|  | cxcptr | key,
|  | cxcptr | data )

Set the value of a pair matching the given key.

Parameters

  map | A map.
  key | The key of the map element to be changed.
  data | Data value to be stored.

Returns
  Previously stored data value of the (key, value) pair.

The function replaces the value of the map element with the key key with value, if the key is present in the map map. The old value of the map element is returned. If the key is not yet present in the map the pair (key, data) is inserted in the map. In this case the returned handle to the previously stored data points to data.

References cx_tree_assign(), cx_tree_end(), cx_tree_insert_unique(), and cx_tree_lower_bound().

## cx_map_size()

cxsize cx_map_size | ( | const cx_map * | map | ) |

Get the actual number of pairs in the map.

Parameters

  map | A map.

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

Retrieves the current number of pairs stored in the map.

References cx_tree_size().

## cx_map_swap()

void cx_map_swap | ( | cx_map * | map1,
|  | cx_map * | map2 )

Swap the contents of two maps.

Parameters

  map1 | First map.
  map2 | Second map.

Returns
  Nothing.

All pairs stored in the first map map1 are moved to the second map map2, while the pairs from map2 are moved to map1. Also the key comparison function, the key and the value destructor are exchanged.

References cx_tree_swap().

## cx_map_upper_bound()

cx_map_iterator cx_map_upper_bound | ( | const cx_map * | map,
|  | cxcptr | key )

Find the end of a subsequence matching a given key.

Parameters

  map | A map.
  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 map that match the given key key. If key is not present in the map map an iterator pointing to the first element that has a greater key than key or cx_map_end() if no such element exists.

Note
  For maps, calling this function is equivalent to:
  cx_map_iterator it;
  it = cx_map_find(map, key);
  it = cx_map_next(map, it);
  cx_map_next
  cx_map_iterator cx_map_next(const cx_map *map, cx_map_const_iterator position)
  Get an iterator for the next pair in the map.
  Definition cxmap.c:105
  cx_map_find
  cx_map_iterator cx_map_find(const cx_map *map, cxcptr key)
  Locate an element in the map.
  Definition cxmap.c:470
  cx_map_iterator
  cx_tree_iterator cx_map_iterator
  The map iterator datatype.
  Definition cxmap.h:49
  omitting all error checks.

References cx_tree_upper_bound().