Map
===
Tucker Evans
v0.5, 2020-07-06

A basic map implemented in an AVL tree.

NOTE: Keys are passed as void pointers and their data is not copied (this
should be handled by the user), they should not be freed without clearing the
map.

NOTE: There is currently no way to distinquish between a failed retrieval
(pop, index, back, etc.) and returning a NULL value. Keep this in mind if
you plan on storing NULL values in the vector, there are plans to fix this in
the future.

Types
----
The following types are defined in the header file:
[[map]]
+map+
~~~~~
This structure holds all internal information regarding a map.
All functions (except constructors) expect a pointer to this struct as their
first parameter.

[[cmp_func]]
+cmp_func+
~~~~~~~~~~~
This is a pointer to a function that to compare keys from pointers. This
typedef is provided to cast comparison functions as a map expects the
comparison function to take void* as its parameters.

Functions
---------
[[map_new]]
+map_new(cmp_func cmp)+
~~~~~~~~~~~~~~~~~~~~~~~
Constructs an empty map.
+cmp+ should be a function that takes two pointers (+lhs+, +rhs+)to your value
type and returns (int) a negative value if +lhs+ is less than  +rhs+, zero if
+lhs+ is equal to +rhs+, and positive value if +lhs+ is greater than +rhs+.

Examples
^^^^^^^^
[source,c]
----
#include "map.h"
#include <string.h>

map *dict = map_new((cmp_func) strcmp);
----

[[map_size]]
+map_size(map *self)+
~~~~~~~~~~~~~~~~~~~~~
Returns the number of key, value pairs stored in map +self+.

Examples
^^^^^^^^
[source,c]
----
#include "map.h"
#include <string.h>

map *dict = map_new((cmp_func) strcmp);

assert(map_size(dict) == 0);
map_insert(dict, "ONE", NULL);
assert(map_size(dict) == 1);
----

[[map_insert]]
+int map_insert(map *self, void *key, void *value)+
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Inserts item +value+ for +key+ into +self+
This returns an int indicating a successful insertion; currently the only
two potential errors are caused by a NULL map or an equivalent key with a
different pointer, this is in order to prevent a memory leak.
<<reset_key,+map_reset_key()+>> can be used to fix this issue.

Examples
^^^^^^^^
[source,c]
----
#include "map.h"
#include <string.h>

map *dict = map_new((cmp_func) strcmp);

map_insert(dict, "ONE", NULL);
assert(map_size(dict) == 1);
----

[[map_reset_key]]
+void* map_reset_key(map *self, vaid *key)+
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
This replaces an equivalent key with the one passed in, the key that is
overwritten is return so the user can free it.

Examples
^^^^^^^^
[source,c]
----
#include "map.h"
#include <string.h>

map *dict = map_new((cmp_func) strcmp);

map_insert(dict, strdup("ONE"), "VALUE");
assert(map_insert(dict, "ONE", "NEW_VALUE") < 0);
free(map_reset_key(dict "ONE"));
assert(map_insert(dict, "ONE", "NEW_VALUE") == 0);
----

[[map_index]]
+void* map_index(map *self, vaid *key)+
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Returns the value associated with +key+ (or equivalent).

Examples
^^^^^^^^
[source,c]
----
#include "map.h"
#include <string.h>

map *dict = map_new((cmp_func) strcmp, sizeof(char*));

map_insert(dict, strdup("ONE"), "VALUE");
assert(strcmp(map_index(dict, "ONE"), "VALUE") == 0);
----

[[map_clear]]
+void map_clear(map *self)+
~~~~~~~~~~~~~~~~~~~~~~~~~~~
Free all elements within dict +self+, and sets dict to empty (size 0).

NOTE: Does not free all internal memory of +self+ or +self+ itself, if this is
desired <<map_free,+map_free()+>> should be called immediatly after this.

Examples
^^^^^^^^
[source,c]
----
#include "map.h"
#include <string.h>

char *str1 = "ONE";
char *str2 = "TWO";

map *dict = map_new();
map_insert(dict, str_dup(str1), NULL);
map_insert(dict, str_dup(str2), NULL);

map_clear(dict);
assert(map_size(dict) == 0);
map_free(dict);
----

[[map_free]]
+void map_free(map *self)+
~~~~~~~~~~~~~~~~~~~~~~~~~~
Frees all internal memory and +self+.

NOTE: All item pointers are still valid after a call to
<<map_free,+map_free()+>>, <<map_clear,+map_clear()+>> should be called before
if they are no longer needed to avoid memory leaks.

Examples
^^^^^^^^
[source,c]
----
#include "map.h"

map *dict = map_new();
map_free(dict);
----
