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 is possible. The documentation says the following about it:

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:

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

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:

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 and anytype data types will help us get out of this situation.

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:

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:

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:

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:

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 🙂