Абстракция очереди

Очень важно определить различие между тем какие сервисы предусматривает тип, и как этот тип их реализует.

Например, абстракция списка, которая имеет соответствующие подпрограммы и сама может быть реализована как связанный список или как массив, может быть использована для реализации абстракции очереди.

Абстракция очереди будет иметь только несколько операций:

Add_To_Tail Remove_From_Head Full Empty Init

Необходимо убедиться, что в программе существует четкое различие между используемой абстракцией и реализацией.

Кроме того, желательно возложить на компилятор проверку правильности осуществления вызова подпрограмм реализации, чтобы автоматически предотвратить непреднамеренные обращения к подпрограммам используемой абстракции.

Ниже приведен пример пакета использование которого может привести к проблемам:

package Lists is

type List is private;

procedure Add_To_Head(Item : in out List; Value : in Integer); procedure Remove_From_Head(Item : in out List; Value : out Integer);

procedure Add_To_Tail(Item : in out List; Value : in Integer); procedure Remove_From_Tail(Item : in out List; Value : out Integer);

function Full(Item : List) return Boolean; function Empty(Item : List) return Boolean;

function Init return List;

private

type List is ... -- полное описание типа

end Lists;

with Lists; use Lists; -- абстракция списка Lists

package Queues is

type Queue is new List; -- наследует операции типа List

-- то есть, следующее описано "автоматически" (неявно) -- -- procedure Add_To_Head(Item : in out Queue; Value : in Integer); -- procedure Remove_From_Head( -- Item : in out Queue; -- Value : out Integer); -- и т.д.

end Queues;

Здесь, тип очереди (Queue) наследует все операции типа список (List), даже те, которые для него не предназначены (например Remove_From_Tail). При такой реализации типа Queue, клиенты абстракции могут легко нарушить очередь, которая должна разрешать только вставку в конец очереди и удаление из начала очереди.

Например, клиент пакета Queues может легко сделать следующее:

with Queues; use Queues;

procedure Break_Abstraction is

My_Q : Queue;

begin

Add_To_Head(My_Q, 5); Add_To_Tail(My_Q, 5);

-- очередь должна разрешать вставку в конец очереди -- и удаление из начала очереди, -- или наоборот

end Break_Abstraction;

Для решения подобной проблемы при создании абстракции очереди необходимо использовать абстракцию списка приватно:

with Lists; -- это используется только приватной секцией

package Queues is

type Queue is private;

procedure Remove_From_Head(Item : in out Queue; Value : out Integer); procedure Add_To_Tail(Item : in out Queue; Value : Integer);

function Full(Item : Queue) return Boolean; function Empty(Item : Queue) return Boolean;

function Init return Queue;

private

type Queue is new Lists.List;

end Queues;

package body Queues is

-- выполняем конверсию типов (из Queue в List), а затем, -- выполняем вызов соответствующей подпрограммы List

use Lists;

-------------------------------------------------------------------- procedure Remove_From_Head(Item : in out Queue; Value : out Integer) is

begin

Lists.Remove_From_Head(List(Item), Value); end Remove_From_Head;

-------------------------------------------------------------------- function Full(Item : Queue) return Boolean is

begin

return Lists.Full(List(Item)); end Full;

. . .

function Init return Queue is

begin

return Queue(Lists.Init); end Init;

end Queues;

Содержание раздела