Dear Chegg Experts, I am a beginner C++ programmer. I would be grateful for any
ID: 3676607 • Letter: D
Question
Dear Chegg Experts,
I am a beginner C++ programmer. I would be grateful for any guidance on how to complete an assignment based on the programming concept of Trees, and implementing deletions within them.
Here is the specification.
Soft Deletion in Trees
Understand the Classes
You are going to be changing the general tree class template, FHtree, of the lectures by adding a single member to the FHtreeNode class:
bool deleted; // true if the node has been removed from the tree
The idea is that when a client asks this class to delete a node, all we will do is set this bool to true and return without further ado.
You will have to rename the classes from FHtreeNode and FHtree (from the lectures) to FHsdTreeNode and FHsdTree, respectively, to distinguish them from the normal-deletion implementations in those lectures.
That's it in a nutshell. The purpose of this new, deleted, member is to avoid ever physically removing a node when the client wants to delete it. Instead we just set deleted = true and it will be considered "gone".
Of course, this is like passing a law. Unless everyone obeys the law, it won't have any effect. So we have to modify most of the methods to take advantage of it.
Some might be easier, some not. For example, remove() may be simpler and shorter than before, since, once it finds the node, all it has to do is set deleted = true -- no actual unlinking of the nodes, destruction of objects, etc. Other methods, like find(), will be more subtle. Finding a node means more than matching the data ( if (x == root->data) ... ). Even though we might find the data, x, in the tree, this does not mean x is really there. It may have been deleted at some point in the past. Remember: now, deleting it leaves it physically in the tree with the deleted flag set. You have to add a second test, if (deleted) ..., before you know whether or not you have really found x. Same thing with display(), size(), etc. They will only report on the virtual tree, not the physical one that is stored in memory. If a node is deleted, it may not be counted or displayed by the various methods.
On the other hand, there will be some new methods that don't have general tree counterparts. sizePhysical() will report on the size of the tree, counting both deleted and non-deleted nodes (so it will basically be exactly our old size() method. displayPhysical() will likewise show everything, including deleted nodes (it will not be required to show the deleted status for this assignment, although that's a nice touch). displayPhysical(), also, can be engineered to reuse the code of the old display() method since that method, by virtue of its ignorance of the newly added deleted flag, already shows all the nodes.
In soft deletion, trees don't normally ever shrink; they keep getting larger. Even though the client may be adding and removing the same number of objects, the add()s will always add nodes, but the remove()s will never take nodes away, just mark them as deleted. This is the meaning and expected behavior of soft deletion. It is used when normal deletion (which we can now call hard or physical deletion to emphasize the difference) has some disruptive effect on the tree and we want to avoid such physical disruption for some reason.
[When we get to binary trees and probing hash tables in the next course, we will be able to re-use the deleted nodes when a client wants to add something that is physically present but marked as deleted. However, for general trees, this refinement is both trickier and less useful, so there is no need for us to burden ourselves with that technique.]
Finally, we will need a collectGarbage() method that goes through the entire tree and physically removes all deleted nodes. This is the only method that will shrink the tree size and bring its physical and virtual contents, at least temporarily, into alignment.
Understand the Client
The client main() that is provided in the lesson (and in your zipped download file, above) will eventually need to be modified in three ways for this assignment:
The #include statement must be changed to reflect the new file name, "SoftDelTree.h. This only works, of course, after you have modified and renamed the supplied header file.
Any references to FHtreeNode and FHtree in the old client must be changed to refer to the new classes we are designing, FHsdTreeNode andFHsdTree.
The client will contain some extra tests in addition to the ones that were there. For example, we'll need to write and test methods like displayPhysical(),collectGarbage().
Implementation Details
After you succeed in compiling and running the lecture code as described above, change the name of the .h file to SoftDelTree.h and the names of the classes it contains to FHsdTreeNode and FHsdTree. Do whatever it takes to both the .h and your .cpp files so that everything compiles with these new names (but don't attempt any new implementation yet). Run again to make sure you get the same output as before. You are now ready to begin your assignment.
Class FHsdTreeNode
Data Members:
All previous members remain plus the one new private (or protected if you prefer) data member bool deleted.
Methods To Modify:
All constructors should take a new default parameter for the deleted member, and the default value for that parameter should be false.
Class FHsdtree
Methods To Modify:
addChild() - not much difference from old addChild(). In particular, we do see if the data is already in the tree as deleted and get clever. We always add the node, exactly as if this were an ordinary tree. However, optionally, you can check the first parameter (treeNode, root, or whatever you call it) to see if it is deleted, and reject the add if it is. There are some unusual scenarios in which the client might inadvisably attempt to make a useless addition under/to a deleted node.
find() - Two versions, just like the old implementation: one non-recursive takes only the data, x, and the other which takes two more parameters for recursion. The non-recursive calls the recursive. The recursive method should check the deleted flag of any data match (a "found" x) and, if true, should return as if the data were not in the tree. If the deleted flag is false, then you would return the node as before, a "good find". Note: the sub-tree of a deleted node is considered entirely deleted, even if individual sub-tree nodes might be still have deleted = false.
remove() - Two versions, just like the previous implementation of a general tree, however, the deleted flag of the appropriate node is set to true. The node is not physically removed from the tree. Note the meaning: this has the same meaning as the old remove(). If a node is marked as deleted, then the entire child sub-tree is considered gone. Those nodes, while not marked themselves (big error to waste time marking them), are no longer in the tree.
display() - Two versions, just like the previous implementation of a general tree, however, the deleted flag must be considered when deciding whether to display something, or return without doing anything. If a node is marked as deleted, neither it, nor its entire child sub-tree should be displayed. They are no longer in the tree.
Others -- any other method which require changes because of the deleted member must be modified. You have to decide. Using common sense on the meaning and interpretation of deleted is part of your assignment. There are several methods that require overriding. Hint: size() will not use mSize, since that member only reflects physical size. Instead, size() has to compute the size, manually (read "recursively"), so it is harder than the old size(). traverse() is another that needs tweaking. Check for more.
New Methods:
"Physical" versions of some methods are needed so we can (for debugging and maintenance purposes) see the actual tree on the console, replete with both deleted and undeleted nodes. Some of these methods work almost exactly as the prior implementation of methods in the non-soft-deletion trees.
int sizePhysical() - returns the actual, physical size. This is easy: just like our old size() from the lectures. It just has a new name in this regime since the old name, size(), is now used to return the virtual size of the tree (a count of non-deleted nodes -- and remember, for our new size(), all children/sub-trees of deleted nodes are considered deleted, even if their deleted flag is still set to false).
void displayPhysical() - like the old display() from the lectures. Ignores the deleted flag. Optionally, place a " (D)" after any node that has deleted == true. Note: you don't have to append the " (D)" if the node is not marked as deleted, even though it might actually be deleted by virtue of its being in a subtree of a deleted node.
bool collectGarbage() - physically removes all nodes that are marked as deleted. After this method is called, the physical and virtual size of the tree would be the same. A physical and virtual display() would also be the same after a call to collectGarbage() (at least temporarily, until more items areremove()ed from the tree). This method does exactly what it says: it takes out the garbage. The return value is true if there was at least one node that got garbage-collected, and false, otherwise. Hint: make use of removeNode(), which can be preserved from the original general tree class.
Suggestion about Order of Implementation
Add the deleted member to the FHsdTreeNode class as private or protected.
Update the signatures of the constructors FHsdTreeNode(), to accommodate the extra parameter (wherever you want to put it).
One at-a-time, begin updating the FHsdTree methods as demanded by the new FHsdTreeNode member, deleted. Suggestion: Start with addChild(), then find(), then remove(). Test as you go. Once these three are working, you'll implement all the rest.
Client
Here is a client you can use to test your code. I am not going to tell you what this client should produce. You should be able to predict that on your own and make a judgment about whether your code is working. At this point in the second programming course, I expect you to be able to make these kinds of determinations. This is the minimal client for testing, but you can add to it, optionally, if you wish.
#include <iostream>
#include <string>
using namespace std;
#include "SoftDelTree.h"
int main()
{
FHsdTree<string> sceneTree;
FHsdTreeNode<string> *tn;
cout << "Starting tree empty? " << sceneTree.empty() << endl << endl;
// create a scene in a room
tn = sceneTree.addChild(NULL, "room");
// add three objects to the scene tree
sceneTree.addChild(tn, "Lily the canine");
sceneTree.addChild(tn, "Miguel the human");
sceneTree.addChild(tn, "table");
// add some parts to Miguel
tn = sceneTree.find("Miguel the human");
// Miguel's left arm
tn = sceneTree.addChild(tn, "torso");
tn = sceneTree.addChild(tn, "left arm");
tn = sceneTree.addChild(tn, "left hand");
sceneTree.addChild(tn, "thumb");
sceneTree.addChild(tn, "index finger");
sceneTree.addChild(tn, "middle finger");
sceneTree.addChild(tn, "ring finger");
sceneTree.addChild(tn, "pinky");
// Miguel's right arm
tn = sceneTree.find("Miguel the human");
tn = sceneTree.find(tn, "torso");
tn = sceneTree.addChild(tn, "right arm");
tn = sceneTree.addChild(tn, "right hand");
sceneTree.addChild(tn, "thumb");
sceneTree.addChild(tn, "index finger");
sceneTree.addChild(tn, "middle finger");
sceneTree.addChild(tn, "ring finger");
sceneTree.addChild(tn, "pinky");
// add some parts to Lily
tn = sceneTree.find("Lily the canine");
tn = sceneTree.addChild(tn, "torso");
sceneTree.addChild(tn, "right front paw");
sceneTree.addChild(tn, "left front paw");
sceneTree.addChild(tn, "right rear paw");
sceneTree.addChild(tn, "left rear paw");
sceneTree.addChild(tn, "spare mutant paw");
sceneTree.addChild(tn, "wagging tail");
// add some parts to table
tn = sceneTree.find("table");
sceneTree.addChild(tn, "north east leg");
sceneTree.addChild(tn, "north west leg");
sceneTree.addChild(tn, "south east leg");
sceneTree.addChild(tn, "south west leg");
cout << " ------------ Loaded Tree ----------------- ";
sceneTree.display();
sceneTree.remove("spare mutant paw");
sceneTree.remove("Miguel the human");
sceneTree.remove("an imagined higgs boson");
cout << " ------------ Virtual (soft) Tree ----------------- ";
sceneTree.display();
cout << " ------------ Physical (hard) Display ----------------- ";
sceneTree.displayPhysical();
cout << "------- Testing Sizes (compare with above)----------- ";
cout << "virtual (soft) size: " << sceneTree.size() << endl;
cout << "physical (hard) size: " << sceneTree.sizePhysical() << endl;
cout << "------------ Collecting Garbage -------------------- ";
cout << "found soft-deleted nodes? " << sceneTree.collectGarbage() << endl;
cout << "immediate collect again? " << sceneTree.collectGarbage() << endl;
cout << "--------- Hard Display after garb col ------------ ";
sceneTree.displayPhysical();
cout << "Semi-deleted tree empty? " << sceneTree.empty() << endl << endl;
sceneTree.remove("room");
cout << "Completely-deleted tree empty? " << sceneTree.empty() << endl << endl;
return 0;
}
These instructions are what I have, and I will provide my attempt below.
Thank you for your guidance.
//Header Code
//
// SoftDelTree.h
//
//
// Created by Macintosh User on 3/4/16.
// Copyright © 2016 Macintosh User. All rights reserved.
//
// File FHsdTree.h
// Template definitions for FHsdTrees, which are general trees
#ifndef FHsdTree_H
#define FHsdTree_H
#include <string>
// advanced prototype for the FHsdTreeNode to use to declare a friend
template <class Object>
class FHsdTree;
// ---------------------- FHsdTreeNode Prototype --------------------------
template <class Object>
class FHsdTreeNode
{
friend class FHsdTree<Object>;
protected:
FHsdTreeNode *firstChild, *sib, *prev;
Object data;
FHsdTreeNode *myRoot; // needed to test for certain error
bool deleted;
public:
FHsdTreeNode( const Object & d = Object(),
FHsdTreeNode *sb = NULL, FHsdTreeNode *chld = NULL, FHsdTreeNode *prv = NULL )
: firstChild(chld), sib(sb), prev(prv), data(d), myRoot(NULL)
{ }
Object GetData() const { return data; }
protected:
// for use only by FHsdTree
FHsdTreeNode( const Object & d,
FHsdTreeNode *sb, FHsdTreeNode *chld, FHsdTreeNode *prv,
FHsdTreeNode *root )
: firstChild(chld), sib(sb), prev(prv), data(d), myRoot(root)
{ }
};
// --------------------------- FHsdTree Prototype ------------------------------
template <class Object>
class FHsdTree
{
protected:
int mSize;
FHsdTreeNode<Object> *mRoot;
public:
FHsdTree() { mSize = 0; mRoot = NULL; }
FHsdTree(const FHsdTree &rhs) { mRoot = NULL; mSize = 0; *this = rhs; }
virtual ~FHsdTree() { clear(); }
bool empty() const { return (mSize == 0); }
int size() const { return mSize; }
void clear() { removeNode(mRoot); }
const FHsdTree & operator=(const FHsdTree &rhs);
FHsdTreeNode<Object> *addChild( FHsdTreeNode<Object> *treeNode, const Object &x );
FHsdTreeNode<Object> *find(const Object &x) { return find(mRoot, x); }
FHsdTreeNode<Object> *find(FHsdTreeNode<Object> *root,
const Object &x, int level = 0);
bool remove(const Object &x) { return remove(mRoot, x); }
bool remove(FHsdTreeNode<Object> *root, const Object &x);
void removeNode(FHsdTreeNode<Object> *nodeToDelete);
int sizePhysical();
void displayPhysical();
bool collectGarbage();
// usual client interfaces (entire tree implied)
void display() const { display(mRoot, 0); }
template <class Processor>
void traverse(Processor func) const { traverse(func, mRoot, 0); }
// recursive helpers
void display(FHsdTreeNode<Object> *treeNode, int level = 0) const;
template <class Processor>
void traverse(Processor func, FHsdTreeNode<Object> *treeNode, int level = 0)
const;
protected:
FHsdTreeNode<Object> *clone( FHsdTreeNode<Object> *root) const;
void setMyRoots(FHsdTreeNode<Object> *treeNode);
};
// FHsdTree Method Definitions -------------------------------------------------
template <class Object>
FHsdTreeNode<Object>* FHsdTree<Object>::find(FHsdTreeNode<Object> *root,
const Object &x, int level)
{
FHsdTreeNode<Object> *retval;
if (mSize == 0 || root == NULL)
return NULL;
if (root->data == x)
return root;
// otherwise, recurse. don't process sibs if this was the original call
if ( level > 0 && (retval = find(root->sib, x, level)))
return retval;
return find(root->firstChild, x, level+1);
}
template <class Object>
bool FHsdTree<Object>::remove(FHsdTreeNode<Object> *root, const Object &x)
{
FHsdTreeNode<Object> *tn = NULL;
if (mSize == 0 || root == NULL)
return false;
if ( (tn = find(root, x)) != NULL )
{
removeNode(tn);
return true;
}
return false;
}
template <class Object>
const FHsdTree<Object> &FHsdTree<Object>::operator=
(const FHsdTree &rhs)
{
if (&rhs != this)
{
clear();
mRoot = clone(rhs.mRoot);
mSize = rhs.mSize;
setMyRoots(mRoot);
}
return *this;
}
template <class Object>
void FHsdTree<Object>::removeNode(FHsdTreeNode<Object> *nodeToDelete)
{
if (nodeToDelete == NULL || mRoot == NULL)
return;
if (nodeToDelete->myRoot != mRoot)
return; // silent error, node does not belong to this tree
// remove all the children of this node
while (nodeToDelete->firstChild)
removeNode(nodeToDelete->firstChild);
if (nodeToDelete->prev == NULL)
mRoot = NULL; // last node in tree
else if (nodeToDelete->prev->sib == nodeToDelete)
nodeToDelete->prev->sib = nodeToDelete->sib; // adjust left sibling
else
nodeToDelete->prev->firstChild = nodeToDelete->sib; // adjust parent
// adjust the successor sib's prev pointer
if (nodeToDelete->sib != NULL)
nodeToDelete->sib->prev = nodeToDelete->prev;
delete nodeToDelete;
--mSize;
}
template <class Object> //Must Modify this addChild()...
FHsdTreeNode<Object> *FHsdTree<Object>::addChild(
FHsdTreeNode<Object> *treeNode, const Object &x )
{
// empty tree? - create a root node if user passes in NULL
if (mSize == 0)
{
if (treeNode != NULL)
return NULL; // silent error something's fishy. treeNode can't right
mRoot = new FHsdTreeNode<Object>(x, NULL, NULL, NULL);
mRoot->myRoot = mRoot;
mSize = 1;
return mRoot;
}
if (treeNode == NULL)
return NULL; // silent error inserting into a non_null tree with a null parent
if (treeNode->myRoot != mRoot)
return NULL; // silent error, node does not belong to this tree
// push this node into the head of the sibling list; adjust prev pointers
FHsdTreeNode<Object> *newNode = new FHsdTreeNode<Object>(x,
treeNode->firstChild, NULL, treeNode, mRoot); // sib, child, prev, root
treeNode->firstChild = newNode;
if (newNode->sib != NULL)
newNode->sib->prev = newNode;
++mSize;
return newNode;
}
template <class Object>
void FHsdTree<Object>::display(FHsdTreeNode<Object> *treeNode, int level) const
{
// this will be static and so will be shared by all calls - a special technique to
// be avoided in recursion, usually
static string blankString = " ";
string indent;
// stop runaway indentation/recursion
if (level > (int)blankString.length() - 1)
{
cout << blankString << " ... " << endl;
return;
}
if (treeNode == NULL)
return;
indent = blankString.substr(0, level);
cout << indent << treeNode->data << endl;
display( treeNode->firstChild, level + 1 );
if (level > 0)
display( treeNode->sib, level );
}
template <class Object>
template <class Processor>
void FHsdTree<Object>::traverse(Processor func, FHsdTreeNode<Object> *treeNode, int level)
const
{
if (treeNode == NULL)
return;
func(treeNode->data);
traverse(func, treeNode->firstChild, level+1);
if (level > 0)
traverse(func, treeNode->sib, level);
}
template <class Object>
FHsdTreeNode<Object> *FHsdTree<Object>::clone(
FHsdTreeNode<Object> *root) const
{
FHsdTreeNode<Object> *newNode;
if (root == NULL)
return NULL;
// does not set myRoot which must be done by caller
newNode = new FHsdTreeNode<Object>(
root->data,
clone(root->sib), clone(root->firstChild));
// entire subtree is cloned, but wire this node into its sib and first chld
if (newNode->sib)
newNode->sib->prev = newNode;
if (newNode->firstChild)
newNode->firstChild->prev = newNode;
return newNode;
}
template <class Object>
void FHsdTree<Object>::setMyRoots(FHsdTreeNode<Object> *treeNode)
{
if (treeNode == NULL)
return;
treeNode->myRoot = mRoot;
setMyRoots(treeNode->sib);
setMyRoots(treeNode->firstChild);
}
template <class Object>
int FHsdTree<Object>::sizePhysical()
{
;
}
template <class Object>
void FHsdTree<Object>::displayPhysical()
{
;
}
template <class Object>
bool FHsdTree<Object>::collectGarbage()
{
;
}
#endif //FHsdTree_H
#define FHsdTree_H
//Main.cpp code
//
// main.cpp
//
//
// Created by Macintosh User on 3/3/16.
// Copyright © 2016 Macintosh User. All rights reserved.
//
// FHtree main
// CS 2B/C, Foothill College, Michael Loceff, creator
#include <iostream>
#include <string>
using namespace std;
#include "SoftDelTree.h"
template <typename Object>
class PrintObject
{
public:
void operator()(Object obj)
{
cout << obj << " ";
}
};
int main()
{
FHsdTree<string> sceneTree;
FHsdTreeNode<string> *tn;
cout << "Starting tree empty? " << sceneTree.empty() << endl << endl;
// create a scene in a room
tn = sceneTree.addChild(NULL, "room");
// add three objects to the scene tree
sceneTree.addChild(tn, "Lily the canine");
sceneTree.addChild(tn, "Miguel the human");
sceneTree.addChild(tn, "table");
// add some parts to Miguel
tn = sceneTree.find("Miguel the human");
// Miguel's left arm
tn = sceneTree.addChild(tn, "torso");
tn = sceneTree.addChild(tn, "left arm");
tn = sceneTree.addChild(tn, "left hand");
sceneTree.addChild(tn, "thumb");
sceneTree.addChild(tn, "index finger");
sceneTree.addChild(tn, "middle finger");
sceneTree.addChild(tn, "ring finger");
sceneTree.addChild(tn, "pinky");
// Miguel's right arm
tn = sceneTree.find("Miguel the human");
tn = sceneTree.find(tn, "torso");
tn = sceneTree.addChild(tn, "right arm");
tn = sceneTree.addChild(tn, "right hand");
sceneTree.addChild(tn, "thumb");
sceneTree.addChild(tn, "index finger");
sceneTree.addChild(tn, "middle finger");
sceneTree.addChild(tn, "ring finger");
sceneTree.addChild(tn, "pinky");
// add some parts to Lily
tn = sceneTree.find("Lily the canine");
tn = sceneTree.addChild(tn, "torso");
sceneTree.addChild(tn, "right front paw");
sceneTree.addChild(tn, "left front paw");
sceneTree.addChild(tn, "right rear paw");
sceneTree.addChild(tn, "left rear paw");
sceneTree.addChild(tn, "spare mutant paw");
sceneTree.addChild(tn, "wagging tail");
// add some parts to table
tn = sceneTree.find("table");
sceneTree.addChild(tn, "north east leg");
sceneTree.addChild(tn, "north west leg");
sceneTree.addChild(tn, "south east leg");
sceneTree.addChild(tn, "south west leg");
cout << " ------------ Loaded Tree ----------------- ";
sceneTree.display();
sceneTree.remove("spare mutant paw");
sceneTree.remove("Miguel the human");
sceneTree.remove("an imagined higgs boson");
cout << " ------------ Virtual (soft) Tree ----------------- ";
sceneTree.display();
cout << " ------------ Physical (hard) Display ----------------- ";
sceneTree.displayPhysical();
cout << "------- Testing Sizes (compare with above)----------- ";
cout << "virtual (soft) size: " << sceneTree.size() << endl;
cout << "physical (hard) size: " << sceneTree.sizePhysical() << endl;
cout << "------------ Collecting Garbage -------------------- ";
cout << "found soft-deleted nodes? " << sceneTree.collectGarbage() << endl;
cout << "immediate collect again? " << sceneTree.collectGarbage() << endl;
cout << "--------- Hard Display after garb col ------------ ";
sceneTree.displayPhysical();
cout << "Semi-deleted tree empty? " << sceneTree.empty() << endl << endl;
sceneTree.remove("room");
cout << "Completely-deleted tree empty? " << sceneTree.empty() << endl << endl;
return 0;
}
Thanks in advance for your help.
Explanation / Answer
#include <iostream>
#include <sstream>
using namespace std;
//#include "FHTree.h"
// File FHgTree.h
// Template definitions for FHtrees, which are general trees
#ifndef FHTREE_H
#define FHTREE_H
#include <string>
// advanced prototype for the FHtreeNode to use to declare a friend
template <class Object>
class FHtree;
// ---------------------- FHtreeNode Prototype --------------------------
template <class Object>
class FHtreeNode
{
friend class FHtree<Object>;
protected:
FHtreeNode *firstChild, *sib, *prev;
Object data;
FHtreeNode *myRoot; // needed to test for certain error
public:
FHtreeNode( const Object & d = Object(),
FHtreeNode *sb = NULL, FHtreeNode *chld = NULL, FHtreeNode *prv = NULL )
: firstChild(chld), sib(sb), prev(prv), data(d), myRoot(NULL)
{ }
Object GetData() const { return data; }
protected:
// for use only by FHtree
FHtreeNode( const Object & d,
FHtreeNode *sb, FHtreeNode *chld, FHtreeNode *prv,
FHtreeNode *root )
: firstChild(chld), sib(sb), prev(prv), data(d), myRoot(root)
{ }
};
// ---------------------- FHtree Prototype --------------------------
template <class Object>
class FHtree
{
protected:
int mSize;
FHtreeNode<Object> *mRoot;
public:
FHtree() { mSize = 0; mRoot = NULL; }
FHtree(const FHtree &rhs) { mRoot = NULL; mSize = 0; *this = rhs; }
virtual ~FHtree() { clear(); }
bool empty() const { return (mSize == 0); }
int size() const { return mSize; }
void clear() { removeNode(mRoot); }
const FHtree & operator=(const FHtree &rhs);
FHtreeNode<Object> *addChild( FHtreeNode<Object> *treeNode, const Object &x );
FHtreeNode<Object> *find(const Object &x) { return find(mRoot, x); }
FHtreeNode<Object> *find(FHtreeNode<Object> *root,
const Object &x, int level = 0);
bool remove(const Object &x) { return remove(mRoot, x); }
bool remove(FHtreeNode<Object> *root, const Object &x);
void removeNode(FHtreeNode<Object> *nodeToDelete);
void display() const { display(mRoot, 0); }
// let be public so cient can call on subtree
void display(FHtreeNode<Object> *treeNode, int level = 0) const;
template <class Processor>
void traverse(Processor func, FHtreeNode<Object> *treeNode = NULL) const;
protected:
FHtreeNode<Object> *clone( FHtreeNode<Object> *root) const;
void setMyRoots(FHtreeNode<Object> *treeNode);
};
// public interface methods of FHtree ------------------------
template <class Object>
FHtreeNode<Object>* FHtree<Object>::find(FHtreeNode<Object> *root,
const Object &x, int level)
{
FHtreeNode<Object> *retval;
if (mSize == 0 || root == NULL)
return NULL;
if (root->data == x)
return root;
// otherwise, recurse. don't process sibs if this was the original call
if ( level > 0 && (retval = find(root->sib, x, level)))
return retval;
return find(root->firstChild, x, ++level);
}
template <class Object>
bool FHtree<Object>::remove(FHtreeNode<Object> *root, const Object &x)
{
FHtreeNode<Object> *tn = NULL;
if (mSize == 0 || root == NULL)
return false;
if ( (tn = find(root, x)) != NULL )
{
removeNode(tn);
return true;
}
return false;
}
template <class Object>
const FHtree<Object> &FHtree<Object>::operator=
(const FHtree &rhs)
{
if (&rhs != this)
{
clear();
mRoot = clone(rhs.mRoot);
mSize = rhs.mSize;
setMyRoots(mRoot);
}
return *this;
}
template <class Object>
void FHtree<Object>::removeNode(FHtreeNode<Object> *nodeToDelete)
{
if (nodeToDelete == NULL || mRoot == NULL)
return;
if (nodeToDelete->myRoot != mRoot)
return; // silent error, node does not belong to this tree
// remove all the children of this node
while (nodeToDelete->firstChild)
removeNode(nodeToDelete->firstChild);
if (nodeToDelete->prev == NULL)
mRoot = NULL; // last node in tree
else if (nodeToDelete->prev->sib == nodeToDelete)
nodeToDelete->prev->sib = nodeToDelete->sib; // adjust left sibling
else
nodeToDelete->prev->firstChild = nodeToDelete->sib; // adjust parent
// adjust the successor sib's prev pointer
if (nodeToDelete->sib != NULL)
nodeToDelete->sib->prev = nodeToDelete->prev;
delete nodeToDelete;
--mSize;
}
template <class Object>
FHtreeNode<Object> *FHtree<Object>::addChild(
FHtreeNode<Object> *treeNode, const Object &x )
{
// empty tree? - create a root node if user passes in NULL
if (mSize == 0)
{
if (treeNode != NULL)
return NULL; // silent error something's fishy. treeNode can't right
mRoot = new FHtreeNode<Object>(x, NULL, NULL, NULL);
mRoot->myRoot = mRoot;
mSize = 1;
return mRoot;
}
if (treeNode == NULL)
return NULL; // silent error inserting into a non_null tree with a null parent
if (treeNode->myRoot != mRoot)
return NULL; // silent error, node does not belong to this tree
// push this node into the head of the sibling list; adjust prev pointers
FHtreeNode<Object> *newNode = new FHtreeNode<Object>(x,
treeNode->firstChild, NULL, treeNode, mRoot); // sib, child, prev, root
treeNode->firstChild = newNode;
if (newNode->sib != NULL)
newNode->sib->prev = newNode;
++mSize;
return newNode;
}
template <class Object>
void FHtree<Object>::display(FHtreeNode<Object> *treeNode, int level) const
{
// this will be static and so will be shared by all calls - a special technique to
// be avoided in recursion, usually
static string blankString = " ";
string indent;
// stop runaway indentation/recursion
if (level > (int)blankString.length() - 1)
{
cout << blankString << " ... " << endl;
return;
}
if (treeNode == NULL)
return;
indent = blankString.substr(0, level);
cout << indent << treeNode->data << endl;
display( treeNode->firstChild, level + 1 );
if (level > 0 )
display( treeNode->sib, level );
}
template <class Object>
template <class Processor>
void FHtree<Object>::traverse(Processor func, FHtreeNode<Object> *treeNode) const
{
FHtreeNode<Object> *child;
if (mRoot == NULL)
return;
if (treeNode == NULL)
{
traverse(func, mRoot);
return;
}
func(treeNode->data);
for (child = treeNode->firstChild; child != NULL; child = child->sib)
traverse(func, child);
}
// FHsearchTree protected method definitions -----------------------------
template <class Object>
FHtreeNode<Object> *FHtree<Object>::clone(
FHtreeNode<Object> *root) const
{
FHtreeNode<Object> *newNode;
if (root == NULL)
return NULL;
// does not set myRoot which must be done by caller
newNode = new FHtreeNode<Object>(
root->data,
clone(root->sib), clone(root->firstChild));
// entire subtree is cloned, but wire this node into its sib and first chld
if (newNode->sib)
newNode->sib->prev = newNode;
if (newNode->firstChild)
newNode->firstChild->prev = newNode;
return newNode;
}
template <class Object>
void FHtree<Object>::setMyRoots(FHtreeNode<Object> *treeNode)
{
if (treeNode == NULL)
return;
treeNode->myRoot = mRoot;
setMyRoots(treeNode->sib);
setMyRoots(treeNode->firstChild);
}
#endif
//#include "SoftDelTree.h"
// File SoftDelTree.h
// Template definitions for FHsdTree, which are general trees
#ifndef FHSDTREE_H
#define FHSDTREE_H
#include <string>
// advanced prototype for the FHsdTreeNode to use to declare a friend
template <class Object>
class FHsdTree;
// ---------------------- FHsdTreeNode Prototype --------------------------
template <class Object>
class FHsdTreeNode : public FHtreeNode<Object>
{
private:
bool deleted;
public:
FHsdTreeNode( const Object & d = Object(),
FHtreeNode<Object> *sb = NULL, FHtreeNode<Object> *chld = NULL,
FHtreeNode<Object> *prv = NULL );
Object getData() const;
FHtreeNode<Object> *getFirstChild() const;
bool getDeleted() const;
FHtreeNode<Object> *getSib() const;
FHtreeNode<Object> *getPrev() const;
FHtreeNode<Object> *getMyRoot() const;
void setDeleted(bool del);
void setData(Object d);
void setFirstChild(FHtreeNode<Object>* fc);
void setSib(FHtreeNode<Object>* sb);
void setPrev(FHtreeNode<Object>* prv);
void setMyRoot(FHtreeNode<Object>* mr);
};
// ---------------------- FHsdTree Prototype --------------------------
template <class Object>
class FHsdTree : public FHtree<Object>
{
public:
FHsdTreeNode<Object> *getMRoot();
int size() const;
int sizePhysical() const;
FHsdTreeNode<Object> *addChild( FHsdTreeNode<Object> *treeNode,
const Object &x );
FHsdTreeNode<Object> *find(const Object &x);
FHsdTreeNode<Object> *find(FHsdTreeNode<Object> *root,
const Object &x, int level = 0);
bool remove(const Object &x);
bool remove(FHsdTreeNode<Object> *root, const Object &x);
void display() const;
void displayPhysical() const;
// let be public so cient can call on subtree
void size(int &count, FHsdTreeNode<Object> *treeNode, int level = 0) const;
void display(FHsdTreeNode<Object> *treeNode, int level = 0) const;
void displayPhysical(FHsdTreeNode<Object> *treeNode, int level = 0) const;
bool collectGarbage();
bool collectGarbage( bool &isDeleted, FHsdTreeNode<Object> *treeNode,
int level = 0);
};
// public interface method for FHsdTreeNode-------------------------------
template <class Object>
FHsdTreeNode<Object>::FHsdTreeNode( const Object & d,
FHtreeNode<Object> *sb, FHtreeNode<Object> *chld, FHtreeNode<Object> *prv)
{
setData(d);
setSib(sb);
setFirstChild(chld);
setPrev(prv);
setMyRoot(NULL);
deleted = false; //true if jode has been removed from the tree
}
template <class Object>
Object FHsdTreeNode<Object>::getData() const
{
return FHtreeNode<Object>::data;
}
template <class Object>
FHtreeNode<Object> * FHsdTreeNode<Object>::getFirstChild() const
{
return FHtreeNode<Object>::firstChild;
}
template <class Object>
bool FHsdTreeNode<Object>::getDeleted() const
{
return deleted;
}
template <class Object>
FHtreeNode<Object> * FHsdTreeNode<Object>::getSib() const
{
return FHtreeNode<Object>::sib;
}
template <class Object>
FHtreeNode<Object> * FHsdTreeNode<Object>::getPrev() const
{
return FHtreeNode<Object>::prev;
}
template <class Object>
FHtreeNode<Object> * FHsdTreeNode<Object>::getMyRoot() const
{
return FHtreeNode<Object>::myRoot;
}
template <class Object>
void FHsdTreeNode<Object>::setDeleted(bool del)
{
deleted = del;
}
template <class Object>
void FHsdTreeNode<Object>::setData(Object d)
{
FHtreeNode<Object>::data = d;
}
template <class Object>
void FHsdTreeNode<Object>::setFirstChild(FHtreeNode<Object>* fc)
{
FHtreeNode<Object>::firstChild = fc;
}
template <class Object>
void FHsdTreeNode<Object>::setSib(FHtreeNode<Object>* sb)
{
FHtreeNode<Object>::sib = sb;
}
template <class Object>
void FHsdTreeNode<Object>::setPrev(FHtreeNode<Object>* prv)
{
FHtreeNode<Object>::prev = prv;
}
template <class Object>
void FHsdTreeNode<Object>::setMyRoot(FHtreeNode<Object>* mr)
{
FHtreeNode<Object>::myRoot = mr;
}
// public interface methods of FHsdTree----------------------------------------
template <class Object>
FHsdTreeNode<Object> * FHsdTree<Object>::getMRoot()
{
return (FHsdTreeNode<Object> *) FHtree<Object>::mRoot;
}
// number of nodes in tree as though the deleted nodes are actually deleted
template <class Object>
int FHsdTree<Object>::size() const
{
int count = 0; size(count,
(FHsdTreeNode<Object> *) FHtree<Object>::mRoot, 0);
return count;
}
// number of nodes total (deleted and not deleted)
template <class Object>
int FHsdTree<Object>::sizePhysical() const
{
return FHtree<Object>::mSize;
}
template <class Object>
FHsdTreeNode<Object> * FHsdTree<Object>::addChild(
FHsdTreeNode<Object> *treeNode, const Object &x )
{
// empty tree? - create a root node if user passes in NULL
if (FHtree<Object>::mSize == 0)
{
FHsdTreeNode<Object> *lMRoot;
if (treeNode != NULL)
return NULL; // silent error something's fishy. treeNode can't right
lMRoot = new FHsdTreeNode<Object>(x, NULL, NULL, NULL);
FHtree<Object>::mRoot = lMRoot;
lMRoot->setMyRoot(lMRoot);
FHtree<Object>::mSize = 1;
return lMRoot;
}
if (treeNode == NULL)
return NULL; // silent error inserting into a non_null tree with a null parent
if (treeNode->getMyRoot() != getMRoot())
return NULL; // silent error, node does not belong to this tree
if (treeNode->getDeleted() == true)
return NULL; // silent error, inserted into a tree with deleted parent
// push this node into the head of the sibling list; adjust prev pointers
FHsdTreeNode<Object> *newNode = new FHsdTreeNode<Object>(x,
treeNode->getFirstChild(), NULL, treeNode); // sib, child, prev, root
newNode->setMyRoot(getMRoot());
treeNode->setFirstChild((FHtreeNode<Object> *)newNode);
if (newNode->getSib() != NULL)
((FHsdTreeNode<Object> *)(newNode->getSib()))->
setPrev((FHtreeNode<Object> *)newNode);
++ FHtree<Object>::mSize;
return newNode;
}
// to find a node, start at the root node
template <class Object>
FHsdTreeNode<Object> * FHsdTree<Object>::find(const Object &x)
{
return find(getMRoot(), x);
}
// find a node starting at the specified root
template <class Object>
FHsdTreeNode<Object> *FHsdTree<Object>::find(FHsdTreeNode<Object> *root,
const Object &x, int level)
{
FHsdTreeNode<Object> *retval;
if (FHtree<Object>::mSize == 0 || root == NULL)
return NULL;
if (root->getData() == x)
{
if (root->getDeleted()) // skip deleted node and its children
{
return NULL;
}
else
{
return root;
}
}
// otherwise, recurse. don't process sibs if this was the original call
if ( level > 0 && (retval = find((FHsdTreeNode<Object> *)(root->getSib()), x, level)))
return retval;
return find((FHsdTreeNode<Object> *)(root->getFirstChild()), x, ++level);
}
// remove node start at the root of the tree
template <class Object>
bool FHsdTree<Object>::remove(const Object &x)
{
return remove(getMRoot(), x);
}
// remove node start at the specified root
template <class Object>
bool FHsdTree<Object>::remove(FHsdTreeNode<Object> *root, const Object &x)
{
FHsdTreeNode<Object> *tn = NULL;
if (FHtree<Object>::mSize == 0 || root == NULL)
return false;
if ( (tn = find(root, x)) != NULL )
{
tn->setDeleted(true);
return true;
}
return false;
}
// display only nondeleted nodes
template <class Object>
void FHsdTree<Object>::display() const
{
FHsdTree<Object>::display((FHsdTreeNode<Object> *) FHtree<Object>::mRoot, 0);
}
// display all nodes (deleted and nondeleted). For deleted node, subscript “(D)”
template <class Object>
void FHsdTree<Object>::displayPhysical() const
{
displayPhysical((FHsdTreeNode<Object> *) FHtree<Object>::mRoot, 0);
}
// number of nondeleted nodes starting at specified treeNode
template <class Object>
void FHsdTree<Object>::size(int &count, FHsdTreeNode<Object> *treeNode, int level) const
{
if (treeNode == NULL)
return;
if (treeNode->getDeleted())
{
if (level > 0)
{
size(count, (FHsdTreeNode<Object> *)treeNode->getSib(), level);
return;
}
}
count++;
size(count, (FHsdTreeNode<Object> *)treeNode->getFirstChild(), level + 1);
if (level > 0)
{
size(count, (FHsdTreeNode<Object> *)treeNode->getSib(), level);
}
}
// display nondeleted nodes
template <class Object>
void FHsdTree<Object>::display(FHsdTreeNode<Object>* treeNode,
int level) const
{
// this will be static and so will be shared by all calls - a special technique to
// be avoided in recursion, usually
static string blankString = " ";
string indent;
// stop runaway indentation/recursion
if (level > (int)blankString.length() - 1)
{
cout << blankString << " ... " << endl;
return;
}
if (treeNode == NULL)
return;
indent = blankString.substr(0, level);
if (treeNode->getDeleted())
{
if (level > 0)
{
display((FHsdTreeNode<Object> *)treeNode->getSib(), level );
}
return;
}
cout << indent << treeNode->getData() << endl;
display((FHsdTreeNode<Object> *)(treeNode->getFirstChild()), level + 1 );
if (level > 0 )
display((FHsdTreeNode<Object> *)treeNode->getSib(), level );
}
// display all nodes (deleted and nondeleted) starting at specified treeNode.
// For deleted node, subscript “(D)”template <class Object>
template <class Object>
void FHsdTree<Object>::displayPhysical(FHsdTreeNode<Object> *treeNode,
int level) const
{
// this will be static and so will be shared by all calls - a special technique to
// be avoided in recursion, usually
static string blankString = " ";
string indent;
// stop runaway indentation/recursion
if (level > (int)blankString.length() - 1)
{
cout << blankString << " ... " << endl;
return;
}
if (treeNode == NULL)
return;
indent = blankString.substr(0, level);
if(treeNode->getDeleted())
{
cout << indent << treeNode->getData() << "(D)" << endl;
}
else
{
cout << indent << treeNode->getData() << endl;
}
displayPhysical( (FHsdTreeNode<Object> *)(treeNode->getFirstChild()), level + 1 );
if (level > 0 )
displayPhysical( (FHsdTreeNode<Object> *)(treeNode->getSib()), level );
}
// remove all deleted nodes starting at the root of the tree
template <class Object>
bool FHsdTree<Object>::collectGarbage()
{
bool isDeleted = false;
return collectGarbage( isDeleted, getMRoot(), 0);
}
//remove all deleted nodes starting at specified treeNode
template <class Object>
bool FHsdTree<Object>::collectGarbage( bool &isDeleted,
FHsdTreeNode<Object> *treeNode, int level)
{
if (treeNode == NULL)
{
return isDeleted;
}
if(treeNode->getDeleted())
{
isDeleted = true;
FHtree<Object>::removeNode(treeNode);
if (level > 0)
{
collectGarbage(isDeleted, (FHsdTreeNode<Object> *)
(treeNode->getSib()), level);
}
return isDeleted;
}
collectGarbage(isDeleted, (FHsdTreeNode<Object> *)
(treeNode->getFirstChild()), level + 1);
if (level > 0)
{
collectGarbage(isDeleted, (FHsdTreeNode<Object> *)
(treeNode->getSib()), level);
}
return isDeleted;
}
#endif
//#include "Employee.h"
// File Employee.h
// Template definitions for Employee
#ifndef EMPLOYEE_H
#define EMPLOYEE_H
#include <string>
class Employee
{
private:
string name;
int id;
double salary;
public:
Employee(string name = " ", int id = 0, double salary = 0.0);
friend bool operator==(const Employee& e1, const Employee& e2);
friend ostream& operator<<(ostream& ostrm, const Employee& e1);
string toString() const;
};
Employee::Employee(string inName, int inId, double inSalary)
{
name = inName;
id = inId;
salary = inSalary;
}
bool operator==(const Employee& e1, const Employee& e2)
{
return e1.id == e2.id;
}
ostream& operator<<(ostream& ostrm, const Employee& e1)
{
ostrm << e1.toString();
return ostrm;
}
string Employee::toString() const
{
ostringstream ssResult;
ssResult << "Employee name: " << name << ", Employee ID: " << id
<< "Employee salary: " << salary;
return ssResult.str();
}
#endif
int main()
{
FHsdTree<string> sceneTree;
FHsdTreeNode<string> *tn;
cout << endl << "=================================================" << endl;
cout << "1. Testing General Tree..." << endl;
cout << "Starting tree empty? " << sceneTree.empty() << endl << endl;
// create a scene in a room
tn = sceneTree.addChild(NULL, "room");
// add three objects to the scene tree
sceneTree.addChild(tn, "Lily the canine");
sceneTree.addChild(tn, "Miguel the human");
sceneTree.addChild(tn, "table");
// add some parts to Miguel
tn = sceneTree.find("Miguel the human");
// Miguel's left arm
tn = sceneTree.addChild(tn, "torso");
tn = sceneTree.addChild(tn, "left arm");
tn = sceneTree.addChild(tn, "left hand");
sceneTree.addChild(tn, "thumb");
sceneTree.addChild(tn, "index finger");
sceneTree.addChild(tn, "middle finger");
sceneTree.addChild(tn, "ring finger");
sceneTree.addChild(tn, "pinky");
// Miguel's right arm
tn = sceneTree.find("Miguel the human");
tn = sceneTree.find(tn, "torso");
tn = sceneTree.addChild(tn, "right arm");
tn = sceneTree.addChild(tn, "right hand");
sceneTree.addChild(tn, "thumb");
sceneTree.addChild(tn, "index finger");
sceneTree.addChild(tn, "middle finger");
sceneTree.addChild(tn, "ring finger");
sceneTree.addChild(tn, "pinky");
// add some parts to Lily
tn = sceneTree.find("Lily the canine");
tn = sceneTree.addChild(tn, "torso");
sceneTree.addChild(tn, "right front paw");
sceneTree.addChild(tn, "left front paw");
sceneTree.addChild(tn, "right rear paw");
sceneTree.addChild(tn, "left rear paw");
sceneTree.addChild(tn, "spare mutant paw");
sceneTree.addChild(tn, "wagging tail");
// add some parts to table
tn = sceneTree.find("table");
sceneTree.addChild(tn, "north east leg");
sceneTree.addChild(tn, "north west leg");
sceneTree.addChild(tn, "south east leg");
sceneTree.addChild(tn, "south west leg");
cout << " ------------ Loaded Tree ----------------- ";
sceneTree.display();
sceneTree.remove("spare mutant paw");
sceneTree.remove("Miguel the human");
sceneTree.remove("an imagined higgs boson");
cout << " ------------ Virtual (soft) Tree ----------------- ";
sceneTree.display();
cout << " ------------ Physical (hard) Display ----------------- ";
sceneTree.displayPhysical();
cout << "------- Testing Sizes (compare with above)----------- ";
cout << "virtual (soft) size: " << sceneTree.size() << endl;
cout << "physical (hard) size: " << sceneTree.sizePhysical() << endl;
cout << "------------ Collecting Garbage -------------------- ";
cout << "found soft-deleted nodes? " << sceneTree.collectGarbage() << endl;
cout << "immediate collect again? " << sceneTree.collectGarbage() << endl;
cout << "--------- Hard Display after garb col ------------ ";
sceneTree.displayPhysical();
cout << "Semi-deleted tree empty? " << sceneTree.empty() << endl << endl;
sceneTree.remove("room");
cout << "------------ Collecting Garbage -------------------- ";
cout << "found soft-deleted nodes? " << sceneTree.collectGarbage() << endl;
cout << "immediate collect again? " << sceneTree.collectGarbage() << endl;
cout << "Completely-deleted tree empty? " << sceneTree.empty() << endl << endl;
cout << endl << "=================================================" << endl;
cout << "2. Testing Tree with Numeric Type..." << endl;
FHsdTree<int> numTree;
FHsdTreeNode<int> *tni;
cout << "Starting tree empty? " << sceneTree.empty() << endl << endl;
// create a root for numTree
tni = numTree.addChild(NULL, 1);
// add objects to the num tree
numTree.addChild(tni, 2);
numTree.addChild(tni, 3);
numTree.addChild(tni, 4);
numTree.addChild(tni, 5);
numTree.addChild(tni, 6);
numTree.addChild(tni, 7);
// add some parts to 4
tni = numTree.find(4);
// Child of 4
numTree.addChild(tni, 8);
// add some parts to 5
tni = numTree.find(5);
// Child of 5
numTree.addChild(tni, 9);
numTree.addChild(tni, 10);
// add some parts to 6
tni = numTree.find(6);
// Child of 6
numTree.addChild(tni, 11);
numTree.addChild(tni, 12);
numTree.addChild(tni, 13);
// add some parts to 7
tni = numTree.find(7);
// Child of 7
numTree.addChild(tni, 14);
// add some parts to 10
tni = numTree.find(10);
// Child of 10
numTree.addChild(tni, 15);
numTree.addChild(tni, 16);
cout << " ------------ Loaded Tree ----------------- ";
numTree.display();
numTree.remove(10);
numTree.remove(6);
numTree.remove(14);
cout << " ------------ Virtual (soft) Tree ----------------- ";
numTree.display();
cout << " ------------ Physical (hard) Display ----------------- ";
numTree.displayPhysical();
cout << "------- Testing Sizes (compare with above)----------- ";
cout << "virtual (soft) size: " << numTree.size() << endl;
cout << "physical (hard) size: " << numTree.sizePhysical() << endl;
cout << "------------ Collecting Garbage -------------------- ";
cout << "found soft-deleted nodes? " << numTree.collectGarbage() << endl;
cout << "immediate collect again? " << numTree.collectGarbage() << endl;
cout << "--------- Hard Display after garb col ------------ ";
numTree.displayPhysical();
cout << "Semi-deleted tree empty? " << numTree.empty() << endl << endl;
numTree.remove(1);
cout << "------------ Collecting Garbage -------------------- ";
cout << "found soft-deleted nodes? " << numTree.collectGarbage() << endl;
cout << "immediate collect again? " << numTree.collectGarbage() << endl;
cout << "Completely-deleted tree empty? " << numTree.empty() << endl << endl;
cout << endl << "=================================================" << endl;
cout << "3. Testing Tree with User Defined Object Type..." << endl;
FHsdTree<Employee> employeeTree;
FHsdTreeNode<Employee> *tne;
cout << "Starting tree empty? " << employeeTree.empty() << endl << endl;
// create employees
Employee e500 ("Harry Banks", 500, 200000);
Employee e499 ("Jane Air", 499, 175000);
Employee e498 ("Joe Shmoe", 498, 175000);
Employee e497 ("Amelia AirHeart", 497, 120000);
Employee e496 ("Sarah Waters", 496, 125000);
Employee e495 ("Aaron Oro", 495, 110000);
Employee e494 ("Jordan Good", 494, 110000);
Employee e493 ("Mike Jones", 493, 100000);
Employee e492 ("Lexi Keller", 492, 125000);
Employee e491 ("Angela Richards", 491, 80000);
// create root for employeeTree
tne = employeeTree.addChild(NULL, e500);
// add child for e500
employeeTree.addChild(tne, e499);
employeeTree.addChild(tne, e498);
// add child for e499
tne = employeeTree.find(e499);
employeeTree.addChild(tne, e497);
employeeTree.addChild(tne, e496);
employeeTree.addChild(tne, e495);
// add child for e498
tne = employeeTree.find(e498);
employeeTree.addChild(tne, e492);
employeeTree.addChild(tne, e493);
employeeTree.addChild(tne, e494);
// add child for e496
tne = employeeTree.find(e496);
employeeTree.addChild(tne, e491);
cout << " ------------ Loaded Tree ----------------- ";
employeeTree.display();
employeeTree.remove(e496);
employeeTree.remove(e492);
cout << " ------------ Virtual (soft) Tree ----------------- ";
employeeTree.display();
cout << " ------------ Physical (hard) Display ----------------- ";
employeeTree.displayPhysical();
cout << "------- Testing Sizes (compare with above)----------- ";
cout << "virtual (soft) size: " << employeeTree.size() << endl;
cout << "physical (hard) size: " << employeeTree.sizePhysical() << endl;
cout << "------------ Collecting Garbage -------------------- ";
cout << "found soft-deleted nodes? " << employeeTree.collectGarbage() << endl;
cout << "immediate collect again? " << employeeTree.collectGarbage() << endl;
cout << "--------- Hard Display after garb col ------------ ";
employeeTree.displayPhysical();
cout << "Semi-deleted tree empty? " << employeeTree.empty() << endl << endl;
employeeTree.remove(e500);
cout << "------------ Collecting Garbage -------------------- ";
cout << "found soft-deleted nodes? " << employeeTree.collectGarbage() << endl;
cout << "immediate collect again? " << employeeTree.collectGarbage() << endl;
cout << "Completely-deleted tree empty? " << employeeTree.empty()
<< endl << endl;
return 0;
}
/*
Output:
=================================================
1. Testing General Tree...
Starting tree empty? 1
------------ Loaded Tree -----------------
room
table
south west leg
south east leg
north west leg
north east leg
Miguel the human
torso
right arm
right hand
pinky
ring finger
middle finger
index finger
thumb
left arm
left hand
pinky
ring finger
middle finger
index finger
thumb
Lily the canine
torso
wagging tail
spare mutant paw
left rear paw
right rear paw
left front paw
right front paw
------------ Virtual (soft) Tree -----------------
room
table
south west leg
south east leg
north west leg
north east leg
Lily the canine
torso
wagging tail
left rear paw
right rear paw
left front paw
right front paw
------------ Physical (hard) Display -----------------
room
table
south west leg
south east leg
north west leg
north east leg
Miguel the human(D)
torso
right arm
right hand
pinky
ring finger
middle finger
index finger
thumb
left arm
left hand
pinky
ring finger
middle finger
index finger
thumb
Lily the canine
torso
wagging tail
spare mutant paw(D)
left rear paw
right rear paw
left front paw
right front paw
------- Testing Sizes (compare with above)-----------
virtual (soft) size: 13
physical (hard) size: 30
------------ Collecting Garbage --------------------
found soft-deleted nodes? 1
immediate collect again? 0
--------- Hard Display after garb col ------------
room
table
south west leg
south east leg
north west leg
north east leg
Lily the canine
torso
wagging tail
left rear paw
right rear paw
left front paw
right front paw
Semi-deleted tree empty? 0
------------ Collecting Garbage --------------------
found soft-deleted nodes? 1
immediate collect again? 0
Completely-deleted tree empty? 1
=================================================
2. Testing Tree with Numeric Type...
Starting tree empty? 1
------------ Loaded Tree -----------------
1
7
14
6
13
12
11
5
10
16
15
9
4
8
3
2
------------ Virtual (soft) Tree -----------------
1
7
5
9
4
8
3
2
------------ Physical (hard) Display -----------------
1
7
14(D)
6(D)
13
12
11
5
10(D)
16
15
9
4
8
3
2
------- Testing Sizes (compare with above)-----------
virtual (soft) size: 8
physical (hard) size: 16
------------ Collecting Garbage --------------------
found soft-deleted nodes? 1
immediate collect again? 0
--------- Hard Display after garb col ------------
1
7
5
9
4
8
3
2
Semi-deleted tree empty? 0
------------ Collecting Garbage --------------------
found soft-deleted nodes? 1
immediate collect again? 0
Completely-deleted tree empty? 1
=================================================
3. Testing Tree with User Defined Object Type...
Starting tree empty? 1
------------ Loaded Tree -----------------
Employee name: Harry Banks, Employee ID: 500Employee salary: 200000
Employee name: Joe Shmoe, Employee ID: 498Employee salary: 175000
Employee name: Jordan Good, Employee ID: 494Employee salary: 110000
Employee name: Mike Jones, Employee ID: 493Employee salary: 100000
Employee name: Lexi Keller, Employee ID: 492Employee salary: 125000
Employee name: Jane Air, Employee ID: 499Employee salary: 175000
Employee name: Aaron Oro, Employee ID: 495Employee salary: 110000
Employee name: Sarah Waters, Employee ID: 496Employee salary: 125000
Employee name: Angela Richards, Employee ID: 491Employee salary: 80000
Employee name: Amelia AirHeart, Employee ID: 497Employee salary: 120000
------------ Virtual (soft) Tree -----------------
Employee name: Harry Banks, Employee ID: 500Employee salary: 200000
Employee name: Joe Shmoe, Employee ID: 498Employee salary: 175000
Employee name: Jordan Good, Employee ID: 494Employee salary: 110000
Employee name: Mike Jones, Employee ID: 493Employee salary: 100000
Employee name: Jane Air, Employee ID: 499Employee salary: 175000
Employee name: Aaron Oro, Employee ID: 495Employee salary: 110000
Employee name: Amelia AirHeart, Employee ID: 497Employee salary: 120000
------------ Physical (hard) Display -----------------
Employee name: Harry Banks, Employee ID: 500Employee salary: 200000
Employee name: Joe Shmoe, Employee ID: 498Employee salary: 175000
Employee name: Jordan Good, Employee ID: 494Employee salary: 110000
Employee name: Mike Jones, Employee ID: 493Employee salary: 100000
Employee name: Lexi Keller, Employee ID: 492Employee salary: 125000(D)
Employee name: Jane Air, Employee ID: 499Employee salary: 175000
Employee name: Aaron Oro, Employee ID: 495Employee salary: 110000
Employee name: Sarah Waters, Employee ID: 496Employee salary: 125000(D)
Employee name: Angela Richards, Employee ID: 491Employee salary: 80000
Employee name: Amelia AirHeart, Employee ID: 497Employee salary: 120000
------- Testing Sizes (compare with above)-----------
virtual (soft) size: 7
physical (hard) size: 10
------------ Collecting Garbage --------------------
found soft-deleted nodes? 1
immediate collect again? 0
--------- Hard Display after garb col ------------
Employee name: Harry Banks, Employee ID: 500Employee salary: 200000
Employee name: Joe Shmoe, Employee ID: 498Employee salary: 175000
Employee name: Jordan Good, Employee ID: 494Employee salary: 110000
Employee name: Mike Jones, Employee ID: 493Employee salary: 100000
Employee name: Jane Air, Employee ID: 499Employee salary: 175000
Employee name: Aaron Oro, Employee ID: 495Employee salary: 110000
Employee name: Amelia AirHeart, Employee ID: 497Employee salary: 120000
Semi-deleted tree empty? 0
------------ Collecting Garbage --------------------
found soft-deleted nodes? 1
immediate collect again? 0
Completely-deleted tree empty? 1
*/
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.