1// Licensed to the .NET Foundation under one or more agreements.
2// The .NET Foundation licenses this file to you under the MIT license.
3// See the LICENSE file in the project root for more information.
4
5#ifndef __GENERIC_TREE_H__
6#define __GENERIC_TREE_H__
7
8#include <windows.h>
9
10// Partially balanced binary tree
11// it does individual rotations on insertion, but does nto allow deletion.
12// thus the worst case depth is not (n), but (n/2)
13// Generic paramter is the element type
14// Find and Add require a method that compares 2 elements
15template <typename _E>
16struct tree
17{
18 _E name;
19 tree<_E> *lChild;
20 tree<_E> *rChild;
21 size_t lDepth;
22 size_t rDepth;
23
24 tree(_E e)
25 {
26 name = e;
27 lChild = rChild = NULL;
28 lDepth = rDepth = 0;
29 }
30 ~tree()
31 {
32 Cleanup();
33 }
34
35 bool InOrderWalk( bool (WalkFunc)(_E))
36 {
37 if (lChild != NULL && !lChild->InOrderWalk(WalkFunc))
38 return false;
39 if (!WalkFunc(name))
40 return false;
41 if (rChild != NULL)
42 return rChild->InOrderWalk(WalkFunc);
43 return true;
44 }
45
46 /*
47 * return the depths of the tree from here down (minimum of 1)
48 */
49 size_t MaxDepth()
50 {
51 return lDepth > rDepth ? lDepth + 1 : rDepth + 1;
52 }
53
54 /*
55 * Search the binary tree for the given string
56 * return a pointer to it was added or NULL if it
57 * doesn't exist
58 */
59 _E * Find(_E SearchVal, int (__cdecl CompFunc)(_E, _E))
60 {
61 int cmp = CompFunc(name, SearchVal);
62 if (cmp < 0)
63 {
64 if (lChild == NULL)
65 return NULL;
66 else
67 return lChild->Find(SearchVal, CompFunc);
68 }
69 else if (cmp > 0)
70 {
71 if (rChild == NULL)
72 return NULL;
73 else
74 return rChild->Find(SearchVal, CompFunc);
75 }
76 else
77 return &name;
78 }
79
80 /*
81 * Search the binary tree and add the given string
82 * return S_OK if it was added or S_FALSE if it already
83 * exists (or E_OUTOFMEMORY)
84 */
85 HRESULT Add(_E add
86 , int (__cdecl CompFunc)(_E, _E))
87 {
88 int cmp = CompFunc(name, add
89 );
90REDO:
91 if (cmp == 0)
92 return S_FALSE;
93
94 if (cmp < 0)
95 {
96 if (lChild == NULL)
97 {
98 lDepth = 1;
99 lChild = new tree<_E>(add
100 );
101 if (lChild == NULL)
102 return E_OUTOFMEMORY;
103 return S_OK;
104 }
105 else if (rDepth < lDepth)
106 {
107 tree<_E> *temp = new tree<_E>(name);
108 if (temp == NULL)
109 return E_OUTOFMEMORY;
110 temp->rChild = rChild;
111 temp->rDepth = rDepth;
112 if (lChild != NULL &&
113 (cmp = CompFunc(lChild->name, add
114 )) > 0)
115 {
116 // push right
117 temp->lChild = NULL;
118 temp->lDepth = 0;
119 name = add
120 ;
121 rChild = temp;
122 rDepth++;
123 return S_OK;
124 }
125 else if (cmp == 0)
126 {
127 temp->rChild = NULL;
128 delete temp;
129 return S_FALSE;
130 }
131 else
132 {
133 // Rotate right
134 temp->lChild = lChild->rChild;
135 temp->lDepth = lChild->rDepth;
136 name = lChild->name;
137 lDepth = lChild->lDepth;
138 rDepth = temp->MaxDepth();
139 rChild = temp;
140 temp = lChild->lChild;
141 lChild->lChild = lChild->rChild = NULL;
142 delete lChild;
143 lChild = temp;
144 goto REDO;
145 }
146 }
147 else
148 {
149 HRESULT hr = lChild->Add(add
150 , CompFunc);
151 lDepth = lChild->MaxDepth();
152 return hr;
153 }
154 }
155 else
156 {
157 if (rChild == NULL)
158 {
159 rDepth = 1;
160 rChild = new tree<_E>(add
161 );
162 if (rChild == NULL)
163 return E_OUTOFMEMORY;
164 return S_OK;
165 }
166 else if (lDepth < rDepth)
167 {
168 tree<_E> *temp = new tree<_E>(name);
169 if (temp == NULL)
170 return E_OUTOFMEMORY;
171 temp->lChild = lChild;
172 temp->lDepth = lDepth;
173 if (rChild != NULL &&
174 (cmp = CompFunc(rChild->name, add
175 )) < 0)
176 {
177 // push left
178 temp->rChild = NULL;
179 temp->rDepth = 0;
180 name = add
181 ;
182 lChild = temp;
183 lDepth++;
184 return S_OK;
185 }
186 else if (cmp == 0)
187 {
188 temp->lChild = NULL;
189 delete temp;
190 return S_FALSE;
191 }
192 else
193 {
194 // Rotate left
195 temp->rChild = rChild->lChild;
196 temp->rDepth = rChild->lDepth;
197 name = rChild->name;
198 rDepth = rChild->rDepth;
199 lDepth = temp->MaxDepth();
200 lChild = temp;
201 temp = rChild->rChild;
202 rChild->rChild = rChild->lChild = NULL;
203 delete rChild;
204 rChild = temp;
205 goto REDO;
206 }
207 }
208 else
209 {
210 HRESULT hr = rChild->Add(add
211 , CompFunc);
212 rDepth = rChild->MaxDepth();
213 return hr;
214 }
215 }
216 }
217
218 /*
219 * Free the memory allocated by the tree (recursive)
220 */
221 void Cleanup()
222 {
223 if (this == NULL)
224 return ;
225 if (lChild != NULL)
226 {
227 lChild->Cleanup();
228 delete lChild;
229 lChild = NULL;
230 }
231 if (rChild != NULL)
232 {
233 rChild->Cleanup();
234 delete rChild;
235 rChild = NULL;
236
237 }
238 }
239
240};
241
242#endif // __GENERIC_TREE_H__
243