BooleanExpression

Scripts

14 years
edited 8 years
Code (jass) Select
1
library BooleanExpression /* v1.2.0.0
2
************************************************************************************
3
*
4
*	*/ uses /*
5
*
6
*		*/ ErrorMessage	/*
7
*		*/ ListT		/*
8
*		*/ Table		/*
9
*		*/ Init			/*
10
*		*/ TableField	/*
11
*
12
************************************************************************************
13
*
14
*	struct BooleanExpression extends array
15
*
16
*		Description
17
*		-------------------------
18
*
19
*			Creates a single boolean expression via Or's
20
*
21
*			Provides a slight speed boost
22
*
23
*			Allows the for the safe usage of TriggerRemoveCondition given that the only boolexpr on the trigger
24
*			is the one from this struct
25
*
26
*			To put multiple boolean expressions on to one trigger, combine them with Or. Be sure to destroy later.
27
*
28
*			Alternatively, they can be wrapped with another BooleanExpression, but this will add overhead. Only use
29
*			if more than three are planned to be on one trigger.
30
*
31
*		Fields
32
*		-------------------------
33
*
34
*			readonly boolexpr expression
35
*
36
*				Examples:	call booleanExpression.register(myCode)
37
*							call TriggerRemoveCondition(thisTrigger, theOneCondition)
38
*							set theOneCondition = TriggerAddCondition(thisTrigger, booleanExpression.expression)
39
*
40
*			boolean reversed
41
*			-	if this is true, the expression will run in reverse
42
*
43
*		Methods
44
*		-------------------------
45
*
46
*			static method create takes boolean reversed returns BooleanExpression
47
*			-	if reversed is true, the expression will run in reverse
48
*
49
*			method destroy takes nothing returns nothing
50
*			-	only use .destroy with BooleanExpression from .create, not .register
51
*
52
*			method register takes boolexpr expression returns BooleanExpression
53
*			-	the returned BooleanExpression is a subtype to be used with
54
*			-	.unregister and .replace
55
*			method unregister takes nothing returns nothing
56
*			-	unregisters a BooleanExpression
57
*			-	only use BooleanExpression from .register, not .create
58
*
59
*			method replace takes boolexpr expression returns nothing
60
*			-	replaces the boolexpr inside of the registered expression
61
*			-	useful for updating expressions without breaking order
62
*			-	null expressions take no space and have no overhead, so use them
63
*			-	only use BooleanExpression from .register, not .create
64
*
65
*			method clear takes nothing returns nothing
66
*			-	only use .clear with BooleanExpression from .create, not .register
67
*
68
*			debug static method calculateMemoryUsage takes nothing returns integer
69
*			-	calculates how many instances are currently active
70
*			debug static method getAllocatedMemoryAsString takes nothing returns string
71
*			-	returns a list of all active instances as a string
72
*
73
************************************************************************************/
74
	private struct List extends array
75
		//! runtextmacro CREATE_TABLE_FIELD("public", "boolean", "reversed", "boolean")
76
77
		implement ListT
78
79
		private static method init takes nothing returns nothing
80
			//! runtextmacro INITIALIZE_TABLE_FIELD("reversed")
81
		endmethod
82
83
		implement Init
84
	endstruct
85
86
	private struct TreeNode extends array
87
		/*
88
		*	Tree Fields
89
		*/
90
		//! runtextmacro CREATE_TABLE_FIELD("public", "integer", "root", "thistype")
91
		//! runtextmacro CREATE_TABLE_FIELD("public", "integer", "left", "thistype")
92
		//! runtextmacro CREATE_TABLE_FIELD("public", "integer", "right", "thistype")
93
		//! runtextmacro CREATE_TABLE_FIELD("public", "integer", "height", "integer")
94
		
95
		/*
96
		*	Standard Fields
97
		*/
98
		//! runtextmacro CREATE_TABLE_FIELD("public", "boolexpr", "expression", "boolexpr")
99
		//! runtextmacro CREATE_TABLE_FIELD("public", "boolean", "canDestroy", "boolean")
100
		
101
		///! runtextmacro CREATE_TABLE_FIELD("public", "integer", "list", "ListExpression")
102
		
103
		public method operator isData takes nothing returns boolean
104
			return height == 1
105
		endmethod
106
		
107
		public method operator isNode takes nothing returns boolean
108
			return height != 1
109
		endmethod
110
		
111
		public method join takes nothing returns nothing
112
			if (canDestroy) then
113
				call DestroyBoolExpr(expression)
114
			endif
115
			
116
			if (left.expression == null) then
117
				set canDestroy = false
118
				
119
				if (right.expression == null) then
120
					call expression_clear()
121
				else
122
					set expression = right.expression
123
				endif
124
			elseif (right.expression == null) then
125
				set canDestroy = false
126
				
127
				set expression = left.expression
128
			elseif (List(this).list.reversed) then
129
				set canDestroy = true
130
				
131
				set expression = Or(right.expression, left.expression)
132
			else
133
				set canDestroy = true
134
				
135
				set expression = Or(left.expression, right.expression)
136
			endif
137
		endmethod
138
		
139
		public method rebuild takes nothing returns nothing
140
			if (isNode) then
141
				call left.rebuild()
142
				call right.rebuild()
143
				
144
				call join()
145
			endif
146
		endmethod
147
		
148
		public method replace takes boolexpr expression returns nothing
149
			if (this.expression == expression) then
150
				return
151
			endif
152
		
153
			if (expression == null) then
154
				call this.expression_clear()
155
			else
156
				set this.expression = expression
157
			endif
158
			
159
			loop
160
				set this = root
161
				exitwhen this == 0
162
				
163
				call join()
164
			endloop
165
		endmethod
166
		
167
		public static method create takes List parent returns thistype
168
			local thistype this = parent.enqueue()
169
			
170
			set canDestroy = false
171
			set height = 1
172
			
173
			return this
174
		endmethod
175
		
176
		public static method createData takes List parent returns thistype
177
			local thistype this = parent.push()
178
			
179
			set canDestroy = false
180
			
181
			return this
182
		endmethod
183
		
184
		method clean takes nothing returns nothing
185
			if (canDestroy) then
186
				call DestroyBoolExpr(expression)
187
			endif
188
			
189
			call expression_clear()
190
		endmethod
191
		
192
		method destroy takes nothing returns nothing
193
			call clean()
194
			
195
			call List(this).remove()
196
		endmethod
197
		
198
		public method operator sibling takes nothing returns thistype
199
			if (root != 0) then
200
				if (root.left == this) then
201
					return root.right
202
				else
203
					return root.left
204
				endif
205
			endif
206
			
207
			return 0
208
		endmethod
209
		
210
		method updateHeight takes nothing returns nothing
211
			if (left.height > right.height) then
212
				set height = left.height + 1
213
			else
214
				set height = right.height + 1
215
			endif
216
		endmethod
217
		
218
		method operator factor takes nothing returns integer
219
			return left.height - right.height
220
		endmethod
221
		
222
		method setRoot takes thistype newNode returns nothing
223
			local thistype root = this.root
224
		
225
			if (root != 0) then
226
				if (this == root.left) then
227
					set root.left = newNode
228
				else
229
					set root.right = newNode
230
				endif
231
			endif
232
			
233
			set newNode.root = root
234
		endmethod
235
	
236
		method rotateRight takes nothing returns thistype
237
			local thistype newRoot = left
238
			
239
			call setRoot(newRoot)
240
			set root = newRoot
241
			
242
			set left = newRoot.right
243
			set left.root = this
244
			set newRoot.right = this
245
			
246
			call updateHeight()
247
			call newRoot.updateHeight()
248
			
249
			call join()
250
			call newRoot.join()
251
			
252
			return newRoot
253
		endmethod
254
		
255
		method rotateLeft takes nothing returns thistype
256
			local thistype newRoot = right
257
			
258
			call setRoot(newRoot)
259
			set root = newRoot
260
			
261
			set right = newRoot.left
262
			set right.root = this
263
			set newRoot.left = this
264
			
265
			call updateHeight()
266
			call newRoot.updateHeight()
267
			
268
			call join()
269
			call newRoot.join()
270
			
271
			return newRoot
272
		endmethod
273
		
274
		method balance takes nothing returns thistype
275
			local integer factor
276
			local thistype node
277
			
278
			loop
279
				call updateHeight()
280
				
281
				set factor = this.factor
282
				
283
				if (factor > 1) then
284
					if (left.factor < 0) then
285
						call left.rotateLeft()
286
					endif
287
288
					set this = rotateRight()
289
290
					exitwhen true
291
				elseif (factor < -1) then
292
					if (right.factor > 0) then
293
						call right.rotateRight()
294
					endif
295
296
					set this = rotateLeft()
297
298
					exitwhen true
299
				else
300
					call join()
301
				endif
302
			
303
				set this = root
304
				exitwhen this == 0
305
			endloop
306
			
307
			if (this != 0) then
308
				set node = root
309
				
310
				loop
311
					exitwhen node == 0
312
					
313
					call node.updateHeight()
314
					call node.join()
315
					set node = node.root
316
				endloop
317
			endif
318
		
319
			return this
320
		endmethod
321
		
322
		private static method init takes nothing returns nothing
323
			//! runtextmacro INITIALIZE_TABLE_FIELD("root")
324
			//! runtextmacro INITIALIZE_TABLE_FIELD("left")
325
			//! runtextmacro INITIALIZE_TABLE_FIELD("right")
326
			//! runtextmacro INITIALIZE_TABLE_FIELD("height")
327
			//! runtextmacro INITIALIZE_TABLE_FIELD("expression")
328
			//! runtextmacro INITIALIZE_TABLE_FIELD("canDestroy")
329
		endmethod
330
		
331
		implement Init
332
	endstruct
333
	
334
	private struct Tree extends array
335
		//! runtextmacro CREATE_TABLE_FIELD("public", "integer", "root", "TreeNode")
336
		
337
		public static method create takes boolean reversed returns thistype
338
			local thistype this = List.create()
339
			
340
			set List(this).reversed = reversed
341
			
342
			return this
343
		endmethod
344
		
345
		method clear takes nothing returns nothing
346
			local List node = List(this).first
347
			
348
			loop
349
				exitwhen node == 0
350
				
351
				call TreeNode(node).clean()
352
				
353
				set node = node.next
354
			endloop
355
			
356
			call List(this).clear()
357
			
358
			call root_clear()
359
		endmethod
360
		
361
		method destroy takes nothing returns nothing
362
			call clear()
363
			
364
			call List(this).destroy()
365
		endmethod
366
		
367
		method operator reversed takes nothing returns boolean
368
			return List(this).reversed
369
		endmethod
370
		
371
		method operator reversed= takes boolean b returns nothing
372
			if (b == reversed) then
373
				return
374
			endif
375
			
376
			set List(this).reversed = b
377
			
378
			if (root != 0) then
379
				call root.rebuild()
380
			endif
381
		endmethod
382
		
383
		method updateRoot takes TreeNode node returns nothing
384
			if (node != 0 and node.root == 0) then
385
				set this.root = node
386
			endif
387
		endmethod
388
		
389
		method insert takes boolexpr expression returns TreeNode
390
			local TreeNode sibling = List(this).last
391
			local TreeNode node = TreeNode.create(this)
392
			local TreeNode root = 0
393
			local TreeNode grandroot = 0
394
			
395
			if (expression != null) then
396
				set node.expression = expression
397
			endif
398
			
399
			if (sibling != 0) then
400
				set root = TreeNode.createData(this)
401
				set grandroot = sibling.root
402
				
403
				set root.left = sibling
404
				set root.right = node
405
				set node.root = root
406
				set sibling.root = root
407
				set root.height = 2
408
				set root.root = grandroot
409
				
410
				call root.join()
411
				
412
				if (grandroot != 0) then
413
					set grandroot.right = root
414
					
415
					call updateRoot(grandroot.balance())
416
				else
417
					set this.root = root
418
				endif
419
			else
420
				set this.root = node
421
				call node.root_clear()
422
			endif
423
			
424
			call node.left_clear()
425
			call node.right_clear()
426
			
427
			return node
428
		endmethod
429
		
430
		method delete takes TreeNode node returns nothing
431
			local TreeNode sibling = node.sibling
432
			local TreeNode root = node.root
433
			local TreeNode grandroot
434
			
435
			if (root != 0) then
436
				set grandroot = root.root
437
			endif
438
			
439
			if (sibling != 0) then
440
				if (sibling.isData) then
441
					set sibling.root = grandroot
442
					
443
					if (grandroot != 0) then
444
						if (grandroot.left == root) then
445
							set grandroot.left = sibling
446
						else
447
							set grandroot.right = sibling
448
						endif
449
						
450
						call updateRoot(grandroot.balance())
451
					else
452
						set this.root = sibling
453
					endif
454
					
455
					call root.destroy()
456
				else
457
					set root.left = sibling.left
458
					set root.right = sibling.right
459
					call root.updateHeight()
460
					call root.join()
461
					
462
					if (sibling.left != 0) then
463
						set sibling.left.root = root
464
					endif
465
					if (sibling.right != 0) then
466
						set sibling.right.root = root
467
					endif
468
					
469
					call sibling.destroy()
470
					
471
					if (grandroot != 0) then
472
						call updateRoot(grandroot.balance())
473
					endif
474
				endif
475
			else
476
				set this.root = 0
477
			endif
478
			
479
			call node.destroy()
480
		endmethod
481
		
482
		private static method init takes nothing returns nothing
483
			//! runtextmacro INITIALIZE_TABLE_FIELD("root")
484
		endmethod
485
		
486
		implement Init
487
	endstruct
488
	
489
	struct BooleanExpression extends array
490
		method operator expression takes nothing returns boolexpr
491
			debug call ThrowError(not List(this).isList,	"BooleanExpression", "expression", "BooleanExpression", this, "Attempted To Read Null Boolean Expression.")
492
			
493
			if (Tree(this).root != 0) then
494
				return Tree(this).root.expression
495
			endif
496
			
497
			return null
498
		endmethod
499
		
500
		method operator reversed takes nothing returns boolean
501
			debug call ThrowError(not List(this).isList,	"BooleanExpression", "reversed", "BooleanExpression", this, "Attempted To Read Null Boolean Expression.")
502
			
503
			return Tree(this).reversed
504
		endmethod
505
		
506
		method operator reversed= takes boolean b returns nothing
507
			debug call ThrowError(not List(this).isList,	"BooleanExpression", "reversed", "BooleanExpression", this, "Attempted To Set Null Boolean Expression.")
508
			
509
			set Tree(this).reversed = b
510
		endmethod
511
		
512
		static method create takes boolean reversed returns thistype
513
			return Tree.create(reversed)
514
		endmethod
515
		
516
		method destroy takes nothing returns nothing
517
			debug call ThrowError(not List(this).isList,	"BooleanExpression", "reversed", "BooleanExpression", this, "Attempted To Destroy Null Boolean Expression.")
518
			call Tree(this).destroy()
519
		endmethod
520
		
521
		method register takes boolexpr expression returns BooleanExpression
522
			return Tree(this).insert(expression)
523
		endmethod
524
		
525
		method unregister takes nothing returns nothing
526
			debug call ThrowError(not TreeNode(this).isData,	"BooleanExpression", "unregister", "BooleanExpression", this, "Attempted To Unregister Null Boolean Expression.")
527
			call Tree(List(this).list).delete(this)
528
		endmethod
529
		
530
		method replace takes boolexpr expression returns nothing
531
			debug call ThrowError(not TreeNode(this).isData,	"BooleanExpression", "replace", "BooleanExpression", this, "Attempted To Replace Null Boolean Expression.")
532
			call TreeNode(this).replace(expression)
533
		endmethod
534
		
535
		method clear takes nothing returns nothing
536
			debug call ThrowError(not List(this).isList,	"BooleanExpression", "clear", "BooleanExpression", this, "Attempted To Clear Null Boolean Expression.")
537
			call Tree(this).clear()
538
		endmethod
539
		
540
		private static string indentation = "            "
541
542
		static method printEx takes TreeNode node, string indent, boolean height returns nothing
543
			if (node != 0) then
544
				call printEx(node.right, indent + indentation, height)
545
				
546
				if (height) then
547
					call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 60000, indent + I2S(node.height))
548
				else
549
					call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 60000, indent + I2S(node))
550
				endif
551
				
552
				call printEx(node.left, indent + indentation, height)
553
			endif
554
		endmethod
555
		
556
		method print takes boolean height returns nothing
557
			call printEx(Tree(this).root, "", height)
558
			call DisplayTimedTextFromPlayer(GetLocalPlayer(), 0, 0, 60000, "------------------------------------")
559
		endmethod
560
		
561
		debug static method calculateMemoryUsage takes nothing returns integer
562
			debug return List.calculateMemoryUsage()
563
		debug endmethod
564
		
565
		debug static method getAllocatedMemoryAsString takes nothing returns string
566
			debug return List.getAllocatedMemoryAsString()
567
		debug endmethod
568
	endstruct
569
endlibrary