aboutsummaryrefslogtreecommitdiffstats
path: root/libparc/parc/algol/test/test_parc_TreeRedBlack.c
diff options
context:
space:
mode:
Diffstat (limited to 'libparc/parc/algol/test/test_parc_TreeRedBlack.c')
-rwxr-xr-xlibparc/parc/algol/test/test_parc_TreeRedBlack.c1462
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);
+}