algorithms.c 3.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128
  1. /*!
  2. Temelia - Algorithms implementation source file.
  3. Copyright (C) 2008, 2009 Ceata (http://ceata.org/proiecte/temelia).
  4. @author Dascalu Laurentiu, Bercaru Cristian
  5. This program is free software; you can redistribute it and
  6. modify it under the terms of the GNU General Public License
  7. as published by the Free Software Foundation; either version 3
  8. of the License, or (at your option) any later version.
  9. This program is distributed in the hope that it will be useful,
  10. but WITHOUT ANY WARRANTY; without even the implied warranty of
  11. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  12. GNU General Public License for more details.
  13. You should have received a copy of the GNU General Public License
  14. along with this program; if not, write to the Free Software
  15. Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  16. */
  17. #include "include/algorithms.h"
  18. #include "include/common.h"
  19. #include <stdlib.h>
  20. void map(void *data, int size, void *key_at(void *data, int index),
  21. void iterate_function(void *key, void *context), void *context)
  22. {
  23. int i;
  24. LOGGER(
  25. "[map] data %p, size %d, key_at %p, iterate_function %p, context %p\n",
  26. data, size, key_at, iterate_function, context);
  27. _ASSERT(data, ==, NULL, NULL_POINTER,);
  28. _ASSERT(size, <=, 0, INVALID_INPUT,);
  29. _ASSERT(key_at, ==, NULL, NULL_POINTER,);
  30. _ASSERT(iterate_function, ==, NULL, NULL_POINTER,);
  31. /*
  32. * Iterates over each key, indexed from 0 to size - 1, of void *data
  33. * and call the delegate function with it and the context.
  34. */
  35. for (i = 0; i < size; i++)
  36. iterate_function(key_at(data, i), context);
  37. }
  38. void filter(void *data, int size, void *key_at(void *data, int index),
  39. int filter_function(void *key, void *context), void then_function(
  40. void *key, void *context), void else_function(void *key,
  41. void *context), void *filter_context, void *then_context,
  42. void *else_context)
  43. {
  44. int i;
  45. void *key;
  46. LOGGER(
  47. "[filter] data %p, size %d, key_at %p, filter_function %p, then_function %p, else_function %p, filter_context %p, then_context %p, else_context %p\n",
  48. data, size, key_at, filter_function, then_context, else_context,
  49. filter_context, then_context, else_context);
  50. _ASSERT(data, ==, NULL, NULL_POINTER,);
  51. _ASSERT(size, <=, 0, INVALID_INPUT,);
  52. _ASSERT(key_at, ==, NULL, NULL_POINTER,);
  53. _ASSERT(filter_function, ==, NULL, NULL_POINTER,);
  54. _ASSERT(then_function, ==, NULL, NULL_POINTER,);
  55. /*
  56. * Iterate over the collection and apply the filter function
  57. * for each key; if the filter returns a nonzero value
  58. * then call the then_function with the key and context, else
  59. * if the else_function exists then call it with the key and context.
  60. */
  61. for (i = 0; i < size; i++)
  62. {
  63. key = key_at(data, i);
  64. if (filter_function(key, filter_context))
  65. then_function(key, then_context);
  66. else
  67. {
  68. if ((void *) else_function != NULL)
  69. else_function(key, else_context);
  70. }
  71. }
  72. }
  73. int binary_search(void *data, int size, void *key, void *key_at(void *data,
  74. int index), int compare(void *x, void *y, void *context), void *context)
  75. {
  76. int inf, sup, mid, aux;
  77. LOGGER(
  78. "[map] data %p, size %d, key %p, key_at %p, compare %p, context %p\n",
  79. data, size, key, key_at, compare, context);
  80. _ASSERT(data, ==, NULL, NULL_POINTER, -1);
  81. _ASSERT(size, <=, 0, INVALID_INPUT, -1);
  82. _ASSERT(key_at, ==, NULL, NULL_POINTER, -1);
  83. _ASSERT(compare, ==, NULL, NULL_POINTER, -1);
  84. inf = 0;
  85. sup = size - 1;
  86. while (inf <= sup)
  87. {
  88. mid = inf + ((sup - inf) / 2);
  89. /*
  90. * Compare the given key with the key in the middle of void *,
  91. * delimited by inf (infimum) and sup (supremum).
  92. * - if the result is 0, then the key was found.
  93. * - else if the result is greater then 0, then the key is in the upper
  94. * interval
  95. * - else the key is in the lower interval
  96. */
  97. aux = compare(key_at(data, mid), key, context);
  98. if (aux == 0)
  99. return mid;
  100. if (aux > 0)
  101. sup = mid - 1;
  102. else
  103. inf = mid + 1;
  104. }
  105. return -1;
  106. }