Section 5 - Deep Copies, Copy Constructors and Assignment

9A.5.1 We Need a Deep Copy Mechanism

As with any class which is based on data stored external to itself, i.e., members that reference objects, we must consider whether or not a deep copy mechanism is required.  If so, it means we should:

  1. Supply an overloaded assignment operator, =
  2. Write a copy constructor
  3. Test code by duplicating objects and passing objects to functions as values

Recall from your previous study with deep copies, passing an object to a function by value does not call a constructor, but it does call a destructor, causing untold devastation which evades the radar of an uneducated C++ programmer.  That's why, in item 3, we mention passing objects as relevant to the topic.

All you have to do is imagine the following scenario in any case to know whether it is necessary to supply a deep copy mechanism:

What happens when you set a = b; and then destruct only one of a or b?  Can you use the remaining object, and can it be destructed without error?

In the case of two FHtree objects, the answer is a resounding no.  An assignment only copies the mRoot and mSize, leaving the rest of the FHtreeNodes to be accessed by both objects (a and b).  If this isn't bad enough in itself -- the production of comingled trees - imagine destructing one of them.  The surviving tree will then have a bunch of stale nodes, rendering it useless.

the destructors movie

9A.5.2 A Private Clone Utility

The basis for the deep copy operations is a private member utility called clone() which will take an FHtreeNode* as a parameter, reproduce the entire tree structure below (and including) that node, and return a pointer to the newly "cloned" subtree.  This is the trickiest part, and it uses recursion:

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));
  if (newNode->sib)
    newNode->sib->prev = newNode;
  if (newNode->firstChild)
    newNode->firstChild->prev = newNode;
  return newNode;
}

The main part is the statement summarized by:

newNode = new FHtreeNode(data, clone(sib), clone(child));

which relies on the recursion (and the FHtreeNode constructor) to correctly clone() the sibling and child and return pointers to those nodes.  It then immediately builds a new FHtreeNode out of those two correctly-built subtrees.  This is the nature of recursion.  We assume that it is done correctly at lower levels without worry.  Of course, we have to make sure our terminal (escape) case works, which it does when root==NULL.

That one statement does result in a completely separate node structure for the new tree, giving the cloned subtree that it generates a life of its own, unlinked to the "clonee" parameter, root.  That's the main thing.  However, we're not done yet, because we have not set the prev links.  That's the purpose of the two last if statements.

Once this is done, we have a cloned sub-tree.

9A.5.3 Assignment Operator

The assignment operators is very simple.  It does little more than clone the mRoot node:

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;
}

There is always some little twist, and in this case, we have to clean up one detail:  the myRoot links for the entire tree, the links that tell every node what its master mRoot is.  Recall, these links are used for error detection to prevent clients from calling a function from one tree, while passing it a node from another tree.  I have tucked away the details of this operation in utility method, setMyRoots().  Since this is not needed in many similar data structures, I don't consider this an important general part of the process.  However, you always have to consider any special accoutrements of your unique implementation (like the myRoot pointers) and take appropriate action.  The code for this function can be found in your include file, FHtree.h.

9A.5.4 Copy Constructor

Finally, we show the copy constructor, which merely calls the assignment operator and is, in fact, defined in-line.

FHtree(const FHtree &rhs) { mRoot = NULL; mSize = 0; *this = rhs; }

In order to make sure that the private data is not left unset in the case of an error or NULL assignment, we initialize them before the call to operator=().

9A.5.5 Client Testing

Here is a client that duplicates everything from the traverse example, but tacks on a copy constructor call to see if all is well.  If it is not, then you will certainly get a crash, causing the program to hang.  I did not supply a function that takes an FHtree object as a parameter (as a test of whether parameter passing is handled correctly now that we have a copy constructor).  That's left as an exercise for the reader.

// FHtree main - Demo of functor and traversal
// CS 2C, Foothill College, Michael Loceff, creator

#include <iostream>
#include <string>
using namespace std;
#include "FHtree.h"

template <typename Object>
class PrintObject
{
public:
  void operator()(Object obj)
  {
    cout << obj << " ";
  }
};

int main()
{
  FHtree<string> sceneTree;
  FHtreeNode<string> *tn;

  // create a scene in a room
  tn = sceneTree.addChild(NULL, "room");

  // ... code deleted - same as previous program ...

  PrintObject<string> formatlessStringPrinter;
  sceneTree.traverse( formatlessStringPrinter );
  cout << endl;

  FHtree<string> sceneTree2(sceneTree);

  sceneTree2.traverse( formatlessStringPrinter );
  cout << endl;

  return 0;
}

/* ------------------ RUN -------------
room table south west leg south east leg north west leg north east leg Miguel th
e 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 right left paw right rear paw le
ft front paw right front paw
room table south west leg south east leg north west leg north east leg Miguel th
e 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 right left paw right rear paw le
ft front paw right front paw
Press any key to continue . . .
-------------------------------------------- */

Just to clarify what you are looking for, there are two things:

  1. The second list should be printed, identically to the first (or, if you changed one of the lists after the clone, they should display differently).
  2. You should see the "Press any key to continue . . . " prompt if you are using Visual C++. This means the class destructors did not hang the program.  Since there is no corresponding built-in alert on a Mac, you can add your own cout << "We made it!"; at the end of the code (or check your Activity Monitor).


9A.5.6 Conclusion

We have really soaked all the information we could in the process of studying general trees.  Everything we learned can be applied to the more specialized trees of the next course (CS 2C) like binary search trees, AVL trees, etc, especially the ideas of recursive method definitions.  We have actually studied the most difficult tree, and the following sub-categories are, oddly, simpler, but that's probably a judgment I should reserve for you.