Notes for week 14

For this week's links click here.

Levels of Access

C++ provides levels of access to class data that allows the programmer to prevent misuse of class data members and functions. Within a class, members can be classified as private, protected and public. Levels of access for inherited members are also set as private, protected and public. We will introduce the need for protected class members and demonstrate difficulties that occur when programmers try to control access.

In the table below we will use the following class definitions.

class Parent
{
public:
	void fooPublic();
protected:
	void fooProtected();
	MyType protectedMember;
private:
	void fooPrivate();
	MyType privateMember;
};

class Child :public Parent
{
public:
	void cfooPublic();
protected:
	void cfooProtected();
private:
	void cfooPrivate();
};

//variables declared in some program
Parent p;
Child c;

Using Protected Members

In all that we have done until now we have used public and private members, but have had only a limited used for protected members. When possible, it is better to make all data members private. A corollary to this is that data members are placed in the children of an abstract base class rather than in the parent's class, since it is easier to work with data members within their own class. Sometimes data members must be in the parent class. The list which we discussed last week had to have a pointer to the first item in the list, or no implementation would have been possible. In the list class it would have been possible to place the pointers in the private section since manipulation of lists is relatively simple. We will look at the problems that occur in a more complex structure, the binary tree.

Constructing a Binary Tree

At first glance, a binary tree seems quit similar to a linked list. The tree will have a pointer to the first node in the tree (the root) and nodes will be a members of a second class. Each node contains two pointers (rather than one) to its descendents. So far this doesn't seem to cause too many insurmountable problems, but some times descendents of the tree contain requirements that the tree remained balanced. This means all of the paths from the root to a leaf must be roughly the same length. At least some of these balanced trees are descendents of the binary tree, and all require that nodes be rotated within the tree.

First, let's construct a minimal binary tree. Our tree will only have an insert and print function since these will be sufficient to illustrate the problems involved in restricting access.

template <class Type>
class Tree
{
friend class TreeIterator;
public:
	Tree(){}
	void insert(const Type &);
	void print()const; //temporary print routine
private:
	void insert(const Type &,RcPointer< Node< Type > > &parent);
	void print(const RcPointer > &node)const; //temporary print routine
	RcPointer< Node< Type > > _root;
};

We will have a tree iterator and as in the case of the list, our iterator needs to be a friend of the Tree so it can access the root. When we add the defintion of Node, we also must access to _right and _left to both the Tree and the Iterator. It turns out that our iterator will use a stack, so we actually need to give access to the stack.

template < class Type>
class Node
{
friend class Tree< Type>;
friend class Stack< Type>;
public:
	Node(const Type&);
	void print(ostream &out){out << _data;}
private:
	Type _data;
	RcPointer< Node> _left;
	RcPointer< Node> _right;
};

You might think that it is possible to avoid the friends if you provide functions left and right that return the pointers _left and _right. In the case of the iterator where the pointers are not altered this will work. But consider the insert routines for tree given here.

template <class Type>
void Tree::insert(const Type &data)
{
	if (!_root)
		_root = new Node< Type>(data);
	else
	{
		if (data <  _root->_data)
			insert(data,_root->_left);
		else
			insert(data,_root->_right);
	}
}

template <class Type>
void Tree::insert(const Type &data,RcPointer< Node< Type> > &parent)
{
	if (!parent)
		parent = new Node< Type>(data);
	else
	{
		if (data < parent->_data)
			insert(data,parent->_left);
		else
			insert(data,parent->_right);
	}
}

The pointer parent in the second insert function is passed by reference, so must take a l-value. The calls to this insert function from the first insert function would pass values if we returned a value from our left and right functions. Returning a reference is considered very dangerous if it gives direct access to a data member of a class. It is equivalent to making the data member public.

The Tree Iterator

Before we see the problems incurred by the descendents of Tree, I want to show you how an iterator for a binary tree can be implemented. Traversals using iterators are linear in that the ++ operator always finds the next item in the structure. In the case of the list, this means simply following the link to the next item. Nodes in a binary tree have two links, so there is no clear next item. To establish an order of traversal, three standard traversals are defined for binary trees, preorder, inorder and postorder. The ++ operator chooses the next item in accord with the rules of one of these traversals.

One way to implement iterators is to create a stack that will always provide the next item in the traversal using the pop function. This stack must have a function that traverses the tree pushing nodes at an appropriate time. Since the stack reverses the sequence of visits, the function creating the stack from a tree must execute the steps of a standard traversal function. The pre-order traversal performs an action on the current node then visits the left child and finally the right child. Our stack function visits the right child, then the left and finally process the node. In the function below you will see the position of the push for each type of traversal.

template <class Type>
void Stack::postOrderInsert(const RcPointer< Node < Type> > &n)
{
	if (n)
	{
		//push(n); //post order traversal
		postOrderInsert(n->_right);
		//push(n); //results in inorder traversal
		postOrderInsert(n->_left);
		push(n); //preorder traversal
	}
}

The init operator (which can be called in a program and which is called from the constructor for the iterator) calls on postOrderInsert to create the stack for the iterator. The int operator (used to check if there are things left to traverse) simply checks to see if the stack is empty. Finally the ++ operators pop the stack while the () operator looks at the stack top.

template <class Type>
RcPointer< Node < Type> > TreeIterator< Type>::operator()()
{
	return _stack.seeTop();
}

template <class Type>
void TreeIterator< Type>::operator++()
{
	_stack.pop();
}

template <class Type>
void TreeIterator< Type>::operator++(int)
{
	_stack.pop();
}

template <class Type>
TreeIterator< Type>::operator int ()
{
	return !(_stack.empty());
}

template <class Type>
void TreeIterator< Type>::init()
{
	_stack.clear();//make sure the stack is clean
	//must use post order traversal to produce stack for preorder traversal
	_stack.postOrderInsert(_root);
}

For a complete copy of this code click here.

The difficulties involved with descendents that use private members of friend classes and the overuse of friend classes can bee seen when we try to create a red-black tree as a descendent of binary tree. For of this problem click here.