Поэтому мы сделаем следующее: когда пользователь будет ставить элемент в очередь, мы будем добавлять элемент в связный список. Это будет сопряжено с определением и использованием узла и, по меньшей мере, двух указателей: указателя самого этого элемента и указателя следующего элемента, хотя по причинам, которые станут понятны несколько позже, мы будем использовать двухсвязный список и поэтому нам потребуется также и предыдущий указатель. Передаваемый нами обратно дескриптор элемента будет адресом узла. Теперь наступает важный момент. Узел хранит также целочисленное значение - позицию элемента в массиве, посредством которого реализовано сортирующее дерево. Сортирующее дерево не хранит сами элементы, а только их дескрипторы (т.е. узлы связного списка). Каждый раз, когда для выполнения сравнения ему нужно будет обратиться к самому элементу, оно будет разыменовывать дескриптор.

К сожалению, мы не можем использовать описанный в главе 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

{создать новый узел для связного списка}

Handle := AddLinkedListNode(FHandles, aItem);

{добавить дескриптор в конец очереди}

FList.Add(Handle);

Handle^.peInx := pred(FList.Count);

{теперь нужно выполнить его пузырьковый подъемна максимально возможный уровень}

if (FList.Count > 1) then

pqBubbleUp(Handle);

{вернуть дескриптор}

Result := Handle;

end;

Подобно методу Enqueue, все эти косвенные ссылки несколько усложняют метод Dequeue, но в коде все же можно распознать стандартные операции исключения из очереди и просачивания.

Листинг 9.11. Исключение из очереди и просачивание в расширенной очереди по приоритету

procedure TtdPriorityQueueEx.pqTrickleDown(aHandle : TtdPQHandle);

var

FromInx : integer;

MaxInx : integer;

ChildInx : integer;

ChildHandle : PpqexNode;

Handle : PpqexNode absolute aHandle;

begin

{если анализируемый элемент меньше одного из своих дочерних элементов, его нужно поменять местами с большим дочерним элементом и продолжить процесс из новой позиции}

FromInx := Handle^.peInx;

MaxInx := pred(FList.Count);