1 /*************************************************************************
2  *                                                                       *
3  * Tokamak Physics Engine, Copyright (C) 2002-2007 David Lam.            *
4  * All rights reserved.  Email: david@tokamakphysics.com                 *
5  *                       Web: www.tokamakphysics.com                     *
6  *                                                                       *
7  * This library is distributed in the hope that it will be useful,       *
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of        *
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the files    *
10  * LICENSE.TXT for more details.                                         *
11  *                                                                       *
12  *************************************************************************/
13 
14 #ifndef CONTAINERS_H
15 #define CONTAINERS_H
16 
17 #define _CRT_SECURE_DEPRECATE_MEMORY
18 #include <memory.h>
19 
20 #define PLACEMENT_MAGIC \
21 	public:\
22 	NEINLINE void * operator new(size_t s,void * addr)\
23 	{\
24 		return addr;\
25 	}\
26 	NEINLINE void * operator new[] (size_t s,void * addr)\
27 	{\
28 		return addr;\
29 	}\
30 	NEINLINE void operator delete(void *)\
31 	{\
32 	}\
33 	NEINLINE void operator delete[](void *)\
34 	{\
35 	}\
36 	NEINLINE void operator delete(void *, void *)\
37 	{\
38 	}\
39 	NEINLINE void operator delete[](void *, void *)\
40 	{\
41 	}
42 
43 template <class T, int initFixedSize = 1> class neSimpleArray
44 {
45 public:
46 	PLACEMENT_MAGIC
47 
IsFixedSize()48 	NEINLINE bool IsFixedSize()
49 	{
50 		return (initFixedSize != 1);
51 	}
52 
neSimpleArray()53 	NEINLINE neSimpleArray()
54 	{
55 		if (IsFixedSize())
56 		{
57 			data = initArray;
58 			nextFree = data;
59 			size = initFixedSize;
60 			alloc = NULL;
61 			growBy = 0;
62 			usedSize = 0;
63 		}
64 		else
65 		{
66 			data = NULL;
67 			nextFree = NULL;
68 			size = 0;
69 			alloc = &allocDef;
70 			growBy = 0;
71 			usedSize = 0;
72 		}
73 	}
~neSimpleArray()74 	NEINLINE ~neSimpleArray()
75 	{
76 		Free();
77 	}
78 	NEINLINE bool Reserve(s32 n, neAllocatorAbstract * al = NULL, s32 _growBy = 0)
79 	{
80 		if (IsFixedSize())
81 		{
82 			ASSERT(0);
83 			return false;
84 		}
85 		Free();
86 
87 		if (al)
88 			alloc = al;
89 		else
90 			alloc = & allocDef;
91 
92 		growBy = _growBy;
93 
94 		neByte * mem = alloc->Alloc(sizeof(T) * n);
95 
96 		data = (T*) mem;
97 
98 		if (data)
99 		{
100 			nextFree = data;
101 			size = n;
102 			return true;
103 		}
104 		return false;
105 	};
106 
107 	NEINLINE T * Alloc(s32 dummy = 0)
108 	{
109 		if (nextFree >= (data + size))
110 		{
111 			if (growBy == 0)
112 				return NULL;
113 
114 			T * oldData = data;
115 
116 			if (growBy == -1)
117 				data = (T*)alloc->Alloc((size * 2) * sizeof(T));
118 			else
119 				data = (T*)alloc->Alloc((size + growBy) * sizeof(T));
120 
121 			if (!data)
122 			{
123 				data = oldData;
124 
125 				return NULL;
126 			}
127 
128 			memcpy(data, oldData, size * sizeof(T));
129 
130 			if (oldData)
131 				alloc->Free((neByte*)oldData);
132 
133 			nextFree = data + size;
134 
135 			if (growBy == -1)
136 				size *= 2;
137 			else
138 				size += growBy;
139 
140 			usedSize++;
141 			return nextFree++;
142 		}
143 		else
144 		{
145 			usedSize++;
146 			return nextFree++;
147 		}
148 	}
GetIndex(T * c)149 	NEINLINE s32 GetIndex(T * c)
150 	{
151 		ASSERT(c >= data);
152 		ASSERT(c < nextFree);
153 
154 		return (s32)(c - data);
155 	}
GetUsedCount()156 	NEINLINE s32 GetUsedCount(){
157 		return (nextFree - data);
158 	}
GetTotalSize()159 	NEINLINE s32 GetTotalSize(){
160 		return size;
161 	}
Free()162 	NEINLINE void Free()
163 	{
164 		if (IsFixedSize())
165 		{
166 			return;
167 		}
168 		if (data)
169 		{
170 			alloc->Free((neByte*)data);
171 		}
172 		data = NULL;
173 		nextFree = NULL;
174 		size = 0;
175 		usedSize = 0;
176 	}
Clear()177 	NEINLINE void Clear()
178 	{
179 		nextFree = data;
180 		usedSize = 0;
181 	}
182 	NEINLINE T & operator [] (s32 index) {
183 		ASSERT(index >= 0);
184 		ASSERT(index < size);
185 		return data[index];
186 	}
MakeFromPointer(T * pdata,s32 makeSize)187 	NEINLINE void MakeFromPointer(T * pdata, s32 makeSize)
188 	{
189 		data = pdata;
190 		size = makeSize;
191 		usedSize = size;
192 		nextFree = pdata + makeSize;
193 		alloc = NULL;
194 		growBy = 0;
195 	}
196 protected:
197 	T * data;
198 	T * nextFree;
199 	s32 size;
200 	s32 usedSize;
201 	neAllocatorAbstract * alloc;
202 	neAllocatorDefault allocDef;
203 	s32 growBy;
204 	T initArray[initFixedSize];
205 };
206 
207 template <class T, int initFixedSize = 1> class neArray
208 {
209 PLACEMENT_MAGIC
210 public:
IsFixedSize()211 	NEINLINE bool IsFixedSize()
212 	{
213 		return (initFixedSize != 1);
214 	}
neArray()215 	NEINLINE neArray(){
216 		if (IsFixedSize())
217 		{
218 			data = initArray;
219 			nextFree = data;
220 			size = initFixedSize;
221 			alloc = NULL;
222 			growBy = 0;
223 		}
224 		else
225 		{
226 			data = NULL;
227 			nextFree = NULL;
228 			size = 0;
229 			alloc = &allocDef;
230 			growBy = 0;
231 		}
232 	}
~neArray()233 	NEINLINE ~neArray()
234 	{
235 		Free();
236 	}
237 	NEINLINE bool Reserve(s32 n, neAllocatorAbstract * al = NULL, s32 _growBy = 0)
238 	{
239 		if (IsFixedSize())
240 		{
241 			ASSERT(0);
242 			return false;
243 		}
244 		Free();
245 
246 		if (al)
247 			alloc = al;
248 		else
249 			alloc = & allocDef;
250 
251 		growBy = _growBy;
252 
253 		neByte * mem = alloc->Alloc(sizeof(T) * n);
254 
255 		data = (T*) mem;
256 
257 		if (data)
258 		{
259 			nextFree = data;
260 			size = n;
261 			return true;
262 		}
263 		return false;
264 	};
265 
Alloc()266 	NEINLINE T * Alloc()
267 	{
268 		if (nextFree >= (data + size))
269 		{
270 			if (growBy == 0)
271 				return NULL;
272 
273 			T * oldData = data;
274 
275 			if (growBy == -1)
276 				data = (T*)alloc->Alloc(sizeof(T) * (size * 2));
277 			else
278 				data = (T*)alloc->Alloc(sizeof(T) * (size + growBy));
279 
280 			if (!data)
281 			{
282 				data = oldData;
283 
284 				return NULL;
285 			}
286 
287 			memcpy(data, oldData, size * sizeof(T));
288 
289 			if (oldData)
290 				alloc->Free((neByte*)oldData);
291 
292 			nextFree = data + size;
293 
294 			if (growBy == -1)
295 				size *= 2;
296 			else
297 				size += growBy;
298 
299 		}
300 		T * ret = new ((void*)(nextFree++)) T;
301 
302 		return ret;
303 	}
GetIndex(T * c)304 	NEINLINE s32 GetIndex(T * c)
305 	{
306 		ASSERT(c >= data);
307 		ASSERT(c < nextFree);
308 
309 		return (s32)(c - data);
310 	}
GetUsedCount()311 	NEINLINE s32 GetUsedCount(){
312 		return (nextFree - data);
313 	}
GetTotalSize()314 	NEINLINE s32 GetTotalSize(){
315 		return size;
316 	}
Free()317 	NEINLINE void Free()
318 	{
319 		if (IsFixedSize())
320 		{
321 			return;
322 		}
323 		if (data)
324 		{
325 			//delete [] (data, (void*)data);
326 
327 			alloc->Free((neByte*)data);
328 		}
329 		data = NULL;
330 		nextFree = NULL;
331 		size = 0;
332 	}
Clear()333 	NEINLINE void Clear()
334 	{
335 		nextFree = data;
336 	}
337 	NEINLINE T & operator [] (s32 index) {
338 		ASSERT(index >= 0);
339 		ASSERT(index < size);
340 		return data[index];
341 	}
MakeFromPointer(T * pdata,s32 makeSize)342 	NEINLINE void MakeFromPointer(T * pdata, s32 makeSize)
343 	{
344 		data = pdata;
345 		size = makeSize;
346 		nextFree = pdata + makeSize;
347 		alloc = NULL;
348 		growBy = 0;
349 	}
350 protected:
351 	T * data;
352 	T * nextFree;
353 	s32 size;
354 	neAllocatorAbstract * alloc;
355 	neAllocatorDefault allocDef;
356 	s32 growBy;
357 
358 	T initArray[initFixedSize];
359 };
360 
361 /////////////////////////////////////////////////////////////
362 
363 template <class T> class neFreeListItem
364 {
365 PLACEMENT_MAGIC
366 public:
367 /*
368 	NEINLINE void * operator new (size_t s,void * addr)
369 	{
370 		return addr;
371 	}
372 	NEINLINE void * operator new[] (size_t s,void * addr)
373 	{
374 		return addr;
375 	}
376 	NEINLINE void operator delete(void *, void *)
377 	{
378 	}
379 	NEINLINE void operator delete[](void *, void *)
380 	{
381 	}
382 */	T thing;
383 	neFreeListItem * next;
384 	neFreeListItem * prev;
385 	bool state;
386 
neFreeListItem()387 	NEINLINE neFreeListItem()
388 	{
389 		prev = NULL;
390 		next = NULL;
391 		state = false;
392 	}
393 
Remove()394 	NEINLINE void Remove()
395 	{
396 		if (next != NULL)
397 		{
398 			next->prev = prev;
399 		}
400 		if (prev != NULL)
401 		{
402 			prev->next = next;
403 		}
404 		Solo();
405 	}
Insert(neFreeListItem * newItem)406 	NEINLINE void Insert(neFreeListItem * newItem)
407 	{
408 		newItem->next = this;
409 		newItem->prev = prev;
410 		if (prev)
411 		{
412 			prev->next = newItem;
413 		}
414 		prev = newItem;
415 	}
Append(neFreeListItem * newItem)416 	NEINLINE void Append(neFreeListItem * newItem)
417 	{
418 		newItem->next = next;
419 		newItem->prev = this;
420 		if (next)
421 		{
422 			next->prev = newItem;
423 		}
424 		next = newItem;
425 	}
Concat(neFreeListItem * newItem)426 	NEINLINE void Concat(neFreeListItem * newItem)
427 	{
428 		ASSERT(next == NULL);
429 
430 		next = newItem;
431 
432 		newItem->prev = this;
433 	}
Solo()434 	NEINLINE void Solo()
435 	{
436 		prev = NULL;
437 		next = NULL;
438 	}
439 };
440 
441 /////////////////////////////////////////////////////////////
442 
443 template <class T, int initFixedSize = 1> class neDLinkList
444 {
445 public:
446 	typedef neFreeListItem<T> listItem;
447 
IsFixedSize()448 	NEINLINE bool IsFixedSize()
449 	{
450 		return (initFixedSize != 1);
451 	}
CheckBelongAndInUse(T * t)452 	NEINLINE neBool CheckBelongAndInUse(T * t)
453 	{
454 		listItem * item = (listItem *)t;
455 
456 		if (item < data)
457 			return false;
458 
459 		if (item >= (data + size))
460 			return false;
461 
462 		return item->state; //1 = in use
463 	}
Init()464 	NEINLINE void Init()
465 	{
466 		if (!IsFixedSize())
467 		{
468 			data = NULL;
469 			unused = NULL;
470 			used = NULL;
471 			unusedTail = NULL;
472 			usedTail = NULL;
473 			size = 0;
474 			usedCount = 0;
475 			unusedCount = 0;
476 		}
477 		else
478 		{
479 			data = initArray;
480 			size = initFixedSize;
481 			for (int i = 0; i < size; i++)
482 			{
483 				data[i].next = &(data[i+1]);
484 				data[i].prev = &(data[i-1]);
485 				data[i].state = false;
486 			}
487 			data[0].prev = NULL;
488 			data[size-1].next = NULL;
489 
490 			unused = data;
491 			unusedTail = data + size;
492 			unusedCount = size;
493 
494 			used = NULL;
495 			usedTail = NULL;
496 			usedCount = 0;
497 		}
498 	}
neDLinkList()499 	NEINLINE neDLinkList()
500 	{
501 		alloc = &allocDef;
502 
503 		Init();
504 	}
Free()505 	NEINLINE void Free()
506 	{
507 		if (IsFixedSize())
508 			return;
509 
510 		//delete [] (data, (void*) data);
511 
512 		if (data)
513 			alloc->Free((neByte*)data-mallocNewDiff);
514 
515 		Init();
516 	}
Size()517 	NEINLINE s32 Size()
518 	{
519 		return size;
520 	}
~neDLinkList()521 	NEINLINE ~neDLinkList()
522 	{
523 		Free();
524 	}
525 	NEINLINE T * Alloc(s32 flag = 0)
526 	{
527 		if (!unused)
528 			return NULL;
529 
530 		T * ret = &(unused->thing);
531 
532 		ASSERT(unused->state == false);
533 
534 		unused->state = true;
535 
536 		listItem * newUnusedHead;
537 
538 		newUnusedHead = unused->next;
539 
540 		unused->Remove();
541 
542 		if (flag == 0)
543 		{
544 			if (usedTail)
545 			{
546 				usedTail->Append(unused);
547 				usedTail = unused;
548 			}
549 			else
550 			{
551 				used = unused;
552 				used->Solo();
553 				usedTail = used;
554 			}
555 		}
556 		else
557 		{
558 			unused->Solo();
559 		}
560 
561 		if (unused == unusedTail)
562 		{
563 			unusedTail = NULL;
564 			unused = NULL;;
565 			ASSERT(newUnusedHead == NULL);
566 		}
567 		else
568 			unused = newUnusedHead;
569 
570 		unusedCount--;
571 		usedCount++;
572 		return ret;
573 	}
574 	NEINLINE bool Reserve(s32 n, neAllocatorAbstract * al = NULL)
575 	{
576 		if (IsFixedSize())
577 		{
578 			ASSERT(0);
579 			return false;
580 		}
581 		Free();
582 
583 		if (n == 0)
584 			return true;
585 
586 		if (al)
587 			alloc = al;
588 
589 		neByte * mem = alloc->Alloc(sizeof(listItem) * n + 4);
590 
591 		data = new (mem) listItem[n];
592 
593 		mallocNewDiff = (neByte*)data - mem;
594 
595 		size = n;
596 
597 		for (int i = 0; i < n; i++)
598 		{
599 			data[i].next = &(data[i+1]);
600 			data[i].prev = &(data[i-1]);
601 			data[i].state = false;
602 		}
603 		data[0].prev = NULL;
604 		data[n-1].next = NULL;
605 
606 		unused = data;
607 		unusedTail = data + size;
608 		unusedCount = n;
609 
610 		used = NULL;
611 		usedTail = NULL;
612 		usedCount = 0;
613 
614 		return true;
615 	}
616 	NEINLINE void Dealloc(T * thing, s32 flag = 0)
617 	{
618 		if (!flag && !used)
619 		{
620 			ASSERT(0);
621 			return;
622 		}
623 
624 		s32 n = GetID(thing);
625 
626 		ASSERT(n >= 0);
627 		ASSERT(n < size);
628 
629 		listItem * newUnused = &(data[n]);
630 
631 		ASSERT(newUnused->state == true);
632 
633 		newUnused->state = false;
634 
635 		if (flag == 0)
636 		{
637 			if (newUnused == used) // dealloc head of used
638 			{
639 				used = newUnused->next;
640 			}
641 			if (newUnused == usedTail) // dealloc tail of used
642 			{
643 				usedTail = newUnused->prev;
644 			}
645 		}
646 
647 		newUnused->Remove();
648 
649 		if (unused)
650 		{
651 			unused->Insert(newUnused);
652 		}
653 		else
654 		{
655 			newUnused->Solo();
656 			unusedTail = newUnused;
657 		}
658 		unused = newUnused;
659 
660 		unusedCount++;
661 		usedCount--;
662 	}
GetID(T * t)663 	NEINLINE s32 GetID(T * t)
664 	{
665 		return ((listItem*)t - data);
666 	}
GetUsedCount()667 	NEINLINE s32 GetUsedCount()
668 	{
669 		return usedCount;
670 	}
671 	class iterator;
672 
Clear()673 	NEINLINE void Clear()
674 	{
675 		iterator iter;
676 
677 		for (iter = BeginUsed(); iter.Valid();)
678 		{
679 			iterator next = BeginNext(iter);
680 
681 			Dealloc(*iter);
682 
683 			iter = next;
684 		}
685 	}
BeginUsed()686 	NEINLINE iterator BeginUsed()
687 	{
688 		iterator iter;
689 
690 		iter.cur = used;
691 
692 		return iter;
693 	}
BeginUnused()694 	NEINLINE iterator BeginUnused()
695 	{
696 		iterator iter;
697 
698 		iter.cur = unused;
699 
700 		return iter;
701 	}
BeginNext(const iterator & it)702 	NEINLINE iterator BeginNext(const iterator & it)
703 	{
704 		iterator next;
705 
706 		next.cur = it.cur->next;
707 
708 		return next;
709 	}
710 	class iterator
711 	{
712 	public:
713 		NEINLINE T * operator * () const
714 		{
715 			if (cur)
716 				return &(cur->thing);
717 			return NULL;
718 		}
719 		NEINLINE bool operator ++ (int)
720 		{
721 			if (cur)
722 			{
723 				cur = cur->next;
724 				return true;
725 			}
726 			return false;
727 		}
728 		NEINLINE bool operator -- ()
729 		{
730 			if (cur)
731 			{
732 				cur = cur->prev;
733 				return true;
734 			}
735 			return false;
736 		}
Valid()737 		NEINLINE bool Valid()
738 		{
739 			return (cur != NULL);
740 		}
741 	public:
742 		listItem * cur;
743 	};
744 
745 public:
746 	listItem * data;
747 	listItem * unused;
748 	listItem * used;
749 	listItem * unusedTail;
750 	listItem * usedTail;
751 	s32 size;
752 	s32 unusedCount;
753 	s32 usedCount;
754 	neAllocatorAbstract * alloc;
755 	neAllocatorDefault allocDef;
756 	s32 mallocNewDiff;
757 	listItem initArray[initFixedSize];
758 };
759 /*
760 template <class T, int initFixedSize = 1> class neHeap
761 {
762 public:
763 	typedef neDLinkList<T*, initFixedSize> FreeList;
764 
765 	NEINLINE IsFixedSize()
766 	{
767 		return (initFixedSize != 1);
768 	}
769 	NEINLINE neHeap()
770 	{
771 		Init();
772 	}
773 	NEINLINE void Init()
774 	{
775 		freeList.Init();
776 
777 		if (IsFixedSize())
778 		{
779 			buffer = initArray;
780 			alloc = NULL;
781 		}
782 		else
783 		{
784 			buffer = NULL;
785 			alloc = &allocDef;
786 		}
787 	}
788 	NEINLINE ~neHeap()
789 	{
790 		Free();
791 	}
792 	NEINLINE bool Reserve(s32 n, neAllocatorAbstract * al = NULL)
793 	{
794 		if (IsFixedSize())
795 		{
796 			ASSERT(0);
797 			return false;
798 		}
799 		Free();
800 
801 		if (!freeList.Reserve(n, al))
802 			return false;
803 
804 		if (al)
805 			alloc = al;
806 
807 		neByte * mem = alloc->Alloc(sizeof(T) * n + 4);
808 
809 		buffer = new(mem) T[n];
810 
811 		mallocNewDiff = (neByte*)buffer - mem;
812 
813 		if (!buffer)
814 		{
815 			Free();
816 			return false;
817 		}
818 		FreeList::iterator it;
819 
820 		int i = 0;
821 		for (it = freeList.BeginUnused(); it.Valid(); it++)
822 		{
823 			(**it) = &(buffer[i]);
824 			i++;
825 		}
826 		return true;
827 	}
828 	NEINLINE T * Alloc(s32 flag = 0)
829 	{
830 		T ** pt =  freeList.Alloc(flag);
831 
832 		new (*pt) T;
833 
834 		if (!pt)
835 			return NULL;
836 		else
837 			return *pt;
838 	}
839 	NEINLINE void Dealloc(T * t, s32 flag = 0)
840 	{
841 		s32 offset = GetID(t);
842 
843 		FreeList::listItem * li = freeList.data + offset;
844 
845 		freeList.Dealloc((T**)li, flag);
846 	}
847 	NEINLINE s32 GetID(T * t)
848 	{
849 		return (t - buffer);
850 	}
851 	NEINLINE neBool IsInUse(T * t)
852 	{
853 		s32 i = GetID(t);
854 
855 		ASSERT(i >= 0 && i <freeList.size);
856 
857 		return freeList.data[i].state;
858 	}
859 	NEINLINE void Free()
860 	{
861 		if (IsFixedSize())
862 			return;
863 
864 		//delete [] (buffer, (void*)buffer);
865 
866 		if (buffer)
867 			alloc->Free((neByte*)buffer-mallocNewDiff);
868 
869 		freeList.Free();
870 
871 		Init();
872 	}
873 	NEINLINE s32 GetUsedCount()
874 	{
875 		return freeList.usedCount;
876 	}
877 	NEINLINE s32 GetUnusedCount()
878 	{
879 		return freeList.unusedCount;
880 	}
881 	NEINLINE s32 Size()
882 	{
883 		return freeList.size;
884 	}
885 	class iterator;
886 
887 	NEINLINE iterator BeginUsed()
888 	{
889 		iterator cur;
890 
891 		cur.iter = freeList.BeginUsed();
892 
893 		return cur;
894 	}
895 	NEINLINE iterator BeginUnused()
896 	{
897 		iterator cur;
898 
899 		cur.iter = freeList.BeginUnused();
900 
901 		return cur;
902 	}
903 	NEINLINE iterator BeginNext(const iterator & it)
904 	{
905 		iterator next;
906 
907 		next.iter = freeList.BeginNext(it.iter);
908 
909 		return next;
910 	}
911 	class iterator
912 	{
913 	public:
914 		FreeList::iterator iter;
915 
916 		NEINLINE T * operator * () const
917 		{
918 			return (**iter);
919 		}
920 		NEINLINE bool operator ++ (int)
921 		{
922 			return (iter++);
923 		}
924 		NEINLINE bool operator -- ()
925 		{
926 			return (iter--)
927 		}
928 		NEINLINE bool Valid()
929 		{
930 			return (iter.Valid());
931 		}
932 	};
933 
934 protected:
935 	T * buffer;
936 	FreeList freeList;
937 	neAllocatorAbstract * alloc;
938 	neAllocatorDefault allocDef;
939 	s32 mallocNewDiff;
940 
941 	T initArray[initFixedSize];
942 };
943 */
944 template <class T> class neCollection
945 {
946 public:
947 	typedef neFreeListItem<T*> itemType;
948 
neCollection()949 	neCollection()
950 	{
951 		Reset();
952 	}
Reset()953 	void Reset()
954 	{
955 		headItem = NULL;
956 		tailItem = NULL;
957 		count = 0;
958 	}
Add(itemType * add)959 	void Add(itemType * add)
960 	{
961 		ASSERT(add);
962 
963 		if (headItem)
964 		{
965 			tailItem->Append(add);
966 
967 			tailItem = add;
968 		}
969 		else
970 		{
971 			headItem = add;
972 			tailItem = add;
973 		}
974 		count++;
975 	}
Remove(itemType * rem)976 	void Remove(itemType * rem)
977 	{
978 		ASSERT(count > 0);
979 
980 		ASSERT(rem);
981 
982 		if (rem == headItem)
983 		{
984 			headItem = rem->next;
985 		}
986 		if (rem == tailItem)
987 		{
988 			tailItem = rem->prev;
989 		}
990 		rem->Remove();
991 
992 		count --;
993 	}
GetHead()994 	itemType * GetHead()
995 	{
996 		return headItem;
997 	}
GetNext(itemType * cur)998 	itemType * GetNext(itemType * cur)
999 	{
1000 		return cur->next;
1001 	}
GetPrev(itemType * cur)1002 	itemType * GetPrev(itemType * cur)
1003 	{
1004 		return cur->prev;
1005 	}
1006 
1007 public:
1008 	neFreeListItem<T*> * headItem;
1009 	neFreeListItem<T*> * tailItem;
1010 	s32 count;
1011 };
1012 
1013 template <class T> class neList
1014 {
1015 public:
1016 	typedef neFreeListItem<T> itemType;
1017 
neList()1018 	neList()
1019 	{
1020 		Reset();
1021 	}
Reset()1022 	void Reset()
1023 	{
1024 		headItem = NULL;
1025 		tailItem = NULL;
1026 		count = 0;
1027 	}
Add(T * add)1028 	void Add(T * add)
1029 	{
1030 		ASSERT(add);
1031 
1032 		itemType * addItem = (itemType *)add;
1033 
1034 		if (headItem)
1035 		{
1036 			tailItem->Append(addItem);
1037 
1038 			tailItem = addItem;
1039 		}
1040 		else
1041 		{
1042 			headItem = addItem;
1043 			tailItem = addItem;
1044 		}
1045 		count++;
1046 	}
AddOrder(T * add)1047 	void AddOrder(T * add)
1048 	{
1049 		ASSERT(add);
1050 
1051 		itemType * addItem = (itemType *)add;
1052 
1053 		if (!headItem)
1054 		{
1055 			headItem = addItem;
1056 
1057 			tailItem = addItem;
1058 
1059 			count = 1;
1060 
1061 			return;
1062 		}
1063 
1064 		itemType * curItem = tailItem;
1065 
1066 		neBool done = false;
1067 
1068 		while (curItem)
1069 		{
1070 			T * curT = (T *)curItem;
1071 
1072 			if (add->Value() <= curT->Value())
1073 			{
1074 				done = true;
1075 
1076 				curItem->Append(addItem);
1077 
1078 				if (curItem == tailItem)
1079 				{
1080 					tailItem = addItem;
1081 				}
1082 				break;
1083 			}
1084 			curItem = curItem->prev;
1085 		}
1086 		if (!done)
1087 		{
1088 			headItem->Insert(addItem);
1089 
1090 			headItem = addItem;
1091 		}
1092 		count++;
1093 	}
UpdateOrder(T * u)1094 	void UpdateOrder(T * u)
1095 	{
1096 		if (count == 1)
1097 			return;
1098 
1099 		itemType * uItem = (itemType *) u;
1100 
1101 		itemType * cItem;
1102 
1103 		neBool done = false;
1104 
1105 		if (uItem == tailItem) // move up
1106 		{
1107 			cItem = uItem->prev;
1108 
1109 			Remove(u);
1110 
1111 			while (cItem)
1112 			{
1113 				if (((T*)cItem)->Value() >= u->Value())
1114 				{
1115 					cItem->Append(uItem);
1116 
1117 					if (cItem == tailItem)
1118 					{
1119 						tailItem = uItem;
1120 					}
1121 					done = true;
1122 
1123 					break;
1124 				}
1125 				cItem = cItem->prev;
1126 			}
1127 			if (!done)
1128 			{
1129 				headItem->Insert(uItem);
1130 
1131 				headItem = uItem;
1132 			}
1133 			count++; // because Remove dec count;
1134 		}
1135 		else if (uItem == headItem) // move down
1136 		{
1137 			cItem = uItem->next;
1138 
1139 			Remove(u);
1140 
1141 			while (cItem)
1142 			{
1143 				if (((T*)cItem)->Value() <= u->Value())
1144 				{
1145 					cItem->Insert(uItem);
1146 
1147 					if (cItem == headItem)
1148 					{
1149 						headItem = uItem;
1150 					}
1151 					done = true;
1152 
1153 					break;
1154 				}
1155 				cItem = cItem->next;
1156 			}
1157 			if (!done)
1158 			{
1159 				tailItem->Append(uItem);
1160 
1161 				tailItem = uItem;
1162 			}
1163 			count ++;
1164 		}
1165 		else
1166 		{
1167 			itemType * nextItem = uItem->next;
1168 
1169 			T * nextT = (T*) nextItem;
1170 
1171 			if (u->Value() < nextT->Value())
1172 			{
1173 				//move down
1174 				cItem = nextItem;
1175 
1176 				Remove(u);
1177 
1178 				while (cItem)
1179 				{
1180 					if (((T*)cItem)->Value() <= u->Value())
1181 					{
1182 						cItem->Insert(uItem);
1183 
1184 						done = true;
1185 
1186 						break;
1187 					}
1188 					cItem = cItem->next;
1189 				}
1190 				if (!done)
1191 				{
1192 					tailItem->Append(uItem);
1193 
1194 					tailItem = uItem;
1195 				}
1196 				count ++;
1197 			}
1198 			else
1199 			{
1200 				//move up
1201 				cItem = uItem->prev;
1202 
1203 				Remove(u);
1204 
1205 				while (cItem)
1206 				{
1207 					if (((T*)cItem)->Value() >= u->Value())
1208 					{
1209 						cItem->Append(uItem);
1210 
1211 						if (cItem == tailItem)
1212 						{
1213 							tailItem = uItem;
1214 						}
1215 						done = true;
1216 
1217 						break;
1218 					}
1219 					cItem = cItem->prev;
1220 				}
1221 				if (!done)
1222 				{
1223 					headItem->Insert(uItem);
1224 
1225 					headItem = uItem;
1226 				}
1227 				count++; // because Remove dec count;
1228 			}
1229 		}
1230 	}
Remove(T * rem)1231 	void Remove(T * rem)
1232 	{
1233 		ASSERT(count > 0);
1234 
1235 		ASSERT(rem);
1236 
1237 		itemType * remItem = (itemType *)rem;
1238 
1239 		if (remItem == headItem)
1240 		{
1241 			headItem = remItem->next;
1242 		}
1243 		if (remItem == tailItem)
1244 		{
1245 			tailItem = remItem->prev;
1246 		}
1247 		remItem->Remove();
1248 
1249 		count --;
1250 	}
GetHead()1251 	T * GetHead()
1252 	{
1253 		return(T*)headItem;
1254 	}
GetNext(T * cur)1255 	T * GetNext(T * cur)
1256 	{
1257 		return (T*)((itemType*)cur)->next;
1258 	}
GetPrev(T * cur)1259 	T * GetPrev(T * cur)
1260 	{
1261 		return (T*)((itemType*)cur)->prev;
1262 	}
1263 
1264 public:
1265 	itemType * headItem;
1266 	itemType * tailItem;
1267 	s32 count;
1268 };
1269 
1270 #endif //CONTAINERS_H