///////////////////////////////////////////////////////////////////////////////
//                                                                           //
// 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