diff options
Diffstat (limited to 'libparc/parc/algol/test/test_parc_TreeRedBlack.c')
| -rwxr-xr-x | libparc/parc/algol/test/test_parc_TreeRedBlack.c | 1462 |
1 files changed, 1462 insertions, 0 deletions
diff --git a/libparc/parc/algol/test/test_parc_TreeRedBlack.c b/libparc/parc/algol/test/test_parc_TreeRedBlack.c new file mode 100755 index 00000000..cf2f19ca --- /dev/null +++ b/libparc/parc/algol/test/test_parc_TreeRedBlack.c @@ -0,0 +1,1462 @@ +/* + * Copyright (c) 2017 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + + +#include <config.h> +#include <stdio.h> +#include <unistd.h> +#include <fcntl.h> +#include <time.h> + +#include <parc/algol/parc_SafeMemory.h> +#include <LongBow/unit-test.h> + +#include "../parc_TreeRedBlack.c" + + +void * +keyNewInt(int key) +{ + int *newKey = parcMemory_Allocate(sizeof(int)); + assertNotNull(newKey, "parcMemory_Allocate(%zu) returned NULL", sizeof(int)); + *newKey = key; + return newKey; +} + +void * +valueNewInt(int value) +{ + int *newValue = parcMemory_Allocate(sizeof(int)); + assertNotNull(newValue, "parcMemory_Allocate(%zu) returned NULL", sizeof(int)); + *newValue = value; + return newValue; +} + +void * +keyCopy(const void *key) +{ + return keyNewInt(*(int *) key); +} + +void * +valueCopy(const void *value) +{ + return valueNewInt(*(int *) value); +} + +void * +keyNew(char *key) +{ + return parcMemory_StringDuplicate(key, strlen(key)); +} + +void * +valueNew(char *value) +{ + return parcMemory_StringDuplicate(value, strlen(value)); +} + +int +intComp(const void *key1, const void *key2) +{ + if (*(int *) key1 < *(int *) key2) { + return -1; + } + if (*(int *) key1 == *(int *) key2) { + return 0; + } + return 1; +} + +bool +intEquals(const void *int1, const void *int2) +{ + return intComp(int1, int2) == 0; +} + +int +pointerComp(const void *key1, const void *key2) +{ + if (key1 < key2) { + return -1; + } + if (key1 == key2) { + return 0; + } + return 1; +} + +int +stringComp(const void *key1, const void *key2) +{ + // We assume all keys are strings. + return strcmp(key1, key2); +} + +void +keyFree(void **value) +{ + parcMemory_Deallocate((void **) value); + *value = NULL; +} + +void +valueFree(void **key) +{ + parcMemory_Deallocate((void **) key); + *key = NULL; +} + + +LONGBOW_TEST_RUNNER(PARC_TreeRedBlack) +{ + LONGBOW_RUN_TEST_FIXTURE(Global); + LONGBOW_RUN_TEST_FIXTURE(Local); + LONGBOW_RUN_TEST_FIXTURE(Stress); +} + +LONGBOW_TEST_RUNNER_SETUP(PARC_TreeRedBlack) +{ + int seed = (int) time(NULL); + printf("Seed = %u\n", seed); + srandom(seed); + return LONGBOW_STATUS_SUCCEEDED; +} + +LONGBOW_TEST_RUNNER_TEARDOWN(PARC_TreeRedBlack) +{ + uint32_t outstandingAllocations = parcSafeMemory_ReportAllocation(STDERR_FILENO); + if (outstandingAllocations != 0) { + printf("%s leaks memory by %d allocations\n", longBowTestRunner_GetName(testRunner), outstandingAllocations); + return LONGBOW_STATUS_MEMORYLEAK; + } + return LONGBOW_STATUS_SUCCEEDED; +} + +LONGBOW_TEST_FIXTURE(Global) +{ + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Remove_Ordered); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Create); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Insert_Destroy); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Insert_Ordered); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Insert_OutOfOrder); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Insert_Overwrite); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_DestroyTillEmpty); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Size_Empty); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Size); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Size_Overwrite); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Get_EmptyTree); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Get_NonExistent); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Get_First); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Get); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Get_Last); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Get_Biggest); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Get_Smallest); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Get_FirstKey); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Get_LastKey); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Get_FirstKey_Empty); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Get_LastKey_Empty); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Remove_First); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Remove); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Remove_Last); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Remove_NonExistent); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_RemoveAndDestroy_First); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_RemoveAndDestroy); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_RemoveAndDestroy_Last); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_RemoveAndDestroy_NonExistent); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Remove_WithSuccessorNonRoot); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Remove_LeftChildRightChild); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Keys); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Values); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Equals_Empty); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Equals); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Equals_Func); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Equals_DifferentLength); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Equals_Not_Values); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Equals_Not_Values_Func); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Equals_Not_Keys); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Copy); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Copy_Direct); + //LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_ExerciseRandom); + //LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_ExerciseRootFailure); +} + +LONGBOW_TEST_FIXTURE_SETUP(Global) +{ + return LONGBOW_STATUS_SUCCEEDED; +} + +LONGBOW_TEST_FIXTURE_TEARDOWN(Global) +{ + /* + * uint32_t outstandingAllocations = parcSafeMemory_ReportAllocation(STDERR_FILENO); + * if (outstandingAllocations != 0) { + * printf("%s leaks memory by %d allocations\n", longBowTestCase_GetName(testCase), outstandingAllocations); + * return LONGBOW_STATUS_MEMORYLEAK; + * } + */ + return LONGBOW_STATUS_SUCCEEDED; +} + +static +int +strComp(const void *s1, const void *s2) +{ + return strcmp((char *) s1, (char *) s2); +} + +static +bool +strEquals(const void *s1, const void *s2) +{ + return strcmp(s1, s2) == 0; +} + +static +int +recursiveCheckBlackDepth(const PARCTreeRedBlack *tree, const Node *node) +{ + assertNotNull(tree, "Null tree?\n"); + assertNotNull(node, "Null node?\n"); + if (node == tree->nil) { + return 0; + } + int right_depth = recursiveCheckBlackDepth(tree, node->right_child); + int left_depth = recursiveCheckBlackDepth(tree, node->left_child); + assertTrue(right_depth == left_depth, "Wrong depth!!\n"); + if (_rbNodeColor(node) == BLACK) { + return right_depth + 1; + } + return right_depth; +} + +static +void +rbCheckTree(const PARCTreeRedBlack *tree) +{ + assertNotNull(tree, "Tree can't be NULL"); + //printf("--- TREE ---\n"); + _rbNodeAssertTreeInvariants(tree); + if (tree->size > 0) { + //_rbNodeRecursiveRun((PARCTreeRedBlack *)tree,tree->root,rbCheckNode,(void *)tree); + recursiveCheckBlackDepth(tree, tree->root); + } +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Remove_Ordered) +{ + char *insertList[16] = { + "01", + "02", + "03", + "04", + "05", + "06", + "07", + "08", + "09", + "10", + "11", + "12", + "13", + "14", + "15", + "16" + }; + + PARCTreeRedBlack *tree1; + + tree1 = parcTreeRedBlack_Create(strComp, NULL, NULL, strEquals, NULL, NULL); + + for (int i = 0; i < 16; i++) { + parcTreeRedBlack_Insert(tree1, insertList[i], insertList[i]); + } + + for (int i = 0; i < 14; i++) { + //rbPrintTreeString(tree1); + void *data = parcTreeRedBlack_Remove(tree1, insertList[i]); + assertNotNull(data, "Data is null!"); + } + + parcTreeRedBlack_Destroy(&tree1); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Create) +{ + PARCTreeRedBlack *tree; + + tree = parcTreeRedBlack_Create(stringComp, NULL, NULL, NULL, NULL, NULL); + + parcTreeRedBlack_Destroy(&tree); + + tree = parcTreeRedBlack_Create(stringComp, keyFree, NULL, NULL, valueFree, NULL); + + parcTreeRedBlack_Destroy(&tree); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Insert_Destroy) +{ + PARCTreeRedBlack *tree; + + tree = parcTreeRedBlack_Create(stringComp, keyFree, NULL, NULL, valueFree, NULL); + + void *value1 = valueNew("value 1"); + void *key1 = keyNew("1"); + void *value2 = valueNew("value 2"); + void *key2 = keyNew("2"); + void *value3 = valueNew("value 3"); + void *key3 = keyNew("3"); + + parcTreeRedBlack_Insert(tree, key1, value1); + parcTreeRedBlack_Insert(tree, key2, value2); + parcTreeRedBlack_Insert(tree, key3, value3); + + parcTreeRedBlack_Destroy(&tree); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Insert_Overwrite) +{ + PARCTreeRedBlack *tree; + + tree = parcTreeRedBlack_Create(stringComp, keyFree, NULL, NULL, valueFree, NULL); + + parcTreeRedBlack_Insert(tree, keyNew("1"), valueNew("v1")); + parcTreeRedBlack_Insert(tree, keyNew("2"), valueNew("v2")); + parcTreeRedBlack_Insert(tree, keyNew("3"), valueNew("v3")); + parcTreeRedBlack_Insert(tree, keyNew("3"), valueNew("v4")); + parcTreeRedBlack_Insert(tree, keyNew("3"), valueNew("v5")); + + assertTrue(3 == parcTreeRedBlack_Size(tree), "Wrong size of tree should stay at 3"); + + parcTreeRedBlack_Destroy(&tree); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Insert_Ordered) +{ + PARCTreeRedBlack *tree; + + tree = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + parcTreeRedBlack_Insert(tree, (void *) 1, (void *) 1001); + parcTreeRedBlack_Insert(tree, (void *) 2, (void *) 1002); + parcTreeRedBlack_Insert(tree, (void *) 3, (void *) 1003); + + parcTreeRedBlack_Destroy(&tree); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Insert_OutOfOrder) +{ + PARCTreeRedBlack *tree; + + tree = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + parcTreeRedBlack_Insert(tree, (void *) 4, (void *) 1004); + parcTreeRedBlack_Insert(tree, (void *) 2, (void *) 1002); + parcTreeRedBlack_Insert(tree, (void *) 3, (void *) 1003); + parcTreeRedBlack_Insert(tree, (void *) 1, (void *) 1001); + + parcTreeRedBlack_Destroy(&tree); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Size_Empty) +{ + PARCTreeRedBlack *tree; + + tree = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + assertTrue(0 == parcTreeRedBlack_Size(tree), "Wrong size of tree - empty, start"); + + parcTreeRedBlack_Destroy(&tree); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Size) +{ + PARCTreeRedBlack *tree; + size_t size; + + tree = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + parcTreeRedBlack_Insert(tree, (void *) 4, (void *) 1004); + parcTreeRedBlack_Insert(tree, (void *) 2, (void *) 1002); + parcTreeRedBlack_Insert(tree, (void *) 3, (void *) 1003); + + assertTrue(3 == parcTreeRedBlack_Size(tree), "Wrong size of tree after add 3"); + + parcTreeRedBlack_Insert(tree, (void *) 1, (void *) 1001); + + assertTrue(4 == parcTreeRedBlack_Size(tree), "Wrong size of tree after add 1 more"); + + parcTreeRedBlack_RemoveAndDestroy(tree, (void *) 2); + + size = parcTreeRedBlack_Size(tree); + + assertTrue(3 == size, "Wrong size of tree after 1 delete (%zu instead of 3)", size); + + parcTreeRedBlack_Insert(tree, (void *) 7, (void *) 1007); + + assertTrue(4 == parcTreeRedBlack_Size(tree), "Wrong size of tree after add 1 more"); + + parcTreeRedBlack_RemoveAndDestroy(tree, (void *) 3); + assertTrue(3 == parcTreeRedBlack_Size(tree), "Wrong size of tree after del 1 more - 3"); + + parcTreeRedBlack_Destroy(&tree); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_DestroyTillEmpty) +{ + PARCTreeRedBlack *tree; + size_t size; + + tree = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + parcTreeRedBlack_Insert(tree, (void *) 4, (void *) 1004); + parcTreeRedBlack_Insert(tree, (void *) 2, (void *) 1002); + parcTreeRedBlack_Insert(tree, (void *) 3, (void *) 1003); + parcTreeRedBlack_Insert(tree, (void *) 1, (void *) 1001); + parcTreeRedBlack_Insert(tree, (void *) 5, (void *) 1001); + parcTreeRedBlack_Insert(tree, (void *) 7, (void *) 1001); + parcTreeRedBlack_Insert(tree, (void *) 6, (void *) 1001); + + parcTreeRedBlack_RemoveAndDestroy(tree, (void *) 3); + parcTreeRedBlack_RemoveAndDestroy(tree, (void *) 1); + parcTreeRedBlack_RemoveAndDestroy(tree, (void *) 4); + parcTreeRedBlack_RemoveAndDestroy(tree, (void *) 2); + parcTreeRedBlack_RemoveAndDestroy(tree, (void *) 6); + parcTreeRedBlack_RemoveAndDestroy(tree, (void *) 5); + parcTreeRedBlack_RemoveAndDestroy(tree, (void *) 7); + + size = parcTreeRedBlack_Size(tree); + + assertTrue(0 == size, "Wrong size of tree - empty (got %zu)", size); + + parcTreeRedBlack_Destroy(&tree); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Size_Overwrite) +{ + PARCTreeRedBlack *tree; + + tree = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + parcTreeRedBlack_Insert(tree, (void *) 4, (void *) 1004); + parcTreeRedBlack_Insert(tree, (void *) 2, (void *) 1002); + parcTreeRedBlack_Insert(tree, (void *) 3, (void *) 1003); + + // Size is 3 here, we'll insert the same number now.. + + parcTreeRedBlack_Insert(tree, (void *) 3, (void *) 1033); + + assertTrue(3 == parcTreeRedBlack_Size(tree), "Wrong size of tree after overwrite"); + + parcTreeRedBlack_Destroy(&tree); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Get_EmptyTree) +{ + PARCTreeRedBlack *tree; + + tree = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + void *value = parcTreeRedBlack_Get(tree, (void *) 1); + + assertTrue(NULL == value, "Object did not exist, must return NULL"); + + parcTreeRedBlack_Destroy(&tree); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Get_NonExistent) +{ + PARCTreeRedBlack *tree; + + tree = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + for (long i = 1; i < 10; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree, (void *) i, (void *) (i << 8)); + } + + void *value = parcTreeRedBlack_Get(tree, (void *) 100); + + assertTrue(NULL == value, "Object did not exist, must return NULL"); + + parcTreeRedBlack_Destroy(&tree); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Get_First) +{ + PARCTreeRedBlack *tree; + + tree = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + for (long i = 1; i < 4; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree, (void *) i, (void *) (i << 8)); + } + + void *value = parcTreeRedBlack_Get(tree, (void *) 1); + + assertTrue((1 << 8) == (long) value, "Wrong value, got %ld", (long) value); + + parcTreeRedBlack_Destroy(&tree); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Get) +{ + PARCTreeRedBlack *tree; + + tree = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + for (long i = 1; i < 10; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree, (void *) i, (void *) (i << 8)); + } + + void *value = parcTreeRedBlack_Get(tree, (void *) 4); + + assertTrue((4 << 8) == (long) value, "Wrong value, got %ld", (long) value); + + parcTreeRedBlack_Destroy(&tree); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Get_Last) +{ + PARCTreeRedBlack *tree; + + tree = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + for (long i = 1; i < 10; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree, (void *) i, (void *) (i << 8)); + } + + void *value = parcTreeRedBlack_Get(tree, (void *) 9); + + assertTrue((9 << 8) == (long) value, "Wrong value, got %ld", (long) value); + + parcTreeRedBlack_Destroy(&tree); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Get_Smallest) +{ + PARCTreeRedBlack *tree; + + tree = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + for (long i = 30; i < 40; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree, (void *) i, (void *) (i << 8)); + } + for (long i = 1; i < 10; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree, (void *) i, (void *) (i << 8)); + } + for (long i = 20; i < 30; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree, (void *) i, (void *) (i << 8)); + } + + + void *value = parcTreeRedBlack_Get(tree, (void *) 1); + + assertTrue((1 << 8) == (long) value, "Wrong value, got %ld", (long) value); + + parcTreeRedBlack_Destroy(&tree); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Get_Biggest) +{ + PARCTreeRedBlack *tree; + + tree = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + for (long i = 30; i < 40; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree, (void *) i, (void *) (i << 8)); + } + for (long i = 1; i < 10; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree, (void *) i, (void *) (i << 8)); + } + for (long i = 20; i < 30; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree, (void *) i, (void *) (i << 8)); + } + + + void *value = parcTreeRedBlack_Get(tree, (void *) 39); + + assertTrue((39 << 8) == (long) value, "Wrong value, got %ld", (long) value); + + parcTreeRedBlack_Destroy(&tree); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Get_FirstKey) +{ + PARCTreeRedBlack *tree; + + tree = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + for (long i = 30; i < 40; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree, (void *) i, (void *) (i << 8)); + } + for (long i = 1; i < 10; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree, (void *) i, (void *) (i << 8)); + } + for (long i = 20; i < 30; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree, (void *) i, (void *) (i << 8)); + } + + void *key = parcTreeRedBlack_FirstKey(tree); + + assertTrue(1 == (long) key, "Wrong value, got %ld", (long) key); + + parcTreeRedBlack_Destroy(&tree); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Get_FirstKey_Empty) +{ + PARCTreeRedBlack *tree; + + tree = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + void *key = parcTreeRedBlack_FirstKey(tree); + + assertNull(key, "Should get NULL on empty tree"); + + parcTreeRedBlack_Destroy(&tree); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Get_LastKey_Empty) +{ + PARCTreeRedBlack *tree; + + tree = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + void *key = parcTreeRedBlack_LastKey(tree); + + assertNull(key, "Should get NULL on empty tree"); + + parcTreeRedBlack_Destroy(&tree); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Get_LastKey) +{ + PARCTreeRedBlack *tree; + + tree = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + for (long i = 30; i < 40; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree, (void *) i, (void *) (i << 8)); + } + for (long i = 1; i < 10; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree, (void *) i, (void *) (i << 8)); + } + for (long i = 20; i < 30; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree, (void *) i, (void *) (i << 8)); + } + + void *key = parcTreeRedBlack_LastKey(tree); + + assertTrue(39 == (long) key, "Wrong value, got %ld", (long) key); + + parcTreeRedBlack_Destroy(&tree); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Remove_First) +{ + PARCTreeRedBlack *tree1; + PARCTreeRedBlack *tree2; + + tree1 = parcTreeRedBlack_Create(intComp, keyFree, NULL, intEquals, valueFree, NULL); + tree2 = parcTreeRedBlack_Create(intComp, keyFree, NULL, intEquals, valueFree, NULL); + + for (int i = 30; i < 40; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, keyNewInt(i), valueNewInt(i << 8)); + parcTreeRedBlack_Insert(tree2, keyNewInt(i), valueNewInt(i << 8)); + } + + parcTreeRedBlack_Insert(tree1, keyNewInt(1), valueNewInt(1 << 8)); + + for (int i = 2; i < 10; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, keyNewInt(i), valueNewInt(i << 8)); + parcTreeRedBlack_Insert(tree2, keyNewInt(i), valueNewInt(i << 8)); + } + + for (int i = 20; i < 30; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, keyNewInt(i), valueNewInt(i << 8)); + parcTreeRedBlack_Insert(tree2, keyNewInt(i), valueNewInt(i << 8)); + } + + int searchKey = 1; + + void *data = parcTreeRedBlack_Remove(tree1, &searchKey); + + valueFree(&data); + + assertTrue(parcTreeRedBlack_Equals(tree1, tree2), "Trees dont match after remove"); + + parcTreeRedBlack_Destroy(&tree1); + parcTreeRedBlack_Destroy(&tree2); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Remove) +{ + PARCTreeRedBlack *tree1; + PARCTreeRedBlack *tree2; + + tree1 = parcTreeRedBlack_Create(intComp, keyFree, NULL, intEquals, valueFree, NULL); + tree2 = parcTreeRedBlack_Create(intComp, keyFree, NULL, intEquals, valueFree, NULL); + + for (int i = 31; i < 40; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, keyNewInt(i), valueNewInt(i << 8)); + parcTreeRedBlack_Insert(tree2, keyNewInt(i), valueNewInt(i << 8)); + } + + parcTreeRedBlack_Insert(tree1, keyNewInt(30), valueNewInt(31 << 8)); + + for (int i = 2; i < 10; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, keyNewInt(i), valueNewInt(i << 8)); + parcTreeRedBlack_Insert(tree2, keyNewInt(i), valueNewInt(i << 8)); + } + + for (int i = 20; i < 30; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, keyNewInt(i), valueNewInt(i << 8)); + parcTreeRedBlack_Insert(tree2, keyNewInt(i), valueNewInt(i << 8)); + } + + int searchKey = 30; + + void *data = parcTreeRedBlack_Remove(tree1, &searchKey); + + valueFree(&data); + + assertTrue(parcTreeRedBlack_Equals(tree1, tree2), "Trees dont match after remove"); + + parcTreeRedBlack_Destroy(&tree1); + parcTreeRedBlack_Destroy(&tree2); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Remove_Last) +{ + PARCTreeRedBlack *tree1; + PARCTreeRedBlack *tree2; + + tree1 = parcTreeRedBlack_Create(intComp, keyFree, NULL, intEquals, valueFree, NULL); + tree2 = parcTreeRedBlack_Create(intComp, keyFree, NULL, intEquals, valueFree, NULL); + + for (int i = 30; i < 40; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, keyNewInt(i), valueNewInt(i << 8)); + parcTreeRedBlack_Insert(tree2, keyNewInt(i), valueNewInt(i << 8)); + } + parcTreeRedBlack_Insert(tree1, keyNewInt(100), valueNewInt(100 << 8)); + for (int i = 2; i < 10; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, keyNewInt(i), valueNewInt(i << 8)); + parcTreeRedBlack_Insert(tree2, keyNewInt(i), valueNewInt(i << 8)); + } + for (int i = 20; i < 30; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, keyNewInt(i), valueNewInt(i << 8)); + parcTreeRedBlack_Insert(tree2, keyNewInt(i), valueNewInt(i << 8)); + } + + int searchKey = 100; + + void *data = parcTreeRedBlack_Remove(tree1, &searchKey); + + valueFree(&data); + + assertTrue(parcTreeRedBlack_Equals(tree1, tree2), "Trees dont match after remove"); + + parcTreeRedBlack_Destroy(&tree1); + parcTreeRedBlack_Destroy(&tree2); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_RemoveAndDestroy_First) +{ + PARCTreeRedBlack *tree1; + PARCTreeRedBlack *tree2; + + tree1 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + tree2 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + for (long i = 30; i < 40; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, (void *) i, (void *) (i << 8)); + parcTreeRedBlack_Insert(tree2, (void *) i, (void *) (i << 8)); + } + + parcTreeRedBlack_Insert(tree1, (void *) 1, (void *) (1 << 8)); + + for (long i = 2; i < 10; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, (void *) i, (void *) (i << 8)); + parcTreeRedBlack_Insert(tree2, (void *) i, (void *) (i << 8)); + } + for (long i = 20; i < 30; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, (void *) i, (void *) (i << 8)); + parcTreeRedBlack_Insert(tree2, (void *) i, (void *) (i << 8)); + } + + parcTreeRedBlack_RemoveAndDestroy(tree1, (void *) 1); + + assertTrue(parcTreeRedBlack_Equals(tree1, tree2), "Trees dont match after remove"); + + parcTreeRedBlack_Destroy(&tree1); + parcTreeRedBlack_Destroy(&tree2); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_RemoveAndDestroy) +{ + PARCTreeRedBlack *tree1; + PARCTreeRedBlack *tree2; + + tree1 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + tree2 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + for (long i = 31; i < 40; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, (void *) i, (void *) (i << 8)); + parcTreeRedBlack_Insert(tree2, (void *) i, (void *) (i << 8)); + } + + parcTreeRedBlack_Insert(tree1, (void *) 30, (void *) (30 << 8)); + + for (long i = 2; i < 10; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, (void *) i, (void *) (i << 8)); + parcTreeRedBlack_Insert(tree2, (void *) i, (void *) (i << 8)); + } + for (long i = 20; i < 30; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, (void *) i, (void *) (i << 8)); + parcTreeRedBlack_Insert(tree2, (void *) i, (void *) (i << 8)); + } + + parcTreeRedBlack_RemoveAndDestroy(tree1, (void *) 30); + + assertTrue(parcTreeRedBlack_Equals(tree1, tree2), "Trees dont match after remove"); + + parcTreeRedBlack_Destroy(&tree1); + parcTreeRedBlack_Destroy(&tree2); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Remove_NonExistent) +{ + PARCTreeRedBlack *tree1; + PARCTreeRedBlack *tree2; + + tree1 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + tree2 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + for (long i = 30; i < 40; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, (void *) i, (void *) (i << 8)); + parcTreeRedBlack_Insert(tree2, (void *) i, (void *) (i << 8)); + } + for (long i = 2; i < 10; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, (void *) i, (void *) (i << 8)); + parcTreeRedBlack_Insert(tree2, (void *) i, (void *) (i << 8)); + } + for (long i = 20; i < 30; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, (void *) i, (void *) (i << 8)); + parcTreeRedBlack_Insert(tree2, (void *) i, (void *) (i << 8)); + } + + void *element = parcTreeRedBlack_Remove(tree1, (void *) 100); + + assertNull(element, "Return value must be NULL on non existing element"); + assertTrue(parcTreeRedBlack_Equals(tree1, tree2), "Trees dont match after remove"); + + parcTreeRedBlack_Destroy(&tree1); + parcTreeRedBlack_Destroy(&tree2); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_RemoveAndDestroy_NonExistent) +{ + PARCTreeRedBlack *tree1; + PARCTreeRedBlack *tree2; + + tree1 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + tree2 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + for (long i = 30; i < 40; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, (void *) i, (void *) (i << 8)); + parcTreeRedBlack_Insert(tree2, (void *) i, (void *) (i << 8)); + } + for (long i = 2; i < 10; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, (void *) i, (void *) (i << 8)); + parcTreeRedBlack_Insert(tree2, (void *) i, (void *) (i << 8)); + } + for (long i = 20; i < 30; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, (void *) i, (void *) (i << 8)); + parcTreeRedBlack_Insert(tree2, (void *) i, (void *) (i << 8)); + } + + parcTreeRedBlack_RemoveAndDestroy(tree1, (void *) 100); + + assertTrue(parcTreeRedBlack_Equals(tree1, tree2), "Trees dont match after remove"); + + parcTreeRedBlack_Destroy(&tree1); + parcTreeRedBlack_Destroy(&tree2); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Remove_WithSuccessorNonRoot) +{ + PARCTreeRedBlack *tree1; + PARCTreeRedBlack *tree2; + + long insert1[15] = { 8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15 }; + long insert2[13] = { 8, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15 }; + + tree1 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + tree2 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + + + for (int i = 0; i < 15; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, (void *) insert1[i], (void *) (insert1[i] << 8)); + } + + for (int i = 0; i < 13; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree2, (void *) insert2[i], (void *) (insert2[i] << 8)); + } + + parcTreeRedBlack_RemoveAndDestroy(tree1, (void *) 4); + parcTreeRedBlack_RemoveAndDestroy(tree1, (void *) 12); + + assertTrue(parcTreeRedBlack_Equals(tree1, tree2), "Trees dont match after remove"); + + parcTreeRedBlack_Destroy(&tree1); + parcTreeRedBlack_Destroy(&tree2); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Remove_LeftChildRightChild) +{ + PARCTreeRedBlack *tree1; + PARCTreeRedBlack *tree2; + + long insert1[15] = { 8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15 }; + long insert2[15] = { 8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15 }; + + tree1 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + tree2 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + + + for (int i = 0; i < 15; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, (void *) insert1[i], (void *) (insert1[i] << 8)); + } + + for (int i = 0; i < 15; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree2, (void *) insert2[i], (void *) (insert2[i] << 8)); + } + + parcTreeRedBlack_RemoveAndDestroy(tree1, (void *) 13); + parcTreeRedBlack_RemoveAndDestroy(tree1, (void *) 7); + parcTreeRedBlack_RemoveAndDestroy(tree1, (void *) 14); + parcTreeRedBlack_RemoveAndDestroy(tree1, (void *) 6); + parcTreeRedBlack_RemoveAndDestroy(tree1, (void *) 15); + parcTreeRedBlack_RemoveAndDestroy(tree1, (void *) 12); + parcTreeRedBlack_RemoveAndDestroy(tree1, (void *) 11); + parcTreeRedBlack_RemoveAndDestroy(tree1, (void *) 10); + parcTreeRedBlack_RemoveAndDestroy(tree1, (void *) 9); + parcTreeRedBlack_RemoveAndDestroy(tree1, (void *) 8); + parcTreeRedBlack_RemoveAndDestroy(tree1, (void *) 5); + parcTreeRedBlack_RemoveAndDestroy(tree1, (void *) 4); + parcTreeRedBlack_RemoveAndDestroy(tree1, (void *) 3); + parcTreeRedBlack_RemoveAndDestroy(tree1, (void *) 2); + parcTreeRedBlack_RemoveAndDestroy(tree1, (void *) 1); + + parcTreeRedBlack_RemoveAndDestroy(tree2, (void *) 1); + parcTreeRedBlack_RemoveAndDestroy(tree2, (void *) 2); + parcTreeRedBlack_RemoveAndDestroy(tree2, (void *) 3); + parcTreeRedBlack_RemoveAndDestroy(tree2, (void *) 4); + parcTreeRedBlack_RemoveAndDestroy(tree2, (void *) 5); + parcTreeRedBlack_RemoveAndDestroy(tree2, (void *) 6); + parcTreeRedBlack_RemoveAndDestroy(tree2, (void *) 7); + parcTreeRedBlack_RemoveAndDestroy(tree2, (void *) 8); + parcTreeRedBlack_RemoveAndDestroy(tree2, (void *) 9); + parcTreeRedBlack_RemoveAndDestroy(tree2, (void *) 10); + parcTreeRedBlack_RemoveAndDestroy(tree2, (void *) 11); + parcTreeRedBlack_RemoveAndDestroy(tree2, (void *) 12); + parcTreeRedBlack_RemoveAndDestroy(tree2, (void *) 13); + parcTreeRedBlack_RemoveAndDestroy(tree2, (void *) 14); + parcTreeRedBlack_RemoveAndDestroy(tree2, (void *) 15); + + //assertTrue(parcTreeRedBlack_Equals(tree1,tree2),"Trees dont match after remove"); + + parcTreeRedBlack_Destroy(&tree1); + parcTreeRedBlack_Destroy(&tree2); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_RemoveAndDestroy_Last) +{ + PARCTreeRedBlack *tree1; + PARCTreeRedBlack *tree2; + + tree1 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + tree2 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + for (long i = 30; i < 40; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, (void *) i, (void *) (i << 8)); + parcTreeRedBlack_Insert(tree2, (void *) i, (void *) (i << 8)); + } + parcTreeRedBlack_Insert(tree1, (void *) 100, (void *) (100 << 8)); + for (long i = 2; i < 10; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, (void *) i, (void *) (i << 8)); + parcTreeRedBlack_Insert(tree2, (void *) i, (void *) (i << 8)); + } + for (long i = 20; i < 30; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, (void *) i, (void *) (i << 8)); + parcTreeRedBlack_Insert(tree2, (void *) i, (void *) (i << 8)); + } + + parcTreeRedBlack_RemoveAndDestroy(tree1, (void *) 100); + + assertTrue(parcTreeRedBlack_Equals(tree1, tree2), "Trees dont match after remove"); + + parcTreeRedBlack_Destroy(&tree1); + parcTreeRedBlack_Destroy(&tree2); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Keys) +{ + PARCTreeRedBlack *tree1; + PARCArrayList *list; + + tree1 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + list = parcArrayList_Create(NULL); + + // Insert in tree out of order + for (long i = 10; i < 20; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, (void *) i, (void *) (i << 8)); + } + for (long i = 1; i < 10; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, (void *) i, (void *) (i << 8)); + } + + // Insert in list in order + for (long i = 1; i < 20; i++) { + // Add some elements to the tree + parcArrayList_Add(list, (void *) i); + } + + PARCArrayList *keys = parcTreeRedBlack_Keys(tree1); + + assertTrue(parcArrayList_Equals(list, keys), "Key list doesnt' match"); + + parcArrayList_Destroy(&keys); + parcArrayList_Destroy(&list); + parcTreeRedBlack_Destroy(&tree1); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Values) +{ + PARCTreeRedBlack *tree1; + PARCArrayList *list; + + tree1 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + list = parcArrayList_Create(NULL); + + // Insert in tree out of order + for (long i = 10; i < 20; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, (void *) i, (void *) (i << 8)); + } + for (long i = 1; i < 10; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, (void *) i, (void *) (i << 8)); + } + + // Insert in list in order + for (long i = 1; i < 20; i++) { + // Add some elements to the tree + parcArrayList_Add(list, (void *) (i << 8)); + } + + PARCArrayList *values = parcTreeRedBlack_Values(tree1); + + assertTrue(parcArrayList_Equals(list, values), "Key list doesnt' match"); + + parcArrayList_Destroy(&values); + parcArrayList_Destroy(&list); + parcTreeRedBlack_Destroy(&tree1); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Equals_Empty) +{ + PARCTreeRedBlack *tree1; + PARCTreeRedBlack *tree2; + + tree1 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + tree2 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + assertTrue(parcTreeRedBlack_Equals(tree1, tree2), "Empty lists are not equal"); + + parcTreeRedBlack_Destroy(&tree1); + parcTreeRedBlack_Destroy(&tree2); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Equals_DifferentLength) +{ + PARCTreeRedBlack *tree1; + PARCTreeRedBlack *tree2; + + int compareInserts = 100; + + tree1 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + tree2 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + for (long i = 1; i < compareInserts; i++) { + parcTreeRedBlack_Insert(tree1, + (void *) i, + (void *) (i << 8)); + parcTreeRedBlack_Insert(tree2, + (void *) (compareInserts - i), + (void *) ((compareInserts - i) << 8)); + } + parcTreeRedBlack_Insert(tree2, (void *) (1000), (void *) ((12304) << 8)); + + assertFalse(parcTreeRedBlack_Equals(tree1, tree2), "Lists are equal"); + + parcTreeRedBlack_Destroy(&tree1); + parcTreeRedBlack_Destroy(&tree2); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Equals_Not_Values) +{ + PARCTreeRedBlack *tree1; + PARCTreeRedBlack *tree2; + + int compareInserts = 100; + + tree1 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + tree2 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + for (long i = 1; i < compareInserts; i++) { + parcTreeRedBlack_Insert(tree1, + (void *) i, + (void *) (i << 8)); + parcTreeRedBlack_Insert(tree2, + (void *) (compareInserts - i), + (void *) ((compareInserts + i) << 8)); + } + + assertFalse(parcTreeRedBlack_Equals(tree1, tree2), "Lists are equal"); + + parcTreeRedBlack_Destroy(&tree1); + parcTreeRedBlack_Destroy(&tree2); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Equals_Not_Values_Func) +{ + PARCTreeRedBlack *tree1; + PARCTreeRedBlack *tree2; + + int compareInserts = 100; + + tree1 = parcTreeRedBlack_Create(pointerComp, keyFree, keyCopy, intEquals, valueFree, valueCopy); + tree2 = parcTreeRedBlack_Create(pointerComp, keyFree, keyCopy, intEquals, valueFree, valueCopy); + + for (int i = 1; i < compareInserts; i++) { + parcTreeRedBlack_Insert(tree1, + keyNewInt(i), + valueNewInt(i + 1000)); + parcTreeRedBlack_Insert(tree2, + keyNewInt(i), + valueNewInt(i + 2000)); + } + + assertFalse(parcTreeRedBlack_Equals(tree1, tree2), "Lists are equal"); + + parcTreeRedBlack_Destroy(&tree1); + parcTreeRedBlack_Destroy(&tree2); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Equals_Not_Keys) +{ + PARCTreeRedBlack *tree1; + PARCTreeRedBlack *tree2; + + int compareInserts = 100; + + tree1 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + tree2 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + for (long i = 1; i < compareInserts; i++) { + parcTreeRedBlack_Insert(tree1, + (void *) i, + (void *) (i << 8)); + parcTreeRedBlack_Insert(tree2, + (void *) (compareInserts + i), + (void *) ((compareInserts - i) << 8)); + } + + assertFalse(parcTreeRedBlack_Equals(tree1, tree2), "Lists are equal"); + + parcTreeRedBlack_Destroy(&tree1); + parcTreeRedBlack_Destroy(&tree2); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Equals) +{ + PARCTreeRedBlack *tree1; + PARCTreeRedBlack *tree2; + + int compareInserts = 100; + + tree1 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + tree2 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + for (long i = 1; i < compareInserts; i++) { + parcTreeRedBlack_Insert(tree1, + (void *) i, + (void *) (i << 8)); + parcTreeRedBlack_Insert(tree2, + (void *) (compareInserts - i), + (void *) ((compareInserts - i) << 8)); + } + + assertTrue(parcTreeRedBlack_Equals(tree1, tree2), "Lists are not equal"); + + parcTreeRedBlack_Destroy(&tree1); + parcTreeRedBlack_Destroy(&tree2); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Equals_Func) +{ + PARCTreeRedBlack *tree1; + PARCTreeRedBlack *tree2; + + int compareInserts = 100; + + tree1 = parcTreeRedBlack_Create(intComp, keyFree, keyCopy, intEquals, valueFree, valueCopy); + tree2 = parcTreeRedBlack_Create(intComp, keyFree, keyCopy, intEquals, valueFree, valueCopy); + + for (int i = 1; i < compareInserts; i++) { + parcTreeRedBlack_Insert(tree1, + keyNewInt(i), + valueNewInt(i + 1000)); + parcTreeRedBlack_Insert(tree2, + keyNewInt(i), + valueNewInt(i + 1000)); + } + + assertTrue(parcTreeRedBlack_Equals(tree1, tree2), "Lists are not equal"); + + parcTreeRedBlack_Destroy(&tree1); + parcTreeRedBlack_Destroy(&tree2); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Copy) +{ + PARCTreeRedBlack *tree1; + PARCTreeRedBlack *tree2; + + int compareInserts = 20; + + tree1 = parcTreeRedBlack_Create(intComp, keyFree, keyCopy, intEquals, valueFree, valueCopy); + + for (int i = 1; i < compareInserts; i++) { + void *key = keyNewInt(i); + void *value = valueNewInt(i + 1000); + //value = (void *) &((*(int*)value) + 100); + parcTreeRedBlack_Insert(tree1, key, value); + } + + tree2 = parcTreeRedBlack_Copy(tree1); + + assertTrue(parcTreeRedBlack_Equals(tree1, tree2), "Lists are not equal"); + + parcTreeRedBlack_Destroy(&tree1); + parcTreeRedBlack_Destroy(&tree2); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Copy_Direct) +{ + PARCTreeRedBlack *tree1; + PARCTreeRedBlack *tree2; + + int compareInserts = 20; + + tree1 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + for (long i = 1; i < compareInserts; i++) { + parcTreeRedBlack_Insert(tree1, + (void *) i, + (void *) (i << 8)); + } + + tree2 = parcTreeRedBlack_Copy(tree1); + + assertTrue(parcTreeRedBlack_Equals(tree1, tree2), "Lists are not equal"); + + parcTreeRedBlack_Destroy(&tree1); + parcTreeRedBlack_Destroy(&tree2); +} + +LONGBOW_TEST_FIXTURE(Local) +{ + //LONGBOW_RUN_TEST_CASE(Local, PARC_TreeRedBlack_EnsureRemaining_NonEmpty); +} + +LONGBOW_TEST_FIXTURE_SETUP(Local) +{ + return LONGBOW_STATUS_SUCCEEDED; +} + +LONGBOW_TEST_FIXTURE_TEARDOWN(Local) +{ + return LONGBOW_STATUS_SUCCEEDED; +} + +LONGBOW_TEST_FIXTURE(Stress) +{ + // LongBow could use a command line option to enable/disable tests + // See LongBow issue #5 + if (getenv("LongBowStress")) { + LONGBOW_RUN_TEST_CASE(Stress, PARC_TreeRedBlack_ExerciseRandomSeededSmall); + LONGBOW_RUN_TEST_CASE(Stress, PARC_TreeRedBlack_ExerciseRandomSeeded); + } +} + +LONGBOW_TEST_FIXTURE_SETUP(Stress) +{ + return LONGBOW_STATUS_SUCCEEDED; +} + +LONGBOW_TEST_FIXTURE_TEARDOWN(Stress) +{ + return LONGBOW_STATUS_SUCCEEDED; +} + +LONGBOW_TEST_CASE(Stress, PARC_TreeRedBlack_ExerciseRandomSeededSmall) +{ + PARCTreeRedBlack *tree1; + unsigned seed; + char *seedString; + + seedString = getenv("RBSeed"); + if (seedString) { + seed = (unsigned) atol(seedString); + } else { + seed = 4179329122; // known to fail + } + + for (int j = 0; j < 1; j++) { + // this test case should obtain a seed and number of iterations from a + // command line option once LongBow has that feature available + + printf("Random seed %u\n", seed); + + srandom(seed); + tree1 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + int inserts = 0; + int deletes = 0; + + for (int i = 0; i < 100; i++) { + intptr_t item = 1 + (random() % 100); + int operation = random() % 1000; + if (operation < 400) { + inserts++; + parcTreeRedBlack_Insert(tree1, (void *) item, (void *) (item << 8)); + } else { + deletes++; + parcTreeRedBlack_Remove(tree1, (void *) item); + } + rbCheckTree(tree1); + } + + parcTreeRedBlack_Destroy(&tree1); + } +} + +LONGBOW_TEST_CASE(Stress, PARC_TreeRedBlack_ExerciseRandomSeeded) +{ + PARCTreeRedBlack *tree1; + unsigned seed; + char *seedString; + + // this test case should obtain a seed and number of iterations from a + // command line option once LongBow has that feature available + seedString = getenv("RBSeed"); + if (seedString) { + seed = (unsigned) atol(seedString); + } else { + seed = 4179329122; // known to fail + } + printf("Random seed %u\n", seed); + + srandom(seed); + + tree1 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + int inserts = 0; + int deletes = 0; + + for (int i = 0; i < 100000; i++) { + intptr_t item = 1 + (random() % 10000); + int operation = random() % 1000; + if (operation < 400) { + inserts++; + parcTreeRedBlack_Insert(tree1, (void *) item, (void *) (item << 8)); + } else { + deletes++; + parcTreeRedBlack_Remove(tree1, (void *) item); + } + rbCheckTree(tree1); + } + + parcTreeRedBlack_Destroy(&tree1); +} + +int +main(int argc, char *argv[]) +{ + LongBowRunner *testRunner = LONGBOW_TEST_RUNNER_CREATE(PARC_TreeRedBlack); + int exitStatus = LONGBOW_TEST_MAIN(argc, argv, testRunner); + longBowTestRunner_Destroy(&testRunner); + exit(exitStatus); +} |