1 /* 2 PSPP - a program for statistical analysis. 3 Copyright (C) 2017 Free Software Foundation, Inc. 4 5 This program is free software: you can redistribute it and/or modify 6 it under the terms of the GNU General Public License as published by 7 the Free Software Foundation, either version 3 of the License, or 8 (at your option) any later version. 9 10 This program is distributed in the hope that it will be useful, 11 but WITHOUT ANY WARRANTY; without even the implied warranty of 12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13 GNU General Public License for more details. 14 15 You should have received a copy of the GNU General Public License 16 along with this program. If not, see <http://www.gnu.org/licenses/>. 17 */ 18 19 #ifndef ALGORITHM_H 20 #define ALGORITHM_H 1 21 22 #include <stddef.h> 23 #include <stdbool.h> 24 25 /* Compares A and B, given auxiliary data AUX, and returns a 26 strcmp()-type result. */ 27 28 typedef int algo_compare_func (const void *a, const void *b, const void *aux); 29 30 /* Tests a predicate on DATA, given auxiliary data AUX */ 31 typedef bool algo_predicate_func (const void *data, const void *aux); 32 33 /* Returns a random number in the range 0 through MAX exclusive, 34 given auxiliary data AUX. */ 35 typedef unsigned algo_random_func (unsigned max, const void *aux); 36 37 /* A generally suitable random function. */ 38 algo_random_func algo_default_random; 39 40 /* Finds an element in ARRAY, which contains COUNT elements of 41 SIZE bytes each, using COMPARE for comparisons. Returns the 42 first element in ARRAY that matches TARGET, or a null pointer 43 on failure. AUX is passed to each comparison as auxiliary 44 data. */ 45 void *find (const void *array, size_t count, size_t size, 46 const void *target, 47 algo_compare_func *compare, const void *aux); 48 49 /* Counts and return the number of elements in ARRAY, which 50 contains COUNT elements of SIZE bytes each, which are equal to 51 ELEMENT as compared with COMPARE. AUX is passed as auxiliary 52 data to COMPARE. */ 53 size_t count_equal (const void *array, size_t count, size_t size, 54 const void *element, 55 algo_compare_func *compare, const void *aux); 56 57 /* Counts and return the number of elements in ARRAY, which 58 contains COUNT elements of SIZE bytes each, for which 59 PREDICATE returns true. AUX is passed as auxiliary data to 60 PREDICATE. */ 61 size_t count_if (const void *array, size_t count, size_t size, 62 algo_predicate_func *predicate, const void *aux); 63 64 /* Sorts ARRAY, which contains COUNT elements of SIZE bytes each, 65 using COMPARE for comparisons. AUX is passed to each 66 comparison as auxiliary data. */ 67 void sort (void *array, size_t count, size_t size, 68 algo_compare_func *compare, const void *aux); 69 70 /* Tests whether ARRAY, which contains COUNT elements of SIZE 71 bytes each, is sorted in order according to COMPARE. AUX is 72 passed to COMPARE as auxiliary data. */ 73 bool is_sorted (const void *array, size_t count, size_t size, 74 algo_compare_func *compare, const void *aux); 75 76 /* Makes the elements in ARRAY unique, by moving up duplicates, 77 and returns the new number of elements in the array. Sorted 78 arrays only. Arguments same as for sort() above. */ 79 size_t unique (void *array, size_t count, size_t size, 80 algo_compare_func *compare, const void *aux); 81 82 /* Helper function that calls sort(), then unique(). */ 83 size_t sort_unique (void *array, size_t count, size_t size, 84 algo_compare_func *compare, const void *aux); 85 86 /* Reorders ARRAY, which contains COUNT elements of SIZE bytes 87 each, so that the elements for which PREDICATE returns true 88 precede those for which PREDICATE returns false. AUX is passed 89 as auxiliary data to PREDICATE. Returns the number of 90 elements for which PREDICATE returns true. Not stable. */ 91 size_t partition (void *array, size_t count, size_t size, 92 algo_predicate_func *predicate, const void *aux); 93 94 /* Checks whether ARRAY, which contains COUNT elements of SIZE 95 bytes each, is partitioned such that PREDICATE returns true 96 for the first TRUE_CNT elements and zero for the remaining 97 elements. AUX is passed as auxiliary data to PREDICATE. */ 98 bool is_partitioned (const void *array, size_t count, size_t size, 99 size_t true_cnt, 100 algo_predicate_func *predicate, const void *aux); 101 102 /* Randomly reorders ARRAY, which contains COUNT elements of SIZE 103 bytes each. Uses RANDOM as a source of random data, passing 104 AUX as the auxiliary data. RANDOM may be null to use a 105 default random source. */ 106 void random_shuffle (void *array, size_t count, size_t size, 107 algo_random_func *random, const void *aux); 108 109 /* Copies the COUNT elements of SIZE bytes each from ARRAY to 110 RESULT, except that elements for which PREDICATE is false are 111 not copied. Returns the number of elements copied. AUX is 112 passed to PREDICATE as auxiliary data. */ 113 size_t copy_if (const void *array, size_t count, size_t size, 114 void *result, 115 algo_predicate_func *predicate, const void *aux); 116 117 /* Removes N elements starting at IDX from ARRAY, which consists 118 of COUNT elements of SIZE bytes each, by shifting the elements 119 following them, if any, into its position. */ 120 void remove_range (void *array, size_t count, size_t size, 121 size_t idx, size_t n); 122 123 /* Removes element IDX from ARRAY, which consists of COUNT 124 elements of SIZE bytes each, by shifting the elements 125 following it, if any, into its position. */ 126 void remove_element (void *array, size_t count, size_t size, 127 size_t idx); 128 129 /* Makes room for N elements starting at IDX in ARRAY, which 130 initially consists of COUNT elements of SIZE bytes each, by 131 shifting elements IDX...COUNT (exclusive) to the right by N 132 positions. */ 133 void insert_range (void *array, size_t count, size_t size, 134 size_t idx, size_t n); 135 136 /* Makes room for a new element at IDX in ARRAY, which initially 137 consists of COUNT elements of SIZE bytes each, by shifting 138 elements IDX...COUNT (exclusive) to the right by one 139 position. */ 140 void insert_element (void *array, size_t count, size_t size, 141 size_t idx); 142 143 /* Moves an element in ARRAY, which consists of COUNT elements of 144 SIZE bytes each, from OLD_IDX to NEW_IDX, shifting around 145 other elements as needed. Runs in O(abs(OLD_IDX - NEW_IDX)) 146 time. */ 147 void move_element (void *array, size_t count, size_t size, 148 size_t old_idx, size_t new_idx); 149 150 /* Moves N elements in ARRAY starting at OLD_IDX, which consists 151 of COUNT elements of SIZE bytes each, so that they now start 152 at NEW_IDX, shifting around other elements as needed. */ 153 void move_range (void *array, size_t count, size_t size, 154 size_t old_idx, size_t new_idx, size_t n); 155 156 /* Removes elements equal to ELEMENT from ARRAY, which consists 157 of COUNT elements of SIZE bytes each. Returns the number of 158 remaining elements. AUX is passed to COMPARE as auxiliary 159 data. */ 160 size_t remove_equal (void *array, size_t count, size_t size, 161 void *element, 162 algo_compare_func *compare, const void *aux); 163 164 /* Copies the COUNT elements of SIZE bytes each from ARRAY to 165 RESULT, except that elements for which PREDICATE is true are 166 not copied. Returns the number of elements copied. AUX is 167 passed to PREDICATE as auxiliary data. */ 168 size_t remove_copy_if (const void *array, size_t count, size_t size, 169 void *result, 170 algo_predicate_func *predicate, const void *aux); 171 172 /* Searches ARRAY, which contains COUNT elements of SIZE bytes 173 each, for VALUE, using a binary search. ARRAY must ordered 174 according to COMPARE. AUX is passed to COMPARE as auxiliary 175 data. */ 176 void *binary_search (const void *array, size_t count, size_t size, 177 void *value, 178 algo_compare_func *compare, const void *aux); 179 180 /* Lexicographically compares ARRAY1, which contains COUNT1 181 elements of SIZE bytes each, to ARRAY2, which contains COUNT2 182 elements of SIZE bytes, according to COMPARE. Returns a 183 strcmp()-type result. AUX is passed to COMPARE as auxiliary 184 data. */ 185 int lexicographical_compare_3way (const void *array1, size_t count1, 186 const void *array2, size_t count2, 187 size_t size, 188 algo_compare_func *compare, const void *aux); 189 190 /* Computes the generalized set difference, ARRAY1 minus ARRAY2, 191 into RESULT, and returns the number of elements written to 192 RESULT. If a value appears M times in ARRAY1 and N times in 193 ARRAY2, then it will appear max(M - N, 0) in RESULT. ARRAY1 194 and ARRAY2 must be sorted, and RESULT is sorted and stable. 195 ARRAY1 consists of COUNT1 elements, ARRAY2 of COUNT2 elements, 196 each SIZE bytes. AUX is passed to COMPARE as auxiliary 197 data. */ 198 size_t set_difference (const void *array1, size_t count1, 199 const void *array2, size_t count2, 200 size_t size, 201 void *result, 202 algo_compare_func *compare, const void *aux); 203 204 /* Finds the first pair of adjacent equal elements in ARRAY, 205 which has COUNT elements of SIZE bytes. Returns the first 206 element in ARRAY such that COMPARE returns true when it and 207 its successor element are compared. AUX is passed to COMPARE 208 as auxiliary data. */ 209 void *adjacent_find_equal (const void *array, size_t count, size_t size, 210 algo_compare_func *compare, const void *aux); 211 212 /* ARRAY contains COUNT elements of SIZE bytes each. Initially 213 the first COUNT - 1 elements of these form a heap, followed by 214 a single element not part of the heap. This function adds the 215 final element, forming a heap of COUNT elements in ARRAY. 216 Uses COMPARE to compare elements, passing AUX as auxiliary 217 data. */ 218 void push_heap (void *array, size_t count, size_t size, 219 algo_compare_func *compare, const void *aux); 220 221 /* ARRAY contains COUNT elements of SIZE bytes each. Initially 222 all COUNT elements form a heap. This function moves the 223 largest element in the heap to the final position in ARRAY and 224 reforms a heap of the remaining COUNT - 1 elements at the 225 beginning of ARRAY. Uses COMPARE to compare elements, passing 226 AUX as auxiliary data. */ 227 void pop_heap (void *array, size_t count, size_t size, 228 algo_compare_func *compare, const void *aux); 229 230 /* Turns ARRAY, which contains COUNT elements of SIZE bytes, into 231 a heap. Uses COMPARE to compare elements, passing AUX as 232 auxiliary data. */ 233 void make_heap (void *array, size_t count, size_t size, 234 algo_compare_func *compare, const void *aux); 235 236 /* ARRAY contains COUNT elements of SIZE bytes each. Initially 237 all COUNT elements form a heap. This function turns the heap 238 into a fully sorted array. Uses COMPARE to compare elements, 239 passing AUX as auxiliary data. */ 240 void sort_heap (void *array, size_t count, size_t size, 241 algo_compare_func *compare, const void *aux); 242 243 /* ARRAY contains COUNT elements of SIZE bytes each. This 244 function tests whether ARRAY is a heap and returns true if so, 245 false otherwise. Uses COMPARE to compare elements, passing 246 AUX as auxiliary data. */ 247 bool is_heap (const void *array, size_t count, size_t size, 248 algo_compare_func *compare, const void *aux); 249 250 /* Reverses the order of ARRAY, which contains COUNT elements of SIZE bytes 251 each. */ 252 void reverse_array (void *array, size_t count, size_t size); 253 254 #endif /* algorithm.h */ 255