WvStreams
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.
23class WvSorterBase
24{
25public:
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; }
35 { if (array) deletev array; }
36 bool next()
37 { return *(++lptr) != 0; }
38 bool cur()
39 { return *lptr != 0; }
40
41protected:
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.
55template <class _type_,class _list_,class _iter_>
56class WvSorter : public WvSorterBase
57{
58public:
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.
78template <class _list_,class _iter_>
79void 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