diff options
Diffstat (limited to 'libparc/parc/algol/test/test_parc_TreeMap.c')
| -rwxr-xr-x | libparc/parc/algol/test/test_parc_TreeMap.c | 1565 |
1 files changed, 0 insertions, 1565 deletions
diff --git a/libparc/parc/algol/test/test_parc_TreeMap.c b/libparc/parc/algol/test/test_parc_TreeMap.c deleted file mode 100755 index 9355380b..00000000 --- a/libparc/parc/algol/test/test_parc_TreeMap.c +++ /dev/null @@ -1,1565 +0,0 @@ -/* - * 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); -} |