WvStreams
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.
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
deletev
#define deletev
Remplacement for delete[].
Definition: delete.h:129
WvSorter
Definition: wvsorter.h:56
WvSorterBase
Definition: wvsorter.h:23