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
130
131
132
133
134
135
|
/*-----------------------------------------------------------------------
File : clb_avlgeneric.h
Author: Stephan Schulz
Contents
Macros for the creation of generic binary tree functions. Currently
used for traversal functions only. Please note that the name is
obsolete (used for convenience only). The functions currently
implemented are generic for binary search trees, and binary search
trees in E are splay trees by now.
Copyright 1998, 1999 by the author.
This code is released under the GNU General Public Licence and
the GNU Lesser General Public License.
See the file COPYING in the main E directory for details..
Run "eprover -h" for contact information.
Changes
<1> Sat May 30 17:55:39 MET DST 1998
New
-----------------------------------------------------------------------*/
#ifndef CLB_AVLGENERIC
#define CLB_AVLGENERIC
#include <clb_pstacks.h>
/*---------------------------------------------------------------------*/
/* Data type declarations */
/*---------------------------------------------------------------------*/
/*---------------------------------------------------------------------*/
/* Exported Functions and Variables */
/*---------------------------------------------------------------------*/
/*-----------------------------------------------------------------------
//
// MACRO: AVL_TRAVERSE_DECLARATION()
//
// Produce a declaration for AVL traversal functions. Name is the name
// prefix to use for the functions, type is the pointer type used in
// tree construction.
//
/----------------------------------------------------------------------*/
#define AVL_TRAVERSE_DECLARATION(name,type)\
PStack_p name##TraverseInit(type root);\
type name##TraverseNext(PStack_p state);
/*-----------------------------------------------------------------------
//
// MACRO: AVL_TRAVERSE_DEFINITION()
//
// Produce code for AVL traversal functions as follows:
//
//-----------------------------------------------------------------------
//
// Function: <name>TraverseInit()
//
// Return a stack containing the path to the smallest element in the
// avl tree.
//
// Global Variables: -
//
// Side Effects : Memory operations
//
//---------------------------------------------------------------------
//
// Function: <name>TraverseNext()
//
// Given a stack describing a traversal state, return the next node
// and update the stack.
//
// Global Variables: -
//
// Side Effects : Updates stack
//
/----------------------------------------------------------------------*/
#define AVL_TRAVERSE_DEFINITION(name,type)\
PStack_p name##TraverseInit(type root)\
{\
PStack_p stack = PStackAlloc();\
\
while(root)\
{\
PStackPushP(stack, root);\
root = root->lson;\
}\
return stack;\
}\
\
\
type name##TraverseNext(PStack_p state)\
{\
type handle, res;\
\
if(PStackEmpty(state))\
{\
return NULL;\
}\
res = PStackPopP(state);\
handle = res->rson;\
while(handle)\
{\
PStackPushP(state, handle);\
handle = handle->lson;\
}\
return res;\
}
#endif
/*---------------------------------------------------------------------*/
/* End of File */
/*---------------------------------------------------------------------*/
|
