2 * Worldvisions Weaver Software:
3 * Copyright (C) 1997-2002 Net Integration Technologies, Inc.
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.
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.
26 typedef int (CompareFunc
)(const void *a
, const void *b
);
32 WvSorterBase(void *_list
)
33 { list
= _list
; array
= lptr
= NULL
; }
35 { if (array
) deletev array
; }
37 { return *(++lptr
) != 0; }
39 { return *lptr
!= 0; }
42 template <class _list_
,class _iter_
> void rewind(CompareFunc
*cmp
);
44 static int magic_compare(const void *_a
, const void *_b
);
45 static CompareFunc
*actual_compare
;
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
59 typedef int (RealCompareFunc
)(const _type_
*a
, const _type_
*b
);
62 WvSorter(_list_
&_list
, RealCompareFunc
*_cmp
)
63 : WvSorterBase(&_list
)
66 { return (_type_
*)(*lptr
); }
68 // declare standard iterator accessors
72 { WvSorterBase::rewind
<_list_
,_iter_
>((CompareFunc
*)cmp
); }
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
)
87 _iter_
i(*(_list_
*)list
);
89 // count the number of elements
91 for (i
.rewind(); i
.next(); )
94 typedef void *VoidPtr
;
95 array
= new VoidPtr
[n
+2];
98 *aptr
++ = NULL
; // initial link is NULL, to act like a normal iterator
100 for (remaining
= n
, i
.rewind(); i
.next() && remaining
; remaining
--)
106 // weird: list length changed?
107 // (this can happen with "virtual" lists like ones from WvDirIter)
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
;
124 #endif // __WVSORTER_H