src/RedBlackTree/EPTF_CLL_RBtreeInteger_Functions.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_Functions
// 
//  Purpose:
//    This module contains generic functions for TTCN-3 integer Red-Black tree implementation.
// 
//  Module depends on:
//    <EPTF_CLL_RBtree_Functions>
//    <EPTF_CLL_RBtree_Definitions>
//    <EPTF_CLL_RBtreeInteger_PrivateFunctions>
//    <EPTF_CLL_Common_Definitions>
//  Current Owner:
//
//    Rita Kovacs (ERITKOV)
// 
//  Last Review Date:
//    2007-12-06
//
//  Detailed Comments:
//    This module contains constants and functions for integer-keyed event scheduling. 
// 
//    - To register a integer event for the tree, call <f_EPTF_RBTreeI_createNewIntegerNode>.
// 
//    - To remove a registered integer event from the tree, call <f_EPTF_RBTreeI_removeIntegerNode>.
//
//    - To to remove a integer-identified event (node) from a cluster chain, call <f_EPTF_RBTReeI_removeIntegerNodeWithSameKey>.
// 
//    - To initiate a tree of integer-identified elements, call <f_EPTF_RBTreeI_initIntegerTree>.
//
//    - To get integer element by key, call <f_EPTF_RBTreeI_getIntegerElementNodeByKey>.
//
//    - To get smallest integer key element, call <f_EPTF_RBTreeI_searchSmallestIntegerNode>.
//
///////////////////////////////////////////////////////////////

module EPTF_CLL_RBtreeInteger_Functions {

import from EPTF_CLL_RBtree_Definitions all;
import from EPTF_CLL_RBtree_Functions all;
import from EPTF_CLL_RBtree_PrivateFunctions all;
import from EPTF_CLL_RBtreeInteger_PrivateFunctions all;

import from EPTF_CLL_Common_Definitions all;



///////////////////////////////////////////////////////////
// Function: f_EPTF_RBTreeI_createNewIntegerNode
// 
// Purpose:
//   Function to register a integer-identified event (new node) for the tree.
// 
// Parameters:
//   rb_Tree - *inout* <EPTF_Integer_RedBlackTree> - the up-to-date red-black-tree
//   key - *in* *integer* - the node to be registered
//   data - *in* <EPTF_IntegerList> - data field of the node identified by integer key value
// 
// Return Value:
//   integer - the index of the new node in the given Tree
///////////////////////////////////////////////////////////

public function f_EPTF_RBTreeI_createNewIntegerNode(inout EPTF_Integer_RedBlackTree rb_Tree, in integer key, in EPTF_IntegerList data) return integer {

    var integer Result;
    var integer I := f_EPTF_RBTreeI_getFreeSlotInteger(rb_Tree);

    rb_Tree.nodes[I] := c_EPTF_emptyRBTNode;
    rb_Tree.nodes[I].left   := rb_Tree.nil;	
    rb_Tree.nodes[I].right  := rb_Tree.nil;
    rb_Tree.nodes[I].parent := rb_Tree.nil;

    rb_Tree.integerKeyData[I] := {key, data};
    Result := I;

    if (rb_Tree.smallestKeyIndex == -1) {
	    rb_Tree.smallestKeyIndex := I;
	    rb_Tree.isSmallestCacheValid := true;
    } else {
	if ((rb_Tree.isSmallestCacheValid) and (rb_Tree.integerKeyData[rb_Tree.smallestKeyIndex].key > key)) {
		rb_Tree.smallestKeyIndex := I;
	}
    }

    f_EPTF_RBTreeI_insertInteger(rb_Tree, I);
    return Result;
}

///////////////////////////////////////////////////////////
// Function: f_EPTF_RBTReeI_removeIntegerNodeWithSameKey
// 
// Purpose:
//   Function to remove a integer-identified event (node) from a cluster chain.
// 
// Parameters:
//   rb_Tree - *inout* <EPTF_Integer_RedBlackTree> - the up-to-date red-black-tree
//   pl_nodeToDeleteIndex - *in* *integer* - the node to be removed
// 
// Return Value:
//   boolean - value returned by function <f_EPTF_RBTree_removeNodeWithSameKey> ()
///////////////////////////////////////////////////////////

public function f_EPTF_RBTReeI_removeIntegerNodeWithSameKey(inout EPTF_Integer_RedBlackTree rb_Tree, in integer pl_nodeToDeleteIndex) return boolean {
	return f_EPTF_RBTree_removeNodeWithSameKey(rb_Tree.nodes, pl_nodeToDeleteIndex, rb_Tree.root, rb_Tree.nil);
}

///////////////////////////////////////////////////////////
// Function: f_EPTF_RBTreeI_removeIntegerNode
// 
// Purpose:
//      Removes a integer-identified element from the given tree.
//      Also sets the appropriate index pointers...
// 
// Parameters:
//   rb_Tree - *inout* <EPTF_Integer_RedBlackTree> - the up-to-date red-black-tree itself
//   pl_z - *in* *integer* - the integer node'index to be removed
//   pl_destroyNode - *in* *boolean* - If true: the node will be also destroyed and placed into the free nodes list.
//                                  If false: the node will be marked as invalid and will not be placed into the free nodes list.
//               HINT: <f_EPTF_RBTreeI_destroyInvalidIntegerNode> should be called when this node is not needed anymore.
// 
// Return Value:
//   boolean - success
///////////////////////////////////////////////////////////

public function f_EPTF_RBTreeI_removeIntegerNode(inout EPTF_Integer_RedBlackTree rb_Tree, in integer pl_z, in boolean pl_destroyNode) {

    // Storing number of elements
    rb_Tree.nOfElements := rb_Tree.nOfElements - 1;
  
    if (f_EPTF_RBTReeI_removeIntegerNodeWithSameKey(rb_Tree, pl_z)) {
       // The element pl_z was in a cluster (maybe was the head of a cluster) and 
       // it's removal has been handled.
        // The same key (pl_z) further exists in the Tree.

       // We only finish the removal here.		
       if (pl_destroyNode) {
           f_EPTF_RBTreeI_destroyIntegerNode(rb_Tree, pl_z);
       } else {
           f_EPTF_RBTreeI_invalidateIntegerNode(rb_Tree, pl_z);
       }
       // if we are to remove node with smallest key, content of cache shall be invalid from now on
       if (rb_Tree.smallestKeyIndex == pl_z) {
            rb_Tree.isSmallestCacheValid := false;  //PERFORMANCE IMPROVEMENT POSSIBILITY: you can set cache true here after setting 
                                                    //smallestKeyIndex to the new head item of cluster chain, if such item exists!!       
       }

       // EXIT
       return;
    }	

    // if we are to remove node with smallest key, content of cache shall be invalid from now on
    if (rb_Tree.smallestKeyIndex == pl_z) {
    	rb_Tree.isSmallestCacheValid := false;
    }

    f_EPTF_RBTree_removeNode(rb_Tree.nodes, pl_z, rb_Tree.root, rb_Tree.nil);
    if (pl_destroyNode) {		
        f_EPTF_RBTreeI_destroyIntegerNode(rb_Tree, pl_z);
    } else {
        f_EPTF_RBTreeI_invalidateIntegerNode(rb_Tree, pl_z);
    }
} // f_EPTF_RBTreeI_removeIntegerNode

///////////////////////////////////////////////////////////
// Function: f_EPTF_RBTreeI_destroyInvalidIntegerNode
// 
// Purpose:
//      deletes invalid integer node
// 
// Parameters:
//   pl_tree - *inout* <EPTF_Integer_RedBlackTree> - the up-to-date integer red-black-tree
//   pl_z - *in* *integer* - index of the invalid integer tree node to delete
// 
// Return Value:
//   boolean - success
///////////////////////////////////////////////////////////
public function f_EPTF_RBTreeI_destroyInvalidIntegerNode(inout EPTF_Integer_RedBlackTree pl_tree, in integer pl_z) return boolean {
	return f_EPTF_RBTree_destroyInvalidNode(pl_tree.nodes, pl_tree.freeHead, pl_tree.freeTail, pl_z);
}

///////////////////////////////////////////////////////////
// Function: f_EPTF_RBTreeI_initIntegerTree
// 
// Purpose:
//      Initiates a tree of integer-identified elements.
//      Also initiates the appropriate index pointers...
// 
// Parameters:
//   rb_Tree - *inout* <EPTF_Integer_RedBlackTree> - the red-black-tree to init
// 
// Return Value:
//   (none)
///////////////////////////////////////////////////////////

public function f_EPTF_RBTreeI_initIntegerTree(inout EPTF_Integer_RedBlackTree rb_Tree){
    rb_Tree.nodes := {};
    rb_Tree.integerKeyData := {};
    rb_Tree.nodesCurMaxIndex := -1;
    rb_Tree.freeHead := -1;
    rb_Tree.freeTail := -1;
    rb_Tree.smallestKeyIndex := -1;
    rb_Tree.isSmallestCacheValid := false;
    rb_Tree.nOfElements := 0;
    rb_Tree.acceptableMaxSize := tsp_CLL_debug_acceptableMaxSizeOfGrowingVariables;

    // creating sentinel objects...
    //     ...leaf (nil)
    var integer newSentinel := f_EPTF_RBTreeI_getFreeSlotInteger(rb_Tree);
    rb_Tree.nodes[newSentinel] := c_EPTF_emptyRBTNode;
    rb_Tree.integerKeyData[newSentinel] := c_EPTF_emptyIntegerNode;
        
    rb_Tree.nodes[newSentinel].left   := newSentinel;
    rb_Tree.nodes[newSentinel].right  := newSentinel;
    rb_Tree.nodes[newSentinel].parent := newSentinel;
    rb_Tree.nodes[newSentinel].color  := black;
    rb_Tree.nodes[newSentinel].isSentinel := true;

    rb_Tree.nil := newSentinel;

    //      ... and root
    newSentinel := f_EPTF_RBTreeI_getFreeSlotInteger(rb_Tree);

    rb_Tree.nodes[newSentinel] := c_EPTF_emptyRBTNode;
    rb_Tree.integerKeyData[newSentinel] := c_EPTF_emptyIntegerNode;
        
    rb_Tree.nodes[newSentinel].left   := rb_Tree.nil;
    rb_Tree.nodes[newSentinel].right  := rb_Tree.nil;
    rb_Tree.nodes[newSentinel].parent := rb_Tree.nil;
    rb_Tree.nodes[newSentinel].color  := black;
    rb_Tree.nodes[newSentinel].isSentinel := true;

    rb_Tree.root := newSentinel;

} // f_EPTF_RBTreeI_initIntegerTree

///////////////////////////////////////////////////////////
// Function: f_EPTF_RBTreeI_getIntegerElementNodeByKey
// 
// Purpose:
//      returns the given integer-keyed node from the given tree
// 
// Parameters:
//   rb_Tree - *inout* <EPTF_Integer_RedBlackTree> - the red-black-tree
//   key - *in* *integer* - the integer node index to find
//   nodeFound - *out* <EPTF_RBTreeNode> - the found integer node
//   indexFound - *out* *integer* - the found index
// 
// Return Value:
//   boolean - success
///////////////////////////////////////////////////////////

public function f_EPTF_RBTreeI_getIntegerElementNodeByKey(inout EPTF_Integer_RedBlackTree rb_Tree, in integer key, out EPTF_IntegerNode nodeFound, out integer indexFound) return boolean {

	var boolean isFound := false;
	indexFound := -1;

	isFound := f_EPTF_RBTreeI_getIntegerElementIndexByKey(rb_Tree, key, indexFound);
	if (isFound) {
		nodeFound := rb_Tree.integerKeyData[indexFound];
	} 
    return isFound;
}

///////////////////////////////////////////////////////////
// Function: f_EPTF_RBTreeI_searchSmallestIntegerNode
// 
// Purpose:
//      Get smallest integer key node from the given tree.
// 
// Parameters:
//   tree - *inout* <EPTF_Integer_RedBlackTree> - the integer red-black-tree
//   nodeFound - *out* <EPTF_IntegerNode> - smallest key integer node
//   indexFound - *out* *integer* - the found index
// 
// Return Value:
//   boolean - success
///////////////////////////////////////////////////////////

public function f_EPTF_RBTreeI_searchSmallestIntegerNode(inout EPTF_Integer_RedBlackTree tree, out EPTF_IntegerNode nodeFound, out integer indexFound) return boolean {  

    var boolean isFound := false;   
    indexFound := f_EPTF_RBTreeI_searchSmallestNodeIndex(tree);
    if (indexFound != -1) {
        isFound := true;
        nodeFound := tree.integerKeyData[indexFound];
    }    
    return isFound;
}

///////////////////////////////////////////////////////////
// Function: f_EPTF_RBTreeI_getSmallestNodeFromCache
// 
// Purpose:
//      Get smallest integer key element from the given tree. Refreshes cache automatically.
// 
// Parameters:
//   rb_Tree - *inout* <EPTF_Integer_RedBlackTree> - the integer red-black-tree itself
//   nodeFound - *out* <EPTF_IntegerNode> - shall be the smallest element of RBTree
// 
// Return Value:
//   boolean - success
///////////////////////////////////////////////////////////

public function f_EPTF_RBTreeI_getSmallestNodeFromCache(inout EPTF_Integer_RedBlackTree rb_Tree, out EPTF_IntegerNode nodeFound) return boolean {
    var boolean isFound := true;    
    var integer x := -1;
    
    if (f_EPTF_RBTreeI_getSmallestIntegerElementIndexFromCache(rb_Tree, x)) {
        isFound := true;
        nodeFound := rb_Tree.integerKeyData[x];
    } else {
        // The tree is empty.
        isFound := false;
    }
    
    return isFound;
}

///////////////////////////////////////////////////////////
// Function: f_EPTF_RBTreeI_getBusyEventHeadIndex
// 
// Purpose:
//      Get the head element of busy event tree.
// 
// Parameters:
//   rb_Tree - *inout* <EPTF_Integer_RedBlackTree> - the integer red-black-tree itself
//   idx - *inout* *integer* - shall be the head element of busy event tree (smallest)
// 
// Return Value:
//   boolean - success
///////////////////////////////////////////////////////////

public function f_EPTF_RBTreeI_getBusyEventHeadIndex(inout EPTF_Integer_RedBlackTree rb_Tree, inout integer idx) return boolean {
    
    return f_EPTF_RBTreeI_getSmallestIntegerElementIndexFromCache(rb_Tree, idx);

}

} //module