1list_sort 2 3 SYNOPSIS 4 Sort a list of item 5 6 USAGE 7 8 9 Int_Type indices = list_sort (List_Type list); % Form 1 10 list_sort (List_Type list; inplace); % Form 2 11 12 13 DESCRIPTION 14 The `list_sort' may be used to sort a list. By default, it 15 returns a permutation index array for the desired sort. If the 16 `inplace' qualifier is given, the sort will be in-place and no 17 index array will be returned. 18 19 QUALIFIERS 20 The following qualifiers may be used to modify the behavior of the 21 function: 22 23 24 dir=1 25 26 If the value of the `dir' qualifier is non-negative, the sort will 27 take place in an increasing order. If negative, the list will be 28 sorted in decreasing order. 29 30 31 cmp=&cmpfunc 32 33 The `cmp' qualifier specifies the function used to comparison 34 operation for two elements of an array. Its value must be a 35 reference to a function that accepts two arguments representing the 36 objects to be compared. It must return a positive integer, 0, or 37 a negative integer if the value of the first argument is greater 38 than, equal to, or less than the value of the second, respectively. 39 40 41 inplace[=1] 42 43 The inplace qualifier may be used to indicate if the list is to be 44 sorted in place. If the qualifier is present with no-value or a 45 non-zero value, the list will be sorted in place and no index array 46 will be returned. If not present, or present with a value of 0, the 47 list will not be modified, and an index array will be returned. 48 49 EXAMPLE 50 51 list = {1, 9, 3, 7}; 52 i = list_sort (list); 53 sorted_list = list[i]; 54 55 The above example creates a second list (`sorted_list') by 56 using the permutation index array to rearrange the objects in the 57 unsorted list. 58 59 60 list = {1, 9, 3, 7}; 61 list_sort (list; inplace); 62 63 In this example, the list is sorted in-place. 64 65 Consider a list of strings that are to be sorted in increasing 66 order of the number of bytes used by each string. For this, a custom 67 sort function is required: 68 69 private define cmpfunc (a, b) 70 { 71 return strbytelen(a) - strbytelen(b); 72 } 73 list = {"Here", "is", "a", "list", "of", "strings"}; 74 list_sort (list; inplace); 75 76 77 NOTES 78 Keep in mind that a list can contain a heterogeneous collection of 79 object where there is no predefined comparison operation. For 80 example, there may be no natural way to compare an integer to a 81 string. For a heterogeneous list, a comparison function must be 82 provided. 83 84 SEE ALSO 85 array_sort, rearrange 86 87-------------------------------------------------------------- 88 89heap_new 90 91 SYNOPSIS 92 Instantiate a heap data object 93 94 USAGE 95 Struct_Type h = new_heap (List_Type list) 96 97 DESCRIPTION 98 The `new_heap' function takes a List_Type object and 99 rearranges its elements to form a heap. A list rearranged to form a 100 heap has the property that `list[i] >= list[2*i+j]', where j=1 or 2, 101 and i is the list index (from 0). 102 103 Upon return, the elements of the list will be rearranged to have the 104 heap property and a new container object (the heap) will be 105 returned. It may be manipulated using the method calls described 106 below. 107 108 QUALIFIERS 109 110 dir=-1 111 112 The `dir' qualifier may be used to specify the direction of the 113 heap. The default (dir=-1) specifies a top-down ordering. A 114 bottom-up ordering corresponds to dir=1. 115 116 117 cmp=&cmpfunc 118 119 The `cmp' may be used to specify the function to be used when 120 comparing elements of the list. Its value must be a reference to a 121 function that takes two parameters and returns a positive integer if 122 the value of the first parameter is greater than the second, 0 if 123 they are equal, or a negative integer if the first is less than 124 the second. For example, if the list consists of structures with 125 fields called `lastname' and `firstname' that are to be 126 used for ordering, then the desired function would look something 127 like: 128 129 define cmpfunc (a, b) 130 { 131 variable c = strcmp (a.lastname, b.lastname); 132 if (c == 0) c = strcmp (a.firstname, b.firstname); 133 return c; 134 } 135 136 137 METHODS 138 .length() : Get the length to the heap 139 .add(obj) : Add a new object to the heap 140 .remove() : Remove the largest (for top-down) or smallest (for 141 bottom-up) item from the heap and return its value. 142 .peek() : Get the largest (top-down) or smallest(bottom-up) item 143 from the heap, but do not remove it. 144 145 Note that attempting to peek at or remove an item from an empty list 146 will result in an `IndexError' exception. 147 148 EXAMPLE 149 Suppose that merging two objects requires a time equal to the 150 combined length of the objects. For example, if the length of first 151 is A and that of the second is B, then the time to merge the two 152 will be A + B. What is the minimum amount of time it takes to merge 153 a list of N objects with lengths `{L_k}, k=0...N-1'? The 154 answer to this is very simple if a bottom-up heap is used. The idea 155 is to remove the two smallest objects from the heap, combine them 156 and then add the result back to the heap. Repeat this process until 157 the heap is empty. In the following, `list' is a list of the 158 lengths of the objects to be merged. 159 160 define compute_merge_time (list) 161 { 162 variable h = heap_new (list; dir=1); % bottom-up heap 163 variable a, b, c, t; 164 a = h.remove (); t = 0; 165 while (h.length()) 166 { 167 b = h.remove (); 168 c = a + b; 169 t += c; 170 h.add (c); 171 a = h.remove (); 172 } 173 return t; 174 } 175 176 177 NOTES 178 Generally speaking, a list will require the specification of a 179 comparison function unless the list consists solely of elements that 180 may be compared using the `>', `<', and `==' operators. 181 182 SEE ALSO 183 list_sort, list_new 184 185-------------------------------------------------------------- 186