This is the mail archive of the gcc-help@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Begin Never Called but End is correctly called for in iterators


I am wondering for the below code:
#include <iostream>
using namespace std;
//Threaded Binary Tree Class that is templated to hold Node pointers with data type T
template <class T>
class ThreadedTree{
	
	//Internal Node Class for each Node in the tree
	struct Node{
		//Constructor for Node Class
		//Takes the data to be held as a paramater and Node pointers for left and right elements
		//defaults are nullptr for left and right elements and data is set to default value for data type T
		Node(const T& data = T{}, Node* left = nullptr, Node* right = nullptr){
			data_ = data;
			right_ = right;
			left_ = left;
		}
		T data_;
		Node*left_;
		Node* right_;
		bool leftThread;
		bool rightThread;
		//Finds the leftmost from the struct Node pointer passed in, returns nullptr if the Node is nullptr
		struct Node* leftMost(struct Node *n){
			if (n == nullptr){
				return nullptr;
			}
			while (n->left_ != nullptr){
				n = n->left_;
			}

			return n;
		}
		//Finds the rightmost from the struct Node pointer passed in, returns nullptr if the Node is nullptr
		struct Node* rightMost(struct Node *n){
			if (n == nullptr){
				return nullptr;
			}

			while (n->right_ != nullptr){
				n = n->right_;
			}

			return n;
		}
	};
	Node* root_;
		void cleanup(Node* subtreeroot){
		if(subtreeroot==root_){
			return;
		}
		if (subtreeroot){
			cleanup(subtreeroot->left_);
			cleanup(subtreeroot->right_);
			delete subtreeroot;
		}
	}
	public:
	class const_iterator{
	protected:
		friend class ThreadedTree;
		//Constructor that sets curr_ internal Node for iterator to Node passed in agrument Node* c
		const_iterator(Node* c){ curr_ = c; }
		Node* curr_;
		//Checks current node  is not nullptr
		bool checkData(){
			return curr_ == nullptr;
		}
	public:
		//Constructor that sets curr_ internal iterator Node to nullptr
		const_iterator(){
			curr_ = nullptr;
		}
		//Takes a interger and makes iterator point to next right element before returning previous element
		const_iterator operator++(int){
			if(curr_==nullptr){
			}
			const_iterator old = *this;
			if (curr_->rightThread){
				curr_ = curr_->right_;
			}
			else {
				curr_ = curr_->left_;
				curr_ = curr_->rightMost(curr_);
			}
			return const_iterator(old);
		}
		//Takes a interger and makes iterator point to next left element before returning previous element
		const_iterator operator--(int){
			const_iterator old =*this;
			if(curr_==nullptr){
				return nullptr;
			}
			if (curr_->leftThread){
				curr_ = curr_->left_;
			}
			else{
				curr_ = curr_->right_;
				curr_ = curr_->leftMost(curr_);
			}
			return const_iterator(old);
		}
		//Takes no arguments and makes iterator point to next right element
		const_iterator operator++(){
			if (curr_==nullptr){
				return nullptr;
			}
			if(curr_->rightThread){
				curr_= curr_->right_;
			}
			else{
				curr_ = curr_->left_;
				curr_ = curr_->rightMost(curr_);
			}
			return iterator(curr_);
		}
		//Takes no arguments and makes iterator point to next left element
		const_iterator operator--(){
			if(curr_==nullptr){
				return nullptr;
			}
			if(curr_->leftThread){
				curr_ = curr_->right_;
			}
			else{
				curr_ = curr_->right_;
				curr_ = curr_->leftMost(curr_);
			}
			return iterator(curr_);
		}
		//Takes no arguments and returns internal Node of iterator
		const T& operator*(){
			return curr_->data_;
		}
		//Takes const_iterator reference and sees if internal element equals passed reference's element
		bool operator==(const const_iterator& rhs) const{
			return curr_ == rhs.curr_;
		}
		//Takes const_iterator reference and sees if internal element does not equals passed reference's element
		bool operator!=(const const_iterator& rhs) const{
			return curr_ != rhs.curr_;
		}
		friend class ThreadedTree;
	};
	class iterator :public const_iterator{
	protected:
		//Constructor that sets curr_ internal iterator Node to Node passsed
		iterator(Node* c) :const_iterator(c){}
	public:
		// Constructor that sets curr_ internal iterator Node to nullptr
		iterator() :const_iterator(){}
		const T& operator*(){
			return this->curr_->data_;
		}

		iterator operator++(int){
			iterator old = *this;
			if(this->checkData()) {
				return nullptr;
			}
			if (this->curr_->rightThread){
				this->curr_ = this->curr_->right_;
			}
			else{
				Node* pass = this->curr_->left_;
				this->curr_ = this->curr_->left_;
				this->curr_ = this->curr_->rightMost(pass);
			}
			return iterator(old);
		}
		//Takes a interger and makes iterator point to left element before returning previous element
		iterator operator--(int){
			const_iterator old = *this;
			if(this->checkData()){
				return nullptr;
			}
			if (this->curr->leftThread){
				this->curr = this->curr->right_;
			}
			else{
				Node* pass = this->curr_->left_;
				this->curr_ = this->curr_->right_;
				this->curr_ = this->curr_->leftMost(pass);
			}
			return iterator(old);
		}
		//Takes a interger and makes iterator point to next right element before returning previous element
		iterator operator++(){
			if(this->checkData()){
				return nullptr;
			}
			if (*this->curr->rightThread){
				this->curr = this->curr->right_;
			}
			else{
				this->curr_ = this->curr_->left_;
				this->curr_ = this->curr_->rightMost(this->curr_->right_);
			}
			return iterator(this->curr_);
		}
		//Takes no arguments and makes iterator point to next right element
		iterator operator--(){
				if(this->checkData()){
					return nullptr;
				}
				if(this->curr->leftThread){
					this->curr = this->curr->right_;
				}
				else{
					this->curr_ = this->curr_->right_;
					this->curr_ = this->curr_->leftMost(this->curr_->left_);
				}
				return iterator(this->curr_);
			}

		friend class ThreadedTree;
	};
	//Constructor that creates new Tree, takes no arguments and sets tree to new state
	ThreadedTree(){
		root_ = new Node();
		root_->right_ = root_->left_ = root_;
		root_->leftThread = true;
	}
	        void printTree() 

        {

            Node *tmp = root_, *p;

            for (;;) 

            {

                p = tmp;

                tmp = tmp->right_;

                if (!p->rightThread) 

                {

                    while (!tmp->leftThread) 

                    {

                        tmp = tmp->left_;

                    }

                }

                if (tmp == root_) 

                    break;

                cout<<tmp->data_<<"   ";

            }

            cout<<endl;

	}
	//Takes const reference of type T and inserts it into tree, returns iterator to inserted Node
	iterator insert(const T& data){
		Node* p = root_;
		for (;;){
			if (p->data_ > data){
				if (p->rightThread)
					break;
				p = p->right_;
			}
			else if (p->data_ < data){
				if (p->leftThread)
					break;
				p = p->left_;
			}
		}
		Node* tmp = new Node();
		tmp->data_ = data;
		tmp->rightThread = tmp->leftThread = true;
		if (p->data_ < data){
			tmp->right_ = p->right_;
			tmp->left_ = p;
			p->right_ = tmp;
			p->rightThread = false;
			return iterator(p->right_);
		}
		else{
			tmp->right_ = p;
			tmp->left_ = p->left_;
			p->left_ = tmp;
			p->leftThread = false;
			return iterator(p->left_);
		}
	}
	//Takes const reference of type T and finds it in table,if not found returns nullptr
	iterator find(const T& data) const{
		Node *tmp = root_->left_;
		for (;;){
			if (tmp->data_ > data){
				if (tmp->rightThread)
					return nullptr;
				tmp = tmp->right_;
			}
			else if (tmp->data_ < data){
				if (tmp->leftThread)
					return nullptr;
				tmp = tmp->left_;
			}
			else{
				return iterator(tmp);
			}
		}
	}
	//Takes no arguments and returns leftmost Node in Tree as iterator
	iterator begin(){
		std::cout << "reached";
		Node* curr = root_;
		if (curr == nullptr) {
			return  nullptr;
		}
		if (curr != nullptr) {
			while(curr->left_!=nullptr){
				curr = curr->left_;
			}
		}
		return iterator(curr);
	}
	//Takes no arguments and returns rightmost Node in Tree as iterator
	iterator end(){
		return nullptr;
	}
	//Takes no arguments and returns leftmost Node in Tree as const_iterator
	const_iterator begin() const{
		std::cout << "reached";
		Node* curr = root_;
		if (curr == nullptr) {
			return nullptr;
		}
		if (curr != nullptr) {
			while(curr->left_!=nullptr){
				curr = curr->left_;
			}
		}
		return const_iterator(curr);
	
	}
	//Takes no arguments and returns rightmost Node in Tree as iterator
	const_iterator end() const{
		return nullptr;
	}
	//Destructor that destroys tree
	~ThreadedTree(){
		cleanup(root_);
	}
};
why is end being called correctly but begin. It makes no sense that it's not be called ever.
I work it a different way before and it was being called, this is very weird due to the reality
that it builds and links the function in fine when I call it.
Nick


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]