Create Priority Queues in Delphi XE5

Question

I would like to know how to create rows of objects with priority in Delphi, we know that the concept of queue is what first comes out first, I know there is already this function ready in Delphi, but I need to expand this function to work with priority. My need is to create N queues (array), and the objects (word and priority) that enter these queues carry a different priority, the objects that have higher priority, must "pass in front" of the objects with lower priority, but keeping the idea of queuing. For example, the line of a bank, where those who have priority pass in front, but still maintain the order of those who arrive first. Those who have priority 1 pass in front of those who have priority 2 and so on. I’ve searched a lot of places on the Internet and I haven’t found any concrete examples of this, just fragments that I’ve tried to use unsuccessfully, I have an algorithm that works in part but not correctly, if someone can share an example using Generics for the queues, and interfaces to objects or anything like that, I’ll be very grateful.

Example of Algorithm I made to get an idea of the need. (Doesn’t work very well).

{ Classe TprioriFila }
type
  TprioriFila = class(TObject)
  private
    countSema: Thandle;
    access: TcriticalSection;
    Active: Boolean; //Se a fila está ativa ou inativa
    prioQueues: array [1..3] of TobjectQueue; //Prioridade 1 para maior e 3 menor.
  public
    constructor create;
    procedure push(inObject: TObject; priority: Integer); virtual; //Push da Fila
    function pop(pResObject: pObject; timeout: Integer): Boolean; //Pop da Fila
    destructor destroy; override;
  end;

Below follows the Object that will be added to the queue (Does not work very well).

{ Classe TPalavra }
type
  TPalavra = class
  private
    // campos
    fTexto: string; //Texto
    fReqRet: Boolean; //Requer Retorno
    // métodos
    function getTexto: string;
    function getReqRet: Boolean;
    procedure setTexto(aTexto: string);
    procedure setReqRet(aReqRet: Boolean);
  public
    // propriedades
    property Texto: string read getTexto write setTexto;
    property ReqRet: Boolean read getReqRet write setReqRet;
  end;

Builder

constructor TprioriFila.create;
var
  initIndex: Integer;
begin
  inherited;
  access := TcriticalSection.create;
  countSema := createSemaphore(nil, 0, maxInt, nil);
  Active := False; //Inicia a Fila como Inativa
  for initIndex := 1 to QprioriMin do
  begin
    prioQueues[initIndex] := TobjectQueue.create; //Cria as filas
  end;
end;

Implementation of PUSH (Object and Priority)

procedure TprioriFila.push(inObject: TObject; priority: Integer);
begin
  access.acquire;
  prioQueues[priority].push(inObject);
  access.release;
  releaseSemaphore(countSema, 1, nil);
end;

Implementation of POP (Object to be removed and its lifetime).

function TprioriFila.pop(pResObject: pObject; timeout: Integer): Boolean;
var
  queueIndex: Integer;
begin
  result := (WAIT_OBJECT_0 = waitForSingleObject(countSema, timeout));
  if result then
  begin
    access.acquire;
    for queueIndex := QprioriMax to QprioriMin do
    begin
      if (prioQueues[queueIndex].count > 0) then
      begin
        pResObject^ := prioQueues[queueIndex].pop;
        break;
      end;
    end;
    access.release;
  end;
end;

I am working recently with FIFO, I have not yet been able to absorb the theorem completely, I ask for a little patience from my more experienced colleagues. I will not post the full code, because as I said, it’s not working very well, if someone has a similar example and can share, I will be very grateful.

Answer 1

My solution proposal for this case would not be to have a single queue that can have several different priorities, but rather several queues, each with its own priority. So what I would do is build a class that presents the two operation methods with queue (Add and Remove, for example), where the Add would accept the priority along with the item being added. The item being added would be in the corresponding queue the specified priority.

Internally this instance class operates a queue list, each dedicated to a priority. Whenever the method Remove is called this runs the list of queues, from the most priority to the least priority. When you can remove an item from one of them, return it and end it.

So priorities will always be respected.

In this solution it is not necessary to change the default behavior of a queue, which simplifies the design of the queue, because a class with both methods and a queue list is easy to implement.

If this solution for some reason is not considered interesting, then I would choose to implement queuing behavior using a TObjectList<T>, where T is a class that displays the priority and the item being added. At the time of adding the new item I would use the method TObjectList<T>.BinarySearch to insert the item in its correct location, respecting the priority, but in reverse order. Whenever I would remove an item from the list, I would use the method TObjectList<T>.Last, that would take the last item on the list, which would be the highest priority.

In this new solution, again it is not necessary to change the behavior of the queue and if it would use the already ready services of the class TObjectList<T>.