procedure Clear;
function Dequeue : pointer;
function Enqueue(alt em : pointer): TtdPQHandle;
function Examine : pointer;
function IsEmpty : boolean;
function Remove(aHandle : TtdPQHandle): pointer;
property Count : integer read pqGetCount;
property Name : TtdNameString read FName write FName;
end;
Как видите, единственное реальное различие между этим классом и классом TtdPriorityQueue состоит в наличии методов Remove и ChangePriority и в том, что метод Enqueue возвращает дескриптор.
Так как же реализован этот интерфейс? Внутренне очередь, как обычно, содержит сортирующее дерево, но на этот раз она должна поддерживать определенную дополнительную информацию, чтобы иметь возможность отслеживать позицию каждого элемента в сортирующем дереве. Кроме того, очередь должна идентифицировать каждый элемент дескриптором, чтобы поиск элемента по заданному дескриптору выполнялся быстро и эффективно - теоретически быстрее, чем в дереве двоичного поиска, где время поиска определяется соотношением O(log(n)).
Поэтому мы сделаем следующее: когда пользователь будет ставить элемент в очередь, мы будем добавлять элемент в связный список. Это будет сопряжено с определением и использованием узла и, по меньшей мере, двух указателей: указателя самого этого элемента и указателя следующего элемента, хотя по причинам, которые станут понятны несколько позже, мы будем использовать двухсвязный список и поэтому нам потребуется также и предыдущий указатель. Передаваемый нами обратно дескриптор элемента будет адресом узла. Теперь наступает важный момент. Узел хранит также целочисленное значение - позицию элемента в массиве, посредством которого реализовано сортирующее дерево. Сортирующее дерево не хранит сами элементы, а только их дескрипторы (т.е. узлы связного списка). Каждый раз, когда для выполнения сравнения ему нужно будет обратиться к самому элементу, оно будет разыменовывать дескриптор.
К сожалению, мы не можем использовать описанный в главе 3 класс связного списка, поскольку нам требуется доступ к узлам, а этот класс был разработан с целью сокрытия структуры узлов. Это один из случаев, когда нельзя использовать заранее стандартные классы и требуется выполнить кодирование от начала до конца. В случае применения двухсвязного списка это не так страшно, поскольку эта структура достаточно проста. Мы создадим связный список с явными начальным и конечным узлами. В результате удаление обычного узла превращается в исключительно простую задачу. Удаление узлов будет выполняться с применением обоих методов Dequeue и Remove класса расширенной очереди по приоритету.
Операции постановки в очередь и пузырькового подъема лишь немногим более сложны. Вначале мы создаем дескриптор, выделяя узел для элемента, и добавляем его в связный список узлов. Поскольку мы добавляем дескрипторы к сортирующему дереву, для доступа к элементам потребуется выполнять разыменование дескрипторов, а при перемещении элемента по сортирующему дереву индекс его новой позиции необходимо сохранять внутри узла. Код реализации методов постановки в очередь и пузырькового подъема приведен в листинге 9.10.
Листинг 9.10. Постановка в очередь и пузырьковый подъем в расширенной очереди по приоритету
procedure TtdPriorityQueueEx.pqBubbleUp(aHandle : pointer);
var
FromInx : integer;
ParentInx : integer;
ParentHandle : PpqexNode;
Handle : PpqexNode absolute aHandle;
begin
{если анализируемый дескриптор больше дескриптора родительского элемента, нужно их нужно поменять местами и продолжить процесс с новой позиции}
{Примечание: родительский узел дочернего узла, имеющего индекс n, имеет индекс (n-1)/2}
FromInx := Handle^.peInx;
if (FromInx > 0) then begin
ParentInx := (FromInx - 1) div 2;
ParentHandle := PpqexNode(FList.List^[ParentInx]);
{если элемент имеет родительский элемент и больше нее о...}
while (FromInx > 0) and
(FCompare (Handle^.peItem, ParentHandle^.peItem) > 0) do
begin
{нужно переместить родительский элемент вниз по дереву}
FList.List^[FromInx] := ParentHandle;
ParentHandle^.peInx := FromInx;
FromInx := ParentInx;
ParentInx := (FromInx - 1) div 2;
ParentHandle := PpqexNode(FList.List^[ParentInx]);
end;
end;
{сохранить элемент в правильной позиции}
FList.List^[FromInx] := Handle;
Handle^.peInx := FromInx;
end;
function TtdPriorityQueueEx.Enqueue(aItem : pointer): TtdPQHandle;
var
Handle : PpqexNode;
begin
{создать новый узел для связного списка}