src/RedBlackTree/EPTF_CLL_RBtreeInteger_PrivateFunctions.ttcn

///////////////////////////////////////////////////////////////////////////////
//                                                                           //
// 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_CLL_RBtreeInteger_PrivateFunctions
// 
//  Purpose:
//    This module contains private functions for TTCN-3 integer Red-Black tree implementation.
//    These functions are not to be used by the user, only by other functions.
// 
//  Module depends on:
//    <EPTF_CLL_Common_Definitions>
//    <EPTF_CLL_Common_Functions>
//    <EPTF_CLL_RBtree_Definitions>
//    <EPTF_CLL_RBtree_PrivateFunctions>
// 
//  Current Owner:
//    Rita Kovacs (ERITKOV)
// 
//  Last Review Date:
//    2007-12-06
///////////////////////////////////////////////////////////////

module EPTF_CLL_RBtreeInteger_PrivateFunctions {

import from EPTF_CLL_Common_Definitions all;
import from EPTF_CLL_Common_Functions all;
import from EPTF_CLL_RBtree_Definitions all;
import from EPTF_CLL_RBtree_PrivateFunctions all;

friend module EPTF_CLL_RBtreeInteger_Functions;


///////////////////////////////////////////////////////////
// Function: f_EPTF_RBTreeI_getIntegerElementIndexByKey
// 
// Purpose:
//   Function to get the given integer-identified event (node) from the tree.
// 
// Parameters:
//   pl_tree - *inout* <EPTF_Integer_RedBlackTree> - the up-to-date integer red-black-tree itself
//   pl_key - *in* *integer* - node to get
//   pl_indexFound - *out* *integer* - index of the tree node of the given key
// 
// Return Value:
//   boolean - success
///////////////////////////////////////////////////////////

friend function f_EPTF_RBTreeI_getIntegerElementIndexByKey(inout EPTF_Integer_RedBlackTree pl_tree, in integer pl_key, out integer pl_indexFound) return boolean {
    var boolean vl_isFound := false;
    var integer root := pl_tree.nodes[pl_tree.root].left; // the real root of the tree
    var integer nil := pl_tree.nil;

    var integer vl_x := root;
    while (vl_x != nil and not vl_isFound) {
	    if (pl_tree.integerKeyData[vl_x].key == pl_key) {
		    vl_isFound := true;
		    pl_indexFound := vl_x;
	            //log("DEBUG: [f_EPTF_RBTreeI_getIntegerElementIndexByKey] pl_indexFound: ",pl_indexFound);
	    } else {
		    if (pl_key < pl_tree.integerKeyData[vl_x].key) {
			    // we go forward to left
			    vl_x := pl_tree.nodes[vl_x].left;
		    } else {
			    // we go forward to right
			    vl_x := pl_tree.nodes[vl_x].right;
		    }
	    } // else
    } // while

    //log("DEBUG: [f_EPTF_RBTreeI_getIntegerElementIndexByKey] vl_isFound: ", vl_isFound);
    return vl_isFound;
} // f_EPTF_RBTreeI_getIntegerElementIndexByKey

///////////////////////////////////////////////////////////
// Function: f_EPTF_RBTreeI_insertIntegerNodeWithSameKey
// 
// Purpose:
//   Function to insert the given integer-identified event (node) to cluster chain.
// 
// Parameters:
//   pl_tree - *inout* <EPTF_Integer_RedBlackTree> - the up-to-date integer red-black-tree itself
//   pl_newNodeIndex - *in* *integer* - index of the integer tree node to insert
// 
// Return Value:
//   boolean - success
///////////////////////////////////////////////////////////

private function f_EPTF_RBTreeI_insertIntegerNodeWithSameKey(inout EPTF_Integer_RedBlackTree pl_tree, in integer pl_newNodeIndex) return boolean {

    var boolean vl_result := false;   
    var integer vl_indexFound := -1;
    if (f_EPTF_RBTreeI_getIntegerElementIndexByKey(pl_tree, pl_tree.integerKeyData[pl_newNodeIndex].key, vl_indexFound)) {
        vl_result := true;  
        f_EPTF_RBTree_insertNodeWithSameKey(pl_tree.nodes, pl_newNodeIndex, vl_indexFound);                               
    }   
    return vl_result;
}

///////////////////////////////////////////////////////////
// Function: f_EPTF_RBTreeI_insertInteger
// 
// Purpose:
//   Function to insert the given integer-identified event (node) to the tree.
// 
// Parameters:
//   pl_tree - *inout* <EPTF_Integer_RedBlackTree> - the up-to-date integer red-black-tree itself
//   pl_x - *in* *integer* - index of the integer tree node to insert
// 
// Return Value:
//   boolean - success
///////////////////////////////////////////////////////////

friend function f_EPTF_RBTreeI_insertInteger(inout EPTF_Integer_RedBlackTree pl_tree, in integer pl_x) {

    // Storing number of elements
    pl_tree.nOfElements := pl_tree.nOfElements + 1;
  
    // If the same key is exists, we append this node to a cluster
    // and not to the tree.
    if (f_EPTF_RBTreeI_insertIntegerNodeWithSameKey(pl_tree, pl_x)) {
        return;
    }
	
    f_EPTF_RBTreeI_helpIntegerTreeInsert(pl_tree, pl_x);
    f_EPTF_RBTree_RBTreeInsert(pl_tree.nodes, pl_tree.root, pl_tree.nil, pl_x);

    f_EPTF_RBTreeI_checkMaxSize(%definitionId, pl_tree);
}

///////////////////////////////////////////////////////////
// Function: f_EPTF_RBTreeI_helpIntegerTreeInsert
// 
// Purpose:
//   Inserts z into the tree as if it were a regular binary tree using the algorithm described 
//   in _Introduction_To_Algorithms_ by Cormen et al. This function is only intended to be called
//   by the <f_EPTF_RBTree_RBTreeInsert> function and not by the user.
// 
// Parameters:
//   pl_tree - *inout* <EPTF_Integer_RedBlackTree> - the up-to-date integer red-black-tree itself
//   pl_z - *in* *integer* - index of the integer tree node to insert
// 
// Return Value:
//   (none)
///////////////////////////////////////////////////////////
private function f_EPTF_RBTreeI_helpIntegerTreeInsert(inout EPTF_Integer_RedBlackTree pl_tree, in integer pl_z) {
    var integer x := pl_tree.nodes[pl_tree.root].left; // real root node of the tree
    var integer y := pl_tree.root; // sentinel
    var integer nil := pl_tree.nil;

    // !!! ? These are not neccessary, because left and right already set during
    //       node creation -> CHECK !!!
    pl_tree.nodes[pl_z].left  := nil;
    pl_tree.nodes[pl_z].right := nil;

    while (x != nil) {
	y := x;
        if (pl_tree.integerKeyData[x].key > pl_tree.integerKeyData[pl_z].key) { 
                x := pl_tree.nodes[x].left; 
            } else { 
                x := pl_tree.nodes[x].right; 
            }
    } // while

    pl_tree.nodes[pl_z].parent := y;

    if ( (y == pl_tree.root) or
         (pl_tree.integerKeyData[y].key > pl_tree.integerKeyData[pl_z].key) ) {
	    pl_tree.nodes[y].left := pl_z;
         } else { 
            pl_tree.nodes[y].right := pl_z;
         }
} //  f_EPTF_RBTreeI_helpIntegerTreeInsert


///////////////////////////////////////////////////////////
// Function: f_EPTF_RBTreeI_getFreeSlotInteger
// 
// Purpose:
//      search for a free (unused or new) slot in integer tree
// 
// Parameters:
//   pl_tree - *inout* <EPTF_Integer_RedBlackTree> - the up-to-date integer red-black-tree
// 
// Return Value:
//   integer - leaf integer node's index
///////////////////////////////////////////////////////////

friend function f_EPTF_RBTreeI_getFreeSlotInteger(inout EPTF_Integer_RedBlackTree pl_tree) return integer {
	return f_EPTF_RBTree_getFreeSlot(
		pl_tree.nodes,
		pl_tree.freeHead,
		pl_tree.freeTail,
		pl_tree.nodesCurMaxIndex
	);
}

///////////////////////////////////////////////////////////
// Function: f_EPTF_RBTreeI_destroyIntegerNode
// 
// Purpose:
//      deletes node from integer tree
// 
// Parameters:
//   pl_tree - *inout* <EPTF_Integer_RedBlackTree> - the up-to-date integer red-black-tree
//   pl_z - *in* *integer* - index of the integer tree node to delete
// 
// Return Value:
//   (none)
///////////////////////////////////////////////////////////

friend function f_EPTF_RBTreeI_destroyIntegerNode(inout EPTF_Integer_RedBlackTree pl_tree, in integer pl_z) {
	f_EPTF_RBTree_destroyNode(pl_tree.nodes, pl_tree.freeHead, pl_tree.freeTail, pl_z);
}

///////////////////////////////////////////////////////////
// Function: f_EPTF_RBTreeI_invalidateIntegerNode
// 
// Purpose:
//      sets node of the given index (pl_z) invalid 
// 
// Parameters:
//   pl_tree - *inout* <EPTF_Integer_RedBlackTree> - the up-to-date integer red-black-tree itself
//   pl_z - *in* *integer* - index of the integer tree node to invalidate
// 
// Return Value:
//   (none)
///////////////////////////////////////////////////////////

friend function f_EPTF_RBTreeI_invalidateIntegerNode(inout EPTF_Integer_RedBlackTree pl_tree, in integer pl_z) {
	f_EPTF_RBTree_invalidateNode(pl_tree.nodes, pl_z);
}

///////////////////////////////////////////////////////////
// Function: f_EPTF_RBTreeI_getSmallestIntegerElementIndexFromCache
// 
// Purpose:
//      Gets smallest keyed integer node index from cache.
//      Refreshes cache if invalid.
// 
// Parameters:
//   pl_tree - *inout* <EPTF_Integer_RedBlackTree> - the up-to-date integer red-black-tree itself
//   pl_idx - *inout* *integer* - smallest key index
// 
// Return Value:
//   boolean - success
///////////////////////////////////////////////////////////

friend function f_EPTF_RBTreeI_getSmallestIntegerElementIndexFromCache(in EPTF_Integer_RedBlackTree pl_tree, inout integer pl_idx) return boolean {
    var integer root := pl_tree.nodes[pl_tree.root].left;

    var boolean vl_result := false;
    if (root == pl_tree.nil) {
        // The tree is empty.
        pl_idx := -1;
        return false;
    }
    
    // If the cache is valid...
    if (pl_tree.isSmallestCacheValid) {
        pl_idx := pl_tree.smallestKeyIndex;
        vl_result := true;
    } else {
        // We have to search and refresh the cache
        pl_idx := f_EPTF_RBTreeI_searchSmallestNodeIndex(pl_tree);
        vl_result := true;
    }   
    return vl_result;
} 

///////////////////////////////////////////////////////////
// Function: f_EPTF_RBTreeI_searchSmallestNodeIndex
// 
// Purpose:
//      Searches for smallest key node in integer tree.
//      Also refreshes smallest key cache if found.
// 
// Parameters:
//   pl_tree - *inout* <EPTF_Integer_RedBlackTree> - the up-to-date integer red-black-tree
//
// Return Value:
//   integer - smallest key index.
//               Returns -1 if the tree is empty.
///////////////////////////////////////////////////////////

friend function f_EPTF_RBTreeI_searchSmallestNodeIndex(in EPTF_Integer_RedBlackTree pl_tree) return integer {  

    var integer nil := pl_tree.nil;
    var integer root := pl_tree.nodes[pl_tree.root].left;


    if (root == nil) {
       // Tree is empty... EXIT
       return -1;
    }

    var integer x := root;
    while (pl_tree.nodes[x].left != nil) {
        x := pl_tree.nodes[x].left;
    } // while

    //pl_tree.smallestKeyIndex := x;
    //pl_tree.isSmallestCacheValid := true;    

    return x;

/* Previous solution. The new (above) might be faster: has less if operation.
    var integer vl_x := pl_tree.root.left;
    while (vl_x != nil and not vl_isFound) {
	    if (pl_tree.nodes[vl_x].left == nil) {
		    // no more left child -> end of the tree
		    // refreshing cache
		    pl_tree.smallestKeyIndex := vl_x;
		    pl_tree.isSmallestCacheValid := true;
		    vl_isFound := true;
	    } else {
		    // go forward to left
		    vl_x := pl_tree.nodes[vl_x].left;
	    }
    } // while  

  return vl_x;

*/



}

///////////////////////////////////////////////////////////
// Function: f_EPTF_RBTreeI_checkMaxSize
//
// Purpose:
//  Function to check if the size of the tree exceeds a certain limit.
//
// Parameters:
//   pl_caller - *in* *charstring* - caller function, use %definitionId when calling
//   pl_tree - *inout* <EPTF_Integer_RedBlackTree> - the tree in question
//
// Return Value:
//   -
//
// Detailed Comments:
//  The tree MUST be initialized by calling f_EPTF_RBTreeI_initIntegerTree.
//
///////////////////////////////////////////////////////////
private function f_EPTF_RBTreeI_checkMaxSize(in charstring pl_caller, inout EPTF_Integer_RedBlackTree pl_tree)
{
  if(c_EPTF_Common_debugSwitch and pl_tree.acceptableMaxSize >= 0) {
    if(pl_tree.nOfElements > pl_tree.acceptableMaxSize) {
      //EPTF_Logging_debug
      f_EPTF_Common_warning(log2str(pl_caller, ": tree exceeds acceptable max size of ", pl_tree.acceptableMaxSize, " elements."));
        f_EPTF_Common_warning(log2str(pl_caller, ": increasing acceptable max size by a factor of ", tsp_CLL_debug_increasePercentage4AcceptableMaxSize));
      pl_tree.acceptableMaxSize := float2int(int2float(pl_tree.acceptableMaxSize)
        * (1.0+tsp_CLL_debug_increasePercentage4AcceptableMaxSize));
      f_EPTF_Common_warning(log2str(pl_caller, ": new acceptable max size: ", pl_tree.acceptableMaxSize));
    }
  }
}

} //module