1// tList.h 
2// 
3// Linked list implementations. There are two implementations in this module. tList is intrusive, tItList (i for 
4// iterator) is non-intrusive. Use the intrusive one for performance and fewer fragmentation issues if possible. 
5// 
6// tList advantages: Faster and less memory fragmentation (one new per object). 
7// tList disadvantages: An object can only be on one list at a time. You must derive from tLink. 
8// 
9// tItList advantages: The same item only in one list at a time. No change in memory image for the objects. Cleaner 
10// iterator syntax similar to the STL containers. Supports the new C++11 range-based for loop syntax. 
11// tItList disadvantages: More memory allocs. Not quite as fast. 
12// 
13// Copyright (c) 2004-2006, 2015, 2017, 2020 Tristan Grimmer. 
14// Permission to use, copy, modify, and/or distribute this software for any purpose with or without fee is hereby 
15// granted, provided that the above copyright notice and this permission notice appear in all copies. 
16// 
17// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL 
18// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, 
19// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN 
20// AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 
21// PERFORMANCE OF THIS SOFTWARE. 
22 
23#pragma once 
24#include "Foundation/tAssert.h" 
25#include "Foundation/tPlatform.h" 
26 
27 
28enum class tListSortAlgorithm 
29{ 
30 Merge, // Guaranteed O(n ln(n)) even in worst case. 
31 Bubble // As bad as O(n^2) on unsorted data. Only O(n) on sorted. 
32}; 
33 
34 
35// You need to derive your object from this if you want to put them on a tList. 
36template<typename T> class tLink 
37{ 
38public: 
39 tLink() : NextItem(nullptr), PrevItem(nullptr) { } 
40 tLink(const tLink&) : NextItem(nullptr), PrevItem(nullptr) { } 
41 T* Next() const { return NextItem; } 
42 T* Prev() const { return PrevItem; } 
43 
44private: 
45 template<typename U> friend class tList; 
46 T* NextItem; 
47 T* PrevItem; 
48}; 
49 
50 
51enum class tListMode 
52{ 
53 StaticZero, Static = StaticZero, // Default. Must be 0. 
54 External, UserOwns = External, 
55 Internal, ListOwns = Internal 
56}; 
57 
58 
59// A tList is an intrusive list implementation. Less mem fragmentation but objects can only be on one list at a time. 
60// A tList may be used in the cdata (global) memory section where zero-initialization is guaranteed. In this mode it 
61// does NOT delete its items on destruction to avoid both the init and de-init fiasco. tLists may also be used on the 
62// stack or heap, in which case it is optional construct with the ListOwns flag. It is vital that for zero-init you 
63// call the constructor with mode as StaticZero IF you intend to have it populated by other statically initialized 
64// objects before main() is entered. This is because we don't know what items will have already been put on the list 
65// before the constructor is called (the C++ init fiasco). The constructor in StaticZero mode does NOT clear the state 
66// variables so it doesn't matter when. 
67// 
68// Note: In static mode, the list does not consider itself to own the things on the list. It is safe to add 'this' 
69// pointers to globally constructed objects for instance. If however you do want the list to delete the items, tList 
70// will allow you to call Empty on a static-zero list. You can also call Reset (no deletes). Clear will be the same 
71// as Reset for static-zero lists. 
72template<typename T> class tList 
73{ 
74public: 
75 // The default constructor has the list owning the items. 
76 tList() : Mode(tListMode::ListOwns), HeadItem(nullptr), TailItem(nullptr), ItemCount(0) { } 
77 
78 // If mode is external the objects will not be deleted when the list is destroyed. You manage item lifetime. 
79 tList(tListMode mode) : Mode(mode) { if (mode != tListMode::StaticZero) { HeadItem = nullptr; TailItem = nullptr; ItemCount = 0; } } 
80  
81 virtual ~tList() { if (Owns()) Empty(); } 
82  
83 T* Insert(T* item); // Insert item at head. Returns item. 
84 T* Insert(T* item, T* here); // Insert item before here. Returns item. 
85 T* Append(T* item); // Append item at tail. Returns item. 
86 T* Append(T* item, T* here); // Append item after here. Returns item. 
87 T* Remove(T* item); // Removes and returns item. 
88 T* Remove(); // Removes and returns head item. 
89 T* Drop(); // Removes and returns tail item. 
90 
91 void Clear() /* Clears the list. Deletes items if list owns them. */ { if (Owns()) Empty(); else Reset(); } 
92 void Reset() /* Resets the list. Never deletes the objects. */ { HeadItem = nullptr; TailItem = nullptr; ItemCount = 0; } 
93 void Empty() /* Empties the list. Always deletes the objects. */ { tAssert(Owns() || (Mode == tListMode::StaticZero)); while (!IsEmpty()) delete Remove(); } 
94 
95 T* Head() const { return HeadItem; } 
96 T* Tail() const { return TailItem; } 
97 T* First() const { return HeadItem; } 
98 T* Last() const { return TailItem; } 
99 
100 T* NextCirc(const T* here) const /* Circular. Gets item after here. */ { return here->NextItem ? here->NextItem : HeadItem; } 
101 T* PrevCirc(const T* here) const /* Circular. Gets item before here. */ { return here->PrevItem ? here->PrevItem : TailItem; } 
102 
103 int GetNumItems() const { return ItemCount; } 
104 int NumItems() const { return ItemCount; } 
105 int Count() const { return ItemCount; } 
106 bool Owns() const { return (Mode == tListMode::Internal); } 
107 bool IsEmpty() const { return !HeadItem; } 
108 bool Contains(const T& item) const /* To use this there must be an operator== for type T. */ { for (const T* n = First(); n; n = n->Next()) if (*n == item) return true; return false; } 
109 
110 // Sorts the list using the algorithm specified. The supplied compare function should never return true on equal. 
111 // To sort ascending return the truth of a < b. Return a > b to sort in descending order. Returns the number of 
112 // compares performed. The compare function usually implements bool CompareFunc(const T& a, const T& b) 
113 template<typename CompareFunc> int Sort(CompareFunc, tListSortAlgorithm alg = tListSortAlgorithm::Merge); 
114 
115 // Inserts item in a sorted list. It will remain sorted. 
116 template<typename CompareFunc> T* Insert(T* item, CompareFunc); 
117 
118 // This does an O(n) single pass of a bubble sort iteration. Allows the cost of sorting to be distributed over time 
119 // for objects that do not change their order very often. Do the expensive merge sort when the list is initially 
120 // populated, then use this to keep it approximately correct. 
121 // 
122 // The direction is important when doing this type of partial sort. A forward bubble will result in the last object 
123 // in the list being correct after one pass, last two for two passes etc. If getting the front of the list correct 
124 // sooner is more important you'll want to bubble backwards. This is true regardless of whether the compare 
125 // function implements an ascending or descending sort. 
126 // 
127 // maxCompares sets how far into the list to perform possible swaps. If maxCompares == -1 it means go all the way. 
128 // That is, GetNumItems() - 1. Returns number of swaps performed. 
129 template<typename CompareFunc> int Bubble(CompareFunc compare, bool backwards = false, int maxCompares = -1) { if (backwards) return BubbleBackward(compare, maxCompares); else return BubbleForward(compare, maxCompares); } 
130 
131private: 
132 // These return the number of swaps performed. If 0 is returned, the items considered were already in the correct 
133 // order. The maxCompares allows you to limit how many compares are performed. -1 means numItems-1 compares will be 
134 // made (a full sweep). The variable gets clamped to [0, numItems) otherwise. 
135 template<typename CompareFunc> int BubbleForward(CompareFunc, int maxCompares = -1); 
136 template<typename CompareFunc> int BubbleBackward(CompareFunc, int maxCompares = -1); 
137 
138 // These return the number of compares performed. 
139 template<typename CompareFunc> int SortMerge(CompareFunc); 
140 template<typename CompareFunc> int SortBubble(CompareFunc); 
141 
142 // Since tList supports static zero-initialization, all defaults for all member vars should be 0. 
143 tListMode Mode; 
144 T* HeadItem; 
145 T* TailItem; 
146 int ItemCount; 
147}; 
148 
149 
150// The tItList implements a doubly linked non-intrusive iterator-based list. This list class is implemented by using a 
151// tList of structs that point to the objects in the list. 
152template<typename T> class tItList 
153{ 
154public: 
155 tItList() : Mode(tListMode::ListOwns), Nodes(tListMode::ListOwns) { } 
156 tItList(tListMode mode) : Mode(mode), Nodes(tListMode::ListOwns) { } 
157 virtual ~tItList() { if (Owns()) Empty(); else Clear(); } 
158 
159private: 
160 // This internal datatype is declared early on to make inlining a bit easier. 
161 struct IterNode : public tLink<IterNode> 
162 { 
163 IterNode(const T* obj) : tLink<IterNode>(), Object(obj) { } 
164 const T* Get() const { return Object; } 
165 const T* Object; 
166 }; 
167 
168public: 
169 // The tItList iterator class for external use. 
170 class Iter 
171 { 
172 public: 
173 Iter() : Node(nullptr), List(nullptr) { } 
174 Iter(const Iter& src) : Node(src.Node), List(src.List) { } 
175 
176 // Iterators may be dereferenced to get to the object. 
177 T& operator*() const { return *((T*)Node->Object); } 
178 T* operator->() const { return (T*)Node->Object; } 
179 operator bool() const { return Node ? true : false; } 
180 
181 // Iterators may be treated as pointers to the object. 
182 operator T*() { return GetObject(); } 
183 operator const T*() const { return GetObject(); } 
184 Iter& operator=(const Iter& i) { if (this != &i) { Node = i.Node; List = i.List; } return *this; } 
185 
186 // Use ++iter instead of iter++ when possible. 
187 const Iter operator++(int) { Iter curr(*this); Next(); return curr; } 
188 const Iter operator--(int) { Iter curr(*this); Prev(); return curr; } 
189 const Iter operator++() { Next(); return *this; } 
190 const Iter operator--() { Prev(); return *this; } 
191 const Iter operator+(int offset) const { tAssert(offset >= 0); Iter i = *this; while (offset--) i.Next(); return i; } 
192 const Iter operator-(int offset) const { tAssert(offset >= 0); Iter i = *this; while (offset--) i.Prev(); return i; } 
193 Iter& operator+=(int offset) { tAssert(offset >= 0); while (offset--) Next(); return *this; } 
194 Iter& operator-=(int offset) { tAssert(offset >= 0); while (offset--) Prev(); return *this; } 
195 bool operator==(const Iter& i) const { return (Node == i.Node) && (List == i.List); } 
196 bool operator!=(const Iter& i) const { return (Node != i.Node) || (List != i.List); } 
197 
198 bool IsValid() const { return Node ? true : false; } 
199 void Clear() { Node = nullptr; List = nullptr; } 
200 void Next() { if (Node) Node = Node->Next(); } 
201 void Prev() { if (Node) Node = Node->Prev(); } 
202 
203 // Accessors that allow the list to be treated as circular. 
204 void NextCirc() { if (Node) Node = Node->Next(); if (!Node) Node = List->Nodes.Head(); } 
205 void PrevCirc() { if (Node) Node = Node->Prev(); if (!Node) Node = List->Nodes.Tail(); } 
206 T* GetObject() const { return (T*)(Node ? Node->Object : nullptr); } 
207 
208 private: 
209 friend class tItList<T>; 
210 Iter(IterNode* listNode, const tItList<T>* list) : Node(listNode), List(list) { } 
211 IterNode* Node; 
212 const tItList<T>* List; 
213 }; 
214 
215 // Insert before head and append after tail. 
216 T* Insert(const T* obj) { tAssert(obj); Nodes.Insert(new IterNode(obj)); return obj; } 
217 T* Insert(const T* obj, const Iter& here) { tAssert(obj); tAssert(this == here.List); Nodes.Insert(new IterNode(obj), here.Node); return obj; } 
218 T* Append(T* obj) { tAssert(obj); Nodes.Append(new IterNode(obj)); return obj; } 
219 T* Append(const T* obj, const Iter& here) { tAssert(obj); tAssert(this == here.List); Nodes.Append(new IterNode(obj), here.Node); return obj; } 
220 
221 T* Remove() /* Removes and returns head. */ { Iter head = Head(); return Remove(head); } 
222 T* Remove(Iter&); // Removed object referred to by Iter. Invalidates Iter. 
223 T* Drop() /* Drops and returns tail. */ { Iter tail = Tail(); return Drop(tail); } 
224 T* Drop(Iter& iter) /* Same a Remove. */ { return Remove(iter); } 
225 
226 void Clear() /* Clears the list. Deletes items if ownership flag set. */ { if (Owns()) Empty(); else Reset(); } 
227 void Reset() /* Resets the list. Never deletes the objects. */ { while (!IsEmpty()) Remove(); } 
228 void Empty() /* Empties the list. Always deletes the objects. */ { while (!IsEmpty()) delete Remove(); } 
229 
230 Iter Head() const { return Iter(Nodes.Head(), this); } 
231 Iter Tail() const { return Iter(Nodes.Tail(), this); } 
232 Iter First() const { return Iter(Nodes.Head(), this); } 
233 Iter Last() const { return Iter(Nodes.Tail(), this); } 
234 
235 // Searches list forward for a particular item. Returns its iterator or an invalid one if it wasn't found. 
236 Iter Find(const T* item) const { for (IterNode* n = Nodes.First(); n; n = n->Next()) if (n->Object == item) return Iter(n, this); return Iter(); } 
237 
238 int GetNumItems() const { return Nodes.GetNumItems(); } 
239 int NumItems() const { return Nodes.NumItems(); } 
240 int Count() const { return Nodes.Count(); } 
241 bool IsEmpty() const { return Nodes.IsEmpty(); } 
242 bool Owns() const { return (Mode == tListMode::ListOwns); } 
243 
244 // For range-based iteration supported in C++11. It worth noting that ++Iter must return a value that matches 
245 // whatever end() returns here. That is != must return false when comparing the final ++Iter next call with 
246 // what is returned by end(). That is why we return an Iter with a null Node but a _valid_ List pointer. 
247 Iter begin() const { return Head(); } 
248 Iter end() const { return Iter(nullptr, this); } 
249 
250 const T& operator[](const Iter& iter) const { tAssert(iter.IsValid() && (iter.List == this)); return *iter.Node->Object; } 
251 T& operator[](const Iter& iter) { tAssert(iter.IsValid() && (iter.List == this)); return *((T*)iter.Node->Object); } 
252 
253 // Sorts the list using the algorithm specified. The supplied compare function should never return true on equal. 
254 // To sort ascending return the truth of a < b. Return a > b to sort in descending order. Returns the number of 
255 // compares performed. The compare function should implement bool CompareFunc(const T& a, const T& b) 
256 template<typename CompareFunc> int Sort(CompareFunc compare, tListSortAlgorithm algo = tListSortAlgorithm::Merge) { auto cmp = [&compare](const IterNode& a, const IterNode& b) { return compare(*a.Get(), *b.Get()); }; return Nodes.Sort(cmp, algo); } 
257 
258 // Inserts item in a sorted list. It will remain sorted. 
259 template<typename CompareFunc> T* Insert(const T* item, CompareFunc compare) { auto cmp = [&compare](IterNode& a, IterNode& b) { return compare(*a.Get(), *b.Get()); }; return Nodes.Insert(item, cmp); } 
260 
261 // This does an O(n) single pass of a bubble sort iteration. Allows the cost of sorting to be distributed over time 
262 // for objects that do not change their order very often. Do the expensive merge sort when the list is initially 
263 // populated, then use this to keep it approximately correct. 
264 // 
265 // The direction is important when doing this type of partial sort. A forward bubble will result in the last object 
266 // in the list being correct after one pass, last two for two passes etc. If getting the front of the list correct 
267 // sooner is more important you'll want to bubble backwards. This is true regardless of whether the compare 
268 // function implements an ascending or descending sort. 
269 // 
270 // maxCompares sets how far into the list to perform possible swaps. If maxCompares == -1 it means go all the way. 
271 // That is, GetNumItems() - 1. Returns number of swaps performed. 
272 // 
273 // Note that any iterators that you are maintaining should remain valid. 
274 template<typename CompareFunc> int Bubble(CompareFunc compare, bool backwards = false, int maxCompares = -1) { return Nodes.Bubble(compare, backwards, maxCompares); } 
275 
276private: 
277 // tItList is implemented using a tList of Nodes that point to the objects. 
278 tListMode Mode; 
279 tList<IterNode> Nodes; 
280}; 
281 
282 
283// Implementation below this line. 
284 
285 
286template<typename T> inline T* tList<T>::Insert(T* item) 
287{ 
288 if (HeadItem) 
289 HeadItem->PrevItem = item; 
290 
291 item->NextItem = HeadItem; 
292 item->PrevItem = nullptr; 
293 HeadItem = item; 
294 if (!TailItem) 
295 TailItem = item; 
296 
297 ItemCount++; 
298 return item; 
299} 
300 
301 
302template<typename T> inline T* tList<T>::Append(T* item) 
303{ 
304 if (TailItem) 
305 TailItem->NextItem = item; 
306 
307 item->PrevItem = TailItem; 
308 item->NextItem = nullptr; 
309 TailItem = item; 
310 if (!HeadItem) 
311 HeadItem = (T*)item; 
312 
313 ItemCount++; 
314 return item; 
315} 
316 
317 
318template<typename T> template<typename CompareFunc> inline T* tList<T>::Insert(T* item, CompareFunc compare) 
319{ 
320 // Find the first item (starting from the smallest/head) that our item is less than. 
321 for (T* contender = Head(); contender; contender = contender->Next()) 
322 if (compare(*item, *contender)) 
323 return Insert(item, contender); 
324  
325 return Append(item);  
326} 
327 
328 
329template<typename T> inline T* tList<T>::Insert(T* item, T* where) 
330{ 
331 tAssert(item); 
332 if (!where) 
333 return Insert(item); 
334 
335 item->NextItem = where; 
336 item->PrevItem = where->PrevItem; 
337 where->PrevItem = item; 
338 
339 if (item->PrevItem) 
340 item->PrevItem->NextItem = item; 
341 else 
342 HeadItem = item; 
343 
344 ItemCount++; 
345 return item; 
346} 
347 
348 
349template<typename T> inline T* tList<T>::Append(T* item, T* where) 
350{ 
351 tAssert(item); 
352 if (!where) 
353 return Append(item); 
354 
355 item->PrevItem = where; 
356 item->NextItem = where->NextItem; 
357 where->NextItem = item; 
358 
359 if (item->NextItem) 
360 item->NextItem->PrevItem = item; 
361 else 
362 TailItem = item; 
363 
364 ItemCount++; 
365 return (T*)item; 
366} 
367 
368 
369template<typename T> inline T* tList<T>::Remove() 
370{ 
371 // It's OK to try to remove from an empty list. 
372 if (!HeadItem) 
373 return nullptr; 
374 
375 T* removed = HeadItem; 
376 HeadItem = (T*)HeadItem->NextItem; 
377 if (!HeadItem) 
378 TailItem = nullptr; 
379 else 
380 HeadItem->PrevItem = nullptr; 
381 
382 ItemCount--; 
383 return removed; 
384} 
385 
386 
387template<typename T> inline T* tList<T>::Drop() 
388{ 
389 // It's OK to try to lose something from an empty list. 
390 if (!TailItem) 
391 return nullptr; 
392 
393 T* dropped = TailItem; 
394 TailItem = (T*)TailItem->PrevItem; 
395 if (!TailItem) 
396 HeadItem = nullptr; 
397 else 
398 TailItem->NextItem = nullptr; 
399 
400 ItemCount--; 
401 return dropped; 
402} 
403 
404 
405template<typename T> inline T* tList<T>::Remove(T* item) 
406{ 
407 if (item->PrevItem) 
408 item->PrevItem->NextItem = item->NextItem; 
409 else 
410 HeadItem = item->NextItem; 
411 
412 if (item->NextItem) 
413 item->NextItem->PrevItem = item->PrevItem; 
414 else 
415 TailItem = item->PrevItem; 
416 
417 ItemCount--; 
418 return item; 
419} 
420 
421 
422template<typename T> template<typename CompareFunc> inline int tList<T>::Sort(CompareFunc compare, tListSortAlgorithm algorithm) 
423{ 
424 switch (algorithm) 
425 { 
426 case tListSortAlgorithm::Bubble: 
427 return SortBubble(compare); 
428 break; 
429 
430 case tListSortAlgorithm::Merge: 
431 default: 
432 return SortMerge(compare); 
433 break; 
434 } 
435 
436 return 0; 
437} 
438 
439 
440template<typename T> template<typename CompareFunc> inline int tList<T>::SortMerge(CompareFunc compare) 
441{ 
442 if (!HeadItem) 
443 return 0; 
444 
445 // Treat every node as a separate list, completely sorted, starting with 1 element each. 
446 int numNodesPerList = 1; 
447 int numCompares = 0; 
448 
449 while (1) 
450 { 
451 T* p = HeadItem; 
452 HeadItem = nullptr; 
453 TailItem = nullptr; 
454 
455 // Num merges in this loop. 
456 int numMerges = 0;  
457 
458 while (p) 
459 { 
460 numMerges++; 
461 T* q = p; 
462 int numPNodes = 0; 
463 for (int i = 0; i < numNodesPerList; i++) 
464 { 
465 numPNodes++; 
466 q = q->Next(); 
467 if (!q) 
468 break; 
469 } 
470 
471 int numQNodes = numNodesPerList; 
472 
473 // Merge the two lists. 
474 while (numPNodes > 0 || (numQNodes > 0 && q)) 
475 { 
476 // Decide whether next tBaseLink of merge comes from p or q. 
477 T* e; 
478 
479 if (numPNodes == 0) 
480 { 
481 // p is empty; e must come from q. 
482 e = q; 
483 q = q->Next(); 
484 
485 numQNodes--; 
486 } 
487 else if (numQNodes == 0 || !q) 
488 { 
489 // q is empty; e must come from p. 
490 e = p; 
491 p = p->Next(); 
492 
493 numPNodes--; 
494 } 
495 else if (++numCompares && !compare(*q, *p)) 
496 { 
497 // p is lower so e must come from p. 
498 e = p; 
499 p = p->Next(); 
500  
501 numPNodes--; 
502 } 
503 else 
504 { 
505 // First gBaseNode of q is bigger or equal; e must come from q. 
506 e = q; 
507 q = q->Next(); 
508  
509 numQNodes--; 
510 } 
511 
512 // add the next gBaseNode to the merged list. 
513 if (TailItem) 
514 TailItem->NextItem = e; 
515 else 
516 HeadItem = e; 
517 
518 e->PrevItem = TailItem; 
519 TailItem = e; 
520 } 
521 
522 // P and Q have moved numNodesPerList places along. 
523 p = q; 
524 } 
525 TailItem->NextItem = nullptr; 
526 
527 // If we have done only one merge, we're all sorted. 
528 if (numMerges <= 1) 
529 return numCompares; 
530 
531 // Otherwise repeat, merging lists twice the size. 
532 numNodesPerList *= 2; 
533 } 
534 
535 return numCompares; 
536} 
537 
538 
539template<typename T> template<typename CompareFunc> inline int tList<T>::SortBubble(CompareFunc compare) 
540{ 
541 // Performs a full bubble sort. 
542 int numCompares = 0; 
543 for (int maxCompares = ItemCount - 1; maxCompares >= 1; maxCompares--) 
544 { 
545 int numSwaps = BubbleForward(compare, maxCompares); 
546 numCompares += maxCompares; 
547 
548 // Early exit detection. If any bubble pass resulted in no swaps, we're done! 
549 if (!numSwaps) 
550 return numCompares; 
551 } 
552 
553 return numCompares; 
554} 
555 
556 
557template<typename T> template<typename CompareFunc> inline int tList<T>::BubbleForward(CompareFunc compare, int maxCompares) 
558{ 
559 // @todo Can -1 ever happen? 
560 if (maxCompares == -1) 
561 maxCompares = ItemCount-1; 
562 else if (maxCompares > ItemCount-1) 
563 maxCompares = ItemCount-1; 
564 
565 // If there are no items, only a single item, or no compares are requested, we're done. 
566 if ((ItemCount < 2) || (maxCompares == 0)) 
567 return 0; 
568 
569 T* a = HeadItem; 
570 int numSwaps = 0; 
571 int numCompares = 0; 
572 
573 while ((a != TailItem) && (numCompares < maxCompares)) 
574 { 
575 T* b = a->NextItem; 
576 
577 // We're sorting from lowest to biggest, so if b < a we need to swap them. 
578 if (compare(*b, *a)) 
579 { 
580 // Swap. 
581 if (a->PrevItem) 
582 a->PrevItem->NextItem = b; 
583 
584 if (b->NextItem) 
585 b->NextItem->PrevItem = a; 
586 
587 a->NextItem = b->NextItem; 
588 b->PrevItem = a->PrevItem; 
589 
590 a->PrevItem = b; 
591 b->NextItem = a; 
592 
593 // Fix head and tail if they were involved in the swap. 
594 if (HeadItem == a) 
595 HeadItem = b; 
596 
597 if (TailItem == b) 
598 TailItem = a; 
599 
600 // Since we swapped, a is now correctly ready for the next loop. 
601 numSwaps++; 
602 } 
603 else 
604 { 
605 a = a->NextItem; 
606 } 
607 numCompares++; 
608 } 
609 
610 return numSwaps; 
611} 
612 
613 
614template<typename T> template<typename CompareFunc> inline int tList<T>::BubbleBackward(CompareFunc compare, int maxCompares) 
615{ 
616 if (maxCompares == -1) 
617 maxCompares = ItemCount-1; 
618 else if (maxCompares > ItemCount-1) 
619 maxCompares = ItemCount-1; 
620 
621 // If there are no items, or only a single one, we're done. 
622 if ((ItemCount < 2) || (maxCompares == 0)) 
623 return 0; 
624 
625 T* a = TailItem; 
626 int numSwaps = 0; 
627 int numCompares = 0; 
628 
629 while ((a != HeadItem) && (numCompares < maxCompares)) 
630 { 
631 T* b = a->PrevItem; 
632 
633 // We're sorting from lowest to biggest, so if a < b we need to swap them. 
634 if (compare(*a, *b)) 
635 { 
636 // Swap. 
637 if (a->NextItem) 
638 a->NextItem->PrevItem = b; 
639 
640 if (b->PrevItem) 
641 b->PrevItem->NextItem = a; 
642 
643 a->PrevItem = b->PrevItem; 
644 b->NextItem = a->NextItem; 
645 
646 a->NextItem = b; 
647 b->PrevItem = a; 
648 
649 // Fix head and tail if they were involved in the swap. 
650 if (HeadItem == b) 
651 HeadItem = a; 
652 
653 if (TailItem == a) 
654 TailItem = b; 
655 
656 // Since we swapped, a is now correctly ready for the next loop. 
657 numSwaps++; 
658 } 
659 else 
660 { 
661 a = a->PrevItem; 
662 } 
663 numCompares++; 
664 } 
665 
666 return numSwaps; 
667} 
668 
669 
670template<typename T> inline T* tItList<T>::Remove(Iter& iter) 
671{ 
672 // It is perfectly valid to try to remove an object referenced by an invalid iterator. 
673 if (!iter.IsValid() || (this != iter.List)) 
674 return nullptr; 
675 
676 IterNode* node = Nodes.Remove(iter.Node); 
677 T* obj = (T*)node->Object; 
678 
679 delete node; 
680 iter.Node = 0; 
681 
682 return obj; 
683} 
684