Core.Object | +--UWindow.UWindowBase | +--UWindow.UWindowList
UWindowList
BranchLeft
BranchRight
int
CompareCount
CurrentSortItem
InternalCount
Last
Next
ParentNode
Prev
Sentinel
bool
bItemOrderChanged
bSortSuspended
bSuspendableSort
bTreeSort
void
AppendItem(UWindowList NewElement)
AppendListCopy(UWindowList L)
Clear()
Compare(UWindowList T, UWindowList B)
ContinueSort()
Count()
/********** These things can only be called on the sentinel **********/
CountShown()
DestroyList()
DestroyListItem()
DisconnectList()
DoAppendItem(UWindowList NewElement)
FindEntry(int Index)
// For sentinel only
GraftLeft(UWindowList NewLeft)
GraftRight(UWindowList NewRight)
InsertItem(UWindowList NewElement)
InsertItemAfter(UWindowList NewElement, optional bool)
InsertItemBefore(UWindowList NewElement)
// Inserts an element before us. DO NOT CALL on the sentinel.
LeftMost()
// Return leftmost child of subtree
MoveItemSorted(UWindowList Item)
Remove()
RightMost()
// Return rightmost child of subtree
SetupSentinel(optional bool)
ShowThisItem()
// for Listboxes only (so far)
Sort()
Tick(float Delta)
Validate()
00001 //============================================================================= 00002 // UWindowList - a generic linked list class 00003 //============================================================================= 00004 class UWindowList extends UWindowBase; 00005 00006 var UWindowList Next; 00007 var UWindowList Last; // Only valid for sentinel 00008 var UWindowList Prev; 00009 var UWindowList Sentinel; 00010 var int InternalCount; 00011 var bool bItemOrderChanged; 00012 00013 var bool bSuspendableSort; 00014 00015 var int CompareCount; 00016 var bool bSortSuspended; 00017 var UWindowList CurrentSortItem; 00018 00019 // Binary tree variables for sentinel 00020 var bool bTreeSort; 00021 00022 // Binary tree variables for each element 00023 var UWindowList BranchLeft; 00024 var UWindowList BranchRight; 00025 var UWindowList ParentNode; 00026 00027 /* Tree Sorting: 00028 00029 - Items must be added with AppendItem() 00030 - Items which require resorting must call MoveItemSorted() 00031 - Should call Tick and set bSuspendableSort - for large sorts! 00032 00033 */ 00034 00035 /********** These things can be called on any element **********/ 00036 00037 function UWindowList CreateItem(Class<UWindowList> C) 00038 { 00039 local UWindowList NewElement; 00040 00041 NewElement = New C; 00042 return NewElement; 00043 } 00044 00045 function GraftLeft(UWindowList NewLeft) 00046 { 00047 assert(Sentinel.bTreeSort); 00048 00049 BranchLeft = NewLeft; 00050 if(NewLeft != None) 00051 NewLeft.ParentNode = Self; 00052 } 00053 00054 function GraftRight(UWindowList NewRight) 00055 { 00056 assert(Sentinel.bTreeSort); 00057 00058 BranchRight = NewRight; 00059 if(NewRight != None) 00060 NewRight.ParentNode = Self; 00061 } 00062 00063 // Return rightmost child of subtree 00064 function UWindowList RightMost() 00065 { 00066 local UWindowList L; 00067 00068 assert(Sentinel.bTreeSort); 00069 00070 if(BranchRight == None) 00071 return None; 00072 00073 L = Self; 00074 while(L.BranchRight != None) 00075 L = L.BranchRight; 00076 00077 return L; 00078 } 00079 00080 // Return leftmost child of subtree 00081 function UWindowList LeftMost() 00082 { 00083 local UWindowList L; 00084 00085 assert(Sentinel.bTreeSort); 00086 00087 if(BranchLeft == None) 00088 return None; 00089 00090 L = Self; 00091 while(L.BranchLeft != None) 00092 L = L.BranchLeft; 00093 00094 return L; 00095 } 00096 00097 function Remove() 00098 { 00099 local UWindowList T; 00100 00101 if(Next != None) 00102 Next.Prev = Prev; 00103 00104 if(Prev != None) 00105 Prev.Next = Next; 00106 00107 if(Sentinel != None) 00108 { 00109 if(Sentinel.bTreeSort && ParentNode!=None) 00110 { 00111 if(BranchLeft != None) 00112 { 00113 if(ParentNode.BranchLeft == Self) 00114 ParentNode.GraftLeft(BranchLeft); 00115 if(ParentNode.BranchRight == Self) 00116 ParentNode.GraftRight(BranchLeft); 00117 00118 // If we had a right branch we better move it 00119 // into the far right of the left branch. 00120 00121 T = BranchLeft.Rightmost(); 00122 if(T != None) 00123 T.GraftRight(BranchRight); 00124 } 00125 else 00126 { 00127 if(ParentNode.BranchLeft == Self) 00128 ParentNode.GraftLeft(BranchRight); 00129 if(ParentNode.BranchRight == Self) 00130 ParentNode.GraftRight(BranchRight); 00131 00132 // no left branch to worry about. 00133 } 00134 00135 ParentNode = None; 00136 BranchLeft = None; 00137 BranchRight = None; 00138 } 00139 00140 Sentinel.InternalCount--; 00141 Sentinel.bItemOrderChanged = True; 00142 00143 if(Sentinel.Last == Self) 00144 Sentinel.Last = Prev; 00145 00146 Prev=None; 00147 Next=None; 00148 00149 /* Sentinel.Validate(); */ 00150 Sentinel = None; 00151 } 00152 } 00153 00154 function int Compare(UWindowList T, UWindowList B) 00155 { 00156 // declare actual sort method in subclass 00157 return 0; 00158 } 00159 00160 // Inserts a new element before us. DO NOT CALL on the sentinel. 00161 function UWindowList InsertBefore(Class<UWindowList> C) 00162 { 00163 local UWindowList NewElement; 00164 00165 NewElement = CreateItem(C); 00166 InsertItemBefore(NewElement); 00167 00168 return NewElement; 00169 } 00170 00171 function UWindowList InsertAfter(Class<UWindowList> C) 00172 { 00173 local UWindowList NewElement; 00174 00175 NewElement = CreateItem(C); 00176 InsertItemAfter(NewElement); 00177 00178 return NewElement; 00179 } 00180 00181 00182 // Inserts an element before us. DO NOT CALL on the sentinel. 00183 function InsertItemBefore(UWindowList NewElement) 00184 { 00185 assert(Sentinel != Self); 00186 00187 NewElement.BranchLeft = None; 00188 NewElement.BranchRight = None; 00189 NewElement.ParentNode = None; 00190 NewElement.Sentinel = Sentinel; 00191 NewElement.BranchLeft = None; 00192 NewElement.BranchRight = None; 00193 NewElement.ParentNode = None; 00194 NewElement.Prev = Prev; 00195 Prev.Next = NewElement; 00196 Prev = NewElement; 00197 NewElement.Next = Self; 00198 00199 if(Sentinel.Next == Self) 00200 Sentinel.Next = NewElement; 00201 00202 Sentinel.InternalCount++; 00203 Sentinel.bItemOrderChanged = True; 00204 } 00205 00206 function InsertItemAfter(UWindowList NewElement, optional bool bCheckShowItem) 00207 { 00208 local UWindowList N; 00209 00210 N = Next; 00211 if(bCheckShowItem) 00212 while(N != None && !N.ShowThisItem()) 00213 N = N.Next; 00214 00215 if(N != None) 00216 N.InsertItemBefore(NewElement); 00217 else 00218 Sentinel.DoAppendItem(NewElement); 00219 Sentinel.bItemOrderChanged = True; 00220 } 00221 00222 function ContinueSort() 00223 { 00224 local UWindowList N; 00225 00226 CompareCount = 0; 00227 bSortSuspended = False; 00228 00229 while(CurrentSortItem != None) 00230 { 00231 N = CurrentSortItem.Next; 00232 AppendItem(CurrentSortItem); 00233 CurrentSortItem = N; 00234 00235 // split sort over multiple frames, if it's BIG 00236 if(CompareCount >= 10000 && bSuspendableSort) 00237 { 00238 bSortSuspended = True; 00239 return; 00240 } 00241 } 00242 } 00243 00244 function Tick(float Delta) 00245 { 00246 if(bSortSuspended) 00247 ContinueSort(); 00248 } 00249 00250 function UWindowList Sort() 00251 { 00252 local UWindowList S; 00253 local UWindowList CurrentItem; 00254 local UWindowList Previous; 00255 local UWindowList Best; 00256 local UWindowList BestPrev; 00257 00258 if(bTreeSort) 00259 { 00260 if(bSortSuspended) 00261 { 00262 ContinueSort(); 00263 return Self; 00264 } 00265 00266 CurrentSortItem = Next; 00267 DisconnectList(); 00268 ContinueSort(); 00269 return Self; 00270 } 00271 00272 CurrentItem = Self; 00273 00274 while(CurrentItem != None) 00275 { 00276 S = CurrentItem.Next; Best = CurrentItem.Next; 00277 Previous = CurrentItem; BestPrev = CurrentItem; 00278 00279 // Find the best server 00280 while(S != None) 00281 { 00282 if(CurrentItem.Compare(S, Best) <= 0) 00283 { 00284 Best = S; 00285 BestPrev = Previous; 00286 } 00287 00288 Previous = S; 00289 S = S.Next; 00290 } 00291 00292 // If we're not already in the right order, move the best one next. 00293 if(Best != CurrentItem.Next) 00294 { 00295 // Delete Best's old position 00296 BestPrev.Next = Best.Next; 00297 if(BestPrev.Next != None) 00298 BestPrev.Next.Prev = BestPrev; 00299 00300 // Fix Self and Best 00301 Best.Prev = CurrentItem; 00302 Best.Next = CurrentItem.Next; 00303 CurrentItem.Next.Prev = Best; 00304 CurrentItem.Next = Best; 00305 00306 // Fix up Sentinel if Best was also Last 00307 if(Sentinel.Last == Best) 00308 { 00309 Sentinel.Last = BestPrev; 00310 if(Sentinel.Last == None) 00311 Sentinel.Last = Sentinel; 00312 } 00313 } 00314 00315 CurrentItem = CurrentItem.Next; 00316 } 00317 00318 //Validate(); 00319 return Self; 00320 } 00321 00322 function DisconnectList() 00323 { 00324 Next=None; 00325 Last=Self; 00326 Prev=None; 00327 BranchLeft = None; 00328 BranchRight = None; 00329 ParentNode = None; 00330 InternalCount = 0; 00331 Sentinel.bItemOrderChanged = True; 00332 } 00333 00334 function DestroyList() 00335 { 00336 local UWindowList L, Temp; 00337 L = Next; 00338 00339 InternalCount = 0; 00340 if(Sentinel != None) 00341 Sentinel.bItemOrderChanged = True; 00342 00343 while(L != None) 00344 { 00345 Temp = L.Next; 00346 L.DestroyListItem(); 00347 L = Temp; 00348 } 00349 DestroyListItem(); 00350 } 00351 00352 function DestroyListItem() 00353 { 00354 Next=None; 00355 Last=Self; 00356 Sentinel=None; 00357 Prev=None; 00358 BranchLeft=None; 00359 BranchRight=None; 00360 ParentNode=None; 00361 } 00362 00363 function int CountShown() 00364 { 00365 local int C; 00366 local UWindowList I; 00367 00368 for(I = Next;I != None; I = I.Next) 00369 if(I.ShowThisItem()) 00370 C++; 00371 00372 return C; 00373 } 00374 00375 function UWindowList CopyExistingListItem(Class<UWindowList> ItemClass, UWindowList SourceItem) 00376 { 00377 local UWindowList I; 00378 00379 I = Append(ItemClass); 00380 Sentinel.bItemOrderChanged = True; 00381 00382 return I; 00383 } 00384 00385 // for Listboxes only (so far) 00386 function bool ShowThisItem() 00387 { 00388 return True; 00389 } 00390 00391 /********** These things can only be called on the sentinel **********/ 00392 function int Count() 00393 { 00394 return InternalCount; 00395 } 00396 00397 function MoveItemSorted(UWindowList Item) 00398 { 00399 local UWindowList L; 00400 00401 if(bTreeSort) 00402 { 00403 Item.Remove(); 00404 AppendItem(Item); 00405 } 00406 else 00407 { 00408 for(L=Next;L != None; L = L.Next) 00409 if(Compare(Item, L) <= 0) break; 00410 00411 if(L != Item) 00412 { 00413 Item.Remove(); 00414 if(L == None) 00415 AppendItem(Item); 00416 else 00417 L.InsertItemBefore(Item); 00418 } 00419 } 00420 } 00421 00422 function SetupSentinel(optional bool bInTreeSort) 00423 { 00424 Last = Self; 00425 Next = None; 00426 Prev = None; 00427 BranchLeft = None; 00428 BranchRight = None; 00429 ParentNode = None; 00430 Sentinel = Self; 00431 InternalCount = 0; 00432 bItemOrderChanged = True; 00433 bTreeSort = bInTreeSort; 00434 } 00435 00436 function Validate() 00437 { 00438 local UWindowList I, Previous; 00439 local int Count; 00440 00441 if(Sentinel != Self) 00442 { 00443 Log("Calling Sentinel.Validate() from "$Self); 00444 Sentinel.Validate(); 00445 return; 00446 } 00447 00448 Log("BEGIN Validate(): "$Class); 00449 00450 Count = 0; 00451 Previous = Self; 00452 00453 for(I = Next; I != None; I = I.Next) 00454 { 00455 Log("Checking item: "$Count); 00456 00457 if(I.Sentinel != Self) 00458 Log(" I.Sentinel reference is broken"); 00459 00460 if(I.Prev != Previous) 00461 Log(" I.Prev reference is broken"); 00462 00463 if(Last == I && I.Next != None) 00464 Log(" Item is Sentinel.Last but Item has valid Next"); 00465 00466 if(I.Next == None && Last != I) 00467 Log(" Item is Item.Next is none, but Item is not Sentinel.Last"); 00468 00469 Previous = I; 00470 Count++; 00471 } 00472 00473 Log("END Validate(): "$Class); 00474 } 00475 00476 // For sentinel only 00477 function UWindowList Append(Class<UWindowList> C) 00478 { 00479 local UWindowList NewElement; 00480 00481 NewElement = CreateItem(C); 00482 AppendItem(NewElement); 00483 00484 return NewElement; 00485 } 00486 00487 function AppendItem(UWindowList NewElement) 00488 { 00489 local UWindowList Node, OldNode, Temp; 00490 local int Test; 00491 00492 if(bTreeSort) 00493 { 00494 // Check for worst cases! 00495 if(Next != None && Last != Self) 00496 { 00497 if(Compare(NewElement, Last) >= 0) 00498 { 00499 // put at end of list 00500 Node = Last; 00501 Node.InsertItemAfter(NewElement, False); 00502 Node.GraftRight(NewElement); 00503 return; 00504 } 00505 00506 if(Compare(NewElement, Next) <= 0) 00507 { 00508 // put at front of list 00509 Node = Next; 00510 Node.InsertItemBefore(NewElement); 00511 Node.GraftLeft(NewElement); 00512 return; 00513 } 00514 } 00515 00516 Node = Self; 00517 while(True) 00518 { 00519 if(Node == Self) 00520 Test = 1; 00521 else 00522 Test = Compare(NewElement, Node); 00523 00524 // special case for equality 00525 if(Test == 0) 00526 { 00527 Node.InsertItemAfter(NewElement, False); 00528 return; 00529 } 00530 else 00531 if(Test > 0) 00532 { 00533 // Traverse right 00534 OldNode = Node; 00535 Node = Node.BranchRight; 00536 if(Node == None) 00537 { 00538 // Move past equal values 00539 Temp = OldNode; 00540 while(Temp.Next != None && Temp.Next.ParentNode == None) 00541 Temp = Temp.Next; 00542 00543 Temp.InsertItemAfter(NewElement, False); 00544 OldNode.GraftRight(NewElement); 00545 return; 00546 } 00547 } 00548 else 00549 { 00550 // Traverse left 00551 OldNode = Node; 00552 Node = Node.BranchLeft; 00553 if(Node == None) 00554 { 00555 OldNode.InsertItemBefore(NewElement); 00556 OldNode.GraftLeft(NewElement); 00557 return; 00558 } 00559 } 00560 } 00561 } 00562 else 00563 DoAppendItem(NewElement); 00564 } 00565 00566 function DoAppendItem(UWindowList NewElement) 00567 { 00568 NewElement.Next = None; 00569 Last.Next = NewElement; 00570 NewElement.Prev = Last; 00571 NewElement.Sentinel = Self; 00572 NewElement.BranchLeft = None; 00573 NewElement.BranchRight = None; 00574 NewElement.ParentNode = None; 00575 Last = NewElement; 00576 Sentinel.InternalCount++; 00577 Sentinel.bItemOrderChanged = True; 00578 } 00579 00580 00581 // For sentinel only 00582 function UWindowList Insert(Class<UWindowList> C) 00583 { 00584 local UWindowList NewElement; 00585 00586 NewElement = CreateItem(C); 00587 InsertItem(NewElement); 00588 00589 return NewElement; 00590 } 00591 00592 function InsertItem(UWindowList NewElement) 00593 { 00594 NewElement.Next = Next; 00595 if(Next != None) 00596 Next.Prev = NewElement; 00597 Next = NewElement; 00598 if(Last == Self) 00599 Last = Next; 00600 NewElement.Prev = Self; 00601 NewElement.Sentinel = Self; 00602 NewElement.BranchLeft = None; 00603 NewElement.BranchRight = None; 00604 NewElement.ParentNode = None; 00605 Sentinel.InternalCount++; 00606 Sentinel.bItemOrderChanged = True; 00607 } 00608 00609 // For sentinel only 00610 function UWindowList FindEntry(int Index) 00611 { 00612 local UWindowList l; 00613 local int i; 00614 00615 l = Next; 00616 for(i=0;i<Index;i++) 00617 { 00618 l = l.Next; 00619 if(l==None) return None; 00620 } 00621 return l; 00622 } 00623 00624 function AppendListCopy(UWindowList L) 00625 { 00626 if(L == None) 00627 return; 00628 00629 for(L = L.Next;L != None; L = L.Next) 00630 CopyExistingListItem(L.Class, L); 00631 } 00632 00633 function Clear() 00634 { 00635 InternalCount = 0; 00636 ParentNode = None; 00637 BranchLeft = None; 00638 BranchRight = None; 00639 bItemOrderChanged = True; 00640 Next = None; 00641 Last = Self; 00642 } 00643 00644 defaultproperties 00645 { 00646 }