Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Namespace Members | Class Members | File Members | Related Pages

wvsorter.h

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

Generated on Tue Oct 5 01:09:20 2004 for WvStreams by doxygen 1.3.7