Overview of containers in WinCC OA. Attempt to implement a priority queue
SIMATIC WinCC Open Architecture is a SCADA development system from ETM(Siemens). In recent years, it has become quite popular in Russia in certain circles.
Since there is not a lot of information about this product on the Internet, and rather superficial knowledge is given in the trainings and many points are not touched upon, the idea came up to try to write a series of articles with topics that are interesting in my opinion.
WinCC OA has a built-in C/C++ similar scripting language CONTROL. Let’s talk about its capabilities today.
Dynamic arrays
Dynamic arrays are represented by two kinds of data types:
vector
, where type is the data type. A type can be as simple as an int or double, or as complex as a string, structure, or another vector. In fact, this is the same vector as in C++ with similar methods and capabilities. dynamic array Dyn_typewhere type is also the data type.
In general, both types are fundamentally no different. The documentation says so verbatim about their differences:
The biggest difference between vectors and dyn_ variables is the index. For vectors this index starts at 0 while dyn_ variables start at 1
It is also worth noting here that such an option as vector
The void data type for a vector allows to add any data type. A vector
is similar to a dyn_anytype, but a dyn_anytype is a dyn_ containing anytype variables, which themselves point to any other type. In terms of performance and memory consumption, the vector is better, since it directly holds the final pointers to whatever datatype was given.
Vector object and dynamic array object have the same methods:
The language also provides separate functions for working with dynamic arrays. Such functions cannot be used with a vector.
List of functions from the documentation:
Associative arrays
This data type is represented by one type: “mapping”.
From documentation:
“mapping” variables store arbitrary key-value pairs. Keys and values are stored in two arrays: one for keys and one for values
Thus, it turns out that here we are dealing with the simplest implementation and “under the hood” we have two arrays. It smacks of linear O(n) complexity to perform the basic add, find, and delete operations. No binary search trees and hash tables here with their logarithmic O(log n) and constant O(1) complexities.
Associative array methods:
Functions for working with mapping:
Function | Description |
mappingClear | Deletes all mapping entries. |
mappingHasKey | Checks for the presence of a “key” in the mapping. |
mappingRemove | Removes the entry (mappings) with the specified “key”. |
mappingGetKey | Returns the key at the specified index. |
mappingKeys | Returns an array with all mapping keys. |
mappingGetValue | Returns the value (of associations) at the specified index |
mappinglen | Returns the size of an associative array |
Strings
Separately, it is worth noting the presence of such a data type as a string: string. Basically, it’s an array with char elements. Indexing, like a vector, starts from 0. Each character can be read using the operator []. But here you have to be careful. Strings cannot be written or overwritten character by character. Otherwise, it is convenient to work with strings. For them, a large number of convenient functions have been implemented.
String Methods:
String Functions
Function | Description |
dpValToString() | Converts the value specified in the val parameter to a string with the format string of the used dp data point element |
patternMatch() | Checks for the presence of a specific string pattern |
sprintf() | Performs string formatting |
sprintfPL() | Performs string formatting. Similar to sprintf(), but jumps to current WinCC OA language before conversion |
sprintfUL() | Performs string formatting similar to sprintf(), but jumps to the current Windows user’s language before conversion |
sscanf() | Imports a formatted string |
sscanfPL() | Imports a formatted string. Similar to sscanf(), but jumps to the current WinCC OA language before conversion. |
sscanfUL() | Imports a formatted string. Similar to sscanf(), but jumps to the current Windows user’s language before conversion |
strchange() | Changes the contents of the string at the given index for a given number of digits using a replacement string |
strexpand | Returns a formatted string |
strformat | Returns a formatted string |
strlen() | Returns the length of the string in bytes |
strltrim() | Excludes certain characters from a string, starting from the left |
strpos() | Returns the position of a string within another string |
strreplace() | Replaces parts of a string with another string |
strrtrim() | Strips certain characters from a string, starting from the right |
strsplit() | Separates strings using delimiter characters |
strtolower() | Changes the characters of a string to lowercase |
strtoupper() | Changes the characters of a string to uppercase |
substr() | Cuts a string or character of a certain length (in bytes) into another string |
strtok() | Finds the first match of a string in another string |
stringEditor() | To edit string variables, for example, in text fields, you can use the “stringEditor()” function. This means string variables are not stored in the file |
That’s all with container data types, but this is quite enough to implement others, given the presence of such a convenient tool as the shared_ptr smart pointer.
To begin with, let’s start with something simpler, namely the priority queue. We will draw inspiration from the priority_queue from the C++ standard library.
Priority queue or Binary heap (Heap)
This data structure is implemented as a pyramid, where the element with the highest priority is located at the root.
It is convenient to make a pyramid on an array. To do this, we will use the following rules:
tree root index is 1
Zero array index is not used. This is necessary for the convenience of calculating the remaining indices of the tree.
index of left child for parent i is 2*i
the right child index for parent i is 2*i + 1
parent index of child i equals integer division of i by 2
Array:
i | 0 | 1 | 2 | 3 | four | five | 6 | 7 | 8 | nine |
value | 0 | 3 | five | 10 | nine | 40 | 15 | 12 | eleven | sixteen |
Let’s try to implement the PriorityQueue class. Here common sense says that the class should be templated, but there is no such concept in WinCC OA. The vector
As fields of the class, we will write a vector that will store our pyramid, separately, purely for dubious convenience, we will store the size of the heap and the pointer to the comparator function. Fortunately, the developers of WinCC OA provided for the presence of such a pointer.
Briefly about it from the documentation:
Go ahead. The constructor will initialize the fields of the class with initial values. For the default value of the pointer to the comparator, we implement the private method DefaultComp.
We also implement methods:
Top – displays the element of the queue with the highest priority (element of the vector with index 1)
Empty – checking the queue for emptiness
Size – displays the size of the queue
Swap – swaps two queues. Here, for convenience, we additionally implement the private method Sw
We get this code:
class PriorityQueue {
private vector<void> heap_;
private int size_;
private function_ptr comp_;
//The compare function must be declared static.
public PriorityQueue(function_ptr compare = DefaultComp){
size_ = 0;
heap_.append(0);
comp_ = compare;
}
//accesses the top element
public anytype Top(){
return heap_.at(1);
}
//checks whether the underlying container is empty
public bool Empty(){
return size_ == 0;
}
//returns the number of elements
public int Size(){
return size_;
}
//swaps the contents
public Swap(PriorityQueue& other){
Sw(size_, other.size_);
Sw(comp_, other.comp_);
Sw(heap_, other.heap_);
}
private Sw(anytype& lhs, anytype& rhs){
anytype temp = lhs;
lhs = rhs;
rhs = temp;
}
private static bool DefaultComp(const anytype lhs, const anytype rhs) {
return lhs < rhs;
}
};Inserting an element
We will insert a new element as follows. The element is added to the end of the heap, i.e. to the end of our array.
Array:
i | 0 | 1 | 2 | 3 | four | five | 6 | 7 | 8 | nine | 10 |
value | 0 | 3 | five | 10 | nine | 40 | 15 | 12 | eleven | sixteen | 6 |
Next, we need to do what is called “sifting up” so that the new element takes its place in the queue in accordance with its value. Such an insertion will occur in O(log n).
Array:
i | 0 | 1 | 2 | 3 | four | five | 6 | 7 | 8 | nine | 10 |
value | 0 | 3 | five | 10 | nine | 6 | 15 | 12 | eleven | sixteen | 40 |
Let’s try to implement. To do this, add the following methods to the PriorityQueue class:
Push – inserting a new element
SiftUp – we will separate sifting up into a separate private method
The code:
//inserts element and sorts the underlying container
public Push(anytype item){
heap_.append(item);
++size_;
SiftUp();
}
private SiftUp() {
int idx = Size();
while (true) {
if (idx == 1) {
break;
}
if (callFunction(comp_, heap_[idx], heap_[idx / 2])) {
Sw(heap_[idx], heap_[idx / 2]);
idx /= 2;
}
else {
break;
}
}
}Removing an element
The element is removed from the root of our pyramid. So that the tree does not fall apart, we plug this place with the last element of the array, transferring it to cell i=1.
Array:
i | 0 | 1 | 2 | 3 | four | five | 6 | 7 | 8 | nine |
value | 0 | 40 | five | 10 | nine | 6 | 15 | 12 | eleven | sixteen |
After that, we need to do a “down sifting” so that the element with the highest priority appears at the top again and all the elements of the heap take their places. Such deletion will occur in O(log n).
Array:
i | 0 | 1 | 2 | 3 | four | five | 6 | 7 | 8 | nine |
value | 0 | five | 6 | 10 | nine | 40 | 15 | 12 | eleven | sixteen |
We implement. To do this, add the following methods to the PriorityQueue class:
Pop – remove the element with the highest priority
TakeTop – removes the item with the highest priority while removing it from the queue
SiftDown – we will separate sifting down into a separate private method
The code:
//removes the top element
public Pop(){
if (Size() > 1) {
heap_[1] = heap_.takeLast();
--size_;
SiftDown();
}
else if(Size() == 1) {
heap_.removeAt(1);
--size_;
}
}
public anytype TakeTop(){
anytype temp = heap_.at(1);
Pop();
return temp;
}
private SiftDown() {
int idx = 1;
while (true) {
if (heap_.count() > 2 * idx + 1) {
if (callFunction(comp_, heap_[2 * idx], heap_[2 * idx + 1])) {
if (callFunction(comp_, heap_[2 * idx], heap_[idx])) {
Sw(heap_[2 * idx], heap_[idx]);
idx = 2 * idx;
}
else {
break;
}
}
else {
if (callFunction(comp_, heap_[2 * idx + 1], heap_[idx])) {
Sw(heap_[2 * idx + 1], heap_[idx]);
idx = 2 * idx + 1;
}
else {
break;
}
}
}
else if (heap_.count() == 2 * idx + 1 && callFunction(comp_, heap_[2 * idx], heap_[idx])) {
Sw(heap_[2 * idx], heap_[idx]);
break;
}
else {
break;
}
}
}Cherry on the cake
For the convenience of setting the priority, let’s create a small class CompareClass
class CompareClass
{
public static bool Greater(const anytype& lhs, const anytype& rhs) {
return lhs > rhs;
}
public static bool Less(const anytype& lhs, const anytype& rhs) {
return lhs < rhs;
}
};Thus, we can conduct a small test of the resulting priority queue
void UnitTestPriorityQueue() {
function_ptr ptr_greater = CompareClass::Greater;
PriorityQueue pq = PriorityQueue(ptr_greater);
oaUnitAssertEqual("TestCase №1", pq.Size(), 0);
oaUnitAssertTrue("TestCase №2", pq.Empty());
pq.Push(10);
oaUnitAssertEqual("TestCase №3", pq.Top(), 10);
pq.Push(4);
oaUnitAssertEqual("TestCase №4", pq.Top(), 10);
pq.Push(15);
oaUnitAssertEqual("TestCase №5", pq.Top(), 15);
pq.Push(6);
oaUnitAssertEqual("TestCase №6", pq.Top(), 15);
pq.Push(3);
oaUnitAssertEqual("TestCase №7", pq.Top(), 15);
pq.Push(20);
oaUnitAssertEqual("TestCase №8", pq.Top(), 20);
pq.Push(7);
oaUnitAssertEqual("TestCase №9", pq.Top(), 20);
oaUnitAssertEqual("TestCase №10", pq.Size(), 7);
pq.Pop();
oaUnitAssertEqual("TestCase №11", pq.Top(), 15);
oaUnitAssertEqual("TestCase №12", pq.Size(), 6);
oaUnitAssertEqual("TestCase №13", pq.TakeTop(), 15);
oaUnitAssertEqual("TestCase №14", pq.Top(), 10);
oaUnitAssertEqual("TestCase №16", pq.Size(), 5);
while(!pq.Empty()) {
pq.Pop();
}
oaUnitAssertEqual("TestCase №16", pq.Size(), 0);
}To be continued … but this is not accurate 🙂
