#!/usr/bin/env python
# coding: utf-8

# # 迭代器

# ## 简介

# 迭代器对象可以在 `for` 循环中使用：

# In[1]:


x = [2, 4, 6]

for n in x:
    print n


# 其好处是不需要对下标进行迭代，但是有些情况下，我们既希望获得下标，也希望获得对应的值，那么可以将迭代器传给 `enumerate` 函数，这样每次迭代都会返回一组 `(index, value)` 组成的元组：

# In[2]:


x = [2, 4, 6]

for i, n in enumerate(x):
    print 'pos', i, 'is', n


# 迭代器对象必须实现 `__iter__` 方法：

# In[3]:


x = [2, 4, 6]
i = x.__iter__()
print i


# `__iter__()` 返回的对象支持 `next` 方法，返回迭代器中的下一个元素：

# In[4]:


print i.next()


# 当下一个元素不存在时，会 `raise` 一个 `StopIteration` 错误：

# In[5]:


print i.next()
print i.next()


# In[6]:


i.next()


# 很多标准库函数返回的是迭代器：

# In[7]:


r = reversed(x)
print r


# 调用它的 `next()` 方法：

# In[8]:


print r.next()
print r.next()
print r.next()


# 字典对象的 `iterkeys, itervalues, iteritems` 方法返回的都是迭代器：

# In[9]:


x = {'a':1, 'b':2, 'c':3}
i = x.iteritems()
print i


# 迭代器的 `__iter__` 方法返回它本身：

# In[10]:


print i.__iter__()


# In[11]:


print i.next()


# ## 自定义迭代器

# 自定义一个 list 的取反迭代器：

# In[12]:


class ReverseListIterator(object):
    
    def __init__(self, list):
        self.list = list
        self.index = len(list)
        
    def __iter__(self):
        return self
    
    def next(self):
        self.index -= 1
        if self.index >= 0:
            return self.list[self.index]
        else:
            raise StopIteration


# In[13]:


x = range(10)
for i in ReverseListIterator(x):
    print i,


# 只要我们定义了这三个方法，我们可以返回任意迭代值：

# In[14]:


class Collatz(object):
    
    def __init__(self, start):
        self.value = start
        
    def __iter__(self):
        return self
    
    def next(self):
        if self.value == 1:
            raise StopIteration
        elif self.value % 2 == 0:
            self.value = self.value / 2
        else:
            self.value = 3 * self.value + 1
        return self.value


# 这里我们实现 [Collatz 猜想](http://baike.baidu.com/view/736196.htm)：
# 
# - 奇数 n：返回 3n + 1
# - 偶数 n：返回 n / 2
# 
# 直到 n 为 1 为止：

# In[15]:


for x in Collatz(7):
    print x,


# 不过迭代器对象存在状态，会出现这样的问题：

# In[16]:


i = Collatz(7)
for x, y in zip(i, i):
    print x, y


# 一个比较好的解决方法是将迭代器和可迭代对象分开处理，这里提供了一个二分树的中序遍历实现：

# In[17]:


class BinaryTree(object):
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

    def __iter__(self):
        return InorderIterator(self)


# In[18]:


class InorderIterator(object):
    
    def __init__(self, node):
        self.node = node
        self.stack = []
    
    def next(self):
        if len(self.stack) > 0 or self.node is not None:
            while self.node is not None:
                self.stack.append(self.node)
                self.node = self.node.left
            node = self.stack.pop()
            self.node = node.right
            return node.value
        else:
            raise StopIteration()


# In[19]:


tree = BinaryTree(
    left=BinaryTree(
        left=BinaryTree(1),
        value=2,
        right=BinaryTree(
            left=BinaryTree(3),
            value=4,
            right=BinaryTree(5)
        ),
    ),
    value=6,
    right=BinaryTree(
        value=7,
        right=BinaryTree(8)
    )
)


# In[20]:


for value in tree:
    print value,


# 不会出现之前的问题：

# In[21]:


for x,y in zip(tree, tree):
    print x, y