1 #ifndef _XPTRLIST_ 2 #define _XPTRLIST_ 3 4 // By Andrew O'Meara 5 6 #include "UtilStr.h" 7 8 // Post: Returns a num >= 0 iff the first arg is less than or equal to the second arg. 9 // Returns a num < 0 iff the first arg is greater than the second arg. 10 typedef int (*CompFunctionT)(const void*, const void*); 11 12 13 enum ListOrderingT { 14 cOrderImportant, 15 cOrderNotImportant, 16 cSortLowToHigh, 17 cSortHighToLow 18 }; 19 20 class XPtrList : protected UtilStr { 21 22 friend class XStrList; 23 friend class XDictionary; 24 friend class Hashtable; 25 friend class XFloatList; 26 friend class XLongList; 27 28 public: 29 XPtrList( const XPtrList& inList ); 30 XPtrList( ListOrderingT inOrdering = cOrderNotImportant ); 31 32 // Post: Assigns this from <inList>. 33 void Assign( const XPtrList& inList ); 34 35 // Post: Adds the ptr to this' list 36 // Order: O( 1 ), O( log n ) if sorting is on. 37 // Note: Returns what index the new element occupies (1-based indexing). 38 long Add( const void* inPtrToAdd ); 39 40 // Post: Adds the ptr to this' list after (existing) ptr number inN--make inN 0 if you want your ptr to be the 1st element 41 // Order: O( 1 ) 42 // Note: If inN is invalid, the closest element is used 43 void Add( const void* inPtrToAdd, long inN ); 44 45 // Post: Adds each element of the incoming list to this list. This is functionally the same as 46 // looping thru the size of inPtrList and calling this.Add() for each element. 47 void Add( const XPtrList& inPtrList ); 48 49 // Post: Searches for the ptr in the list and removes it if found. 50 // Note: <true> is returned if the ptr was found (and removed) 51 // Order: O( N ), O( log n + alpha n ) if sorting is on. 52 bool Remove( const void* inPtrToRemove ); 53 54 // Note: <true> is returned if the element was found (and removed) 55 // Order: O( N ), O( log n ) if sorting is on. 56 // Note: When order is set to be preserved (via cOrderImportant or a specificed sort fcn), elements 57 // at the end of the list are removed faster 58 bool RemoveElement( long inIndex ); 59 bool RemoveLast(); 60 61 // Post: Empties the ptr list 62 void RemoveAll(); 63 64 // Post: Used to fetch any given ptr. If the index exists, <true> is returned and the ptr is copied to *inPtrDest. 65 // Note: One based indexing is used 66 // Order: O( 1 ) 67 void* Fetch( long inIndex ) const; 68 bool Fetch( long inIndex, void** ioPtrDest ) const; FetchLast(void ** ioPtrDest)69 inline bool FetchLast( void** ioPtrDest ) const { return Fetch( Count(), ioPtrDest ); } 70 71 // Allows easy dynamic array usage. Simple use any index and XPtrList will expand to meet that size. 72 // Impt: Zero based indexing is used here!! (In contrast to Fetch()) 73 // Note: Elements that are newly accessed are initialized to 0 74 // Note: Indexs below 0 lead to sDummy; 75 // Note: Since caller has access to changes values, any current sorting fcn is not used 76 void*& operator[] ( const long inIndex ); 77 78 // Post: Moves element at <inIndex> so that it has index 1. 79 void MoveToHead( long inIndex ); 80 81 // Post: Searches for the given ptr in its ptr list and returns the index of the match 82 // If the item cannot be found, 0 is returned 83 // Note: One based indexing is used 84 // Order: O( N ), O( log n ) if sorting is on. 85 long FindIndexOf( const void* inMatchPtr ) const; 86 87 // Post: Returns the number of items in this list. 88 // Order: O( 1 ) Count()89 inline long Count() const { return length() / 4; } 90 91 // Post: All ptrs in this list are randomly reordered. 92 void Randomize(); 93 94 // Allows the compare fcn to be set. Causes the current contents to be removed. 95 void SetCompFcn( CompFunctionT inFcn, bool inSortLowToHigh ); 96 97 protected: 98 99 100 ListOrderingT mOrdering; 101 CompFunctionT mCompFcn; 102 103 // Pre: The list of nums must be sorted 104 // Post: Returns the (one based) index of the predicessor of <inNum>. If zero is returned, 105 // then <inNum> is <= than all the elements in the list. 106 long FetchPredIndex( const void* inNum ) const; 107 108 static void* sDummy; 109 110 }; 111 112 113 114 115 116 #endif 117