sahar_karimi
کاربر تازه وارد
- تاریخ عضویت
- 9 جولای 2006
- نوشتهها
- 10
- لایکها
- 0
کد:
[CODE]// *****************************************************
// * ThreadedTree.h *
// * Header file for Threaded Binary Search Tree *
// * Contains ThreadedTree, ThreadedNode, iterator, *
// * and const_iterators *
// * *
// *****************************************************
#ifndef THREADED_TREE
#define THREADED_TREE
#include <iostream>
#include <cstdlib>
using std::cout;
using std::endl;
template <typename Etype>
class ThreadedTree {
private:
/********************************
* ThreadedTree<>::ThreadedNode *
* Nested class for tree nodes *
* node class *
********************************/
class ThreadedNode {
public:
// ThreadedNode - Basic constructor
// Initializes node to default values.
ThreadedNode() : element(), left(NULL), right(NULL) { leftFlag = 0; rightFlag = 0; }
// ThreadedNode - Constructor that can set a few values
// Parameters -- elem == initialization element.
// leftPtr == initialization left pointer.
// rightPtr == initialization right pointer.
// Initializes node to parameter values.
ThreadedNode(Etype elem, ThreadedNode* leftPtr, ThreadedNode* rightPtr) :
element(elem), left(leftPtr), right(rightPtr) { leftFlag = 0; rightFlag = 0; }
Etype element;
ThreadedNode* left;
ThreadedNode* right;
int leftFlag;
int rightFlag;
};
/********************/
/* MEMBER VARIABLES */
/********************/
typename ThreadedTree<Etype>::ThreadedNode* root; // points to the root node.
typename ThreadedTree<Etype>::ThreadedNode* nil; // points to a node outside of tree.
int treeSize; // # of nodes in the tree.
/************/
/* TYPEDEFS */
/************/
typedef Etype value_type;
typedef Etype * pointer;
typedef Etype & reference;
typedef Etype const * const_pointer;
typedef Etype const & const_reference;
/*****************************/
/* ThreadedTree<>::iterator */
/* iterator class */
/*****************************/
public:
class iterator {
public:
// same typedefs as for vector, only now they are in the
// iterator class, so (for example), if you want the type
// an iterator points to, not only would vector<...>::value_type
// work, but so would vector<...>::iterator::value_type.
// This is especially helpful once you pass iterator objects
// as arguments to generic functions.
typedef Etype value_type;
typedef Etype * pointer;
typedef Etype & reference;
// iterator
// - constructor
// - initializes this iterator to point to NULL
iterator();
// operator*
// - return type : a reference to the element type
// - returns by reference the cell storing the element
// to which this iterator points. There is no
// error checking done to ensure that this is
// a legal cell on which to perform this operation.
Etype & operator*();
// operator->
// - return type : a pointer to the element type
// - returns a pointer to the cell storing the element
// to which this iterator points. There is no
// error checking done to ensure that this is
// a legal cell on which to perform this operation.
Etype * operator->();
// operator++ (prefix version)
// - return type : reference to an iterator
// - moves this iterator one position forward in the
// collection it points to, and then returns
// this iterator after moving it. There is no
// error checking done to ensure that this is
// a legal position at which to perform this
// operation.
typename ThreadedTree<Etype>::iterator & operator++();
// operator-- (prefix version)
// - return type: reference to an iterator
// - moves this iterator one position backward in the
// collection it points to, and then returns
// this iterator after moving it. There is no
// error checking done to ensure that this is
// a legal position at which to perform this
// operation.
typename ThreadedTree<Etype>::iterator & operator--();
// operator++ (postfix version)
// - parameters : ignore - argument always the integer 1, to
// distinguish this from prefix version
// - return type : an iterator
// - moves this iterator one position forward in the
// collection it points to, and then returns an
// iterator to the position this iterator pointed
// to before this function was run. There is no
// error checking done to ensure that this is a
// legal position at which to perform this operation.
typename ThreadedTree<Etype>::iterator operator++(int ignore);
// operator-- (postfix version)
// - parameters : ignore - argument always the integer 1, to
// distinguish this from prefix version
// - return type : an iterator
// - moves this iterator one position backward in the
// collection it points to, and then returns an
// iterator to the position this iterator pointed
// to before this function was run. There is no
// error checking done to ensure that this is a
// legal position at which to perform this operation.
typename ThreadedTree<Etype>::iterator operator--(int ignore);
// operator==
// - parameters : origVal - previously created iterator
// - return value : boolean with true indicating equality
// - returns true if this iterator and the parameter
// iterator point to the same location; else returns false
bool operator==(typename ThreadedTree<Etype>::iterator const & origVal) const;
// operator!=
// - parameters : origVal - previously created iterator
// - return value : boolean with true indicating inequality
// - returns true if this iterator and the parameter
// iterator point different locations; else returns false
bool operator!=(typename ThreadedTree<Etype>::iterator const & origVal) const;
private:
typename ThreadedTree<Etype>::ThreadedNode * ptr; // pointer to whatever type of value this
// iterator is meant to point to; the entire
// iterator object is basically a wrapper for
// this pointer.
// iterator
// - constructor
// - parameters : assignPtr - a pointer to the same type
// that this iterator points to
// - initializes iterator to point to the same place as
// the parameter pointer points to
iterator(typename ThreadedTree<Etype>::ThreadedNode * assignPtr);
// these lines give the ThreadedTree class and the const_iterator class
// access to the above private members of iterator
friend class ThreadedTree<Etype>;
friend class ThreadedTree<Etype>::const_iterator;
};
/**********************************/
/* ThreadedTree<>::const_iterator */
/* const_iterator class */
/**********************************/
class const_iterator {
public:
// Same typedefs as for vector, only now they are in the
// const_iterator class, so (for example), if you want the
// type an const_iterator points to, not only would
// vector<...>::value_type work, but so would
// vector<...>::const_iterator::value_type. This is especially
// helpful once you pass iterator objects as arguments to generic
// functions.
typedef Etype value_type;
typedef Etype const * const_pointer;
typedef Etype const & const_reference;
// const_iterator
// - constructor
// - initializes this const_iterator to point to NULL
const_iterator();
// const_iterator
// - constructor
// - parameters : theIter - an iterator
// - initializes this const_iterator to point to the same
// location as the parameter iterator
const_iterator(typename ThreadedTree<Etype>::iterator const & theIter);
// operator*
// - return type : a reference to a value of the element type,
// a value that cannot be altered through this reference
// - returns by reference the element to which this
// const_iterator points; it will not be possible to change
// that value through the returned reference. There is no
// error checking done to ensure that this is a legal position
// at which to perform this operation.
Etype const & operator*() const;
// operator->
// - return type : a pointer to a value of the element type,
// a value that cannot be altered through this pointer
// - returns a pointer to the element to which this
// const_iterator points; it will not be possible to change
// that value through the returned pointer. There is no error
// checking done to ensure that this is a legal position
// at which to perform this operation.
Etype const * operator->() const;
// operator++ (prefix version)
// - return type : reference to a const_iterator
// - moves this const_iterator one position forward in the
// collection it points to, and then returns this
// const_iterator after moving it. There is no error
// checking done to ensure that this is a legal
// position at which to perform this operation.
typename ThreadedTree<Etype>::const_iterator & operator++();
// operator-- (prefix version)
// - return type: reference to a const_iterator
// - moves this const_iterator one position backward in the
// collection it points to, and then returns this
// const_iterator after moving it. There is no error
// checking done to ensure that this is a legal
// position at which to perform this operation.
typename ThreadedTree<Etype>::const_iterator & operator--();
// operator++ (postfix version)
// - parameters : ignore - argument always the integer 1, to
// distinguish this from prefix version
// - return type : a const_iterator
// - moves this const_iterator one position forward in the
// collection it points to, and then returns a
// const_iterator to the position this const_iterator
// pointed to before this function was run. There is no
// error checking done to ensure that this is a
// legal position at which to perform this operation.
typename ThreadedTree<Etype>::const_iterator operator++(int ignore);
// operator-- (postfix version)
// - parameters : ignore - argument always the integer 1, to
// distinguish this from prefix version
// - return type : a const_iterator
// - moves this const_iterator one position backward in the
// collection it points to, and then returns a
// const_iterator to the position this const_iterator
// pointed to before this function was run. There is no
// error checking done to ensure that this is a
// legal position at which to perform this operation.
typename ThreadedTree<Etype>::const_iterator operator--(int ignore);
// operator==
// - parameters : origVal - previously created const_iterator
// - return value : boolean with true indicating equality
// - returns true if this const_iterator and the parameter
// const_iterator point to the same location; else returns
// false
bool operator==(
typename ThreadedTree<Etype>::const_iterator const & origVal) const;
// operator!=
// - parameters : origVal - previously created const_iterator
// - return value : boolean with true indicating inequality
// - returns true if this const_iterator and the parameter
// const_iterator point different locations; else returns
// false
bool operator!=(
typename ThreadedTree<Etype>::const_iterator const & origVal) const;
private:
typename ThreadedTree<Etype>::ThreadedNode * ptr; // pointer to whatever type of value this
// const_iterator is meant to point to; the entire
// const_iterator object is basically a wrapper for
// this pointer.
// these lines give the threaded tree class access to the above
// private members of iterator
friend class ThreadedTree<Etype>;
};
/*******************************************/
/* USER INTERFACE: public member functions */
/*******************************************/
public:
// ThreadedTree - Basic constructor
// Initializes tree to be empty.
ThreadedTree();
// ThreadedTree
// Copy constructor.
// Parameters -- origVal == previously allocated ThreadedTree object.
// Initializes object to be a copy of origVal.
ThreadedTree(ThreadedTree const & origVal);
// ~ThreadedTree
// Destructor.
// Deletes dynamically allocated memory!
~ThreadedTree();
// operator=
// Parameters -- origVal == previously allocated ThreadedTree object.
// Return value -- const reference to this object.
// Sets object to be a copy of origVal.
ThreadedTree const & operator=(ThreadedTree const & origVal);
// begin
// Returns an interator pointing to the tree's minimum element.
typename ThreadedTree<Etype>::iterator & begin();
// begin
// Same as non const begin, except it returns a const_iterator instead.
typename ThreadedTree<Etype>::const_iterator & begin() const;
// end
// Returns an iterator to the end of the tree. (One node past maximum element).
typename ThreadedTree<Etype>::iterator & end();
// end_const
// Same as non const end, except it returns a const_iterator instead.
typename ThreadedTree<Etype>::const_iterator & end() const;
// find
// Parameters -- key == element of type Etype.
// Return value -- an integer.
// Checks to see if the tree has a node with element value key. If so, 1 is returned. 0 is returned if otherwise.
int find(Etype const & key) const;
// insert
// Parameters -- item == element of type Etype to be inserted into our tree.
// Inserts param into the tree.
void insert(Etype const & item);
// remove
// Parameters -- item == element of type Etype to be removed from our tree.
// Removes param from tree.
void remove(Etype const & item);
// preorder
// Prints out values stored by tree in preorder format.
void preorder() const;
// size
// Return value -- an integer.
// Returns the number of nodes in the tree.
int size() const;
/********************************************/
/* IMPLEMENTATION: private member functions */
/********************************************/
private:
// copy
// Parameters -- ptr == a ThreadedNode pointer.
// Return value -- a ThreadedNode pointer.
// Makes a new ThreadedNode which is a copy of the
// parameter node, and returns it.
typename ThreadedTree<Etype>::ThreadedNode* copy(typename ThreadedTree<Etype>::ThreadedNode const * ptr);
// clear
// Parameters -- ptr == reference to a tree node pointer.
// Recursively clears the tree.
void clear(typename ThreadedTree<Etype>::ThreadedNode * & ptr);
// find
// Parameters -- key == element of type Etype.
// ptr == a ThreadedNode pointer.
// Return value -- a boolean value.
// Recursive helper method for public find function.
typename ThreadedTree<Etype>::ThreadedNode* find(Etype key, ThreadedTree<Etype>::ThreadedNode * ptr) const;
// print
// Parameters -- ptr == a ThreadedNode pointer.
// Recursive helper method for public preorder function.
void print(ThreadedTree<Etype>::ThreadedNode const * ptr) const;
// insert
// Parameters -- item == item of type Etype to be inserted into our tree
// Recursive helper method for public insert function.
void insert(Etype item, typename ThreadedTree<Etype>::ThreadedNode * & ptr);
// remove
// Parameters -- item == item to be removed from the tree
// Recursive helper method for the public insert function.
void remove(Etype const & item, typename ThreadedTree<Etype>::ThreadedNode * & ptr);
// getParent
// Parameters -- item == item of type Etype
// -- root == pointer to the root of the tree
// Searches the tree for a node containing item. If it is found a pointer
// to the node's parent is returned. Otherwise nil is returned.
//typename ThreadedTree<Etype>::ThreadedNode * & getParent(Etype item, typename ThreadedTree<Etype>::ThreadedNode * & ptr);
};
#endif
// *****************************************************
// * ThreadedTree.h *
// * Source file for Threaded Binary Search Tree *
// * Contains ThreadedTree, ThreadedNode, iterator, *
// * and const_iterators *
// * *
// *****************************************************
#include "ThreadedTree.h"
#include "String.h"
#include "Asserts.h"
#include <cstddef>
#include <iostream>
using std::cout;
using std::endl;
/*************************** PUBLIC INTERFACE **********************/
template <typename Etype>
ThreadedTree<Etype>::ThreadedTree() : root(NULL), nil(NULL), treeSize(0) {
}
template <typename Etype>
ThreadedTree<Etype>::ThreadedTree(ThreadedTree<Etype> const & origVal) {
root = copy(origVal.root);
nil = nil = new typename ThreadedTree<Etype>::ThreadedNode();
treeSize = origVal.treeSize;
typename ThreadedTree<Etype>::ThreadedNode * trav = root;
while (trav->rightFlag == 1)
trav = trav->right;
trav->right = nil;
trav->right->left = trav;
}
template <typename Etype>
ThreadedTree<Etype>::~ThreadedTree() {
clear(root);
delete nil;
}
template <typename Etype>
ThreadedTree<Etype> const & ThreadedTree<Etype>::operator=(ThreadedTree<Etype> const & origVal) {
if (this != &origVal) {
clear(root);
delete nil;
root = copy(origVal.root);
nil = new typename ThreadedTree<Etype>::ThreadedNode();
treeSize = origVal.treeSize;
}
return *this;
}
template <typename Etype>
typename ThreadedTree<Etype>::iterator & ThreadedTree<Etype>::begin() {
typename ThreadedTree<Etype>::ThreadedNode* min;
if (root->leftFlag == 0)
min = root;
else {
typename ThreadedTree<Etype>::ThreadedNode * trav = root;
while (trav->leftFlag == 1)
trav = trav->left;
min = trav;
}
return *(new typename ThreadedTree<Etype>::iterator(min));
}
template <typename Etype>
typename ThreadedTree<Etype>::const_iterator & ThreadedTree<Etype>::begin() const {
typename ThreadedTree<Etype>::ThreadedNode* min;
if (root->leftFlag == 0)
min = root;
else {
typename ThreadedTree<Etype>::ThreadedNode * trav = root;
while (trav->leftFlag == 1)
trav = trav->left;
min = trav;
}
return *(new typename ThreadedTree<Etype>::const_iterator(min));
}
template <typename Etype>
typename ThreadedTree<Etype>::iterator & ThreadedTree<Etype>::end() {
typename ThreadedTree<Etype>::ThreadedNode* max;
max = root;
while (max->rightFlag == 1)
max = max->right;
max = max->right;
return *(new typename ThreadedTree<Etype>::iterator(max));
}
template <typename Etype>
typename ThreadedTree<Etype>::const_iterator & ThreadedTree<Etype>::end() const{
typename ThreadedTree<Etype>::ThreadedNode* max;
max = root;
while (max->rightFlag == 1)
max = max->right;
max = max->right;
return *(new typename ThreadedTree<Etype>::const_iterator(max));
}
template <typename Etype>
int ThreadedTree<Etype>::find(Etype const & key) const {
if (root != NULL)
if (find(key, root)!=NULL)
return 1;
return 0;
}
template <typename Etype>
void ThreadedTree<Etype>::insert(Etype const & item) {
if (root != NULL)
insert(item, root);
else { // insert at root
root = new typename ThreadedTree<Etype>::ThreadedNode(item, nil, nil);
nil = new typename ThreadedTree<Etype>::ThreadedNode(item, root, root);
root->left = nil;
root->right = nil;
}
treeSize++;
typename ThreadedTree<Etype>::ThreadedNode * trav = root;
while (trav->rightFlag == 1)
trav = trav->right;
trav->right->left = trav;
}
template <typename Etype>
void ThreadedTree<Etype>::remove(Etype const & item) {
typename ThreadedTree<Etype>::ThreadedNode* temp = find(item, root);
remove(item, temp);
typename ThreadedTree<Etype>::ThreadedNode * trav = root;
while (trav->rightFlag == 1)
trav = trav->right;
trav->right->left = trav;
}
template <typename Etype>
void ThreadedTree<Etype>::preorder() const {
print(root);
}
template <typename Etype>
int ThreadedTree<Etype>::size() const {
return treeSize;
}
/********************** PRIVATE HELPER FUNCTIONS *******************/
template <typename Etype>
typename ThreadedTree<Etype>::ThreadedNode* ThreadedTree<Etype>::copy(typename ThreadedTree<Etype>::ThreadedNode const * ptr) {
typename ThreadedTree<Etype>::ThreadedNode* returnPtr;
if (ptr == nil)
returnPtr = nil;
if ((ptr->leftFlag == 1)&&(ptr->rightFlag == 1)) {
returnPtr = new typename ThreadedTree<Etype>::ThreadedNode(ptr->element, NULL, NULL);
returnPtr->right = copy(ptr->right);
returnPtr->left = copy(ptr->left);
returnPtr->rightFlag = 1;
returnPtr->leftFlag = 1;
}
else if (ptr->rightFlag == 1) {
returnPtr = new typename ThreadedTree<Etype>::ThreadedNode(ptr->element, NULL, NULL);
returnPtr->right = copy(ptr->right);
returnPtr->left = nil;
returnPtr->rightFlag = 1;
returnPtr->leftFlag = 0;
}
else if (ptr->leftFlag == 1) {
returnPtr = new typename ThreadedTree<Etype>::ThreadedNode(ptr->element, NULL, NULL);
returnPtr->right = nil;
returnPtr->left = copy(ptr->left);
returnPtr->rightFlag = 0;
returnPtr->leftFlag = 1;
}
else {
returnPtr = new typename ThreadedTree<Etype>::ThreadedNode(ptr->element, NULL, NULL);
returnPtr->right = nil;
returnPtr->left = nil;
returnPtr->rightFlag = 0;
returnPtr->leftFlag = 0;
}
typename ThreadedTree<Etype>::ThreadedNode* trav = returnPtr;
if (trav->rightFlag == 1) {
trav = trav->right;
while (trav->leftFlag == 1)
trav = trav->left;
trav->left = returnPtr;
}
trav = returnPtr;
if (trav->leftFlag == 1) {
trav = trav->left;
while (trav->rightFlag == 1)
trav = trav->right;
trav->right = returnPtr;
}
return returnPtr;
}
template <typename Etype>
void ThreadedTree<Etype>::clear(typename ThreadedTree<Etype>::ThreadedNode * & ptr) {
if (ptr == NULL) {// empty tree
return;
}
if ((ptr->leftFlag == 1) && (ptr->rightFlag == 1)) {
clear(ptr->left);
clear(ptr->right);
delete ptr;
}
else if (ptr->leftFlag == 1) {
clear(ptr->left);
delete ptr;
}
else if (ptr->rightFlag == 1) {
clear(ptr->right);
delete ptr;
}
else {
delete ptr;
}
}
template <typename Etype>
typename ThreadedTree<Etype>::ThreadedNode* ThreadedTree<Etype>::find(Etype key, ThreadedTree<Etype>::ThreadedNode * ptr) const {
if (ptr->element == key)
return ptr;
else {
if( (ptr->element > key) && (ptr->leftFlag == 1) )
return find(key, ptr->left);
else if(ptr->element > key)
return NULL;
if ( (ptr->element < key) && (ptr->rightFlag == 1) )
return find(key, ptr->right);
else if(ptr->element < key)
return NULL;
}
}
template <typename Etype>
void ThreadedTree<Etype>::print(ThreadedTree<Etype>::ThreadedNode const * ptr) const {
if (ptr != NULL)
cout << ptr->element << endl;
if ( (ptr->leftFlag == 1) && (ptr->rightFlag ==1) ) {
print(ptr->left);
print(ptr->right);
}
else if(ptr->leftFlag == 1)
print(ptr->left);
else if (ptr->rightFlag == 1)
print(ptr->right);
}
template <typename Etype>
void ThreadedTree<Etype>::insert(Etype item, typename ThreadedTree<Etype>::ThreadedNode * & ptr) {
if ((ptr->element < item)&&(ptr->rightFlag == 0)) {
typename ThreadedTree<Etype>::ThreadedNode* temp = ptr->right;
ptr->right = new typename ThreadedTree<Etype>::ThreadedNode(item, NULL, NULL);
ptr->rightFlag = 1;
ptr->right->right = temp;
ptr->right->left = ptr;
}
else if (ptr->element < item)
insert(item, ptr->right);
else if ( (ptr->element > item) && (ptr->leftFlag == 0) ) {
typename ThreadedTree<Etype>::ThreadedNode* temp = ptr->left;
ptr->left = new typename ThreadedTree<Etype>::ThreadedNode(item, NULL, NULL);
ptr->leftFlag = 1;
ptr->left->right = ptr;
ptr->left->left = temp;
}
else
insert(item, ptr->left);
}
template <typename Etype>
void ThreadedTree<Etype>::remove(Etype const & item, typename ThreadedTree<Etype>::ThreadedNode * & ptr) {
if ((ptr->leftFlag == 1)&&(ptr->rightFlag == 0)) {
typename ThreadedTree<Etype>::ThreadedNode* trav = root;
typename ThreadedTree<Etype>::ThreadedNode* parent;
cout << "case 1\n";
cout << "val: " << ptr->element << endl;
cout << "lval: " << ptr->left->element << endl;
cout << "rval: " << ptr->right->element << endl;
while ((trav->left != ptr)&&(trav->right != ptr)){
if (root == ptr){
trav == NULL;
break;
}
if (ptr->element < trav->element)
trav = trav->left;
else
trav = trav->right;
}
parent = trav;
if (parent == NULL){
root == root->left;
root->right = nil;
nil->left = root;
delete ptr;
return;}
if ((parent->leftFlag == 1)&&(parent->left == ptr))
parent->left = ptr->left;
else
parent->right = ptr->left;
trav = ptr;
if (trav->leftFlag == 1) {
trav = trav->left;
while (trav->rightFlag == 1)
trav = trav->right;
trav->right = ptr->right;
}
delete ptr;
}
if ((ptr->leftFlag == 0)&&(ptr->rightFlag == 1)) {
typename ThreadedTree<Etype>::ThreadedNode* trav = root;
typename ThreadedTree<Etype>::ThreadedNode* parent;
cout << "case 2\n";
cout << "val: " << ptr->element << endl;
cout << "lval: " << ptr->left->element << endl;
cout << "rval: " << ptr->right->element << endl;
while ((trav->left != ptr)&&(trav->right != ptr)){
if (root == ptr){
trav == NULL;
break;
}
if (ptr->element < trav->element)
trav = trav->left;
else
trav = trav->right;
}
parent = trav;
if (parent == NULL){
root == root->right;
delete ptr;
return;}
if ((parent->leftFlag == 1)&&(parent->left == ptr)) // ptr is the left child
parent->left = ptr->right;
else
parent->right = ptr->right;
trav = ptr;
if (trav->leftFlag == 1) {
trav = trav->right;
while (trav->leftFlag == 1)
trav = trav->left;
trav->left = ptr->left;
}
delete ptr;
}
if ((ptr->leftFlag == 0)&&(ptr->rightFlag == 0)) {
cout << "case 3\n";
cout << "val: " << ptr->element << endl;
cout << "lval: " << ptr->left->element << endl;
cout << "rval: " << ptr->right->element << endl;
if ((ptr->right->left == ptr)&&(ptr->right != nil)) {
cout << "3l\n";
ptr->right->left = ptr->left;
ptr->right->leftFlag = 0;
}
if ((ptr->left->right == ptr)&&(ptr->left !=nil)) {
cout << "3r\n";
ptr->left->right = ptr->right;
ptr->left->rightFlag = 0;
}
delete ptr;
}
if ((ptr->leftFlag == 1)&&(ptr->rightFlag == 1)) {
cout << "case 4\n";
cout << "val: " << ptr->element << endl;
cout << "lval: " << ptr->left->element << endl;
cout << "rval: " << ptr->right->element << endl;
typename ThreadedTree<Etype>::ThreadedNode* IOS = ptr->right;
while (IOS->leftFlag == 1)
IOS = IOS->left;
ptr->element = IOS->element;
remove(IOS->element, IOS);
}
}
// getParent
/************************* ITERATOR FUNCTIONS ***********************/
template <typename Etype>
ThreadedTree<Etype>::iterator::iterator() : ptr(NULL) {
}
template <typename Etype>
Etype & ThreadedTree<Etype>::iterator::operator*() {
return ptr->element;
}
template <typename Etype>
Etype * ThreadedTree<Etype>::iterator::operator->() {
return &(ptr->element);
}
template <typename Etype>
typename ThreadedTree<Etype>::iterator & ThreadedTree<Etype>::iterator::operator++() {
if (ptr->rightFlag == 0){
ptr = ptr->right;
return *this;
}
ptr = ptr->right;
while (ptr->leftFlag == 1)
ptr = ptr->left;
return *this;
}
template <typename Etype>
typename ThreadedTree<Etype>::iterator & ThreadedTree<Etype>::iterator::operator--() {
if (ptr->leftFlag == 0){
ptr = ptr->left;
return *this;
}
ptr = ptr->left;
while (ptr->rightFlag == 1)
ptr = ptr->right;
return *this;
}
template <typename Etype>
typename ThreadedTree<Etype>::iterator ThreadedTree<Etype>::iterator::operator++(int ignore) {
typename ThreadedTree<Etype>::iterator temp = *this;
if (ptr->rightFlag == 0){
ptr = ptr->right;
return temp;
}
ptr = ptr->right;
while (ptr->leftFlag == 1)
ptr = ptr->left;
return temp;
}
template <typename Etype>
typename ThreadedTree<Etype>::iterator ThreadedTree<Etype>::iterator::operator--(int ignore) {
typename ThreadedTree<Etype>::iterator temp = *this;
if (ptr->leftFlag == 0){
ptr = ptr->left;
return temp;
}
ptr = ptr->left;
while (ptr->rightFlag == 1){
ptr = ptr->right;
}
return temp;
}
template <typename Etype>
bool ThreadedTree<Etype>::iterator::operator==(typename ThreadedTree<Etype>::iterator const & origVal) const {
return (ptr == origVal.ptr);
}
template <typename Etype>
bool ThreadedTree<Etype>::iterator::operator!=(typename ThreadedTree<Etype>::iterator const & origVal) const {
return (ptr != origVal.ptr);
}
template <typename Etype>
ThreadedTree<Etype>::iterator::iterator(ThreadedTree<Etype>::ThreadedNode* assignPtr) : ptr(assignPtr) {
}
/****************** CONST_ITERATOR FUNCTIONS **********************/
template <typename Etype>
ThreadedTree<Etype>::const_iterator::const_iterator() : ptr(NULL) {
}
template <typename Etype>
ThreadedTree<Etype>::const_iterator::const_iterator(typename ThreadedTree<Etype>::iterator const & theIter) {
ptr = theIter.ptr;
}
template <typename Etype>
Etype const & ThreadedTree<Etype>::const_iterator::operator*() const {
return ptr->element;
}
template <typename Etype>
Etype const * ThreadedTree<Etype>::const_iterator::operator->() const {
return &(ptr->element);
}
template <typename Etype>
typename ThreadedTree<Etype>::const_iterator & ThreadedTree<Etype>::const_iterator::operator++() {
if (ptr->rightFlag == 0){
ptr = ptr->right;
return *this;
}
ptr = ptr->right;
while (ptr->leftFlag == 1)
ptr = ptr->left;
return *this;
}
template <typename Etype>
typename ThreadedTree<Etype>::const_iterator & ThreadedTree<Etype>::const_iterator::operator--() {
if (ptr->leftFlag == 0){
ptr = ptr->left;
return *this;
}
ptr = ptr->left;
while (ptr->rightFlag == 1)
ptr = ptr->right;
return *this;
}
template <typename Etype>
typename ThreadedTree<Etype>::const_iterator ThreadedTree<Etype>::const_iterator::operator++(int ignore) {
typename ThreadedTree<Etype>::const_iterator temp = *this;
if (ptr->rightFlag == 0){
ptr = ptr->right;
return temp;
}
ptr = ptr->right;
while (ptr->leftFlag == 1)
ptr = ptr->left;
return temp;
}
template <typename Etype>
typename ThreadedTree<Etype>::const_iterator ThreadedTree<Etype>::const_iterator::operator--(int ignore) {
typename ThreadedTree<Etype>::const_iterator temp = *this;
if (ptr->leftFlag == 0){
ptr = ptr->left;
return temp;
}
ptr = ptr->left;
while (ptr->rightFlag == 1){
ptr = ptr->right;
}
return temp;
}
template <typename Etype>
bool ThreadedTree<Etype>::const_iterator::operator==(typename ThreadedTree<Etype>::const_iterator const & origVal) const {
return (ptr == origVal.ptr);
}
template <typename Etype>
bool ThreadedTree<Etype>::const_iterator::operator!=(typename ThreadedTree<Etype>::const_iterator const & origVal) const {
return (ptr != origVal.ptr);
}
template class ThreadedTree<int>;
template class ThreadedTree<String>;