1 /* $Header$ */
2 
3 /*
4  *   Copyright (c) 2000, 2002 Michael J. Roberts.  All Rights Reserved.
5  *
6  *   Please see the accompanying license file, LICENSE.TXT, for information
7  *   on using and copying this software.
8  */
9 /*
10 Name
11   vmsort.h - T3 VM quicksort implementation
12 Function
13 
14 Notes
15 
16 Modified
17   05/14/00 MJRoberts  - Creation
18 */
19 
20 #ifndef VMSORT_H
21 #define VMSORT_H
22 
23 #include <stdlib.h>
24 #include "t3std.h"
25 #include "vmglob.h"
26 #include "vmtype.h"
27 
28 
29 /* ------------------------------------------------------------------------ */
30 /*
31  *   Quicksort data interface
32  */
33 class CVmQSortData
34 {
35 public:
36     /*
37      *   sort a range; to sort the entire array, provide the indices of
38      *   the first and last elements of the array, inclusive
39      */
40     void sort(VMG_ size_t l, size_t r);
41 
42     /*
43      *   compare two elements by index - returns -1 if the first element
44      *   is less than the second, 0 if they're equal, 1 if the first is
45      *   greater than the second
46      */
47     virtual int compare(VMG_ size_t idx_a, size_t idx_b) = 0;
48 
49     /* exchange two elements */
50     virtual void exchange(VMG_ size_t idx_a, size_t idx_b) = 0;
51 };
52 
53 /* ------------------------------------------------------------------------ */
54 /*
55  *   Sorter implementation for sets of vm_val_t data
56  */
57 class CVmQSortVal: public CVmQSortData
58 {
59 public:
CVmQSortVal()60     CVmQSortVal()
61     {
62         compare_fn_.set_nil();
63         descending_ = FALSE;
64     }
65 
66     /* get/set an element */
67     virtual void get_ele(VMG_ size_t idx, vm_val_t *val) = 0;
68     virtual void set_ele(VMG_ size_t idx, const vm_val_t *val) = 0;
69 
70     /* compare */
71     virtual int compare(VMG_ size_t idx_a, size_t idx_b);
72 
73     /* exchange */
74     virtual void exchange(VMG_ size_t idx_a, size_t idx_b);
75 
76     /*
77      *   comparison function - if this is nil, we'll compare the values as
78      *   ordinary values
79      */
80     vm_val_t compare_fn_;
81 
82     /* flag: sort descending */
83     int descending_;
84 };
85 
86 #endif /* VMSORT_H */
87