Implementations of the C++ Standard Library in... C. Can creatures armed without wings engage in flight?
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

algorithm.h 16KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347
  1. /**
  2. * algorithm.h of the C STL.
  3. *
  4. * Copyright (C) 2020 Luiserebii
  5. *
  6. * This program is free software: you can redistribute it and/or modify
  7. * it under the terms of the GNU General Public License as published by
  8. * the Free Software Foundation, either version 3 of the License, or
  9. * (at your option) any later version.
  10. *
  11. * This program is distributed in the hope that it will be useful,
  12. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  14. * GNU General Public License for more details.
  15. *
  16. * You should have received a copy of the GNU General Public License
  17. * along with this program. If not, see <https://www.gnu.org/licenses/>.
  18. */
  19. #ifndef CSTL_ALGORITHM_H
  20. #define CSTL_ALGORITHM_H
  21. /**
  22. * algorithm_copy(type, begin, end, dest, res)
  23. *
  24. * Takes a pointer type as the first parameter, which is to be substituted as a generic for the values
  25. * of begin and dest. Essentially, the range [begin, end) is copied into dest. The new end of the range
  26. * beginning with dest is copied into res.
  27. *
  28. * Ex: algorithm_copy(int*, months, months + 12, words, newWordsend)
  29. */
  30. #define algorithm_copy(type, begin, end, dest, res) \
  31. { \
  32. res = dest; \
  33. for(const type _alg_copy_it = begin; _alg_copy_it != end; *res++ = *_alg_copy_it++) \
  34. ; \
  35. }
  36. /**
  37. * algorithm_min_copy(type, begin, end, dest)
  38. *
  39. * Takes a pointer type as the first parameter, which is to be substituted as a generic for the values
  40. * of begin and dest. Essentially, the range [begin, end) is copied into dest.
  41. *
  42. * Ex: algorithm_copy(int*, months, months + 12, words)
  43. */
  44. #define algorithm_min_copy(type, begin, end, dest) \
  45. { \
  46. const type _alg_copy_it = begin; \
  47. for(type _alg_copy_dest = dest; _alg_copy_it != end; *_alg_copy_dest++ = *_alg_copy_it++) \
  48. ; \
  49. }
  50. /**
  51. * algorithm_fill(type, begin, end, val)
  52. *
  53. * Takes a pointer type as the first parameter, which is to be substituted as a generic for the value
  54. * of begin. Essentially, the value val is copied into the range [begin, end).
  55. *
  56. * Ex: algorithm_fill(int*, months, months + 12, words)
  57. */
  58. #define algorithm_fill(type, begin, end, val) \
  59. { \
  60. for(type _alg_copy_it = begin; _alg_copy_it != end; *_alg_copy_it++ = val) \
  61. ; \
  62. }
  63. /**
  64. * algorithm_find(begin, end, val, res)
  65. *
  66. * Searches through [begin, end) for val. Returns a pointer to the found value through
  67. * res, or end if nothing found.
  68. *
  69. * Ex: algorithm_find(nums, nums + sz, 100, first100);
  70. */
  71. #define algorithm_find(begin, end, val, res) \
  72. { \
  73. res = begin; \
  74. while(res != end && *res != val) { \
  75. ++res; \
  76. } \
  77. }
  78. /**
  79. * algorithm_find_last(begin, end, val, res)
  80. *
  81. * Searches through [begin, end) for val. Returns a pointer to the last found value through
  82. * res, or end if nothing found.
  83. *
  84. * Ex: algorithm_find_last(nums, nums + sz, 100, last100);
  85. */
  86. #define algorithm_find_last(begin, end, val, res) \
  87. { \
  88. res = end - 1; \
  89. while(res != begin - 1 && *res != val) { \
  90. --res; \
  91. } \
  92. }
  93. /**
  94. * algorithm_equal(type, begin, end, begin2, res)
  95. *
  96. * Searches and compares [begin, end) to [begin2, x), where x is end - begin.
  97. * Returns a boolean value into res representing the equivalence of the range.
  98. *
  99. * Ex: algorithm_equal(char*, word, word + sz, word2, res);
  100. */
  101. #define algorithm_equal(type, begin, end, begin2, res) \
  102. { \
  103. res = 1; \
  104. const type _alg_eq_b = begin; \
  105. for(const type _alg_eq_b2 = begin2; _alg_eq_b != end; ++_alg_eq_b, ++_alg_eq_b2) { \
  106. if(*_alg_eq_b != *_alg_eq_b2) { \
  107. res = 0; \
  108. break; \
  109. } \
  110. } \
  111. }
  112. /**
  113. * algorithm_max(a, b)
  114. *
  115. * Returns the greater of the two values by resolving into an expression.
  116. */
  117. #define algorithm_max(a, b) (a > b) ? a : b
  118. /**
  119. * algorithm_min(a, b)
  120. *
  121. * Returns the lesser of the two values by resolving into an expression.
  122. */
  123. #define algorithm_min(a, b) (a < b) ? a : b
  124. /**
  125. * algorithm_count(type, begin, end, val, res)
  126. *
  127. * Returns the number of times val appears in [begin, end) into res.
  128. *
  129. * Ex: algorithm_count(int*, nums, nums + sz, 10, res);
  130. */
  131. #define algorithm_count(type, begin, end, val, res) \
  132. { \
  133. res = 0; \
  134. for(const type _alg_count_it = begin; _alg_count_it != end; ++_alg_count_it) { \
  135. if(*_alg_count_it == val) { \
  136. ++res; \
  137. } \
  138. } \
  139. }
  140. /**
  141. * algorithm_transform(type, begin, end, dest, f)
  142. *
  143. * Apply the unary function f to the range [begin, end), storing the result
  144. * in a range [dest, end - begin).
  145. *
  146. * Ex: algorithm_transform(int*, nums, nums + sz, doubled, doubleNum);
  147. * where doubleNum is a function (int doubleNum(int x) { returns x * 2; })
  148. */
  149. #define algorithm_transform(type, begin, end, dest, f) \
  150. { \
  151. const type _alg_tr_it = begin; \
  152. type _alg_tr_dest = dest; \
  153. while(_alg_tr_it != end) { \
  154. *_alg_tr_dest++ = f(*_alg_tr_it++); \
  155. } \
  156. }
  157. /**
  158. * algorithm_accumulate(type, begin, end, res)
  159. *
  160. * Add all values found in the range [begin, end) and return in res.
  161. *
  162. * Aside from storing the result of the computation, the initial value of res
  163. * will be used within the sum. Typically, res should therefore be 0.
  164. *
  165. * Ex: algorithm_accumulate(int*, nums, nums + sz, sum);
  166. */
  167. #define algorithm_accumulate(type, begin, end, res) \
  168. { \
  169. const type _alg_acc_it = begin; \
  170. while(_alg_acc_it != end) { \
  171. res += *_alg_acc_it++; \
  172. } \
  173. }
  174. /**
  175. * algorithm_remove_copy_if(type, begin, end, dest, f)
  176. *
  177. * Copies all values in the range [begin, end) to dest which
  178. * do not match the predicate f passed.
  179. *
  180. * Alternatively, this function removes any elements which match
  181. * the predicate and places this new range in dest.
  182. *
  183. * Ex: algorithm_remove_copy_if(char*, a, a + sz, b, islower)
  184. */
  185. #define algorithm_remove_copy_if(type, begin, end, dest, f) \
  186. { \
  187. type _alg_cpif_dest = dest; \
  188. for(const type _alg_cpif_it = begin; _alg_cpif_it != end; ++_alg_cpif_it) { \
  189. if(!f(*_alg_cpif_it)) { \
  190. *_alg_cpif_dest++ = *_alg_cpif_it; \
  191. } \
  192. } \
  193. }
  194. /**
  195. * algorithm_search(type, begin, end, begin2, end2, res)
  196. *
  197. * Searches through the range [begin, end) for [begin2, end2).
  198. * Returns a pointer to the first element found that matches this sequence
  199. * through res, or end if nothing is found.
  200. *
  201. * Ex: algorithm_search(char*, charList, charList + cLsz, word, word + wsz, res);
  202. */
  203. #define algorithm_search(type, begin, end, begin2, end2, res) \
  204. { \
  205. /* Declaring local label */ \
  206. __label__ _algorithm_search_end; \
  207. \
  208. for(const type _alg_search_b1 = begin; _alg_search_b1 != end; ++_alg_search_b1) { \
  209. /* Idea behind continue; only add names below if we snag an equal initial val*/ \
  210. if(*_alg_search_b1 != *begin2) { \
  211. continue; \
  212. } \
  213. const type _alg_search_it1 = _alg_search_b1; \
  214. const type _alg_search_it2 = begin2; \
  215. for(; _alg_search_it2 != end2 && *_alg_search_it1 == *_alg_search_it2; \
  216. ++_alg_search_it1, ++_alg_search_it2) { \
  217. if(_alg_search_it1 == end) { \
  218. res = end; \
  219. goto _algorithm_search_end; \
  220. } \
  221. } \
  222. if(_alg_search_it2 == end2) { \
  223. res = _alg_search_b1; \
  224. goto _algorithm_search_end; \
  225. } \
  226. } \
  227. res = end; \
  228. _algorithm_search_end:; \
  229. }
  230. /**
  231. * algorithm_find_if(begin, end, f, res)
  232. *
  233. * Searches through [begin, end) for the first element in which the
  234. * predicate f returns true. Returns a pointer to the found value through
  235. * res, or end if nothing found.
  236. *
  237. * Ex: algorithm_find(nums, nums + sz, isEven, res);
  238. */
  239. #define algorithm_find_if(begin, end, f, res) \
  240. { \
  241. res = begin; \
  242. while(res != end && !f(*res)) { \
  243. ++res; \
  244. } \
  245. }
  246. /**
  247. * algorithm_remove(type, begin, end, val, res)
  248. *
  249. * Iterates through [begin, end), removing any elements equal to val.
  250. * Elements are not truly removed; the function simply does not set elements
  251. * equal to val in the range [begin, res), where res is a pointer to the
  252. * new end of the range.
  253. *
  254. * This function is convenient when paired with vector's erase, forming an idiom.
  255. *
  256. * Ex: algorithm_remove(int*, nums, nums + sz, 10, res);
  257. */
  258. #define algorithm_remove(type, begin, end, val, res) \
  259. { \
  260. res = begin; \
  261. for(type _alg_remove_it = begin; _alg_remove_it != end; ++_alg_remove_it) { \
  262. if(*_alg_remove_it != val) { \
  263. *res++ = *_alg_remove_it; \
  264. } \
  265. } \
  266. }
  267. /**
  268. * algorithm_remove_if(type, begin, end, f, res)
  269. *
  270. * Iterates through [begin, end), removing any elements which return true when
  271. * passed to the predicate f.
  272. *
  273. * Elements are not truly removed; the function simply does not set elements
  274. * which return true in the range [begin, res), where res is a pointer to the
  275. * new end of the range.
  276. *
  277. * This function is convenient when paired with vector's erase, forming an idiom.
  278. *
  279. * Ex: algorithm_remove_if(int*, nums, nums + sz, isEven, res);
  280. */
  281. #define algorithm_remove_if(type, begin, end, f, res) \
  282. { \
  283. res = begin; \
  284. for(type _alg_remove_it = begin; _alg_remove_it != end; ++_alg_remove_it) { \
  285. if(!f(*_alg_remove_it)) { \
  286. *res++ = *_alg_remove_it; \
  287. } \
  288. } \
  289. }
  290. /**
  291. * algorithm_remove_copy(type, begin, end, dest, val)
  292. *
  293. * Copies all values in the range [begin, end) to dest which
  294. * do not match the value val passed.
  295. *
  296. * Alternatively, this function removes any elements which match
  297. * the value and places this new range in dest.
  298. *
  299. * Ex: algorithm_remove_copy(int*, nums, nums + sz, newNums, 100);
  300. */
  301. #define algorithm_remove_copy(type, begin, end, dest, val) \
  302. { \
  303. type _alg_rmcp_dest = dest; \
  304. for(const type _alg_rmcp_it = begin; _alg_rmcp_it != end; ++_alg_rmcp_it) { \
  305. if(*_alg_rmcp_it != val) { \
  306. *_alg_rmcp_dest++ = *_alg_rmcp_it; \
  307. } \
  308. } \
  309. }
  310. /**
  311. * algorithm_partition(type, begin, end, ftype, f, res)
  312. *
  313. * Sorts the range [begin, end) where all elements for which the predicate f returns
  314. * true are moved to the front of the range. The end of this parititioned range is
  315. * returned via res. ftype represents the type of the argument taken by the unary
  316. * predicate f.
  317. *
  318. * Ex: algorithm_partition(int*, nums, nums + sz, int, isEven, ptend);
  319. */
  320. #define algorithm_partition(type, begin, end, predtype, f, res) \
  321. res = begin; \
  322. for(type _alg_prt_it = begin; _alg_prt_it != end; ++_alg_prt_it) { \
  323. if(!f(*_alg_prt_it)) { \
  324. predtype _alg_prt_val = *res; \
  325. *res++ = *_alg_prt_it; \
  326. *_alg_prt_it = _alg_prt_val; \
  327. } \
  328. }
  329. #endif