# Iterator

September 17, 2014
Author：Eric
Source：http://blog.wjin.org/posts/iterator.html
Declaration: this work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

# Iterator

## Introduction

The iterator pattern provides a way to access the elements of an aggregate object sequentially without exposing its underlying representation.

## Example

Here I use binary tree to practice iterator pattern. I design three iterators corresponding to tree preorder, inorder and postorder traverse respectively.

## Code

### Cpp

``````#include <iostream>
#include <stack>

using namespace std;

// abstract iterator interface
template <typename T>
class Iterator
{
public:
virtual bool hasNext() = 0;
virtual T next() = 0;
};

// binary tree implementation
class BinaryTree
{
private:
struct TreeNode {
int data;
TreeNode *left, *right;

TreeNode(int d = -1, TreeNode *l = nullptr, TreeNode *r = nullptr) :
data(d), left(l), right(r) {}
};

TreeNode *root;

public:
// preorder iterator
class PreorderIterator : public Iterator<TreeNode*>
{
private:
TreeNode *cur;
stack<TreeNode*> s;

public:
PreorderIterator(TreeNode *root = nullptr) : cur(root)
{
}

bool hasNext()
{
if (!cur && s.empty()) return false;

TreeNode *tc = cur; // temp cur
stack<TreeNode*> ts = s; // temp stack

TreeNode *n = next();
if (!n) return false;

// restore cur and stack s
cur = tc;
swap(s, ts); // faster than s = ts;
return true;
}

// might return nullptr
// hasNext will use it to make a decision
TreeNode* next()
{
TreeNode *ret = nullptr;
if (!cur) {
do {
cur = s.top();
s.pop();
cur = cur->right;
} while (!cur && !s.empty());
}

if (cur) {
s.push(cur);
ret = cur;
cur = cur->left;
}
return ret;
}
};

// inorder iterator
class InorderIterator : public Iterator<TreeNode*>
{
private:
TreeNode *cur;
stack<TreeNode*> s;

public:
InorderIterator(TreeNode *root = nullptr) : cur(root)
{
}

bool hasNext()
{
if (!cur && s.empty()) return false;

return true;
}

// never return nullptr
TreeNode* next()
{
TreeNode *ret = nullptr;
// guarantee no crash if hasNext() returns false, but still
// try to call next()
// if (!cur && s.empty()) return ret;

if (!cur) {
cur = s.top();
s.pop();
ret = cur;
cur = cur->right;
return ret;
}

while (cur && cur->left) {
s.push(cur);
cur = cur->left;
}

ret = cur;
cur = cur->right;
return ret;
}
};

// postorder iterator
class PostorderIterator : public Iterator<TreeNode*>
{
private:
TreeNode *cur, *prev;
stack<TreeNode*> s;

public:
PostorderIterator(TreeNode* root = nullptr) : cur(root), prev(nullptr)
{
}

bool hasNext()
{
if (!cur && s.empty()) return false;

return true;
}

// never return nullptr
TreeNode* next()
{
TreeNode *ret = nullptr;
// if (!cur && s.empty()) return ret;

while (true) {
while (cur) {
s.push(cur);
cur = cur->left;
}

cur = s.top();
if (cur->right && cur->right != prev) {
cur = cur->right;
s.push(cur);
cur = cur->left;
} else {
break;
}
}

ret = cur;
prev = cur;
s.pop();
cur = nullptr;
return ret;
}
};

private:
// create tree recursively with pre-order
// s[i] == '#' means this tree is empty
TreeNode* CreateTree(const string &s, int &idx)
{
if (s[idx] == '#') // null tree
return nullptr;

TreeNode *t = new TreeNode(s[idx]);
t->left = CreateTree(s, ++idx);
t->right = CreateTree(s, ++idx);
return t;
}

void destroy(TreeNode *t)
{
if (!t) return;

destroy(t->left);
destroy(t->right);
delete t;
}

void Init(const string &s)
{
int idx = 0;
root = CreateTree(s, idx);
}

public:

BinaryTree(const string &s)
{
// please guarantee s is valid
// do not check it here
Init(s);
}

~BinaryTree()
{
destroy(root);
}

void Handle(TreeNode *t)
{
cout << static_cast<char>(t->data) << "-->";
}

void PreOrder()
{
TreeNode *cur = root;
stack<TreeNode*> s;

while (cur || !s.empty()) {
if (cur) {
s.push(cur);
Handle(cur);
cur = cur->left;
} else {
cur = s.top();
s.pop();
cur = cur->right;
}
}
}

void InOrder()
{
TreeNode* cur = root;
stack<TreeNode*> s;

while (cur || !s.empty()) {
if (cur) {
s.push(cur);
cur = cur->left;
} else {
cur = s.top();
s.pop();
Handle(cur);
cur = cur->right;
}
}
}

void PostOrder()
{
TreeNode* cur = root, *prev = nullptr;
stack<TreeNode*> s;

while (cur || !s.empty()) {
if (cur) {
s.push(cur);
cur = cur->left;
} else {
cur = s.top();

if (cur->right && cur->right != prev) {
cur = cur->right;
s.push(cur);
cur = cur->left;
} else {
s.pop();
Handle(cur);
prev = cur;
cur = nullptr;
}
}
}
}

shared_ptr<PreorderIterator> CreatePreorderIterator()
{
return shared_ptr<PreorderIterator>(new PreorderIterator(root));
}

shared_ptr<InorderIterator> CreateInorderIterator()
{
return shared_ptr<InorderIterator>(new InorderIterator(root));
}

shared_ptr<PostorderIterator> CreatePostorderIterator()
{
return shared_ptr<PostorderIterator>(new PostorderIterator(root));
}
};

int main(int argc, const char* argv[])
{
/*
*   Test  Tree
*
A
/   \
B     F
/ \    /
C   D   G
/     \
E       H
*/

// preorder of tree node, # means empty subtree
string s("ABC##DE###FG#H###");
BinaryTree t(s);

cout << "PreOrder: " << endl;
t.PreOrder();
cout << endl;
auto pre = t.CreatePreorderIterator();
while (pre->hasNext()) {
t.Handle(pre->next());
}
cout << endl;

cout << "InOrder: " << endl;
t.InOrder();
cout << endl;
auto in = t.CreateInorderIterator();
while (in->hasNext()) {
t.Handle(in->next());
}
cout << endl;

cout << "PostOrder: " << endl;
t.PostOrder();
cout << endl;
auto post = t.CreatePostorderIterator();
while (post->hasNext()) {
t.Handle(post->next());
}
cout << endl;

return 0;
}
``````