ass5-2/BinarySearchTree.cpp
ass5-2/BinarySearchTree.cpp
modified from Frank M. Ca
ano and Timothy M. Henry.
modified by Matthieu Blanchet and Shashank Chennapragada
#include "BinarySearchTree.h"
#include
#include
using namespace std;
BinaryNode constructor w/ item
Pre: none
Post: a binaryNode containing anItem is created
BinaryNode::BinaryNode(int anItem) : item(anItem) {}
====================== Constructors/Destructors=============================
Default constructo
Pre: none
Post: a Threaded binary search tree (TBST) has been created
BinarySearchTree::BinarySearchTree() = default;
Constructor to generate nodes , generates n nodes from with values of 1 ,2,.
.. n, adds these nodes to the binary tree such that the tree is balanced!
Pre: nodeA
is number of nodes to add
Post: a TBST had been created with n nodes
BinarySearchTree::BinarySearchTree(int nodeA
) {
if (nodeA
> 0) {
vecto
int> nodes(nodeA
);
for (int i = 0; i < nodeA
; i++) {
nodes[i] = i + 1;
}
addNodes(nodes, 0, nodeA
- 1);
}
}
Recursive helper function for constructor that adds nodes from a vector to
the tree
Pre: the TBST is empty,nodes contains the nodes to add, front is the
front of the vector, back is the back of the vecto
Post: the TBST contains the nodes in "nodes"
void BinarySearchTree::addNodes(vecto
int> nodes, int front, int back) {
ase case: if back is lower then front, the a
ay is empty
if (back >= front) {
int midpoint = (back + front) / 2;
add(nodes[midpoint]);
add the halfway point
addNodes(nodes, front, midpoint - 1);
addNodes(nodes, midpoint + 1, back);
}
}
Copy constructo
Pre: tree is a TBST
Post: our TBST is a deep copy of "tree"
BinarySearchTree::BinarySearchTree(const BinarySearchTree &tree) {
copyTree(tree.rootPtr);
}
Recursive helper function for the copy constructo
Pre: nodeTreePtr is the tree we need to copy values from
Post: values from nodeTreePtr are copied to our TBST
void BinarySearchTree::copyTree(const BinaryNode* nodeTreePtr) {
if (nodeTreePtr != nullptr) {
int copyData = nodeTreePtr->item;
add(copyData);
if (!nodeTreePtr->threadLeft) {
copyTree(nodeTreePtr->leftChildPtr);
}
if (!nodeTreePtr->threadRight) {
copyTree(nodeTreePtr-
ightChildPtr);
}
}
}
Destructo
Pre: none
Post: the TBST's heap memory has been deallocated
BinarySearchTree:: ~BinarySearchTree() {
destroyTree(rootPtr);
}
Recusive helper function for the destructo
Pre: subtreePtr is the subtree we want to delete
Post: subtreePtr and its children have been deleted
void BinarySearchTree::destroyTree(BinaryNode* subTreePtr) {
if (subTreePtr != nullptr) {
if (!subTreePtr->threadLeft || !subTreePtr->threadRight) {
if (!subTreePtr->threadLeft) {
destroyTree(subTreePtr->leftChildPtr);
}
if (!subTreePtr->threadRight) {
destroyTree(subTreePtr-
ightChildPtr);
}
delete subTreePtr;
} else if (subTreePtr->threadLeft && subTreePtr->threadRight) {
delete subTreePtr;
}
}
}
====================== end of Constructors/destructors=====================
Adds a node to the tree, also updates the threads in the tree as necessary
Pre: newData is the int to insert in our tree
Post: our tree contains the node
ool BinarySearchTree::add(const int& newData) {
BinaryNode* newPtr = new BinaryNode(newData);
return placeNode(rootPtr, newPtr);
}
Recursive helper function for add, determines where to place a node
Pre: subTreePtr is the tree to add the node, newNodePtr is the node to add
Post: newNodePtr has been added to subTreePt
ool BinarySearchTree::placeNode(BinaryNode *subTreePtr,
BinaryNode *newNodePtr) {
if (subTreePtr == nullptr){
if there's no root
rootPtr = newNodePtr;
set the root
rootPtr->threadLeft = true;
rootPtr->threadRight = true;
return true;
} else if(subTreePtr->item > newNodePtr->item) {
if(subTreePtr->threadLeft) {
base case there's a right thread!
set the new node to have the thread
newNodePtr->threadLeft = true;
newNodePtr->leftChildPtr = subTreePtr->leftChildPtr;
newNodePtr->threadRight = true;
newNodePtr-
ightChildPtr = subTreePtr;
subTreePtr->threadLeft = false;
subTreePtr->leftChildPtr = newNodePtr;
return true;
}
return placeNode(subTreePtr->leftChildPtr, newNodePtr);
not at the end
} else {
subtree <= newNode
base case there's a right thread!
if (subTreePtr->threadRight) {
set the new node to have the thread
newNodePtr->threadRight = true;
newNodePtr-
ightChildPtr = subTreePtr-
ightChildPtr;
newNodePtr->threadLeft = true;
newNodePtr->leftChildPtr = subTreePtr;
subTreePtr->threadRight = false;
subTreePtr-
ightChildPtr = newNodePtr;
return true;
}
return placeNode(subTreePtr-
ightChildPtr, newNodePtr);
}
return false;
}
Removes a value from a threaded binary search tree,
returns true if successful, false otherwise
Pre: target is the int to remove from our TBST
Post: the target has been removed from our TBST
ool BinarySearchTree::remove( const int& target) {
bool successful = false;
removeValue(rootPtr, target, nullptr, successful, false);
return successful;
}
Recursive helper method for remove(), recursively locates the node to delete
and calls
Pre: subTreePtr is the tree where we want to remove target, parent is the
parent of subTreePtr, success indicates if we have removed the node co
ectly
isLeft indicates if the parent is to the left of the child (true if so,
false otherwise)
Post: target has been removed from subTreePt
BinaryNode* BinarySearchTree::removeValue(BinaryNode* subTreePtr, int target,
BinaryNode* parent, bool& success,
bool isleft) {
BinaryNode* tempPtr = nullptr;
probably not necessary leave till testing
if (subTreePtr == nullptr) {
check if rootptr is initialized
return nullptr;
} else if (subTreePtr->item == target) {
found the target
subTreePtr = removeNode(subTreePtr, isleft, parent);
Remove the item
success = true;
return subTreePtr;
} else if (subTreePtr->threadRight && subTreePtr->threadLeft) {
hit a leaf without finding the target
return subTreePtr;
} else if (subTreePtr->item > target) {
Search the left subtree
tempPtr = removeValue(subTreePtr->leftChildPtr, target, subTreePtr,
success, false);
subTreePtr->leftChildPtr = tempPtr;
return subTreePtr;
} else {
Search the right subtree
tempPtr = removeValue(subTreePtr-
ightChildPtr, target, subTreePtr,
success , true);
subTreePtr-
ightChildPtr = tempPtr;
return subTreePtr;
}
}
Recursive helper for removeValue()
Pre: RemNode is the node to be deleted, isLeft is the location of the parent
left of remNode if true, right otherwise, parent is the parent of remNode
Post: remNode has been deleted and su
ounding threads have been updated
BinaryNode* BinarySearchTree::removeNode(BinaryNode* remNode, bool isLeft,
BinaryNode* parent) {
BinaryNode* tempPtr;
BinaryNode* tempPtr2;
for rethreading
if ((remNode->threadLeft) && (remNode->threadRight)) {
is N a leaf?
if (isLeft) {
tempPtr = remNode-
ightChildPtr;
pass back the right pointer status
} else {
tempPtr = remNode->leftChildPtr;
pass back the left pointer status
}
if (parent != nullptr) {
if there's a parent, it needs to inherit
the child's threadedness
if (isLeft) {
parent->threadRight = remNode->threadRight;
} else {
parent->threadLeft = remNode->threadLeft;
}
}
delete remNode;
remNode = nullptr;
return tempPtr;
} else if ((remNode->threadRight) || (remNode->threadLeft)) {
N has 1 child
C replaces N as the child of N's parent
is the child in the left
anch?
if (remNode->threadRight) {
tempPtr = remNode->leftChildPtr;
tempPtr2 = tempPtr;
while (tempPtr2-
ightChildPtr != remNode) {
runs till tempPtr2 points w/ thread to the Node to be deleted
tempPtr2 = tempPtr2-
ightChildPtr;
}
tempPtr2-
ightChildPtr = remNode-
ightChildPtr;
} else {
child is in the right
anch
tempPtr = remNode-
ightChildPtr;
tempPtr2 = tempPtr;
while (tempPtr2->leftChildPtr != remNode) {
runs till tempPtr2 points w/ thread to the Node to be deleted
tempPtr2 = tempPtr2->leftChildPtr;
}
tempPtr2->leftChildPtr = remNode->leftChildPtr;
}
delete remNode;
remNode = nullptr;
return tempPtr;
needed to reconnect child nodes
} else {
N has two children!
we need to delete the leftmost node of the right node of N
and insert that node's value into N
int val;
bool rightThread;
bool isLeft = true;
tempPtr = removeLeftMostNode(remNode-
ightChildPtr,
val, isLeft, rightThread);
remNode-
ightChildPtr = tempPtr;
if (isLeft) {
should we inherit the right threadedness
remNode->threadRight = rightThread;
}
remNode->item = val;
return remNode;
}
}
Recursive helper for removeNode()
Removes the leftmost node in the left subtree of the node pointed to by
remNode. Sets inorderSuccessor to the value in this node.
Pre: RemNode is the node to be deleted, successor is the value of remNode
once we delete it, isLeft indicates if the parent is left or remNode
rightThread stores the threadedness of remNode once we delete it
Post: remNode has been deleted and su
ounding threads have been updated
we use successor and rightThread in removeNode to update the previous node to
be deleted
BinaryNode* BinarySearchTree::removeLeftMostNode(BinaryNode* remNode,
int& successor, bool& isLeft,
bool& rightThread) {
BinaryNode* tempPtr;
if (remNode->threadLeft) {
this is the leftmost node , grab its item and delete it.
successor = remNode->item;
rightThread = remNode->threadRight;
return removeNode(remNode, isLeft, nullptr);
} else {
isLeft = false;
remNode->threadLeft = remNode->leftChildPtr->threadLeft;
tempPtr = removeLeftMostNode(remNode->leftChildPtr, successor,
isLeft, rightThread);
remNode->leftChildPtr = tempPtr;
return remNode;
}
}
Deletes a tree
Pre: A TBST exists
Post: The TBST has been deleted
void BinarySearchTree::clear() {
destroyTree(rootPtr);
}
Prints out the values of a TBST inorder.
Pre: A TBST exists
Post: The values of the TBST have been printed inorde
void BinarySearchTree::inorderTraverse() const {
BinaryNode* curptr = rootPtr;
while (curptr->leftChildPtr != nullptr) {
go all the way left to start
curptr = curptr->leftChildPtr;
}
cout
curptr->item
" ";
while (curptr-
ightChildPtr != nullptr) {
if (curptr->threadRight) {
are we moving using a thread?
just move forward
curptr = curptr-
ightChildPtr;
} else {
if not using thread then we have moved into a subtree
curptr = curptr-
ightChildPtr;
moved into a subtree, need to check left nodes!
while (!curptr->threadLeft) {
go all the way left
curptr = curptr->leftChildPtr;
}
}
cout
curptr->item
" ";
print
}
cout
endl;
}
__MACOSX/ass5-2/._BinarySearchTree.cpp
__MACOSX/ass5-2/._cmake-build-debug
ass5-2/destroyTree.cpp
ass5-2/destroyTree.cpp
Created by Frank M. Ca
ano and Timothy M. Henry.
Copyright (c) 2017 Pearson Education, Hoboken, New Jersey.
template
void BinaryNodeTree
::
destroyTree(std::shared_pt
BinaryNode subTreePtr)
{
if (subTreePtr != nullptr)
{
destroyTree(subTreePtr–>getLeftChildPtr());
destroyTree(subTreePtr–>getRightChildPtr());
subTreePtr.reset();
Decrement reference count to node
}
end if
}
end destroyTree
__MACOSX/ass5-2/._destroyTree.cpp
ass5-2/getHeightHelper.cpp
ass5-2/getHeightHelper.cpp
Created by Frank M. Ca
ano and Timothy M. Henry.
Copyright (c) 2017 Pearson Education, Hoboken, New Jersey.
templateint BinaryNodeTree::
getHeightHelper(std::shared_pt
BinaryNode subTreePtr) const
{
if (subTreePtr == nullptr)
return 0;
else
return 1 + max(getHeightHelper(subTreePtr–>getLeftChildPtr()),
getHeightHelper(subTreePtr–>getRightChildPtr()));
}
end getHeightHelpe
__MACOSX/ass5-2/._getHeightHelper.cpp
ass5-2/CMakeLists.txt
cmake_minimum_required(VERSION 3.17)
project(ass5)
set(CMAKE_CXX_STANDARD 14)
add_executable(ass5 main.cpp BinarySearchTree.cpp BinarySearchTree.h BinaryNode.h)
__MACOSX/ass5-2/._CMakeLists.txt
ass5-2/simplecompile.sh
#!
in
ash
# To more easily compile and run this program on CSS Linux La
# Lines starting with '$' indicate what is typed on command line
# if you get the following e
or:
# -bash: ./simplecompile.sh:
in
ash^M: bad interpreter: No such file or directory
# run dos2unix to fix it
# $ dos2unix simplecompile.sh
# make this file executable
# $ chmod 700 simplecompile.sh
# redirect the output and stde
from this file to output.txt
# $ ./simplecompile.sh > output.txt 2>&1
#TO ENABLE CLANGTIDY do this EVERYTIME on linux lab: scl enable llvm-toolset-7.0 bash
date
echo "*** compiling with clang++ to create an executable called myprogram"
clang++ --version
clang++ -std=c++11 -Wall -Wextra -Wno-sign-compare *.cpp -g -o myprogram
# echo "*** running clang-tidy using options from .clang-tidy"
clang-tidy --version
clang-tidy *.cpp -- -std=c++11
echo "*** running myprogram"
./myprogram
# valgrind will detect memory leaks
echo "*** running with valgrind"
valgrind --leak-check=full ./myprogram
echo "*** cleaning up, deleting myprogram"
m myprogram
date
__MACOSX/ass5-2/._simplecompile.sh
ass5-2/constructors.cpp
ass5-2/constructors.cpp
Created by Frank M. Ca
ano and Timothy M. Henry.
Copyright (c) 2017 Pearson Education, Hoboken, New Jersey.
templateBinaryNodeTree::BinaryNodeTree() : rootPtr(nullptr)
{
}
end default constructo
templateBinaryNodeTree::
BinaryNodeTree(const ItemType& rootItem)
: rootPtr(std::make_shared(rootItem, nullptr, nullptr))
{
}
end constructo
templateBinaryNodeTree::
BinaryNodeTree(const ItemType& rootItem,
const std::shared_pt
BinaryNodeTree leftTreePtr,
const std::shared_pt
BinaryNodeTree rightTreePtr)
: rootPtr(std::make_shared(rootItem,
copyTree(leftTreePtr–
ootPtr),
copyTree(rightTreePtr–
ootPtr))
{
}
end constructo
templateBinaryNodeTree::
BinaryNodeTree(const BinaryNodeTree& treePtr)
{
rootPtr = copyTree(treePtr.rootPtr);
}
end copy constructo
templatestd::shared_pt
BinaryNode BinaryNodeTree::copyTree(
const std::shared_pt
BinaryNode oldTreeRootPtr) const
{
std::shared_pt
BinaryNode newTreePtr;
Copy tree nodes during a preorder traversal
if (oldTreeRootPtr != nullptr)
{
Copy node
newTreePtr = std::make_shared(oldTreeRootPtr–>getItem(),
nullptr, nullptr);
newTreePtr–>setLeftChildPtr(copyTree(oldTreeRootPtr–>getLeftChildPtr()));
newTreePtr–>setRightChildPtr(copyTree(oldTreeRootPtr–>getRightChildPtr()));
}
end if
Else tree is empty (newTreePtr is nullptr)
return newTreePtr;
}
end copyTree
__MACOSX/ass5-2/._constructors.cpp
ass5-2/create-output.sh
#!
in
ash
# Run this script as `./create-output.sh > output.txt 2>&1`
# How we want to call our executable,
# possibly with some command line parameters
EXEC_PROGRAM="./a.out "
# Timestamp for starting this script
date
MACHINE=""
# Display machine name if uname command is available
if hash uname 2
dev/null; then
uname -a
MACHINE=`uname -a`
fi
# Display user name if id command is available
if hash id 2
dev/null; then
id
fi
# If we are running as a GitHub action, install programs
GITHUB_MACHINE='Linux fv-az'
if [[ $MACHINE == *"${GITHUB_MACHINE}"* ]]; then
echo "====================================================="
echo "Running as a GitHub action, attempting to install programs"
echo "====================================================="
sudo apt-get install llvm clang-tidy clang-format valgrind
fi
# If we are running on CSSLAB and
# clang-tidy is not active, print a message
CSSLAB_MACHINE='Linux csslab'
CLANG_TIDY_EXE='/opt
h/llvm-toolset-7.0
oot
in/clang-tidy'
if [[ $MACHINE == *"${CSSLAB_MACHINE}"* ]]; then
if ! hash clang-tidy 2
dev/null && [ -e "${CLANG_TIDY_EXE}" ] ; then
XXXXXXXXXXecho "====================================================="
XXXXXXXXXXecho "ERROR ERROR ERROR ERROR ERROR ERROR ERROR ERROR ERROR "
XXXXXXXXXXecho "clang-tidy NOT found in path (but is in $CLANG_TIDY_EXE )"
XXXXXXXXXXecho "Add the following command to ~/.bashrc file"
XXXXXXXXXXecho " source scl_source enable llvm-toolset-7.0"
XXXXXXXXXXecho "You can add the command by executing the following line"
XXXXXXXXXXecho " echo \"source scl_source enable llvm-toolset-7.0\"
~/.bashrc"
XXXXXXXXXXecho "====================================================="
fi
fi
# delete a.out, do not give any e
ors if it does not exist
m ./a.out 2
dev/null
echo "====================================================="
echo "1. Compiles without warnings with -Wall -Wextra flags"
echo "====================================================="
g++ -g -std=c++11 -Wall -Wextra -Wno-sign-compare *.cpp
echo "====================================================="
echo "2. Runs and produces co
ect output"
echo "====================================================="
# Execute program
$EXEC_PROGRAM
echo "====================================================="
echo "3. clang-tidy warnings are fixed"
echo "====================================================="
if hash clang-tidy 2
dev/null; then
clang-tidy *.cpp -- -std=c++11
else
echo "WARNING: clang-tidy not available."
fi
echo "====================================================="
echo "4. clang-format does not find any formatting issues"
echo "====================================================="
if hash clang-format 2
dev/null; then
# different LLVMs have slightly different configurations which can
eak things, so regenerate
echo "# generated using: clang-format -style=llvm -dump-config > .clang-format" > .clang-format
clang-format -style=llvm -dump-config
.clang-format
for f in ./*.cpp; do
echo "Running clang-format on $f"
clang-format $f | diff $f -
done
else
echo "WARNING: clang-format not available"
fi
echo "====================================================="
echo "5. No memory leaks using g++"
echo "====================================================="
m ./a.out 2
dev/null
g++ -std=c++11 -fsanitize=address -fno-omit-frame-pointer -g *.cpp
# Execute program
$EXEC_PROGRAM > /dev/null
echo "====================================================="
echo "6. No memory leaks using valgrind, look for \"definitely lost\" "
echo "====================================================="
m ./a.out 2
dev/null
if hash valgrind 2
dev/null; then
g++ -g -std=c++11 *.cpp
# redirect program output to /dev/null will running valgrind
valgrind --log-file="valgrind-output.txt" $EXEC_PROGRAM > /dev/null
cat valgrind-output.txt
rm valgrind-output.txt 2
dev/null
else
echo "WARNING: valgrind not available"
fi
echo "====================================================="
echo "7. Tests have full code coverage"
echo "====================================================="
./check-code-coverage.sh
# Remove the executable
m ./a.out* 2
dev/null
date
echo "====================================================="
echo "To create an output.txt file with all the output from this script"
echo "Run the below command"
echo " ./create-output.sh > output.txt 2>&1 "
echo "====================================================="
__MACOSX/ass5-2/._create-output.sh
ass5-2/clang-tidy
# Configuration options for clang-tidy
# CSS Linux machines, Sep 2019: LLVM version 3.8.1
#
# usage: clang-tidy *.cpp -- -std=c++11
#
#
---
# See https:
clang.llvm.org/extra/clang-tidy/#using-clang-tidy for all possible checks
Checks: '*,-fuchsia-*,-cppcoreguidelines-owning-memory,-cppcoreguidelines-pro-bounds-a
ay-to-pointer-decay,-cppcoreguidelines-pro-bounds-pointer-arithmetic,-google-build-using-namespace,-hicpp-no-a
ay-decay,-modernize-use-trailing-return-type,-llvm-header-guard,-cert-e
60-cpp,-cppcoreguidelines-pro-bounds-constant-a
ay-index,-google-global-names-in-headers'
WarningsAsE
ors: '*'
HeaderFilterRegex: '.*'
CheckOptions:
- { key: readability-identifier-naming.ClassCase, XXXXXXXXXXvalue: CamelCase }
- { key: readability-identifier-naming.StructCase, XXXXXXXXXXvalue: CamelCase }
- { key: readability-identifier-naming.EnumCase, XXXXXXXXXXvalue: CamelCase }
- { key: readability-identifier-naming.GlobalConstantCase, value: UPPER_CASE }
- { key: readability-identifier-naming.VariableCase, XXXXXXXXXXvalue: camelBack }
- { key: readability-identifier-naming.ParameterCase, value: camelBack }
- { key: readability-identifier-naming.PublicMemberCase, value: camelBack }
# No good consensus on function names problem.isFinished() and GetInputFromUser() are both good
# - { key: readability-identifier-naming.FunctionCase, XXXXXXXXXXvalue: camelBack }
# - { key: readability-identifier-naming.PublicMethodCase, value: camelBack }
# - { key: readability-identifier-naming.PrivateMethodCase, value: camelBack }
########################################################################
# Disabled checks
########################################################################
# -fuchsia-*,
# Checks associated with fuchsia operating system
# -cppcoreguidelines-owning-memory,
# Using and learning about raw pointers, not type-based semantics of gsl::owne
T*
# -cppcoreguidelines-pro-bounds-a
ay-to-pointer-decay,
# Using pointers to a
ays
# -cppcoreguidelines-pro-bounds-pointer-arithmetic,
# Not using which is in C++20
# -google-build-using-namespace,
# Will use "using namespace std" to make code easier to read
# -hicpp-no-a
ay-decay,
# Using pointers to a
ays
# -modernize-use-trailing-return-type,
# Not using the modern return type indications such as "factorial(int n) -> int"
# -llvm-header-guard
# Will use short header guards not full directory and file name
# -cert-e
60-cpp
# Want to be able to throw exception with string
# -cppcoreguidelines-pro-bounds-constant-a
ay-index
# Want to use a
ay[index] without having to use gsl::at()
# -google-global-names-in-headers
# Readbility, want to have "using namespace std;" in headers as well
__MACOSX/ass5-2/._clang-tidy
ass5-2/inorder.cpp
ass5-2/inorder.cpp
Created by Frank M. Ca
ano and Timothy M. Henry.
Copyright (c) 2017 Pearson Education, Hoboken, New Jersey.
templatevoid BinaryNodeTree::
inorder(void visit(ItemType&),
std::shared_pt
BinaryNode treePtr) const
{
if (treePtr != nullptr)
{
inorder(visit, treePtr–>getLeftChildPtr());
ItemType theItem = treePtr–>getItem();
visit(theItem);
inorder(visit, treePtr–>getRightChildPtr());
}
end if
}
end inorde
__MACOSX/ass5-2/._inorder.cpp
ass5-2/BinarySearchTree.h
Created by Frank M. Ca
ano and Timothy M. Henry.
Copyright (c) 2017 Pearson Education, Hoboken, New Jersey.
modified by Matthieu Blanchet and Shashank Chennapragada
#include "BinaryNode.h"
#include #ifndef BINARY_SEARCH_TREE_
#define BINARY_SEARCH_TREE_
using namespace std;
class BinarySearchTree
{
private:
BinaryNode* rootPtr = nullptr;
pointer to the tree's start
------------------------------------------------------------
Recursive helper methods
------------------------------------------------------------
recursive helper function for add, determines where to place a node
Pre: subTreePtr is the tree to add the node, newNodePtr is the node to
add
Post: newNodePtr