http://www.ousob.com --- Legacy Redefined OuSob - File: /wwwroot/clipx/usr/include/wvstreams/wvsorter.h

/* -*- Mode: C++ -*- * Worldvisions Weaver Software: * Copyright (C) 1997-2002 Net Integration Technologies, Inc. * * An iterator that can sort anything that has an iterator, includes the * right member functions, and uses WvLink objects - at the moment, * this includes WvList- and WvHashTable-based objects. */ #ifndef __WVSORTER_H #define __WVSORTER_H #include "wvxplc.h" #include "wvlink.h" // the base class for sorted list iterators. // It is similar to IterBase, except for rewind(), next(), and cur(). // The sorting is done in rewind(), which makes an array of WvLink // pointers and calls qsort. "lptr" is a pointer to the current WvLink * // in the array, and next() increments to the next one. // NOTE: we do not keep "prev" because it makes no sense to do so. // I guess Sorter::unlink() will be slow... <sigh> // ...so we didn't implement it. class WvSorterBase { public: typedef int (CompareFunc)(const void *a, const void *b); void *list; void **array; void **lptr; WvSorterBase(void *_list) { list = _list; array = lptr = NULL; } ~WvSorterBase() { if (array) deletev array; } bool next() { return *(++lptr) != 0; } bool cur() { return *lptr != 0; } protected: template <class _list_,class _iter_> void rewind(CompareFunc *cmp); static int magic_compare(const void *_a, const void *_b); static CompareFunc *actual_compare; }; // the actual type-specific sorter. Set _list_ and _iter_ to be your // common base class (eg. WvListBase and WvListBase::IterBase) if possible, // so we don't need to generate a specific rewind(cmp) function for each // specific type of list. Since rewind(cmp) is the only non-inline function // in a sorter, that means you only need one of them per top-level container // type (ie. one for WvList and one for HashTable), not one per data type // you might store in such a container. template <class _type_,class _list_,class _iter_> class WvSorter : public WvSorterBase { public: typedef int (RealCompareFunc)(const _type_ *a, const _type_ *b); RealCompareFunc *cmp; WvSorter(_list_ &_list, RealCompareFunc *_cmp) : WvSorterBase(&_list) { cmp = _cmp; } _type_ *ptr() const { return (_type_ *)(*lptr); } // declare standard iterator accessors WvIterStuff(_type_); void rewind() { WvSorterBase::rewind<_list_,_iter_>((CompareFunc *)cmp); } }; // Note that this is largely the same as WvLink::SorterBase::rewind(), // except we iterate through a bunch of lists instead of a single one. template <class _list_,class _iter_> void WvSorterBase::rewind(CompareFunc *cmp) { int n, remaining; if (array) deletev array; array = lptr = NULL; _iter_ i(*(_list_ *)list); // count the number of elements n = 0; for (i.rewind(); i.next(); ) n++; typedef void *VoidPtr; array = new VoidPtr[n+2]; void **aptr = array; *aptr++ = NULL; // initial link is NULL, to act like a normal iterator for (remaining = n, i.rewind(); i.next() && remaining; remaining--) { *aptr = i.vptr(); aptr++; } // weird: list length changed? // (this can happen with "virtual" lists like ones from WvDirIter) if (remaining) n -= remaining; *aptr = NULL; // sort the array. "Very nearly re-entrant" (unless the compare function // ends up being called recursively or something really weird...) CompareFunc *old_compare = actual_compare; actual_compare = cmp; qsort(array+1, n, sizeof(void *), magic_compare); actual_compare = old_compare; lptr = array; } #endif // __WVSORTER_H