User Tools

Site Tools


k7:k7.3:k7.3.4:start

7.3.4 Class PrioQueue (gb. data)

A priority queue or PrioQueue is a queue? chapter 7.3.3, which first divides its elements into priority classes and follows the FIFO semantics in each of these classes. Like all classes in the component gb. data, PrioQueue uses the data type Variant for its elements.

You can assign an integer as a priority to each element when you place it in the PrioQueue. The higher this number is, the more important the element is and it is placed further at the beginning of the queue. If two elements have the same priority - are in a priority class - the FIFO principle is applied. The element that will be added to the end of the priority class.

7.3.4.1 Properties

The properties of the PrioQueue correspond to those of the queue:

Property Data typeDescription
.SizeInteger (ReadOnly)Number of elements of the PrioQueue
.IsEmptyBoolean (ReadOnly)True, if there are no elements in the PrioQueue, otherwise wrong

Table 7.3.4.1.1: Properties of the PrioQueue class

7.3.4.2 Methods of a PrioQueue object

Except for the Enq () method, those of the PrioQueue are the same as those of the queue. The Enq () method additionally takes over the priority for the element to be grouped.

MethodDescription
Clear ()Remove all elements from the stack
Enq (vElement, iPrio)Synonym for Enqueue (vElement, iPrio)
Enqueue (vElement, iPrio)Insertion of a new element with the specified priority
Deq ()Synonym for Dequeue ()
Dequeue ()Remove and return the first element
Peek ()Returns the first element without removing it

Table 7.3.4.2.1: Methods of the Class PrioQueue

The following code:

Dim hPrioQueue As New PrioQueue 
 
hPrioQueue.Enq("x", 2) 
hPrioQueue.Enq("y", 1) 
hPrioQueue.Enq("z", 2) 
 
Print hPrioQueue.Deq() 
Print hPrioQueue.Deq() 
Print hPrioQueue.Deq() 

creates this output in the console:

x
z 
y 

“x” and “z” are in a priority class (–> 2). Since“ z” was later classified as “x”, it is later in the same class. “y” with lower priority is the last element in the output.

7.3.4.3 Project for using the PrioQueue class

Gambas developer Bruce Bruce Bruen mentioned that he used the PrioQueue class to run 56 SQL scripts in 5 priority classes for integrity checking and statistics generation for a large database. Until then, this functionality had to be implemented and manually maintained in a larger shell script, which became increasingly tedious for occasionally added scripts. Since Gambas 3.2, a very small Gambas program can dynamically determine the priority of the script from the header of the script files and execute all scripts in the intended order.

Based on this case of use, a project will be presented to demonstrate the PrioQueue class, which divides a large number of shell scripts into priority levels (5 scripts in 4 steps are provided in the project) and executes them. The order of execution of the scripts within a priority level is arbitrary? level 3 with 2 scripts. All scripts with a higher priority number have to be executed before those with a lower priority number - which corresponds to the semantics of the PrioQueue. The priority is given in each script file via a line with the syntax:

# PRIO <X>

where <X> has priority[0…9] of a script in the presented project.

Start

Figure 7.3.4.3.1: Project PriorityQueue (Start)

Level4

Figure 7.3.4.3.3.2: Project PriorityQueue (processing level 2)

This system of classifying scripts into defined priority levels is comparable to the individual runlevels that are run at the start of a Unix operating system http://de.wikipedia.org/wiki/Runlevel.

You must take note of an exception: A PrioQueue cannot be traversed backwards!

Download

7.3.4 Klasse PrioQueue (gb.data)

Eine Prioritäts-Queue oder PrioQueue ist eine Queue → Kapitel 7.3.3, die ihre Elemente zuerst in Prioritätsklassen einteilt und in jeder dieser Klassen der FIFO-Semantik folgt. Wie alle Klassen in der Komponente gb.data, verwendet auch PrioQueue den Datentyp Variant für seine Elemente.

Jedem Element kann von Ihnen bei der Einreihung in die PrioQueue eine ganze Zahl als Priorität zugewiesen werden. Je höher diese Zahl ist, desto wichtiger ist das Element und es wird weiter am Anfang der Queue eingeordnet. Besitzen zwei Elemente die gleiche Priorität – liegen in einer Prioritätsklasse – so wird das FIFO-Prinzip angewandt. Das später eingeordnete Element wird an das Ende der Prioritätsklasse angefügt.

7.3.4.1 Eigenschaften

Die Eigenschaften der PrioQueue entsprechen denen der Queue:

Eigenschaft DatentypBeschreibung
.SizeInteger (ReadOnly)Anzahl der Elemente der PrioQueue
.IsEmptyBoolean (ReadOnly)Wahr, wenn keine Elemente in der PrioQueue sind, sonst falsch

Tabelle 7.3.4.1.1: Eigenschaften der Klasse PrioQueue

7.3.4.2 Methoden eines PrioQueue-Objektes

Bis auf die Enq()-Methode entsprechen die der PrioQueue denen der Queue. Die Enq()-Methode übernimmt zusätzlich die Priorität für das einzureihende Element.

MethodeBeschreibung
Clear()Entfernen aller Elemente vom Stapel
Enq(vElement, iPrio)Synonym für Enqueue(vElement, iPrio)
Enqueue(vElement, iPrio)Einreihen eines neuen Elements mit der angegebenen Priorität
Deq()Synonym für Dequeue()
Dequeue()Entfernen und zurückgeben des ersten Elements
Peek()Rückgabe des ersten Elements, ohne es zu entfernen

Tabelle 7.3.4.2.1: Methoden der Klasse PrioQueue

Der folgende Code:

Dim hPrioQueue As New PrioQueue 
 
hPrioQueue.Enq("x", 2) 
hPrioQueue.Enq("y", 1) 
hPrioQueue.Enq("z", 2) 
 
Print hPrioQueue.Deq() 
Print hPrioQueue.Deq() 
Print hPrioQueue.Deq() 

erzeugt diese Ausgabe in der Konsole:

x
z 
y 

“x” und “z” liegen in einer Prioritätsklasse (→ 2). Da “z” später als “x” eingereiht wurde, liegt es weiter hinten in derselben Klasse. “y” mit geringerer Priorität ist das letzte Element in der Ausgabe.

7.3.4.3 Projekt zum Einsatz der Klasse PrioQueue

Der Gambas-Entwickler Bruce Bruen erwähnte, dass er die Klasse PrioQueue nutze, um 56 SQL-Skripte in 5 Prioritätsklassen zur Integritätsprüfung und Statistikerstellung für eine große Datenbank auszuführen. Bis dahin musste diese Funktionalität in einem größeren Shell-Skript implementiert und manuell gepflegt werden, was bei gelegentlich hinzuzufügenden Skripten zunehmend mühsam wurde. Seit Gambas 3.2 kann ein sehr kleines Gambas-Programm aus dem Header der Skriptdateien dynamisch die Priorität des Skripts ermitteln und alle Skripte in der vorgesehenen Reihenfolge ausführen.

Angelehnt an diesen Einsatzfall soll zur Demonstration der Klasse PrioQueue ein Projekt vorgestellt werden, das eine Vielzahl von Shell-Skripten in Prioritätsstufen unterteilt (5 Skripte in 4 Stufen werden Ihnen im Projekt zur Verfügung gestellt) und ausführt. Die Reihenfolge der Ausführung der Skripte innerhalb einer Prioritätsstufe ist beliebig → Level 3 mit 2 Skripten. Alle Skripte mit höherer Prioritätszahl müssen vor denjenigen mit geringerer Prioritätszahl ausgeführt werden – was der Semantik der PrioQueue entspricht. Die Priorität wird in jeder Skript-Datei über eine Zeile mit der Syntax:

# PRIO <X>

festgelegt, wobei <X> die Priorität [0..9] eines Skripts im vorgestellten Projekt ist.

Start

Abbildung 7.3.4.3.1: Projekt PriorityQueue (Start)

Level4

Abbildung 7.3.4.3.2: Projekt PriorityQueue (Abarbeitung Level 2)

Dieses System der Einteilung der Skripte in definierte Prioritätsstufen ist vergleichbar mit den einzelnen Runleveln, die beim Start eines Unix-Betriebssystems durchlaufen werden http://de.wikipedia.org/wiki/Runlevel.

Eine Ausnahme müssen Sie beachten: Eine PrioQueue kann nicht rückwärts durchlaufen werden!

Download

The website uses a temporary session cookie. This technically necessary cookie is deleted when the browser is closed. You can find information on cookies in our privacy policy.
k7/k7.3/k7.3.4/start.txt · Last modified: 02.07.2018 (external edit)

Page Tools