1% Copyright (C) 2012-2017,2018 John E. Davis 2% 3% This file is part of the S-Lang Library and may be distributed under the 4% terms of the GNU General Public License. See the file COPYING for 5% more information. 6%--------------------------------------------------------------------------- 7require ("arrayfuns"); 8 9private define user_sort_cmp (cd, i, j) 10{ 11 variable list = cd.list; 12 return (@cd.cmp) (list[i], list[j]); 13} 14 15private define default_sort_cmp (list, i, j) 16{ 17 if (list[i] > list[j]) return 1; 18 if (list[i] == list[j]) return 0; 19 return -1; 20} 21 22 23define list_sort (list) 24{ 25 variable dir = qualifier ("dir", 1); 26 variable cmp = qualifier ("cmp"); 27 28 variable n = length (list); 29 variable i; 30 if (cmp == NULL) 31 i = array_sort (list, &default_sort_cmp, n; dir=dir); 32 else 33 i = array_sort (struct {list=list, cmp=cmp}, &user_sort_cmp, n; dir=dir); 34 35 variable inplace = qualifier ("inplace", 0); 36 if (inplace == 0) 37 return i; 38 39 rearrange (list, i); 40} 41 42% Heap Implementation 43 44private define heap_length (h) 45{ 46 return length (h.list); 47} 48 49private define upheap (list, k, cmp) 50{ 51 variable obj = list[k]; 52 variable k2 = (k-1)/2; 53 while (k && (@cmp)(obj,list[k2]) > 0) 54 { 55 list[k] = list[k2]; 56 k = k2; 57 k2 = (k-1)/2; 58 } 59 list[k] = obj; 60} 61 62private define downheap (list, k, cmp) 63{ 64 variable obj = list[k]; 65 variable n = length(list), n2 = n/2; 66 n--; 67% 0 68% 1 2 69% 3 4 5 6 70% 7 8 9 10 11 12 13 14 71 while (k < n2) 72 { 73 variable j = 2*k + 1; 74 if ((j < n) 75 && ((@cmp)(list[j], list[j+1]) < 0)) 76 j++; 77 if ((@cmp)(obj, list[j]) >= 0) 78 break; 79 list[k] = list[j]; 80 k = j; 81 } 82 list[k] = obj; 83} 84 85 86private define heap_add (h, obj) 87{ 88 variable list = h.list; 89 list_append (list, obj); 90 upheap (list, length(list)-1, h.cmp); 91} 92 93private define heap_pop (h) 94{ 95 variable list = h.list; 96 variable obj = list[0]; 97 variable last = list_pop(list, -1); 98 if (length (list)) 99 { 100 list[0] = last; 101 downheap (list, 0, h.cmp); 102 } 103 return obj; 104} 105 106private define heap_peek (h) 107{ 108 return h.list[0]; 109} 110 111private define default_heap_cmp (a, b) 112{ 113 if (a > b) return 1; 114 if (a < b) return -1; 115 return 0; 116} 117 118private define default_heap_cmp_rev (a, b) 119{ 120 if (a > b) return -1; 121 if (a < b) return 1; 122 return 0; 123} 124 125 126define heap_new () 127{ 128 if (_NARGS == 0) 129 usage (` 130h = new_heap (list; cmp=&cmpfun, dir=val); 131len = h.length(); 132h.add (item); 133top = h.remove(); 134top = h.peek (); 135` 136 ); 137 138 variable list = (); 139 variable cmp = qualifier ("cmp"); 140 variable dir = qualifier ("dir", -1); 141 142 % The conventional interpretation of a heap is that the largest 143 % element is at the root, and smaller ones below. For this reason, 144 % dir=-1 (ascending order) is the default for sorting. 145 list_sort (list; cmp=cmp, dir=dir, inplace); 146 147 if (cmp == NULL) 148 { 149 cmp = (dir <= 0) ? &default_heap_cmp : &default_heap_cmp_rev; 150 } 151 152 variable h = struct 153 { 154 list = list, 155 cmp = cmp, 156 length = &heap_length, 157 add = &heap_add, 158 remove = &heap_pop, 159 peek = &heap_peek, 160 }; 161 return h; 162} 163