s5ashraf_design_p5.txt

CLASS DESIGN

The classes I implemented were the TimeSeries class. This class is where I carefully abstracted away the logic that the front facing cpp file, (InputHandler.cpp).
This mean't stuff like the size of the arrays as well as the capacities were all in private variables. Even the count of the valid data points was a private variable. The only thing that was exposed in that front was 
the function, emptyDataSet() which kind of acts like a way that the input handler can know if there is any valid, to adhere to project requirements (to print failure when there is no valid data).
I also tried making helper functions that were independent of the rest of the methods in the time series class to help handle the resizing of the dynamic array as per the project requirements. This allowed for an easier debugging process
In addition I for project 2's purposes I made it so that there is a country class that contains a linked list of time series as well as the string for the country name as well as code. This means that all the data for that country is isolated in
the sense that the country class could simply be thrown out when we are trying to load a new country, or when we are going to start storing multiple countries, at that point we can have a data structure that contains multiple country objects. 
Another piece of class design that really makes my project stand out I feel like would be the organization between the actual implementation of the code 
from that of the actual helper functions that are kept private for the class. This helps greatly when debugging since I exactly know which functions 
are responsible for actually printing and which ones are responsible for the implementation of the code. We will now talk about the implementation of the Binary Search tree.
The binary search tree implementation consists of the class BST as well as the BST_Node class. The Binary Search Tree is made up of these BST_Nodes which are crucial for the project.
These BST_Nodes have a contains relationship with the BST class, as we well as a has relationship with the Time Series class. For my project 3 implementation, what I did have is an array of 512, which was made up of country objects. 
These objects were stored in sequential order, meaning that there is no optimal storing happening. The difference that we had for project 4 is that we had HASHING being done, instead of sequentially adding to the array, i.e., adding to the end of the array. 
The hashing implementation allowed us to get an O(1) lookup. This is because we no longer had to iterate through the whole array to search for a certain country, instead, we just used the hashing function to access. 
In addition, I added some private helper methods in order for the hashing implementation to be modular for our array that we had in p3. 
Finally, what I also added was an existence method inside the countries class in order to assist with the lookup of the hashing as well. The hashing mechanism not only improved the efficiency but also ensured that there was no linear search,
as the key-value pairs enabled direct access, leveraging the hash table structure. Now for project 5, I added a new class called the graph class. This class is responsible for storing all the information related to the graph structure needed for this project.
Inside the graph class, I used an unordered_map, where the key is the country code and the value is a G_Node. The G_Node class contains a pointer to the actual Country object, as well as another unordered_map. 
This second map stores neighbouring country codes as keys and has an unordered_set of relationship_tuple entries as the values. These relationship_tuple entries represent all the different comparisons that exist between the two countries.
The graph class is the one that handles all the graph-related commands like INITIALIZE, UPDATE_EDGES, ADJACENT, PATH, and RELATIONSHIP. All of these are handled inside the graph class directly. 
I also made sure to add some private helper functions that make the code more modular and easier to debug. These helpers are responsible for internal logic, like checking if two countries meet the same relationship criteria or accessing internal data.
The relationship_tuple class is used to represent a single comparison. It stores the series code, threshold, and the comparison type. This means that all the logic related to the comparisons is kept inside this class, which makes it cleaner and allows the graph class to stay focused on managing the structure and operations of the graph itself.


I decided to only write the TimeSeries class, since that was the only class that was require by the project and wrote a file called InputHandler.cpp which contained the main function. This was the file that implemented
all the helper methods for input and output. A route that I could have taken is making a template for my resizable array. However, I did make sure that I kept the logic pertaining to the resizing was as separated as possible. This meant
that there was no pushing or popping logic as well as memory management logic inside any of the time series functions that were required, and all of that logic was abstracted away in private methods. 
This allowed for a good time in debugging. Another thing that I made sure to do is split up all the calculations term by term. Although it does require for the computer to store more values into the memory, it does allow 
for an easier time debugging since now I can calculate out the expected value, then breakpoint on the singular terms and see if one of the terms is being miscalculated or not. It is a lot easier to debug then 
placing a lot of brackets together and calculating out the m and b values like that. Also it calls for a cleaner looking code and does not cause any BEDMAS errors. Yet again I could have made a template for the linked list implementation 
however I decided to keep it simple for now. Another thing that I would say that I could have done differently is used a different data structure, instead of a linked list, however I decided to use a linked list it is 
a lot easier to add as well as remove elements from the list. Something that requires some justification is the load method that I made use of from a previous project, project 1. This method was used to load the data from the csv
into the time series which was very convenient. This will allow me to use similar logic for the load in project 3.
Some justification for this project would be for the use of storing an array of time series. This allowed me to have all the perks of the time series 
class that we developed at the start of the project, mainly in project one. An alternative that I could have done is instead had some sort of mapping 
between country as well as the time series, maybe another class and then storing that within the array would be effective however I stayed away from that 
due to time constraints. I could have made a templated hastable but it wouldn't make sense since the current table that we are making is specific to the dataset that we have. I just kept the 
hashtable in the current countries class due to the fact that the hashtable contains individual countries. 

RUNTIME ANALYSIS

The worst-case runtime for the ADJACENT command is determined by the number of neighbour lookups and the operations performed within the loop. Let n be the number of countries in the graph, and let k be the number of neighbours for the given country.
Firstly, the command calls a helper function to retrieve the list of neighbouring countries. This results in a loop that runs k times, where k is the number of neighbours for the country being queried.
Inside this loop, each iteration performs a constant-time operation, such as appending a name to a result vector or printing it. These O(1) operations do not scale with either k or n and therefore do not contribute meaningfully to the time complexity. As a result, they do not add to the upper bound.
Secondly, during each of the k iterations, a helper function is called to retrieve the country name using the country code. This operation relies on an unordered_map. 
In the worst-case, due to collisions and depending on the collision resolution strategy of the underlying implementation of std::unordered_map, this lookup may take up to O(n) time.
Since we are doing this lookup k times, one for each neighbour, and each lookup may take up to O(n), the total time complexity becomes O(k * n). 
There also exists an unordered_set storing the relationships for each edge, but since it is not accessed or modified in the ADJACENT command, it has no effect on the upper bound.
Therefore, the overall worst-case runtime for the ADJACENT command comes out to be O(k * n).