| /////////////////////////////////////////////////////////////////////////////// |
| // // |
| // Copyright (c) 2000-2019 Ericsson Telecom AB // |
| // // |
| // All rights reserved. This program and the accompanying materials // |
| // are made available under the terms of the Eclipse Public License v2.0 // |
| // which accompanies this distribution, and is available at // |
| // https://www.eclipse.org/org/documents/epl-2.0/EPL-2.0.html // |
| /////////////////////////////////////////////////////////////////////////////// |
| module EPTF_RBT_Test |
| { |
| //========================================================================= |
| // Import part |
| //========================================================================= |
| import from EPTF_CLL_Base_Functions all; |
| import from EPTF_CLL_RBT_Definitions all; |
| import from EPTF_CLL_RBT_Functions all; |
| |
| import from EPTF_CLL_Common_Definitions all; |
| import from EPTF_CLL_RBtree_Definitions all; |
| import from EPTF_CLL_RBtree_Functions all; |
| import from EPTF_CLL_RBtreeFloat_Functions all; |
| import from EPTF_CLL_RBtreeInteger_Functions all; |
| import from TCCEnv_Functions all; |
| |
| //========================================================================= |
| // Module Parameters |
| //========================================================================= |
| //modulepar integer tsp_CLL_debug_acceptableMaxSizeOfGrowingVariables := 1; |
| modulepar EPTF_IntegerList tsp_EPTF_RBT_Test_initIntegerTree := {50, 100, 200, 150, 70, 85, 25, 60, 55, 53}; |
| modulepar EPTF_FloatList tsp_EPTF_RBT_Test_initFloatTree := {50.0, 100.0, 200.0, 150.0, 70.0, 85.0, 25.0, 60.0, 55.0, 53.0}; |
| //========================================================================= |
| // Component type |
| //========================================================================= |
| type component RBT_Test_CT |
| { |
| } |
| |
| //========================================================================= |
| // Functions |
| //========================================================================= |
| function f_RBT_Test_createBusyElems4IntegerRBT( |
| inout EPTF_Integer_RedBlackTree pl_tree, |
| in integer pl_num) |
| runs on RBT_Test_CT |
| { |
| var integer i := 0; |
| var integer vl_dumy; |
| for(i := 0; i < pl_num; i := i + 1) { |
| var EPTF_IntegerList vl_iList := { i }; |
| vl_dumy := f_EPTF_RBTreeI_createNewIntegerNode(pl_tree, i, vl_iList); |
| } |
| } |
| |
| function f_RBT_Test_createBusyElems4FloatRBT( |
| inout EPTF_Float_RedBlackTree pl_tree, |
| in integer pl_num) |
| runs on RBT_Test_CT |
| { |
| var integer i := 0; |
| var integer vl_dumy; |
| for(i := 0; i < pl_num; i := i + 1) { |
| var EPTF_IntegerList vl_iList := { i }; |
| vl_dumy := f_EPTF_RBTreeF_createNewFloatNode(pl_tree, int2float(i), vl_iList); |
| } |
| } |
| |
| //========================================================================= |
| // Testcases |
| //========================================================================= |
| testcase tc_RBT_Test_testIntegerRBTGrowage() runs on RBT_Test_CT |
| { |
| var EPTF_Integer_RedBlackTree vl_tree; |
| var integer i := 0; |
| var EPTF_IntegerList vl_createNodes; |
| var EPTF_IntegerList vl_data := {}; |
| var integer vl_getNodeIdx; |
| var EPTF_IntegerNode vl_node; |
| var boolean vl_success; |
| var integer vl_nodeSize := 1000; |
| |
| f_EPTF_RBTreeI_initIntegerTree(vl_tree); |
| |
| if(tsp_CLL_debug_acceptableMaxSizeOfGrowingVariables < 0) { |
| log(%definitionId&": tsp_CLL_debug_acceptableMaxSizeOfGrowingVariables is less than 0."); |
| } |
| |
| log(%definitionId&": Creating a tree with ", tsp_CLL_debug_acceptableMaxSizeOfGrowingVariables, " elements"); |
| log(%definitionId&": This should cause NO logs about exceeding the max size."); |
| f_RBT_Test_createBusyElems4IntegerRBT(vl_tree, tsp_CLL_debug_acceptableMaxSizeOfGrowingVariables); |
| |
| f_EPTF_RBTreeI_initIntegerTree(vl_tree); |
| log("### 1.", vl_tree); |
| log(%definitionId&": Creating a tree with ", tsp_CLL_debug_acceptableMaxSizeOfGrowingVariables + 10, " elements"); |
| log(%definitionId&": This should cause a single log about exceeding the max size."); |
| f_RBT_Test_createBusyElems4IntegerRBT(vl_tree, tsp_CLL_debug_acceptableMaxSizeOfGrowingVariables + 10); |
| log("### 2.", vl_tree); |
| if(tsp_CLL_debug_acceptableMaxSizeOfGrowingVariables > 0) { |
| f_EPTF_RBTreeI_initIntegerTree(vl_tree); |
| log(%definitionId&": Creating a tree with ", 2*tsp_CLL_debug_acceptableMaxSizeOfGrowingVariables, " elements"); |
| log(%definitionId&": This should cause a few logs about exceeding the max size.") |
| f_RBT_Test_createBusyElems4IntegerRBT(vl_tree, 2 * tsp_CLL_debug_acceptableMaxSizeOfGrowingVariables); |
| |
| f_EPTF_RBTreeI_initIntegerTree(vl_tree); |
| log(%definitionId&": Creating a tree with ", 100*tsp_CLL_debug_acceptableMaxSizeOfGrowingVariables, " elements"); |
| log(%definitionId&": This should cause more logs about exceeding the max size.") |
| f_RBT_Test_createBusyElems4IntegerRBT(vl_tree, 100 * tsp_CLL_debug_acceptableMaxSizeOfGrowingVariables); |
| } |
| |
| for(i := 0; i < vl_nodeSize; i := i + 1) { |
| vl_createNodes[i] := i; |
| } |
| f_EPTF_RBTreeI_initIntegerTree(vl_tree); |
| for(i := 0; i < sizeof(vl_createNodes); i := i + 1) |
| { |
| vl_data := {i + 2}; |
| vl_getNodeIdx := f_EPTF_RBTreeI_createNewIntegerNode(vl_tree, vl_createNodes[i], vl_data); |
| |
| if (vl_getNodeIdx != i + 2) { |
| log("Error: "&%definitionId&"returns with wrong node index: ", vl_getNodeIdx, " expected: ", i + 2); |
| setverdict(fail); |
| } |
| } |
| if(sizeof(vl_tree.nodes) == vl_nodeSize + 2) { |
| setverdict(pass); |
| } else { |
| log("Error: wrong node size: ",sizeof(vl_tree.nodes), ", expected: ", vl_nodeSize + 2); |
| setverdict(fail); |
| } |
| |
| for(i := 0; i < sizeof(vl_createNodes); i := i + 1) |
| { |
| vl_success := f_EPTF_RBTreeI_getIntegerElementNodeByKey(vl_tree, vl_createNodes[i], vl_node, vl_getNodeIdx); |
| f_EPTF_RBTreeI_removeIntegerNode(vl_tree, vl_getNodeIdx, true); |
| } |
| |
| for(i := 0; i < sizeof(vl_createNodes); i := i + 1) |
| { |
| vl_data := {i + 2}; |
| vl_getNodeIdx := f_EPTF_RBTreeI_createNewIntegerNode(vl_tree, vl_createNodes[i], vl_data); |
| |
| } |
| if(sizeof(vl_tree.nodes) == vl_nodeSize + 2) { |
| setverdict(pass); |
| } else { |
| log("Error: wrong node size: ",sizeof(vl_tree.nodes), ", expected: ", vl_nodeSize + 2); |
| setverdict(fail); |
| } |
| |
| for(i := 0; i < sizeof(vl_createNodes) / 2; i := i + 1) |
| { |
| vl_success := f_EPTF_RBTreeI_getIntegerElementNodeByKey(vl_tree, vl_createNodes[i], vl_node, vl_getNodeIdx); |
| f_EPTF_RBTreeI_removeIntegerNode(vl_tree, vl_getNodeIdx, true); |
| } |
| for(i := 0; i < sizeof(vl_createNodes); i := i + 1) |
| { |
| vl_data := {i + 2}; |
| vl_getNodeIdx := f_EPTF_RBTreeI_createNewIntegerNode(vl_tree, vl_createNodes[i], vl_data); |
| |
| } |
| if(sizeof(vl_tree.nodes) == vl_nodeSize + vl_nodeSize / 2 + 2) { |
| setverdict(pass); |
| } else { |
| log("Error: wrong node size: ",sizeof(vl_tree.nodes), ", expected: ", vl_nodeSize + vl_nodeSize / 2 + 2); |
| setverdict(fail); |
| } |
| |
| } |
| |
| testcase tc_RBT_Test_testFloatRBTGrowage() runs on RBT_Test_CT |
| { |
| var EPTF_Float_RedBlackTree vl_tree; |
| var integer i := 0; |
| var EPTF_FloatList vl_createNodes; |
| var EPTF_IntegerList vl_data := {}; |
| var integer vl_getNodeIdx; |
| var EPTF_FloatNode vl_node; |
| var boolean vl_success; |
| var integer vl_nodeSize := 1000; |
| |
| f_EPTF_RBTreeF_initFloatTree(vl_tree); |
| if(tsp_CLL_debug_acceptableMaxSizeOfGrowingVariables < 0) { |
| log(%definitionId&": tsp_CLL_debug_acceptableMaxSizeOfGrowingVariables is less than 0."); |
| } |
| |
| log(%definitionId&": Creating a tree with ", tsp_CLL_debug_acceptableMaxSizeOfGrowingVariables, " elements"); |
| log(%definitionId&": This should cause NO logs about exceeding the max size."); |
| f_RBT_Test_createBusyElems4FloatRBT(vl_tree, tsp_CLL_debug_acceptableMaxSizeOfGrowingVariables); |
| |
| f_EPTF_RBTreeF_initFloatTree(vl_tree); |
| log(%definitionId&": Creating a tree with ", tsp_CLL_debug_acceptableMaxSizeOfGrowingVariables + 1, " elements"); |
| log(%definitionId&": This should cause a single log about exceeding the max size."); |
| f_RBT_Test_createBusyElems4FloatRBT(vl_tree, tsp_CLL_debug_acceptableMaxSizeOfGrowingVariables + 1); |
| |
| if(tsp_CLL_debug_acceptableMaxSizeOfGrowingVariables > 0) { |
| f_EPTF_RBTreeF_initFloatTree(vl_tree); |
| log(%definitionId&": Creating a tree with ", 2*tsp_CLL_debug_acceptableMaxSizeOfGrowingVariables, " elements"); |
| log(%definitionId&": This should cause a few logs about exceeding the max size.") |
| f_RBT_Test_createBusyElems4FloatRBT(vl_tree, 2 * tsp_CLL_debug_acceptableMaxSizeOfGrowingVariables); |
| |
| f_EPTF_RBTreeF_initFloatTree(vl_tree); |
| log(%definitionId&": Creating a tree with ", 100*tsp_CLL_debug_acceptableMaxSizeOfGrowingVariables, " elements"); |
| log(%definitionId&": This should cause more logs about exceeding the max size.") |
| f_RBT_Test_createBusyElems4FloatRBT(vl_tree, 100 * tsp_CLL_debug_acceptableMaxSizeOfGrowingVariables); |
| } |
| for(i := 0; i < vl_nodeSize; i := i + 1) { |
| vl_createNodes[i] := int2float(i); |
| } |
| f_EPTF_RBTreeF_initFloatTree(vl_tree); |
| for(i := 0; i < sizeof(vl_createNodes); i := i + 1) |
| { |
| vl_data := {i + 2}; |
| vl_getNodeIdx := f_EPTF_RBTreeF_createNewFloatNode(vl_tree, vl_createNodes[i], vl_data); |
| |
| if (vl_getNodeIdx != i + 2) { |
| log("Error: "&%definitionId&"returns with wrong node index: ", vl_getNodeIdx, " expected: ", i + 2); |
| setverdict(fail); |
| } |
| } |
| if(sizeof(vl_tree.nodes) == vl_nodeSize + 2) { |
| setverdict(pass); |
| } else { |
| log("Error: wrong node size: ",sizeof(vl_tree.nodes), ", expected: ", vl_nodeSize + 2); |
| setverdict(fail); |
| } |
| |
| for(i := 0; i < sizeof(vl_createNodes); i := i + 1) |
| { |
| vl_success := f_EPTF_RBTreeF_getFloatNodeByKey(vl_tree, vl_createNodes[i], vl_node, vl_getNodeIdx); |
| f_EPTF_RBTreeF_removeFloatNode(vl_tree, vl_getNodeIdx, true); |
| } |
| |
| for(i := 0; i < sizeof(vl_createNodes); i := i + 1) |
| { |
| vl_data := {i + 2}; |
| vl_getNodeIdx := f_EPTF_RBTreeF_createNewFloatNode(vl_tree, vl_createNodes[i], vl_data); |
| |
| } |
| if(sizeof(vl_tree.nodes) == vl_nodeSize + 2) { |
| setverdict(pass); |
| } else { |
| log("Error: wrong node size: ",sizeof(vl_tree.nodes), ", expected: ", vl_nodeSize + 2); |
| setverdict(fail); |
| } |
| |
| for(i := 0; i < sizeof(vl_createNodes) / 2; i := i + 1) |
| { |
| vl_success := f_EPTF_RBTreeF_getFloatNodeByKey(vl_tree, vl_createNodes[i], vl_node, vl_getNodeIdx); |
| f_EPTF_RBTreeF_removeFloatNode(vl_tree, vl_getNodeIdx, true); |
| } |
| for(i := 0; i < sizeof(vl_createNodes); i := i + 1) |
| { |
| vl_data := {i + 2}; |
| vl_getNodeIdx := f_EPTF_RBTreeF_createNewFloatNode(vl_tree, vl_createNodes[i], vl_data); |
| |
| } |
| if(sizeof(vl_tree.nodes) == vl_nodeSize + vl_nodeSize / 2 + 2) { |
| setverdict(pass); |
| } else { |
| log("Error: wrong node size: ",sizeof(vl_tree.nodes), ", expected: ", vl_nodeSize + vl_nodeSize / 2 + 2); |
| setverdict(fail); |
| } |
| |
| |
| } |
| |
| /////////////////////////////////////////////////////////// |
| // Testcase: tc_EPTF_RBTreeF_initFloatTree |
| // |
| // Purpose: |
| // to test f_EPTF_RBTreeF_initFloatTree() function |
| // |
| // Requirement: |
| // - |
| // |
| // Action: |
| // - calls f_EPTF_RBTreeF_initFloatTree() function |
| // - matches the initiated RBtree with the expected one |
| // |
| // Expected Result: |
| // initiated RBtree variable is the same as expected |
| /////////////////////////////////////////////////////////// |
| testcase tc_EPTF_RBTreeF_initFloatTree() runs on RBT_Test_CT { |
| |
| var EPTF_Float_RedBlackTree rb_Tree; |
| var EPTF_Float_RedBlackTree rb_expected; |
| // Init |
| f_EPTF_RBTreeF_initFloatTree(rb_Tree); |
| |
| rb_expected := { |
| nodes := { |
| { |
| color := black, |
| left := 0, |
| right := 0, |
| parent := 0, |
| fwd := -1, |
| bwd := -1, |
| isHeadInSameKeysCluster := false, |
| isSentinel := true, |
| startOfClusterIdx := -1, |
| endOfClusterIdx := -1 |
| }, |
| { |
| color := black, |
| left := 0, |
| right := 0, |
| parent := 0, |
| fwd := -1, |
| bwd := -1, |
| isHeadInSameKeysCluster := false, |
| isSentinel := true, |
| startOfClusterIdx := -1, |
| endOfClusterIdx := -1 |
| } |
| }, |
| floatKeyData := { |
| { |
| key := 0.000000, |
| data := { |
| |
| } |
| }, |
| { |
| key := 0.000000, |
| data := { |
| |
| } |
| } |
| }, |
| nodesCurMaxIndex := 1, |
| root := 1, |
| nil := 0, |
| freeHead := -1, |
| freeTail := -1, |
| smallestKeyIndex := -1, |
| isSmallestCacheValid := false, |
| nOfElements := 0, |
| acceptableMaxSize := tsp_CLL_debug_acceptableMaxSizeOfGrowingVariables |
| } |
| |
| if (rb_Tree == rb_expected) { |
| setverdict(pass); |
| } else { |
| log("Error: wrong result: ", rb_Tree,", expected: ", rb_expected); |
| setverdict(fail); |
| }; |
| |
| } |
| |
| /////////////////////////////////////////////////////////// |
| // Testcase: tc_EPTF_RBTreeI_initIntegerTree |
| // |
| // Purpose: |
| // to test f_EPTF_RBTreeI_initIntegerTree() function |
| // |
| // Requirement: |
| // - |
| // |
| // Action: |
| // - calls f_EPTF_RBTreeI_initIntegerTree() function |
| // - matches the initiated RBtree with the expected one |
| // |
| // Expected Result: |
| // initiated RBtree variable is the same as expected |
| /////////////////////////////////////////////////////////// |
| testcase tc_EPTF_RBTreeI_initIntegerTree() runs on RBT_Test_CT { |
| |
| var EPTF_Integer_RedBlackTree rb_Tree; |
| var EPTF_Integer_RedBlackTree rb_expected; |
| // Init |
| f_EPTF_RBTreeI_initIntegerTree(rb_Tree); |
| |
| rb_expected := { |
| nodes := { |
| { |
| color := black, |
| left := 0, |
| right := 0, |
| parent := 0, |
| fwd := -1, |
| bwd := -1, |
| isHeadInSameKeysCluster := false, |
| isSentinel := true, |
| startOfClusterIdx := -1, |
| endOfClusterIdx := -1 |
| }, |
| { |
| color := black, |
| left := 0, |
| right := 0, |
| parent := 0, |
| fwd := -1, |
| bwd := -1, |
| isHeadInSameKeysCluster := false, |
| isSentinel := true, |
| startOfClusterIdx := -1, |
| endOfClusterIdx := -1 |
| } |
| }, |
| integerKeyData := { |
| { |
| key := 0, |
| data := { |
| |
| } |
| }, |
| { |
| key := 0, |
| data := { |
| |
| } |
| } |
| }, |
| nodesCurMaxIndex := 1, |
| root := 1, |
| nil := 0, |
| freeHead := -1, |
| freeTail := -1, |
| smallestKeyIndex := -1, |
| isSmallestCacheValid := false, |
| nOfElements := 0, |
| acceptableMaxSize := tsp_CLL_debug_acceptableMaxSizeOfGrowingVariables |
| } |
| |
| if (rb_Tree == rb_expected) { |
| setverdict(pass); |
| } else { |
| log("Error: wrong result: ", rb_Tree,", expected: ", rb_expected); |
| setverdict(fail); |
| }; |
| } |
| |
| /////////////////////////////////////////////////////////// |
| // Testcase: tc_EPTF_RBTreeI_createNewIntegerNode |
| // |
| // Purpose: |
| // to test f_EPTF_RBTreeI_createNewIntegerNode() function |
| // |
| // Requirement: |
| // - |
| // |
| // Action: |
| // - calls f_EPTF_RBTreeI_initIntegerTree() function |
| // - creates several nodes by calling f_EPTF_RBTreeI_createNewIntegerNode() function with tsp_EPTF_RBT_Test_initIntegerTree |
| // - matches the initiated RBtree with the expected one |
| // |
| // Expected Result: |
| // initiated RBtree variable is the same as expected |
| /////////////////////////////////////////////////////////// |
| testcase tc_EPTF_RBTreeI_createNewIntegerNode() runs on RBT_Test_CT { |
| |
| var EPTF_Integer_RedBlackTree rb_Tree; |
| var EPTF_Integer_RedBlackTree rb_expected; |
| var EPTF_IntegerList vl_data := {}; |
| var integer vl_getNodeIdx := 0; |
| var EPTF_IntegerList vl_createNodes := tsp_EPTF_RBT_Test_initIntegerTree; |
| // Init |
| f_EPTF_RBTreeI_initIntegerTree(rb_Tree); |
| for(var integer i := 0; i < sizeof(vl_createNodes); i := i + 1) |
| { |
| vl_data := {i + 2}; |
| vl_getNodeIdx := f_EPTF_RBTreeI_createNewIntegerNode(rb_Tree, vl_createNodes[i], vl_data); |
| if (vl_getNodeIdx == i + 2) { |
| setverdict(pass); |
| } else { |
| log("Error: "&%definitionId&"returns with wrong node index: ", vl_getNodeIdx, " expected: ", i + 2); |
| setverdict(fail); |
| } |
| } |
| |
| rb_expected := { |
| nodes := { |
| { |
| color := black, |
| left := 0, |
| right := 0, |
| parent := 0, |
| fwd := -1, |
| bwd := -1, |
| isHeadInSameKeysCluster := false, |
| isSentinel := true, |
| startOfClusterIdx := -1, |
| endOfClusterIdx := -1 |
| }, |
| { |
| color := black, |
| left := 6, |
| right := 0, |
| parent := 0, |
| fwd := -1, |
| bwd := -1, |
| isHeadInSameKeysCluster := false, |
| isSentinel := true, |
| startOfClusterIdx := -1, |
| endOfClusterIdx := -1 |
| }, |
| { |
| color := red, |
| left := 8, |
| right := 10, |
| parent := 6, |
| fwd := -1, |
| bwd := -1, |
| isHeadInSameKeysCluster := false, |
| isSentinel := false, |
| startOfClusterIdx := -1, |
| endOfClusterIdx := -1 |
| }, |
| { |
| color := red, |
| left := 7, |
| right := 4, |
| parent := 6, |
| fwd := -1, |
| bwd := -1, |
| isHeadInSameKeysCluster := false, |
| isSentinel := false, |
| startOfClusterIdx := -1, |
| endOfClusterIdx := -1 |
| }, |
| { |
| color := black, |
| left := 5, |
| right := 0, |
| parent := 3, |
| fwd := -1, |
| bwd := -1, |
| isHeadInSameKeysCluster := false, |
| isSentinel := false, |
| startOfClusterIdx := -1, |
| endOfClusterIdx := -1 |
| }, |
| { |
| color := red, |
| left := 0, |
| right := 0, |
| parent := 4, |
| fwd := -1, |
| bwd := -1, |
| isHeadInSameKeysCluster := false, |
| isSentinel := false, |
| startOfClusterIdx := -1, |
| endOfClusterIdx := -1 |
| }, |
| { |
| color := black, |
| left := 2, |
| right := 3, |
| parent := 1, |
| fwd := -1, |
| bwd := -1, |
| isHeadInSameKeysCluster := false, |
| isSentinel := false, |
| startOfClusterIdx := -1, |
| endOfClusterIdx := -1 |
| }, |
| { |
| color := black, |
| left := 0, |
| right := 0, |
| parent := 3, |
| fwd := -1, |
| bwd := -1, |
| isHeadInSameKeysCluster := false, |
| isSentinel := false, |
| startOfClusterIdx := -1, |
| endOfClusterIdx := -1 |
| }, |
| { |
| color := black, |
| left := 0, |
| right := 0, |
| parent := 2, |
| fwd := -1, |
| bwd := -1, |
| isHeadInSameKeysCluster := false, |
| isSentinel := false, |
| startOfClusterIdx := -1, |
| endOfClusterIdx := -1 |
| }, |
| { |
| color := red, |
| left := 0, |
| right := 0, |
| parent := 10, |
| fwd := -1, |
| bwd := -1, |
| isHeadInSameKeysCluster := false, |
| isSentinel := false, |
| startOfClusterIdx := -1, |
| endOfClusterIdx := -1 |
| }, |
| { |
| color := black, |
| left := 11, |
| right := 9, |
| parent := 2, |
| fwd := -1, |
| bwd := -1, |
| isHeadInSameKeysCluster := false, |
| isSentinel := false, |
| startOfClusterIdx := -1, |
| endOfClusterIdx := -1 |
| }, |
| { |
| color := red, |
| left := 0, |
| right := 0, |
| parent := 10, |
| fwd := -1, |
| bwd := -1, |
| isHeadInSameKeysCluster := false, |
| isSentinel := false, |
| startOfClusterIdx := -1, |
| endOfClusterIdx := -1 |
| } |
| }, |
| integerKeyData := { |
| {key := 0,data := {}}, |
| {key := 0,data := {}}, |
| {key := 50,data := {2}}, |
| {key := 100,data := {3}}, |
| {key := 200,data := {4}}, |
| {key := 150,data := {5}}, |
| {key := 70,data := {6}}, |
| {key := 85,data := {7}}, |
| {key := 25,data := {8}}, |
| {key := 60,data := {9}}, |
| {key := 55,data := {10}}, |
| {key := 53,data := {11}} |
| }, |
| nodesCurMaxIndex := 11, |
| root := 1, |
| nil := 0, |
| freeHead := -1, |
| freeTail := -1, |
| smallestKeyIndex := 8, |
| isSmallestCacheValid := true, |
| nOfElements := 10, |
| acceptableMaxSize := tsp_CLL_debug_acceptableMaxSizeOfGrowingVariables |
| } |
| if (rb_Tree == rb_expected) { |
| setverdict(pass); |
| } else { |
| log("Error: wrong result: ", rb_Tree,", expected: ", rb_expected); |
| setverdict(fail); |
| }; |
| } |
| |
| /////////////////////////////////////////////////////////// |
| // Testcase: tc_EPTF_RBTreeI_removeIntegerNodeWithSameKey |
| // |
| // Purpose: |
| // to test f_EPTF_RBTReeI_removeIntegerNodeWithSameKey() function |
| // |
| // Requirement: |
| // one |
| // |
| // Action: |
| // - calls *f_EPTF_RBTreeI_initIntegerTree()* function |
| // - creates several nodes by calling f_EPTF_RBTreeI_createNewIntegerNode() function with *tsp_EPTF_RBT_Test_initIntegerTree* |
| // - adds a new node with an allready used key in the initiated RBTree |
| // - calls twice the f_EPTF_RBTReeI_removeIntegerNodeWithSameKey() function with one of the nodes's index having the same key |
| // |
| // Expected Result: |
| // - once the tested function returs with true, then false |
| /////////////////////////////////////////////////////////// |
| testcase tc_EPTF_RBTreeI_removeIntegerNodeWithSameKey() runs on RBT_Test_CT { |
| |
| var EPTF_Integer_RedBlackTree rb_Tree; |
| var EPTF_Integer_RedBlackTree rb_expected; |
| var EPTF_IntegerList vl_data := {}; |
| var EPTF_IntegerNode vl_node; |
| var integer vl_sameKey := 53; |
| var integer vl_getNodeIdx; |
| var EPTF_IntegerList vl_createNodes := tsp_EPTF_RBT_Test_initIntegerTree; |
| // Init |
| vl_createNodes[sizeof(vl_createNodes)] := vl_sameKey; |
| |
| f_EPTF_RBTreeI_initIntegerTree(rb_Tree); |
| for(var integer i := 0; i < sizeof(vl_createNodes); i := i + 1) |
| { |
| vl_data := {i + 2}; |
| vl_getNodeIdx := f_EPTF_RBTreeI_createNewIntegerNode(rb_Tree, vl_createNodes[i], vl_data); |
| } |
| if(f_EPTF_RBTreeI_getIntegerElementNodeByKey(rb_Tree, vl_sameKey, vl_node, vl_getNodeIdx) and f_EPTF_RBTReeI_removeIntegerNodeWithSameKey(rb_Tree, vl_getNodeIdx)) { |
| setverdict(pass); |
| } else { |
| log("Error: same key node not removed: ", vl_sameKey); |
| setverdict(fail); |
| } |
| |
| if(f_EPTF_RBTreeI_getIntegerElementNodeByKey(rb_Tree, vl_sameKey, vl_node, vl_getNodeIdx) and not f_EPTF_RBTReeI_removeIntegerNodeWithSameKey(rb_Tree, vl_getNodeIdx)){ |
| setverdict(pass); |
| } else { |
| log("Error: same key node removed: ", vl_sameKey); |
| setverdict(fail); |
| } |
| } |
| |
| /////////////////////////////////////////////////////////// |
| // Testcase: tc_EPTF_RBTreeI_removeIntegerNode |
| // |
| // Purpose: |
| // to test f_EPTF_RBTreeI_removeIntegerNode() function |
| // |
| // Requirement: |
| // - |
| // |
| // Action: |
| // calls f_EPTF_RBTreeI_initIntegerTree() function |
| // creates several nodes by calling f_EPTF_RBTreeI_createNewIntegerNode() function with <tsp_EPTF_RBT_Test_initIntegerTree> |
| // calls the f_EPTF_RBTreeI_removeIntegerNode() function with one of the created nodes's index, and destroy it |
| // calls the f_EPTF_RBTreeI_removeIntegerNode() function with one of the created nodes's index, but not destroy it |
| // matches the modified RBtree with the expected one |
| // |
| // Expected Result: |
| // modified RBtree variable is the same as expected |
| /////////////////////////////////////////////////////////// |
| testcase tc_EPTF_RBTreeI_removeIntegerNode() runs on RBT_Test_CT { |
| |
| var EPTF_Integer_RedBlackTree rb_Tree; |
| var EPTF_Integer_RedBlackTree rb_expected; |
| var EPTF_IntegerList vl_data := {}; |
| var EPTF_IntegerNode vl_node; |
| var integer vl_getNodeIdx; |
| var boolean vl_success; |
| var EPTF_IntegerList vl_createNodes := tsp_EPTF_RBT_Test_initIntegerTree; |
| var EPTF_IntegerList vl_destroyNodes := {70, 50, 55}; |
| var EPTF_IntegerList vl_noDestroyNodes := {150}; |
| // Init |
| f_EPTF_RBTreeI_initIntegerTree(rb_Tree); |
| for(var integer i := 0; i < sizeof(vl_createNodes); i := i + 1) |
| { |
| vl_data := {i + 2}; |
| vl_getNodeIdx := f_EPTF_RBTreeI_createNewIntegerNode(rb_Tree, vl_createNodes[i], vl_data); |
| } |
| for(var integer i := 0; i < sizeof(vl_destroyNodes); i := i + 1) |
| { |
| vl_success := f_EPTF_RBTreeI_getIntegerElementNodeByKey(rb_Tree, vl_destroyNodes[i], vl_node, vl_getNodeIdx); |
| f_EPTF_RBTreeI_removeIntegerNode(rb_Tree, vl_getNodeIdx, true); |
| } |
| for(var integer i := 0; i < sizeof(vl_noDestroyNodes); i := i + 1) |
| { |
| vl_success := f_EPTF_RBTreeI_getIntegerElementNodeByKey(rb_Tree, vl_noDestroyNodes[i], vl_node, vl_getNodeIdx); |
| f_EPTF_RBTreeI_removeIntegerNode(rb_Tree, vl_getNodeIdx, false); |
| } |
| rb_expected := { |
| nodes := { |
| { |
| color := black, |
| left := 0, |
| right := 0, |
| parent := 4, |
| fwd := -1, |
| bwd := -1, |
| isHeadInSameKeysCluster := false, |
| isSentinel := true, |
| startOfClusterIdx := -1, |
| endOfClusterIdx := -1 |
| }, |
| { |
| color := black, |
| left := 7, |
| right := 0, |
| parent := 0, |
| fwd := -1, |
| bwd := -1, |
| isHeadInSameKeysCluster := false, |
| isSentinel := true, |
| startOfClusterIdx := -1, |
| endOfClusterIdx := -1 |
| }, |
| { |
| color := unused, |
| left := 6, |
| right := 10, |
| parent := 7, |
| fwd := -1, |
| bwd := -1, |
| isHeadInSameKeysCluster := false, |
| isSentinel := false, |
| startOfClusterIdx := -1, |
| endOfClusterIdx := -1 |
| }, |
| { |
| color := red, |
| left := 0, |
| right := 0, |
| parent := 4, |
| fwd := -1, |
| bwd := -1, |
| isHeadInSameKeysCluster := false, |
| isSentinel := false, |
| startOfClusterIdx := -1, |
| endOfClusterIdx := -1 |
| }, |
| { |
| color := black, |
| left := 3, |
| right := 0, |
| parent := 7, |
| fwd := -1, |
| bwd := -1, |
| isHeadInSameKeysCluster := false, |
| isSentinel := false, |
| startOfClusterIdx := -1, |
| endOfClusterIdx := -1 |
| }, |
| { |
| color := invalid, |
| left := 3, |
| right := 0, |
| parent := 7, |
| fwd := -1, |
| bwd := -1, |
| isHeadInSameKeysCluster := false, |
| isSentinel := false, |
| startOfClusterIdx := -1, |
| endOfClusterIdx := -1 |
| }, |
| { |
| color := unused, |
| left := -1, |
| right := 2, |
| parent := 1, |
| fwd := -1, |
| bwd := -1, |
| isHeadInSameKeysCluster := false, |
| isSentinel := false, |
| startOfClusterIdx := -1, |
| endOfClusterIdx := -1 |
| }, |
| { |
| color := black, |
| left := 11, |
| right := 4, |
| parent := 1, |
| fwd := -1, |
| bwd := -1, |
| isHeadInSameKeysCluster := false, |
| isSentinel := false, |
| startOfClusterIdx := -1, |
| endOfClusterIdx := -1 |
| }, |
| { |
| color := black, |
| left := 0, |
| right := 0, |
| parent := 11, |
| fwd := -1, |
| bwd := -1, |
| isHeadInSameKeysCluster := false, |
| isSentinel := false, |
| startOfClusterIdx := -1, |
| endOfClusterIdx := -1 |
| }, |
| { |
| color := black, |
| left := 0, |
| right := 0, |
| parent := 11, |
| fwd := -1, |
| bwd := -1, |
| isHeadInSameKeysCluster := false, |
| isSentinel := false, |
| startOfClusterIdx := -1, |
| endOfClusterIdx := -1 |
| }, |
| { |
| color := unused, |
| left := 2, |
| right := -1, |
| parent := 11, |
| fwd := -1, |
| bwd := -1, |
| isHeadInSameKeysCluster := false, |
| isSentinel := false, |
| startOfClusterIdx := -1, |
| endOfClusterIdx := -1 |
| }, |
| { |
| color := red, |
| left := 8, |
| right := 9, |
| parent := 7, |
| fwd := -1, |
| bwd := -1, |
| isHeadInSameKeysCluster := false, |
| isSentinel := false, |
| startOfClusterIdx := -1, |
| endOfClusterIdx := -1 |
| } |
| }, |
| integerKeyData := { |
| {key := 0,data := {}}, |
| {key := 0,data := {}}, |
| {key := 50,data := {2}}, |
| {key := 100,data := {3}}, |
| {key := 200,data := {4}}, |
| {key := 150,data := {5}}, |
| {key := 70,data := {6}}, |
| {key := 85,data := {7}}, |
| {key := 25,data := {8}}, |
| {key := 60,data := {9}}, |
| {key := 55,data := {10}}, |
| {key := 53,data := {11}} |
| }, |
| nodesCurMaxIndex := 11, |
| root := 1, |
| nil := 0, |
| freeHead := 6, |
| freeTail := 10, |
| smallestKeyIndex := 8, |
| isSmallestCacheValid := true, |
| nOfElements := 6, |
| acceptableMaxSize := tsp_CLL_debug_acceptableMaxSizeOfGrowingVariables |
| } |
| if (rb_Tree == rb_expected) { |
| setverdict(pass); |
| } else { |
| log("Error: wrong result: ", rb_Tree,", expected: ", rb_expected); |
| setverdict(fail); |
| }; |
| } |
| |
| /////////////////////////////////////////////////////////// |
| // Testcase: tc_EPTF_RBTreeF_removeFloatNodeWithSameKey |
| // |
| // Purpose: |
| // to test f_EPTF_RBTreeF_removeFloatNodeWithSameKey() function |
| // |
| // Requirement: |
| // - |
| // |
| // Action: |
| // calls f_EPTF_RBTreeF_initFloatTree() function |
| // creates several nodes by calling f_EPTF_RBTreeF_createNewFloatNode() function with <tsp_EPTF_RBT_Test_initFloatTree> |
| // adds a new node with an allready used key in the initiated RBTree |
| // calls twice the f_EPTF_RBTreeF_removeFloatNodeWithSameKey() function with one of the nodes's index having the same key |
| // |
| // Expected Result: |
| // once the tested function returs with true, then false |
| /////////////////////////////////////////////////////////// |
| testcase tc_EPTF_RBTreeF_removeFloatNodeWithSameKey() runs on RBT_Test_CT { |
| |
| var EPTF_Float_RedBlackTree rb_Tree; |
| var EPTF_Float_RedBlackTree rb_expected; |
| var EPTF_IntegerList vl_data := {}; |
| var EPTF_FloatNode vl_node; |
| var integer vl_getNodeIdx; |
| var float vl_sameKey := 53.0; |
| var EPTF_FloatList vl_createNodes := tsp_EPTF_RBT_Test_initFloatTree; |
| // Init |
| vl_createNodes[sizeof(vl_createNodes)] := vl_sameKey; |
| |
| // Init |
| f_EPTF_RBTreeF_initFloatTree(rb_Tree); |
| for(var integer i := 0; i < sizeof(vl_createNodes); i := i + 1) |
| { |
| vl_data := {i + 2}; |
| vl_getNodeIdx := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, vl_createNodes[i], vl_data); |
| } |
| |
| if(f_EPTF_RBTreeF_getFloatNodeByKey(rb_Tree, vl_sameKey, vl_node, vl_getNodeIdx) and f_EPTF_RBTreeF_removeFloatNodeWithSameKey(rb_Tree, vl_getNodeIdx)) { |
| setverdict(pass); |
| } else { |
| log("Error: same key node not removed: ", vl_sameKey); |
| setverdict(fail); |
| } |
| if(f_EPTF_RBTreeF_getFloatNodeByKey(rb_Tree, vl_sameKey, vl_node, vl_getNodeIdx) and not f_EPTF_RBTreeF_removeFloatNodeWithSameKey(rb_Tree, vl_getNodeIdx)){ |
| setverdict(pass); |
| } else { |
| log("Error: same key node removed: ", vl_sameKey); |
| setverdict(fail); |
| } |
| |
| } |
| |
| /////////////////////////////////////////////////////////// |
| // Testcase: tc_EPTF_RBTreeI_getIntegerElementNodeByKey |
| // |
| // Purpose: |
| // to test f_EPTF_RBTreeI_getIntegerElementNodeByKey() function |
| // |
| // Requirement: |
| // - |
| // |
| // Action: |
| // calls f_EPTF_RBTreeI_initIntegerTree() function |
| // calls f_EPTF_RBTreeI_getIntegerElementNodeByKey() function |
| // creates several nodes by calling f_EPTF_RBTreeI_createNewIntegerNode() function with <tsp_EPTF_RBT_Test_initIntegerTree> |
| // calls several times the f_EPTF_RBTreeI_getIntegerElementNodeByKey() function with one of the created nodes's index |
| // |
| // Expected Result: |
| // first time the tested function returs with false, then true |
| /////////////////////////////////////////////////////////// |
| testcase tc_EPTF_RBTreeI_getIntegerElementNodeByKey() runs on RBT_Test_CT { |
| |
| var EPTF_Integer_RedBlackTree rb_Tree; |
| var EPTF_IntegerList vl_data := {}; |
| var EPTF_IntegerNode vl_node; |
| var integer vl_getNodeIdx; |
| var EPTF_IntegerList vl_createNodes := tsp_EPTF_RBT_Test_initIntegerTree; |
| |
| // Init |
| f_EPTF_RBTreeI_initIntegerTree(rb_Tree); |
| if(f_EPTF_RBTreeI_getIntegerElementNodeByKey(rb_Tree, vl_createNodes[0], vl_node, vl_getNodeIdx)) { |
| log("Error: ", %definitionId&" returns true"); |
| setverdict(fail); |
| } else { |
| setverdict(pass); |
| } |
| |
| for(var integer i := 0; i < sizeof(vl_createNodes); i := i + 1) |
| { |
| vl_data := {i + 2}; |
| vl_getNodeIdx := f_EPTF_RBTreeI_createNewIntegerNode(rb_Tree, vl_createNodes[i], vl_data); |
| } |
| for(var integer i := 0; i < sizeof(vl_createNodes); i := i + 1) |
| { |
| if(f_EPTF_RBTreeI_getIntegerElementNodeByKey(rb_Tree, vl_createNodes[i], vl_node, vl_getNodeIdx)) { |
| if(vl_getNodeIdx == i + 2) { |
| setverdict(pass); |
| } else { |
| log("Error: wrong node index for ", vl_createNodes[i], ": ", vl_getNodeIdx, " expected: ", i + 2); |
| setverdict(fail); |
| } |
| } else { |
| log("Error: ", %definitionId&" returns false"); |
| setverdict(fail); |
| } |
| } |
| } |
| |
| /////////////////////////////////////////////////////////// |
| // Testcase: tc_EPTF_RBTreeF_getFloatNodeByKey |
| // |
| // Purpose: |
| // to test f_EPTF_RBTreeF_getFloatNodeByKey() function |
| // |
| // Requirement: |
| // - |
| // |
| // Action: |
| // calls f_EPTF_RBTreeF_initFloatTree() function |
| // calls f_EPTF_RBTreeF_getFloatNodeByKey() function |
| // creates several nodes by calling f_EPTF_RBTreeF_createNewFloatNode() function with <tsp_EPTF_RBT_Test_initFloatTree> |
| // calls several times the f_EPTF_RBTreeF_getFloatNodeByKey() function with one of the created nodes's index |
| // |
| // Expected Result: |
| // first time the tested function returs with false, then true |
| /////////////////////////////////////////////////////////// |
| testcase tc_EPTF_RBTreeF_getFloatNodeByKey() runs on RBT_Test_CT { |
| |
| var EPTF_Float_RedBlackTree rb_Tree; |
| var EPTF_IntegerList vl_data := {}; |
| var EPTF_FloatNode vl_node; |
| var integer vl_getNodeIdx; |
| |
| var EPTF_FloatList vl_createNodes := tsp_EPTF_RBT_Test_initFloatTree; |
| |
| // Init |
| f_EPTF_RBTreeF_initFloatTree(rb_Tree); |
| if(f_EPTF_RBTreeF_getFloatNodeByKey(rb_Tree, vl_createNodes[0], vl_node, vl_getNodeIdx)) { |
| log("Error: ", %definitionId&" returns true"); |
| setverdict(fail); |
| } else { |
| setverdict(pass); |
| } |
| for(var integer i := 0; i < sizeof(vl_createNodes); i := i + 1) |
| { |
| vl_data := {i + 2}; |
| vl_getNodeIdx := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, vl_createNodes[i], vl_data); |
| } |
| |
| for(var integer i := 0; i < sizeof(vl_createNodes); i := i + 1) |
| { |
| if(f_EPTF_RBTreeF_getFloatNodeByKey(rb_Tree, vl_createNodes[i], vl_node, vl_getNodeIdx)) { |
| if(vl_getNodeIdx == i + 2) { |
| setverdict(pass); |
| } else { |
| log("Error: wrong node index for ", vl_createNodes[i], ": ", vl_getNodeIdx, " expected: ", i + 2); |
| setverdict(fail); |
| } |
| } else { |
| log("Error: ", %definitionId&" returns false"); |
| setverdict(fail); |
| } |
| } |
| |
| } |
| |
| /////////////////////////////////////////////////////////// |
| // Testcase: tc_EPTF_RBTreeI_searchSmallestIntegerNode |
| // |
| // Purpose: |
| // to test f_EPTF_RBTreeI_searchSmallestIntegerNode() function |
| // |
| // Requirement: |
| // - |
| // |
| // Action: |
| // calls f_EPTF_RBTreeI_initIntegerTree() function |
| // calls f_EPTF_RBTreeI_searchSmallestIntegerNode() function |
| // search the smallest node key in <tsp_EPTF_RBT_Test_initIntegerTree> |
| // creates several nodes by calling f_EPTF_RBTreeI_createNewIntegerNode() function with <tsp_EPTF_RBT_Test_initIntegerTree> |
| // calls the f_EPTF_RBTreeI_searchSmallestIntegerNode() function |
| // |
| // Expected Result: |
| // first time the tested function returs with false, then out parameter *indexFound* matches with the founded index |
| /////////////////////////////////////////////////////////// |
| testcase tc_EPTF_RBTreeI_searchSmallestIntegerNode() runs on RBT_Test_CT { |
| |
| var EPTF_Integer_RedBlackTree rb_Tree; |
| var EPTF_IntegerList vl_data := {}; |
| var EPTF_IntegerNode vl_node; |
| var integer vl_getNodeIdx; |
| var integer vl_smallest := 100000; |
| var integer vl_smallestIdx := 0; |
| var EPTF_IntegerList vl_createNodes := tsp_EPTF_RBT_Test_initIntegerTree; |
| |
| // Init |
| f_EPTF_RBTreeI_initIntegerTree(rb_Tree); |
| if(f_EPTF_RBTreeI_searchSmallestIntegerNode(rb_Tree, vl_node, vl_getNodeIdx)) { |
| log("Error: ", %definitionId&" returns true"); |
| setverdict(fail); |
| } else { |
| setverdict(pass); |
| } |
| //find smallest |
| for(var integer i := 0; i < sizeof(vl_createNodes); i := i + 1) { |
| if (vl_smallest > vl_createNodes[i]) { |
| vl_smallest := vl_createNodes[i]; |
| vl_smallestIdx := i + 2; |
| } |
| } |
| |
| for(var integer i := 0; i < sizeof(vl_createNodes); i := i + 1) |
| { |
| vl_data := {i + 2}; |
| vl_getNodeIdx := f_EPTF_RBTreeI_createNewIntegerNode(rb_Tree, vl_createNodes[i], vl_data); |
| } |
| |
| if(f_EPTF_RBTreeI_searchSmallestIntegerNode(rb_Tree, vl_node, vl_getNodeIdx)) { |
| if(vl_getNodeIdx == vl_smallestIdx) { |
| setverdict(pass); |
| } else { |
| log("Error: wrong node index for smallest node - ", vl_smallest, ": ", vl_getNodeIdx, " expected: ", vl_smallestIdx); |
| setverdict(fail); |
| } |
| } else { |
| log("Error: ", %definitionId&" returns false"); |
| setverdict(fail); |
| } |
| |
| } |
| |
| /////////////////////////////////////////////////////////// |
| // Testcase: tc_EPTF_RBTreeI_getBusyEventHeadIndex |
| // |
| // Purpose: |
| // to test f_EPTF_RBTreeI_getBusyEventHeadIndex() function |
| // |
| // Requirement: |
| // - |
| // |
| // Action: |
| // calls f_EPTF_RBTreeI_initIntegerTree() function |
| // calls f_EPTF_RBTreeI_getBusyEventHeadIndex() function |
| // search the smallest node key in <tsp_EPTF_RBT_Test_initIntegerTree> |
| // creates several nodes by calling f_EPTF_RBTreeI_createNewIntegerNode() function with <tsp_EPTF_RBT_Test_initIntegerTree> |
| // calls the f_EPTF_RBTreeI_getBusyEventHeadIndex() function |
| // |
| // Expected Result: |
| // first time the tested function returs with false, then out parameter *idx* matches with the founded index |
| /////////////////////////////////////////////////////////// |
| testcase tc_EPTF_RBTreeI_getBusyEventHeadIndex() runs on RBT_Test_CT { |
| |
| var EPTF_Integer_RedBlackTree rb_Tree; |
| var EPTF_IntegerList vl_data := {}; |
| var EPTF_IntegerNode vl_node; |
| var integer vl_getHeadIdx; |
| var integer vl_smallest := 100000; |
| var integer vl_smallestIdx := 0; |
| var EPTF_IntegerList vl_createNodes := tsp_EPTF_RBT_Test_initIntegerTree; |
| |
| // Init |
| f_EPTF_RBTreeI_initIntegerTree(rb_Tree); |
| if(f_EPTF_RBTreeI_getBusyEventHeadIndex(rb_Tree, vl_getHeadIdx)) { |
| log("Error: ", %definitionId&" returns true"); |
| setverdict(fail); |
| } else { |
| setverdict(pass); |
| } |
| //find smallest |
| for(var integer i := 0; i < sizeof(vl_createNodes); i := i + 1) { |
| if (vl_smallest > vl_createNodes[i]) { |
| vl_smallest := vl_createNodes[i]; |
| vl_smallestIdx := i + 2; |
| } |
| } |
| for(var integer i := 0; i < sizeof(vl_createNodes); i := i + 1) |
| { |
| vl_data := {i + 2}; |
| vl_getHeadIdx := f_EPTF_RBTreeI_createNewIntegerNode(rb_Tree, vl_createNodes[i], vl_data); |
| } |
| log(rb_Tree); |
| if(f_EPTF_RBTreeI_getBusyEventHeadIndex(rb_Tree, vl_getHeadIdx)) { |
| if(vl_getHeadIdx == vl_smallestIdx) { |
| setverdict(pass); |
| } else { |
| log("Error: wrong busy event head index: ", vl_getHeadIdx, " expected: ", vl_smallestIdx); |
| setverdict(fail); |
| } |
| } else { |
| log("Error: ", %definitionId&" returns false"); |
| setverdict(fail); |
| } |
| |
| } |
| |
| /////////////////////////////////////////////////////////// |
| // Testcase: tc_EPTF_RBTreeF_searchSmallestNode |
| // |
| // Purpose: |
| // to test f_EPTF_RBTreeF_searchSmallestNode() function |
| // |
| // Requirement: |
| // - |
| // |
| // Action: |
| // calls f_EPTF_RBTreeF_initFloatTree() function |
| // calls f_EPTF_RBTreeF_searchSmallestNode() function |
| // search the smallest node key in <tsp_EPTF_RBT_Test_initFloatTree> |
| // creates several nodes by calling f_EPTF_RBTreeF_createNewFloatNode() function with <tsp_EPTF_RBT_Test_initFloatTree> |
| // calls the f_EPTF_RBTreeF_searchSmallestNode() function |
| // |
| // Expected Result: |
| // first time the tested function returs with false, then out parameter *pl_indexFound* matches with the founded index |
| /////////////////////////////////////////////////////////// |
| testcase tc_EPTF_RBTreeF_searchSmallestNode() runs on RBT_Test_CT { |
| |
| var EPTF_Float_RedBlackTree rb_Tree; |
| var EPTF_IntegerList vl_data := {}; |
| var EPTF_FloatNode vl_node; |
| var integer vl_getNodeIdx; |
| var float vl_smallest := 100000.0; |
| var integer vl_smallestIdx := 0; |
| var EPTF_FloatList vl_createNodes := tsp_EPTF_RBT_Test_initFloatTree; |
| |
| // Init |
| f_EPTF_RBTreeF_initFloatTree(rb_Tree); |
| if(f_EPTF_RBTreeF_searchSmallestNode(rb_Tree, vl_node, vl_getNodeIdx)) { |
| log("Error: ", %definitionId&" returns true"); |
| setverdict(fail); |
| } else { |
| setverdict(pass); |
| } |
| //find smallest |
| for(var integer i := 0; i < sizeof(vl_createNodes); i := i + 1) { |
| if (vl_smallest > vl_createNodes[i]) { |
| vl_smallest := vl_createNodes[i]; |
| vl_smallestIdx := i + 2; |
| } |
| } |
| |
| for(var integer i := 0; i < sizeof(vl_createNodes); i := i + 1) |
| { |
| vl_data := {i + 2}; |
| vl_getNodeIdx := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, vl_createNodes[i], vl_data); |
| } |
| |
| if(f_EPTF_RBTreeF_searchSmallestNode(rb_Tree, vl_node, vl_getNodeIdx)) { |
| if(vl_getNodeIdx == vl_smallestIdx) { |
| setverdict(pass); |
| } else { |
| log("Error: wrong node index for smallest node - ", vl_smallest, ": ", vl_getNodeIdx, " expected: ", vl_smallestIdx); |
| setverdict(fail); |
| } |
| } else { |
| log("Error: ", %definitionId&" returns false"); |
| setverdict(fail); |
| } |
| |
| } |
| |
| /////////////////////////////////////////////////////////// |
| // Testcase: tc_EPTF_RBTreeF_getSmallestNodeFromCache |
| // |
| // Purpose: |
| // to test f_EPTF_RBTreeF_getSmallestNodeFromCache() function |
| // |
| // Requirement: |
| // - |
| // |
| // Action: |
| // calls f_EPTF_RBTreeF_initFloatTree() function |
| // calls f_EPTF_RBTreeF_getSmallestNodeFromCache() function |
| // search the smallest node key in <tsp_EPTF_RBT_Test_initFloatTree> |
| // creates several nodes by calling f_EPTF_RBTreeF_createNewFloatNode() function with <tsp_EPTF_RBT_Test_initFloatTree> |
| // calls the f_EPTF_RBTreeF_getSmallestNodeFromCache() function |
| // |
| // Expected Result: |
| // first time the tested function returs with false, then out parameter *pl_nodeFound* matches with the founded index |
| /////////////////////////////////////////////////////////// |
| testcase tc_EPTF_RBTreeF_getSmallestNodeFromCache() runs on RBT_Test_CT { |
| |
| var EPTF_Float_RedBlackTree rb_Tree; |
| var EPTF_IntegerList vl_data := {}; |
| var EPTF_FloatNode vl_node; |
| var integer vl_getNodeIdx; |
| var EPTF_FloatNode vl_smallest := {key := 100000.0,data := {0}}; |
| var EPTF_FloatList vl_createNodes := tsp_EPTF_RBT_Test_initFloatTree; |
| |
| // Init |
| f_EPTF_RBTreeF_initFloatTree(rb_Tree); |
| |
| if(f_EPTF_RBTreeF_getSmallestNodeFromCache(rb_Tree, vl_node)) { |
| log("Error: ", %definitionId&" returns true"); |
| setverdict(fail); |
| } else { |
| setverdict(pass); |
| } |
| //find smallest |
| for(var integer i := 0; i < sizeof(vl_createNodes); i := i + 1) { |
| if (vl_smallest.key > vl_createNodes[i]) { |
| vl_smallest.key := vl_createNodes[i]; |
| vl_smallest.data[0] := i + 2; |
| } |
| } |
| |
| for(var integer i := 0; i < sizeof(vl_createNodes); i := i + 1) |
| { |
| vl_data := {i + 2}; |
| vl_getNodeIdx := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, vl_createNodes[i], vl_data); |
| } |
| |
| if(f_EPTF_RBTreeF_getSmallestNodeFromCache(rb_Tree, vl_node)) { |
| |
| if(vl_node == vl_smallest) { |
| setverdict(pass); |
| } else { |
| log("Error: wrong node index for smallest node ", vl_node, " expected: ", vl_smallest); |
| setverdict(fail); |
| } |
| } else { |
| log("Error: ", %definitionId&" returns false"); |
| setverdict(fail); |
| } |
| |
| } |
| |
| /////////////////////////////////////////////////////////// |
| // Testcase: tc_EPTF_RBTreeF_getBusyEventHeadIndex |
| // |
| // Purpose: |
| // to test f_RBTree_getBusyEventHeadIndex() function |
| // |
| // Requirement: |
| // - |
| // |
| // Action: |
| // calls f_EPTF_RBTreeF_initFloatTree() function |
| // calls f_RBTree_getBusyEventHeadIndex() function |
| // search the smallest node key in <tsp_EPTF_RBT_Test_initFloatTree> |
| // creates several nodes by calling f_EPTF_RBTreeF_createNewFloatNode() function with <tsp_EPTF_RBT_Test_initFloatTree> |
| // calls the f_RBTree_getBusyEventHeadIndex() function |
| // |
| // Expected Result: |
| // first time the tested function returs with false, then out parameter *pl_idx* matches with the founded index |
| /////////////////////////////////////////////////////////// |
| testcase tc_EPTF_RBTreeF_getBusyEventHeadIndex() runs on RBT_Test_CT { |
| |
| var EPTF_Float_RedBlackTree rb_Tree; |
| var EPTF_IntegerList vl_data := {}; |
| var integer vl_getHeadIdx; |
| var float vl_smallest := 100000.0; |
| var integer vl_smallestIdx := 0; |
| var EPTF_FloatList vl_createNodes := tsp_EPTF_RBT_Test_initFloatTree; |
| |
| // Init |
| f_EPTF_RBTreeF_initFloatTree(rb_Tree); |
| if(f_RBTree_getBusyEventHeadIndex(rb_Tree, vl_getHeadIdx)) { |
| log("Error: ", %definitionId&" returns true"); |
| setverdict(fail); |
| } else { |
| setverdict(pass); |
| } |
| //find smallest |
| for(var integer i := 0; i < sizeof(vl_createNodes); i := i + 1) { |
| if (vl_smallest > vl_createNodes[i]) { |
| vl_smallest := vl_createNodes[i]; |
| vl_smallestIdx := i + 2; |
| } |
| } |
| for(var integer i := 0; i < sizeof(vl_createNodes); i := i + 1) |
| { |
| vl_data := {i + 2}; |
| vl_getHeadIdx := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, vl_createNodes[i], vl_data); |
| } |
| log(rb_Tree); |
| |
| if(f_RBTree_getBusyEventHeadIndex(rb_Tree, vl_getHeadIdx)) { |
| if(vl_getHeadIdx == vl_smallestIdx) { |
| setverdict(pass); |
| } else { |
| log("Error: wrong busy event head index: ", vl_getHeadIdx, " expected: ", vl_smallestIdx); |
| setverdict(fail); |
| } |
| } else { |
| log("Error: ", %definitionId&" returns false"); |
| setverdict(fail); |
| } |
| |
| } |
| |
| /////////////////////////////////////////////////////////// |
| // Testcase: tc_EPTF_RBTree_getNextSmallestFloatElementIndex |
| // |
| // Purpose: |
| // to test f_RBTree_getNextSmallestFloatElementIndex() function |
| // |
| // Requirement: |
| // - |
| // |
| // Action: |
| // calls f_EPTF_RBTreeF_initFloatTree() function |
| // calls f_RBTree_getNextSmallestFloatElementIndex() function |
| // search the smallest and second smallest node key in <tsp_EPTF_RBT_Test_initFloatTree> |
| // creates several nodes by calling f_EPTF_RBTreeF_createNewFloatNode() function with <tsp_EPTF_RBT_Test_initFloatTree> |
| // calss the f_EPTF_RBTreeF_searchSmallestNode() function |
| // calls the f_RBTree_getNextSmallestFloatElementIndex() function with the smallest node index |
| // |
| // Expected Result: |
| // first time the tested function returs with false, then out parameter *pl_indexFound* matches with the founded second smallest node index |
| /////////////////////////////////////////////////////////// |
| testcase tc_EPTF_RBTree_getNextSmallestFloatElementIndex() runs on RBT_Test_CT { |
| |
| var EPTF_Float_RedBlackTree rb_Tree; |
| var EPTF_IntegerList vl_data := {}; |
| var EPTF_FloatNode vl_node; |
| var integer vl_getNodeIdx; |
| var float vl_smallest := 100000.0; |
| var float vl_2ndSmallest := 100000.0; |
| var integer vl_smallestIdx := 0; |
| var integer vl_2ndSmallestIdx := 0; |
| var EPTF_FloatList vl_createNodes := tsp_EPTF_RBT_Test_initFloatTree; |
| |
| // Init |
| f_EPTF_RBTreeF_initFloatTree(rb_Tree); |
| if(f_RBTree_getNextSmallestFloatElementIndex(rb_Tree, vl_smallestIdx, vl_2ndSmallestIdx)) { |
| log("Error: ", %definitionId&" returns true"); |
| setverdict(fail); |
| } else { |
| setverdict(pass); |
| } |
| //find smallest |
| for(var integer i := 0; i < sizeof(vl_createNodes); i := i + 1) { |
| if (vl_smallest > vl_createNodes[i]) { |
| vl_2ndSmallest := vl_smallest; |
| vl_2ndSmallestIdx := vl_smallestIdx; |
| vl_smallest := vl_createNodes[i]; |
| vl_smallestIdx := i + 2; |
| } |
| } |
| |
| for(var integer i := 0; i < sizeof(vl_createNodes); i := i + 1) |
| { |
| vl_data := {i + 2}; |
| vl_getNodeIdx := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, vl_createNodes[i], vl_data); |
| } |
| |
| if(f_EPTF_RBTreeF_searchSmallestNode(rb_Tree, vl_node, vl_getNodeIdx)) { |
| if(vl_getNodeIdx == vl_smallestIdx) { |
| setverdict(pass); |
| } else { |
| log("Error: wrong node index for smallest node - ", vl_smallest, ": ", vl_getNodeIdx, " expected: ", vl_smallestIdx); |
| setverdict(fail); |
| } |
| } else { |
| log("Error: ", %definitionId&" returns false"); |
| setverdict(fail); |
| } |
| |
| if(f_RBTree_getNextSmallestFloatElementIndex(rb_Tree, vl_smallestIdx, vl_getNodeIdx)) { |
| if(vl_getNodeIdx == vl_2ndSmallestIdx) { |
| setverdict(pass); |
| } else { |
| log("Error: wrong node index for 2nd smallest node - ", vl_2ndSmallest, ": ", vl_getNodeIdx, " expected: ", vl_2ndSmallestIdx); |
| setverdict(fail); |
| } |
| } else { |
| log("Error: ", %definitionId&" returns false"); |
| setverdict(fail); |
| } |
| |
| } |
| |
| |
| testcase tc_EPTF_RBTreeF_testFloatTreeCluster() |
| runs on RBT_Test_CT |
| { |
| var EPTF_Float_RedBlackTree rb_Tree; |
| |
| // Init |
| f_EPTF_RBTreeF_initFloatTree(rb_Tree); |
| |
| // insert nodes with same key -> cluster |
| var integer vl_head := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 1.0, {1}); |
| var integer vl_newHead := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 1.0, {2}); |
| f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 1.0, {3}); |
| var integer vl_newTail := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 1.0, {4}); |
| var integer vl_tail := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 1.0, {5}); |
| log(rb_Tree); |
| |
| if(rb_Tree.nodes[vl_newHead].isHeadInSameKeysCluster == true) { setverdict(fail); } |
| if(rb_Tree.nodes[vl_newTail].fwd < 0) { setverdict(fail); } |
| |
| f_EPTF_RBTreeF_removeFloatNode(rb_Tree, vl_head, true); // remove head, newHead becomes start of cluster, tail should point to newHead as start of cluster |
| log(rb_Tree); |
| |
| if(rb_Tree.nodes[vl_newHead].isHeadInSameKeysCluster == true) { setverdict(pass); } |
| else { setverdict(fail); } |
| if(rb_Tree.nodes[vl_newHead].endOfClusterIdx == vl_tail) { setverdict(pass); } |
| else { setverdict(fail); } |
| if(rb_Tree.nodes[vl_tail].startOfClusterIdx == vl_newHead) { setverdict(pass); } |
| else { setverdict(fail); } |
| |
| f_EPTF_RBTreeF_removeFloatNode(rb_Tree, vl_tail, true); // remove tail, newTail becomes end of cluster, newHead should point to newTail as end of cluster |
| log(rb_Tree); |
| |
| if(rb_Tree.nodes[vl_newTail].fwd < 0) { setverdict(pass); } |
| else { setverdict(fail); } |
| if(rb_Tree.nodes[vl_newTail].startOfClusterIdx == vl_newHead) { setverdict(pass); } |
| else { setverdict(fail); } |
| if(rb_Tree.nodes[vl_newHead].endOfClusterIdx == vl_newTail) { setverdict(pass); } |
| else { setverdict(fail); } |
| } |
| |
| |
| group RBTv2 { |
| |
| type enumerated InsertOrder { |
| ascending, |
| descending, |
| random |
| }; |
| |
| modulepar boolean tsp_pngEachStep := false; |
| modulepar boolean tsp_pngEachStep_remove := false; |
| modulepar boolean tsp_pngFinal := false; |
| |
| function f_insert(out integer pl_tree, out integer pl_smallestIdx, in InsertOrder pl_order, in charstring pl_pngPrefix) |
| runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT("mtc"); |
| var EPTF_RBT_TreeId vl_dummy := f_EPTF_RBT_createIntTree(); |
| pl_tree := f_EPTF_RBT_createFloatTree(); |
| var EPTF_IntegerList vl_items := {}; |
| pl_smallestIdx := -1; |
| var float pl_smallestKey := 10.0; |
| var float vl_key := 1.0; |
| for(var integer i:=0; i<100; i:=i+1) { |
| select(pl_order) { |
| case(ascending) { |
| vl_key := vl_key + 0.01; |
| } |
| case(descending) { |
| vl_key := vl_key - 0.01; |
| } |
| case else { |
| vl_key := int2float(float2int(rnd()*100.0))/100.0; |
| } |
| } |
| if(vl_key < pl_smallestKey) { |
| pl_smallestKey := vl_key; |
| pl_smallestIdx := i; |
| } |
| vl_items[i] := f_EPTF_RBT_insertFloatItem(pl_tree, vl_key); |
| if(tsp_pngEachStep) { |
| if(i<10) { |
| f_EPTF_RBT_dumpToPng(pl_tree, pl_pngPrefix&"00"&int2str(i)); |
| } else if(i<100) { |
| f_EPTF_RBT_dumpToPng(pl_tree, pl_pngPrefix&"0"&int2str(i)); |
| } else { |
| f_EPTF_RBT_dumpToPng(pl_tree, pl_pngPrefix&int2str(i)); |
| } |
| } |
| if(not f_EPTF_RBT_isTreeValid(pl_tree)) { |
| setverdict(fail, "invalid tree (step "&int2str(i)&")"); |
| f_EPTF_RBT_dumpToPng(pl_tree, pl_pngPrefix&"invalid_"&int2str(i)); |
| f_EPTF_Base_stop(none); |
| } |
| } |
| if(tsp_pngFinal) { |
| f_EPTF_RBT_dumpToPng(pl_tree, pl_pngPrefix&"final"); |
| } |
| } |
| |
| function f_insertCheck(in integer pl_tree, in integer pl_smallestIdx, in charstring pl_pngPrefix) runs on EPTF_RBT_CT |
| { |
| if(not f_EPTF_RBT_isTreeValid(pl_tree)) { |
| setverdict(fail, "invalid tree"); |
| f_EPTF_RBT_dumpToPng(pl_tree, pl_pngPrefix&"final_invalid"); |
| f_EPTF_Base_stop(none); |
| } |
| var EPTF_RBT_ItemIdx vl_smallest := f_EPTF_RBT_getItemWithSmallestKey(pl_tree); |
| if(pl_smallestIdx == vl_smallest) { |
| f_EPTF_Base_stop(pass); |
| } else { |
| setverdict(fail, "invalid smallest key "& |
| int2str(vl_smallest)&", should be "&int2str(pl_smallestIdx)); |
| f_EPTF_Base_stop(none); |
| } |
| } |
| |
| testcase tc_EPTF_RBT_Test_insertAscending() runs on EPTF_RBT_CT |
| { |
| var integer vl_tree, vl_smallest; |
| f_insert(vl_tree, vl_smallest, ascending, "tree_ascending_"); |
| f_insertCheck(vl_tree, vl_smallest, "tree_ascending_"); |
| } |
| |
| testcase tc_EPTF_RBT_Test_insertDescending() runs on EPTF_RBT_CT |
| { |
| var integer vl_tree, vl_smallest; |
| f_insert(vl_tree, vl_smallest, descending, "tree_descending_"); |
| f_insertCheck(vl_tree, vl_smallest, "tree_descending_"); |
| } |
| |
| testcase tc_EPTF_RBT_Test_insertRandom() runs on EPTF_RBT_CT |
| { |
| var integer vl_tree, vl_smallest; |
| f_insert(vl_tree, vl_smallest, random, "tree_random_"); |
| f_insertCheck(vl_tree, vl_smallest, "tree_random_"); |
| } |
| |
| testcase tc_EPTF_RBT_Test_Neg_insertIntoNonexistingTree() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| f_EPTF_Base_setExpectedAssertMsg("f_EPTF_RBT_insertIntItem: invalid tree 2, number of trees: 0"); |
| var EPTF_RBT_ItemIdx vl_itemIdx := f_EPTF_RBT_insertIntItem(2, 5); |
| f_EPTF_Base_stop(); |
| } |
| |
| testcase tc_EPTF_RBT_Test_insertIntParentBlack() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| var EPTF_RBT_TreeInitNode vl_initialTree := { |
| isRed:=false, |
| key:={intKey:=4}, |
| leftChild:={ |
| isRed:=false, |
| key:={intKey:=2}, |
| leftChild:=omit, |
| rightChild:=omit |
| }, |
| rightChild:={ |
| isRed:=false, |
| key:={intKey:=5}, |
| leftChild:=omit, |
| rightChild:=omit |
| } |
| }; |
| var integer vl_tree := f_EPTF_RBT_createAndInitTree("IntRBT", vl_initialTree); |
| |
| var EPTF_RBT_ItemIdx vl_itemIdx := f_EPTF_RBT_insertIntItem(vl_tree, 3); |
| |
| var EPTF_RBT_ItemIdx vl_root := f_EPTF_RBT_getRoot(vl_tree); |
| var EPTF_RBT_ItemIdx vl_rootL := f_EPTF_RBT_getLeft(vl_tree, vl_root); |
| var EPTF_RBT_ItemIdx vl_rootR := f_EPTF_RBT_getRight(vl_tree, vl_root); |
| var EPTF_RBT_ItemIdx vl_rootLR := f_EPTF_RBT_getRight(vl_tree, vl_rootL); |
| |
| var verdicttype vl_verdict := pass; |
| if( f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_root) != 4 or f_EPTF_RBT_getItemType(vl_tree, vl_root) != BlackNode) |
| { |
| vl_verdict := fail; |
| } |
| if( f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootL) != 2 or f_EPTF_RBT_getItemType(vl_tree, vl_rootL) != BlackNode) |
| { |
| vl_verdict := fail; |
| } |
| if( f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootR) != 5 or f_EPTF_RBT_getItemType(vl_tree, vl_rootR) != BlackNode) |
| { |
| vl_verdict := fail; |
| } |
| if( f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootLR) != 3 or f_EPTF_RBT_getItemType(vl_tree, vl_rootLR) != RedNode) |
| { |
| vl_verdict := fail; |
| } |
| if(vl_verdict == fail){setverdict(fail, "Incorrect insert-algorithm if parent is black.")} |
| f_EPTF_Base_stop(vl_verdict); |
| } |
| |
| testcase tc_EPTF_RBT_Test_insertIntParentRedUncleRed() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| var EPTF_RBT_TreeInitNode vl_initialTree := { |
| isRed:=false, |
| key:={intKey:=4}, |
| leftChild:={ |
| isRed:=true, |
| key:={intKey:=2}, |
| leftChild:=omit, |
| rightChild:=omit |
| }, |
| rightChild:={ |
| isRed:=true, |
| key:={intKey:=5}, |
| leftChild:=omit, |
| rightChild:=omit |
| } |
| }; |
| var integer vl_tree := f_EPTF_RBT_createAndInitTree("IntRBT", vl_initialTree); |
| |
| var EPTF_RBT_ItemIdx vl_itemIdx := f_EPTF_RBT_insertIntItem(vl_tree, 3); |
| |
| var EPTF_RBT_ItemIdx vl_root := f_EPTF_RBT_getRoot(vl_tree); |
| var EPTF_RBT_ItemIdx vl_rootL := f_EPTF_RBT_getLeft(vl_tree, vl_root); |
| var EPTF_RBT_ItemIdx vl_rootR := f_EPTF_RBT_getRight(vl_tree, vl_root); |
| var EPTF_RBT_ItemIdx vl_rootLR := f_EPTF_RBT_getRight(vl_tree, vl_rootL); |
| |
| var verdicttype vl_verdict := pass; |
| if( f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_root) != 4 or f_EPTF_RBT_getItemType(vl_tree, vl_root) != BlackNode) |
| { |
| vl_verdict := fail; |
| } |
| if( f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootL) != 2 or f_EPTF_RBT_getItemType(vl_tree, vl_rootL) != BlackNode) |
| { |
| vl_verdict := fail; |
| } |
| if( f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootR) != 5 or f_EPTF_RBT_getItemType(vl_tree, vl_rootR) != BlackNode) |
| { |
| vl_verdict := fail; |
| } |
| if( f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootLR) != 3 or f_EPTF_RBT_getItemType(vl_tree, vl_rootLR) != RedNode) |
| { |
| vl_verdict := fail; |
| } |
| if(vl_verdict == fail){setverdict(fail, "Incorrect insert-algorithm if parent is red and uncle is red too.")} |
| f_EPTF_Base_stop(vl_verdict); |
| } |
| |
| testcase tc_EPTF_RBT_Test_insertIntParentRedUncleRed2() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| var EPTF_RBT_TreeInitNode vl_initialTree := { |
| isRed:=false, |
| key:={intKey:=10}, |
| leftChild:= { |
| isRed:=false, |
| key:={intKey:=4}, |
| leftChild:={ |
| isRed:=true, |
| key:={intKey:=2}, |
| leftChild:=omit, |
| rightChild:=omit |
| }, |
| rightChild:={ |
| isRed:=true, |
| key:={intKey:=5}, |
| leftChild:=omit, |
| rightChild:=omit |
| } |
| }, |
| rightChild:={ |
| isRed:=true, |
| key:={intKey:=20}, |
| leftChild:={ |
| isRed:=false, |
| key:={intKey:=15}, |
| leftChild:=omit, |
| rightChild:=omit |
| }, |
| rightChild:={ |
| isRed:=false, |
| key:={intKey:=25}, |
| leftChild:=omit, |
| rightChild:=omit |
| } |
| } |
| }; |
| |
| var integer vl_tree := f_EPTF_RBT_createAndInitTree("IntRBT", vl_initialTree); |
| |
| var EPTF_RBT_ItemIdx vl_itemIdx := f_EPTF_RBT_insertIntItem(vl_tree, 3); |
| |
| var EPTF_RBT_ItemIdx vl_root := f_EPTF_RBT_getRoot(vl_tree); |
| var EPTF_RBT_ItemIdx vl_rootL := f_EPTF_RBT_getLeft(vl_tree, vl_root); |
| var EPTF_RBT_ItemIdx vl_rootR := f_EPTF_RBT_getRight(vl_tree, vl_root); |
| var EPTF_RBT_ItemIdx vl_rootLL := f_EPTF_RBT_getLeft(vl_tree, vl_rootL); |
| var EPTF_RBT_ItemIdx vl_rootLR := f_EPTF_RBT_getRight(vl_tree, vl_rootL); |
| var EPTF_RBT_ItemIdx vl_rootRL := f_EPTF_RBT_getLeft(vl_tree, vl_rootR); |
| var EPTF_RBT_ItemIdx vl_rootRR := f_EPTF_RBT_getRight(vl_tree, vl_rootR); |
| var EPTF_RBT_ItemIdx vl_rootLLR := f_EPTF_RBT_getRight(vl_tree, vl_rootLL); |
| |
| var verdicttype vl_verdict := pass; |
| if( f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_root) != 10 or f_EPTF_RBT_getItemType(vl_tree, vl_root) != BlackNode) |
| { |
| vl_verdict := fail; |
| } |
| if( f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootL) != 4 or f_EPTF_RBT_getItemType(vl_tree, vl_rootL) != RedNode) |
| { |
| vl_verdict := fail; |
| } |
| if( f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootR) != 20 or f_EPTF_RBT_getItemType(vl_tree, vl_rootR) != RedNode) |
| { |
| vl_verdict := fail; |
| } |
| if( f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootLR) != 5 or f_EPTF_RBT_getItemType(vl_tree, vl_rootLR) != BlackNode) |
| { |
| vl_verdict := fail; |
| } |
| if( f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootLL) != 2 or f_EPTF_RBT_getItemType(vl_tree, vl_rootLL) != BlackNode) |
| { |
| vl_verdict := fail; |
| } |
| if( f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootRL) != 15 or f_EPTF_RBT_getItemType(vl_tree, vl_rootRL) != BlackNode) |
| { |
| vl_verdict := fail; |
| } |
| if( f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootRR) != 25 or f_EPTF_RBT_getItemType(vl_tree, vl_rootRR) != BlackNode) |
| { |
| vl_verdict := fail; |
| } |
| if( f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootLLR) != 3 or f_EPTF_RBT_getItemType(vl_tree, vl_rootLLR) != RedNode) |
| { |
| vl_verdict := fail; |
| } |
| if(vl_verdict == fail){setverdict(fail, "Incorrect insert-algorithm if parent is red and uncle is red too.")} |
| f_EPTF_Base_stop(vl_verdict); |
| } |
| |
| testcase tc_EPTF_RBT_Test_insertIntParentRedUncleBlack() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| var EPTF_RBT_TreeInitNode vl_initialTree := { |
| isRed:=false, |
| key:={intKey:=10}, |
| leftChild:={ |
| isRed:=true, |
| key:={intKey:=5}, |
| leftChild:=omit, |
| rightChild:=omit |
| }, |
| rightChild:=omit |
| }; |
| var integer vl_tree := f_EPTF_RBT_createAndInitTree("IntRBT", vl_initialTree); |
| |
| var EPTF_RBT_ItemIdx vl_itemIdx := f_EPTF_RBT_insertIntItem(vl_tree, 3); |
| |
| var EPTF_RBT_ItemIdx vl_root := f_EPTF_RBT_getRoot(vl_tree); |
| var EPTF_RBT_ItemIdx vl_rootL := f_EPTF_RBT_getLeft(vl_tree, vl_root); |
| var EPTF_RBT_ItemIdx vl_rootR := f_EPTF_RBT_getRight(vl_tree, vl_root); |
| var EPTF_RBT_ItemIdx vl_rootLL := f_EPTF_RBT_getLeft(vl_tree, vl_rootL); |
| |
| var verdicttype vl_verdict := pass; |
| if( f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_root) != 5 or f_EPTF_RBT_getItemType(vl_tree, vl_root) != BlackNode) |
| { |
| vl_verdict := fail; |
| } |
| if( f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootL) != 3 or f_EPTF_RBT_getItemType(vl_tree, vl_rootL) != RedNode) |
| { |
| vl_verdict := fail; |
| } |
| if( f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootR) != 10 or f_EPTF_RBT_getItemType(vl_tree, vl_rootR) != RedNode) |
| { |
| vl_verdict := fail; |
| } |
| if(vl_verdict == fail){setverdict(fail, "Incorrect insert-algorithm if parent is red and uncle is black.")} |
| f_EPTF_Base_stop(vl_verdict); |
| } |
| |
| testcase tc_EPTF_RBT_Test_insertIntParentRedUncleBlack2() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| var EPTF_RBT_TreeInitNode vl_initialTree := { |
| isRed:=false, |
| key:={intKey:=10}, |
| leftChild:={ |
| isRed:=true, |
| key:={intKey:=3}, |
| leftChild:=omit, |
| rightChild:=omit |
| }, |
| rightChild:=omit |
| }; |
| var integer vl_tree := f_EPTF_RBT_createAndInitTree("IntRBT", vl_initialTree); |
| |
| var EPTF_RBT_ItemIdx vl_itemIdx := f_EPTF_RBT_insertIntItem(vl_tree, 5); |
| |
| var EPTF_RBT_ItemIdx vl_root := f_EPTF_RBT_getRoot(vl_tree); |
| var EPTF_RBT_ItemIdx vl_rootL := f_EPTF_RBT_getLeft(vl_tree, vl_root); |
| var EPTF_RBT_ItemIdx vl_rootR := f_EPTF_RBT_getRight(vl_tree, vl_root); |
| var EPTF_RBT_ItemIdx vl_rootLL := f_EPTF_RBT_getLeft(vl_tree, vl_rootL); |
| |
| var verdicttype vl_verdict := pass; |
| if( f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_root) != 5 or f_EPTF_RBT_getItemType(vl_tree, vl_root) != BlackNode) |
| { |
| vl_verdict := fail; |
| } |
| if( f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootL) != 3 or f_EPTF_RBT_getItemType(vl_tree, vl_rootL) != RedNode) |
| { |
| vl_verdict := fail; |
| } |
| if( f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootR) != 10 or f_EPTF_RBT_getItemType(vl_tree, vl_rootR) != RedNode) |
| { |
| vl_verdict := fail; |
| } |
| if(vl_verdict == fail){setverdict(fail, "Incorrect insert-algorithm if parent is red and uncle is black.")} |
| f_EPTF_Base_stop(vl_verdict); |
| } |
| |
| testcase tc_EPTF_RBT_Test_deleteTree() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| var integer vl_tree := f_EPTF_RBT_createIntTree("IntRBT"); |
| f_EPTF_RBT_insertIntItem(vl_tree, 3); |
| f_EPTF_RBT_insertIntItem(vl_tree, 8); |
| f_EPTF_RBT_insertIntItem(vl_tree, 5); |
| f_EPTF_RBT_deleteTree(vl_tree); |
| f_EPTF_Base_setExpectedAssertMsg("f_EPTF_RBT_insertIntItem: invalid tree 0, tree has been deleted."); |
| f_EPTF_RBT_insertIntItem(vl_tree, 7); |
| f_EPTF_Base_stop(); |
| } |
| |
| testcase tc_EPTF_RBT_Test_Neg_deleteTree() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| var integer vl_tree := f_EPTF_RBT_createIntTree("IntRBT"); |
| f_EPTF_RBT_insertIntItem(vl_tree, 3); |
| f_EPTF_RBT_insertIntItem(vl_tree, 8); |
| f_EPTF_RBT_insertIntItem(vl_tree, 5); |
| f_EPTF_RBT_deleteTree(vl_tree); |
| f_EPTF_Base_setExpectedAssertMsg("f_EPTF_RBT_deleteTree: invalid tree 0, tree has been deleted."); |
| f_EPTF_RBT_deleteTree(vl_tree); |
| f_EPTF_Base_stop(); |
| } |
| |
| testcase tc_EPTF_RBT_Test_getName() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| var integer vl_tree := f_EPTF_RBT_createIntTree("IntRBT"); |
| var verdicttype vl_verdict := fail; |
| if(f_EPTF_RBT_getName(vl_tree) == "IntRBT") |
| { |
| vl_verdict := pass; |
| } |
| f_EPTF_Base_stop(vl_verdict); |
| } |
| |
| testcase tc_EPTF_RBT_Test_Neg_getName() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| var integer vl_tree := f_EPTF_RBT_createIntTree("IntRBT"); |
| f_EPTF_RBT_deleteTree(vl_tree); |
| f_EPTF_Base_setExpectedAssertMsg("f_EPTF_RBT_getName: invalid tree 0, tree has been deleted."); |
| f_EPTF_RBT_getName(vl_tree); |
| f_EPTF_Base_stop(); |
| } |
| |
| testcase tc_EPTF_RBT_Test_removeItem() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| var integer vl_tree := f_EPTF_RBT_createIntTree("IntRBT"); |
| var EPTF_RBT_ItemIdx vl_itemIdx := f_EPTF_RBT_insertIntItem(vl_tree, 3); |
| f_EPTF_RBT_removeItem(vl_tree, vl_itemIdx); |
| f_EPTF_Base_setExpectedAssertMsg("f_EPTF_RBT_getKeyOfIntItem: item 0 in tree \"IntRBT\" is in the free chain"); |
| var integer vl_key := f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_itemIdx); |
| f_EPTF_Base_stop(); |
| } |
| |
| //Sibling is black with two red children |
| |
| testcase tc_EPTF_RBT_Test_removeBlack1() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| var EPTF_RBT_TreeInitNode vl_initialTree := { |
| isRed:=false, |
| key:={intKey:=10}, |
| leftChild:={ |
| isRed:=false, |
| key:={intKey:=5}, |
| leftChild:=omit, |
| rightChild:=omit |
| }, |
| rightChild:={ |
| isRed:=false, |
| key:={intKey:=12}, |
| leftChild:={ |
| isRed:=true, |
| key:={intKey:=11}, |
| leftChild:=omit, |
| rightChild:=omit |
| }, |
| rightChild:={ |
| isRed:=true, |
| key:={intKey:=13}, |
| leftChild:=omit, |
| rightChild:=omit |
| } |
| } |
| }; |
| var integer vl_tree := f_EPTF_RBT_createAndInitTree("IntRBT", vl_initialTree); |
| f_EPTF_RBT_removeItem(vl_tree, f_EPTF_RBT_findFirstItemByIntKey(vl_tree, 5)); |
| |
| var verdicttype vl_verdict := pass; |
| |
| var EPTF_RBT_ItemIdx vl_root := f_EPTF_RBT_getRoot(vl_tree); |
| var EPTF_RBT_ItemIdx vl_rootL := f_EPTF_RBT_getLeft(vl_tree, vl_root); |
| var EPTF_RBT_ItemIdx vl_rootR := f_EPTF_RBT_getRight(vl_tree, vl_root); |
| var EPTF_RBT_ItemIdx vl_rootRR := f_EPTF_RBT_getRight(vl_tree, vl_rootR); |
| |
| if(f_EPTF_RBT_getItemType(vl_tree, vl_root) != BlackNode or f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_root) != 11) |
| { |
| vl_verdict := fail; |
| } |
| if(f_EPTF_RBT_getItemType(vl_tree, vl_rootL) != BlackNode or f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootL) != 10) |
| { |
| action("2"); |
| vl_verdict := fail; |
| } |
| if(f_EPTF_RBT_getItemType(vl_tree, vl_rootR) != BlackNode or f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootR) != 12) |
| { |
| vl_verdict := fail; |
| } |
| if(f_EPTF_RBT_getItemType(vl_tree, vl_rootRR) != RedNode or f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootRR) != 13) |
| { |
| action("4"); |
| vl_verdict := fail; |
| } |
| if(vl_verdict == fail) |
| { |
| setverdict(fail, "Wrong remove algorythm if node to be deleted and its sibling is black, and the sibling has two red child."); |
| } |
| f_EPTF_Base_stop(vl_verdict); |
| } |
| |
| //Sibling is black with a red left child |
| |
| testcase tc_EPTF_RBT_Test_removeBlack2() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| var EPTF_RBT_TreeInitNode vl_initialTree := { |
| isRed:=false, |
| key:={intKey:=10}, |
| leftChild:={ |
| isRed:=false, |
| key:={intKey:=5}, |
| leftChild:=omit, |
| rightChild:=omit |
| }, |
| rightChild:={ |
| isRed:=false, |
| key:={intKey:=12}, |
| leftChild:={ |
| isRed:=true, |
| key:={intKey:=11}, |
| leftChild:=omit, |
| rightChild:=omit |
| }, |
| rightChild:=omit |
| } |
| }; |
| var integer vl_tree := f_EPTF_RBT_createAndInitTree("IntRBT", vl_initialTree); |
| f_EPTF_RBT_removeItem(vl_tree, f_EPTF_RBT_findFirstItemByIntKey(vl_tree, 5)); |
| |
| var verdicttype vl_verdict := pass; |
| |
| var EPTF_RBT_ItemIdx vl_root := f_EPTF_RBT_getRoot(vl_tree); |
| var EPTF_RBT_ItemIdx vl_rootL := f_EPTF_RBT_getLeft(vl_tree, vl_root); |
| var EPTF_RBT_ItemIdx vl_rootR := f_EPTF_RBT_getRight(vl_tree, vl_root); |
| if(f_EPTF_RBT_getItemType(vl_tree, vl_root) != BlackNode or f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_root) != 11) |
| { |
| vl_verdict := fail; |
| } |
| if(f_EPTF_RBT_getItemType(vl_tree, vl_rootL) != BlackNode or f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootL) != 10) |
| { |
| vl_verdict := fail; |
| } |
| if(f_EPTF_RBT_getItemType(vl_tree, vl_rootR) != BlackNode or f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootR) != 12) |
| { |
| vl_verdict := fail; |
| } |
| if(vl_verdict == fail) |
| { |
| setverdict(fail, "Wrong remove algorythm if node to be deleted and its sibling is black, and the sibling has one, left child which is red."); |
| } |
| f_EPTF_Base_stop(vl_verdict); |
| } |
| |
| //Sibling is black with a red right child |
| |
| testcase tc_EPTF_RBT_Test_removeBlack3() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| var EPTF_RBT_TreeInitNode vl_initialTree := { |
| isRed:=false, |
| key:={intKey:=10}, |
| leftChild:={ |
| isRed:=false, |
| key:={intKey:=5}, |
| leftChild:=omit, |
| rightChild:=omit |
| }, |
| rightChild:={ |
| isRed:=false, |
| key:={intKey:=12}, |
| leftChild:=omit, |
| rightChild:={ |
| isRed:=true, |
| key:={intKey:=13}, |
| leftChild:=omit, |
| rightChild:=omit |
| } |
| } |
| }; |
| var integer vl_tree := f_EPTF_RBT_createAndInitTree("IntRBT", vl_initialTree); |
| f_EPTF_RBT_removeItem(vl_tree, f_EPTF_RBT_findFirstItemByIntKey(vl_tree, 5)); |
| |
| var verdicttype vl_verdict := pass; |
| |
| var EPTF_RBT_ItemIdx vl_root := f_EPTF_RBT_getRoot(vl_tree); |
| var EPTF_RBT_ItemIdx vl_rootL := f_EPTF_RBT_getLeft(vl_tree, vl_root); |
| var EPTF_RBT_ItemIdx vl_rootR := f_EPTF_RBT_getRight(vl_tree, vl_root); |
| if(f_EPTF_RBT_getItemType(vl_tree, vl_root) != BlackNode or f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_root) != 12) |
| { |
| vl_verdict := fail; |
| } |
| if(f_EPTF_RBT_getItemType(vl_tree, vl_rootL) != BlackNode or f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootL) != 10) |
| { |
| vl_verdict := fail; |
| } |
| if(f_EPTF_RBT_getItemType(vl_tree, vl_rootR) != BlackNode or f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootR) != 13) |
| { |
| vl_verdict := fail; |
| } |
| if(vl_verdict == fail) |
| { |
| setverdict(fail, "Wrong remove algorythm if node to be deleted and its sibling is black, and the sibling has one, right child which is red."); |
| } |
| f_EPTF_Base_stop(vl_verdict); |
| } |
| |
| //Sibling is black with no red children, and its parent is red |
| |
| testcase tc_EPTF_RBT_Test_removeBlack4() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| var EPTF_RBT_TreeInitNode vl_initialTree := { |
| isRed:=false, |
| key:={intKey:=10}, |
| leftChild:={ |
| isRed:=false, |
| key:={intKey:=5}, |
| leftChild:={ |
| isRed:=true, |
| key:={intKey:=3}, |
| leftChild:={ |
| isRed:=false, |
| key:={intKey:=1}, |
| leftChild:=omit, |
| rightChild:=omit |
| }, |
| rightChild:={ |
| isRed:=false, |
| key:={intKey:=4}, |
| leftChild:=omit, |
| rightChild:=omit |
| } |
| }, |
| rightChild:={ |
| isRed:=true, |
| key:={intKey:=8}, |
| leftChild:={ |
| isRed:=false, |
| key:={intKey:=7}, |
| leftChild:=omit, |
| rightChild:=omit |
| }, |
| rightChild:={ |
| isRed:=false, |
| key:={intKey:=9}, |
| leftChild:=omit, |
| rightChild:=omit |
| } |
| } |
| }, |
| rightChild:={ |
| isRed:=false, |
| key:={intKey:=15}, |
| leftChild:={ |
| isRed:=true, |
| key:={intKey:=13}, |
| leftChild:={ |
| isRed:=false, |
| key:={intKey:=12}, |
| leftChild:=omit, |
| rightChild:=omit |
| }, |
| rightChild:={ |
| isRed:=false, |
| key:={intKey:=14}, |
| leftChild:=omit, |
| rightChild:=omit |
| } |
| }, |
| rightChild:={ |
| isRed:=true, |
| key:={intKey:=18}, |
| leftChild:={ |
| isRed:=false, |
| key:={intKey:=17}, |
| leftChild:=omit, |
| rightChild:=omit |
| }, |
| rightChild:={ |
| isRed:=false, |
| key:={intKey:=19}, |
| leftChild:=omit, |
| rightChild:=omit |
| } |
| } |
| } |
| }; |
| var integer vl_tree := f_EPTF_RBT_createAndInitTree("IntRBT", vl_initialTree); |
| f_EPTF_RBT_removeItem(vl_tree, f_EPTF_RBT_findFirstItemByIntKey(vl_tree, 5)); |
| var EPTF_RBT_ItemIdx vl_root := f_EPTF_RBT_getRoot(vl_tree); |
| var EPTF_RBT_ItemIdx vl_rootL := f_EPTF_RBT_getLeft(vl_tree, vl_root); |
| var EPTF_RBT_ItemIdx vl_rootR := f_EPTF_RBT_getRight(vl_tree, vl_root); |
| var EPTF_RBT_ItemIdx vl_rootLL := f_EPTF_RBT_getLeft(vl_tree, vl_rootL); |
| var EPTF_RBT_ItemIdx vl_rootLR := f_EPTF_RBT_getRight(vl_tree, vl_rootL); |
| var EPTF_RBT_ItemIdx vl_rootRL := f_EPTF_RBT_getLeft(vl_tree, vl_rootR); |
| var EPTF_RBT_ItemIdx vl_rootRR := f_EPTF_RBT_getRight(vl_tree, vl_rootR); |
| var EPTF_RBT_ItemIdx vl_rootLLL := f_EPTF_RBT_getLeft(vl_tree, vl_rootLL); |
| var EPTF_RBT_ItemIdx vl_rootLLR := f_EPTF_RBT_getRight(vl_tree, vl_rootLL); |
| var EPTF_RBT_ItemIdx vl_rootLRL := f_EPTF_RBT_getLeft(vl_tree, vl_rootLR); |
| var EPTF_RBT_ItemIdx vl_rootLRR := f_EPTF_RBT_getRight(vl_tree, vl_rootLR); |
| var EPTF_RBT_ItemIdx vl_rootRLL := f_EPTF_RBT_getLeft(vl_tree, vl_rootRL); |
| var EPTF_RBT_ItemIdx vl_rootRLR := f_EPTF_RBT_getRight(vl_tree, vl_rootRL); |
| var EPTF_RBT_ItemIdx vl_rootRRL := f_EPTF_RBT_getLeft(vl_tree, vl_rootRR); |
| var EPTF_RBT_ItemIdx vl_rootRRR := f_EPTF_RBT_getRight(vl_tree, vl_rootRR); |
| |
| var verdicttype vl_verdict := pass; |
| |
| if(f_EPTF_RBT_getItemType(vl_tree, vl_root) != BlackNode or f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_root) != 10) |
| { |
| vl_verdict := fail; |
| } |
| |
| if( f_EPTF_RBT_getItemType(vl_tree, vl_rootL) == BlackNode and f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootL) == 4 ) |
| { |
| if( f_EPTF_RBT_getItemType(vl_tree, vl_rootLL) != BlackNode or f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootLL) != 3) |
| { |
| vl_verdict := fail; |
| } |
| |
| if( f_EPTF_RBT_getItemType(vl_tree, vl_rootLLL) != RedNode or f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootLLL) != 1) |
| { |
| vl_verdict := fail; |
| } |
| if( f_EPTF_RBT_getItemType(vl_tree, vl_rootLR) != RedNode or f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootLR) != 8) |
| { |
| vl_verdict := fail; |
| } |
| if( f_EPTF_RBT_getItemType(vl_tree, vl_rootLRL) != BlackNode or f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootLRL) != 7) |
| { |
| vl_verdict := fail; |
| } |
| if( f_EPTF_RBT_getItemType(vl_tree, vl_rootLRR) != BlackNode or f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootLRR) != 9) |
| { |
| vl_verdict := fail; |
| } |
| if( vl_rootLLR != -1 ) |
| { |
| vl_verdict := fail; |
| } |
| } |
| else if( f_EPTF_RBT_getItemType(vl_tree, vl_rootL) == BlackNode and f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootL) == 7 ) |
| { |
| if( f_EPTF_RBT_getItemType(vl_tree, vl_rootLL) != RedNode or f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootLL) != 3) |
| { |
| vl_verdict := fail; |
| } |
| |
| if( f_EPTF_RBT_getItemType(vl_tree, vl_rootLLL) != BlackNode or f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootLLL) != 1) |
| { |
| vl_verdict := fail; |
| } |
| if( f_EPTF_RBT_getItemType(vl_tree, vl_rootLR) != RedNode or f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootLR) != 8) |
| { |
| vl_verdict := fail; |
| } |
| if(vl_rootLRL != -1) |
| { |
| vl_verdict := fail; |
| } |
| if( f_EPTF_RBT_getItemType(vl_tree, vl_rootLRR) != BlackNode or f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootLRR) != 9) |
| { |
| vl_verdict := fail; |
| } |
| if( f_EPTF_RBT_getItemType(vl_tree, vl_rootLLR) != BlackNode or f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootLLR) != 4) |
| { |
| vl_verdict := fail; |
| } |
| } |
| else |
| { |
| vl_verdict := fail; |
| } |
| |
| if(f_EPTF_RBT_getItemType(vl_tree, vl_rootR) != BlackNode or f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootR) != 15) |
| { |
| vl_verdict := fail; |
| } |
| if(f_EPTF_RBT_getItemType(vl_tree, vl_rootRL) != RedNode or f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootRL) != 13) |
| { |
| vl_verdict := fail; |
| } |
| if(f_EPTF_RBT_getItemType(vl_tree, vl_rootRR) != RedNode or f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootRR) != 18) |
| { |
| vl_verdict := fail; |
| } |
| |
| if(f_EPTF_RBT_getItemType(vl_tree, vl_rootRLL) != BlackNode or f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootRLL) != 12) |
| { |
| vl_verdict := fail; |
| } |
| if(f_EPTF_RBT_getItemType(vl_tree, vl_rootRLR) != BlackNode or f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootRLR) != 14) |
| { |
| vl_verdict := fail; |
| } |
| if(f_EPTF_RBT_getItemType(vl_tree, vl_rootRRL) != BlackNode or f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootRRL) != 17) |
| { |
| vl_verdict := fail; |
| } |
| if(f_EPTF_RBT_getItemType(vl_tree, vl_rootRRR) != BlackNode or f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootRRR) != 19) |
| { |
| vl_verdict := fail; |
| } |
| |
| f_EPTF_Base_stop(vl_verdict); |
| } |
| |
| //Sibling is black with no red children, and its parent is black |
| |
| testcase tc_EPTF_RBT_Test_removeBlack5() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| var EPTF_RBT_TreeInitNode vl_initialTree := { |
| isRed:=false, |
| key:={intKey:=10}, |
| leftChild:={ |
| isRed:=false, |
| key:={intKey:=5}, |
| leftChild:={ |
| isRed:=false, |
| key:={intKey:=3}, |
| leftChild:=omit, |
| rightChild:=omit |
| }, |
| rightChild:={ |
| isRed:=false, |
| key:={intKey:=6}, |
| leftChild:=omit, |
| rightChild:=omit |
| } |
| }, |
| rightChild:={ |
| isRed:=false, |
| key:={intKey:=15}, |
| leftChild:={ |
| isRed:=false, |
| key:={intKey:=13}, |
| leftChild:=omit, |
| rightChild:=omit |
| }, |
| rightChild:={ |
| isRed:=false, |
| key:={intKey:=16}, |
| leftChild:=omit, |
| rightChild:=omit |
| } |
| } |
| }; |
| var integer vl_tree := f_EPTF_RBT_createAndInitTree("IntRBT", vl_initialTree); |
| f_EPTF_RBT_removeItem(vl_tree, f_EPTF_RBT_findFirstItemByIntKey(vl_tree, 3)); |
| |
| var EPTF_RBT_ItemIdx vl_root := f_EPTF_RBT_getRoot(vl_tree); |
| var EPTF_RBT_ItemIdx vl_rootL := f_EPTF_RBT_getLeft(vl_tree, vl_root); |
| var EPTF_RBT_ItemIdx vl_rootR := f_EPTF_RBT_getRight(vl_tree, vl_root); |
| var EPTF_RBT_ItemIdx vl_rootLL := f_EPTF_RBT_getLeft(vl_tree, vl_rootL); |
| var EPTF_RBT_ItemIdx vl_rootLR := f_EPTF_RBT_getRight(vl_tree, vl_rootL); |
| var EPTF_RBT_ItemIdx vl_rootRL := f_EPTF_RBT_getLeft(vl_tree, vl_rootR); |
| var EPTF_RBT_ItemIdx vl_rootRR := f_EPTF_RBT_getRight(vl_tree, vl_rootR); |
| |
| var verdicttype vl_verdict := pass; |
| |
| if(f_EPTF_RBT_getItemType(vl_tree, vl_root) != BlackNode or f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_root) != 10) |
| { |
| vl_verdict := fail; |
| } |
| if(f_EPTF_RBT_getItemType(vl_tree, vl_rootL) != BlackNode or f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootL) != 5) |
| { |
| vl_verdict := fail; |
| } |
| if(f_EPTF_RBT_getItemType(vl_tree, vl_rootR) != RedNode or f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootR) != 15) |
| { |
| vl_verdict := fail; |
| } |
| if(vl_rootLL!=-1) |
| { |
| vl_verdict := fail; |
| } |
| if(f_EPTF_RBT_getItemType(vl_tree, vl_rootLR) != RedNode or f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootLR) != 6) |
| { |
| vl_verdict := fail; |
| } |
| if(f_EPTF_RBT_getItemType(vl_tree, vl_rootRL) != BlackNode or f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootRL) != 13) |
| { |
| vl_verdict := fail; |
| } |
| if(f_EPTF_RBT_getItemType(vl_tree, vl_rootRR) != BlackNode or f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootRR) != 16) |
| { |
| vl_verdict := fail; |
| } |
| |
| f_EPTF_Base_stop(vl_verdict); |
| } |
| |
| //Node to delete is red |
| |
| testcase tc_EPTF_RBT_Test_removeRed() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| var EPTF_RBT_TreeInitNode vl_initialTree := { |
| isRed:=false, |
| key:={intKey:=10}, |
| leftChild:={ |
| isRed:=true, |
| key:={intKey:=5}, |
| leftChild:=omit, |
| rightChild:=omit |
| }, |
| rightChild:={ |
| isRed:=true, |
| key:={intKey:=15}, |
| leftChild:=omit, |
| rightChild:=omit |
| } |
| }; |
| |
| var integer vl_tree := f_EPTF_RBT_createAndInitTree("IntRBT", vl_initialTree); |
| f_EPTF_RBT_removeItem(vl_tree, f_EPTF_RBT_findFirstItemByIntKey(vl_tree, 5)); |
| |
| var verdicttype vl_verdict:=pass; |
| |
| var EPTF_RBT_ItemIdx vl_root := f_EPTF_RBT_getRoot(vl_tree); |
| var EPTF_RBT_ItemIdx vl_rootL := f_EPTF_RBT_getLeft(vl_tree, vl_root); |
| var EPTF_RBT_ItemIdx vl_rootR := f_EPTF_RBT_getRight(vl_tree, vl_root); |
| |
| if(f_EPTF_RBT_getItemType(vl_tree, vl_root) != BlackNode or f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_root) != 10) |
| { |
| vl_verdict := fail; |
| } |
| if(vl_rootL!=-1) |
| { |
| vl_verdict := fail; |
| } |
| if(f_EPTF_RBT_getItemType(vl_tree, vl_rootR) != RedNode or f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_rootR) != 15) |
| { |
| vl_verdict := fail; |
| } |
| |
| f_EPTF_Base_stop(vl_verdict); |
| } |
| |
| testcase tc_EPTF_RBT_Test_getKeyOfIntItem() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| var integer vl_tree := f_EPTF_RBT_createIntTree("IntRBT"); |
| var EPTF_RBT_ItemIdx vl_first := f_EPTF_RBT_insertIntItem(vl_tree, 3); |
| var EPTF_RBT_ItemIdx vl_second := f_EPTF_RBT_insertIntItem(vl_tree, 8); |
| var EPTF_RBT_ItemIdx vl_third := f_EPTF_RBT_insertIntItem(vl_tree, 5); |
| var integer vl_key2 := f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_second); |
| var verdicttype vl_verdict := fail; |
| if(vl_key2 == 8) |
| { |
| vl_verdict := pass; |
| } |
| f_EPTF_Base_stop(vl_verdict); |
| } |
| |
| testcase tc_EPTF_RBT_Test_Neg_getKeyOfIntItem1() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| var integer vl_tree := f_EPTF_RBT_createIntTree("IntRBT"); |
| var EPTF_RBT_ItemIdx vl_first := f_EPTF_RBT_insertIntItem(vl_tree, 3); |
| var EPTF_RBT_ItemIdx vl_second := f_EPTF_RBT_insertIntItem(vl_tree, 8); |
| var EPTF_RBT_ItemIdx vl_third := f_EPTF_RBT_insertIntItem(vl_tree, 5); |
| f_EPTF_RBT_removeItem(vl_tree, vl_second); |
| f_EPTF_Base_setExpectedAssertMsg("f_EPTF_RBT_getKeyOfIntItem: item 1 in tree \"IntRBT\" is in the free chain"); |
| var integer vl_key2 := f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_second); |
| f_EPTF_Base_stop(); |
| } |
| |
| testcase tc_EPTF_RBT_Test_Neg_getKeyOfIntItem2() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| var integer vl_tree := f_EPTF_RBT_createIntTree("IntRBT"); |
| var EPTF_RBT_ItemIdx vl_first := f_EPTF_RBT_insertIntItem(vl_tree, 3); |
| var EPTF_RBT_ItemIdx vl_second := f_EPTF_RBT_insertIntItem(vl_tree, 8); |
| var EPTF_RBT_ItemIdx vl_third := f_EPTF_RBT_insertIntItem(vl_tree, 5); |
| f_EPTF_RBT_removeItem(vl_tree, vl_second); |
| f_EPTF_Base_setExpectedAssertMsg("f_EPTF_RBT_getKeyOfIntItem: invalid tree 0, tree has been deleted."); |
| f_EPTF_RBT_deleteTree(vl_tree); |
| var integer vl_key2 := f_EPTF_RBT_getKeyOfIntItem(vl_tree, vl_second); |
| f_EPTF_Base_stop(); |
| } |
| |
| testcase tc_EPTF_RBT_Test_getKeyOfFloatItem() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| var integer vl_tree := f_EPTF_RBT_createFloatTree("FloatRBT"); |
| var EPTF_RBT_ItemIdx vl_first := f_EPTF_RBT_insertFloatItem(vl_tree, 3.0); |
| var EPTF_RBT_ItemIdx vl_second := f_EPTF_RBT_insertFloatItem(vl_tree, 8.0); |
| var EPTF_RBT_ItemIdx vl_third := f_EPTF_RBT_insertFloatItem(vl_tree, 5.0); |
| var float vl_key2 := f_EPTF_RBT_getKeyOfFloatItem(vl_tree, vl_second); |
| var verdicttype vl_verdict := fail; |
| if(vl_key2 == 8.0) |
| { |
| vl_verdict := pass; |
| } |
| f_EPTF_Base_stop(vl_verdict); |
| } |
| |
| testcase tc_EPTF_RBT_Test_Neg_getKeyOfFloatItem1() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| var integer vl_tree := f_EPTF_RBT_createFloatTree("FloatRBT"); |
| var EPTF_RBT_ItemIdx vl_first := f_EPTF_RBT_insertFloatItem(vl_tree, 3.0); |
| var EPTF_RBT_ItemIdx vl_second := f_EPTF_RBT_insertFloatItem(vl_tree, 8.0); |
| var EPTF_RBT_ItemIdx vl_third := f_EPTF_RBT_insertFloatItem(vl_tree, 5.0); |
| f_EPTF_RBT_removeItem(vl_tree, vl_second); |
| f_EPTF_Base_setExpectedAssertMsg("f_EPTF_RBT_getKeyOfFloatItem: item 1 in tree \"FloatRBT\" is in the free chain"); |
| var float vl_key2 := f_EPTF_RBT_getKeyOfFloatItem(vl_tree, vl_second); |
| f_EPTF_Base_stop(); |
| } |
| |
| testcase tc_EPTF_RBT_Test_Neg_getKeyOfFloatItem2() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| var integer vl_tree := f_EPTF_RBT_createFloatTree("FloatRBT"); |
| var EPTF_RBT_ItemIdx vl_first := f_EPTF_RBT_insertFloatItem(vl_tree, 3.0); |
| var EPTF_RBT_ItemIdx vl_second := f_EPTF_RBT_insertFloatItem(vl_tree, 8.0); |
| var EPTF_RBT_ItemIdx vl_third := f_EPTF_RBT_insertFloatItem(vl_tree, 5.0); |
| f_EPTF_RBT_removeItem(vl_tree, vl_second); |
| f_EPTF_Base_setExpectedAssertMsg("f_EPTF_RBT_getKeyOfFloatItem: invalid tree 0, tree has been deleted."); |
| f_EPTF_RBT_deleteTree(vl_tree); |
| var float vl_key2 := f_EPTF_RBT_getKeyOfFloatItem(vl_tree, vl_second); |
| f_EPTF_Base_stop(); |
| } |
| |
| testcase tc_EPTF_RBT_Test_getKeyOfCharstringItem() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| var integer vl_tree := f_EPTF_RBT_createCharstringTree("CharstringRBT"); |
| var EPTF_RBT_ItemIdx vl_first := f_EPTF_RBT_insertCharstringItem(vl_tree, "apple"); |
| var EPTF_RBT_ItemIdx vl_second := f_EPTF_RBT_insertCharstringItem(vl_tree, "bear"); |
| var EPTF_RBT_ItemIdx vl_third := f_EPTF_RBT_insertCharstringItem(vl_tree, "sugar"); |
| var charstring vl_key2 := f_EPTF_RBT_getKeyOfCharstringItem(vl_tree, vl_second); |
| var verdicttype vl_verdict := fail; |
| if(vl_key2 == "bear") |
| { |
| vl_verdict := pass; |
| } |
| f_EPTF_Base_stop(vl_verdict); |
| } |
| |
| testcase tc_EPTF_RBT_Test_Neg_getKeyOfCharstringItem1() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| var integer vl_tree := f_EPTF_RBT_createCharstringTree("CharstringRBT"); |
| var EPTF_RBT_ItemIdx vl_first := f_EPTF_RBT_insertCharstringItem(vl_tree, "apple"); |
| var EPTF_RBT_ItemIdx vl_second := f_EPTF_RBT_insertCharstringItem(vl_tree, "bear"); |
| var EPTF_RBT_ItemIdx vl_third := f_EPTF_RBT_insertCharstringItem(vl_tree, "sugar"); |
| f_EPTF_RBT_removeItem(vl_tree, vl_second); |
| f_EPTF_Base_setExpectedAssertMsg("f_EPTF_RBT_getKeyOfCharstringItem: item 1 in tree \"CharstringRBT\" is in the free chain"); |
| var charstring vl_key2 := f_EPTF_RBT_getKeyOfCharstringItem(vl_tree, vl_second); |
| f_EPTF_Base_stop(); |
| } |
| |
| testcase tc_EPTF_RBT_Test_Neg_getKeyOfCharstringItem2() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| var integer vl_tree := f_EPTF_RBT_createCharstringTree("CharstringRBT"); |
| var EPTF_RBT_ItemIdx vl_first := f_EPTF_RBT_insertCharstringItem(vl_tree, "apple"); |
| var EPTF_RBT_ItemIdx vl_second := f_EPTF_RBT_insertCharstringItem(vl_tree, "bear"); |
| var EPTF_RBT_ItemIdx vl_third := f_EPTF_RBT_insertCharstringItem(vl_tree, "sugar"); |
| f_EPTF_RBT_removeItem(vl_tree, vl_second); |
| f_EPTF_Base_setExpectedAssertMsg("f_EPTF_RBT_getKeyOfCharstringItem: invalid tree 0, tree has been deleted."); |
| f_EPTF_RBT_deleteTree(vl_tree); |
| var charstring vl_key2 := f_EPTF_RBT_getKeyOfCharstringItem(vl_tree, vl_second); |
| f_EPTF_Base_stop(); |
| } |
| |
| testcase tc_EPTF_RBT_Test_findFirstItemByIntKey() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| var integer vl_tree := f_EPTF_RBT_createIntTree("IntRBT"); |
| var EPTF_RBT_ItemIdx vl_first := f_EPTF_RBT_insertIntItem(vl_tree, 3); |
| var EPTF_RBT_ItemIdx vl_second := f_EPTF_RBT_insertIntItem(vl_tree, 8); |
| var EPTF_RBT_ItemIdx vl_third := f_EPTF_RBT_insertIntItem(vl_tree, 5); |
| var EPTF_RBT_ItemIdx vl_fourth := f_EPTF_RBT_insertIntItem(vl_tree, 8); |
| var EPTF_RBT_ItemIdx vl_item1 := f_EPTF_RBT_findFirstItemByIntKey(vl_tree, 8); |
| var EPTF_RBT_ItemIdx vl_item2 := f_EPTF_RBT_findFirstItemByIntKey(vl_tree, 6); |
| var verdicttype vl_verdict := fail; |
| if(vl_item1 == vl_second) |
| { |
| vl_verdict := pass; |
| } |
| if(vl_item2 != -1) |
| { |
| vl_verdict := fail; |
| log("f_EPTF_RBT_findFirstItemByIntKey returned item for a non-existing key."); |
| } |
| f_EPTF_Base_stop(vl_verdict); |
| } |
| |
| testcase tc_EPTF_RBT_Test_Neg_findFirstItemByIntKey() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| f_EPTF_Base_setExpectedAssertMsg("f_EPTF_RBT_findFirstItemByIntKey: invalid tree 0, number of trees: 0"); |
| var EPTF_RBT_ItemIdx vl_item1 := f_EPTF_RBT_findFirstItemByIntKey(0, 8); |
| f_EPTF_Base_stop(); |
| } |
| |
| testcase tc_EPTF_RBT_Test_findFirstItemByFloatKey() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| var integer vl_tree := f_EPTF_RBT_createFloatTree("FloatRBT"); |
| var EPTF_RBT_ItemIdx vl_first := f_EPTF_RBT_insertFloatItem(vl_tree, 3.0); |
| var EPTF_RBT_ItemIdx vl_second := f_EPTF_RBT_insertFloatItem(vl_tree, 8.0); |
| var EPTF_RBT_ItemIdx vl_third := f_EPTF_RBT_insertFloatItem(vl_tree, 5.0); |
| var EPTF_RBT_ItemIdx vl_fourth := f_EPTF_RBT_insertFloatItem(vl_tree, 8.0); |
| var EPTF_RBT_ItemIdx vl_item1 := f_EPTF_RBT_findFirstItemByFloatKey(vl_tree, 8.0); |
| var EPTF_RBT_ItemIdx vl_item2 := f_EPTF_RBT_findFirstItemByFloatKey(vl_tree, 6.0); |
| var verdicttype vl_verdict := fail; |
| if(vl_item1 == vl_second) |
| { |
| vl_verdict := pass; |
| } |
| if(vl_item2 != -1) |
| { |
| vl_verdict := fail; |
| log("f_EPTF_RBT_findFirstItemByFloatKey returned item for a non-existing key."); |
| } |
| f_EPTF_Base_stop(vl_verdict); |
| } |
| |
| testcase tc_EPTF_RBT_Test_Neg_findFirstItemByFloatKey() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| f_EPTF_Base_setExpectedAssertMsg("f_EPTF_RBT_findFirstItemByFloatKey: invalid tree 0, number of trees: 0"); |
| var EPTF_RBT_ItemIdx vl_item1 := f_EPTF_RBT_findFirstItemByFloatKey(0, 8.0); |
| f_EPTF_Base_stop(); |
| } |
| |
| testcase tc_EPTF_RBT_Test_findFirstItemByCharstringKey() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| var integer vl_tree := f_EPTF_RBT_createCharstringTree("CharstringRBT"); |
| var EPTF_RBT_ItemIdx vl_first := f_EPTF_RBT_insertCharstringItem(vl_tree, "apple"); |
| var EPTF_RBT_ItemIdx vl_second := f_EPTF_RBT_insertCharstringItem(vl_tree, "bear"); |
| var EPTF_RBT_ItemIdx vl_third := f_EPTF_RBT_insertCharstringItem(vl_tree, "sugar"); |
| var EPTF_RBT_ItemIdx vl_fourth := f_EPTF_RBT_insertCharstringItem(vl_tree, "bear"); |
| var EPTF_RBT_ItemIdx vl_item1 := f_EPTF_RBT_findFirstItemByCharstringKey(vl_tree, "bear"); |
| var EPTF_RBT_ItemIdx vl_item2 := f_EPTF_RBT_findFirstItemByCharstringKey(vl_tree, "calmar"); |
| var verdicttype vl_verdict := pass; |
| if(vl_item1 != vl_second) |
| { |
| vl_verdict := fail; |
| } |
| if(vl_item2 != -1) |
| { |
| vl_verdict := fail; |
| log("f_EPTF_RBT_findFirstItemByCharstringKey returned item for a non-existing key."); |
| } |
| f_EPTF_Base_stop(vl_verdict); |
| } |
| |
| testcase tc_EPTF_RBT_Test_Neg_findFirstItemByCharstringKey() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| f_EPTF_Base_setExpectedAssertMsg("f_EPTF_RBT_findFirstItemByCharstringKey: invalid tree 0, number of trees: 0"); |
| var EPTF_RBT_ItemIdx vl_item1 := f_EPTF_RBT_findFirstItemByCharstringKey(0, "bear"); |
| f_EPTF_Base_stop(); |
| } |
| |
| testcase tc_EPTF_RBT_Test_getRootLeftRightParent() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| var integer vl_tree1 := f_EPTF_RBT_createIntTree("IntRBT"); |
| var integer vl_tree2 := f_EPTF_RBT_createFloatTree("FloatRBT"); |
| var integer vl_tree3 := f_EPTF_RBT_createCharstringTree("CharstringRBT"); |
| var EPTF_RBT_ItemIdx vl_firstInt := f_EPTF_RBT_insertIntItem(vl_tree1, 3); |
| var EPTF_RBT_ItemIdx vl_secondInt := f_EPTF_RBT_insertIntItem(vl_tree1, 8); |
| var EPTF_RBT_ItemIdx vl_thirdInt := f_EPTF_RBT_insertIntItem(vl_tree1, 5); |
| var EPTF_RBT_ItemIdx vl_firstFloat := f_EPTF_RBT_insertFloatItem(vl_tree2, 3.0); |
| var EPTF_RBT_ItemIdx vl_secondFloat := f_EPTF_RBT_insertFloatItem(vl_tree2, 8.0); |
| var EPTF_RBT_ItemIdx vl_thirdFloat := f_EPTF_RBT_insertFloatItem(vl_tree2, 5.0); |
| var EPTF_RBT_ItemIdx vl_firstCharstring := f_EPTF_RBT_insertCharstringItem(vl_tree3, "apple"); |
| var EPTF_RBT_ItemIdx vl_secondCharstring := f_EPTF_RBT_insertCharstringItem(vl_tree3, "bear"); |
| var EPTF_RBT_ItemIdx vl_thirdCharstring := f_EPTF_RBT_insertCharstringItem(vl_tree3, "sugar"); |
| var EPTF_RBT_ItemIdx vl_rootInt := f_EPTF_RBT_getRoot(vl_tree1); |
| var EPTF_RBT_ItemIdx vl_rootFloat := f_EPTF_RBT_getRoot(vl_tree2); |
| var EPTF_RBT_ItemIdx vl_rootCharstring := f_EPTF_RBT_getRoot(vl_tree3); |
| var verdicttype vl_verdict := pass; |
| if(vl_rootInt != vl_thirdInt) |
| { |
| vl_verdict := fail; |
| log("f_EPTF_RBT_getRoot returned wrong root for integer tree."); |
| } |
| |
| if(vl_rootFloat != vl_thirdFloat) |
| { |
| vl_verdict := fail; |
| log("f_EPTF_RBT_getRoot returned wrong root for float tree."); |
| } |
| |
| if(vl_rootCharstring != vl_secondCharstring) |
| { |
| vl_verdict := fail; |
| log("f_EPTF_RBT_getRoot returned wrong root for charstring tree."); |
| } |
| |
| var EPTF_RBT_ItemIdx vl_leftOfRootInt := f_EPTF_RBT_getLeft(vl_tree1, vl_rootInt); |
| var EPTF_RBT_ItemIdx vl_leftOfRootFloat := f_EPTF_RBT_getLeft(vl_tree2, vl_rootFloat); |
| var EPTF_RBT_ItemIdx vl_leftOfRootCharstring := f_EPTF_RBT_getLeft(vl_tree3, vl_rootCharstring); |
| |
| if(vl_leftOfRootInt != vl_firstInt) |
| { |
| vl_verdict := fail; |
| log("f_EPTF_RBT_getLeft returned wrong item for integer tree."); |
| } |
| |
| if(vl_leftOfRootFloat != vl_firstFloat) |
| { |
| vl_verdict := fail; |
| log("f_EPTF_RBT_getLeft returned wrong item for float tree."); |
| } |
| |
| if(vl_leftOfRootCharstring != vl_firstCharstring) |
| { |
| vl_verdict := fail; |
| log("f_EPTF_RBT_getLeft returned wrong item for charstring tree."); |
| } |
| |
| var EPTF_RBT_ItemIdx vl_rightOfRootInt := f_EPTF_RBT_getRight(vl_tree1, vl_rootInt); |
| var EPTF_RBT_ItemIdx vl_rightOfRootFloat := f_EPTF_RBT_getRight(vl_tree2, vl_rootFloat); |
| var EPTF_RBT_ItemIdx vl_rightOfRootCharstring := f_EPTF_RBT_getRight(vl_tree3, vl_rootCharstring); |
| |
| if(vl_rightOfRootInt != vl_secondInt) |
| { |
| vl_verdict := fail; |
| log("f_EPTF_RBT_getRight returned wrong item for integer tree."); |
| } |
| |
| if(vl_rightOfRootFloat != vl_secondFloat) |
| { |
| vl_verdict := fail; |
| log("f_EPTF_RBT_getRight returned wrong item for float tree."); |
| } |
| |
| if(vl_rightOfRootCharstring != vl_thirdCharstring) |
| { |
| vl_verdict := fail; |
| log("f_EPTF_RBT_getRight returned wrong item for charstring tree."); |
| } |
| |
| var EPTF_RBT_ItemIdx vl_parentOfRootInt := f_EPTF_RBT_getParent(vl_tree1, vl_rootInt); |
| var EPTF_RBT_ItemIdx vl_parentOfRootFloat := f_EPTF_RBT_getParent(vl_tree2, vl_rootFloat); |
| var EPTF_RBT_ItemIdx vl_parentOfRootCharstring := f_EPTF_RBT_getParent(vl_tree3, vl_rootCharstring); |
| |
| if(vl_parentOfRootInt != -1) |
| { |
| vl_verdict := fail; |
| log("f_EPTF_RBT_getParent returned wrong item for integer tree."); |
| } |
| |
| if(vl_parentOfRootFloat != -1) |
| { |
| vl_verdict := fail; |
| log("f_EPTF_RBT_getParent returned wrong item for float tree."); |
| } |
| |
| if(vl_parentOfRootCharstring != -1) |
| { |
| vl_verdict := fail; |
| log("f_EPTF_RBT_getParent returned wrong item for charstring tree."); |
| } |
| |
| var EPTF_RBT_ItemIdx vl_parentOfInt := f_EPTF_RBT_getParent(vl_tree1, vl_rightOfRootInt); |
| var EPTF_RBT_ItemIdx vl_parentOfFloat := f_EPTF_RBT_getParent(vl_tree2, vl_rightOfRootFloat); |
| var EPTF_RBT_ItemIdx vl_parentOfCharstring := f_EPTF_RBT_getParent(vl_tree3, vl_rightOfRootCharstring); |
| |
| if(vl_parentOfInt != vl_rootInt) |
| { |
| vl_verdict := fail; |
| } |
| |
| if(vl_parentOfFloat != vl_rootFloat) |
| { |
| vl_verdict := fail; |
| } |
| |
| if(vl_parentOfCharstring != vl_rootCharstring) |
| { |
| vl_verdict := fail; |
| } |
| |
| f_EPTF_Base_stop(vl_verdict); |
| } |
| |
| testcase tc_EPTF_RBT_Test_getNextInChain() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| var integer vl_tree1 := f_EPTF_RBT_createIntTree("IntRBT"); |
| var EPTF_RBT_ItemIdx vl_firstInt := f_EPTF_RBT_insertIntItem(vl_tree1, 3); |
| var EPTF_RBT_ItemIdx vl_secondInt := f_EPTF_RBT_insertIntItem(vl_tree1, 8); |
| var EPTF_RBT_ItemIdx vl_thirdInt := f_EPTF_RBT_insertIntItem(vl_tree1, 5); |
| var EPTF_RBT_ItemIdx vl_fourthInt := f_EPTF_RBT_insertIntItem(vl_tree1, 8); |
| var EPTF_RBT_ItemIdx vl_fifthInt := f_EPTF_RBT_insertIntItem(vl_tree1, 8); |
| |
| var EPTF_RBT_ItemIdx vl_nextInt2nd := f_EPTF_RBT_getNextInChain(vl_tree1, vl_secondInt); |
| var EPTF_RBT_ItemIdx vl_nextInt4th := f_EPTF_RBT_getNextInChain(vl_tree1, vl_nextInt2nd); |
| var EPTF_RBT_ItemIdx vl_nextInt5th := f_EPTF_RBT_getNextInChain(vl_tree1, vl_nextInt4th); |
| |
| var verdicttype vl_verdict := pass; |
| if(vl_nextInt2nd != vl_fourthInt) |
| { |
| log("Next item of item: "&log2str(vl_secondInt)&"is: "&log2str(vl_nextInt2nd)&"instead of: "&log2str(vl_fourthInt)); |
| vl_verdict := fail; |
| } |
| if(vl_nextInt4th != vl_fifthInt) |
| { |
| log("Next item of item: "&log2str(vl_fourthInt)&"is: "&log2str(vl_nextInt4th)&"instead of: "&log2str(vl_fifthInt)); |
| vl_verdict := fail; |
| } |
| if(vl_nextInt5th != -1) |
| { |
| log("Next item of item: "&log2str(vl_fifthInt)&"is: "&log2str(vl_nextInt5th)&"instead of: "&log2str(-1)); |
| vl_verdict := fail; |
| } |
| f_EPTF_Base_stop(vl_verdict); |
| } |
| |
| testcase tc_EPTF_RBT_Test_Neg_getNextInChain1() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| var integer vl_tree1 := f_EPTF_RBT_createIntTree("IntRBT"); |
| f_EPTF_Base_setExpectedAssertMsg("f_EPTF_RBT_getNextInChain: invalid item 0, number of items in tree \"IntRBT\": 0"); |
| var EPTF_RBT_ItemIdx vl_item := f_EPTF_RBT_getNextInChain(vl_tree1, 0); |
| f_EPTF_Base_stop(); |
| } |
| |
| testcase tc_EPTF_RBT_Test_Neg_getNextInChain2() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| f_EPTF_Base_setExpectedAssertMsg("f_EPTF_RBT_getNextInChain: invalid tree 1, number of trees: 0"); |
| var EPTF_RBT_ItemIdx vl_item := f_EPTF_RBT_getNextInChain(1, 7); |
| f_EPTF_Base_stop(); |
| } |
| |
| testcase tc_EPTF_RBT_Test_getPrevInChain() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| var integer vl_tree1 := f_EPTF_RBT_createIntTree("IntRBT"); |
| var EPTF_RBT_ItemIdx vl_firstInt := f_EPTF_RBT_insertIntItem(vl_tree1, 3); |
| var EPTF_RBT_ItemIdx vl_secondInt := f_EPTF_RBT_insertIntItem(vl_tree1, 8); |
| var EPTF_RBT_ItemIdx vl_thirdInt := f_EPTF_RBT_insertIntItem(vl_tree1, 5); |
| var EPTF_RBT_ItemIdx vl_fourthInt := f_EPTF_RBT_insertIntItem(vl_tree1, 8); |
| var EPTF_RBT_ItemIdx vl_fifthInt := f_EPTF_RBT_insertIntItem(vl_tree1, 8); |
| |
| var EPTF_RBT_ItemIdx vl_prevInt5th := f_EPTF_RBT_getPrevInChain(vl_tree1, vl_fifthInt); |
| var EPTF_RBT_ItemIdx vl_prevInt4th := f_EPTF_RBT_getPrevInChain(vl_tree1, vl_prevInt5th); |
| var EPTF_RBT_ItemIdx vl_prevInt2nd := f_EPTF_RBT_getPrevInChain(vl_tree1, vl_prevInt4th); |
| |
| var verdicttype vl_verdict := pass; |
| if(vl_prevInt5th != vl_fourthInt) |
| { |
| log("Previous item of item: "&log2str(vl_fifthInt)&"is: "&log2str(vl_prevInt5th)&"instead of: "&log2str(vl_fourthInt)); |
| vl_verdict := fail; |
| } |
| if(vl_prevInt4th != vl_secondInt) |
| { |
| log("Previous item of item: "&log2str(vl_fourthInt)&"is: "&log2str(vl_prevInt4th)&"instead of: "&log2str(vl_secondInt)); |
| vl_verdict := fail; |
| } |
| if(vl_prevInt2nd != -1) |
| { |
| log("Previous item of item: "&log2str(vl_secondInt)&"is: "&log2str(vl_prevInt2nd)&"instead of: "&log2str(-1)); |
| vl_verdict := fail; |
| } |
| f_EPTF_Base_stop(vl_verdict); |
| } |
| |
| testcase tc_EPTF_RBT_Test_Neg_getPrevInChain1() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| var integer vl_tree1 := f_EPTF_RBT_createIntTree("IntRBT"); |
| f_EPTF_Base_setExpectedAssertMsg("f_EPTF_RBT_getPrevInChain: invalid item 0, number of items in tree \"IntRBT\": 0"); |
| var EPTF_RBT_ItemIdx vl_item := f_EPTF_RBT_getPrevInChain(vl_tree1, 0); |
| f_EPTF_Base_stop(); |
| } |
| |
| testcase tc_EPTF_RBT_Test_Neg_getPrevInChain2() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| f_EPTF_Base_setExpectedAssertMsg("f_EPTF_RBT_getPrevInChain: invalid tree 1, number of trees: 0"); |
| var EPTF_RBT_ItemIdx vl_item := f_EPTF_RBT_getPrevInChain(1, 7); |
| f_EPTF_Base_stop(); |
| } |
| |
| testcase tc_EPTF_RBT_Test_iterateIncremental() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| var integer vl_tree1 := f_EPTF_RBT_createIntTree("IntRBT"); |
| var EPTF_RBT_ItemIdx vl_firstInt := f_EPTF_RBT_insertIntItem(vl_tree1, 3); |
| var EPTF_RBT_ItemIdx vl_secondInt := f_EPTF_RBT_insertIntItem(vl_tree1, 1); |
| var EPTF_RBT_ItemIdx vl_thirdInt := f_EPTF_RBT_insertIntItem(vl_tree1, 5); |
| var EPTF_RBT_ItemIdx vl_fourthInt := f_EPTF_RBT_insertIntItem(vl_tree1, 1); |
| var EPTF_RBT_ItemIdx vl_fifthInt := f_EPTF_RBT_insertIntItem(vl_tree1, 1); |
| |
| var EPTF_RBT_ItemIdx vl_iter1 := f_EPTF_RBT_iterateIncremental(vl_tree1, vl_secondInt); |
| var EPTF_RBT_ItemIdx vl_iter2 := f_EPTF_RBT_iterateIncremental(vl_tree1, vl_iter1); |
| var EPTF_RBT_ItemIdx vl_iter3 := f_EPTF_RBT_iterateIncremental(vl_tree1, vl_iter2); |
| var EPTF_RBT_ItemIdx vl_iter4 := f_EPTF_RBT_iterateIncremental(vl_tree1, vl_iter3); |
| var EPTF_RBT_ItemIdx vl_iter5 := f_EPTF_RBT_iterateIncremental(vl_tree1, vl_iter4); |
| |
| var verdicttype vl_verdict := pass; |
| |
| if(vl_iter1 != vl_fourthInt) |
| { |
| log("f_EPTF_RBT_iterateIncremental returned: "&log2str(vl_iter1)&" as next item of item: "&log2str(vl_secondInt)&" istead of: "&log2str(vl_fourthInt)); |
| vl_verdict := fail; |
| } |
| if(vl_iter2 != vl_fifthInt) |
| { |
| log("f_EPTF_RBT_iterateIncremental returned: "&log2str(vl_iter2)&" as next item of item: "&log2str(vl_iter1)&" istead of: "&log2str(vl_fifthInt)); |
| vl_verdict := fail; |
| } |
| if(vl_iter3 != vl_firstInt) |
| { |
| log("f_EPTF_RBT_iterateIncremental returned: "&log2str(vl_iter3)&" as next item of item: "&log2str(vl_iter2)&" istead of: "&log2str(vl_firstInt)); |
| vl_verdict := fail; |
| } |
| if(vl_iter4 != vl_thirdInt) |
| { |
| log("f_EPTF_RBT_iterateIncremental returned: "&log2str(vl_iter4)&" as next item of item: "&log2str(vl_iter3)&" istead of: "&log2str(vl_thirdInt)); |
| vl_verdict := fail; |
| } |
| if(vl_iter5 != -1) |
| { |
| log("f_EPTF_RBT_iterateIncremental returned: "&log2str(vl_iter5)&" as next item of item: "&log2str(vl_iter4)&" istead of: "&log2str(-1)); |
| vl_verdict := fail; |
| } |
| f_EPTF_Base_stop(vl_verdict); |
| } |
| |
| testcase tc_EPTF_RBT_Test_Neg_iterateIncremental1() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| var integer vl_tree1 := f_EPTF_RBT_createIntTree("IntRBT"); |
| f_EPTF_Base_setExpectedAssertMsg("f_EPTF_RBT_iterateIncremental: invalid item 8, number of items in tree \"IntRBT\": 0"); |
| var EPTF_RBT_ItemIdx vl_iter5 := f_EPTF_RBT_iterateIncremental(vl_tree1, 8); |
| f_EPTF_Base_stop(); |
| } |
| |
| testcase tc_EPTF_RBT_Test_Neg_iterateIncremental2() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| f_EPTF_Base_setExpectedAssertMsg("f_EPTF_RBT_iterateIncremental: invalid tree 2, number of trees: 0"); |
| var EPTF_RBT_ItemIdx vl_iter5 := f_EPTF_RBT_iterateIncremental(2, 8); |
| f_EPTF_Base_stop(); |
| } |
| |
| testcase tc_EPTF_RBT_Test_sortIncrementalInt() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| f_EPTF_RBT_init_CT(%definitionId); |
| var integer vl_tree1 := f_EPTF_RBT_createIntTree("IntRBT"); |
| var EPTF_RBT_ItemIdx vl_firstInt := f_EPTF_RBT_insertIntItem(vl_tree1, 3); |
| var EPTF_RBT_ItemIdx vl_secondInt := f_EPTF_RBT_insertIntItem(vl_tree1, 1); |
| var EPTF_RBT_ItemIdx vl_thirdInt := f_EPTF_RBT_insertIntItem(vl_tree1, 5); |
| var EPTF_RBT_ItemIdx vl_fourthInt := f_EPTF_RBT_insertIntItem(vl_tree1, 45); |
| var EPTF_RBT_ItemIdx vl_fifthInt := f_EPTF_RBT_insertIntItem(vl_tree1, 2); |
| var EPTF_RBT_ItemIdx vl_sixthInt := f_EPTF_RBT_insertIntItem(vl_tree1, 8); |
| |
| var verdicttype vl_verdict := pass; |
| |
| var EPTF_RBT_ItemIdxList vl_itemsIncremental; |
| var EPTF_RBT_ItemIdxList vl_expected := {vl_secondInt, vl_fifthInt, vl_firstInt, vl_thirdInt, vl_sixthInt, vl_fourthInt}; |
| |
| f_EPTF_RBT_sortIncremental(vl_tree1, vl_itemsIncremental); |
| if(vl_itemsIncremental != vl_expected) |
| { |
| vl_verdict := fail; |
| log("f_EPTF_RBT_sortIncremental returned bad sequence of items: "&log2str(vl_itemsIncremental)&" instead of: "&log2str(vl_expected)); |
| } |
| f_EPTF_Base_stop(vl_verdict); |
| } |
| |
| testcase tc_EPTF_RBT_Test_sortIncrementalFloat() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| f_EPTF_RBT_init_CT(%definitionId); |
| var integer vl_tree1 := f_EPTF_RBT_createFloatTree("FloatRBT"); |
| var EPTF_RBT_ItemIdx vl_firstFloat := f_EPTF_RBT_insertFloatItem(vl_tree1, 3.0); |
| var EPTF_RBT_ItemIdx vl_secondFloat := f_EPTF_RBT_insertFloatItem(vl_tree1, 1.0); |
| var EPTF_RBT_ItemIdx vl_thirdFloat := f_EPTF_RBT_insertFloatItem(vl_tree1, 5.0); |
| var EPTF_RBT_ItemIdx vl_fourthFloat := f_EPTF_RBT_insertFloatItem(vl_tree1, 45.0); |
| var EPTF_RBT_ItemIdx vl_fifthFloat := f_EPTF_RBT_insertFloatItem(vl_tree1, 2.0); |
| var EPTF_RBT_ItemIdx vl_sixthFloat := f_EPTF_RBT_insertFloatItem(vl_tree1, 8.0); |
| |
| var verdicttype vl_verdict := pass; |
| |
| var EPTF_RBT_ItemIdxList vl_itemsIncremental; |
| var EPTF_RBT_ItemIdxList vl_expected := {vl_secondFloat, vl_fifthFloat, vl_firstFloat, vl_thirdFloat, vl_sixthFloat, vl_fourthFloat}; |
| |
| f_EPTF_RBT_sortIncremental(vl_tree1, vl_itemsIncremental); |
| if(vl_itemsIncremental != vl_expected) |
| { |
| vl_verdict := fail; |
| log("f_EPTF_RBT_sortIncremental returned bad sequence of items: "&log2str(vl_itemsIncremental)&" instead of: "&log2str(vl_expected)); |
| } |
| f_EPTF_Base_stop(vl_verdict); |
| } |
| |
| testcase tc_EPTF_RBT_Test_sortIncrementalCharstring() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| f_EPTF_RBT_init_CT(%definitionId); |
| var integer vl_tree1 := f_EPTF_RBT_createCharstringTree("CharstringRBT"); |
| var EPTF_RBT_ItemIdx vl_firstCharstring := f_EPTF_RBT_insertCharstringItem(vl_tree1, "beard"); |
| var EPTF_RBT_ItemIdx vl_secondCharstring := f_EPTF_RBT_insertCharstringItem(vl_tree1, "apple"); |
| var EPTF_RBT_ItemIdx vl_thirdCharstring := f_EPTF_RBT_insertCharstringItem(vl_tree1, "bearded"); |
| var EPTF_RBT_ItemIdx vl_fourthCharstring := f_EPTF_RBT_insertCharstringItem(vl_tree1, "zero"); |
| var EPTF_RBT_ItemIdx vl_fifthCharstring := f_EPTF_RBT_insertCharstringItem(vl_tree1, "bear"); |
| var EPTF_RBT_ItemIdx vl_sixthCharstring := f_EPTF_RBT_insertCharstringItem(vl_tree1, "yellow"); |
| |
| var verdicttype vl_verdict := pass; |
| |
| var EPTF_RBT_ItemIdxList vl_itemsIncremental; |
| var EPTF_RBT_ItemIdxList vl_expected := {vl_secondCharstring, vl_fifthCharstring, vl_firstCharstring, vl_thirdCharstring, vl_sixthCharstring, vl_fourthCharstring}; |
| |
| f_EPTF_RBT_sortIncremental(vl_tree1, vl_itemsIncremental); |
| if(vl_itemsIncremental != vl_expected) |
| { |
| vl_verdict := fail; |
| log("f_EPTF_RBT_sortIncremental returned bad sequence of items: "&log2str(vl_itemsIncremental)&" instead of: "&log2str(vl_expected)); |
| } |
| f_EPTF_Base_stop(vl_verdict); |
| } |
| |
| function f_EPTF_RBT_Test_removeRoot(in InsertOrder pl_order, in charstring pl_pngPrefix) runs on EPTF_RBT_CT |
| { |
| var integer vl_tree, vl_smallest; |
| f_insert(vl_tree, vl_smallest, pl_order, pl_pngPrefix); |
| // // note: tree has 100 items, with index 0..99 |
| var integer vl_root := f_EPTF_RBT_getRoot(vl_tree); |
| action("vl_root: ", vl_root); |
| if(tsp_pngFinal) { |
| f_EPTF_RBT_dumpToPng(vl_tree, pl_pngPrefix&"preRemove"); |
| } |
| f_EPTF_RBT_removeItem(vl_tree, vl_root); |
| vl_root := f_EPTF_RBT_getRoot(vl_tree); |
| action("new vl_root: ", vl_root); |
| if(not f_EPTF_RBT_isTreeValid(vl_tree)) { |
| setverdict(fail, "invalid tree after removal"); |
| f_EPTF_RBT_dumpToPng(vl_tree, pl_pngPrefix&"invalid"); |
| f_EPTF_Base_stop(none); |
| } |
| if(tsp_pngFinal) { |
| f_EPTF_RBT_dumpToPng(vl_tree, pl_pngPrefix&"postRemove"); |
| } |
| f_EPTF_Base_stop(pass); |
| } |
| |
| testcase tc_EPTF_RBT_Test_removeRootAsc() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_Test_removeRoot(ascending, "tree_removeRootAsc_"); |
| } |
| |
| testcase tc_EPTF_RBT_Test_removeRootDesc() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_Test_removeRoot(descending, "tree_removeRootDesc_"); |
| } |
| |
| testcase tc_EPTF_RBT_Test_removeRootRnd() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_Test_removeRoot(random, "tree_removeRootRnd_"); |
| } |
| |
| function f_int2str_3digit(in integer i) |
| return charstring |
| { |
| if(i<0) { return int2str(i); } |
| else if(i>99) { return int2str(i); } |
| else if(i>9) { return "0"&int2str(i); } |
| return "00"&int2str(i); |
| } |
| |
| function f_EPTF_RBT_Test_removeAllFromRoot(in InsertOrder pl_order, in charstring pl_pngPrefix) runs on EPTF_RBT_CT |
| { |
| var integer vl_tree, vl_smallest; |
| f_insert(vl_tree, vl_smallest, pl_order, pl_pngPrefix); |
| var integer vl_step := 0; |
| if(tsp_pngEachStep_remove) { |
| f_EPTF_RBT_dumpToPng(vl_tree, pl_pngPrefix&f_int2str_3digit(vl_step)); |
| } |
| while(true) { |
| var integer vl_root := f_EPTF_RBT_getRoot(vl_tree); |
| action("vl_root: ", vl_root); |
| f_EPTF_RBT_removeItem(vl_tree, vl_root); |
| vl_root := f_EPTF_RBT_getRoot(vl_tree); |
| action("new vl_root: ", vl_root); |
| if(not f_EPTF_RBT_isTreeValid(vl_tree)) { |
| setverdict(fail, "invalid tree after removal (step "&int2str(vl_step)&")"); |
| f_EPTF_RBT_dumpToPng(vl_tree, pl_pngPrefix&"invalid"); |
| f_EPTF_Base_stop(none); |
| } |
| vl_step := vl_step + 1; |
| if(tsp_pngEachStep_remove) { |
| f_EPTF_RBT_dumpToPng(vl_tree, pl_pngPrefix&f_int2str_3digit(vl_step)); |
| } |
| if(vl_root < 0) { break; } |
| } |
| f_EPTF_Base_stop(pass); |
| } |
| |
| testcase tc_EPTF_RBT_Test_removeAllFromRootAsc() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_Test_removeAllFromRoot(ascending, "tree_removeAllFromRootAsc_"); |
| } |
| |
| testcase tc_EPTF_RBT_Test_removeAllFromRootDesc() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_Test_removeAllFromRoot(descending, "tree_removeAllFromRootDesc_"); |
| } |
| |
| testcase tc_EPTF_RBT_Test_removeAllFromRootRnd() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_Test_removeAllFromRoot(random, "tree_removeAllFromRootRnd_"); |
| } |
| |
| function f_EPTF_RBT_Test_removeAllFromSmallest(in InsertOrder pl_order, in charstring pl_pngPrefix) runs on EPTF_RBT_CT |
| { |
| var integer vl_tree, vl_smallest; |
| f_insert(vl_tree, vl_smallest, pl_order, pl_pngPrefix); |
| var integer vl_step := 0; |
| if(tsp_pngEachStep_remove) { |
| f_EPTF_RBT_dumpToPng(vl_tree, pl_pngPrefix&f_int2str_3digit(vl_step)); |
| } |
| while(true) { |
| vl_smallest := f_EPTF_RBT_getItemWithSmallestKey(vl_tree); |
| if(vl_smallest >= 0) { |
| action("vl_smallest: ", vl_smallest, ", key: ", f_EPTF_RBT_getKeyOfFloatItem(vl_tree, vl_smallest)); |
| } else { |
| action("vl_smallest: ", vl_smallest); |
| } |
| if(vl_smallest < 0) { break; } |
| f_EPTF_RBT_removeItem(vl_tree, vl_smallest); |
| if(not f_EPTF_RBT_isTreeValid(vl_tree)) { |
| setverdict(fail, "invalid tree after removal (step "&int2str(vl_step)&")"); |
| f_EPTF_RBT_dumpToPng(vl_tree, pl_pngPrefix&"invalid"); |
| f_EPTF_Base_stop(none); |
| } |
| vl_step := vl_step + 1; |
| if(tsp_pngEachStep_remove) { |
| f_EPTF_RBT_dumpToPng(vl_tree, pl_pngPrefix&f_int2str_3digit(vl_step)); |
| } |
| } |
| f_EPTF_Base_stop(pass); |
| } |
| |
| testcase tc_EPTF_RBT_Test_removeAllFromSmallestAsc() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_Test_removeAllFromSmallest(ascending, "tree_removeAllFromSmallestAsc_"); |
| } |
| |
| testcase tc_EPTF_RBT_Test_removeAllFromSmallestDesc() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_Test_removeAllFromSmallest(descending, "tree_removeAllFromSmallestDesc_"); |
| } |
| |
| testcase tc_EPTF_RBT_Test_removeAllFromSmallestRnd() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_Test_removeAllFromSmallest(random, "tree_removeAllFromSmallestRnd_"); |
| } |
| |
| modulepar float tsp_stressTestInterval := 30.0; |
| modulepar integer tsp_stressTestPrefill := 10000; |
| |
| function f_EPTF_RBT_Test_stressTest(in boolean pl_validateTree) runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT("mtc"); |
| var EPTF_RBT_TreeId vl_dummy := f_EPTF_RBT_createIntTree(); |
| var EPTF_RBT_TreeId vl_tree := f_EPTF_RBT_createFloatTree(); |
| var EPTF_RBT_TreeId vl_clone := f_EPTF_RBT_createFloatTree(); |
| |
| if(tsp_stressTestPrefill > 0) { |
| action("Perfroming pre-fill of tree with ", tsp_stressTestPrefill, " elements..."); |
| } |
| for(var integer i:=0; i<tsp_stressTestPrefill; i:=i+1) { |
| var float vl_key := int2float(float2int(rnd()*1000000.0))/1000000.0; |
| f_EPTF_RBT_insertFloatItem(vl_tree, vl_key); |
| } |
| if(tsp_stressTestPrefill > 0) { |
| action("Pre-fill of tree finished."); |
| } |
| |
| timer t_dummy := 0.0; |
| timer t_run := tsp_stressTestInterval; |
| t_dummy.start; |
| t_run.start; |
| var integer vl_step := 0; |
| var integer vl_inserts := 0; |
| var integer vl_rootRemoves := 0; |
| var integer vl_smallestRemoves := 0; |
| alt { |
| []t_run.timeout { } |
| []t_dummy.timeout { |
| // f_EPTF_RBT_cloneTree(vl_tree, vl_clone); |
| if(rnd() < 0.5) { |
| var float vl_key := int2float(float2int(rnd()*1000000.0))/1000000.0; |
| var integer vl_newItem := f_EPTF_RBT_insertFloatItem(vl_tree, vl_key); |
| log("inserted new item ", vl_newItem, " with key ", vl_key); |
| vl_inserts := vl_inserts + 1; |
| } else { |
| if(rnd() < 0.5) { |
| var integer vl_root := f_EPTF_RBT_getRoot(vl_tree); |
| if(vl_root < 0) { |
| log("removing root item skipped, tree is empty"); |
| t_dummy.start; |
| repeat; |
| } |
| var float vl_key := f_EPTF_RBT_getKeyOfFloatItem(vl_tree, vl_root); |
| log("removing root item ", vl_root, " with key ", vl_key); |
| f_EPTF_RBT_removeItem(vl_tree, vl_root); |
| vl_rootRemoves := vl_rootRemoves + 1; |
| } else { |
| var integer vl_smallest := f_EPTF_RBT_getItemWithSmallestKey(vl_tree); |
| if(vl_smallest < 0) { |
| log("removing smallest item skipped, tree is empty"); |
| t_dummy.start; |
| repeat; |
| } |
| var float vl_key := f_EPTF_RBT_getKeyOfFloatItem(vl_tree, vl_smallest); |
| log("removing smallest item ", vl_smallest, " with key ", vl_key); |
| f_EPTF_RBT_removeItem(vl_tree, vl_smallest); |
| vl_smallestRemoves := vl_smallestRemoves + 1; |
| } |
| } |
| vl_step := vl_step + 1; |
| // if(tsp_pngEachStep) { |
| // f_EPTF_RBT_dumpToPng(vl_tree, "tree_stressTest_"&f_int2str_3digit(vl_step)); |
| // } |
| if(pl_validateTree) { |
| if(not f_EPTF_RBT_isTreeValid(vl_tree)) { |
| setverdict(fail, "invalid tree after "&int2str(vl_step)&" steps"); |
| f_EPTF_RBT_dumpToPng(vl_clone, "tree_stressTest_1"); |
| f_EPTF_RBT_dumpToPng(vl_tree, "tree_stressTest_invalid"); |
| f_EPTF_Base_stop(none); |
| } |
| } |
| |
| t_dummy.start; |
| repeat; |
| } |
| } |
| action("stress test successfuly finished, steps performed: ", vl_step); |
| action("inserts: ", vl_inserts); |
| action("root removes: ", vl_rootRemoves); |
| action("smallest removes: ", vl_smallestRemoves); |
| f_EPTF_Base_stop(pass); |
| } |
| |
| testcase tc_EPTF_RBT_Test_stressTest() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_Test_stressTest(true); |
| } |
| |
| testcase tc_EPTF_RBT_Test_perfTest() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_Test_stressTest(false); |
| } |
| |
| group RBT_PerfTest { |
| |
| modulepar integer tsp_perfTest_elems := 10000000; |
| |
| function f_EPTF_RBT_perfTest_insert_oldRBT( |
| inout EPTF_Float_RedBlackTree pl_rbt, |
| in integer pl_elems, |
| in integer pl_clusterSize) |
| runs on EPTF_RBT_CT |
| return float |
| { |
| var float vl_key := 0.0; |
| var integer vl_clusterCtr := 0; |
| timer T_meas := 1000000.0; |
| T_meas.start; |
| for(var integer i:=0; i<pl_elems; i:=i+1) { |
| vl_clusterCtr := vl_clusterCtr + 1; |
| if(vl_clusterCtr > pl_clusterSize) { |
| vl_key := vl_key + 0.1; |
| vl_clusterCtr := 0; |
| } |
| f_EPTF_RBTreeF_createNewFloatNode(pl_rbt, vl_key, { i }); |
| } |
| var float vl_elapsed := T_meas.read; |
| T_meas.stop; |
| return vl_elapsed; |
| // action(%definitionId&": added ", pl_elems, " elements with cluster size ", pl_clusterSize, " in ", vl_elapsed, " seconds."); |
| } |
| |
| function f_EPTF_RBT_perfTest_remove_oldRBT( |
| inout EPTF_Float_RedBlackTree pl_rbt, |
| in integer pl_elems) |
| runs on EPTF_RBT_CT |
| return float |
| { |
| timer T_meas := 1000000.0; |
| T_meas.start; |
| for(var integer i:=0; i<pl_elems; i:=i+1) { |
| var integer vl_idx; |
| var EPTF_FloatNode vl_node; |
| if(f_EPTF_RBTreeF_searchSmallestNode(pl_rbt, vl_node, vl_idx)) { |
| f_EPTF_RBTreeF_removeFloatNode(pl_rbt, vl_idx, true); |
| } else { |
| action("no more elements, i==", i); |
| break; |
| } |
| } |
| var float vl_elapsed := T_meas.read; |
| T_meas.stop; |
| return vl_elapsed; |
| // action(%definitionId&": removed ", pl_elems, " elements in ", vl_elapsed, " seconds."); |
| /* if(f_EPTF_RBT_getRoot(pl_rbt) != -1) { |
| action("Tree still has elements"); |
| }*/ |
| } |
| |
| testcase tc_EPTF_RBT_perfTest_insert_oldRBT() runs on EPTF_RBT_CT |
| { |
| var EPTF_Float_RedBlackTree vl_rbt; |
| f_EPTF_RBTreeF_initFloatTree(vl_rbt); |
| action("Old RBT"); |
| |
| const integer c_repeat := 5; |
| for(var integer vl_elem := 10000; vl_elem <= 10000000; vl_elem := vl_elem*10) { |
| for(var integer vl_cluster := 1; vl_cluster <= vl_elem; vl_cluster := vl_cluster * 10) { |
| var float vl_insert := 0.0; |
| var float vl_remove := 0.0; |
| for(var integer vl_repeat := 0; vl_repeat < c_repeat; vl_repeat := vl_repeat + 1) { |
| vl_insert := vl_insert + f_EPTF_RBT_perfTest_insert_oldRBT(vl_rbt, vl_elem, vl_cluster); |
| vl_remove := vl_remove + f_EPTF_RBT_perfTest_remove_oldRBT(vl_rbt, vl_elem); |
| } |
| vl_insert := vl_insert / int2float(c_repeat); |
| vl_remove := vl_remove / int2float(c_repeat); |
| action("added ", vl_elem, " elements with cluster size ", vl_cluster, " in ", vl_insert, " seconds."); |
| action("removed ", vl_elem, " elements with cluster size ", vl_cluster, " in ", vl_remove, " seconds."); |
| } |
| } |
| setverdict(pass); |
| action("check top for memory usage..."); |
| timer T_wait := 1000.0; |
| T_wait.start; |
| T_wait.timeout; |
| } |
| |
| testcase tc_EPTF_RBT_perfTest_mem_oldRBT() runs on EPTF_RBT_CT |
| { |
| var EPTF_Float_RedBlackTree vl_rbt; |
| f_EPTF_RBTreeF_initFloatTree(vl_rbt); |
| action("Old RBT"); |
| |
| f_EPTF_RBT_perfTest_insert_oldRBT(vl_rbt, 10000000, 1); |
| |
| setverdict(pass); |
| action("check top for memory usage..."); |
| timer T_wait := 1000.0; |
| T_wait.start; |
| T_wait.timeout; |
| } |
| |
| function f_EPTF_RBT_perfTest_insert_newRBT( |
| in EPTF_RBT_TreeId pl_tree, |
| inout EPTF_IntegerArray2D pl_data, |
| in integer pl_elems, |
| in integer pl_clusterSize) |
| runs on EPTF_RBT_CT |
| return float |
| { |
| var float vl_key := 0.0; |
| var integer vl_clusterCtr := 0; |
| timer T_meas := 1000000.0; |
| T_meas.start; |
| for(var integer i:=0; i<pl_elems; i:=i+1) { |
| vl_clusterCtr := vl_clusterCtr + 1; |
| if(vl_clusterCtr >= pl_clusterSize) { |
| vl_key := vl_key + 0.1; |
| vl_clusterCtr := 0; |
| } |
| var integer vl_idx := f_EPTF_RBT_insertFloatItem(pl_tree, vl_key); |
| pl_data[vl_idx] := { i }; |
| } |
| var float vl_elapsed := T_meas.read; |
| T_meas.stop; |
| return vl_elapsed; |
| } |
| |
| function f_EPTF_RBT_perfTest_remove_newRBT( |
| in EPTF_RBT_TreeId pl_tree, |
| in integer pl_elems) |
| runs on EPTF_RBT_CT |
| return float |
| { |
| timer T_meas := 1000000.0; |
| T_meas.start; |
| for(var integer i:=0; i<pl_elems; i:=i+1) { |
| f_EPTF_RBT_removeItem(pl_tree, f_EPTF_RBT_getItemWithSmallestKey(pl_tree)); |
| } |
| var float vl_elapsed := T_meas.read; |
| T_meas.stop; |
| // action(%definitionId&": removed ", pl_elems, " elements in ", vl_elapsed, " seconds."); |
| if(f_EPTF_RBT_getRoot(pl_tree) != -1) { |
| action("Tree still has elements"); |
| } |
| return vl_elapsed; |
| } |
| |
| testcase tc_EPTF_RBT_perfTest_insert_newRBT() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT("mtc"); |
| var EPTF_RBT_TreeId vl_tree := f_EPTF_RBT_createFloatTree(); |
| action("New RBT"); |
| |
| const integer c_repeat := 5; |
| var EPTF_IntegerArray2D vl_data := {}; |
| for(var integer vl_elem := 10000; vl_elem <= 10000000; vl_elem := vl_elem*10) { |
| for(var integer vl_cluster := 1; vl_cluster <= vl_elem; vl_cluster := vl_cluster * 10) { |
| // for(var integer vl_elem := 1000000; vl_elem <= 10000000; vl_elem := vl_elem*10) { |
| // for(var integer vl_cluster := 1; vl_cluster <= 10; vl_cluster := vl_cluster * 10) { |
| var float vl_insert := 0.0; |
| var float vl_remove := 0.0; |
| for(var integer vl_repeat := 0; vl_repeat < c_repeat; vl_repeat := vl_repeat + 1) { |
| vl_insert := vl_insert + f_EPTF_RBT_perfTest_insert_newRBT(vl_tree, vl_data, vl_elem, vl_cluster); |
| vl_remove := vl_remove + f_EPTF_RBT_perfTest_remove_newRBT(vl_tree, vl_elem); |
| } |
| vl_insert := vl_insert / int2float(c_repeat); |
| vl_remove := vl_remove / int2float(c_repeat); |
| action("added ", vl_elem, " elements with cluster size ", vl_cluster, " in ", vl_insert, " seconds."); |
| action("removed ", vl_elem, " elements with cluster size ", vl_cluster, " in ", vl_remove, " seconds."); |
| } |
| } |
| setverdict(pass); |
| // action("check top for memory usage..."); |
| // timer T_wait := 1000.0; |
| // T_wait.start; |
| // T_wait.timeout; |
| f_EPTF_Base_stop(pass); |
| } |
| |
| testcase tc_EPTF_RBT_perfTest_mem_newRBT() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT("mtc"); |
| var EPTF_RBT_TreeId vl_tree := f_EPTF_RBT_createFloatTree(); |
| action("New RBT"); |
| |
| var EPTF_IntegerArray2D vl_data := {}; |
| f_EPTF_RBT_perfTest_insert_newRBT(vl_tree, vl_data, 10000000, 1); |
| |
| setverdict(pass); |
| action("check top for memory usage..."); |
| timer T_wait := 1000.0; |
| T_wait.start; |
| T_wait.timeout; |
| f_EPTF_Base_stop(pass); |
| } |
| |
| /* type component MyCT { } |
| type record of record of integer intarray; |
| |
| testcase tc_intarray() runs on MyCT |
| { |
| var intarray vl_intarray; |
| for(var integer i:=0; i<10000000; i:=i+1) { |
| vl_intarray[i] := { i }; |
| } |
| timer T_wait := 1000.0; |
| T_wait.start; |
| T_wait.timeout; |
| }*/ |
| |
| } // group RBT_PerfTest |
| |
| |
| testcase tc_csRBT() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT("mtc"); |
| var EPTF_RBT_TreeId vl_tree := f_EPTF_RBT_createCharstringTree(); |
| var EPTF_CharstringList vl_keys := { |
| "Repa", "retek", "mogyoro", "koran", "reggel", "ritkan", "rikkant", "a", "rigo" |
| // "a", "b", "c", "d", "e", "f", "g" |
| // "a", "e", "f", "f", "f", "a", "e", "r", "g", "f", "r", "e", "r", "g", "e", "r" |
| } |
| |
| var EPTF_IntegerList vl_items := {}; |
| for(var integer i:=0; i<sizeof(vl_keys); i:=i+1) { |
| vl_items[i] := f_EPTF_RBT_insertCharstringItem(vl_tree, vl_keys[i]); |
| if(i<10) { |
| f_EPTF_RBT_dumpToPng(vl_tree, "theTree_0"&int2str(i)); |
| } else { |
| f_EPTF_RBT_dumpToPng(vl_tree, "theTree_"&int2str(i)); |
| } |
| } |
| |
| f_EPTF_Base_stop(pass); |
| } |
| |
| testcase tc_intInitTree() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT("mtc"); |
| const EPTF_RBT_TreeInitNode c_Tree := { |
| isRed := false, |
| key := { intKey := 5 }, |
| leftChild := { |
| isRed := false, |
| key := { intKey := 3 }, |
| leftChild := omit, |
| rightChild := { |
| isRed := true, |
| key := { intKey := 4 }, |
| leftChild := omit, |
| rightChild := omit |
| } |
| }, |
| rightChild := { |
| isRed := false, |
| key := { intKey := 6 }, |
| leftChild := omit, |
| rightChild := omit |
| } |
| } |
| |
| var EPTF_RBT_TreeId vl_tree := f_EPTF_RBT_createAndInitTree("myTree", c_Tree); |
| |
| if(vl_tree < 0) { f_EPTF_Base_stop(fail); } |
| |
| f_EPTF_RBT_dumpToPng(vl_tree, %definitionId); |
| |
| f_EPTF_Base_stop(pass); |
| } |
| |
| } // group RBTv2 |
| |
| //========================================================================= |
| // Control Part |
| //========================================================================= |
| |
| control |
| { |
| select (f_GetEnv("TTCN_TEST_TYPE")) { |
| case ("SMOKE") { |
| execute(tc_RBT_Test_testIntegerRBTGrowage()); |
| execute(tc_RBT_Test_testFloatRBTGrowage()); |
| execute(tc_EPTF_RBTreeF_initFloatTree()); |
| execute(tc_EPTF_RBTreeI_initIntegerTree()); |
| execute(tc_EPTF_RBTreeI_createNewIntegerNode()); |
| execute(tc_EPTF_RBTreeI_removeIntegerNodeWithSameKey()); |
| execute(tc_EPTF_RBTreeI_removeIntegerNode()); |
| execute(tc_EPTF_RBTreeF_removeFloatNodeWithSameKey()); |
| execute(tc_EPTF_RBTreeI_getIntegerElementNodeByKey()); |
| execute(tc_EPTF_RBTreeF_getFloatNodeByKey()); |
| execute(tc_EPTF_RBTreeI_searchSmallestIntegerNode()); |
| execute(tc_EPTF_RBTreeI_getBusyEventHeadIndex()); |
| execute(tc_EPTF_RBTreeF_searchSmallestNode()); |
| execute(tc_EPTF_RBTreeF_getSmallestNodeFromCache()); |
| execute(tc_EPTF_RBTreeF_getBusyEventHeadIndex()); |
| execute(tc_EPTF_RBTree_getNextSmallestFloatElementIndex()); |
| execute(tc_EPTF_RBTreeF_testFloatTreeCluster()); |
| } |
| case else { |
| execute(tc_RBT_Test_testIntegerRBTGrowage()); |
| execute(tc_RBT_Test_testFloatRBTGrowage()); |
| execute(tc_EPTF_RBTreeF_initFloatTree()); |
| execute(tc_EPTF_RBTreeI_initIntegerTree()); |
| execute(tc_EPTF_RBTreeI_createNewIntegerNode()); |
| execute(tc_EPTF_RBTreeI_removeIntegerNodeWithSameKey()); |
| execute(tc_EPTF_RBTreeI_removeIntegerNode()); |
| execute(tc_EPTF_RBTreeF_removeFloatNodeWithSameKey()); |
| execute(tc_EPTF_RBTreeI_getIntegerElementNodeByKey()); |
| execute(tc_EPTF_RBTreeF_getFloatNodeByKey()); |
| execute(tc_EPTF_RBTreeI_searchSmallestIntegerNode()); |
| execute(tc_EPTF_RBTreeI_getBusyEventHeadIndex()); |
| execute(tc_EPTF_RBTreeF_searchSmallestNode()); |
| execute(tc_EPTF_RBTreeF_getSmallestNodeFromCache()); |
| execute(tc_EPTF_RBTreeF_getBusyEventHeadIndex()); |
| execute(tc_EPTF_RBTree_getNextSmallestFloatElementIndex()); |
| execute(tc_EPTF_RBTreeF_testFloatTreeCluster()); |
| execute(tc_EPTF_RBT_Test_insertAscending()); |
| execute(tc_EPTF_RBT_Test_insertDescending()); |
| execute(tc_EPTF_RBT_Test_insertRandom()); |
| execute(tc_EPTF_RBT_Test_removeRootAsc()); |
| execute(tc_EPTF_RBT_Test_removeRootDesc()); |
| execute(tc_EPTF_RBT_Test_removeRootRnd()); |
| execute(tc_EPTF_RBT_Test_removeAllFromRootAsc()); |
| execute(tc_EPTF_RBT_Test_removeAllFromRootDesc()); |
| execute(tc_EPTF_RBT_Test_removeAllFromRootRnd()); |
| execute(tc_EPTF_RBT_Test_removeAllFromSmallestAsc()); |
| execute(tc_EPTF_RBT_Test_removeAllFromSmallestDesc()); |
| execute(tc_EPTF_RBT_Test_removeAllFromSmallestRnd()); |
| execute(tc_EPTF_RBT_Test_stressTest()); |
| execute(tc_EPTF_RBT_Test_Neg_insertIntoNonexistingTree()); |
| execute(tc_EPTF_RBT_Test_insertIntParentBlack()); |
| execute(tc_EPTF_RBT_Test_insertIntParentRedUncleRed()); |
| execute(tc_EPTF_RBT_Test_insertIntParentRedUncleRed2()); |
| execute(tc_EPTF_RBT_Test_insertIntParentRedUncleBlack()); |
| execute(tc_EPTF_RBT_Test_insertIntParentRedUncleBlack2()); |
| execute(tc_EPTF_RBT_Test_deleteTree()); |
| execute(tc_EPTF_RBT_Test_Neg_deleteTree()); |
| execute(tc_EPTF_RBT_Test_getName()); |
| execute(tc_EPTF_RBT_Test_Neg_getName()); |
| execute(tc_EPTF_RBT_Test_removeItem()); |
| execute(tc_EPTF_RBT_Test_removeBlack1()); |
| execute(tc_EPTF_RBT_Test_removeBlack2()); |
| execute(tc_EPTF_RBT_Test_removeBlack3()); |
| execute(tc_EPTF_RBT_Test_removeBlack4()); |
| execute(tc_EPTF_RBT_Test_removeBlack5()); |
| execute(tc_EPTF_RBT_Test_removeRed()); |
| execute(tc_EPTF_RBT_Test_getKeyOfIntItem()); |
| execute(tc_EPTF_RBT_Test_Neg_getKeyOfIntItem1()); |
| execute(tc_EPTF_RBT_Test_Neg_getKeyOfIntItem2()); |
| execute(tc_EPTF_RBT_Test_getKeyOfFloatItem()); |
| execute(tc_EPTF_RBT_Test_Neg_getKeyOfFloatItem1()); |
| execute(tc_EPTF_RBT_Test_Neg_getKeyOfFloatItem2()); |
| execute(tc_EPTF_RBT_Test_getKeyOfCharstringItem()); |
| execute(tc_EPTF_RBT_Test_Neg_getKeyOfCharstringItem1()); |
| execute(tc_EPTF_RBT_Test_Neg_getKeyOfCharstringItem2()); |
| execute(tc_EPTF_RBT_Test_findFirstItemByIntKey()); |
| execute(tc_EPTF_RBT_Test_Neg_findFirstItemByIntKey()); |
| execute(tc_EPTF_RBT_Test_findFirstItemByFloatKey()); |
| execute(tc_EPTF_RBT_Test_Neg_findFirstItemByFloatKey()); |
| execute(tc_EPTF_RBT_Test_findFirstItemByCharstringKey()); |
| execute(tc_EPTF_RBT_Test_Neg_findFirstItemByCharstringKey()); |
| execute(tc_EPTF_RBT_Test_getRootLeftRightParent()); |
| execute(tc_EPTF_RBT_Test_getNextInChain()); |
| execute(tc_EPTF_RBT_Test_Neg_getNextInChain1()); |
| execute(tc_EPTF_RBT_Test_Neg_getNextInChain2()); |
| execute(tc_EPTF_RBT_Test_getPrevInChain()); |
| execute(tc_EPTF_RBT_Test_Neg_getPrevInChain1()); |
| execute(tc_EPTF_RBT_Test_Neg_getPrevInChain2()); |
| execute(tc_EPTF_RBT_Test_iterateIncremental()); |
| execute(tc_EPTF_RBT_Test_Neg_iterateIncremental1()); |
| execute(tc_EPTF_RBT_Test_Neg_iterateIncremental2()); |
| execute(tc_EPTF_RBT_Test_sortIncrementalInt()); |
| execute(tc_EPTF_RBT_Test_sortIncrementalFloat()); |
| execute(tc_EPTF_RBT_Test_sortIncrementalCharstring()); |
| } |
| } |
| } |
| } // end of module |