TASK 1 QUADTREES

As the name of the data structure entails ‘Quadtree’. A quadtree is a tree structure where a parent node can hold four and only four children nodes. These children nodes are represented as the north-west, north-east, south-west and south-east nodes. Usually, a key is decomposed into two parts, expressed in x and y coordinates. Therefore, a node contains four pointers for the children nodes and a point which is then turned into x and y coordinates and a value. The implementation of this data structure vitally contains two classes, quadtree and node. Although, the name of the classes speak for themselves, the quadtree class essentially creates the quadtree in question taking instances of the node class when inserting a leaf into the quadtree. A node object contains both the x and y coordinates, along with the status, which can be any value stored in the node. The visualisation, or representation processes of the quadtree take place in the bnw and boolean classes, which create a black and white, and boolean output of the quadtree respectively. Both classes instead of continuously converting each child node into their respective visualisation. The quadtree is parsed line for line and then printed in a separate function of the same class. When parsing the quadtree inserts a new node of the respective type of representation to itself, which is then printed.

TASK 3 BITWISE OPERATORS

Design Overview

Although not boasting as many object-oriented principles as the previous tasks, the implementation of the task in question relies heavily on operator overloading and class constructor overloading. A class MyUint was created which holds multiple definitions, such as string, char, long long and integer. All of the integer operators defined in the C++ documentation are overloaded with function signatures accepting two MyUints and another definition accepting one MyUint value and an integer value. Most of the integer operators are handled with bitwise operators, which are defined earlier in the class.

Technical Overview and Limitations Bitwise Operators: And Operator (&) was tackled by comparting the value of argc and argv at the same point. If both of the values in the arguments are ‘1’, the output vector value of the location ‘i’ is set to 1. If the values include a 0, the output vector element is set to 0. Or Operator (|) was tackled similarly to the and operator, but if the values at the respective vector location contain at least one 1, the output value is set to 1. Otherwise, the output value is set to 0. The XOR Operator (^) compares the vector values, and if the values are unique, the output vector element is set to 1. Otherwise, the output vector value is set to 0. The shift operators (<<) and (>>) only take one argument in the function signature. The output vector copies the current vector value but at an incremented or decremented value accordingly. Similarly, the NOT Operator (~) takes only one argument and quite simply, the output vector’s value is set to be the opposite of the current argument value. Integer Operations Addition: The function accepts two arguments, two MyUints or one MyUint and an integer when overloading. The overloading occurs on all integer operations. The function is carried out by iterating through the size of the arguments passed. For each iteration the current value ‘i’ being iterated is compared to be greater than the argument size. If the value is greater, the carry is set to be equal to the current value of the argument. If the value ‘i’ is not greater, the output object is pushed back with a carry modulated with base. The base is a value set in the beginning of the class, referring to base 9. After that, the carry is set to be equal to the base. After iteration is finished, if there is a carry, the output object ‘res’ is pushed back with carry as an argument, and then the output object ‘ret’ is returned. For the overloaded function constructer, the + operator is called to a type casted integer, and the above is carried out. Subtraction: The main algorithm of the function is set in the iterator. The iteration is carried out till the size of the first argument, the argument that is being subtracted. The carry of the subtraction is set to be the current value of the first argument in the iteration, subtracted by the second argument if the current value of ‘i’ is greater than the size of the second argument. Else the first argument is subtracted by 0 and the carry is set to -1. After the iteration is fully completed, the output object ‘ret’ is returned. Division and Modulo: In the contrary to the other operators, the main functionality occurs in a decrementing iteration from the first argument’s size -1 until the iterated value is 0. The function continuously compares, the left-hand side and the right-hand side. The left-hand side is initially set to 0, and the right-hand side is the base described earlier. If the left-hand size is less than or equal to the right-hand side, a temporary value ‘point’ is set to be the left hand side and the right hand size left shifted once. After that, if the second integer multiplied by the point is greater than 0, another value is set to be equal to point and the right-hand side is set to be the point -1. If the multiplication is greater than 0, the left-hand side is set to be point +1. After the while conditions are met, the output object ‘ret’ is returned. The modulo operator returns the remainder rather than the rounded value of the division operator. Multiplication: The multiplication operator takes influence from Booth’s multiplication algorithm, which in essence is an iteration of the first argument’s size -1 with a continuous addition for the size of the second argument.