blob: 3ae26ac1f87c72c5af37323260cbd65a96316bd5 [file] [log] [blame]
///////////////////////////////////////////////////////////////////////////////
// //
// 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