Creating Priority Queues in Delphi XE5

Navigation
3

I would like to know how to create priority object queues in Delphi, we know that the queue concept is what comes in first, it comes out first, I know that Delphi is already there, but I need to expand this function to work with priority . My need is to create N arrays, and the objects (word and priority) that enter these queues carry a different priority, objects that have higher priority, must "pass in front" of the objects with lower priority, but keeping the idea of row. For example the queue of a bank, where those who have priority passes in front, but still keeps the order of who arrives first. Those who have priority 1 pass in front of those who have priority 2 and so on. I have searched in several places on the internet and found no concrete example of this, only fragments that I have tried unsuccessfully to use, have an algorithm ready that works partly but not correctly, if someone can share an example using Generics for queues, and interfaces to the objects or anything of the kind, I will be very grateful.

Example of Algorithm I did to get an idea of the need. (It does not 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 is 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;

PUSH Implementation (Object and Priority) 

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

POP implementation (Object to be removed and lifetime of it). 

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'm working with FIFO shortly, I still can not absorb the theorem completely, I ask for some patience from the more experienced colleagues. I will not post the complete code, as I said, it is not working very well, if someone has a similar example and can share, I will be very grateful.

    
asked by anonymous 19.08.2014 / 14:16

1 answer

3

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

Internally this class instantiates and operates a list of queues, each dedicated to a priority. Whenever the Remove method is called this runs through the list of queues, from the highest priority to the least priority. When you can remove an item from one of them, it returns and ends.

So priorities will always be respected.

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

If this solution is not considered interesting for some reason, then I would choose to implement the queue 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 TObjectList<T>.BinarySearch to enter the item in its correct location, respecting the priority, but in reverse order . Whenever you remove an item from the list, you would use the TObjectList<T>.Last method, which would take the last item in the list, which would be the highest priority.

In this new solution, you do not have to change the behavior of the queue again and you would use the ready-made services of class TObjectList<T> .

    
19.08.2014 / 16:14
Running background processes - Accessing same script twice Using SendMessage with applications such as Notepad, Word, DreamWeaver