| /////////////////////////////////////////////////////////////////////////////// |
| // // |
| // 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_RedBlackTree_demo |
| // |
| // Purpose: |
| // This module contains function definitions for testing EPTF Red Black Tree |
| // |
| // Module Parameters: |
| // - |
| // |
| // Module depends on: |
| // <EPTF_CLL_RBtree_Functions> |
| // <EPTF_CLL_RBtree_PrivateFunctions> |
| // <EPTF_CLL_RBtreeFloat_Functions> |
| // <EPTF_CLL_RBtreeFloat_PrivateFunctions> |
| // <EPTF_CLL_RBtree_Definitions> |
| // <EPTF_CLL_Common_Definitions> |
| // |
| // Current Owner: |
| // Gabor Tatarka (egbotat) |
| // |
| // Last Review Date: |
| // - |
| // |
| // Detailed Comments: |
| // - |
| /////////////////////////////////////////////////////////// |
| |
| module EPTF_RedBlackTree_demo { |
| |
| import from EPTF_CLL_RBtreeFloat_Functions all; |
| import from EPTF_CLL_RBtree_Definitions all; |
| import from EPTF_CLL_Common_Definitions all; |
| |
| //import from EPTF_CLL_Base_Definitions all; |
| import from EPTF_CLL_Base_Functions all; |
| import from EPTF_CLL_RBT_Definitions all; |
| import from EPTF_CLL_RBT_Functions all; |
| |
| |
| modulepar EPTF_FloatList tsp_itemsToInsert := { |
| 12.0, 3.0, 22.0, 8.0, 3.14, 1.41, 8.0, 9.3 |
| } |
| |
| testcase tc_insertItems() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| |
| var EPTF_RBT_TreeId vl_tree := f_EPTF_RBT_createFloatTree("my float tree"); |
| |
| action("Input: ", tsp_itemsToInsert); |
| |
| for(var integer i:=0; i<lengthof(tsp_itemsToInsert); i:=i+1) { |
| f_EPTF_RBT_insertFloatItem(vl_tree, tsp_itemsToInsert[i]); |
| } |
| |
| f_EPTF_RBT_dumpToPng(vl_tree, %definitionId); |
| var integer vl_smallest := f_EPTF_RBT_getItemWithSmallestKey(vl_tree); |
| action("Index of smallest item: ", vl_smallest); |
| |
| action("Key of smallest item: ", f_EPTF_RBT_getKeyOfFloatItem(vl_tree, vl_smallest)); |
| //note: same as: |
| //action("Key of smallest item: ", tsp_itemsToInsert[vl_smallest]); |
| |
| var EPTF_IntegerList vl_order; |
| f_EPTF_RBT_sortIncremental(vl_tree, vl_order); |
| action("Order of items: ", vl_order); |
| var EPTF_FloatList vl_sorted := {}; |
| for(var integer i:=0; i<lengthof(vl_order); i:=i+1) { |
| vl_sorted[i] := f_EPTF_RBT_getKeyOfFloatItem(vl_tree, vl_order[i]); |
| // same as: |
| // vl_sorted[i] := tsp_itemsToInsert[vl_order[i]]; |
| } |
| action("Sorted keys: ", vl_sorted); |
| |
| f_EPTF_RBT_dumpToPng(vl_tree, %definitionId); |
| |
| f_EPTF_Base_stop(pass); |
| } |
| |
| modulepar EPTF_CharstringList tsp_stringsToSort := { |
| "The", "words", "of", "this", "sentence", "are", "going", "to", "be", "sorted" |
| } |
| |
| testcase tc_sortStrings() runs on EPTF_RBT_CT |
| { |
| f_EPTF_RBT_init_CT(%definitionId); |
| |
| var EPTF_RBT_TreeId vl_tree := f_EPTF_RBT_createCharstringTree("my charstring tree"); |
| |
| action("Input: ", tsp_stringsToSort); |
| |
| for(var integer i:=0; i<lengthof(tsp_stringsToSort); i:=i+1) { |
| f_EPTF_RBT_insertCharstringItem(vl_tree, tsp_stringsToSort[i]); |
| } |
| |
| var EPTF_IntegerList vl_order; |
| f_EPTF_RBT_sortIncremental(vl_tree, vl_order); |
| |
| var EPTF_CharstringList vl_sorted := {}; |
| for(var integer i:=0; i<lengthof(vl_order); i:=i+1) { |
| vl_sorted[i] := f_EPTF_RBT_getKeyOfCharstringItem(vl_tree, vl_order[i]); |
| } |
| |
| action("Sorted: ", vl_sorted); |
| |
| f_EPTF_RBT_dumpToPng(vl_tree, %definitionId); |
| |
| f_EPTF_Base_stop(pass); |
| } |
| |
| |
| |
| group RBT_Obsolete { |
| |
| type component PCOComp {} |
| |
| |
| //////////////////////////////////////////////////////////////////////////// |
| // by egbozie |
| |
| //print the red-black tree into the log as a graphviz file |
| function Log_RBTree(in charstring title, in EPTF_Float_RedBlackTree rb_Tree) |
| { |
| //print preamble |
| log("graphviz:"&title&": digraph structs"); |
| log("graphviz:"&title&": { node [shape=record, width=1.5, height=0.3, fixedsize=true, style=filled];"); |
| log("graphviz:"&title&": "& title &" [label="&title&" color=white];") |
| //print nodes |
| Log_RBTree_FromPos(title, rb_Tree, rb_Tree.root); |
| //print postamble |
| log("graphviz:"&title&":}"); |
| } |
| function Log_RBTree_FromPos(in charstring title, in EPTF_Float_RedBlackTree rb_Tree, in integer pos) |
| { |
| //print the node |
| var charstring mycolor; |
| var charstring mytime := float2str(rb_Tree.floatKeyData[pos].key) |
| if (rb_Tree.nodes[pos].color == red) { |
| mycolor:="red" |
| } else { |
| mycolor := "gray40" |
| } |
| log("graphviz:"&title&": "& int2str(pos)& " [label=""{|"&int2str(pos)&":"&mytime&"|{<left>|<right>}}"", color="&mycolor&"];"); |
| |
| var charstring mylabel; |
| //print arrows to children, if any |
| // if there is a left child, print arrow(s) and the subtree(s) recursively |
| if (rb_Tree.nodes[pos].left!=-1) { |
| // if there is also a right child, then there will be two arrows, |
| // otherwise only one |
| if (rb_Tree.nodes[pos].right!=-1) { |
| mylabel := ":left" |
| } else { |
| mylabel := "" |
| }; |
| log("graphviz:"&title&": "&int2str(pos)& mylabel&" -> "& int2str(rb_Tree.nodes[pos].left)&";"); |
| Log_RBTree_FromPos(title, rb_Tree, rb_Tree.nodes[pos].left); |
| } |
| // if there is a right child |
| if (rb_Tree.nodes[pos].right!=-1) { |
| // if there is also a left child, then there will be two arrows, |
| // otherwise only one |
| if (rb_Tree.nodes[pos].left!=-1) { |
| mylabel := ":right" |
| } else { |
| mylabel := "" |
| }; |
| log("graphviz:"&title&": "& int2str(pos)&mylabel&" -> "& int2str(rb_Tree.nodes[pos].right)&";"); |
| Log_RBTree_FromPos(title, rb_Tree, rb_Tree.nodes[pos].right); |
| } |
| } |
| |
| function f_checkTree(in EPTF_Float_RedBlackTree checkThis, in EPTF_Float_RedBlackTree againstThis) { |
| log("f_checkTree: checkThis:=", checkThis,", againstThis:", againstThis); |
| if (checkThis == againstThis) { |
| setverdict(pass); |
| } else { |
| setverdict(fail, log2str(checkThis, " should be ", againstThis)); |
| }; |
| } |
| //////////////////////////////////////////////////////////// |
| testcase tc_add_10_elements() runs on PCOComp system PCOComp { |
| |
| var EPTF_Float_RedBlackTree rb_Tree; |
| var integer I; |
| var integer j; |
| var charstring s; |
| var EPTF_IntegerList data; |
| |
| // Init |
| f_EPTF_RBTreeF_initFloatTree(rb_Tree); |
| |
| // Add element 1 |
| data := {}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 1.0, data); |
| //Log_RBTree("Added_"& int2str(I), rb_Tree); |
| |
| // Add element 2 |
| data := {}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 6.0, data); |
| //Log_RBTree("Added_"& int2str(I), rb_Tree); |
| |
| // Add element 3 |
| data := {}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 8.0, data); |
| //Log_RBTree("Added_"& int2str(I), rb_Tree); |
| |
| // Add element 4 |
| data := {}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 11.0, data); |
| //Log_RBTree("Added_"& int2str(I), rb_Tree); |
| |
| // Add element 5 |
| data := {}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 13.0, data); |
| //Log_RBTree("Added_"& int2str(I), rb_Tree); |
| |
| // Add element 6 |
| data := {}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 15.0, data); |
| //Log_RBTree("Added_"& int2str(I), rb_Tree); |
| |
| // Add element 7 |
| data := {}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 17.0, data); |
| //Log_RBTree("Added_"& int2str(I), rb_Tree); |
| |
| // Add element 8 |
| data := {}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 22.0, data); |
| //Log_RBTree("Added_"& int2str(I), rb_Tree); |
| |
| // Add element 9 |
| data := {}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 25.0, data); |
| //Log_RBTree("Added_"& int2str(I), rb_Tree); |
| |
| // Add element 10 |
| data := {}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 27.0, data); |
| //Log_RBTree("Added_"& int2str(I), rb_Tree); |
| |
| log("DEBUG: Insertions done..."); |
| |
| // Printout |
| log("-----------------"); |
| log("ROOT: " & int2str(rb_Tree.root)); |
| for (j := 0; j <= rb_Tree.nodesCurMaxIndex; j:=j+1) { |
| log("Index: " & int2str(j)); |
| log("Key: " & float2str(rb_Tree.floatKeyData[j].key)); |
| |
| if ( rb_Tree.nodes[j].color != unused) { |
| if (rb_Tree.nodes[j].color == red) { |
| s := "RED"; |
| } else if (rb_Tree.nodes[j].color == black){ |
| s := "BLACK"; |
| } else if (rb_Tree.nodes[j].color == invalid){ |
| s := "INVALID"; |
| } else { |
| s := "UNUSED"; |
| } |
| log("Color: " & s); |
| log("Parent: " & int2str(rb_Tree.nodes[j].parent)); |
| log("Left: " & int2str(rb_Tree.nodes[j].left)); |
| log("Right: " & int2str(rb_Tree.nodes[j].right)); |
| log("-----------------"); |
| } // if |
| } // for |
| |
| var EPTF_Float_RedBlackTree mytree := { |
| nodes := { |
| { color := black, left := 0, right := 0, parent := 0, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := true }, //leaf |
| { color := black, left := 5, right := 0, parent := 0, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := true }, //leaf |
| { color := black, left := 0, right := 0, parent := 3, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := black, left := 2, right := 4, parent := 5, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := black, left := 0, right := 0, parent := 3, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := black, left := 3, right := 7, parent := 1, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := black, left := 0, right := 0, parent := 7, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := black, left := 6, right := 9, parent := 5, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := black, left := 0, right := 0, parent := 9, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := red, left := 8, right := 10, parent := 7, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := black, left := 0, right := 11, parent := 9, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := red, left := 0, right := 0, parent := 10, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false } }, |
| floatKeyData := { |
| { key := 0.000000, data := { } }, |
| { key := 0.000000, data := { } }, |
| { key := 1.000000, data := { } }, |
| { key := 6.000000, data := { } }, |
| { key := 8.000000, data := { } }, |
| { key := 11.000000, data := { } }, |
| { key := 13.000000, data := { } }, |
| { key := 15.000000, data := { } }, |
| { key := 17.000000, data := { } }, |
| { key := 22.000000, data := { } }, |
| { key := 25.000000, data := { } }, |
| { key := 27.000000, data := { } } }, |
| nodesCurMaxIndex := 11, |
| root := 1, |
| nil := 0, |
| freeHead := -1, |
| freeTail := -1, |
| smallestKeyIndex := 2, |
| isSmallestCacheValid := true, |
| nOfElements := 10, |
| acceptableMaxSize := -1 |
| } |
| |
| f_checkTree(rb_Tree, mytree); |
| |
| } //testcase tc_add_10_elements() |
| |
| testcase tc_removeElement() runs on PCOComp system PCOComp { |
| |
| var EPTF_Float_RedBlackTree rb_Tree; |
| var integer I; |
| var integer j; |
| var charstring s; |
| var EPTF_IntegerList data; |
| |
| // Init |
| f_EPTF_RBTreeF_initFloatTree(rb_Tree); |
| |
| // Add element 1 |
| data := {}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 100.0, data); |
| |
| // Add element 2 |
| data := {}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 150.0, data); |
| |
| // Add element 3 |
| data := {}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 50.0, data); |
| |
| // Add element 4 |
| data := {}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 25.0, data); |
| |
| // Add element 5 |
| data := {}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 40.0, data); |
| |
| log("DEBUG: Insertions done..."); |
| |
| // Printout |
| log("ROOT: " & int2str(rb_Tree.root)); |
| for (j := 0; j <= rb_Tree.nodesCurMaxIndex; j:=j+1) { |
| log("Index: " & int2str(j)); |
| log("Key: " & float2str(rb_Tree.floatKeyData[j].key)); |
| |
| if (rb_Tree.nodes[j].color == red) { |
| s := "RED"; |
| } else if (rb_Tree.nodes[j].color == black){ |
| s := "BLACK"; |
| } else { |
| s := "UNUSED"; |
| } |
| log("Color: " & s); |
| log("Parent: " & int2str(rb_Tree.nodes[j].parent)); |
| log("Left: " & int2str(rb_Tree.nodes[j].left)); |
| log("Right: " & int2str(rb_Tree.nodes[j].right)); |
| log("-----------------"); |
| } // for |
| |
| var EPTF_Float_RedBlackTree mytree := { |
| nodes := { |
| { color := black, left := 0, right := 0, parent := 0, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := true }, |
| { color := black, left := 2, right := 0, parent := 0, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := true }, |
| { color := black, left := 6, right := 3, parent := 1, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := black, left := 0, right := 0, parent := 2, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := red, left := 0, right := 0, parent := 6, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := red, left := 0, right := 0, parent := 6, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := black, left := 5, right := 4, parent := 2, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false } }, |
| floatKeyData := { |
| { key := 0.000000, data := { } }, |
| { key := 0.000000, data := { } }, |
| { key := 100.000000, data := { } }, |
| { key := 150.000000, data := { } }, |
| { key := 50.000000, data := { } }, |
| { key := 25.000000, data := { } }, |
| { key := 40.000000, data := { } } }, |
| nodesCurMaxIndex := 6, |
| root := 1, |
| nil := 0, |
| freeHead := -1, |
| freeTail := -1, |
| smallestKeyIndex := 5, |
| isSmallestCacheValid := true, |
| nOfElements := 5, |
| acceptableMaxSize := -1 |
| } |
| |
| f_checkTree(rb_Tree, mytree); |
| |
| log("DEBUG: Deletes node with key value '40.0'..."); |
| f_EPTF_RBTreeF_removeFloatNode(rb_Tree, 4, true); |
| |
| // Printout |
| log("ROOT: " & int2str(rb_Tree.root)); |
| for (j := 0; j <= rb_Tree.nodesCurMaxIndex; j:=j+1) { |
| log("Index: " & int2str(j)); |
| log("Key: " & float2str(rb_Tree.floatKeyData[j].key)); |
| |
| if (rb_Tree.nodes[j].color == red) { |
| s := "RED"; |
| } else if (rb_Tree.nodes[j].color == black){ |
| s := "BLACK"; |
| } else { |
| s := "UNUSED"; |
| } |
| log("Color: " & s); |
| log("Parent: " & int2str(rb_Tree.nodes[j].parent)); |
| log("Left: " & int2str(rb_Tree.nodes[j].left)); |
| log("Right: " & int2str(rb_Tree.nodes[j].right)); |
| log("-----------------"); |
| } // for |
| |
| mytree := { |
| nodes := { |
| { color := black, left := 0, right := 0, parent := 6, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := true }, |
| { color := black, left := 2, right := 0, parent := 0, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := true }, |
| { color := black, left := 6, right := 3, parent := 1, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := black, left := 0, right := 0, parent := 2, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := unused, left := -1, right := -1, parent := 6, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := red, left := 0, right := 0, parent := 6, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := black, left := 5, right := 0, parent := 2, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false } }, |
| floatKeyData := { |
| { key := 0.000000, data := { } }, |
| { key := 0.000000, data := { } }, |
| { key := 100.000000, data := { } }, |
| { key := 150.000000, data := { } }, |
| { key := 50.000000, data := { } }, |
| { key := 25.000000, data := { } }, |
| { key := 40.000000, data := { } } }, |
| nodesCurMaxIndex := 6, |
| root := 1, |
| nil := 0, |
| freeHead := 4, |
| freeTail := 4, |
| smallestKeyIndex := 5, |
| isSmallestCacheValid := true, |
| nOfElements := 4, |
| acceptableMaxSize := -1 |
| } |
| |
| f_checkTree(rb_Tree, mytree); |
| //Log_RBTree("Final", rb_Tree); |
| |
| } //testcase tc_removeElement() |
| |
| testcase tc_remove_4_elements() runs on PCOComp system PCOComp { |
| |
| var EPTF_Float_RedBlackTree rb_Tree; |
| var integer I; |
| var integer j; |
| var charstring s; |
| var EPTF_IntegerList data; |
| |
| // Init |
| f_EPTF_RBTreeF_initFloatTree(rb_Tree); |
| |
| // Add 8 elements |
| data := {}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 1.0, data); |
| //Log_RBTree("Added_"& int2str(I), rb_Tree); |
| data := {}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 6.0, data); |
| //Log_RBTree("Added_"& int2str(I), rb_Tree); |
| data := {}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 8.0, data); |
| //Log_RBTree("Added_"& int2str(I), rb_Tree); |
| data := {}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 11.0, data); |
| //Log_RBTree("Added_"& int2str(I), rb_Tree); |
| data := {}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 25.0, data); |
| //Log_RBTree("Added_"& int2str(I), rb_Tree); |
| data := {}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 27.0, data); |
| //Log_RBTree("Added_"& int2str(I), rb_Tree); |
| data := {}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 5.0, data); |
| //Log_RBTree("Added_"& int2str(I), rb_Tree); |
| data := {}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 7.0, data); |
| //Log_RBTree("Added_"& int2str(I), rb_Tree); |
| log("DEBUG: Insertions done..."); |
| |
| var EPTF_Float_RedBlackTree mytree := { |
| nodes := { |
| { color := black, left := 0, right := 0, parent := 0, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := true }, |
| { color := black, left := 3, right := 0, parent := 0, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := true }, |
| { color := black, left := 0, right := 8, parent := 3, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := black, left := 2, right := 5, parent := 1, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| {color := black, left := 9, right := 0, parent := 5, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := red, left := 4, right := 6, parent := 3, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := black, left := 0, right := 7, parent := 5, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := red, left := 0, right := 0, parent := 6, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := red, left := 0, right := 0, parent := 2, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := red, left := 0, right := 0, parent := 4, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false } }, |
| floatKeyData := { |
| { key := 0.000000, data := { } }, |
| { key := 0.000000, data := { } }, |
| { key := 1.000000, data := { } }, |
| { key := 6.000000, data := { } }, |
| { key := 8.000000, data := { } }, |
| { key := 11.000000, data := { } }, |
| { key := 25.000000, data := { } }, |
| { key := 27.000000, data := { } }, |
| { key := 5.000000, data := { } }, |
| { key := 7.000000, data := { } } }, |
| nodesCurMaxIndex := 9, |
| root := 1, |
| nil := 0, |
| freeHead := -1, |
| freeTail := -1, |
| smallestKeyIndex := 2, |
| isSmallestCacheValid := true, |
| nOfElements := 8, |
| acceptableMaxSize := -1 |
| } |
| |
| f_checkTree(rb_Tree,mytree); |
| |
| f_EPTF_RBTreeF_removeFloatNode(rb_Tree, 2, true); //smallest |
| //Log_RBTree("Removed_0", rb_Tree); |
| |
| // Printout |
| log("ROOT: " & int2str(rb_Tree.root)); |
| for (j := 0; j <= rb_Tree.nodesCurMaxIndex; j:=j+1) { |
| log("Index: " & int2str(j)); |
| log("Key: " & float2str(rb_Tree.floatKeyData[j].key)); |
| |
| if (rb_Tree.nodes[j].color == red) { |
| s := "RED"; |
| } else if (rb_Tree.nodes[j].color == black){ |
| s := "BLACK"; |
| } else { |
| s := "UNUSED"; |
| } |
| log("Color: " & s); |
| log("Parent: " & int2str(rb_Tree.nodes[j].parent)); |
| log("Left: " & int2str(rb_Tree.nodes[j].left)); |
| log("Right: " & int2str(rb_Tree.nodes[j].right)); |
| log("-----------------"); |
| } // for |
| |
| mytree := { |
| nodes := { |
| { color := black, left := 0, right := 0, parent := 0, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := true }, |
| { color := black, left := 3, right := 0, parent := 0, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := true }, |
| { color := unused, left := -1, right := -1, parent := 3, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := black, left := 8, right := 5, parent := 1, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := black, left := 9, right := 0, parent := 5, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := red, left := 4, right := 6, parent := 3, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := black, left := 0, right := 7, parent := 5, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := red, left := 0, right := 0, parent := 6, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := black, left := 0, right := 0, parent := 3, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := red, left := 0, right := 0, parent := 4, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false } }, |
| floatKeyData := { |
| { key := 0.000000, data := { } }, |
| { key := 0.000000, data := { } }, |
| { key := 1.000000, data := { } }, |
| { key := 6.000000, data := { } }, |
| { key := 8.000000, data := { } }, |
| { key := 11.000000, data := { } }, |
| { key := 25.000000, data := { } }, |
| { key := 27.000000, data := { } }, |
| { key := 5.000000, data := { } }, |
| { key := 7.000000, data := { } } }, |
| nodesCurMaxIndex := 9, |
| root := 1, |
| nil := 0, |
| freeHead := 2, |
| freeTail := 2, |
| smallestKeyIndex := 2, |
| isSmallestCacheValid := false, |
| nOfElements := 7, |
| acceptableMaxSize := -1 |
| } |
| |
| f_checkTree(rb_Tree,mytree); |
| |
| f_EPTF_RBTreeF_removeFloatNode(rb_Tree, 8, true); //next smallest |
| //Log_RBTree("Removed_6", rb_Tree); |
| |
| mytree := { |
| nodes := { |
| { color := black, left := 0, right := 0, parent := 3, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := true }, |
| { color := black, left := 5, right := 0, parent := 0, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := true }, |
| { color := unused, left := -1, right := 8, parent := 3, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := black, left := 0, right := 0, parent := 9, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := black, left := 0, right := 0, parent := 9, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := black, left := 9, right := 6, parent := 1, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := black, left := 0, right := 7, parent := 5, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := red, left := 0, right := 0, parent := 6, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := unused, left := 2, right := -1, parent := 3, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := red, left := 3, right := 4, parent := 5, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false } }, |
| floatKeyData := { |
| { key := 0.000000, data := { } }, |
| { key := 0.000000, data := { } }, |
| { key := 1.000000, data := { } }, |
| { key := 6.000000, data := { } }, |
| { key := 8.000000, data := { } }, |
| { key := 11.000000, data := { } }, |
| { key := 25.000000, data := { } }, |
| { key := 27.000000, data := { } }, |
| { key := 5.000000, data := { } }, |
| { key := 7.000000, data := { } } }, |
| nodesCurMaxIndex := 9, |
| root := 1, |
| nil := 0, |
| freeHead := 2, |
| freeTail := 8, |
| smallestKeyIndex := 2, |
| isSmallestCacheValid := false, |
| nOfElements := 6, |
| acceptableMaxSize := -1 |
| } |
| |
| f_checkTree(rb_Tree,mytree); |
| |
| f_EPTF_RBTreeF_removeFloatNode(rb_Tree, 3, true); //next smallest |
| //Log_RBTree("Removed_1", rb_Tree); |
| |
| mytree := { |
| nodes := { |
| { color := black, left := 0, right := 0, parent := 9, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := true }, |
| { color := black, left := 5, right := 0, parent := 0, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := true }, |
| { color := unused, left := -1, right := 8, parent := 3, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := unused, left := 8, right := -1, parent := 9, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := red, left := 0, right := 0, parent := 9, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := black, left := 9, right := 6, parent := 1, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := black, left := 0, right := 7, parent := 5, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := red, left := 0, right := 0, parent := 6, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := unused, left := 2, right := 3, parent := 3, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := black, left := 0, right := 4, parent := 5, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false } }, |
| floatKeyData := { |
| { key := 0.000000, data := { } }, |
| { key := 0.000000, data := { } }, |
| { key := 1.000000, data := { } }, |
| { key := 6.000000, data := { } }, |
| { key := 8.000000, data := { } }, |
| { key := 11.000000, data := { } }, |
| { key := 25.000000, data := { } }, |
| { key := 27.000000, data := { } }, |
| { key := 5.000000, data := { } }, |
| { key := 7.000000, data := { } } }, |
| nodesCurMaxIndex := 9, |
| root := 1, |
| nil := 0, |
| freeHead := 2, |
| freeTail := 3, |
| smallestKeyIndex := 2, |
| isSmallestCacheValid := false, |
| nOfElements := 5, |
| acceptableMaxSize := -1 |
| } |
| |
| f_checkTree(rb_Tree, mytree); |
| |
| f_EPTF_RBTreeF_removeFloatNode(rb_Tree, 9, true); //next smallest |
| //Log_RBTree("Removed_7", rb_Tree); |
| |
| mytree := { |
| nodes := { |
| { color := black, left := 0, right := 0, parent := 9, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := true }, |
| { color := black, left := 5, right := 0, parent := 0, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := true }, |
| { color := unused, left := -1, right := 8, parent := 3, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := unused, left := 8, right := 9, parent := 9, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := black, left := 0, right := 0, parent := 5, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := black, left := 4, right := 6, parent := 1, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := black, left := 0, right := 7, parent := 5, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := red, left := 0, right := 0, parent := 6, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := unused, left := 2, right := 3, parent := 3, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := unused, left := 3, right := -1, parent := 5, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false } }, |
| floatKeyData := { |
| { key := 0.000000, data := { } }, |
| { key := 0.000000, data := { } }, |
| { key := 1.000000, data := { } }, |
| { key := 6.000000, data := { } }, |
| { key := 8.000000, data := { } }, |
| { key := 11.000000, data := { } }, |
| { key := 25.000000, data := { } }, |
| { key := 27.000000, data := { } }, |
| { key := 5.000000, data := { } }, |
| { key := 7.000000, data := { } } }, |
| nodesCurMaxIndex := 9, |
| root := 1, |
| nil := 0, |
| freeHead := 2, |
| freeTail := 9, |
| smallestKeyIndex := 2, |
| isSmallestCacheValid := false, |
| nOfElements := 4, |
| acceptableMaxSize := -1 |
| } |
| |
| f_checkTree(rb_Tree,mytree); |
| //Log_RBTree("Final", rb_Tree); |
| |
| } //tc_remove_4_elements() |
| |
| testcase tc_findSmallestIndex() runs on PCOComp system PCOComp { |
| |
| var EPTF_Float_RedBlackTree rb_Tree; |
| |
| // Init |
| f_EPTF_RBTreeF_initFloatTree(rb_Tree); |
| |
| var integer smallestIndex := -1; |
| if (f_RBTree_getBusyEventHeadIndex(rb_Tree, smallestIndex)) { |
| log("Smallest index: " & int2str(smallestIndex)); |
| log(" ^^^^^^^^^^^^^^^^^^^ "); |
| setverdict(fail, "Error occured during call f_RBTree_getBusyEventHeadIndex"); |
| } else { |
| log("Smallest index: " & int2str(smallestIndex)); |
| log(" ^^^^^^^^^^^^^^^^^^^ "); |
| log("Could not find a valid smallest index... "); |
| if (smallestIndex == -1) { |
| setverdict(pass); |
| } else { |
| setverdict(fail, "Smallest index should be -1 after init!"); |
| } |
| } |
| |
| } //testcase tc_findSmallestIndex() |
| |
| |
| testcase tc_findSmallest() runs on PCOComp system PCOComp { |
| |
| var EPTF_Float_RedBlackTree rb_Tree; |
| var integer I; |
| var integer j; |
| var charstring s; |
| var EPTF_IntegerList data; |
| |
| // Init |
| f_EPTF_RBTreeF_initFloatTree(rb_Tree); |
| |
| // Add element 1 |
| data := {}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 100.0, data); |
| |
| // Add element 2 |
| data := {}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 150.0, data); |
| |
| // Add element 3 |
| data := {}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 50.0, data); |
| |
| // Add element 4 |
| data := {}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 25.0, data); |
| |
| // Add element 5 |
| data := {}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 40.0, data); |
| |
| log("DEBUG: Insertions done..."); |
| |
| var EPTF_FloatNode smallestNode := c_EPTF_emptyFloatNode; |
| if (f_EPTF_RBTreeF_getSmallestNodeFromCache(rb_Tree, smallestNode)) { |
| log("Smallest key: " & float2str(smallestNode.key)); |
| log(" ^^^^^^^^^^^^^^^^^^^^^^^^ "); |
| if (smallestNode.key == 25.0) {setverdict(pass);} else {setverdict(fail, log2str("smallestNode.key should be 25.0, but it is: ", smallestNode.key));} |
| } else { |
| setverdict(fail, " could not find a valid smallest key... "); |
| } |
| |
| // Printout |
| log("ROOT: " & int2str(rb_Tree.root)); |
| for (j := 0; j <= rb_Tree.nodesCurMaxIndex; j:=j+1) { |
| log("Index: " & int2str(j)); |
| log("Key: " & float2str(rb_Tree.floatKeyData[j].key)); |
| |
| if (rb_Tree.nodes[j].color == red) { |
| s := "RED"; |
| } else if (rb_Tree.nodes[j].color == black){ |
| s := "BLACK"; |
| } else { |
| s := "UNUSED"; |
| } |
| log("Color: " & s); |
| log("Parent: " & int2str(rb_Tree.nodes[j].parent)); |
| log("Left: " & int2str(rb_Tree.nodes[j].left)); |
| log("Right: " & int2str(rb_Tree.nodes[j].right)); |
| log("-----------------"); |
| } // for |
| |
| log("DEBUG: Deletes node with key value '40.0'..."); |
| f_EPTF_RBTreeF_removeFloatNode(rb_Tree, 6, true); |
| |
| log("DEBUG: Deletes node with key value '25.0'..."); |
| f_EPTF_RBTreeF_removeFloatNode(rb_Tree, 5, true); |
| |
| // Printout |
| log("ROOT: " & int2str(rb_Tree.root)); |
| for (j := 0; j <= rb_Tree.nodesCurMaxIndex; j:=j+1) { |
| log("Index: " & int2str(j)); |
| log("Key: " & float2str(rb_Tree.floatKeyData[j].key)); |
| |
| if (rb_Tree.nodes[j].color == red) { |
| s := "RED"; |
| } else if (rb_Tree.nodes[j].color == black){ |
| s := "BLACK"; |
| } else { |
| s := "UNUSED"; |
| } |
| log("Color: " & s); |
| log("Parent: " & int2str(rb_Tree.nodes[j].parent)); |
| log("Left: " & int2str(rb_Tree.nodes[j].left)); |
| log("Right: " & int2str(rb_Tree.nodes[j].right)); |
| log("-----------------"); |
| } // for |
| |
| if (f_EPTF_RBTreeF_getSmallestNodeFromCache(rb_Tree, smallestNode)) { |
| log("Smallest key: " & float2str(smallestNode.key)); |
| log(" ^^^^^^^^^^^^^^^^^^^^^^^^ "); |
| if (smallestNode.key == 50.0) {setverdict(pass);} else {setverdict(fail, log2str("smallestNode.key should be 50.0, but it is: ", smallestNode.key));} |
| } else { |
| setverdict(fail, "could not find a valid smallest key"); |
| } |
| //Log_RBTree("Final", rb_Tree); |
| |
| } //testcase tc_findSmallest() |
| |
| testcase tc_getFloatNodeByKey() runs on PCOComp system PCOComp { |
| |
| var EPTF_Float_RedBlackTree rb_Tree; |
| var integer I; |
| var charstring s; |
| var EPTF_IntegerList data; |
| var EPTF_FloatNode node; |
| var integer l_index; |
| var boolean result; |
| |
| // Init |
| f_EPTF_RBTreeF_initFloatTree(rb_Tree); |
| |
| log("-----------------Add four elements----------------------"); |
| // Add element 1 |
| data := {1}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 1.0, data); |
| //Log_RBTree("Added_"& int2str(I), rb_Tree); |
| |
| // Add element 2 |
| data := {2}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 2.0, data); |
| //Log_RBTree("Added_"& int2str(I), rb_Tree); |
| |
| // Add element 3 |
| data := {3}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 3.0, data); |
| //Log_RBTree("Added_"& int2str(I), rb_Tree); |
| |
| data := {4}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 4.0, data); |
| //Log_RBTree("Added_"& int2str(I), rb_Tree); |
| |
| log("Before removal ",rb_Tree); |
| log("-----------------removing element with key 1.0----------------------"); |
| result := f_EPTF_RBTreeF_getFloatNodeByKey(rb_Tree, 1.0, node, l_index); |
| log("Found index: ", l_index); |
| log("smallestKeyindex: ",rb_Tree.smallestKeyIndex); |
| f_EPTF_RBTreeF_removeFloatNode(rb_Tree, l_index, true); |
| log("After removal ",rb_Tree); |
| |
| log("-----------------Add one new element----------------------"); |
| data := {5}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 5.0, data); |
| //Log_RBTree("Added_"& int2str(I), rb_Tree); |
| |
| log("Before removal ",rb_Tree); |
| log("-----------------removing element with key 2.0----------------------"); |
| result := f_EPTF_RBTreeF_getFloatNodeByKey(rb_Tree, 2.0, node, l_index); |
| log("Found index: ", l_index); |
| f_EPTF_RBTreeF_removeFloatNode(rb_Tree, l_index, true); |
| log("After removal ",rb_Tree); |
| |
| log("-----------------Add one new element----------------------"); |
| log("Add node... "); |
| data := {2}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 6.0, data); |
| //Log_RBTree("Added_"& int2str(I), rb_Tree); |
| |
| // Printout |
| var EPTF_Float_RedBlackTree mytree := { |
| nodes := { |
| { color := black, left := 0, right := 0, parent := 4, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := true }, |
| { color := black, left := 5, right := 0, parent := 0, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := true }, |
| { color := black, left := 0, right := 3, parent := 5, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := red, left := 0, right := 0, parent := 2, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := black, left := 0, right := 0, parent := 5, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := black, left := 4, right := 2, parent := 1, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false } }, |
| floatKeyData := { |
| { key := 0.000000, data := { } }, |
| { key := 0.000000, data := { } }, |
| { key := 5.000000, data := { 5 } }, |
| { key := 6.000000, data := { 2 } }, |
| { key := 3.000000, data := { 3 } }, |
| { key := 4.000000, data := { 4 } } }, |
| nodesCurMaxIndex := 5, |
| root := 1, |
| nil := 0, |
| freeHead := -1, |
| freeTail := -1, |
| smallestKeyIndex := 2, |
| isSmallestCacheValid := false, |
| nOfElements := 4, |
| acceptableMaxSize := -1 |
| } |
| |
| f_checkTree(rb_Tree,mytree); |
| |
| log("-----------------removing element with key 3.0----------------------"); |
| result := f_EPTF_RBTreeF_getFloatNodeByKey(rb_Tree, 3.0, node, l_index); |
| log("Found index: ", l_index); |
| f_EPTF_RBTreeF_removeFloatNode(rb_Tree, l_index, true); |
| log("After removal ",rb_Tree); |
| |
| mytree := { |
| nodes := { |
| { color := black, left := 0, right := 0, parent := 5, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := true }, |
| { color := black, left := 2, right := 0, parent := 0, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := true }, |
| { color := black, left := 5, right := 3, parent := 1, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := black, left := 0, right := 0, parent := 2, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := unused, left := -1, right := -1, parent := 5, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := black, left := 0, right := 0, parent := 2, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false } }, |
| floatKeyData := { |
| { key := 0.000000, data := { } }, |
| { key := 0.000000, data := { } }, |
| { key := 5.000000, data := { 5 } }, |
| { key := 6.000000, data := { 2 } }, |
| { key := 3.000000, data := { 3 } }, |
| { key := 4.000000, data := { 4 } } }, |
| nodesCurMaxIndex := 5, |
| root := 1, |
| nil := 0, |
| freeHead := 4, |
| freeTail := 4, |
| smallestKeyIndex := 2, |
| isSmallestCacheValid := false, |
| nOfElements := 3, |
| acceptableMaxSize := -1 |
| } |
| |
| f_checkTree(rb_Tree,mytree); |
| |
| result := f_EPTF_RBTreeF_getFloatNodeByKey(rb_Tree, 4.0, node, l_index); |
| log("Found index: ", l_index); |
| log("result: ", result); |
| } |
| |
| testcase tc_add_remove() runs on PCOComp system PCOComp { |
| |
| var EPTF_Float_RedBlackTree rb_Tree; |
| var integer I; |
| var charstring s; |
| var EPTF_IntegerList data; |
| var boolean success; |
| |
| // Init |
| f_EPTF_RBTreeF_initFloatTree(rb_Tree); |
| |
| log("Creating first node..."); |
| data := {2}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 1.0, data); |
| |
| log("Invalidating first node..."); |
| f_EPTF_RBTreeF_removeFloatNode(rb_Tree, 2, false); |
| |
| data := {5}; |
| log("Creating second node..."); |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 2.0, data); |
| |
| // Printout |
| var EPTF_Float_RedBlackTree mytree := { |
| nodes := { |
| { color := black, left := 0, right := 0, parent := 1, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := true }, |
| { color := black, left := 3, right := 0, parent := 0, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := true }, |
| { color := invalid, left := 0, right := 0, parent := 1, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := black, left := 0, right := 0, parent := 1, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false } }, |
| floatKeyData := { |
| { key := 0.000000, data := { } }, |
| { key := 0.000000, data := { } }, |
| { key := 1.000000, data := { 2 } }, |
| { key := 2.000000, data := { 5 } } }, |
| nodesCurMaxIndex := 3, |
| root := 1, |
| nil := 0, |
| freeHead := -1, |
| freeTail := -1, |
| smallestKeyIndex := 2, |
| isSmallestCacheValid := false, |
| nOfElements := 1, |
| acceptableMaxSize := -1 |
| } |
| |
| f_checkTree(rb_Tree,mytree); |
| |
| log("Removing first node..."); |
| success := f_EPTF_RBTreeF_destroyInvalidFloatNode(rb_Tree, 2); |
| |
| // Printout |
| mytree := { |
| nodes := { |
| { color := black, left := 0, right := 0, parent := 1, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := true }, |
| { color := black, left := 3, right := 0, parent := 0, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := true }, |
| { color := unused, left := -1, right := -1, parent := 1, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := black, left := 0, right := 0, parent := 1, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false } }, |
| floatKeyData := { |
| { key := 0.000000, data := { } }, |
| { key := 0.000000, data := { } }, |
| { key := 1.000000, data := { 2 } }, |
| { key := 2.000000, data := { 5 } } }, |
| nodesCurMaxIndex := 3, |
| root := 1, |
| nil := 0, |
| freeHead := 2, |
| freeTail := 2, |
| smallestKeyIndex := 2, |
| isSmallestCacheValid := false, |
| nOfElements := 1, |
| acceptableMaxSize := -1 |
| } |
| |
| f_checkTree(rb_Tree,mytree); |
| |
| log("Invalidating the only valid node..."); |
| f_EPTF_RBTreeF_removeFloatNode(rb_Tree, 3, false); |
| |
| log("Creating new node..."); |
| data := {2}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 1.0, data); |
| |
| log("Removing just invalidated node..."); |
| success := f_EPTF_RBTreeF_destroyInvalidFloatNode(rb_Tree, 3); |
| |
| // Printout |
| mytree := { |
| nodes := { |
| { color := black, left := 0, right := 0, parent := 1, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := true }, |
| { color := black, left := 2, right := 0, parent := 0, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := true }, |
| { color := black, left := 0, right := 0, parent := 1, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := unused, left := -1, right := -1, parent := 1, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false } }, |
| floatKeyData := { |
| { key := 0.000000, data := { } }, |
| { key := 0.000000, data := { } }, |
| { key := 1.000000, data := { 2 } }, |
| { key := 2.000000, data := { 5 } } }, |
| nodesCurMaxIndex := 3, |
| root := 1, |
| nil := 0, |
| freeHead := 3, |
| freeTail := 3, |
| smallestKeyIndex := 2, |
| isSmallestCacheValid := false, |
| nOfElements := 1, |
| acceptableMaxSize := -1 |
| } |
| |
| f_checkTree(rb_Tree,mytree); |
| |
| log("Invalidating the only valid node..."); |
| f_EPTF_RBTreeF_removeFloatNode(rb_Tree, 2, false); |
| |
| log("Creating new node..."); |
| data := {5}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 2.0, data); |
| |
| log("Removing node with index 3 (invalid already)"); |
| success := f_EPTF_RBTreeF_destroyInvalidFloatNode(rb_Tree, 2); |
| |
| log("Invalidating the only valid node..."); |
| f_EPTF_RBTreeF_removeFloatNode(rb_Tree, 3, false); |
| |
| // Printout |
| mytree := { |
| nodes := { |
| { color := black, left := 0, right := 0, parent := 1, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := true }, |
| { color := black, left := 0, right := 0, parent := 0, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := true }, |
| { color := unused, left := -1, right := -1, parent := 1, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := invalid, left := 0, right := 0, parent := 1, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false } }, |
| floatKeyData := { |
| { key := 0.000000, data := { } }, |
| { key := 0.000000, data := { } }, |
| { key := 1.000000, data := { 2 } }, |
| { key := 2.000000, data := { 5 } } }, |
| nodesCurMaxIndex := 3, |
| root := 1, |
| nil := 0, |
| freeHead := 2, |
| freeTail := 2, |
| smallestKeyIndex := 2, |
| isSmallestCacheValid := false, |
| nOfElements := 0, |
| acceptableMaxSize := -1 |
| } |
| |
| f_checkTree(rb_Tree,mytree); |
| |
| log("Creating new node..."); |
| data := {2}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 1.0, data); |
| |
| log("Removing node with index 3"); |
| success := f_EPTF_RBTreeF_destroyInvalidFloatNode(rb_Tree, 3); |
| |
| log("Invalidating the only valid node..."); |
| f_EPTF_RBTreeF_removeFloatNode(rb_Tree, 2, false); |
| |
| log("Creating new node..."); |
| data := {5}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 5.0, data); |
| |
| // Printout |
| mytree := { |
| nodes := { |
| { color := black, left := 0, right := 0, parent := 1, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := true }, |
| { color := black, left := 3, right := 0, parent := 0, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := true }, |
| { color := invalid, left := 0, right := 0, parent := 1, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := black, left := 0, right := 0, parent := 1, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false } }, |
| floatKeyData := { |
| { key := 0.000000, data := { } }, |
| { key := 0.000000, data := { } }, |
| { key := 1.000000, data := { 2 } }, |
| { key := 5.000000, data := { 5 } } }, |
| nodesCurMaxIndex := 3, |
| root := 1, |
| nil := 0, |
| freeHead := -1, |
| freeTail := -1, |
| smallestKeyIndex := 2, |
| isSmallestCacheValid := false, |
| nOfElements := 1, |
| acceptableMaxSize := -1 |
| } |
| |
| f_checkTree(rb_Tree,mytree); |
| |
| log("Removing node with index 2"); |
| success := f_EPTF_RBTreeF_destroyInvalidFloatNode(rb_Tree, 2); |
| |
| log("Creating new node..."); |
| data := {8}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 8.0, data); |
| |
| mytree := { |
| nodes := { |
| { color := black, left := 0, right := 0, parent := 1, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := true }, |
| { color := black, left := 3, right := 0, parent := 0, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := true }, |
| { color := red, left := 0, right := 0, parent := 3, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := black, left := 0, right := 2, parent := 1, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false } }, |
| floatKeyData := { |
| { key := 0.000000, data := { } }, |
| { key := 0.000000, data := { } }, |
| { key := 8.000000, data := { 8 } }, |
| { key := 5.000000, data := { 5 } } }, |
| nodesCurMaxIndex := 3, |
| root := 1, |
| nil := 0, |
| freeHead := -1, |
| freeTail := -1, |
| smallestKeyIndex := 2, |
| isSmallestCacheValid := false, |
| nOfElements := 2, |
| acceptableMaxSize := -1 |
| } |
| |
| f_checkTree(rb_Tree,mytree); |
| |
| log("Invalidating the node with index 3..."); |
| f_EPTF_RBTreeF_removeFloatNode(rb_Tree, 3, false); |
| |
| log("Creating new node..."); |
| data := {3}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 3.0, data); |
| |
| // Printout |
| mytree := { |
| nodes := { |
| { color := black, left := 0, right := 0, parent := 1, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := true }, |
| { color := black, left := 2, right := 0, parent := 0, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := true }, |
| { color := black, left := 4, right := 0, parent := 1, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := invalid, left := 0, right := 2, parent := 1, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := red, left := 0, right := 0, parent := 2, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false } }, |
| floatKeyData := { |
| { key := 0.000000, data := { } }, |
| { key := 0.000000, data := { } }, |
| { key := 8.000000, data := { 8 } }, |
| { key := 5.000000, data := { 5 } }, |
| { key := 3.000000, data := { 3 } } }, |
| nodesCurMaxIndex := 4, |
| root := 1, |
| nil := 0, |
| freeHead := -1, |
| freeTail := -1, |
| smallestKeyIndex := 2, |
| isSmallestCacheValid := false, |
| nOfElements := 2, |
| acceptableMaxSize := -1 |
| } |
| |
| f_checkTree(rb_Tree,mytree); |
| |
| log("Removing node with index 3"); |
| success := f_EPTF_RBTreeF_destroyInvalidFloatNode(rb_Tree, 3); |
| log("After removal rb_Tree= ", rb_Tree); |
| } |
| |
| testcase tc_use_duplicate_keys() runs on PCOComp system PCOComp { |
| |
| var EPTF_Float_RedBlackTree rb_Tree; |
| var integer I; |
| var charstring s; |
| var EPTF_IntegerList data; |
| |
| // Init |
| f_EPTF_RBTreeF_initFloatTree(rb_Tree); |
| |
| // Add 8 elements |
| data := {}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 1.0, data); |
| //Log_RBTree("Added_"& int2str(I), rb_Tree); |
| data := {}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 6.0, data); |
| //Log_RBTree("Added_"& int2str(I), rb_Tree); |
| data := {}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 25.0, data); |
| //Log_RBTree("Added_"& int2str(I), rb_Tree); |
| data := {}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 11.0, data); |
| //Log_RBTree("Added_"& int2str(I), rb_Tree); |
| data := {}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 25.0, data); |
| //Log_RBTree("Added_"& int2str(I), rb_Tree); |
| data := {}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 27.0, data); |
| //Log_RBTree("Added_"& int2str(I), rb_Tree); |
| data := {}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 25.0, data); |
| //Log_RBTree("Added_"& int2str(I), rb_Tree); |
| data := {}; |
| I := f_EPTF_RBTreeF_createNewFloatNode(rb_Tree, 7.0, data); |
| //Log_RBTree("Added_"& int2str(I), rb_Tree); |
| log("DEBUG: Insertions done..."); |
| |
| var EPTF_Float_RedBlackTree mytree := { |
| nodes := { |
| { color := black, left := 0, right := 0, parent := 0, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := true }, |
| { color := black, left := 3, right := 0, parent := 0, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := true }, |
| { color := black, left := 0, right := 0, parent := 3, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := black, left := 2, right := 4, parent := 1, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := red, left := 5, right := 7, parent := 3, fwd := 6, bwd := -1, isHeadInSameKeysCluster := true, isSentinel := false }, |
| { color := black, left := 9, right := 0, parent := 4, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := incluster, left := 0, right := 0, parent := 0, fwd := 8, bwd := 4, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := black, left := 0, right := 0, parent := 4, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := incluster, left := 0, right := 0, parent := 0, fwd := -1, bwd := 6, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := red, left := 0, right := 0, parent := 5, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false } }, |
| floatKeyData := { |
| { key := 0.000000, data := { } }, |
| { key := 0.000000, data := { } }, |
| { key := 1.000000, data := { } }, |
| { key := 6.000000, data := { } }, |
| { key := 25.000000, data := { } }, |
| { key := 11.000000, data := { } }, |
| { key := 25.000000, data := { } }, |
| { key := 27.000000, data := { } }, |
| { key := 25.000000, data := { } }, |
| { key := 7.000000, data := { } } }, |
| nodesCurMaxIndex := 9, |
| root := 1, |
| nil := 0, |
| freeHead := -1, |
| freeTail := -1, |
| smallestKeyIndex := 2, |
| isSmallestCacheValid := true, |
| nOfElements := 8, |
| acceptableMaxSize := -1 |
| } |
| |
| f_checkTree(rb_Tree, mytree); |
| |
| f_EPTF_RBTreeF_removeFloatNode(rb_Tree, 4, true); //middle of cluster |
| |
| mytree := { |
| nodes := { |
| { color := black, left := 0, right := 0, parent := 0, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := true }, |
| { color := black, left := 3, right := 0, parent := 0, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := true }, |
| { color := black, left := 0, right := 0, parent := 3, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := black, left := 2, right := 6, parent := 1, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := unused, left := -1, right := -1, parent := 3, fwd := 6, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := black, left := 9, right := 0, parent := 6, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := red, left := 5, right := 7, parent := 3, fwd := 8, bwd := -1, isHeadInSameKeysCluster := true, isSentinel := false }, |
| { color := black, left := 0, right := 0, parent := 6, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := incluster, left := 0, right := 0, parent := 0, fwd := -1, bwd := 6, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := red, left := 0, right := 0, parent := 5, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false } }, |
| floatKeyData := { |
| { key := 0.000000, data := { } }, |
| { key := 0.000000, data := { } }, |
| { key := 1.000000, data := { } }, |
| { key := 6.000000, data := { } }, |
| { key := 25.000000, data := { } }, |
| { key := 11.000000, data := { } }, |
| { key := 25.000000, data := { } }, |
| { key := 27.000000, data := { } }, |
| { key := 25.000000, data := { } }, |
| { key := 7.000000, data := { } } }, |
| nodesCurMaxIndex := 9, |
| root := 1, |
| nil := 0, |
| freeHead := 4, |
| freeTail := 4, |
| smallestKeyIndex := 2, |
| isSmallestCacheValid := true, |
| nOfElements := 7, |
| acceptableMaxSize := -1 |
| } |
| |
| f_checkTree(rb_Tree, mytree); |
| |
| f_EPTF_RBTreeF_removeFloatNode(rb_Tree, 6, true); //head of cluster |
| //Log_RBTree("Removed_6", rb_Tree); |
| |
| mytree := { |
| nodes := { |
| { color := black, left := 0, right := 0, parent := 0, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := true }, |
| { color := black, left := 3, right := 0, parent := 0, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := true }, |
| { color := black, left := 0, right := 0, parent := 3, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := black, left := 2, right := 8, parent := 1, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := unused, left := -1, right := 6, parent := 3, fwd := 6, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := black, left := 9, right := 0, parent := 8, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := unused, left := 4, right := -1, parent := 3, fwd := 8, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := black, left := 0, right := 0, parent := 8, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := red, left := 5, right := 7, parent := 3, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false }, |
| { color := red, left := 0, right := 0, parent := 5, fwd := -1, bwd := -1, isHeadInSameKeysCluster := false, isSentinel := false } }, |
| floatKeyData := { |
| { key := 0.000000, data := { } }, |
| { key := 0.000000, data := { } }, |
| { key := 1.000000, data := { } }, |
| { key := 6.000000, data := { } }, |
| { key := 25.000000, data := { } }, |
| { key := 11.000000, data := { } }, |
| { key := 25.000000, data := { } }, |
| { key := 27.000000, data := { } }, |
| { key := 25.000000, data := { } }, |
| { key := 7.000000, data := { } } }, |
| nodesCurMaxIndex := 9, |
| root := 1, |
| nil := 0, |
| freeHead := 4, |
| freeTail := 6, |
| smallestKeyIndex := 2, |
| isSmallestCacheValid := true, |
| nOfElements := 6, |
| acceptableMaxSize := -1 |
| } |
| |
| f_checkTree(rb_Tree, mytree); |
| //Log_RBTree("Final", rb_Tree); |
| |
| } //tc_use_duplicate_keys() |
| |
| } // group RBT_Obsolete |
| |
| control{ |
| /* execute(tc_add_10_elements()); |
| execute(tc_removeElement()); |
| execute(tc_remove_4_elements()); |
| execute(tc_findSmallestIndex()); |
| execute(tc_findSmallest()); |
| execute(tc_getFloatNodeByKey()); |
| execute(tc_add_remove()); |
| execute(tc_use_duplicate_keys());*/ |
| execute(tc_insertItems()); |
| execute(tc_sortStrings()); |
| } |
| |
| |
| } //module |
