1 /*
2 ** nodebuild_events.cpp
3 **
4 ** A red-black tree for keeping track of segs that get touched by a splitter.
5 **
6 **---------------------------------------------------------------------------
7 ** Copyright 2002-2006 Randy Heit
8 ** All rights reserved.
9 **
10 ** Redistribution and use in source and binary forms, with or without
11 ** modification, are permitted provided that the following conditions
12 ** are met:
13 **
14 ** 1. Redistributions of source code must retain the above copyright
15 ** notice, this list of conditions and the following disclaimer.
16 ** 2. Redistributions in binary form must reproduce the above copyright
17 ** notice, this list of conditions and the following disclaimer in the
18 ** documentation and/or other materials provided with the distribution.
19 ** 3. The name of the author may not be used to endorse or promote products
20 ** derived from this software without specific prior written permission.
21 ** 4. When not used as part of ZDoom or a ZDoom derivative, this code will be
22 ** covered by the terms of the GNU General Public License as published by
23 ** the Free Software Foundation; either version 2 of the License, or (at
24 ** your option) any later version.
25 **
26 ** THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
27 ** IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
28 ** OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
29 ** IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
30 ** INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
31 ** NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
32 ** DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
33 ** THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
34 ** (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
35 ** THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
36 **---------------------------------------------------------------------------
37 **
38 */
39
40 #include <string.h>
41 #include "doomtype.h"
42 #include "nodebuild.h"
43
FEventTree()44 FEventTree::FEventTree ()
45 : Root (&Nil), Spare (NULL)
46 {
47 memset (&Nil, 0, sizeof(Nil));
48 }
49
~FEventTree()50 FEventTree::~FEventTree ()
51 {
52 FEvent *probe;
53
54 DeleteAll ();
55 probe = Spare;
56 while (probe != NULL)
57 {
58 FEvent *next = probe->Left;
59 delete probe;
60 probe = next;
61 }
62 }
63
DeleteAll()64 void FEventTree::DeleteAll ()
65 {
66 DeletionTraverser (Root);
67 Root = &Nil;
68 }
69
DeletionTraverser(FEvent * node)70 void FEventTree::DeletionTraverser (FEvent *node)
71 {
72 if (node != &Nil && node != NULL)
73 {
74 DeletionTraverser (node->Left);
75 DeletionTraverser (node->Right);
76 node->Left = Spare;
77 Spare = node;
78 }
79 }
80
GetNewNode()81 FEvent *FEventTree::GetNewNode ()
82 {
83 FEvent *node;
84
85 if (Spare != NULL)
86 {
87 node = Spare;
88 Spare = node->Left;
89 }
90 else
91 {
92 node = new FEvent;
93 }
94 return node;
95 }
96
Insert(FEvent * z)97 void FEventTree::Insert (FEvent *z)
98 {
99 FEvent *y = &Nil;
100 FEvent *x = Root;
101
102 while (x != &Nil)
103 {
104 y = x;
105 if (z->Distance < x->Distance)
106 {
107 x = x->Left;
108 }
109 else
110 {
111 x = x->Right;
112 }
113 }
114 z->Parent = y;
115 if (y == &Nil)
116 {
117 Root = z;
118 }
119 else if (z->Distance < y->Distance)
120 {
121 y->Left = z;
122 }
123 else
124 {
125 y->Right = z;
126 }
127 z->Left = &Nil;
128 z->Right = &Nil;
129 }
130
Successor(FEvent * event) const131 FEvent *FEventTree::Successor (FEvent *event) const
132 {
133 if (event->Right != &Nil)
134 {
135 event = event->Right;
136 while (event->Left != &Nil)
137 {
138 event = event->Left;
139 }
140 return event;
141 }
142 else
143 {
144 FEvent *y = event->Parent;
145 while (y != &Nil && event == y->Right)
146 {
147 event = y;
148 y = y->Parent;
149 }
150 return y;
151 }
152 }
153
Predecessor(FEvent * event) const154 FEvent *FEventTree::Predecessor (FEvent *event) const
155 {
156 if (event->Left != &Nil)
157 {
158 event = event->Left;
159 while (event->Right != &Nil)
160 {
161 event = event->Right;
162 }
163 return event;
164 }
165 else
166 {
167 FEvent *y = event->Parent;
168 while (y != &Nil && event == y->Left)
169 {
170 event = y;
171 y = y->Parent;
172 }
173 return y;
174 }
175 }
176
FindEvent(double key) const177 FEvent *FEventTree::FindEvent (double key) const
178 {
179 FEvent *node = Root;
180
181 while (node != &Nil)
182 {
183 if (node->Distance == key)
184 {
185 return node;
186 }
187 else if (node->Distance > key)
188 {
189 node = node->Left;
190 }
191 else
192 {
193 node = node->Right;
194 }
195 }
196 return NULL;
197 }
198
GetMinimum()199 FEvent *FEventTree::GetMinimum ()
200 {
201 FEvent *node = Root;
202
203 if (node == &Nil)
204 {
205 return NULL;
206 }
207 while (node->Left != &Nil)
208 {
209 node = node->Left;
210 }
211 return node;
212 }
213
PrintTree(const FEvent * event) const214 void FEventTree::PrintTree (const FEvent *event) const
215 {
216 // Use the CRT's sprintf so that it shares the same formatting as ZDBSP's output.
217 char buff[100];
218 if (event != &Nil)
219 {
220 PrintTree(event->Left);
221 sprintf(buff, " Distance %g, vertex %d, seg %u\n",
222 sqrt(event->Distance/4294967296.0), event->Info.Vertex, (unsigned)event->Info.FrontSeg);
223 Printf(PRINT_LOG, "%s", buff);
224 PrintTree(event->Right);
225 }
226 }
227