How to get iterator to work properly?

I have written an iterator class which is nested in my AVL tree class. The AVL node looks like so:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct AvlNode
    {
        Comparable element;
	list<int> lines; //line occurrences
	bool flag; //checks validity
        AvlNode   *left;
        AvlNode   *right;
		AvlNode   *parent; //parent pointer 
        int       height;

        AvlNode( const Comparable & theElement, AvlNode *lt, AvlNode *rt, AvlNode *pt,
									int h = 0, bool b = true )
          : element( theElement ), left( lt ), right( rt ), parent( pt ), height( h ), flag( b ) { }
    };


I wrote iterator as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class iterator
	 {
		protected:
		
			friend class AvlTree<Comparable>;
			AvlNode * node;
			
			AvlNode * findInOrderSuccessor(AvlNode * & t)
			{
				AvlNode * temp;
				//node has a right child
				// so successor is leftmost node of right subtree
				if(t->right != NULL)
				{
					temp = t->right; //go right
					//go all the way left
					while(temp->left != NULL)
					{
						temp = temp->left; 
					}
					return temp;
				}
		
				//node has no right child
				//if we are someone's left child, go up one
				if(t->parent->left == t)
				{
					//return your parent
					temp = t->parent;
					return temp;
				}
				//if we are someone's right child, go up until the current node
				//is someone's left child, then go up one more
				temp = t->parent;
				while(temp->parent->left != temp)
				{
					temp = temp->parent; //go up 
				}
				//return your parent
				temp = t->parent;
				return temp;
			
			}
			
		public:
			iterator(AvlNode * p) : node(p)
				{ }
		
			//overload * to make *iterator return the element of its node
			Comparable & operator*() 
				{ return node->element; }
				
			iterator operator++ (int) //postfix operator
			{
				node = findInOrderSuccessor(node);
				return iterator(node);
			}
			
			// == comparison overload
			bool operator==(iterator & rhs)
				{ return node == rhs.node; }
			// != comparison overload
			bool operator!=(iterator &rhs)
				{ return node != rhs.node; }
	};


As public members of my AVL Tree class, I have included iterator begin() and iterator end(), which point to the leftmost node and one past rightmost node, respectively. While my code compiles, the iterators don't seem to work at all. If I try to print just *tree.begin(), it will print nothing, instead of the expected Comparable element (in this case, a string). Am I doing something improperly?
Nothing really jumps out at me as far as causing that behavior. Does tree.begin() point to a node with an empty string element?

Your postfix operator++ is wrong in that it should return an iterator to the current object instead of the next one.

I don't see any reason to pass the parameter to findInOrderSuccessor by reference and it doesn't really make sense for the container class to be a friend.
findInOrderSuccessor doesn't seem right to me.

For a start, I can't see how it works in the trivial cases where:
- the tree is empty
- the tree has one element
Topic archived. No new replies allowed.