Использование Generic-ов (FPC)
  Еще о Generic-ах: Часть 2
   

Я уже приводил несколько способов написания модулей обработки данных, независимо от их типа...

Например, здесь описывался метод, при котором части Interface и Implementation модуля реализуются в отдельных файлах, и включаются в собственно модуль директивами {$I <файл_описания_интерфейса>} и {$I <файл_описания_реализации>}. Там же приведены и недостатки этого метода.

Немного более эффективным является метод, работающий при использовании компилятора FPC, описанный вот тут (с перегрузкой операторов)... Этот метод уже лучше, но все равно не лишен недостатков, в частности, все так же нельзя в одной и той же программе использовать структуру с разными типами данных.

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

С выходом в свет версии 2.2.0 компилятора FPC для решения поставленной задачи можно пользоваться дженериками (Generics), которые представляют собой нечто вроде макросов для компилятора, которые "раскрываются" при специализации дженерика.

Попробуем с помощью дженериков реализовать ту же самую задачу, которая приводилась как тест класса TQueue здесь :

"Каким бы образом сделать так, чтобы на вывод шёл не только первый встреченный искомый элемент с его местоположением (ну например максимальный), но и другие равные ему, с их родными индексами?"


Первое, что нам для этого понадобится - это написание собственно класса Очереди... Ну, поскольку он уже написан: Очередь (FIFO: First In First Out), то я возьму этот готовый класс и немного его подкорректирую для использования новых возможностей...
  1. Первый шаг - описываем шаблонный класс TQueue:

    (T в данном случае - spaceholder, т.е., при специализации на место T будет подставлен конкретный тип данных)
    type
      generic
      tqueue<T> = object
    
      // В этой секции будут описываться типы, которые специфичны для данного класса (локальные типы).
      // Ими можно будет пользоваться только внутри класса, извне они недоступны... Кроме этого, для
      // типов можно задать область видимости, которая будет соблюдаться при наследовании.
      
      (*
        Что касается поставленной задачи - поскольку тип Titem используется исключительно внутри класса,
        я задал его как локальный тип, из основной программы к нему нельзя будет обратиться. Все действия
        над элементами очереди будут производиться посредством вызова процедуры ForEach, в которой это
        действие и будет определено для отдельного элемента.
      *)
      type public
    
        TForEach = procedure(value: T);
        PTitem = ^Titem;
        Titem = record
          info: T;
          next: PTitem;
        end;
    
      // То же самое - для локальных переменных...
      
      (*
        В данном случае - локальные переменные head и tail объявлены частными, т.е., они не будут доступны
        даже наследникам класса TQueue (принцип упрятывания информации)
      *)
      var private
        head, tail: ptitem;
    
      public
    
        (*
          Здесь все осталось, как и было раньше, за исключением того, что добавлена процедура ForEach
        *)
        constructor init;
        destructor done;
    
        procedure put(x: T);
        function get(var value: T): boolean;
        procedure clear;
    
        function empty: boolean;
        procedure ForEach(p : TForEach);
      end;
    
    Примечание:

    К сожалению, на данный момент, описание области видимости в Generic-классах не изменяет область видимости на самом деле: независимо от указанного спецификатора все переменные / типы / методы имеют public уровень доступа (описано в mantis как баг компилятора, будем ждать исправления).

  2. Второе - реализация методов шаблонного класса. В отличие от С++, здесь не нужно указывать, что метод является шаблонным при его реализации, компилятор сам прекрасно разбирается в этом. Для примера - ForEach:
    // Получаем процедуру, которая будет применяться к каждому элементу очереди ...
    procedure tqueue.ForEach(p : TForEach);
    var pt: ptitem;
    begin
      // ... и для всех элементов - вызываем переданную процедуру
      pt := head;
      while assigned(pt) do begin
        p(pt^.info); // <--- передавая ей сам элемент в качестве параметра.
                     // Пускай она и разбирается, что с ним делать...
        pt := pt^.next
      end;
    end;
    
  3. Третье. После того, как был описан шаблон очереди, и создана реализация методов, осталось специализировать шаблон каким-то типом, чтобы с ним можно было начинать работать. А этот тип (если он не является базовам типом Паскаля) нужно предварительно создать. Ну, поскольку я рассматриваю уже готовый пример, то и работать я тоже хочу с тем же типом (pair), с которым работал и раньше...

    Но тут есть небольшое изменение - программа упрощается тем, что мне уже нет никакой необходимости наследовать pair от какого-то базового типа, поскольку теперь (при реализации ДСД на Generic-ах) можно реализовать очередь с любым независимым типом данных. Поэтому опишем pair не как объект, а как структуру:
    type
      // Определим сам тип Pair
      pair = record
        one, two: integer;
      end;
    
    // ... функцию для удобной инициализации переменной этого типа
    // (для того, чтобы можно было ее использовать непосредственно в выражениях) ...
    function _pair(a, b: integer): pair;
    begin
      result.one := a; result.two := b;
    end;
    
    // ... ну и процедуру, которая, собственно, и будет использоваться
    // для вывода на экран содержимого очереди
    
    procedure print_pair(value: pair);
    begin
      write('<', value.one, ':', value.two, '> ');
    end;
    
  4. Этап четвертый - собственно специализация:
    // Указываем компилятору тот тип данных, с которым будет использоваться очередь типа pairQueue ...
    type
      pairQueue = specialize TQueue<pair>;
    // ... и объявляем переменную этого типа ...  
    var
      q: pairQueue;
    ...  
    
    Объявление типа pairQueue сделано не случайно - дело в том, что специализировать Generic-и можно только в разделе Type, но нельзя конструировать новые типы при описании переменных. Это чем-то напоминает запрет на подобные описания:
    // Нельзя !!!
    procedure P(var arr: array[1 .. 20] of integer);
    
    // Хотя вот это вполне допустимо:
    type
      Tarr = array[1 .. 20] of integer;
     procedure P(var arr: Tarr);
    
    За подобным ограничением стоит не что иное, как правила эквивалентности типов: два описанных в разных местах типа (даже совершенно одинаковых с точки зрения программиста) считаются компилятором разными:
    type
      TA = array[1 .. 10] of integer;
      TB = array[1 .. 10] of integer;
    var
      A: TA; B: TB;
    begin
      A := B; // <--- Нельзя, типы разные !!!
    end.
    
    При специализации действует то же правило. Если бы можно было написать:
    var
      qa: TQueue<integer>;
      qb: TQueue<integer>;
      
    ...
      qa := qb; // <--- здесь была бы ошибка
    
    Вышеуказанное ограничение (на специализацию только в разделе type) как раз и призвано уменьшить количество подобных ошибок.

  5. Ну, и пятый этап - написание основной программы. Здесь тоже произошли некоторые изменения:
    type
      pairQueue = specialize TQueue<pair>;
    var
      q: pairQueue;
      max, i, j: integer;
    
    begin
      // При инициализации очереди теперь нет необходимости "запоминать" тип элементов,
      // с которым она работает - попытки записать в очередь элемент другого типа будут
      // отловлены еще на этапе компиляции
      
      q.init;
      max := - maxint;
    
      for i := 1 to n do begin
        for j := 1 to n do begin
    
          if arr[i, j] > max then begin
            max := arr[i, j];
            q.clear;
            q.put(_pair(i, j));
          end
          else
            if arr[i, j] = max then
              q.put(_pair(i, j));
    
        end;
      end;
    
      q.ForEach(@print_pair);  // Вот так теперь распечатывается очередь
      q.done;
    end.
    
Полностью описание шаблона и тестовая программа доступны здесь: queue_gnr.rar

В процессе подготовки: generic-и и наследование, generic-и м перегрузка операций/функций



Free Web Hosting