#include "MyDinosaurDatabase.hpp$"$

#include

#include

namespace CPSC$131$::Databases::Dinosaurs

$\{$

MyDinosaurDatabase::MyDinosaurDatabase$()$

$\{$

$///$ Insert a Dinosaur record into the database

void MyDinosaurDatabase::insert$($const Dinosaur& dino$)$

$\{$

$//$ TODO: Your code here

$\}$

$///$ Check if a Dinosaur record exists in the database

bool MyDinosaurDatabase::exists$($const Dinosaur& dino$)$ const

$\{$

$//$ TODO: Your code here

return false;

$\}$

$/**$

$*$ Return a Dinosaur record from the database to the caller

$*$ For all methods here that take an incoming Dinosaur object,

$*$ the caller expects to create an empty Dinosaur object

$*$ with $***$only$***$ the ID field filled out.

$*$ When the Dinosaur class has its comparison operators

$*$ overloaded properly, the BST will be able to locate

$*$ the correct Dinosaur entry in the tree using just the ID field. $*/$

Dinosaur& MyDinosaurDatabase::find$($const Dinosaur& dino$)$

$\{$

$//$ TODO: Your code here

return $*($new Dinosaur$)$;

$\}$

$///$ Remove a Dinosaur entry from the database.

void MyDinosaurDatabase::remove$($const Dinosaur& dino$)$

$\{$

$//$ TODO: Your code here

$\}$

$///$ Iterate all Dinosaur records using pre$-$order traversal.

void MyDinosaurDatabase::traversePreOrder

$($ std::function$)>$ callback $)$

$\{$

$//$ TODO: Your code here

$\}$

$/*$

$*$ Iterate Dinosaur records with in$-$order traversal

$*($const version$)$

$*/$

void MyDinosaurDatabase::traverseInOrder

$($ std::function$$ bool$($const DinoTree&$,$ std::shared$\_$ptr$)>$ callback $)$ const

$\{$

$//$ TODO: Your code here

$\}$

$/**$

$*$ Iterate Dinosaur records with in$-$order traversal

$*($non$-$const version$)$

$*/$

void MyDinosaurDatabase::traverseInOrder

$($ std::function$$ bool$($DinoTree&$,$ std::shared$\_$ptr$)>$ callback $)$

$\{$

$//$ TODO: Your code here

$\}$

$/**$

$*$ Iterate Dinosaur records with post$-$order traversal

$*($non$-$const$)$

$*/$

void MyDinosaurDatabase::traversePostOrder

$($ std::function$$ bool$($DinoTree&$,$ std::shared$\_$ptr$)>$ callback $)$

$\{$

$//$ TODO: Your code here

$\}$

$/**$

$*$ Iterate Dinosaur records with level$-$order traversal

$*($non$-$const$)$

$*/$

void MyDinosaurDatabase::traverseLevelOrder

$($ std::function$$ bool$($DinoTree&$,$ std::shared$\_$ptr$)>$ callback $)$

$\{$

$//$ TODO: Your code here

$\}$

$///$ Return the computed height of the database's internal BST

size$\_$t MyDinosaurDatabase::computeHeight$()$

$\{$

$//$ TODO: Your code here

return $0$;

$\}$

$///$ Return the number of records in the database

size$\_$t MyDinosaurDatabase::size$()$

$\{$

$//$ TODO: Your code here

return $0$;

$\}$

$///$ Return true if the database if empty; false otherwise

bool MyDinosaurDatabase::empty$()$

$\{$

$//$ TODO: Your code here

return false;

$\}$

$///$ Clear the entire database

void MyDinosaurDatabase::clear$()$

$\{$

$//$ TODO: Your code here

$\}$

$///$ Return a reference to the internal binary search tree

DinoTree& MyDinosaurDatabase::tree$()$

$\{$

$//$ TODO: Your code here

return $*($new DinoTree$)$;

$\}$

$\}```$

Class MyBST

MyBST$()$;

MyBST$($const MyBST& other$)$;

~MyBST$()$;

void insert$($T value$)$;

T& find$($T value$)$;

std::shared$\_$ptr find$\_$node$($T value$)$ const;

void remove$($T value$)$;

void remove$($std::shared$\_$ptr node$)$;

bool exists$($T value$)$ const;

std::shared$\_$ptr getRoot$()$ const;

bool isRoot$($const std::shared$\_$ptr& node$)$ const;

bool isInternal$($const std::shared$\_$ptr& node$)$ const;

bool isExternal$($const std::shared$\_$ptr& node$)$ const;

bool isLeaf$($const std::shared$\_$ptr& node$)$ const;

bool isParent$($const std::shared$\_$ptr& node$)$ const;

bool hasParent$($const std::shared$\_$ptr& node$)$ const;

size$\_$t getChildCount$($const std::shared$\_$ptr& node$)$ const;

bool hasOneChild$($const std::shared$\_$ptr& node$)$ const;

bool hasTwoChildren$($const std::shared$\_$ptr& node$)$ const;

bool isLeftChild$($const std::shared$\_$ptr& node$)$ const;

bool hasLeftChild$($const std::shared$\_$ptr& node$)$ const;

bool isRightChild$($const std::shared$\_$ptr& node$)$ const;

$``````$

bool hasRightChild$($const std::shared$\_$ptr& node$)$ const;

void traversePreOrder$($std::function$)>$ callback$)$;

void traverseInOrder$($std::function$)>$ callback$)$ const;

void traverseInOrder$($std::function$)>$ callback$)$;

void traversePostOrder$($std::function$)>$ callback$)$;

void traverseLevelOrder$($std::function$)>$ callback$)$ const;

void traverseLevelOrder$($std::function$)>$ callback$)$;

void clear$()$;

bool empty$()$ const;

size$\_$t size$()$ const;

std::shared$\_$ptr getDeepestLeaf$()$;

size$\_$t computeHeight$()$;

std::string renderToDot$()$ const;

$```$