3

Gostaria de saber como poderia criar filas de objetos com prioridade em Delphi, sabemos que o conceito de fila é o que entra primeiro sai primeiro, sei que já existe essa função pronta no Delphi, mas preciso expandir essa função para trabalhar com prioridade. Minha necessidade é criar N filas (array), e os objetos (palavra e prioridade) que entram nessas filas carregam uma prioridade diferente, os objetos que tem prioridade maior, devem "passar na frente" dos objetos com prioridade menor, mas mantendo a ideia de fila. Por exemplo a fila de um banco, onde quem tem prioridade passa na frente, mas ainda se mantem a ordem de quem chega primeiro. Quem tem prioridade 1 passa na frente de quem tem prioridade 2 e assim sucessivamente. Procurei em diversos lugares na internet e não achei nenhum exemplo concreto sobre isso, apenas fragmentos que tentei usar sem sucesso, tenho um algoritmo pronto que funciona em parte mas não corretamente, se alguém puder compartilhar um exemplo usando Generics para as filas, e interfaces para os objetos ou qualquer coisa do tipo, serei muito grato.

Exemplo de Algorítimo que fiz para ter uma ideia da necessidade. (Não funciona muito bem).

{ 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;

Abaixo segue o Objeto que será adicionado a fila (Não funciona muito bem).

{ 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;

Construtor

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;

Implementação do PUSH (Objeto e Prioridade)

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

Implementação do POP (Objeto a ser removido e o tempo de vida dele).

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;

Estou trabalhando a pouco tempo com FIFO, ainda não consegui absorver o teorema completamente, peço um pouco de paciência dos colegas mais experientes. Não vou postar o código completo, pois como eu disse, ele não ta funcionando muito bem, se alguém tiver um exemplo parecido e puder compartilhar, serei muito grato.

1 Resposta 1

3

Minha proposta de solução para este caso não seria ter uma única fila que possa ter várias prioridades diferentes, mas sim várias filas, cada uma com sua prioridade. Assim, o que eu faria seria construir uma classe que apresenta os dois métodos de operação com fila (Add e Remove, por exemplo), sendo que o Add aceitaria a prioridade junto com o item sendo adicionado. O item sendo adicionado o seria na fila correspondente a prioridade especificada.

Internamente esta classe instancia e opera uma lista de filas, cada uma dedicada a uma prioridade. Sempre que o método Remove é chamado este percorre a lista de filas, da mais prioritária para a menos prioritária. Quando conseguir retirar um item de uma delas, o devolve e termina.

Assim as prioridades serão sempre respeitadas.

Nesta solução não é necessário alterar o comportamento padrão de uma fila, o que simplifica o desenho da mesma, pois uma classe com os dois métodos e uma lista de filas é fácil de ser implementado.

Se esta solução por algum motivo não for considerada interessante, então eu optaria por implementar o comportamento de fila usando um TObjectList<T>, onde T é uma classe que apresenta a prioridade e o item sendo adicionado. No momento de adicionar o novo item eu usaria o método TObjectList<T>.BinarySearch para inserir o item em seu local correto, respeitando a prioridade, mas em ordem inversa. Sempre que fosse remover um item da lista, usaria o método TObjectList<T>.Last, que pegaria o último item da lista, que seria o mais prioritário.

Nesta nova solução, novamente não é necessário alterar o comportamento da fila e se usaria os serviços já prontos da classe TObjectList<T>.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .