In this lab $12\mathrm{.}6,$ the Tree$234$ class is extended to support iteration with a range$-$based for loop. Iteration support is provided via the implementation of an iterator that can iterate through the tree's keys in ascending order.

An iterator is an object that maintains a pointer to a specific element in a collection and can move to the next element. Ex: A Tree$234$ iterator points to the tree's minimum key upon construction. The iterator can then move to the second to minimum key, then the third to minimum, and so on$.$ After moving past the tree's last key, the iterator can move no further.

Overview of iterable objects in C$++$

This lab requires implementation of a simplified iterator that:

Implements the dereference operator $(*)$ to return the key that the iterator currently points to

Implements the pre$-$increment operator $(++)$ to advance to the next key

Supports copy construction and copy assignment

Supports equality and inequality comparison

Range$-$based for loops work on any class that implements the begin$()$ and end$()$ member functions such that each returns an iterator. So Tree$234$ implements begin$()$ and end$().$ Tree$234\text{'}$s begin$()$ member function returns an instance of Tree$234$Iterator object representing the inclusive starting point of iteration: the tree's minimum key. Tree$234\text{'}$s end$()$ member function returns an instance of Tree$234$Iterator object representing the exclusive ending point of iteration: one beyond the tree's maximum key.

Step $1$: Inspect the Node$234.$h file

Inspect the Node$234.$h file. Node$234.$h is read$-$only and has a complete implementation of a Node$234$ class for a $2-3-4$ tree node. Member variables are protected and so must be accessed through the provided getter and setter functions.

Step $2$: Inspect the Tree$234$Iterator.h file

Inspect the Tree$234$Iterator.h file. The Tree$234$Iterator class is declared, but required member functions are not implemented. The implementation must satisfy the following requirements:

Iteration never changes the tree in any way.

Iteration starts at the tree's minimum key and ends at the maximum.

Construction occurs in worst$-$case O$($log N$)$ time.

Dereferencing executes in worst$-$case O$(1)$ time.

Incrementing executes in worst$-$case O$($log N$)$ time.

Space complexity is worst$-$case O$($log N$).$

For simplicity, assume the tree is not changed by an outside source during the iterator's lifetime.

Step $3$: Understand requirement implications

To satisfy the requirements, the iterator must maintain a collection of node pointers. A node exists in the collection only if that node must be revisited at some point in time.

The iterator must visit only the necessary nodes to deliver a key when the iterator is dereferenced. "Visiting" a node means calling any of that node's member functions. Ex: Suppose an iterator is built for the tree below. Then the iterator's $*$ operator is invoked to return key $5,$ then $++$ is invoked to advance to key $10,$ then $*$ is invoked to return key $10,$ then $++$ is invoked to advance to key $15,$ and then $*$ is invoked to return key $15.$ The iterator should have only visited the highlighted nodes.

$2-3-4$ tree with $14$ nodes and $19$ keys. Root node's keys are $30$ and $70.$ Root's child $0$ has keys $10$ and $20.$ Root's child $1$ has keys $40,50,$ and $60.$ Root's child $2$ has keys $80$ and $90.$ Node $(10,20)$ has $3$ single$-$keyed children: $5,15,$ and $25.$ Node $(40,50,60)$ has $4$ single$-$keyed children: $25,45,55,$ and $65.$ Node $(80,90)$ has $3$ single$-$keyed children: $75,85,$ and $95.$

Step $4$: Implement the Tree$234$Iterator class

Implement the Tree$234$Iterator to satisfy the complexity requirements mentioned above. Code in main.cpp adds random keys to a Tree$234$ object, then tests that the iterator properly iterates through all keys in ascending order. But time and space complexity aren't tested by code in main.cpp$.$ Rather, main.cpp only ensures that the iterator properly iterates through all keys.

Most unit tests will fail if the iterator does not properly iterate through all the tree's keys in the correct order. So run code and ensure that the test in main.cpp passes before submitting code for grading.

Hints

Assume that Tree$234\text{'}$s begin$()$ and end$()$ member functions return a Tree$234$Iterator object.

Tree$234$ uses a template type, IteratorType, for the iterator type, allowing specialized iterators to be used for grading. So the declared return type for begin$()$ and end$()$ is actually IteratorType.

The conceptual description of an iterator mentions that the iterator "points to$"$ a key. In the actual implementation, the "pointer" to a key is not an int$*.$ The iterator must know if more keys exist in the node, and a direct pointer to the key integer itself does not include such information.

#ifndef TREE$234$ITERATOR$\_$H

#define TREE$234$ITERATOR$\_$H

#include "Node$234.$h$"$

class Tree$234$Iterator $\{$

private:

$//$ TODO: Type your code here

public:

Tree$234$Iterator$($Node$234*$ root$)\{$

$//$ TODO: Type your code