123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128 |
- /*!
- Temelia - Algorithms implementation source file.
- Copyright (C) 2008, 2009 Ceata (http://ceata.org/proiecte/temelia).
- @author Dascalu Laurentiu, Bercaru Cristian
- This program is free software; you can redistribute it and
- modify it under the terms of the GNU General Public License
- as published by the Free Software Foundation; either version 3
- of the License, or (at your option) any later version.
- This program is distributed in the hope that it will be useful,
- but WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- GNU General Public License for more details.
- You should have received a copy of the GNU General Public License
- along with this program; if not, write to the Free Software
- Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
- */
- #include "include/algorithms.h"
- #include "include/common.h"
- #include <stdlib.h>
- void map(void *data, int size, void *key_at(void *data, int index),
- void iterate_function(void *key, void *context), void *context)
- {
- int i;
- LOGGER(
- "[map] data %p, size %d, key_at %p, iterate_function %p, context %p\n",
- data, size, key_at, iterate_function, context);
- _ASSERT(data, ==, NULL, NULL_POINTER,);
- _ASSERT(size, <=, 0, INVALID_INPUT,);
- _ASSERT(key_at, ==, NULL, NULL_POINTER,);
- _ASSERT(iterate_function, ==, NULL, NULL_POINTER,);
- /*
- * Iterates over each key, indexed from 0 to size - 1, of void *data
- * and call the delegate function with it and the context.
- */
- for (i = 0; i < size; i++)
- iterate_function(key_at(data, i), context);
- }
- void filter(void *data, int size, void *key_at(void *data, int index),
- int filter_function(void *key, void *context), void then_function(
- void *key, void *context), void else_function(void *key,
- void *context), void *filter_context, void *then_context,
- void *else_context)
- {
- int i;
- void *key;
- LOGGER(
- "[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",
- data, size, key_at, filter_function, then_context, else_context,
- filter_context, then_context, else_context);
- _ASSERT(data, ==, NULL, NULL_POINTER,);
- _ASSERT(size, <=, 0, INVALID_INPUT,);
- _ASSERT(key_at, ==, NULL, NULL_POINTER,);
- _ASSERT(filter_function, ==, NULL, NULL_POINTER,);
- _ASSERT(then_function, ==, NULL, NULL_POINTER,);
- /*
- * Iterate over the collection and apply the filter function
- * for each key; if the filter returns a nonzero value
- * then call the then_function with the key and context, else
- * if the else_function exists then call it with the key and context.
- */
- for (i = 0; i < size; i++)
- {
- key = key_at(data, i);
- if (filter_function(key, filter_context))
- then_function(key, then_context);
- else
- {
- if ((void *) else_function != NULL)
- else_function(key, else_context);
- }
- }
- }
- int binary_search(void *data, int size, void *key, void *key_at(void *data,
- int index), int compare(void *x, void *y, void *context), void *context)
- {
- int inf, sup, mid, aux;
- LOGGER(
- "[map] data %p, size %d, key %p, key_at %p, compare %p, context %p\n",
- data, size, key, key_at, compare, context);
- _ASSERT(data, ==, NULL, NULL_POINTER, -1);
- _ASSERT(size, <=, 0, INVALID_INPUT, -1);
- _ASSERT(key_at, ==, NULL, NULL_POINTER, -1);
- _ASSERT(compare, ==, NULL, NULL_POINTER, -1);
- inf = 0;
- sup = size - 1;
- while (inf <= sup)
- {
- mid = inf + ((sup - inf) / 2);
- /*
- * Compare the given key with the key in the middle of void *,
- * delimited by inf (infimum) and sup (supremum).
- * - if the result is 0, then the key was found.
- * - else if the result is greater then 0, then the key is in the upper
- * interval
- * - else the key is in the lower interval
- */
- aux = compare(key_at(data, mid), key, context);
- if (aux == 0)
- return mid;
- if (aux > 0)
- sup = mid - 1;
- else
- inf = mid + 1;
- }
- return -1;
- }
|