# README for `libmaze` library
## Team: Group 9 - Invalid Pointer
Members: Samiha Datta, Mer Anderson, Sabrina Jain
GitHub usernames: samihadatta, meranderson, sabrinajain747
Date: March 9th, 2020

## Overview
The `libmaze` library holds everything required to make the algorithm run. It contains the following modules, which are listed in different categories of functionality (for quicker navigation of this section):
* Modules created specifically for the algorithm ("algorithm helper modules")
* `avatar` (represents an avatar moving through maze)
* `avatar_info` (the information passed to each `avatar` thread)
* `message` (handles the reading and writing of messages to and from the server)
* `pointlib` (useful functions related to the `XYPos` structure)
* `coordinate` (doubly-linked list node)
* `discovered` (doubly-linked list manipulator)
* `move_algorithm` (methods that determine the optimal next move for each avatar)
* Modules necessary for output
* `gui` (graphical user interface methods)
* `logfile` (used for printing to console and logfile)
* General modules/data structures (used in previous labs) ("given modules")
* `hashtable` (Hashtable hashes keys to slots (which each contain a set) and stores keys to object pairs in sets).
* `set` (Stores a linked list of key to object pairs).
* `jhash` (Contains a function to hash a string to a constant hashkey).

## Implementation Strategy

### Algorithm helper modules
#### `avatar`

void *run_avatar (void *info);

* The `run_avatar` method called for each avatar's thread; essentially the "main" function for each thread. Calls algorithm to determine moves and calls relevant graphicsmethods to update the ASCII GUI.

#### `avatar_info`

typedef struct avatar_info { ... } avatar_info_t
avatar_info_t *new_avatar_info (int id, uint32_t n_avatars, uint32_t difficulty, int comm_sock, uint32_t maze_port, char *log_file, uint32_t maze_width, uint32_t maze_height);
void avatar_info_delete (avatar_info_t *info);

* `avatar_info_t` is a structure that holds information about maze/documentation that's passed to each avatar's thread which includes the avatar id, number of avatars in the maze, maze difficulty, socket number for the socket over with communication is occuring, the identifier for the used maze port, string for the log file, exit status of the thread, width of the maze, and height of the maze
* `new_avatar_info` creates a new avatar_info structure, initializing each of its attributes to the provided values (attributes described above).
* `avatar_info_delete` deletes the avatar_info struct

#### `message`

AM_Message new_AM_message (int comm_sock);
AM_Message new_INIT_message (uint32_t n_avatars, uint32_t difficulty);
void send_INIT_message (AM_Message message, int comm_sock);
AM_Message new_READY_message (uint32_t id);
void send_READY_message (AM_Message message, int comm_sock);
void send_MOVE_message(int comm_sock, uint32_t id, uint32_t direction);

* `new_AM_message` reads in and create a new message from the server (client has specific message constructors).
* `new_INIT_message` constructs a new AM_INIT message for client.
* `send_INIT_message` sends AM_INIT messsage to server through provided socket.
* `new_READY_message` constructs a new AM_READY message
* `send_READY_message` sends AM_READY message to server through provided socket.
* `send_MOVE_message` sends AM_MOVE messsage to server through provided socket with provided id (of the avatar) and direction (of the move).

#### `pointlib`

XYPos point_new(uint32_t x, uint32_t y);
char *string_from_point(XYPos point);
XYPos point_from_string(char *string_pt);
bool points_are_equal(XYPos pt1, XYPos pt2);
int get_move_direction(XYPos pt1, XYPos pt2);
bool point_is_null_equivalent(XYPos pt);
XYPos point_null_equivalent();
int get_num_digits(uint32_t num);
char *ivl_from_point(XYPos point, int last_move);

* `point_new` returns a new XYPos structure with the provided x and y coordinates.
* `string_from_point`, when given an XYPos struct, it returns its string representation (in char* form) as follows, point: (x,y) --> string: x y
* `point_from_string` when given a string representation of a point, returns the corresponding XYPos struct (i.e. an XYPos struct with the provided x and y values) as follows, string: x y --> Point: (x,y)
* `points_are_equal` is an equality checker for the XYPos struct. If the two provided XYPos structures have the same X and Y values, returns true; else (or if either are NULL) returns false.
* `get_move_direction` returns the direction of the move from XYPos pt1 to XYPos pt2. Directions are defined in `amazing.h`.
* `point_is_null_equivalent` returns true if the point is equal to the null equivalent and false if not.
* `point_null_equivalent` returns a null equivalent of the point (each coordinate at max value, which the maze will never reach itself).
* `get_num_digits` provided a uint32_t number, returns the number of digits it encompasses.
* `ivl_from_point` invalid hashtable representation of point (used in algorithm).

#### `coordinate`

typedef struct coordinate coordinate_t;
coordinate_t *coordinate_new(Avatar *move, int turn_number);
XYPos coordinate_getPos(coordinate_t *coordinate);
int coordinate_getTurnNumber(coordinate_t *coordinate);
int coordinate_getID(coordinate_t *coordinate);
coordinate_t *coordinate_getPrevious(coordinate_t *coordinate);
coordinate_t *coordinate_getNext(coordinate_t *coordinate);
bool coordinate_getFollow(coordinate_t *coordinate);
bool coordinate_getMatch(coordinate_t *coordinate);
void coordinate_setNext(coordinate_t *base, coordinate_t *new_next);
void coordinate_setPrevious(coordinate_t *new_next, coordinate_t *to_be_previous);
void coordinate_setFollow(coordinate_t *coordinate, bool follow);
void coordinate_setMatch(coordinate_t *coordinate, bool match);
bool coordinates_areEqual(coordinate_t *c1, coordinate_t *c2);
void coordinate_print(coordinate_t *coordinate, FILE *fp);
void coordinate_delete(coordinate_t *coordinate);

* `coordinate_new` creates and returns a new coordinate_t structure (or NULL if error)
* `coordinate_getPos` when provided a coordinate, returns the XYPos associated with the coordinate's move and NULL if the coordinate's avatar is NULL.
* `coordinate_getTurnNumber` returns provided coordinate's turn number and -1 if the coordinate is NULL.
* `coordinate_getID` returns provided coordinate's id and -1 if the coordinate is NULL.
* `coordinate_getPrevious` returns the provided coordinate's previous coordinate and NULL if the coordinate is NULL.
* `coordinate_getNext` returns the provided coordinate's next coordinate and NULL if the coordinate is NULL.
* `coordinate_getFollow` returns the found_follow boolean associated with the provided coordinate.
* `coordinate_getMatch` returns the found_match boolean associated with the provided coordinate.
* `coordinate_setNext` sets the first coordinate's next coordinate pointer to the second coordinate if the first coordinate is not NULL.
* `coordinate_setPrevious` sets the first coordinate's previous coordinate pointer to the second coordinate if the first coordinate is not NULL.
* `coordinate_setFollow` sets the provided coordinate's found_follow attribute to the provided boolean.
* `coordinate_setMatch` sets the provided coordinate's found_match attribute to the provided boolean.
* `coordinates_areEqual` checks if the two coordinates are equal (via points_are_equal in pointlib.c). Returns true if the coordinates are equal (as defined above, i.e. in accordance with the pointlib) and false otherwise including NULL cases).
* `coordinate_print` prints a representation of the current coordinate in the following format:
* `coordinate {point -> [XYPos string], id -> [id integer], turn: [turn number]}`
* `coordinate_delete` deletes the provided coordinate.

#### `discovered`

typedef struct discovered discovered_t;
coordinate_t *discovered_getHead(discovered_t *discovered);
discovered_t *discovered_new(void);
void discovered_add(discovered_t *discovered, Avatar *move, int turn_number);
void discovered_delete(discovered_t *discovered);
void discovered_print(discovered_t *discovered, FILE *fp);
coordinate_t *discovered_getCorrespondingCoordinate(discovered_t *discovered, Avatar *move);

* `discovered_getHead` when provided a non-NULL discovered struct, returns its head (a coordinate_t struct). In the event of a NULL provided struct, returns NULL.
* `discovered_new` creates a discovered struct with a head initialized to NULL; in the case of failure, returns NULL.
* `discovered_add` adds new point (information given through provided Avatar and turn number) to list of discovered coordinates. Only adds if the new point is different from the most recent point.
* `discovered_delete` deletes the provided discovered structure.
* `discovered_print` prints the provided discovered structure coordinate by coordinate.
* `discovered_getCorrespondingCoordinate` given a discovered list and an Avatar, returns the coordinate that contains the point corresponding to the avatar or NULL if the point doesn't exist in the discovered struct or any of the inputs are NULL.

#### `move_algorithm`

int get_move(hashtable_t *htdisc_heads, hashtable_t *htpoints_all, hashtable_t *my_invalid_ht, int avatarid, int last_attempt, int n_avatars);
XYPos get_adj_point(XYPos start, uint32_t direction);

* `get_move` is the function that executes algorithm functionality. It accepts a hashtable of the heads of the linked list of discovered points for each avatar, a hashtable of all the discovered points, a hashtable of all the invalid points, the current avatar id, the last attempted move by that avatar, and the total number of avatars.
* `get_adj_point` takes in an `XYPos` and a direction and returns the `XYPos` point coordinates if the avatar was to move in that direction.

### Output modules
#### `gui`

typedef struct grid
{
    char **matrix;
    int maze_width;
    int maze_height;
    int grid_width;
    int grid_height;
    int num_avatars;
} grid_t;

/**************** getter functions *****************/
int grid_get_maze_width(grid_t *grid);
int grid_get_maze_height(grid_t *grid);

/**************** other functions *****************/
grid_t *grid_new(int maze_width, int maze_height, int num_avatars);
void grid_update(grid_t *grid, XYPos prev_location, XYPos new_location, int id);
void grid_add_wall(grid_t *maze, XYPos maze_location, int direction);
void print_separator(FILE *fp, grid_t *grid);
bool valid_direction(int direction);
bool vertical_direction(int direction);
bool horizontal_direction(int direction);
void grid_set_point(grid_t *grid, XYPos point, char filler);
void grid_print(grid_t *maze, FILE *fp);
bool point_within_maze(grid_t *grid, XYPos point);
void grid_delete(grid_t *grid);
XYPos get_adjacent_point(XYPos start, int direction);

The `gui` class contains all the methods necessary for making a graphical user interface. It includes the `grid_t` struct and a variety of helpful methods. See the header file for more information, but the following is a summary:
* `grid_t`: holds a matrix to represent the grid, the maze height and width, and the grid height and width (because the grid also contains room for walls). The ASCII GUI relies on this for all functionality
* `grid_get_maze_width`: returns the `maze_width` attribute of the provided grid or -1 if the grid is null
* `grid_get_maze_height`: Returns the `maze_height` attribute of the provided grid or -1 if the grid is null
* `grid_new`: Provided a maze width and height and the number of avatars, creates a grid structure with these values
* `grid_update`: Updates the provided grid based on the provided current and last location of the avatar with the given id.
* `grid_add_wall`: Provided a grid, a pointer to the XYPos for the place from which a move is being attempted (in maze coordinates), and the direction in which the move was attempted to be made, adds a wall (which will be drawn based on the direction that the attempted move was made in).
* `print_separator`: Provided a grid, prints a line of `SEPARATOR_CHAR` (global variable) to separate different prints of the maze
* `valid_direction`: Provided a direction, checks if it's a valid way in which one can move. If so, returns true; otherwise, returns false
* `vertical_direction`: Returns true if the provided integer direction is vertical and false if not
* `horizontal_direction`: Returns true if the provided integer direction is horizontal and false if not
* `grid_set_point`: Provided a grid, a point converted to the grid coordinate system, and a character, sets the point in the grid to the character (if the point is inside of the grid)
* `grid_print`: Prints the ASCII graphical user interface given the provided grid structure (which represents the maze) to the provided file
* `point_within_maze`: Provided a grid and a point in maze coordinate form, checks if the point is inside of the grid by converting to maze coordinates and then calling `point_within_grid`
* `grid_delete`: Provided a grid, deletes it by freeing each row of the double matrix and then freeing the entire grid structure
* `get_adjacent_point`: Given a point and the direction in which the move should be made, returns the adjacent point to the provided point in the provided direction (used for finding wall locations in gui.c and for finding adjacent maze points in avatar.c)

#### `logfile`

void write_action(char *log_file, Avatar *avatar, XYPos point, uint32_t last_move, grid_t *GRID);
void write_positions (char *log_file, hashtable_t *discovered_paths, int n_avatars);
void write_insert(char *log_file, int avatar_id, XYPos point, grid_t *grid);
void write_maze_solved(char *log_file);
void write_error(char *log_file, uint32_t message_type);

The `logfile` class contains the methods necessary to update the grid and print to `stdout` and the logfile. Its methods include:
* `write_action`: Provided the name of the log file, the avatar that moved, the point to which it moved (converted to a usable format), the last move made, the hashtable of invalid points, and the grid, writes the action to the graphics and the log file
* `write_positions`: Provided the name of the log file, a hashtable of discovered paths, and the number of avatars, writes the positions of each avatar to the log file.
* `write_insert`: Provided the name of the log file, the id of the avatar that was inserted, the point at which it was inserted, and the graphics grid struct for the class, prints out messages stating that the avatar has been inserted, inserts the avatar into the grid, and prints the grid
* `write_maze_solved`: Provided the name of the log file, writes a message to indicate that the maze is solved
* `write_error`: Provided the name of the log file and a uint32_t for the message type, writes an error

### Given modules
#### `hashtable`
We use hashtables to track the avatars moves, store discovered points, and store invalid points.

typedef struct hashtable hashtable_t;
hashtable_t *hashtable_new(const int num_slots);
bool hashtable_insert(hashtable_t *ht, const char *key, void *item);
void *hashtable_find(hashtable_t *ht, const char *key);
void hashtable_print(hashtable_t *ht, FILE *fp, void (*itemprint)(FILE *fp, const char *key, void *item));
void hashtable_iterate(hashtable_t *ht, void *arg, void (*itemfunc)(void *arg, const char *key, void *item));
void hashtable_delete(hashtable_t *ht, void (*itemdelete)(void *item) );

* `hashtable_new` creates a new (empty) hashtable. The caller provides: number of slots to be used for the hashtable (must be > 0). We return: pointer to the new hashtable; return NULL if error. We guarantee: hashtable is initialized empty. Caller is responsible for: later calling hashtable_delete.
* `hashtable_insert` inserts an item, identified by key (string), into the given hashtable. Caller provides: valid pointer to hashtable, valid string for key, valid pointer for item. We return: false if key exists in ht, any parameter is NULL, or error and true iff new item was inserted. Notes: The key string is copied for use by the hashtable; that is, the module is responsible for allocating memory for a copy of the key string, and later deallocating that memory; thus, the caller is free to re-use or deallocate its key string after this call.
* `hashtable_find` returns the item associated with the given key. Caller provides: valid pointer to hashtable, valid string for key. We return: pointer to the item corresponding to the given key, if found; NULL if hashtable is NULL, key is NULL, or key is not found. Notes: the hashtable is unchanged by this operation.
* `hashtable_print` prints the whole table; provide the output file and func to print each item. Caller provides: valid pointer to hashtable, FILE open for writing, itemprint that can print a single (key, item) pair. We print: nothing, if NULL fp. "(null)" if NULL ht. One line per hash slot, with no items, if NULL itemprint. Otherwise, one line per hash slot, listing (key,item) pairs in that slot. Note: the hashtable and its contents are not changed by this function.
* `hashtable_iterate` iterates over all items in the table; in undefined order. Caller provides: valid pointer to hashtable, arbitrary void*arg pointer, itemfunc that can handle a single (key, item) pair. We do: nothing, if ht equals NULL or itemfunc equals NULL. Otherwise, call the itemfunc once for each item, with (arg, key, item). Notes: the order in which hashtable items are handled is undefined. The hashtable and its contents are not changed by this function, but the itemfunc may change the contents of the item.
* `hashtable_delete` deletes the hashtable, calling a delete function on each item. Caller provides: valid hashtable pointer, valid pointer to function that handles one item (may be NULL). We do: if hashtable equals NULL, do nothing. Otherwise, unless itemfunc equals NULL, call the itemfunc on each item. Free all the key strings, and the hashtable itself. Notes: We free the strings that represent key for each item, because this module allocated that memory in hashtable_insert.

#### `jhash`

unsigned long JenkinsHash(const char *str, unsigned long mod);

* `JenkinsHash` is a given function that determines the optimal spot to store an item in a hashtable based on the given key.

#### `set`
Supports hashtable functionality.

typedef struct set set_t;
set_t *set_new(void);
bool set_insert(set_t *set, const char *key, void *item);
void *set_find(set_t *set, const char *key);
void set_print(set_t *set, FILE *fp, void (*itemprint)(FILE *fp, const char *key, void *item));
void set_iterate(set_t *set, void *arg, void (*itemfunc)(void *arg, const char *key, void *item));
void set_delete(set_t *set, void (*itemdelete)(void *item));

* `set_new` returns a pointer to a new set, or NULL if error. We guarantee the set is initialized empty. Caller is responsible for later calling set_delete.
* `set_insert` inserts an item, identified by a key (string), into the given set. The caller provides a valid set pointer, valid string pointer, and pointer to item. We return false if key exists, any parameter is NULL, or error and true iff new item was inserted. The caller is responsible for later calling set_delete to free the memory used by key strings. Notes: The key string is copied for use by the set; that is, the module is responsible for allocating memory for a copy of the key string, and later deallocating that memory; thus, the caller is free to re-use or deallocate its key string after this call.
* `set_find` returns the item associated with the given key. The caller provides a valid set pointer and valid string pointer. We return a pointer to the desired item, if found; NULL if set is NULL, key is NULL, or key is not found. Notes: The item is *not* removed from the set. Thus, the caller should *not* free the pointer that is returned.
* `set_print` prints the whole set; provide the output file and func to print each item. The caller provides: valid set pointer, FILE open for writing, valid pointer to function that prints one item. We print: nothing if NULL fp. Print (null) if NULL set. Print a set with no items if NULL itemprint. Otherwise, print a comma-separated list of items surrounded by {brackets}. Notes: The set and its contents are not changed. The 'itemprint' function is responsible for printing (key,item).
* `set_iterate` iterates over the set, calling a function on each item. Caller provides: valid set pointer, arbitrary argument (pointer) that is passed-through to itemfunc, and valid pointer to function that handles one item. We do: nothing, if set equals NULL or itemfunc equals NULL. Otherwise, call the itemfunc on each item, with (arg, key, item). Notes: the order in which set items are handled is undefined. The set and its contents are not changed by this function, but the itemfunc may change the contents of the item.
* `set_delete` deletes the set, calling a delete function on each item. Caller provides: valid set pointer, valid pointer to function that handles one item (may be NULL). We do: if set equals NULL, do nothing. Otherwise, unless itemfunc equals NULL, call the itemfunc on each item. Free all the key strings, and the set itself. Notes: We free the strings that represent key for each item, because this module allocated that memory in set_insert.

## Compilation

To build, run `make`.

To clean up, run `make clean`.