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