summaryrefslogtreecommitdiffstats
path: root/libparc/parc/algol/test/test_parc_TreeMap.c
diff options
context:
space:
mode:
Diffstat (limited to 'libparc/parc/algol/test/test_parc_TreeMap.c')
-rwxr-xr-xlibparc/parc/algol/test/test_parc_TreeMap.c1565
1 files changed, 1565 insertions, 0 deletions
diff --git a/libparc/parc/algol/test/test_parc_TreeMap.c b/libparc/parc/algol/test/test_parc_TreeMap.c
new file mode 100755
index 00000000..9355380b
--- /dev/null
+++ b/libparc/parc/algol/test/test_parc_TreeMap.c
@@ -0,0 +1,1565 @@
+/*
+ * 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_TreeMap.c"
+
+
+typedef struct {
+ int value;
+} _Int;
+
+static _Int *
+_int_Copy(const _Int *source);
+
+static bool
+_int_Equals(const _Int *a, const _Int *b)
+{
+ return a->value == b->value;
+}
+
+static int
+_int_Compare(const _Int *a, const _Int *b)
+{
+ int result = 0;
+ if (a->value > b->value) {
+ result = 1;
+ } else if (a->value < b->value) {
+ result = -1;
+ }
+
+ return result;
+}
+
+parcObject_ExtendPARCObject(_Int, NULL, _int_Copy, NULL, _int_Equals, _int_Compare, NULL, NULL);
+
+static
+parcObject_ImplementRelease(_int, _Int);
+
+static _Int *
+_int_Create(const int value)
+{
+ _Int *newObj = parcObject_CreateInstance(_Int);
+ assertNotNull(newObj, "parcMemory_Allocate(%zu) returned NULL", sizeof(int));
+ newObj->value = value;
+ return newObj;
+}
+
+static _Int *
+_int_Copy(const _Int *source)
+{
+ return _int_Create(source->value);
+}
+
+static _Int *
+_int_Set(_Int *obj, const int value)
+{
+ obj->value = value;
+ return obj;
+}
+static PARCBuffer*
+strBuf(char *key)
+{
+ return parcBuffer_WrapCString(key);
+}
+
+
+LONGBOW_TEST_RUNNER(PARC_TreeMap)
+{
+ LONGBOW_RUN_TEST_FIXTURE(Global);
+ LONGBOW_RUN_TEST_FIXTURE(Local);
+ LONGBOW_RUN_TEST_FIXTURE(Stress);
+}
+
+LONGBOW_TEST_RUNNER_SETUP(PARC_TreeMap)
+{
+ parcMemory_SetInterface(&PARCSafeMemoryAsPARCMemory);
+
+ int seed = (int) time(NULL);
+ srandom(seed);
+ return LONGBOW_STATUS_SUCCEEDED;
+}
+
+LONGBOW_TEST_RUNNER_TEARDOWN(PARC_TreeMap)
+{
+ 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_TreeMap_Create);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_Acquire);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_Remove_Ordered);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_Put_Release);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_Put_Ordered);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_Put_OutOfOrder);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_Put_Overwrite);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_ReleaseTillEmpty);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_Size_Empty);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_Size);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_Size_Overwrite);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_Get_EmptyTree);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_Get_NonExistent);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_Get_First);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_Get);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_Get_Last);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_Get_Biggest);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_Get_Smallest);
+
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_FirstKey);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_FirstEntry);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_LastKey);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_LastEntry);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_FirstKey_Empty);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_LastKey_Empty);
+
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_LowerEntry);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_LowerKey);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_HigherEntry);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_HigherKey);
+
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_Remove_First);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_Remove);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_Remove_Last);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_Remove_NonExistent);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_RemoveAndRelease_First);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_RemoveAndRelease);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_RemoveAndRelease_Last);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_RemoveAndRelease_NonExistent);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_Remove_WithSuccessorNonRoot);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_Remove_LeftChildRightChild);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_Keys);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_Values);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_Equals_Empty);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_Equals);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_Equals_DifferentLength);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_Equals_Not_Values);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_Equals_Not_Keys);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_Copy);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_Copy_Direct);
+
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_Iterator);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_ValueIterator);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_KeyIterator);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_Remove_Using_Iterator);
+ LONGBOW_RUN_TEST_CASE(Global, PARC_TreeMap_Remove_Element_Using_Iterator);
+}
+
+#define N_TEST_ELEMENTS 42
+
+typedef struct {
+ PARCTreeMap *testMap1;
+ PARCTreeMap *testMap2;
+ _Int *k[N_TEST_ELEMENTS];
+ _Int *v[N_TEST_ELEMENTS];
+} TestData;
+
+LONGBOW_TEST_FIXTURE_SETUP(Global)
+{
+ TestData *data = parcMemory_AllocateAndClear(sizeof(TestData));
+ assertNotNull(data, "parcMemory_AllocateAndClear(%zu) returned NULL", sizeof(TestData));
+ data->testMap1 = parcTreeMap_Create();
+ data->testMap2 = parcTreeMap_CreateCustom((PARCTreeMap_CustomCompare *) _int_Compare);
+
+ for (int i = 0; i < N_TEST_ELEMENTS; ++i) {
+ data->k[i] = _int_Create(i);
+ data->v[i] = _int_Create(i + 1000);
+ }
+ longBowTestCase_SetClipBoardData(testCase, data);
+
+ return LONGBOW_STATUS_SUCCEEDED;
+}
+
+
+LONGBOW_TEST_FIXTURE_TEARDOWN(Global)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+
+ parcTreeMap_Release(&data->testMap1);
+ parcTreeMap_Release(&data->testMap2);
+
+ for (int i = 0; i < N_TEST_ELEMENTS; ++i) {
+ _int_Release(&(data->k[i]));
+ _int_Release(&(data->v[i]));
+ }
+
+ parcMemory_Deallocate((void **) &data);
+
+ /*
+ * 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
+recursiveCheckBlackDepth(const PARCTreeMap *tree, const _RBNode *node)
+{
+ assertNotNull(tree, "Null tree?\n");
+ assertNotNull(node, "Null node?\n");
+ if (node == tree->nil) {
+ return 0;
+ }
+ int right_depth = recursiveCheckBlackDepth(tree, node->rightChild);
+ int left_depth = recursiveCheckBlackDepth(tree, node->leftChild);
+ assertTrue(right_depth == left_depth, "Wrong depth!!\n");
+ if (_rbNodeColor(node) == BLACK) {
+ return right_depth + 1;
+ }
+ return right_depth;
+}
+
+static
+void
+rbCheckTree(const PARCTreeMap *tree)
+{
+ assertNotNull(tree, "Tree can't be NULL");
+ _rbNodeAssertTreeInvariants(tree);
+ if (tree->size > 0) {
+ recursiveCheckBlackDepth(tree, tree->root);
+ }
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_Remove_Ordered)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+
+ PARCTreeMap *tree1 = data->testMap1;
+
+ for (int i = 0; i < 16; i++) {
+ parcTreeMap_Put(tree1, data->k[i], data->v[i]);
+ }
+
+ for (int i = 0; i < 14; i++) {
+ //rbPrintTreeString(tree1);
+ PARCObject *value = parcTreeMap_Remove(tree1, data->k[i]);
+ assertNotNull(value, "Data is null!");
+ assertTrue(_int_Equals(value, data->v[i]), "Expect the ordered value.");
+ parcObject_Release(&value);
+ }
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_Create)
+{
+ PARCTreeMap *map = parcTreeMap_Create();
+ parcTreeMap_Release(&map);
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_Acquire)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+ PARCTreeMap *map = parcTreeMap_Acquire(data->testMap1);
+ parcTreeMap_Release(&map);
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_Put_Release)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+
+ PARCTreeMap *tree = data->testMap1;
+
+ PARCBuffer *value1 = strBuf("value 1");
+ PARCBuffer *key1 = strBuf("1");
+ PARCBuffer *value2 = strBuf("value 2");
+ PARCBuffer *key2 = strBuf("2");
+ PARCBuffer *value3 = strBuf("value 3");
+ PARCBuffer *key3 = strBuf("3");
+
+ parcTreeMap_Put(tree, key1, value1);
+ parcTreeMap_Put(tree, key2, value2);
+ parcTreeMap_Put(tree, key3, value3);
+
+ parcBuffer_Release(&key1);
+ parcBuffer_Release(&value1);
+ parcBuffer_Release(&key2);
+ parcBuffer_Release(&value2);
+ parcBuffer_Release(&key3);
+ parcBuffer_Release(&value3);
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_Put_Overwrite)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+
+ PARCTreeMap *tree = data->testMap1;
+
+ parcTreeMap_Put(tree, data->k[1], data->v[1]);
+ parcTreeMap_Put(tree, data->k[2], data->v[2]);
+ parcTreeMap_Put(tree, data->k[3], data->v[3]);
+ parcTreeMap_Put(tree, data->k[3], data->v[4]);
+ parcTreeMap_Put(tree, data->k[3], data->v[5]);
+
+ assertTrue(3 == parcTreeMap_Size(tree), "Wrong size of tree should stay at 3");
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_Put_Ordered)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+
+ PARCTreeMap *tree = data->testMap1;
+
+ parcTreeMap_Put(tree, data->k[1], data->v[1]);
+ parcTreeMap_Put(tree, data->k[2], data->v[2]);
+ parcTreeMap_Put(tree, data->k[3], data->v[3]);
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_Put_OutOfOrder)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+
+ PARCTreeMap *tree1 = data->testMap1;
+
+ parcTreeMap_Put(tree1, data->k[4], data->v[4]);
+ parcTreeMap_Put(tree1, data->k[2], data->v[2]);
+ parcTreeMap_Put(tree1, data->k[3], data->v[3]);
+ parcTreeMap_Put(tree1, data->k[1], data->v[1]);
+
+ PARCTreeMap *tree2 = data->testMap2;
+ parcTreeMap_Put(tree2, data->k[1], data->v[1]);
+ parcTreeMap_Put(tree2, data->k[3], data->v[3]);
+ parcTreeMap_Put(tree2, data->k[2], data->v[2]);
+ parcTreeMap_Put(tree2, data->k[4], data->v[4]);
+
+ assertTrue(parcTreeMap_Equals(tree1, tree2), "Expect trees to be Equal");
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_Size_Empty)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+
+ PARCTreeMap *tree = data->testMap1;
+
+ assertTrue(0 == parcTreeMap_Size(tree), "Wrong size of tree - empty, start");
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_Size)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+
+ PARCTreeMap *tree = data->testMap1;
+
+ parcTreeMap_Put(tree, data->k[4], data->v[4]);
+ parcTreeMap_Put(tree, data->k[2], data->v[2]);
+ parcTreeMap_Put(tree, data->k[3], data->v[3]);
+
+ assertTrue(3 == parcTreeMap_Size(tree), "Wrong size of tree after add 3");
+
+ parcTreeMap_Put(tree, data->k[1], data->v[1]);
+
+ assertTrue(4 == parcTreeMap_Size(tree), "Wrong size of tree after add 1 more");
+
+ parcTreeMap_RemoveAndRelease(tree, data->k[2]);
+
+ size_t size = parcTreeMap_Size(tree);
+
+ assertTrue(3 == size, "Wrong size of tree after 1 delete (%zu instead of 3)", size);
+
+ parcTreeMap_Put(tree, data->k[7], data->v[7]);
+
+ assertTrue(4 == parcTreeMap_Size(tree), "Wrong size of tree after add 1 more");
+
+ parcTreeMap_RemoveAndRelease(tree, data->k[3]);
+ assertTrue(3 == parcTreeMap_Size(tree), "Wrong size of tree after del 1 more - 3");
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_ReleaseTillEmpty)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+
+ PARCTreeMap *tree1 = data->testMap1;
+ PARCTreeMap *tree2 = data->testMap2;
+
+ // This order of puts are removes exercises code paths
+ // in TreeMap not exercised in any other place.
+ int idx1a[7] = { 4, 2, 3, 1, 5, 7, 6 };
+ int idx1b[7] = { 3, 1, 4, 2, 6, 5, 7 };
+ int idx2a[7] = { 4, 6, 5, 7, 3, 1, 2 };
+ int idx2b[7] = { 5, 7, 4, 6, 2, 3, 1 };
+
+ for (int i = 0; i < 7; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree1, data->k[idx1a[i]], data->v[idx1a[i]]);
+ parcTreeMap_Put(tree2, data->k[idx2a[i]], data->v[idx2a[i]]);
+ }
+
+ for (int i = 0; i < 7; ++i) {
+ parcTreeMap_RemoveAndRelease(tree1, data->k[idx1b[i]]);
+ parcTreeMap_RemoveAndRelease(tree2, data->k[idx2b[i]]);
+ }
+
+ size_t size;
+ size = parcTreeMap_Size(tree1);
+
+ assertTrue(0 == size, "Wrong size of tree - empty (got %zu)", size);
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_Size_Overwrite)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+
+ PARCTreeMap *tree = data->testMap1;
+
+ parcTreeMap_Put(tree, data->k[4], data->v[4]);
+ parcTreeMap_Put(tree, data->k[2], data->v[2]);
+ parcTreeMap_Put(tree, data->k[3], data->v[3]);
+
+ // Size is 3 here, we'll insert the same number now..
+
+ parcTreeMap_Put(tree, data->k[3], data->v[23]);
+
+ assertTrue(3 == parcTreeMap_Size(tree), "Wrong size of tree after overwrite");
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_Get_EmptyTree)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+
+ PARCTreeMap *tree = data->testMap1;
+
+ PARCObject *value = parcTreeMap_Get(tree, data->k[1]);
+
+ assertTrue(NULL == value, "Object did not exist, must return NULL");
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_Get_NonExistent)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+
+ PARCTreeMap *tree = data->testMap1;
+
+ for (long i = 1; i < 10; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree, data->k[i], data->v[i]);
+ }
+
+ PARCObject *value = parcTreeMap_Get(tree, data->k[23]);
+
+ assertTrue(NULL == value, "Object did not exist, must return NULL");
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_Get_First)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+ PARCTreeMap *tree = data->testMap1;
+
+ for (long i = 1; i < 4; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree, data->k[i], data->v[i]);
+ }
+
+ PARCObject *value = parcTreeMap_Get(tree, data->k[1]);
+
+ assertTrue(_int_Equals(data->v[1], value), "Wrong value, got %ld", (long) value);
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_Get)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+ PARCTreeMap *tree = data->testMap1;
+
+ for (long i = 1; i < 10; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree, data->k[i], data->v[i]);
+ }
+
+ PARCObject *value = parcTreeMap_Get(tree, data->k[4]);
+
+ assertTrue(_int_Equals(data->v[4], value), "Wrong value, got %ld", (long) value);
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_Get_Last)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+ PARCTreeMap *tree = data->testMap1;
+
+ for (long i = 1; i < 10; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree, data->k[i], data->v[i]);
+ }
+
+ PARCObject *value = parcTreeMap_Get(tree, data->k[9]);
+
+ assertTrue(_int_Equals(data->v[9], value), "Wrong value, got %ld", (long) value);
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_Get_Smallest)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+ PARCTreeMap *tree = data->testMap1;
+
+ for (long i = 30; i < 40; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree, data->k[i], data->v[i]);
+ }
+ for (long i = 1; i < 10; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree, data->k[i], data->v[i]);
+ }
+ for (long i = 20; i < 30; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree, data->k[i], data->v[i]);
+ }
+
+
+ PARCObject *value = parcTreeMap_Get(tree, data->k[1]);
+
+ assertTrue(_int_Equals(data->v[1], value), "Wrong value, got %ld", (long) value);
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_Get_Biggest)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+ PARCTreeMap *tree = data->testMap1;
+
+ for (long i = 30; i < 40; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree, data->k[i], data->v[i]);
+ }
+ for (long i = 1; i < 10; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree, data->k[i], data->v[i]);
+ }
+ for (long i = 20; i < 30; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree, data->k[i], data->v[i]);
+ }
+
+ PARCObject *value = parcTreeMap_Get(tree, data->k[39]);
+
+ assertTrue(_int_Equals(data->v[39], value), "Wrong value, got %ld", (long) value);
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_FirstEntry)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+ PARCTreeMap *tree = data->testMap1;
+
+ for (long i = 30; i < 40; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree, data->k[i], data->v[i]);
+ }
+ for (long i = 1; i < 10; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree, data->k[i], data->v[i]);
+ }
+ for (long i = 20; i < 30; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree, data->k[i], data->v[i]);
+ }
+
+ PARCKeyValue *entry = parcTreeMap_GetFirstEntry(tree);
+
+ assertTrue(_int_Equals(data->k[1], parcKeyValue_GetKey(entry)),
+ "Wrong value, got %ld", (long) parcKeyValue_GetKey(entry));
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_FirstKey)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+ PARCTreeMap *tree = data->testMap1;
+
+ for (long i = 30; i < 40; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree, data->k[i], data->v[i]);
+ }
+ for (long i = 1; i < 10; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree, data->k[i], data->v[i]);
+ }
+ for (long i = 20; i < 30; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree, data->k[i], data->v[i]);
+ }
+
+ PARCObject *key = parcTreeMap_GetFirstKey(tree);
+
+ assertTrue(_int_Equals(data->k[1], key), "Wrong value, got %ld", (long) key);
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_FirstKey_Empty)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+ PARCTreeMap *tree = data->testMap1;
+
+ PARCObject *key = parcTreeMap_GetFirstKey(tree);
+
+ assertNull(key, "Should get NULL on empty tree");
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_LastKey_Empty)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+ PARCTreeMap *tree = data->testMap1;
+
+ PARCObject *key = parcTreeMap_GetLastKey(tree);
+
+ assertNull(key, "Should get NULL on empty tree");
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_LastEntry)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+ PARCTreeMap *tree = data->testMap1;
+
+ for (long i = 30; i < 40; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree, data->k[i], data->v[i]);
+ }
+ for (long i = 1; i < 10; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree, data->k[i], data->v[i]);
+ }
+ for (long i = 20; i < 30; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree, data->k[i], data->v[i]);
+ }
+
+ PARCKeyValue *entry = parcTreeMap_GetLastEntry(tree);
+
+ assertTrue(_int_Equals(data->k[39], parcKeyValue_GetKey(entry)),
+ "Wrong value, got %ld", (long) parcKeyValue_GetKey(entry));
+}
+
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_LastKey)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+ PARCTreeMap *tree = data->testMap1;
+
+ for (long i = 30; i < 40; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree, data->k[i], data->v[i]);
+ }
+ for (long i = 1; i < 10; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree, data->k[i], data->v[i]);
+ }
+ for (long i = 20; i < 30; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree, data->k[i], data->v[i]);
+ }
+
+ PARCObject *key = parcTreeMap_GetLastKey(tree);
+
+ assertTrue(_int_Equals(data->k[39], key), "Wrong value, got %ld", (long) key);
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_Remove_First)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+
+ PARCTreeMap *tree1 = data->testMap1;
+ PARCTreeMap *tree2 = data->testMap2;
+
+ for (int i = 30; i < 40; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree1, data->k[i], data->v[i]);
+ parcTreeMap_Put(tree2, data->k[i], data->v[i]);
+ }
+
+ parcTreeMap_Put(tree1, data->k[1], data->v[1]);
+
+ for (int i = 2; i < 10; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree1, data->k[i], data->v[i]);
+ parcTreeMap_Put(tree2, data->k[i], data->v[i]);
+ }
+
+ for (int i = 20; i < 30; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree1, data->k[i], data->v[i]);
+ parcTreeMap_Put(tree2, data->k[i], data->v[i]);
+ }
+
+ PARCObject *value = parcTreeMap_Remove(tree1, data->k[1]);
+ parcObject_Release(&value);
+
+ assertTrue(parcTreeMap_Equals(tree1, tree2), "Trees dont match after remove");
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_Remove)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+
+ PARCTreeMap *tree1 = data->testMap1;
+ PARCTreeMap *tree2 = data->testMap2;
+
+ for (int i = 31; i < 40; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree1, data->k[i], data->v[i]);
+ parcTreeMap_Put(tree2, data->k[i], data->v[i]);
+ }
+
+ parcTreeMap_Put(tree1, data->k[30], data->v[30]);
+
+ for (int i = 2; i < 10; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree1, data->k[i], data->v[i]);
+ parcTreeMap_Put(tree2, data->k[i], data->v[i]);
+ }
+
+ for (int i = 20; i < 30; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree1, data->k[i], data->v[i]);
+ parcTreeMap_Put(tree2, data->k[i], data->v[i]);
+ }
+
+ PARCObject *value = parcTreeMap_Remove(tree1, data->k[30]);
+ parcObject_Release(&value);
+
+ assertTrue(parcTreeMap_Equals(tree1, tree2), "Trees dont match after remove");
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_Remove_Last)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+
+ PARCTreeMap *tree1 = data->testMap1;
+ PARCTreeMap *tree2 = data->testMap2;
+
+ for (int i = 30; i < 40; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree1, data->k[i], data->v[i]);
+ parcTreeMap_Put(tree2, data->k[i], data->v[i]);
+ }
+
+ parcTreeMap_Put(tree1, data->k[41], data->v[41]);
+
+ for (int i = 2; i < 10; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree1, data->k[i], data->v[i]);
+ parcTreeMap_Put(tree2, data->k[i], data->v[i]);
+ }
+ for (int i = 20; i < 30; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree1, data->k[i], data->v[i]);
+ parcTreeMap_Put(tree2, data->k[i], data->v[i]);
+ }
+
+ PARCObject *value = parcTreeMap_Remove(tree1, data->k[41]);
+ assertNotNull(value, "Expected to find some object.");
+ assertTrue(_int_Equals(data->v[41], value), "Expected value 41 in return");
+ parcObject_Release(&value);
+
+ assertTrue(parcTreeMap_Equals(tree1, tree2), "Trees don't match after remove");
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_RemoveAndRelease_First)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+
+ PARCTreeMap *tree1 = data->testMap1;
+ PARCTreeMap *tree2 = data->testMap2;
+
+ for (int i = 30; i < 40; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree1, data->k[i], data->v[i]);
+ parcTreeMap_Put(tree2, data->k[i], data->v[i]);
+ }
+
+ parcTreeMap_Put(tree1, data->k[1], data->v[1]);
+
+ for (int i = 2; i < 10; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree1, data->k[i], data->v[i]);
+ parcTreeMap_Put(tree2, data->k[i], data->v[i]);
+ }
+ for (int i = 20; i < 30; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree1, data->k[i], data->v[i]);
+ parcTreeMap_Put(tree2, data->k[i], data->v[i]);
+ }
+
+ parcTreeMap_RemoveAndRelease(tree1, data->k[1]);
+
+ assertTrue(parcTreeMap_Equals(tree1, tree2), "Trees dont match after remove");
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_RemoveAndRelease)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+
+ PARCTreeMap *tree1 = data->testMap1;
+ PARCTreeMap *tree2 = data->testMap2;
+
+ for (int i = 31; i < 40; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree1, data->k[i], data->v[i]);
+ parcTreeMap_Put(tree2, data->k[i], data->v[i]);
+ }
+
+ parcTreeMap_Put(tree1, data->k[30], data->v[30]);
+
+ for (int i = 2; i < 10; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree1, data->k[i], data->v[i]);
+ parcTreeMap_Put(tree2, data->k[i], data->v[i]);
+ }
+ for (int i = 20; i < 30; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree1, data->k[i], data->v[i]);
+ parcTreeMap_Put(tree2, data->k[i], data->v[i]);
+ }
+
+ parcTreeMap_RemoveAndRelease(tree1, data->k[30]);
+ assertTrue(parcTreeMap_Equals(tree1, tree2), "Trees dont match after remove");
+
+ for (int i = 20; i < 30; i++) {
+ parcTreeMap_RemoveAndRelease(tree1, data->k[i]);
+ parcTreeMap_RemoveAndRelease(tree2, data->k[49 - i]);
+ }
+ assertTrue(parcTreeMap_Equals(tree1, tree2), "Trees dont match after remove");
+
+ for (int i = 2; i < 10; i++) {
+ parcTreeMap_RemoveAndRelease(tree1, data->k[i]);
+ parcTreeMap_RemoveAndRelease(tree2, data->k[11 - i]);
+ }
+ assertTrue(parcTreeMap_Equals(tree1, tree2), "Trees dont match after remove");
+
+ for (int i = 31; i < 40; i++) {
+ parcTreeMap_RemoveAndRelease(tree1, data->k[i]);
+ parcTreeMap_RemoveAndRelease(tree2, data->k[70 - i]);
+ }
+ assertTrue(parcTreeMap_Equals(tree1, tree2), "Trees dont match after remove");
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_Remove_NonExistent)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+
+ PARCTreeMap *tree1 = data->testMap1;
+ PARCTreeMap *tree2 = data->testMap2;
+
+ for (int i = 30; i < 40; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree1, data->k[i], data->v[i]);
+ parcTreeMap_Put(tree2, data->k[i], data->v[i]);
+ }
+ for (int i = 2; i < 10; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree1, data->k[i], data->v[i]);
+ parcTreeMap_Put(tree2, data->k[i], data->v[i]);
+ }
+ for (int i = 20; i < 30; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree1, data->k[i], data->v[i]);
+ parcTreeMap_Put(tree2, data->k[i], data->v[i]);
+ }
+
+ PARCObject *element = parcTreeMap_Remove(tree1, data->k[0]);
+
+ assertNull(element, "Return value must be NULL on non existing element");
+ assertTrue(parcTreeMap_Equals(tree1, tree2), "Trees dont match after remove");
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_RemoveAndRelease_NonExistent)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+
+ PARCTreeMap *tree1 = data->testMap1;
+ PARCTreeMap *tree2 = data->testMap2;
+
+ for (int i = 30; i < 40; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree1, data->k[i], data->v[i]);
+ parcTreeMap_Put(tree2, data->k[i], data->v[i]);
+ }
+ for (int i = 2; i < 10; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree1, data->k[i], data->v[i]);
+ parcTreeMap_Put(tree2, data->k[i], data->v[i]);
+ }
+ for (int i = 20; i < 30; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree1, data->k[i], data->v[i]);
+ parcTreeMap_Put(tree2, data->k[i], data->v[i]);
+ }
+
+ parcTreeMap_RemoveAndRelease(tree1, data->k[0]);
+
+ assertTrue(parcTreeMap_Equals(tree1, tree2), "Trees dont match after remove");
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_Remove_WithSuccessorNonRoot)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+ PARCTreeMap *tree1 = data->testMap1;
+ PARCTreeMap *tree2 = data->testMap2;
+
+ int idx1[15] = { 8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15 };
+ int idx2[13] = { 8, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15 };
+
+ for (int i = 0; i < 15; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree1, data->k[idx1[i]], data->v[idx1[i]]);
+ }
+
+ for (int i = 0; i < 13; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree2, data->k[idx2[i]], data->v[idx2[i]]);
+ }
+
+ _Int *key = _int_Create(4);
+ parcTreeMap_RemoveAndRelease(tree1, key);
+ parcTreeMap_RemoveAndRelease(tree1, _int_Set(key, 12));
+ _int_Release(&key);
+
+ assertTrue(parcTreeMap_Equals(tree1, tree2), "Trees dont match after remove");
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_Remove_LeftChildRightChild)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+ PARCTreeMap *tree1 = data->testMap1;
+ PARCTreeMap *tree2 = data->testMap2;
+
+ int idx1[15] = { 8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15 };
+
+ for (int i = 0; i < 15; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree1, data->k[idx1[i]], data->v[idx1[i]]);
+ parcTreeMap_Put(tree2, data->k[idx1[i]], data->v[idx1[i]]);
+ }
+
+ _Int *key = _int_Create(0);
+ parcTreeMap_RemoveAndRelease(tree1, _int_Set(key, 13));
+ parcTreeMap_RemoveAndRelease(tree1, _int_Set(key, 7));
+ parcTreeMap_RemoveAndRelease(tree1, _int_Set(key, 14));
+ parcTreeMap_RemoveAndRelease(tree1, _int_Set(key, 6));
+ parcTreeMap_RemoveAndRelease(tree1, _int_Set(key, 15));
+ parcTreeMap_RemoveAndRelease(tree1, _int_Set(key, 12));
+ parcTreeMap_RemoveAndRelease(tree1, _int_Set(key, 11));
+ parcTreeMap_RemoveAndRelease(tree1, _int_Set(key, 10));
+ parcTreeMap_RemoveAndRelease(tree1, _int_Set(key, 9));
+ parcTreeMap_RemoveAndRelease(tree1, _int_Set(key, 8));
+ parcTreeMap_RemoveAndRelease(tree1, _int_Set(key, 5));
+ parcTreeMap_RemoveAndRelease(tree1, _int_Set(key, 4));
+ parcTreeMap_RemoveAndRelease(tree1, _int_Set(key, 3));
+ parcTreeMap_RemoveAndRelease(tree1, _int_Set(key, 2));
+ parcTreeMap_RemoveAndRelease(tree1, _int_Set(key, 1));
+
+ parcTreeMap_RemoveAndRelease(tree2, _int_Set(key, 1));
+ parcTreeMap_RemoveAndRelease(tree2, _int_Set(key, 2));
+ parcTreeMap_RemoveAndRelease(tree2, _int_Set(key, 3));
+ parcTreeMap_RemoveAndRelease(tree2, _int_Set(key, 4));
+ parcTreeMap_RemoveAndRelease(tree2, _int_Set(key, 5));
+ parcTreeMap_RemoveAndRelease(tree2, _int_Set(key, 6));
+ parcTreeMap_RemoveAndRelease(tree2, _int_Set(key, 7));
+ parcTreeMap_RemoveAndRelease(tree2, _int_Set(key, 8));
+ parcTreeMap_RemoveAndRelease(tree2, _int_Set(key, 9));
+ parcTreeMap_RemoveAndRelease(tree2, _int_Set(key, 10));
+ parcTreeMap_RemoveAndRelease(tree2, _int_Set(key, 11));
+ parcTreeMap_RemoveAndRelease(tree2, _int_Set(key, 12));
+ parcTreeMap_RemoveAndRelease(tree2, _int_Set(key, 13));
+ parcTreeMap_RemoveAndRelease(tree2, _int_Set(key, 14));
+ parcTreeMap_RemoveAndRelease(tree2, _int_Set(key, 15));
+ _int_Release(&key);
+
+ assertTrue(parcTreeMap_Equals(tree1, tree2), "Trees dont match after remove");
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_RemoveAndRelease_Last)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+ PARCTreeMap *tree1 = data->testMap1;
+ PARCTreeMap *tree2 = data->testMap2;
+
+ for (int i = 30; i < 40; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree1, data->k[i], data->v[i]);
+ parcTreeMap_Put(tree2, data->k[i], data->v[i]);
+ }
+ parcTreeMap_Put(tree1, data->k[41], data->v[41]);
+ for (int i = 2; i < 10; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree1, data->k[i], data->v[i]);
+ parcTreeMap_Put(tree2, data->k[i], data->v[i]);
+ }
+ for (int i = 20; i < 30; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree1, data->k[i], data->v[i]);
+ parcTreeMap_Put(tree2, data->k[i], data->v[i]);
+ }
+
+ parcTreeMap_RemoveAndRelease(tree1, data->k[41]);
+
+ assertTrue(parcTreeMap_Equals(tree1, tree2), "Trees dont match after remove");
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_LowerEntry)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+ PARCTreeMap *tree1 = data->testMap1;
+
+ // Empty Tree
+ PARCKeyValue *kv = parcTreeMap_GetLowerEntry(tree1, data->k[23]);
+ assertNull(kv, "Expected a NULL return for LowerEntry() on empty tree");
+
+ // Fill Tree
+ int max = N_TEST_ELEMENTS - 1;
+ for (int i = 21; i <= max; ++i) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree1, data->k[i], data->v[i]);
+ }
+ for (int i = 1; i < 21; ++i) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree1, data->k[i], data->v[i]);
+ }
+
+ // Using lowest key in tree
+ kv = parcTreeMap_GetLowerEntry(tree1, data->k[1]);
+ assertNull(kv, "Expected a NULL return for no lower entry");
+
+ // On all entries except the lowest tree
+ for (int i = max; i > 1; --i) {
+ kv = parcTreeMap_GetLowerEntry(tree1, data->k[i]);
+ assertNotNull(kv, "Expected a lower entry to exist");
+ _Int *key = (_Int *) parcKeyValue_GetKey(kv);
+ assertTrue(_int_Equals(key, data->k[i - 1]),
+ "Expected entry with key %d, got %d",
+ data->k[i - 1]->value, key->value);
+ }
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_LowerKey)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+ PARCTreeMap *tree1 = data->testMap1;
+
+ // Empty Tree
+ _Int *key = (_Int *) parcTreeMap_GetLowerKey(tree1, data->k[23]);
+ assertNull(key, "Expected a NULL return for LowerEntry() on empty tree");
+
+ int max = N_TEST_ELEMENTS - 1;
+ for (int i = 21; i <= max; ++i) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree1, data->k[i], data->v[i]);
+ }
+ for (int i = 1; i < 21; ++i) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree1, data->k[i], data->v[i]);
+ }
+
+ // Using lowest key in tree
+ key = (_Int *) parcTreeMap_GetLowerKey(tree1, data->k[1]);
+ assertNull(key, "Expected a NULL return for no lower entry");
+
+ // On all entries except the lowest tree
+ for (int i = max; i > 1; --i) {
+ key = parcTreeMap_GetLowerKey(tree1, data->k[i]);
+ assertNotNull(key, "Expected a lower entry to exist");
+ assertTrue(_int_Equals(key, data->k[i - 1]),
+ "Expected entry with key %d, got %d",
+ data->k[i - 1]->value, key->value);
+ }
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_HigherEntry)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+ PARCTreeMap *tree1 = data->testMap1;
+
+ // Empty Tree
+ PARCKeyValue *kv = parcTreeMap_GetHigherEntry(tree1, data->k[23]);
+ assertNull(kv, "Expected a NULL return for HigherEntry() on empty tree");
+
+ int max = N_TEST_ELEMENTS - 2;
+ for (int i = 21; i <= max; ++i) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree1, data->k[i], data->v[i]);
+ }
+ for (int i = 1; i < 21; ++i) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree1, data->k[i], data->v[i]);
+ }
+
+ // Using highest key in tree
+ kv = parcTreeMap_GetHigherEntry(tree1, data->k[max]);
+ assertNull(kv, "Expected a NULL return for no higher entry");
+
+ // On all entries except the lowest tree
+ for (int i = 1; i < max; ++i) {
+ kv = parcTreeMap_GetHigherEntry(tree1, data->k[i]);
+ assertNotNull(kv, "Expected a higher entry to exist");
+ _Int *key = (_Int *) parcKeyValue_GetKey(kv);
+ assertTrue(_int_Equals(key, data->k[i + 1]),
+ "Expected entry with key %d, got %d",
+ data->k[i + 1]->value, key->value);
+ }
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_HigherKey)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+ PARCTreeMap *tree1 = data->testMap1;
+
+ // Empty Tree
+ _Int *key = (_Int *) parcTreeMap_GetHigherKey(tree1, data->k[23]);
+ assertNull(key, "Expected a NULL return for LowerEntry() on empty tree");
+
+ int max = N_TEST_ELEMENTS - 2;
+ for (int i = 21; i <= max; ++i) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree1, data->k[i], data->v[i]);
+ }
+ for (int i = 1; i < 21; ++i) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree1, data->k[i], data->v[i]);
+ }
+
+ key = (_Int *) parcTreeMap_GetHigherEntry(tree1, data->k[max]);
+ assertNull(key, "Expected a NULL return for no higher entry");
+
+ for (int i = 1; i < max; ++i) {
+ key = (_Int *) parcTreeMap_GetHigherKey(tree1, data->k[i]);
+ assertNotNull(key, "Expected a higher entry to exist");
+ assertTrue(_int_Equals(key, data->k[i + 1]),
+ "Expected entry with key %d, got %d",
+ data->k[i + 1]->value, key->value);
+ }
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_Keys)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+
+ PARCTreeMap *tree1 = data->testMap1;
+
+ PARCList *list = parcList(parcArrayList_Create(NULL), PARCArrayListAsPARCList);
+
+ // Insert in tree out of order
+ for (int i = 10; i < 20; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree1, data->k[i], data->v[i]);
+ }
+ for (int i = 1; i < 10; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree1, data->k[i], data->v[i]);
+ }
+
+ // Insert in list in order
+ for (int i = 1; i < 20; i++) {
+ // Add some elements to the tree
+ parcList_Add(list, data->k[i]);
+ }
+
+ PARCList *keys = parcTreeMap_AcquireKeys(tree1);
+
+ assertTrue(parcList_Equals(list, keys), "Key list doesnt' match");
+
+ parcList_Release(&keys);
+ parcList_Release(&list);
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_Values)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+
+ PARCTreeMap *tree1 = data->testMap1;
+
+ PARCList *list = parcList(parcArrayList_Create(NULL), PARCArrayListAsPARCList);
+
+ // Insert in tree out of order
+ for (int i = 10; i < 20; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree1, data->k[i], data->v[i]);
+ }
+ for (int i = 1; i < 10; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree1, data->k[i], data->v[i]);
+ }
+
+ // Insert in list in order
+ for (int i = 1; i < 20; i++) {
+ // Add some elements to the tree
+ parcList_Add(list, data->v[i]);
+ }
+
+ PARCList *values = parcTreeMap_AcquireValues(tree1);
+
+ assertTrue(parcList_Equals(list, values), "Key list doesnt' match");
+
+ parcList_Release(&values);
+ parcList_Release(&list);
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_Equals_Empty)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+
+ PARCTreeMap *tree1 = data->testMap1;
+ PARCTreeMap *tree2 = data->testMap2;
+
+ assertTrue(parcTreeMap_Equals(tree1, tree2), "Empty lists are not equal");
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_Equals_DifferentLength)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+
+ PARCTreeMap *tree1 = data->testMap1;
+ PARCTreeMap *tree2 = data->testMap2;
+
+
+ for (int i = 1; i < 20; i++) {
+ parcTreeMap_Put(tree1, data->k[i], data->v[i]);
+ parcTreeMap_Put(tree2, data->k[i], data->v[i]);
+ }
+
+ parcTreeMap_Put(tree2, data->k[41], data->v[41]);
+
+ assertFalse(parcTreeMap_Equals(tree1, tree2), "Lists are equal");
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_Equals_Not_Values)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+
+ PARCTreeMap *tree1 = data->testMap1;
+ PARCTreeMap *tree2 = data->testMap2;
+
+ for (int i = 1; i < 20; i++) {
+ parcTreeMap_Put(tree1, data->k[i], data->v[i]);
+ parcTreeMap_Put(tree2, data->k[i], data->v[20 - i]);
+ }
+
+ assertFalse(parcTreeMap_Equals(tree1, tree2), "Lists are equal");
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_Equals_Not_Keys)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+
+ PARCTreeMap *tree1 = data->testMap1;
+ PARCTreeMap *tree2 = data->testMap2;
+
+ for (int i = 1; i < 20; i++) {
+ parcTreeMap_Put(tree1, data->k[i], data->v[i]);
+ parcTreeMap_Put(tree2, data->k[i + 1], data->v[i]);
+ }
+ assertTrue(parcTreeMap_Size(tree1) == parcTreeMap_Size(tree2), "Expect trees to have the same size.");
+
+ assertFalse(parcTreeMap_Equals(tree1, tree2), "Lists should not be equal");
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_Equals)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+
+ PARCTreeMap *tree1 = data->testMap1;
+ PARCTreeMap *tree2 = data->testMap2;
+
+ for (int i = 1; i < 40; i++) {
+ parcTreeMap_Put(tree1, data->k[i], data->v[i]);
+ parcTreeMap_Put(tree2, data->k[40 - i], data->v[40 - i]);
+ }
+
+ assertTrue(parcTreeMap_Equals(tree1, tree2), "Lists are not equal");
+}
+
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_Copy)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+
+ PARCTreeMap *tree1 = data->testMap1;
+ PARCTreeMap *treeCopy = parcTreeMap_Copy(tree1);
+
+ for (int i = 1; i < 10; i++) {
+ parcTreeMap_Put(tree1, data->k[i], data->v[i]);
+ }
+
+ assertFalse(parcTreeMap_Equals(tree1, treeCopy), "Lists are not equal");
+
+ parcTreeMap_Release(&treeCopy);
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_Copy_Direct)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+ PARCTreeMap *tree1 = data->testMap1;
+
+ for (int i = 1; i < 20; i++) {
+ parcTreeMap_Put(tree1, data->k[i], data->v[i]);
+ }
+
+ PARCTreeMap *treeCopy = parcTreeMap_Copy(tree1);
+
+ assertTrue(parcTreeMap_Equals(tree1, treeCopy), "Lists are not equal");
+
+ parcTreeMap_Release(&treeCopy);
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_ValueIterator)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+ PARCTreeMap *tree1 = data->testMap1;
+
+ int idx1[15] = { 8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15 };
+
+ for (int i = 0; i < 15; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree1, data->k[idx1[i]], data->v[idx1[i]]);
+ }
+
+ PARCIterator *it = parcTreeMap_CreateValueIterator(tree1);
+
+ for (int idx = 1; parcIterator_HasNext(it); ++idx) {
+ _Int *value = (_Int *) parcIterator_Next(it);
+ assertTrue(_int_Equals(value, data->v[idx]), "Expected value %d got %d", data->v[idx]->value, value->value);
+ }
+
+ parcIterator_Release(&it);
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_KeyIterator)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+ PARCTreeMap *tree1 = data->testMap1;
+
+ int idx1[15] = { 8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15 };
+
+ for (int i = 0; i < 15; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree1, data->k[idx1[i]], data->v[idx1[i]]);
+ }
+
+ PARCIterator *it = parcTreeMap_CreateKeyIterator(tree1);
+
+ for (int idx = 1; parcIterator_HasNext(it); ++idx) {
+ _Int *key = (_Int *) parcIterator_Next(it);
+ assertTrue(_int_Equals(key, data->k[idx]),
+ "Expected value %d got %d",
+ data->k[idx]->value,
+ key->value);
+ }
+
+ parcIterator_Release(&it);
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_Iterator)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+ PARCTreeMap *tree1 = data->testMap1;
+
+ int idx1[15] = { 8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15 };
+
+ for (int i = 0; i < 15; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree1, data->k[idx1[i]], data->v[idx1[i]]);
+ }
+
+ PARCIterator *it = parcTreeMap_CreateKeyValueIterator(tree1);
+
+ for (int idx = 1; parcIterator_HasNext(it); ++idx) {
+ PARCKeyValue *kv = (PARCKeyValue *) parcIterator_Next(it);
+ assertTrue(_int_Equals((_Int *) parcKeyValue_GetKey(kv), data->k[idx]),
+ "Expected value %d got %d",
+ data->k[idx]->value,
+ ((_Int *) parcKeyValue_GetKey(kv))->value);
+ }
+
+ parcIterator_Release(&it);
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_Remove_Using_Iterator)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+ PARCTreeMap *tree1 = data->testMap1;
+
+ int idx1[15] = { 8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15 };
+
+ for (int i = 0; i < 15; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree1, data->k[idx1[i]], data->v[idx1[i]]);
+ }
+
+ PARCIterator *it = parcTreeMap_CreateKeyValueIterator(tree1);
+ for (int idx = 1; parcIterator_HasNext(it); ++idx) {
+ parcIterator_Next(it);
+ parcIterator_Remove(it);
+ }
+ parcIterator_Release(&it);
+
+ assertTrue(parcTreeMap_Size(tree1) == 0, "Expect the tree to be empty after removes.");
+}
+
+LONGBOW_TEST_CASE(Global, PARC_TreeMap_Remove_Element_Using_Iterator)
+{
+ TestData *data = longBowTestCase_GetClipBoardData(testCase);
+ PARCTreeMap *tree1 = data->testMap1;
+ PARCTreeMap *tree2 = data->testMap1;
+
+ int idx1[15] = { 8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 15, 13 }; //Missing 11
+
+ for (int i = 0; i < 14; i++) {
+ // Add some elements to the tree
+ parcTreeMap_Put(tree1, data->k[idx1[i]], data->v[idx1[i]]);
+ parcTreeMap_Put(tree2, data->k[idx1[i]], data->v[idx1[i]]);
+ }
+
+ parcTreeMap_Put(tree1, data->k[11], data->v[11]);
+
+
+ PARCIterator *it = parcTreeMap_CreateKeyValueIterator(tree1);
+ for (int idx = 1; parcIterator_HasNext(it); ++idx) {
+ parcIterator_Next(it);
+ if (idx == 11) {
+ parcIterator_Remove(it);
+ }
+ }
+ parcIterator_Release(&it);
+
+ assertTrue(parcTreeMap_Equals(tree1, tree2), "Expect the trees to be equal after remove.");
+}
+
+LONGBOW_TEST_FIXTURE(Local)
+{
+ //LONGBOW_RUN_TEST_CASE(Local, PARC_TreeMap_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_TreeMap_ExerciseRandomSeededSmall);
+ LONGBOW_RUN_TEST_CASE(Stress, PARC_TreeMap_ExerciseRandomSeeded);
+ }
+}
+
+LONGBOW_TEST_FIXTURE_SETUP(Stress)
+{
+ return LONGBOW_STATUS_SUCCEEDED;
+}
+
+LONGBOW_TEST_FIXTURE_TEARDOWN(Stress)
+{
+ return LONGBOW_STATUS_SUCCEEDED;
+}
+
+LONGBOW_TEST_CASE(Stress, PARC_TreeMap_ExerciseRandomSeededSmall)
+{
+ 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
+
+ srandom(seed);
+ PARCTreeMap *tree = parcTreeMap_Create();
+
+ 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++;
+ parcTreeMap_Put(tree, (void *) item, (void *) (item << 8));
+ } else {
+ deletes++;
+ parcTreeMap_Remove(tree, (void *) item);
+ }
+ rbCheckTree(tree);
+ }
+
+ parcTreeMap_Release(&tree);
+ }
+}
+
+LONGBOW_TEST_CASE(Stress, PARC_TreeMap_ExerciseRandomSeeded)
+{
+ PARCTreeMap *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
+ }
+
+ srandom(seed);
+
+ tree1 = parcTreeMap_Create();
+
+ 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++;
+ parcTreeMap_Put(tree1, (void *) item, (void *) (item << 8));
+ } else {
+ deletes++;
+ parcTreeMap_Remove(tree1, (void *) item);
+ }
+ rbCheckTree(tree1);
+ }
+
+ parcTreeMap_Release(&tree1);
+}
+
+int
+main(int argc, char *argv[])
+{
+ LongBowRunner *testRunner = LONGBOW_TEST_RUNNER_CREATE(PARC_TreeMap);
+ int exitStatus = LONGBOW_TEST_MAIN(argc, argv, testRunner);
+ longBowTestRunner_Destroy(&testRunner);
+ exit(exitStatus);
+}