Ада: удаление из гетерогенного списка

Question

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

PACKAGE AbstList IS
   TYPE AbstractList IS LIMITED PRIVATE;

   TYPE Node IS TAGGED PRIVATE;
   TYPE NodePtr IS ACCESS ALL Node'Class;

   PROCEDURE Init_Head(List: ACCESS AbstractList);

   PROCEDURE InsertFront(List: ACCESS AbstractList; Item: IN NodePtr; Success: OUT Boolean);

   PROCEDURE InsertRear(List: ACCESS AbstractList; Item: IN NodePtr; Success: OUT Boolean);

   FUNCTION ListSize(List: ACCESS AbstractList) RETURN Integer;

   -- The following are commented out as they are not complete in the package body

   --FUNCTION FindItem(List: ACCESS AbstractList; Value: NodePtr) RETURN NodePtr;

   --PROCEDURE Delete(List: ACCESS AbstractList; Item: NodePtr);   

   --PROCEDURE Print(List: ACCESS AbstractList);


   PRIVATE
   TYPE Node IS TAGGED RECORD
      Rlink, Llink: NodePtr;
   END RECORD;

   TYPE AbstractList IS LIMITED RECORD
      Count: Integer := 0;
      Head: NodePtr := NEW Node;
   END RECORD;

END AbstList;

Одна такая запись, которую я использую для вставки в список, выглядит следующим образом:

   TYPE CarName IS (GMC, Chevy, Ford, RAM);

   TYPE Car IS NEW AbstList.Node WITH RECORD 
      NumDoors: Integer;
      Manufacturer: CarName := GMC;   -- Default manu.
   END RECORD;

Так, например, как я могу найти узел в списке, который содержит указанный "Производитель"? Мне было предложено перегрузить оператор "=", хотя я не уверен, как это будет работать, учитывая то, что у меня есть. Мы ценим любые предложения.

Answer 1

Согласно ARM, оператор равенства задан для неограниченных типов, что имеет место для вашего типа узла.

Если вы хотите, чтобы поведение отличалось от поведения по умолчанию (равенство всех членов вашей записи, просто переопределите его. Спецификация функции находится на той же странице, просто T с вашим типом узла (в данном случае Car) и напишите, что вы хотите

Answer 2

В главе 4 Обоснования Ada 95, часть 2, говорится в разделе 4.3.

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

Для равенства несоответствие тегов рассматривается как неравенство. Только если совпадение тегов является отправкой, выполняется операция проверки равенства для конкретного типа. Этот подход позволяет программе безопасно сравнивать два значения тегового типа для класса на предмет равенства, не проверяя сначала, совпадают ли их теги. Тот факт, что в такой проверке равенства не возникает никаких исключений, согласуется с другими предопределенными реляционными операторами, как отмечено в [RM83 4.5.2(12)].

Таким образом, вы ожидаете, что сможете сказать, например, в FindItem

   Current : Nodeptr := List.Head.Rlink;
begin
   ...
   if Value.all = Current.all then
      --  we’ve found a match

но предопределенное равенство для Car включает в себя Node компоненты Llink, Rlink также.

Требуется операция равенства, которая просто сравнивает Car компоненты.

Вы можете переопределить предопределенное равенство, сказав

type Node is abstract tagged private;
function "=" (L, R : Node) return Boolean is abstract;

а потом

type Car is new Abstlist.Node with record
   Numdoors: Integer;
   Manufacturer: Carname := Gmc;
end record;
overriding
function "=" (L, R : Car) return Boolean is
  (L.Manufacturer = R.Manufacturer and then L.Numdoors = R.Numdoors);

(это синтаксис Ады 2012).