TreeIterators/tree_lazy_iterator.cc at develop · DannyBaobei/TreeIterators · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include "tree_definition.h"
#include "vczh/gc_ptr.h"
#include <functional>
#include <cstddef>


using namespace std;

#define  NO_GC 0

#if NO_GC
struct List {
    function <TreeNode_p_t()> first;
    function <List_p_t()>     rest;
};
#else
struct List:ENABLE_GC{
    function <TreeNode_p_t()> first;
    function <List_p_t()>     rest;
};
#endif

TreeNode_p_t first(List_p_t list1)
{
    return list1 == NULL ? NULL : list1->first();
}

List_p_t rest(List_p_t list1)
{
    return list1 == NULL ? NULL : list1->rest();
}

List_p_t Empty() {
    return NULL;
};
List_p_t alloc_node()
{
#if NO_GC
    List *node = new List();
#else
    List_p_t node = vczh::make_gc<List>().operator ->();
#endif
    return node;
}
List_p_t Singleton(TreeNode_p_t e) {
    List_p_t node = alloc_node();
    node->first = [=]()mutable{
        return e;
    };

    node->rest = [=]()mutable{
        return (List_p_t)NULL;
    };
    return node;
}

List_p_t Append(List_p_t list1, List_p_t list2)
{
    if (NULL == list1) return list2;
    if (NULL == list2) return list1;

    List_p_t node = alloc_node();
    node->first = [=]()mutable{
        return first(list1);
    };

    node->rest = [=]()mutable{
        return Append(rest(list1), list2);
    };
    return node;
}


List_p_t make_inorder_tree_iterator(TreeNode_p_t node)
{
    if (!node)
        return NULL;
    List_p_t listNode = alloc_node();
    listNode->first = [node]()mutable {
        return NULL != node->lchild ? first(make_inorder_tree_iterator(node->lchild)) : node;
    };
    listNode->rest = [node]()mutable {
        List_p_t left_it = (NULL == node->lchild ? NULL : make_inorder_tree_iterator(node->lchild));
        List_p_t root_it = Singleton(node);
        List_p_t right_it = (NULL == node->rchild ? NULL : make_inorder_tree_iterator(node->rchild));
        List_p_t it = Append(Append(left_it, root_it), right_it);
        return rest(it);
    };
    return listNode;
}

List_p_t make_preorder_tree_iterator(TreeNode_p_t node)
{
    if (!node)
        return NULL;
    List_p_t listNode = alloc_node();
    listNode->first = [node]()mutable {
        return node;
    };
    listNode->rest = [node]()mutable {
        List_p_t left_it = (NULL == node->lchild ? NULL : make_preorder_tree_iterator(node->lchild));
        List_p_t root_it = Singleton(node);
        List_p_t right_it = (NULL == node->rchild ? NULL : make_preorder_tree_iterator(node->rchild));
        List_p_t it = Append(Append(root_it, left_it), right_it);
        return rest(it);
    };
    return listNode;
}

List_p_t make_postorder_tree_iterator(TreeNode_p_t node)
{
    if (!node)
        return NULL;
    List_p_t listNode = alloc_node();

    listNode->first = [node]()mutable {
        if (NULL == node->lchild  &&  NULL == node->rchild)
            return node;
        return NULL != node->lchild ? first(make_postorder_tree_iterator(node->lchild)) : first(make_postorder_tree_iterator(node->rchild));
    };
    listNode->rest = [node]()mutable {
        List_p_t left_it = (NULL == node->lchild ? NULL : make_postorder_tree_iterator(node->lchild));
        List_p_t root_it = Singleton(node);
        List_p_t right_it = (NULL == node->rchild ? NULL : make_postorder_tree_iterator(node->rchild));
        List_p_t it = Append(Append(left_it, right_it), root_it);
        return rest(it);
    };
    return listNode;
}