# CIS2750 Final Exam F22
- Kyle Lukaszek / ID: 1113798
- If the PDF formatting is weird, you can read this on: https://hackmd.io/@klukasze/BJFP8SpPo

---
# Question 1
## Function 1:
- Function Signature:
- void parsePair(xmlDoc *doc, xmlNode *node, StyleMap *stylemap, int pair_num)

- Function Location:
- This function is located at line 681 in KMLHelpers.c in Assignment 1 and line 682 in Assignments 2-3.

- Function Purpose:
- This function is used to parse a StyleMap pair (int pair_num) key and URL into a StyleMap struct from an xmlNode pointer which can be placed into a KML struct's StyleMap list. This function would be called twice by my createStyleMap() helper function since we assume that each StyleMap contains two pairs.

- Testing Strategy:
- Since parsePair() is the backbone for my other helper function createStyleMap(), I technically tested the two at the same time since if parsePair() failed, createStyleMap() would also fail.
- To test these functions, I first started by trying to pass them various NULL parameters to see if they could successfully handle returning without crashing or leaking memory when being handed an invalid parameter.
- Next I tested the function by trying to read the pairs from Reyn_UC1_blue-390.kml and then printing out the parsed contents from within the function to see if the strings contained the correct data.
- Once I validated that the printed strings were correct, I removed the print statements, and then tested to make sure that the strings were also correct within the final StyleMap struct because sometimes memory errors can occur when making a small mistake using anything with dynamic memory allocation.
- If strings printed from the StyleMap for Reyn_UC1_blue-390.kml contained key1: normal, url1: #failed0, and key2: highlight, url2: #failed1, I knew that the function worked as intended.
- I then repeated the previous tests by editing the contents of the Reyn_UC1_blue-390.kml StyleMap to have different values to make sure that it worked for various strings of different lengths.
- Once the testFiles were released with test1pre, I then made sure to test createStyleMap() and parsePair() using the other KML files provided to make sure that there were no other problems when using different files.

## Function 2:
- Function Signature:
- xmlDoc* KMLtoXmlDoc(const KML *doc)

- Function Location:
- This function is located at line 82 in KMLHelpersA2.c in Assignments 2-3.

- Function Purpose:
- This function is used to generate an xmlDoc struct pointer from a KML struct (const KML *doc) that has been validated by validateKML() by utilizing various different libxml2 functions to populate a new xmlDoc struct.

- Testing Strategy:
- KMLtoXmlDoc() is a backbone helper function of KMLParser functions validateKML() and writeKML(). I had the liberty of assuming that the contents of the KML struct followed all specifications of KMLParser.h since this helper function is called after checking all specs in validateKML() and since we can ALWAYS assume that validateKML() is called before calling writeKML(), we know that the passed KML parameter has nothing wrong with it.
- I still made sure to check to see if the KML struct is NULL and return since it is just smart practice to do so.
- As a precaution, I then made sure to check the constraints of the KML struct again within every helper function that KMLtoXmlDoc() calls to populate a new xmlDoc pointer. If any of these helper functions return false, that means an error has occured and the function will return a NULL xmlDoc pointer after freeing any memory that libxml2 may have allocated when building a new xmlDoc pointer.
- To test this function I used every test file provided by the A1 test suite and then created individual KML structs using createValidKML(). After creating the structs, I then passed them to KMLtoXmlDoc() to see if an xmlDoc pointer is successfully returned. Once returned, I then called the libxml2 function "xmlSaveFormatFileEnc()" to see if I could create a copy of the original KML file using the newly generated xmlDoc pointer that was returned.

- ```
KML *doc = createValidKML(filename, schemafile);
xmlDoc *new_doc = KMLtoXmlDoc(doc);
xmlSaveFormatFileEnc(test.kml, new_doc, "UTF-8", 1);

    - After testing every provided test KML file and comparing the KML file contents to one another to see if they matched, I concluded that the function worked as intended.

# Question 2
## List* getPathsWithLength(const KML *doc, double len, double delta):
- Function Location:
    - This function can be found in src/KMLParser.c starting at line 942 in Assignment 2 or at line 943 in Assignment 3.

- Function Purpose: 
    - This function exists to return a list of existing paths that are similar in length to the provided length (len) by comparing every path length to the desired length +/- the provided tolerance (delta). This could be useful if you are looking for a new trail to run on that is similar in length to what you are used to. Although this function was unused in the end, this function could have easily been implemented into A3 as a simple search function that has a default tolerance that is set and the user just has to search for their desired length. Maybe in a settings tab the tolerance could be adjusted but we did not have to do anything like that for our "isLoop" functionality in A3.

- My Implementation:

List* getPathsWithLength(const KML *doc, double len, double delta)
{
//make sure function parameters are up to spec
if (doc == NULL) return NULL;
if (len < 0) return NULL;
if (delta < 0) return NULL;

//make sure doc has path placemarks
if (doc->pathPlacemarks == NULL) return NULL;
if (getLength(doc->pathPlacemarks) == 0) return NULL;

//initialize an empty list (formatting is just for the pdf's sake)
List *results = initializeList(
&pathPlacemarkToString, &deleteDataDummy, &comparePathPlacemarks);

//create iterator of path placemarks and get first element from list
ListIterator iter = createIterator(doc->pathPlacemarks);
PathPlacemark *ppm = nextElement(&iter);

//set max/min length based on len +/- delta
double max_len = len + delta;
double min_len = len - delta;

//iterate through path placemarks
while (ppm != NULL)
{
//get current path total distance
double dist = getPathLen(ppm);

//make sure getPathLen() does not return 0 since that means an error occured
if(dist > 0)
{
//if the distance between two lengths is within the tolerance,
//they are considered equal and the path placemark is added as a result
if(dist >= min_len && dist <= max_len) insertBack(results, ppm);
}
//get next path placemark
ppm = nextElement(&iter);
}
return results;
}

### Annotations and Justifications:

//make sure function parameters are up to spec
if (doc == NULL) return NULL;
if (len < 0) return NULL;
if (delta < 0) return NULL;

- This code fragment makes sure that all function parameters do not violate the function specifications. If any specification is violated, the function returns NULL as expected.

//make sure doc has path placemarks
if (doc->pathPlacemarks == NULL) return NULL;
if (getLength(doc->pathPlacemarks) == 0) return NULL;

- This code fragment makes sure that the KML struct contains Path Placemarks, if not the function returns NULL as expected since the function can't really do anything without any Path Placemarks.

//initialize an empty list (formatting is just for the pdf's sake)
List *results = initializeList(
&pathPlacemarkToString, &deleteDataDummy, &comparePathPlacemarks);

//create iterator of path placemarks and get first element from list
ListIterator iter = createIterator(doc->pathPlacemarks);
PathPlacemark *ppm = nextElement(&iter);

//set max/min length based on len +/- delta
double max_len = len + delta;
double min_len = len - delta;

- This code fragment initializes the list of results that will ultimately be returned, as well as the list iterator that will be used to iterate through all paths. We also initialize the maximum and minimum lengths based on the provided length and delta so that we can find matching results.

//iterate through path placemarks
while (ppm != NULL)
{
//get current path total distance
double dist = getPathLen(ppm);

//make sure getPathLen() does not return 0 since that means an error occured
if(dist > 0)
{
//if the distance between two lengths is within the tolerance,
//they are considered equal and the path placemark is added as a result
if(dist >= min_len && dist <= max_len) insertBack(results, ppm);
}
//get next path placemark
ppm = nextElement(&iter);
}
return results;
}

- This final code fragment iterates through the Path Placemark list and attempts to populate the results list by first getting the length of each path using haversines formula. If the length returned is greater than 0 (0 = error), the function checks to see if the returned length is within the inclusive range of min_len and max_len, if that is the case, the path is added to the results list. Finally, the function returns the list even if it might be empty.

I believe that my approach in writing this function is correct since it follows the function specification properly and does the job in a concise and legible manner that should be easy to follow by just looking at the code, which is why I wrote somewhat short annotations for this function. 

## bool validateKML(const KML *doc, const char *schemaFile):

- Function Location:
    - This function can be found in src/KMLParser.c starting at line 652 in Assignment 2 or at line 653 in Assignment 3.

- Function Purpose:
    - The purpose of this function is to make sure that the contents of the KML struct that has been edited do not go against any of the specifications laid out in KMLHelpers.h to ensure that nothing is wrong with our KML struct. Once the function has made sure that the contents of the KML struct are up to spec, it is then validated against the schema file to make sure that the contents of the KML struct do not go against the general specifications of the KML format. If the KML struct is successfully validated it, the function returns true, else it returns false.

- My Implementation:

bool validateKML(const KML *doc, const char* schemaFile)
{
if(doc == NULL) return false;
if(schemaFile == NULL) return false;
if(schemaFile[0] == '\0') return false;

ListIterator iter;

//validate all namespaces
if(doc->namespaces == NULL) return false;
iter = createIterator(doc->namespaces);
XMLNamespace *ns = nextElement(&iter);
while(ns != NULL)
{
//make sure namespace->value is up to spec
if(ns->value == NULL) return false;
if(strcmp(ns->value, "") == 0) return false;
ns = nextElement(&iter);
}

//validate all stylemaps
if(doc->styleMaps == NULL) return false;
iter = createIterator(doc->styleMaps);
StyleMap *stylemap = nextElement(&iter);
while(stylemap != NULL)
{
//make sure stylemap is up to spec
if(stylemap->id == NULL ) return false;
if(strcmp(stylemap->id, "") == 0) return false;

stylemap = nextElement(&iter);
}

//validate all styles
if(doc->styles == NULL) return false;
iter = createIterator(doc->styles);
Style *style = nextElement(&iter);
while(style != NULL)
{
//check if style is valid according to KMLParser.h specs
if(style->id == NULL || style->colour == NULL) return false;
if(strcmp(style->id, "") == 0 || strcmp(style->colour, "") == 0) return false;
style = nextElement(&iter);
}

//validate all point placemarks
if(doc->pointPlacemarks == NULL) return false;
iter = createIterator(doc->pointPlacemarks);
PointPlacemark *pointPlacemark = nextElement(&iter);
while(pointPlacemark != NULL)
{
//check if point placemark is up to spec
if(pointPlacemark->point == NULL) return false;
if(pointPlacemark->otherElements == NULL) return false;

//check if point struct is up to spec
Point *point = pointPlacemark->point;
if (point->coordinate == NULL) return false;
if (point->otherElements == NULL) return false;

//validate KML elements in pathPlacemark->otherElements list
ListIterator elemIter = createIterator(pointPlacemark->otherElements);
KMLElement *elem = nextElement(&elemIter);
while(elem != NULL)
{
if(elem->name == NULL || elem->value == NULL) return false;
if(elem->name[0] == '\0' || elem->value[0] == '\0') return false;
elem = nextElement(&elemIter);
}

//validate KML elements in point->otherElements list
elemIter = createIterator(point->otherElements);
elem = nextElement(&elemIter);
while(elem != NULL)
{
if(elem->name == NULL || elem->value == NULL) return false;
if(elem->name[0] == '\0' || elem->value[0] == '\0') return false;
elem = nextElement(&elemIter);
}

pointPlacemark = nextElement(&iter);
}

//validate all path placemarks
if(doc->pathPlacemarks == NULL) return false;
iter = createIterator(doc->pathPlacemarks);
PathPlacemark *pathPlacemark = nextElement(&iter);
while(pathPlacemark != NULL)
{
//check if path placemark is up to spec from KMLParser.h
if(pathPlacemark->pathData == NULL) return false;
if(pathPlacemark->otherElements == NULL) return false;

//check if line struct is up to spec
Line *pathData = pathPlacemark->pathData;
if(pathData->coordinates == NULL) return false;
if(pathData->otherElements == NULL) return false;
if(getLength(pathData->coordinates) < 2) return false;

//validate KML elements in pathPlacemark->otherElements list
ListIterator elemIter = createIterator(pathPlacemark->otherElements);
KMLElement *elem = nextElement(&elemIter);
while(elem != NULL)
{
if(elem->name == NULL || elem->value == NULL) return false;
if(elem->name[0] == '\0' || elem->value[0] == '\0') return false;
elem = nextElement(&elemIter);
}

//validate KML elements in pathData->otherElements list
elemIter = createIterator(pathData->otherElements);
elem = nextElement(&elemIter);
while(elem != NULL)
{
if(elem->name == NULL || elem->value == NULL) return false;
if(elem->name[0] == '\0' || elem->value[0] == '\0') return false;
elem = nextElement(&elemIter);
}

pathPlacemark = nextElement(&iter);
}

//once we know that the contents of the KML struct are valid,
//we turn the struct into an xmlDoc and validate the tree against the schemaFile
xmlDoc *temp = KMLtoXmlDoc(doc);
if (temp == NULL) return false;
int valid = validateXmlDoc(temp, schemaFile);

// if doc is not valid
if (valid != 0)
{
xmlFreeDoc(temp);
/*
*Free the global variables that may
*have been allocated by the parser.
*/

xmlDictCleanup();
xmlCleanupParser();
return false;
}

xmlFreeDoc(temp);

return true;
}

### Annotations and Justifications:
    

if(doc == NULL) return false;
if(schemaFile == NULL) return false;
if(schemaFile[0] == '\0') return false;

ListIterator iter;

- At the beginning of the function I make sure that the KML doc is not NULL and I also ensure that the schema file is not NULL or just an empty string since if any of these are true we should return false and not waste any time validating anything. After these checks, I define an iterator "iter" that will be used throughout the function to iterate through the many lists that exist within a KML struct.

//validate all namespaces
if(doc->namespaces == NULL) return false;
iter = createIterator(doc->namespaces);
XMLNamespace *ns = nextElement(&iter);
while(ns != NULL)
{
//make sure namespace->value is up to spec
if(ns->value == NULL) return false;
if(strcmp(ns->value, "") == 0) return false;
ns = nextElement(&iter);
}

 - The block of code above iterates through and validates all namespaces that exist within the KML struct and makes sure that the namespaces abide by all constraints defined within KMLParser.h. If a constraint is violated then we immediately return false since we know the KML struct is not valid. If the list containing the namespaces is NULL, these checks are ignored and the function returns false since the namespace list cannot be NULL as per KMLParser.h.
    

//validate all stylemaps
if(doc->styleMaps == NULL) return false;
iter = createIterator(doc->styleMaps);
StyleMap *stylemap = nextElement(&iter);
while(stylemap != NULL)
{
//make sure stylemap is up to spec
if(stylemap->id == NULL ) return false;
if(strcmp(stylemap->id, "") == 0) return false;

stylemap = nextElement(&iter);
}

- The block of code above iterates through and validates all StyleMaps that exist within the KML struct and makes sure that the StyleMaps abide by all constraints defined within KMLParser.h. If the id is NULL we return false, and we do the same if the id is an empty string. If the list containing the StyleMaps is NULL, these checks are ignored and the function returns false since the style list cannot be NULL as per KMLParser.h.

//validate all styles
if(doc->styles == NULL) return false;
iter = createIterator(doc->styles);
Style *style = nextElement(&iter);
while(style != NULL)
{
//check if style is valid according to KMLParser.h specs
if(style->id == NULL || style->colour == NULL) return false;
if(strcmp(style->id, "") == 0 || strcmp(style->colour, "") == 0) return false;
style = nextElement(&iter);
}

- The block of code above iterates through and validates all styles that exist within the KML struct and makes sure that the styles abide by all constraints defined within KMLParser.h. If the id or color are NULL we return false, and we do the same if they are empty strings. If the list containing the styles is NULL, these checks are ignored and the function returns false since the style list cannot be NULL as per KMLParser.h.

//validate all point placemarks
if(doc->pointPlacemarks == NULL) return false;
iter = createIterator(doc->pointPlacemarks);
PointPlacemark *pointPlacemark = nextElement(&iter);
while(pointPlacemark != NULL)
{
//check if point placemark is up to spec
if(pointPlacemark->point == NULL) return false;
if(pointPlacemark->otherElements == NULL) return false;

//check if point struct is up to spec
Point *point = pointPlacemark->point;
if (point->coordinate == NULL) return false;
if (point->otherElements == NULL) return false;

//validate KML elements in pathPlacemark->otherElements list
ListIterator elemIter = createIterator(pointPlacemark->otherElements);
KMLElement *elem = nextElement(&elemIter);
while(elem != NULL)
{
if(elem->name == NULL || elem->value == NULL) return false;
if(elem->name[0] == '\0' || elem->value[0] == '\0') return false;
elem = nextElement(&elemIter);
}

//validate KML elements in point->otherElements list
elemIter = createIterator(point->otherElements);
elem = nextElement(&elemIter);
while(elem != NULL)
{
if(elem->name == NULL || elem->value == NULL) return false;
if(elem->name[0] == '\0' || elem->value[0] == '\0') return false;
elem = nextElement(&elemIter);
}

pointPlacemark = nextElement(&iter);
}

- The very long block of code above may seem more intricate than the previous blocks of code but it technically does the exact same thing. This code fragment first checks to make sure the Point Placemark list is not NULL since KMLParser.h states that the list should never be NULL. After that, we iterate through all Point Placemarks and check their constraints as well as the constraints of it's sub-structures (Lists, KMLElements, and Points). If anything is found that violates any constraints defined by KMLParser.h, the function will immediately return false since there is nothing that has to be freed and we know that the KML struct is not up to spec since we discovered a discrepancy (this could be a NULL variable or an empty string variable). 

//validate all path placemarks
if(doc->pathPlacemarks == NULL) return false;
iter = createIterator(doc->pathPlacemarks);
PathPlacemark *pathPlacemark = nextElement(&iter);
while(pathPlacemark != NULL)
{
//check if path placemark is up to spec from KMLParser.h
if(pathPlacemark->pathData == NULL) return false;
if(pathPlacemark->otherElements == NULL) return false;

//check if line struct is up to spec
Line *pathData = pathPlacemark->pathData;
if(pathData->coordinates == NULL) return false;
if(pathData->otherElements == NULL) return false;
if(getLength(pathData->coordinates) < 2) return false;

//validate KML elements in pathPlacemark->otherElements list
ListIterator elemIter = createIterator(pathPlacemark->otherElements);
KMLElement *elem = nextElement(&elemIter);
while(elem != NULL)
{
if(elem->name == NULL || elem->value == NULL) return false;
if(elem->name[0] == '\0' || elem->value[0] == '\0') return false;
elem = nextElement(&elemIter);
}

//validate KML elements in pathData->otherElements list
elemIter = createIterator(pathData->otherElements);
elem = nextElement(&elemIter);
while(elem != NULL)
{
if(elem->name == NULL || elem->value == NULL) return false;
if(elem->name[0] == '\0' || elem->value[0] == '\0') return false;
elem = nextElement(&elemIter);
}

pathPlacemark = nextElement(&iter);
}

- This code fragment works just like the previous one but instead it exists to validate all Path Placemarks instead of Point Placemarks. If any constraint is found to be violated the function will immediately return since as stated previously, there is no memory to be freed and we know that the KML struct is no longer valid. Just as the previous code block, we have to validate the sub-structures that exist within a Path Placemark and make sure none of their constraints are violated as well. 

//once we know that the contents of the KML struct are valid,
//we turn the struct into an xmlDoc and validate the tree against the schemaFile
xmlDoc *temp = KMLtoXmlDoc(doc);
if (temp == NULL) return false;
int valid = validateXmlDoc(temp, schemaFile);

// if doc is not valid
if (valid != 0)
{
xmlFreeDoc(temp);
/*
*Free the global variables that may
*have been allocated by the parser.
*/

xmlDictCleanup();
xmlCleanupParser();
return false;
}

xmlFreeDoc(temp);

return true;
}

- Since all contents of the KML struct have been validated against the constraints defined in KMLParser.h, we can now convert the KML struct to an xmlDoc pointer so that we can validate the KML contents against the schema file provided. If KMLtoXMLDoc() fails at any point, it will return NULL, and the function will return false, however this should not be possible unless something critical fails. Once the KML struct is converted to an xmlDoc pointer, it is validated against the schema file using the validateXmlDoc() helper function and the function then frees all memory that was allocated by the libxml2 library using specific libxml2 functions. In the end, the function either return true or false based on the return value of validateXmlDoc().

I believe that my approach in writing this function was the most logical one since if any kind of error/discrepancy is encountered along the way, the function will immediately return false since we know that something is wrong with the KML struct and therefore the KML struct is not to be considered as valid. This function has to be robust since if we want to create/edit any KML files using our library, they have to be considered valid to be functional everwhere. Therefore, my function checks the contents of the KML struct itself and then it validates the contents against the schema file, just as the function specification dictates in the assignment.