include/wvsorter.h

   1 /* -*- Mode: C++ -*-
   2  * Worldvisions Weaver Software:
   3  *   Copyright (C) 1997-2002 Net Integration Technologies, Inc.
   4  *
   5  * An iterator that can sort anything that has an iterator, includes the
   6  * right member functions, and uses WvLink objects - at the moment,
   7  * this includes WvList- and WvHashTable-based objects.
   8  */
   9 #ifndef __WVSORTER_H
  10 #define __WVSORTER_H
  11
  12 #include "wvxplc.h"
  13 #include "wvlink.h"
  14
  15 // the base class for sorted list iterators.
  16 // It is similar to IterBase, except for rewind(), next(), and cur().
  17 // The sorting is done in rewind(), which makes an array of WvLink
  18 // pointers and calls qsort.  "lptr" is a pointer to the current WvLink *
  19 // in the array, and next() increments to the next one.
  20 // NOTE: we do not keep "prev" because it makes no sense to do so.
  21 //       I guess Sorter::unlink() will be slow... <sigh>
  22 //       ...so we didn't implement it.
  23 class WvSorterBase
  24 {
  25 public:
  26     typedef int (CompareFunc)(const void *a, const void *b);
  27
  28     void *list;
  29     void **array;
  30     void **lptr;
  31
  32     WvSorterBase(void *_list)
  33         { list = _list; array = lptr = NULL; }
  34     ~WvSorterBase()
  35         { if (array) deletev array; }
  36     bool next()
  37         { return *(++lptr) != 0; }
  38     bool cur()
  39         { return *lptr != 0; }
  40
  41 protected:
  42     template <class _list_,class _iter_> void rewind(CompareFunc *cmp);
  43
  44     static int magic_compare(const void *_a, const void *_b);
  45     static CompareFunc *actual_compare;
  46 };
  47
  48 // the actual type-specific sorter.  Set _list_ and _iter_ to be your
  49 // common base class (eg. WvListBase and WvListBase::IterBase) if possible,
  50 // so we don't need to generate a specific rewind(cmp) function for each
  51 // specific type of list.  Since rewind(cmp) is the only non-inline function
  52 // in a sorter, that means you only need one of them per top-level container
  53 // type (ie. one for WvList and one for HashTable), not one per data type
  54 // you might store in such a container.
  55 template <class _type_,class _list_,class _iter_>
  56 class WvSorter : public WvSorterBase
  57 {
  58 public:
  59     typedef int (RealCompareFunc)(const _type_ *a, const _type_ *b);
  60     RealCompareFunc *cmp;
  61
  62     WvSorter(_list_ &_list, RealCompareFunc *_cmp)
  63         : WvSorterBase(&_list)
  64         { cmp = _cmp; }
  65     _type_ *ptr() const
  66         { return (_type_ *)(*lptr); }
  67
  68     // declare standard iterator accessors
  69     WvIterStuff(_type_);
  70
  71     void rewind()
  72       { WvSorterBase::rewind<_list_,_iter_>((CompareFunc *)cmp); }
  73 };
  74
  75
  76 // Note that this is largely the same as WvLink::SorterBase::rewind(),
  77 // except we iterate through a bunch of lists instead of a single one.
  78 template <class _list_,class _iter_>
  79 void WvSorterBase::rewind(CompareFunc *cmp)
  80 {
  81     int n, remaining;
  82
  83     if (array)
  84         deletev array;
  85     array = lptr = NULL;
  86
  87     _iter_ i(*(_list_ *)list);
  88
  89     // count the number of elements
  90     n = 0;
  91     for (i.rewind(); i.next(); )
  92         n++;
  93
  94     typedef void *VoidPtr;
  95     array = new VoidPtr[n+2];
  96     void **aptr = array;
  97
  98     *aptr++ = NULL; // initial link is NULL, to act like a normal iterator
  99
 100     for (remaining = n, i.rewind(); i.next() && remaining; remaining--)
 101     {
 102         *aptr = i.vptr();
 103         aptr++;
 104     }
 105
 106     // weird: list length changed?
 107     // (this can happen with "virtual" lists like ones from WvDirIter)
 108     if (remaining)
 109         n -= remaining;
 110
 111     *aptr = NULL;
 112
 113     // sort the array.  "Very nearly re-entrant" (unless the compare function
 114     // ends up being called recursively or something really weird...)
 115     CompareFunc *old_compare = actual_compare;
 116     actual_compare = cmp;
 117     qsort(array+1, n, sizeof(void *), magic_compare);
 118     actual_compare = old_compare;
 119
 120     lptr = array;
 121 }
 122
 123
 124 #endif // __WVSORTER_H