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 Sat Mar 13 14:55:54 2004 for WvStreams by doxygen 1.3.6-20040222