From ec688b4723a041044226358bcd4dd6e2da39da49 Mon Sep 17 00:00:00 2001 From: Luca Muscariello Date: Thu, 23 Feb 2017 17:01:02 +0100 Subject: Initial commit: cframework. Longbow and Libparc Change-Id: I90378dbd30da6033b20fb1f829b3b822cf366c59 Signed-off-by: Luca Muscariello --- libparc/parc/algol/test/test_parc_TreeMap.c | 1565 +++++++++++++++++++++++++++ 1 file changed, 1565 insertions(+) create mode 100755 libparc/parc/algol/test/test_parc_TreeMap.c (limited to 'libparc/parc/algol/test/test_parc_TreeMap.c') 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 +#include +#include +#include +#include + +#include +#include + +#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); +} -- cgit 1.2.3-korg