# 浅拷贝操作只会拷贝被拷贝对象的第一层对象，对于更深层级的只不过是拷贝其引用，如下例中 `a[2]`
# 和 `lst[2]` 这两个对象为第二层，实际上浅拷贝之后，这两个还是一个对象。深拷贝会完全的拷贝被拷
# 贝对象的所有层级对象，也就是一个真正意义上的拷贝。
>>> from copy import copy, deepcopy
>>> lst = [1, 2, [3, 4]]
>>> a, b = copy(lst), deepcopy(lst)
>>> a, b
([1, 2, [3, 4]], [1, 2, [3, 4]])
>>> id(lst[2]), id(a[2]), id(b[2])
(139842737414224, 139842737414224, 139842737414584)
>>> lst[0] = 10
>>> a
[1, 2, [3, 4]]
>>> b
[1, 2, [3, 4]]
>>> lst[2][0] = 'test'
>>> lst
[10, 2, ['test', 4]]
>>> a
[1, 2, ['test', 4]]
>>> b
[1, 2, [3, 4]]

>>> def foo(a, b=[1, 2]):
        print(b)
        b.append(a)
        print(b)
>>> val = 4
>>> foo(val)
# [1, 2]
# [1, 2, 4]
>>> foo(val)
# [1, 2, 4]
# [1, 2, 4, 4]
# 这里可以看到，第二次执行函数时，默认参数 b 的值已经变成 `[1, 2, 4]` 了，原因是，默认参数只在第
# 一次执行时会进行初始化，后面就默认使用 **初始化后的这个对象(引用)**，但是这里 b 是可变对象，
#添加了一个元素还是之前的对象，所以，引用没变，不过是值变了而已。

# coding: utf-8

from collections import deque


class BNode:
    """ 二叉树节点 """

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


def level_traverse(binary_tree):
    """ 层次遍历二叉树 """
    stack = deque([binary_tree])
    while stack:
        top = stack.popleft()
        print(top.value)
        if top.left:
            stack.append(top.left)
        if top.right:
            stack.append(top.right)


if __name__ == "__main__":
    b_tree = BNode(1, BNode(2, BNode(4, BNode(5, BNode(7)))), BNode(3, BNode(6, right=BNode(8))))
    level_traverse(b_tree)

# 存在 V 型和 Y 型，如果交叉，则最后一个节点肯定是相同的，故直接从最后一个节点进行反向遍历。
# 反转单链表
def reverse_single_link_lst(link_lst):
    if not link_lst:
        return link_lst
    pre = link_lst
    cur = link_lst.next
    pre.next = None
    while cur:
        tmp = cur.next
        cur.next = pre
        pre = cur
        cur = tmp
    return pre

# 寻找交叉点
def point(node_a, node_b):
    if node_a is None or node_b is None:
        return None
    next_a, next_b = node_a, node_b
    while next_a or next_b:
        if next_a.val == next_b.val:
            if next_a.next and next_b.next and (next_a.next.val == next_b.next.val):
                next_a, next_b = next_a.next, next_b.next
                continue
            return next_a.val
        next_a, next_b = next_a.next, next_b.next
    return None

# 构造单链表
class Node(object):
    def __init__(self, value, next=None):
        self.val = value
        self.next = next

a = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
b = ListNode(7, ListNode(9, ListNode(4, ListNode(5))))

ra = reverse_single_link_lst(a)
rb = reverse_single_link_lst(b)
point(ra, rb)
# output:
# 4

# 快速排序，lz 当时写的比较复杂，但是是最常见的写法（紧张导致有几个小bug），如下
def quick_sort(lst, start, stop):
    if start < stop:
        i, j, x = start, stop, lst[start]
        while i < j:
            while (i < j) and (lst[j] > x):
                j -= 1
            if (i < j):
                lst[i] = lst[j]
                i += 1
            while (i < j) and (lst[i] < x):
                i += 1
            if (i < j):
                lst[j] = lst[i]
                j -= 1
        lst[i] = x
        quick_sort(lst, start, i-1)
        quick_sort(lst, i+1, stop)
    return lst

def qsort(alist):
    """
    quick sort(easy way, but more memory)
    test: python -m doctest qsort.py
    >>> import math
    >>> import random
    >>> size = 100
    >>> alist = [random.randint(0, size * 10) for i in range(size)]
    >>> qlist = qsort(alist)
    >>> alist.sort()
    >>> assert qlist == alist
    """

    if len(alist) <= 1:
        return alist

    key = alist[0]
    left_list, middle_list, right_list = [], [], []

    [{i < key: left_list, i == key: middle_list, i > key: right_list}[
        True
    ].append(i) for i in alist]

    return qsort(left_list) + middle_list + qsort(right_list)

# 可以指定重试次数，直到函数返回正确结果。
@retry(retries=3)
def func(*args, **kw):
    try:
        # some action
        return True
    except:
        return False

from functools import wraps

def retry(retries=3):
    def timesf(func):
        @wraps(func)
        def wrap(*args, **kw):
            i = 0
            status = True
            while status and i < times:
                status = func(*args, **kw)
                i += 1
            return status
        return wrap
    return timesf