home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 5 / Apprentice-Release5.iso / Source Code / Libraries / DCLAP 6d / dclap6d / DClap / DList.h < prev    next >
Encoding:
Text File  |  1996-07-05  |  3.0 KB  |  111 lines  |  [TEXT/R*ch]
  1. // DList.h
  2. // d.g.gilbert
  3.  
  4. #ifndef _DLIST_
  5. #define _DLIST_
  6.  
  7. #include "Dvibrant.h"
  8. #include "DObject.h"
  9.  
  10.  
  11.  
  12. enum CompareConsts { 
  13.     kEmptyIndex = -1,
  14.     kEmptySize = 0,
  15.     kMaxArrayIndex = -2 
  16.     };
  17.  
  18. typedef    short (*CompareFunc)( void*, void*);     // compare two list/array Items 
  19.  
  20.  
  21.  
  22. class DArray : public DObject
  23. {    
  24. public:
  25.     DArray(short itemSize = sizeof(long), long initialSize = 5);
  26.     virtual ~DArray();
  27.     virtual DObject* Clone();
  28.  
  29.     virtual long GetSize() { return fSize; }  
  30.     virtual Boolean IsEmpty(void) { return (fSize == kEmptySize); }  
  31.     virtual void SetArraySize(long theSize);    
  32.     
  33.     virtual void GetItemsAt(long index, void* itemPtr, long count);
  34.     virtual void InsertItemsBefore(long index, void* itemPtr, long count);
  35.     virtual void ReplaceItemsAt(long index, void* itemPtr, long count);
  36.     virtual void DeleteItemsAt(long index, long count);
  37.     virtual void DeleteAll(void);
  38.  
  39.     virtual long Search(CompareFunc compare, void *itemPtr);
  40.  
  41. protected:
  42.     long     fSize;                                     // count of items in array
  43.     short fItemSize;                             // byte size of items, power of 2
  44.     short fItemSizeShift;                 // power of 2 for size << shift
  45.     long     fArrayIncrement;                 // amount to increase array byte size by when needed
  46.     long    fArraySize;                             // current allocated byte size of array
  47.     void* fArrayStore;                        // storage space for array items
  48.  
  49.     virtual void* ComputeAddress(long index);
  50. };
  51.  
  52.  
  53.  
  54. class DList : public DArray     
  55. {        
  56. public:
  57.     enum ListFlags { 
  58.         kDontOwnObjects = 0, kOwnObjects = 2, 
  59.         kDontDeleteObjects = 0, kDeleteObjects= 4 
  60.         };
  61.     Boolean    fOwnObjects;
  62.     Boolean    fDeleteObjects;
  63.     CompareFunc    fCompareFunc;
  64.     
  65.     DList(CompareFunc itsComparer = NULL, short options = kDontOwnObjects + kDontDeleteObjects);        
  66.     virtual ~DList(); 
  67.  
  68.     virtual DObject* At(long index);
  69.     DObject* operator[](long index) { return At(index); }
  70.     virtual DObject* First(void);
  71.     virtual DObject* Last(void);
  72.  
  73.     virtual void AtPut(long index, DObject* newItem);
  74.     virtual void InsertBefore(long index, DObject* item);
  75.     virtual void InsertFirst(DObject* item);
  76.     virtual void InsertLast(DObject* item);
  77.     virtual void InsertInOrder(DObject* item);                // insert in sort order
  78.     
  79.     virtual long  GetEqualItemNo(DObject* item);          // uses fCompareFunc(item, indexobj)
  80.     virtual long  GetIdentityItemNo(DObject* item);        // uses long(item) == long(indexobj)
  81.  
  82.     virtual void Sort(void);                                                    // uses fCompareFunc(obj1,obj2)
  83.     virtual void SortBy(CompareFunc CompareItems);
  84.  
  85.     virtual void AtDelete(long index);
  86.     virtual void Delete(DObject* item);
  87.     
  88.     virtual void Push(DObject* item);     // last-in-first-out stack
  89.     virtual DObject* Pop(void);                 // last-in-first-out stack
  90.     
  91.     virtual void Queue(DObject* item);  // first-in-first-out queue
  92.     virtual DObject* Dequeue(void);       // first-in-first-out queue
  93.  
  94.     virtual void FreeAllObjects(void); 
  95.         
  96. private:
  97.     void QuickSort(long beginIndex, long endIndex, CompareFunc CompareItems);
  98.     long QSPartition(long beginIndex, long endIndex, CompareFunc CompareItems);
  99.     long QSRandomPartition(long beginIndex, long endIndex, CompareFunc CompareItems);
  100. };
  101.  
  102.  
  103.  
  104.  
  105.  
  106. DList*    FreeListIfObject(DList* aList);
  107.  
  108.  
  109.  
  110. #endif
  111.