Mercurial > hg > ucx / changeset

--- a/src/list.c	Thu Nov 07 10:43:31 2019 +0100
+++ b/src/list.c	Sun Nov 24 17:57:25 2019 +0100
@@ -28,11 +28,11 @@
 
 #include "ucx/list.h"
 
-UcxList *ucx_list_clone(UcxList *l, copy_func fnc, void *data) {
+UcxList *ucx_list_clone(const UcxList *l, copy_func fnc, void *data) {
     return ucx_list_clone_a(ucx_default_allocator(), l, fnc, data);
 }
 
-UcxList *ucx_list_clone_a(UcxAllocator *alloc, UcxList *l,
+UcxList *ucx_list_clone_a(UcxAllocator *alloc, const UcxList *l,
         copy_func fnc, void *data) {
     UcxList *ret = NULL;
     while (l) {
@@ -172,7 +172,8 @@
     return (UcxList*)(index == 0 ? e : NULL);
 }
 
-ssize_t ucx_list_find(UcxList *l, void *elem, cmp_func fnc, void *cmpdata) {
+ssize_t ucx_list_find(const UcxList *l, void *elem,
+        cmp_func fnc, void *cmpdata) {
     ssize_t index = 0;
     UCX_FOREACH(e, l) {
         if (fnc) {
@@ -189,7 +190,8 @@
     return -1;
 }
 
-int ucx_list_contains(UcxList *l, void *elem, cmp_func fnc, void *cmpdata) {
+int ucx_list_contains(const UcxList *l, void *elem,
+        cmp_func fnc, void *cmpdata) {
     return ucx_list_find(l, elem, fnc, cmpdata) > -1;
 }
 
@@ -334,3 +336,93 @@
     alfree(alloc, e);
     return l;
 }
+
+
+static UcxList* ucx_list_setoperation_a(UcxAllocator *allocator,
+        UcxList const *left, UcxList const *right,
+        cmp_func cmpfnc, void* cmpdata,
+        copy_func cpfnc, void* cpdata,
+        int op) {
+    
+    UcxList *res = NULL;
+    UcxList *cur = NULL;
+    const UcxList *src = left;
+    
+    do {
+        UCX_FOREACH(node, src) {
+            void* elem = node->data;
+            if (
+                (op == 0 && !ucx_list_contains(res, elem, cmpfnc, cmpdata)) ||
+                (op == 1 && ucx_list_contains(right, elem, cmpfnc, cmpdata)) ||
+                (op == 2 && !ucx_list_contains(right, elem, cmpfnc, cmpdata))) {
+                UcxList *nl = almalloc(allocator, sizeof(UcxList));
+                nl->prev = cur;
+                nl->next = NULL;
+                if (cpfnc) {
+                    nl->data = cpfnc(elem, cpdata);
+                } else {
+                    nl->data = elem;
+                }
+                if (cur != NULL)
+                    cur->next = nl;
+                cur = nl;
+                if (res == NULL)
+                    res = cur;
+            }
+        }
+        if (op == 0 && src == left)
+            src = right;
+        else
+            src = NULL;
+    } while (src != NULL);
+    
+    return res;
+}
+
+UcxList* ucx_list_union(UcxList const *left, UcxList const *right,
+        cmp_func cmpfnc, void* cmpdata,
+        copy_func cpfnc, void* cpdata) {
+    return ucx_list_union_a(ucx_default_allocator(),
+            left, right, cmpfnc, cmpdata, cpfnc, cpdata);
+}
+
+UcxList* ucx_list_union_a(UcxAllocator *allocator,
+        UcxList const *left, UcxList const *right,
+        cmp_func cmpfnc, void* cmpdata,
+        copy_func cpfnc, void* cpdata) {
+    
+    return ucx_list_setoperation_a(allocator, left, right,
+            cmpfnc, cmpdata, cpfnc, cpdata, 0);
+}
+
+UcxList* ucx_list_intersection(UcxList const *left, UcxList const *right,
+        cmp_func cmpfnc, void* cmpdata,
+        copy_func cpfnc, void* cpdata) {
+    return ucx_list_intersection_a(ucx_default_allocator(), left, right,
+            cmpfnc, cmpdata, cpfnc, cpdata);
+}
+
+UcxList* ucx_list_intersection_a(UcxAllocator *allocator,
+        UcxList const *left, UcxList const *right,
+        cmp_func cmpfnc, void* cmpdata,
+        copy_func cpfnc, void* cpdata) {
+    
+    return ucx_list_setoperation_a(allocator, left, right,
+            cmpfnc, cmpdata, cpfnc, cpdata, 1);
+}
+
+UcxList* ucx_list_difference(UcxList const *left, UcxList const *right,
+        cmp_func cmpfnc, void* cmpdata,
+        copy_func cpfnc, void* cpdata) {
+    return ucx_list_difference_a(ucx_default_allocator(), left, right,
+            cmpfnc, cmpdata, cpfnc, cpdata);
+}
+
+UcxList* ucx_list_difference_a(UcxAllocator *allocator,
+        UcxList const *left, UcxList const *right,
+        cmp_func cmpfnc, void* cmpdata,
+        copy_func cpfnc, void* cpdata) {
+    
+    return ucx_list_setoperation_a(allocator, left, right,
+            cmpfnc, cmpdata, cpfnc, cpdata, 2);
+}

--- a/src/ucx/list.h	Thu Nov 07 10:43:31 2019 +0100
+++ b/src/ucx/list.h	Sun Nov 24 17:57:25 2019 +0100
@@ -57,7 +57,7 @@
  * @param elem The variable name of the element
  */
 #define UCX_FOREACH(elem,list) \
-        for (UcxList* elem = list ; elem != NULL ; elem = elem->next)
+        for (UcxList* elem = (UcxList*) list ; elem != NULL ; elem = elem->next)
 
 /**
  * UCX list type.
@@ -99,7 +99,7 @@
  * @param data additional data for the copy_func()
  * @return a pointer to the copy
  */
-UcxList *ucx_list_clone(UcxList *list, copy_func cpyfnc, void* data);
+UcxList *ucx_list_clone(const UcxList *list, copy_func cpyfnc, void* data);
 
 /**
  * Creates an element-wise copy of a list using a UcxAllocator.
@@ -117,7 +117,7 @@
  * @return a pointer to the copy
  * @see ucx_list_clone()
  */
-UcxList *ucx_list_clone_a(UcxAllocator *allocator, UcxList *list,
+UcxList *ucx_list_clone_a(UcxAllocator *allocator, const UcxList *list,
         copy_func cpyfnc, void* data);
 
 /**
@@ -328,7 +328,8 @@
  * @return the index of the element containing the specified data or -1 if the
  * data is not found in this list
  */
-ssize_t ucx_list_find(UcxList *list, void *elem, cmp_func cmpfnc, void *data);
+ssize_t ucx_list_find(const UcxList *list, void *elem,
+    cmp_func cmpfnc, void *data);
 
 /**
  * Checks, if a list contains a specific element.
@@ -342,7 +343,8 @@
  * @return 1, if and only if the list contains the specified element data
  * @see ucx_list_find()
  */
-int ucx_list_contains(UcxList *list, void *elem, cmp_func cmpfnc, void *data);
+int ucx_list_contains(const UcxList *list, void *elem,
+    cmp_func cmpfnc, void *data);
 
 /**
  * Sorts a UcxList with natural merge sort.
@@ -388,6 +390,120 @@
 UcxList *ucx_list_remove_a(UcxAllocator *allocator, UcxList *list,
         UcxList *element);
 
+/**
+ * Returns the union of two lists.
+ * 
+ * The union is a list of unique elements regarding cmpfnc obtained from
+ * both source lists.
+ * 
+ * @param left the left source list
+ * @param right the right source list
+ * @param cmpfnc a function to compare elements
+ * @param cmpdata additional data for the compare function
+ * @param cpfnc a function to copy the elements
+ * @param cpdata additional data for the copy function
+ * @return a new list containing the union
+ */
+UcxList* ucx_list_union(const UcxList *left, const UcxList *right,
+    cmp_func cmpfnc, void* cmpdata,
+    copy_func cpfnc, void* cpdata);
+
+/**
+ * Returns the union of two lists.
+ * 
+ * The union is a list of unique elements regarding cmpfnc obtained from
+ * both source lists.
+ * 
+ * @param allocator allocates the new list elements
+ * @param left the left source list
+ * @param right the right source list
+ * @param cmpfnc a function to compare elements
+ * @param cmpdata additional data for the compare function
+ * @param cpfnc a function to copy the elements
+ * @param cpdata additional data for the copy function
+ * @return a new list containing the union
+ */
+UcxList* ucx_list_union_a(UcxAllocator *allocator,
+    const UcxList *left, const UcxList *right,
+    cmp_func cmpfnc, void* cmpdata,
+    copy_func cpfnc, void* cpdata);
+
+/**
+ * Returns the intersection of two lists.
+ * 
+ * The intersection contains all elements of the left list
+ * (including duplicates) that can be found in the right list.
+ * 
+ * @param left the left source list
+ * @param right the right source list
+ * @param cmpfnc a function to compare elements
+ * @param cmpdata additional data for the compare function
+ * @param cpfnc a function to copy the elements
+ * @param cpdata additional data for the copy function
+ * @return a new list containing the intersection
+ */
+UcxList* ucx_list_intersection(const UcxList *left, const UcxList *right,
+    cmp_func cmpfnc, void* cmpdata,
+    copy_func cpfnc, void* cpdata);
+
+/**
+ * Returns the intersection of two lists.
+ * 
+ * The intersection contains all elements of the left list
+ * (including duplicates) that can be found in the right list.
+ * 
+ * @param allocator allocates the new list elements
+ * @param left the left source list
+ * @param right the right source list
+ * @param cmpfnc a function to compare elements
+ * @param cmpdata additional data for the compare function
+ * @param cpfnc a function to copy the elements
+ * @param cpdata additional data for the copy function
+ * @return a new list containing the intersection
+ */
+UcxList* ucx_list_intersection_a(UcxAllocator *allocator,
+    const UcxList *left, const UcxList *right,
+    cmp_func cmpfnc, void* cmpdata,
+    copy_func cpfnc, void* cpdata);
+
+/**
+ * Returns the difference of two lists.
+ * 
+ * The difference contains all elements of the left list
+ * (including duplicates) that are not equal to any element of the right list.
+ * 
+ * @param left the left source list
+ * @param right the right source list
+ * @param cmpfnc a function to compare elements
+ * @param cmpdata additional data for the compare function
+ * @param cpfnc a function to copy the elements
+ * @param cpdata additional data for the copy function
+ * @return a new list containing the difference
+ */
+UcxList* ucx_list_difference(const UcxList *left, const UcxList *right,
+    cmp_func cmpfnc, void* cmpdata,
+    copy_func cpfnc, void* cpdata);
+
+/**
+ * Returns the difference of two lists.
+ * 
+ * The difference contains all elements of the left list
+ * (including duplicates) that are not equal to any element of the right list.
+ * 
+ * @param allocator allocates the new list elements
+ * @param left the left source list
+ * @param right the right source list
+ * @param cmpfnc a function to compare elements
+ * @param cmpdata additional data for the compare function
+ * @param cpfnc a function to copy the elements
+ * @param cpdata additional data for the copy function
+ * @return a new list containing the difference
+ */
+UcxList* ucx_list_difference_a(UcxAllocator *allocator,
+    const UcxList *left, const UcxList *right,
+    cmp_func cmpfnc, void* cmpdata,
+    copy_func cpfnc, void* cpdata);
+
 #ifdef	__cplusplus
 }
 #endif

--- a/test/list_tests.c	Thu Nov 07 10:43:31 2019 +0100
+++ b/test/list_tests.c	Sun Nov 24 17:57:25 2019 +0100
@@ -403,3 +403,94 @@
     ucx_list_free(expected);
     ucx_list_free(list);
 }
+
+UCX_TEST(test_ucx_list_union) {
+    UcxList *left = ucx_list_append(NULL, (void*)"this");
+    left = ucx_list_append(left, (void*)"is");
+    left = ucx_list_append(left, (void*)"a");
+    left = ucx_list_append(left, (void*)"test");
+
+    UcxList *right = ucx_list_append(NULL, (void*)"to");
+    right = ucx_list_append(right, (void*)"test");
+    right = ucx_list_append(right, (void*)"set");
+    right = ucx_list_append(right, (void*)"operations");
+    
+    UcxList *expected = ucx_list_append(NULL, (void*)"this");
+    expected = ucx_list_append(expected, (void*)"is");
+    expected = ucx_list_append(expected, (void*)"a");
+    expected = ucx_list_append(expected, (void*)"test");
+    expected = ucx_list_append(expected, (void*)"to");
+    expected = ucx_list_append(expected, (void*)"set");
+    expected = ucx_list_append(expected, (void*)"operations");
+
+    UcxList* result = ucx_list_union(left, right, ucx_cmp_str,
+            NULL, NULL, NULL);
+
+    UCX_TEST_BEGIN
+    UCX_TEST_ASSERT(ucx_list_equals(result, expected,
+            ucx_cmp_str, NULL), "failed");
+    UCX_TEST_END
+
+    ucx_list_free(result);
+    ucx_list_free(expected);
+    ucx_list_free(right);
+    ucx_list_free(left);
+}
+
+UCX_TEST(test_ucx_list_intersection) {
+    UcxList *left = ucx_list_append(NULL, (void*)"this");
+    left = ucx_list_append(left, (void*)"is");
+    left = ucx_list_append(left, (void*)"a");
+    left = ucx_list_append(left, (void*)"test");
+
+    UcxList *right = ucx_list_append(NULL, (void*)"to");
+    right = ucx_list_append(right, (void*)"test");
+    right = ucx_list_append(right, (void*)"a");
+    right = ucx_list_append(right, (void*)"set");
+    right = ucx_list_append(right, (void*)"operation");
+    
+    UcxList *expected = ucx_list_append(NULL, (void*)"a");
+    expected = ucx_list_append(expected, (void*)"test");
+
+    UcxList* result = ucx_list_intersection(left, right, ucx_cmp_str,
+            NULL, NULL, NULL);
+
+    UCX_TEST_BEGIN
+    UCX_TEST_ASSERT(ucx_list_equals(result, expected,
+            ucx_cmp_str, NULL), "failed");
+    UCX_TEST_END
+
+    ucx_list_free(result);
+    ucx_list_free(expected);
+    ucx_list_free(right);
+    ucx_list_free(left);
+}
+
+UCX_TEST(test_ucx_list_difference) {
+    UcxList *left = ucx_list_append(NULL, (void*)"this");
+    left = ucx_list_append(left, (void*)"is");
+    left = ucx_list_append(left, (void*)"a");
+    left = ucx_list_append(left, (void*)"test");
+
+    UcxList *right = ucx_list_append(NULL, (void*)"to");
+    right = ucx_list_append(right, (void*)"test");
+    right = ucx_list_append(right, (void*)"this");
+    right = ucx_list_append(right, (void*)"set");
+    right = ucx_list_append(right, (void*)"operations");
+    
+    UcxList *expected = ucx_list_append(NULL, (void*)"is");
+    expected = ucx_list_append(expected, (void*)"a");
+    
+    UcxList* result = ucx_list_difference(left, right, ucx_cmp_str,
+            NULL, NULL, NULL);
+
+    UCX_TEST_BEGIN
+    UCX_TEST_ASSERT(ucx_list_equals(result, expected,
+            ucx_cmp_str, NULL), "failed");
+    UCX_TEST_END
+
+    ucx_list_free(result);
+    ucx_list_free(expected);
+    ucx_list_free(right);
+    ucx_list_free(left);
+}

--- a/test/list_tests.h	Thu Nov 07 10:43:31 2019 +0100
+++ b/test/list_tests.h	Sun Nov 24 17:57:25 2019 +0100
@@ -55,6 +55,9 @@
 UCX_TEST(test_ucx_list_remove);
 UCX_TEST(test_ucx_list_clone);
 UCX_TEST(test_ucx_list_sort);
+UCX_TEST(test_ucx_list_union);
+UCX_TEST(test_ucx_list_intersection);
+UCX_TEST(test_ucx_list_difference);
 
 #ifdef	__cplusplus
 }

--- a/test/main.c	Thu Nov 07 10:43:31 2019 +0100
+++ b/test/main.c	Sun Nov 24 17:57:25 2019 +0100
@@ -180,6 +180,9 @@
         ucx_test_register(suite, test_ucx_list_remove);
         ucx_test_register(suite, test_ucx_list_clone);
         ucx_test_register(suite, test_ucx_list_sort);
+        ucx_test_register(suite, test_ucx_list_union);
+        ucx_test_register(suite, test_ucx_list_intersection);
+        ucx_test_register(suite, test_ucx_list_difference);
 
         /* UcxMemPool Tests */
         ucx_test_register(suite, test_ucx_mempool_new);