Overview Package Class Source Class tree Glossary
previous class      next class frames      no frames

UWindow.UWindowList


00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072
00073
00074
00075
00076
00077
00078
00079
00080
00081
00082
00083
00084
00085
00086
00087
00088
00089
00090
00091
00092
00093
00094
00095
00096
00097
00098
00099
00100
00101
00102
00103
00104
00105
00106
00107
00108
00109
00110
00111
00112
00113
00114
00115
00116
00117
00118
00119
00120
00121
00122
00123
00124
00125
00126
00127
00128
00129
00130
00131
00132
00133
00134
00135
00136
00137
00138
00139
00140
00141
00142
00143
00144
00145
00146
00147
00148
00149
00150
00151
00152
00153
00154
00155
00156
00157
00158
00159
00160
00161
00162
00163
00164
00165
00166
00167
00168
00169
00170
00171
00172
00173
00174
00175
00176
00177
00178
00179
00180
00181
00182
00183
00184
00185
00186
00187
00188
00189
00190
00191
00192
00193
00194
00195
00196
00197
00198
00199
00200
00201
00202
00203
00204
00205
00206
00207
00208
00209
00210
00211
00212
00213
00214
00215
00216
00217
00218
00219
00220
00221
00222
00223
00224
00225
00226
00227
00228
00229
00230
00231
00232
00233
00234
00235
00236
00237
00238
00239
00240
00241
00242
00243
00244
00245
00246
00247
00248
00249
00250
00251
00252
00253
00254
00255
00256
00257
00258
00259
00260
00261
00262
00263
00264
00265
00266
00267
00268
00269
00270
00271
00272
00273
00274
00275
00276
00277
00278
00279
00280
00281
00282
00283
00284
00285
00286
00287
00288
00289
00290
00291
00292
00293
00294
00295
00296
00297
00298
00299
00300
00301
00302
00303
00304
00305
00306
00307
00308
00309
00310
00311
00312
00313
00314
00315
00316
00317
00318
00319
00320
00321
00322
00323
00324
00325
00326
00327
00328
00329
00330
00331
00332
00333
00334
00335
00336
00337
00338
00339
00340
00341
00342
00343
00344
00345
00346
00347
00348
00349
00350
00351
00352
00353
00354
00355
00356
00357
00358
00359
00360
00361
00362
00363
00364
00365
00366
00367
00368
00369
00370
00371
00372
00373
00374
00375
00376
00377
00378
00379
00380
00381
00382
00383
00384
00385
00386
00387
00388
00389
00390
00391
00392
00393
00394
00395
00396
00397
00398
00399
00400
00401
00402
00403
00404
00405
00406
00407
00408
00409
00410
00411
00412
00413
00414
00415
00416
00417
00418
00419
00420
00421
00422
00423
00424
00425
00426
00427
00428
00429
00430
00431
00432
00433
00434
00435
00436
00437
00438
00439
00440
00441
00442
00443
00444
00445
00446
00447
00448
00449
00450
00451
00452
00453
00454
00455
00456
00457
00458
00459
00460
00461
00462
00463
00464
00465
00466
00467
00468
00469
00470
00471
00472
00473
00474
00475
00476
00477
00478
00479
00480
00481
00482
00483
00484
00485
00486
00487
00488
00489
00490
00491
00492
00493
00494
00495
00496
00497
00498
00499
00500
00501
00502
00503
00504
00505
00506
00507
00508
00509
00510
00511
00512
00513
00514
00515
00516
00517
00518
00519
00520
00521
00522
00523
00524
00525
00526
00527
00528
00529
00530
00531
00532
00533
00534
00535
00536
00537
00538
00539
00540
00541
00542
00543
00544
00545
00546
00547
00548
00549
00550
00551
00552
00553
00554
00555
00556
00557
00558
00559
00560
00561
00562
00563
00564
00565
00566
00567
00568
00569
00570
00571
00572
00573
00574
00575
00576
00577
00578
00579
00580
00581
00582
00583
00584
00585
00586
00587
00588
00589
00590
00591
00592
00593
00594
00595
00596
00597
00598
00599
00600
00601
00602
00603
00604
00605
00606
00607
00608
00609
00610
00611
00612
00613
00614
00615
00616
00617
00618
00619
00620
00621
00622
00623
00624
00625
00626
00627
00628
00629
00630
00631
00632
00633
00634
00635
00636
00637
00638
00639
00640
00641
00642
00643
00644
00645
//=============================================================================
// UWindowList - a generic linked list class
//=============================================================================
class UWindowList extends UWindowBase;

var UWindowList	Next;
var UWindowList	Last;		// Only valid for sentinel
var UWindowList	Prev;
var UWindowList	Sentinel;
var int			InternalCount;
var bool		bItemOrderChanged;

var bool		bSuspendableSort;

var int			CompareCount;
var bool		bSortSuspended;
var UWindowList CurrentSortItem;

// Binary tree variables for sentinel
var bool		bTreeSort;

// Binary tree variables for each element
var UWindowList BranchLeft;
var UWindowList BranchRight;
var UWindowList ParentNode;

var int Tag;

/* Tree Sorting:

- Items must be added with AppendItem()
- Items which require resorting must call MoveItemSorted()
- Should call Tick and set bSuspendableSort - for large sorts!

*/

/********** These things can be called on any element **********/

function UWindowList CreateItem(Class<UWindowList> C)
{
	local UWindowList NewElement;

	NewElement = New C;
	return NewElement;
}

function GraftLeft(UWindowList NewLeft)
{
	assert(Sentinel.bTreeSort);

	BranchLeft = NewLeft;
	if(NewLeft != None)
		NewLeft.ParentNode = Self;
}

function GraftRight(UWindowList NewRight)
{
	assert(Sentinel.bTreeSort);

	BranchRight = NewRight;
	if(NewRight != None)
		NewRight.ParentNode = Self;
}

// Return rightmost child of subtree
function UWindowList RightMost()
{
	local UWindowList L;

	assert(Sentinel.bTreeSort);

	if(BranchRight == None)
		return None;

	L = Self;
	while(L.BranchRight != None)
		L = L.BranchRight;

	return L;
}

// Return leftmost child of subtree
function UWindowList LeftMost()
{
	local UWindowList L;

	assert(Sentinel.bTreeSort);

	if(BranchLeft == None)
		return None;

	L = Self;
	while(L.BranchLeft != None)
		L = L.BranchLeft;

	return L;
}

function Remove()
{
	local UWindowList T;

	if(Next != None)
		Next.Prev = Prev;
	
	if(Prev != None)
		Prev.Next = Next;
	
	if(Sentinel != None)
	{
		if(Sentinel.bTreeSort && ParentNode!=None)
		{
			if(BranchLeft != None)
			{
				if(ParentNode.BranchLeft == Self)
					ParentNode.GraftLeft(BranchLeft);
				if(ParentNode.BranchRight == Self)
					ParentNode.GraftRight(BranchLeft);

				// If we had a right branch we better move it
				// into the far right of the left branch.

				T = BranchLeft.Rightmost();
				if(T != None)
					T.GraftRight(BranchRight);
			}
			else
			{
				if(ParentNode.BranchLeft == Self)
					ParentNode.GraftLeft(BranchRight);
				if(ParentNode.BranchRight == Self)
					ParentNode.GraftRight(BranchRight);

				// no left branch to worry about.
			}
	
			ParentNode = None;
			BranchLeft = None;
			BranchRight = None;
		}

		Sentinel.InternalCount--;
		Sentinel.bItemOrderChanged = True;

		if(Sentinel.Last == Self)
			Sentinel.Last = Prev;

		Prev=None;
		Next=None;
	
	/*	Sentinel.Validate();  */
		Sentinel = None;
	}
}

function int Compare(UWindowList T, UWindowList B)
{
	// declare actual sort method in subclass
	return 0;
}

// Inserts a new element before us.  DO NOT CALL on the sentinel.
function UWindowList InsertBefore(Class<UWindowList> C)
{
	local UWindowList NewElement;

	NewElement = CreateItem(C);
	InsertItemBefore(NewElement);

	return NewElement;
}

function UWindowList InsertAfter(Class<UWindowList> C)
{
	local UWindowList NewElement;

	NewElement = CreateItem(C);
	InsertItemAfter(NewElement);

	return NewElement;
}


// Inserts an element before us.  DO NOT CALL on the sentinel.
function InsertItemBefore(UWindowList NewElement)
{
	assert(Sentinel != Self);

	NewElement.BranchLeft = None;
	NewElement.BranchRight = None;
	NewElement.ParentNode = None;
	NewElement.Sentinel = Sentinel;	
	NewElement.BranchLeft = None;
	NewElement.BranchRight = None;
	NewElement.ParentNode = None;
	NewElement.Prev = Prev;	
	Prev.Next = NewElement;
	Prev = NewElement;
	NewElement.Next = Self;

	if(Sentinel.Next == Self)
		Sentinel.Next = NewElement;

	Sentinel.InternalCount++;
	Sentinel.bItemOrderChanged = True;
}

function InsertItemAfter(UWindowList NewElement, optional bool bCheckShowItem)
{
	local UWindowList N;
	
	N = Next;
	if(bCheckShowItem)
		while(N != None && !N.ShowThisItem())
			N = N.Next; 

	if(N != None)
		N.InsertItemBefore(NewElement);
	else
		Sentinel.DoAppendItem(NewElement);
	Sentinel.bItemOrderChanged = True;
}

function ContinueSort()
{
	local UWindowList N;

	CompareCount = 0;
	bSortSuspended = False;

	while(CurrentSortItem != None)
	{
		N = CurrentSortItem.Next;
		AppendItem(CurrentSortItem);
		CurrentSortItem = N;

		// split sort over multiple frames, if it's BIG
		if(CompareCount >= 10000 && bSuspendableSort)
		{
			bSortSuspended = True;
			return;
		}
	}		
}

function Tick(float Delta)
{
	if(bSortSuspended)
		ContinueSort();
}

function UWindowList Sort()
{
	local UWindowList S;
	local UWindowList CurrentItem;
	local UWindowList Previous;
	local UWindowList Best;
	local UWindowList BestPrev;

	if(bTreeSort)
	{
		if(bSortSuspended)
		{
			ContinueSort();
			return Self;
		}

		CurrentSortItem = Next;
		DisconnectList();
		ContinueSort();
		return Self;
	}

	CurrentItem = Self;

	while(CurrentItem != None)
	{
		S = CurrentItem.Next;	Best = CurrentItem.Next;
		Previous = CurrentItem;	BestPrev = CurrentItem;
		
		// Find the best server
		while(S != None)
		{
			if(CurrentItem.Compare(S, Best) <= 0) 
			{
				Best = S;
				BestPrev = Previous;
			}
			
			Previous = S;
			S = S.Next;
		}

		// If we're not already in the right order, move the best one next.
		if(Best != CurrentItem.Next)
		{
			// Delete Best's old position
			BestPrev.Next = Best.Next;
			if(BestPrev.Next != None)
				BestPrev.Next.Prev = BestPrev;

			// Fix Self and Best
			Best.Prev = CurrentItem;
			Best.Next = CurrentItem.Next;
			CurrentItem.Next.Prev = Best; 
			CurrentItem.Next = Best;
			
			// Fix up Sentinel if Best was also Last 
			if(Sentinel.Last == Best)
			{
				Sentinel.Last = BestPrev;
				if(Sentinel.Last == None)
					Sentinel.Last = Sentinel;
			}
		}

		CurrentItem = CurrentItem.Next;
	}

	//Validate();
	return Self;
}

function DisconnectList() 
{
	Next=None;
	Last=Self;
	Prev=None;
	BranchLeft = None;
	BranchRight = None;
	ParentNode = None;
	InternalCount = 0;
	Sentinel.bItemOrderChanged = True;
}

function DestroyList() 
{
	local UWindowList L, Temp;
	L = Next;

	InternalCount = 0;
	if(Sentinel != None)
		Sentinel.bItemOrderChanged = True;

	while(L != None)
	{
		Temp = L.Next;
		L.DestroyListItem();
		L = Temp;
	}
	DestroyListItem();
}

function DestroyListItem()
{
	Next=None;
	Last=Self;
	Sentinel=None;
	Prev=None;
	BranchLeft=None;
	BranchRight=None;
	ParentNode=None;
}

function int CountShown() 
{
	local int C;
	local UWindowList I;

	for(I = Next;I != None; I = I.Next)
		if(I.ShowThisItem())
			C++;

	return C;
}

function UWindowList CopyExistingListItem(Class<UWindowList> ItemClass, UWindowList SourceItem)
{
	local UWindowList I;

	I = Append(ItemClass);
	Sentinel.bItemOrderChanged = True;

	return I;
}

// for Listboxes only (so far)
function bool ShowThisItem()
{
	return True;
}

/********** These things can only be called on the sentinel **********/
function int Count() 
{
	return InternalCount;
}

function MoveItemSorted(UWindowList Item)
{
	local UWindowList L;

	if(bTreeSort)
	{
		Item.Remove();
		AppendItem(Item);
	}
	else
	{
		for(L=Next;L != None; L = L.Next)
			if(Compare(Item, L) <= 0) break;

		if(L != Item)
		{
			Item.Remove();
			if(L == None)
				AppendItem(Item);
			else
				L.InsertItemBefore(Item);
		}
	}
}

function SetupSentinel(optional bool bInTreeSort)
{
	Last = Self;
	Next = None;
	Prev = None;
	BranchLeft = None;
	BranchRight = None;
	ParentNode = None;
	Sentinel = Self;
	InternalCount = 0;
	bItemOrderChanged = True;
	bTreeSort = bInTreeSort;
}

function Validate()
{
	local UWindowList I, Previous;
	local int Count;

	if(Sentinel != Self)
	{
		Log("Calling Sentinel.Validate() from "$Self);
		Sentinel.Validate();
		return;
	}

	Log("BEGIN Validate(): "$Class);

	Count = 0;
	Previous = Self;

	for(I = Next; I != None; I = I.Next)
	{
		Log("Checking item: "$Count);

		if(I.Sentinel != Self)
			Log("   I.Sentinel reference is broken");
	
		if(I.Prev != Previous)
			Log("   I.Prev reference is broken");

		if(Last == I && I.Next != None)
			Log("   Item is Sentinel.Last but Item has valid Next");

		if(I.Next == None && Last != I)
			Log("   Item is Item.Next is none, but Item is not Sentinel.Last");

		Previous = I;
		Count++;
	}

	Log("END Validate(): "$Class);		
}

// For sentinel only
function UWindowList Append(Class<UWindowList> C)
{
	local UWindowList NewElement;

	NewElement = CreateItem(C);
	AppendItem(NewElement);	
	
	return NewElement;
}

function AppendItem(UWindowList NewElement)
{
	local UWindowList Node, OldNode, Temp;
	local int Test;

	if(bTreeSort)
	{
		// Check for worst cases!
		if(Next != None && Last != Self)
		{
			if(Compare(NewElement, Last) >= 0)
			{
				// put at end of list
				Node = Last;
				Node.InsertItemAfter(NewElement, False);
				Node.GraftRight(NewElement);
				return;	
			}

			if(Compare(NewElement, Next) <= 0)
			{
				// put at front of list
				Node = Next;
				Node.InsertItemBefore(NewElement);
				Node.GraftLeft(NewElement);
				return;
			}
		}

		Node = Self;
		while(True)
		{
			if(Node == Self)
				Test = 1;
			else
				Test = Compare(NewElement, Node);

			// special case for equality
			if(Test == 0)
			{
				Node.InsertItemAfter(NewElement, False);
				return;
			}
			else
			if(Test > 0)
			{
				// Traverse right
				OldNode = Node;
				Node = Node.BranchRight;
				if(Node == None)
				{
					// Move past equal values
					Temp = OldNode;
					while(Temp.Next != None && Temp.Next.ParentNode == None)
						Temp = Temp.Next;
					
					Temp.InsertItemAfter(NewElement, False);
					OldNode.GraftRight(NewElement);
					return;
				}
			}
			else
			{
				// Traverse left
				OldNode = Node;
				Node = Node.BranchLeft;
				if(Node == None)
				{
					OldNode.InsertItemBefore(NewElement);
					OldNode.GraftLeft(NewElement);
					return;
				}
			}
		}
	}
	else
		DoAppendItem(NewElement);
}

function DoAppendItem(UWindowList NewElement)
{
	NewElement.Next = None;
	Last.Next = NewElement;
	NewElement.Prev = Last;
	NewElement.Sentinel = Self;
	NewElement.BranchLeft = None;
	NewElement.BranchRight = None;
	NewElement.ParentNode = None;
	Last = NewElement;
	Sentinel.InternalCount++;
	Sentinel.bItemOrderChanged = True;
}


// For sentinel only
function UWindowList Insert(Class<UWindowList> C)
{
	local UWindowList NewElement;

	NewElement = CreateItem(C);
	InsertItem(NewElement);
	
	return NewElement;
}

function InsertItem(UWindowList NewElement)
{
	NewElement.Next = Next;
	if(Next != None)
		Next.Prev = NewElement;
	Next = NewElement;
	if(Last == Self)
		Last = Next;
	NewElement.Prev = Self;
	NewElement.Sentinel = Self;	
	NewElement.BranchLeft = None;
	NewElement.BranchRight = None;
	NewElement.ParentNode = None;
	Sentinel.InternalCount++;
	Sentinel.bItemOrderChanged = True;
}

// For sentinel only
function UWindowList FindEntry(int Index)
{
	local UWindowList l;
	local int i;

	l = Next;
	for(i=0;i<Index;i++) 
	{
		l = l.Next;
		if(l==None) return None;
	}
	return l;
}

function AppendListCopy(UWindowList L)
{
	if(L == None)
		return;

	for(L = L.Next;L != None; L = L.Next)
		CopyExistingListItem(L.Class, L);
}

function Clear()
{
	InternalCount = 0;
	ParentNode = None;
	BranchLeft = None;
	BranchRight = None;
	bItemOrderChanged = True;
	Next = None;	
	Last = Self;
}

Overview Package Class Source Class tree Glossary
previous class      next class frames      no frames
Class file time: ne 5.9.2004 16:02:32.000 - Creation time: st 23.5.2018 00:10:50.088 - Created with UnCodeX