WvStreams
|
00001 /* -*- Mode: C++ -*- 00002 * Worldvisions Weaver Software: 00003 * Copyright (C) 1997-2002 Net Integration Technologies, Inc. 00004 * 00005 * An iterator that can sort anything that has an iterator, includes the 00006 * right member functions, and uses WvLink objects - at the moment, 00007 * this includes WvList- and WvHashTable-based objects. 00008 */ 00009 #ifndef __WVSORTER_H 00010 #define __WVSORTER_H 00011 00012 #include "wvxplc.h" 00013 #include "wvlink.h" 00014 00015 // the base class for sorted list iterators. 00016 // It is similar to IterBase, except for rewind(), next(), and cur(). 00017 // The sorting is done in rewind(), which makes an array of WvLink 00018 // pointers and calls qsort. "lptr" is a pointer to the current WvLink * 00019 // in the array, and next() increments to the next one. 00020 // NOTE: we do not keep "prev" because it makes no sense to do so. 00021 // I guess Sorter::unlink() will be slow... <sigh> 00022 // ...so we didn't implement it. 00023 class WvSorterBase 00024 { 00025 public: 00026 typedef int (CompareFunc)(const void *a, const void *b); 00027 00028 void *list; 00029 void **array; 00030 void **lptr; 00031 00032 WvSorterBase(void *_list) 00033 { list = _list; array = lptr = NULL; } 00034 ~WvSorterBase() 00035 { if (array) deletev array; } 00036 bool next() 00037 { return *(++lptr) != 0; } 00038 bool cur() 00039 { return *lptr != 0; } 00040 00041 protected: 00042 template <class _list_,class _iter_> void rewind(CompareFunc *cmp); 00043 00044 static int magic_compare(const void *_a, const void *_b); 00045 static CompareFunc *actual_compare; 00046 }; 00047 00048 // the actual type-specific sorter. Set _list_ and _iter_ to be your 00049 // common base class (eg. WvListBase and WvListBase::IterBase) if possible, 00050 // so we don't need to generate a specific rewind(cmp) function for each 00051 // specific type of list. Since rewind(cmp) is the only non-inline function 00052 // in a sorter, that means you only need one of them per top-level container 00053 // type (ie. one for WvList and one for HashTable), not one per data type 00054 // you might store in such a container. 00055 template <class _type_,class _list_,class _iter_> 00056 class WvSorter : public WvSorterBase 00057 { 00058 public: 00059 typedef int (RealCompareFunc)(const _type_ *a, const _type_ *b); 00060 RealCompareFunc *cmp; 00061 00062 WvSorter(_list_ &_list, RealCompareFunc *_cmp) 00063 : WvSorterBase(&_list) 00064 { cmp = _cmp; } 00065 _type_ *ptr() const 00066 { return (_type_ *)(*lptr); } 00067 00068 // declare standard iterator accessors 00069 WvIterStuff(_type_); 00070 00071 void rewind() 00072 { WvSorterBase::rewind<_list_,_iter_>((CompareFunc *)cmp); } 00073 }; 00074 00075 00076 // Note that this is largely the same as WvLink::SorterBase::rewind(), 00077 // except we iterate through a bunch of lists instead of a single one. 00078 template <class _list_,class _iter_> 00079 void WvSorterBase::rewind(CompareFunc *cmp) 00080 { 00081 int n, remaining; 00082 00083 if (array) 00084 deletev array; 00085 array = lptr = NULL; 00086 00087 _iter_ i(*(_list_ *)list); 00088 00089 // count the number of elements 00090 n = 0; 00091 for (i.rewind(); i.next(); ) 00092 n++; 00093 00094 typedef void *VoidPtr; 00095 array = new VoidPtr[n+2]; 00096 void **aptr = array; 00097 00098 *aptr++ = NULL; // initial link is NULL, to act like a normal iterator 00099 00100 for (remaining = n, i.rewind(); i.next() && remaining; remaining--) 00101 { 00102 *aptr = i.vptr(); 00103 aptr++; 00104 } 00105 00106 // weird: list length changed? 00107 // (this can happen with "virtual" lists like ones from WvDirIter) 00108 if (remaining) 00109 n -= remaining; 00110 00111 *aptr = NULL; 00112 00113 // sort the array. "Very nearly re-entrant" (unless the compare function 00114 // ends up being called recursively or something really weird...) 00115 CompareFunc *old_compare = actual_compare; 00116 actual_compare = cmp; 00117 qsort(array+1, n, sizeof(void *), magic_compare); 00118 actual_compare = old_compare; 00119 00120 lptr = array; 00121 } 00122 00123 00124 #endif // __WVSORTER_H