FB_Tree_Map (Function Block)

A collection of key-value pair items implemented using an iterative AVL Tree. Keys and values can be retrieved as an immutable list (whose base is FB_ArrayList) via 4 traversal methods; Inorder, Preorder, Postorder and Level Order. This data structure was implemented with the help of Max Goren’s iterative AVL tree in C++. See Function Block’s body for more details.

Extends: FB_Collection

Implements: I_Tree_Map

Properties

_Traversal

Type: T_BST_Traversal

Traversal method for retrieving keys and values in the tree map set.

Methods

Balance

Performs rotation and updates heights until tree is balanced.

Inputs

Name	Type	Description
`pNode`	`POINTER TO` T_AVL_Map_Node

Clear

Empties/Clears/Deletes every item in the map.

Clear_Node

Deletes the node and its tree/sub-trees.

Inputs

Name	Type	Description
`pRoot`	`POINTER TO` T_AVL_Map_Node

Contains

Checks if key is contained in the map.

Inputs

Name	Type	Description
`Key`	`ANY`	Key to find.

Create_Node

Creates a new node in dynamic memory with a clone of the generic item as it data.

Inputs

Name	Type	Description
`Key, Value`	T_Generic

Outputs

Name	Type	Description
`bSuccess`	`BOOL`
`Error`	T_Error

Delete_Node

Safety deletes node. If the node and/or it’s value/data is in dynamic memory it/they will be deleted.

Inputs

Name	Type	Description
`pNode`	`REFERENCE TO POINTER TO` T_AVL_Map_Node

FB_exit

Inputs

Name	Type	Description
`bInCopyCode`	`BOOL`	if TRUE, the exit method is called for exiting an instance that is copied afterwards (online change).

Find_Minimum_Node

Finds the node with the smallest item in a tree or sub-tree.

Inputs

Name	Type	Description
`pNode`	`POINTER TO` T_AVL_Map_Node

Get

Gets the value associated with the specified key without removing it from the map.

Inputs

Name	Type	Description
`Key`	`ANY`	Key used to identify stored value
`Value`	`ANY`	Variable to store requested data

Outputs

Name	Type	Description
`bSuccess`	`BOOL`

Get_As_String

Returns value as a string, if type to string conversion is supported.

Inputs

Name	Type	Description
`Key`	`ANY`	Key used to identify stored value
`sValue`	`REFERENCE TO` `STRING`	Variable to store returned item.

Outputs

Name	Type	Description
`bSuccess`	`BOOL`

Get_Balance

Gets the difference between the left and right sub-trees.

Inputs

Name	Type	Description
`pNode`	`POINTER TO` T_AVL_Map_Node

Get_Generic

Gets the value in its generic form associated with the specified key in its generic form without removing it from the map. Use carefully as this contains the pointer of the actual value in the collection. If you wish to use this it is recommeded you create a copy of the returned value using MEMMOVE or MEMCPY

Inputs

Name	Type	Description
`Key`	T_Generic	Key used to identify stored value

Outputs

Name	Type	Description
`Value`	T_Generic	Variable to store requested data
`bSuccess`	`BOOL`

Get_Height

Safely gets the height of a sub-tree.

Inputs

Name	Type	Description
`pNode`	`POINTER TO` T_AVL_Map_Node

Get_Keys

Gets an immutable list of the keys.

Get_Values

Gets an immutable list of the values.

Insert

Insert an element with the provided key and value to the map.

Inputs

Name	Type	Description
`Key`	`ANY`	Key used to identify stored value
`Value`	`ANY`	Value to store in map with key

Outputs

Name	Type	Description
`bSuccess`	`BOOL`

Insert_Generic

Insert an element with the provided key and value in their generic forms to the map.

Inputs

Name	Type	Description
`Key`	T_Generic	Key used to identify stored value
`Value`	T_Generic	Value to store in map with key
`bUpdate`	`BOOL`	If this is true the value will be updated if the key already exists.

Outputs

Name	Type	Description
`bSuccess`	`BOOL`

Move_Node

Moves from node at source into the position of the destination.

Inputs

Name	Type	Description
`pDestination, pSource`	`POINTER TO` T_AVL_Map_Node

Remove

Removes value with the specified key from the map.

Inputs

Name	Type	Description
`Key`	`ANY`	Key used to identify stored value

Outputs

Name	Type	Description
`bSuccess`	`BOOL`

Remove_Generic

Removes value with the specified key in its generic form from the map.

Inputs

Name	Type	Description
`Key`	T_Generic	Key used to identify stored value

Outputs

Name	Type	Description
`bSuccess`	`BOOL`	Indicates whether operation was successful. Success = TRUE, Failure = FALSE

Remove_Node

Finds and removes a node from a tree/sub-tree and returns the new root of the tree/subtree.

Inputs

Name	Type	Description
`pNode`	`REFERENCE TO POINTER TO` T_AVL_Map_Node

Rotate_Left

Rotates a tree/sub-tree left.

Inputs

Name	Type	Description
`pX`	`POINTER TO` T_AVL_Map_Node

Rotate_Right

Rotates a tree/sub-tree right.

Inputs

Name	Type	Description
`pX`	`POINTER TO` T_AVL_Map_Node

Search_Node

Checks if an item is in a tree/ sub-tree.

Inputs

Name	Type	Description
`pNode`	`POINTER TO` T_AVL_Map_Node
`Key`	T_Generic

Update

Updates the value at the provided key with the new value in the map.

Inputs

Name	Type	Description
`Key`	`ANY`	Key used to identify stored value
`Value`	`ANY`	Value to store in map with key

Outputs

Name	Type	Description
`bSuccess`	`BOOL`

Update_Generic

Updates the value at the provided key with the new value in their generic forms in the map.

Inputs

Name	Type	Description
`Key`	T_Generic	Key used to identify stored value
`Value`	T_Generic	Value to store in map with key

Outputs

Name	Type	Description
`bSuccess`	`BOOL`

Update_Height

Inputs

Name	Type	Description
`pNode`	`POINTER TO` T_AVL_Map_Node

Upsert

Updates a value in the map for a given key. If the key doesnt exist, it will be inserted.

Inputs

Name	Type	Description
`Key`	`ANY`	Key used to identify stored value
`Value`	`ANY`	Value to store in map with key

Outputs

Name	Type	Description
`bSuccess`	`BOOL`