Main Page   Class Hierarchy   Compound List   File List   Compound Members   File Members  

wvsorter.h

Go to the documentation of this file.
00001 /*
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 extern WvLink blank_wvlink;
00015 
00016 // the base class for sorted list iterators.
00017 // It is similar to IterBase, except for rewind(), next(), and cur().
00018 // The sorting is done in rewind(), which makes an array of WvLink
00019 // pointers and calls qsort.  "lptr" is a pointer to the current WvLink *
00020 // in the array, and next() increments to the next one.
00021 // NOTE: we do not keep "prev" because it makes no sense to do so.
00022 //       I guess Sorter::unlink() will be slow... <sigh>
00023 class WvSorterBase
00024 {
00025 public:
00026     typedef int (CompareFunc)(const void *a, const void *b);
00027     
00028     void *list;
00029     WvLink **array;
00030     WvLink **lptr;
00031     
00032     WvSorterBase(void *_list)
00033         { list = _list; array = lptr = NULL; }
00034     ~WvSorterBase()
00035         { if (array) delete array; }
00036     WvLink *next()
00037         { return lptr ? *(++lptr) : *(lptr = array); }
00038     WvLink *cur()
00039         { return lptr ? *lptr : &blank_wvlink; }
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)->data; }
00067     
00068     // declare standard iterator accessors
00069     WvIterStuff(_type_);
00070     
00071     //void rewind()
00072     //  { WvSorterBase::rewind((CompareFunc *)cmp); }
00073     
00074     void rewind()
00075       { WvSorterBase::rewind<_list_,_iter_>((CompareFunc *)cmp); }
00076 };
00077 
00078 
00079 // Note that this is largely the same as WvLink::SorterBase::rewind(),
00080 // except we iterate through a bunch of lists instead of a single one.
00081 template <class _list_,class _iter_>
00082 void WvSorterBase::rewind(CompareFunc *cmp)
00083 {
00084     if (array)
00085         delete array;
00086     array = lptr = NULL;
00087 
00088     int n = ((_list_ *)list)->count();
00089     array = new WvLink * [n+1];
00090     WvLink **aptr = array;
00091 
00092     // fill the array with data pointers for sorting, so that the user doesn't
00093     // have to deal with the WvLink objects.  Put the WvLink pointers back 
00094     // in after sorting.
00095     _iter_ i(*(_list_ *)list);
00096     aptr = array;
00097     for (i.rewind(); i.next(); )
00098     {
00099         *aptr = i.cur();
00100         aptr++;
00101     }
00102     
00103     *aptr = NULL;
00104 
00105     // sort the array.  "Very nearly re-entrant" (unless the compare function
00106     // ends up being called recursively or something really weird...)
00107     CompareFunc *old_compare = actual_compare;
00108     actual_compare = cmp;
00109     qsort(array, n, sizeof(WvLink *), magic_compare);
00110     actual_compare = old_compare;
00111 
00112     lptr = NULL;    // subsequent next() will set it to first element.
00113 }
00114 
00115 
00116 #endif // __WVSORTER_H

Generated on Sat Aug 24 23:07:56 2002 for WvStreams by doxygen1.2.15