WvStreams
wvsorter.h
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