I'd like to write my own iterator for a 234-tree, but I'm a little confused about how to go about this.
The purpose of having an iterator for it is particularly useful for searching the tree. If you have a Tree_iterator then a user can do more than just display the path it took to get to a particular Key value, like put the information in any data-type they wish (being able to put it into a list, vector, queue, etc. ).
The problem I'm having is that each Node has a vector in it. This is what Node looks like:
Code:
struct Node{
std::vector<T> key;
Node* parent;
Node* one;
Node* two;
Node* three;
Node* four;
Node( const T& d, Node* p )
: parent( p ), one( 0 ), two( 0 ), three( 0 ), four( 0 ) {
key.push_back( d );
};
private:
/* NODE IS NON-COPYABLE:
*/
Node( const Node& rhs );
Node& operator=( const Node& rhs );
}; /* END STURCT NODE */
So far this is what I've got for the Tree_iterator:
Code:
class Tree_iterator{
public:
Tree_iterator( Node* c )
: curr( c ), position( c->key.begin() ){};
const T& operator*() const { return *position; };
T& operator*(){ return *position; };
bool operator!=( const Tree_iterator& i ) { return i.position != curr.position; };
bool operator==( const Tree_iterator& i ) { return i.position == curr.position; };
bool operator<( const Tree_iterator& i ) { return i.position < curr.position; };
Tree_iterator& operator++( ){ position = ++position; return *this; };
private:
Node* curr;
typename std::vector<T>::iterator position;
}; /* END CLASS TREE_ITERATOR */
The way it is above, every time I want to go down a level of the tree, I have to re-assign the iterator, something like this:
Code:
Tree_iterator it = begin();
// Do something with the iterator, then when we have to go down a level:
it = another_Node;
// Where "another_Node is a Node* that also must be incremented in some fashion.
However this is not the behavior I'd like the iterator to have. I'd like for when a user does this:
It checks "position", whether its less then or greater than, and navigates not only the internal vector of keys, but will also go to the appropriate Node* (one,two,three or four)
Any ideas?
Also, begin() is very straight forward, it's implemented like this:
Code:
const Tree_iterator begin() const { return Tree_iterator( root ); };
where root is a Node* to the highest level Node of the tree.
but how might you write an end() function? By the very nature of a tree, end() should have a particular key value that you're searching for and also some terminating value that signifies you've reached the end of the tree and haven't found the value. The fact that end() would have to fulfill both of these things is a problem for me.
Is there a way to write the end() in this manner, or can any of you suggest a better approach to this problem?
Thanks in advance!