ГЛАВА 7. КОЛЛЕКЦИИ.

     Программисты на Паскале традиционно тратят  много  времени  на
создание кода,  который  поддерживает  структуры данных,  такие как
связанные списки и динамические массивы.  В дейсвительности один  и
тот же  код  структуры данных переписывается и отлаживается снова и
снова.
     Традициооный Паскаль  обеспечивает  только встроенные записи и
массивы. Остальные структуры Вы должны разрабатывать сами.
     Например, если  Вы  собираетесь хранить данные в массиве,  Вам
необходимо написать код для создания массива, импортирования данных
в массив,  выборки данных из массива для обработки и, вероятно, для
вывода данных  на  устройство  В/В.  Позже,   когда   в   программе
потребуется новый тип элементов массива, Вы начнете все сначала.
     Было бы хорошо,  если бы тип массива поступал вместе с  кодом,
который будет обрабатывать большинство операций,  который Вы обычно
производите с массивом,  или если бы этот тип  массива  можно  было
расширить не изменяя оригинальный код.
     В этом назначение типа TCollection в Turbo Vision. Это объект,
который хранит  набор  указателей и предоставляет встроенные методы
для манипуляции ими.

Объекты коллекции.

     Поскольку коллекция  -  это  объект  и,  следовательно,  имеет
методы, встроенные в него,  она имеет 2 дополнительные  возможности
по сравнению   с   массивами   Паскаля   -  динамический  размер  и
полиморфизм.

Динамический размер.

     Размер стандартных  массивов Turbo Pascal фиксируется во время
компиляции и  это  удобно,  если  Вы  точно  знаете  размер  Вашего
массива, но  во  время  работы  Вашей  программы  он  иногда  может
заполняться не  полностью.  Изменение   размера   массива   требует
изменения кода и перекомпиляции.
     Для коллекции Вы устанавливаете первоначальный размер,  но  он
может динамически   увеличиваться   во   время   выполнения,  чтобы
соответствовать данным, хранящимся в нем. Это делает Вашу программу
более гибкой в ее компилированном виде.

Полиморфизм.

     Второе свойство массивов, которое может стать ограничением для
Вашей программы  в  том,  что  каждый  элемент  массива должен быть
одного типа и этот тип определяется во время компиляции.
     Коллекции обходят  это  ограничение,  используя нетипированные
указатели. Это не  только  быстро  и  эффективно,  но  и  позволяет
коллекции содержать  объекты  (и даже не объекты) различных типов и
размеров. Так же как поток,  коллекция не должна  ничего  знать  об
обрабатываемых объектах. Она только хранит их и выдает по запросу.

Проверка типов и коллекции.

     Коллекция обходит строгую проверку типа традиционного Паскаля.
Это означает, что Вы можете поместить в коллекцию что-либо и, когда
Вы выбираете эти данные обратно, компилятор не может проверить Ваши
предположения об этих данных.  Вы можете поместить в коллекцию один
объект и прочитать его обратно как  другой  и  коллекция  не  имеет
возможности предупредить Вас об этом.
     Как программист  на  Turbo  Pascal,   Вы   можете   испытывать
определенный дискомфорт  в  этой ситуации.  Проверка типов Паскаля,
кроме всего прочего,  сохраняет многие часы отлавливания  некоторых
неуловимых ошибок.  Слушайте внимательно: Вы можете не беспокоиться
о трудностях нахождения таких ошибок,  поскольку компилятор  найдет
их за   Вас!   Однако,  если  Ваша  программа  зависает,  тщательно
проверьте типы объектов, сохраняемых и извлекаемых из коллеций.

Коллекции не объектов.

     Вы можете  так  же добавить в коллекцию данные,  не являющиеся
объектами, но это приведет к другой серьезной  проблеме.  Коллекции
ожидают получить нетипированные указатели на что-либо. Но некоторые
методы TCollection   предназначены    для    обработки    коллекций
экземпляров, порожденных  от  TObject.  Они  включают в себя методы
доступа к потоку PutItem и GetItem,  а так же стандартную процедуру
FreeItem.
     Это означает,  что Вы можете сохранить PString в коллекции, но
если Вы  попытаетесь  передать  эту коллекцию в поток,  Вы получите
неудовлетворительные результаты,  если  не  перекроете  стандартные
методы GetItem и PutItem. Аналогично, когда Вы пытаетесь освободить
коллекцию, она освобождает каждый элемент, используя FreeItem. Если
Вы хотите  использовать  в коллекции элементы не типа TObject,  Вам
необходимо переопределить смысл "элемента"  в  GetItem,  PutItem  и
FreeItem. В TStringCollection, например, делается именно это.
     Если Вы работаете с осторожностью,  Вы  найдете  коллекции  (и
объекты, порожденные    от    коллекций)    быстрыми,   гибкими   и
настраиваемыми структурами данных.

Создание коллекции.

     Создать коллекцию  так  же просто,  как определить тип данных,
который Вы хотите хранить. Предположим, что Вы консультант и хотите
хранить и  использовать  табельный  номер,  имя  и  номер  телефона
каждого из Ваших клиентов.  Для начала  определите  объект  клиента
(TClient), который будет храниться в коллекции:

     {Не забудьте определить указатель на каждый новый тип объекта}
     type
       PClient = ^TClient;
       TClient = object(TObject)
         Account, Name, Phone: PString;
         constructor Init(NewAccount, NewName, NewPhone: String);
         destructor Done; virtual;
       end;

     Затем Вы реализуете методы Init и  Done  для  распределения  и
освобождения данных   клиента.   Заметим,  что  поля  объекта  типа
PString, так что  память  распределяется  только  под  используемую
часть строки. Функции NewStr и DisposeStr обрабатывают динамические
строки очень эффективно.

     constructor TClient.Init(NewAccount, NewName, NewPhone:
                              String);
     begin
       Account := NewStr(NewAccount);
       Name := NewStr(NewName);
       Phone := NewStr(NewPhone);
     end;

     destructor TClient.Done;
     begin
       Dispose(Account);
       Dispose(Name);
       Dispose(Phone);
     end;

     TClient.Done вызывается  автоматически для каждого клиента при
удалении всей коллекции. Сейчас Вы создадите коллекцию для хранения
Ваших клиентов  и  вставите  записи  клиентов  в нее.  Тело главной
программы:

     { TVGUID17.PAS }
     var
       ClientList: PCollection;

     begin
       ClientList := New(PCollection, Init(50, 10));
       with ClientList^ do
       begin
         Insert(New(PClient, Init('90-167', 'Smith, Zelda',
                '(800) 555-1212')));
         Insert(New(PClient, Init('90-160', 'Johnson, Agatha',
                '(302) 139-8913')));
         Insert(New(PClient, Init('90-177', 'Smitty, John',
                '(406) 987-4321')));
         Insert(New(PClient, Init('90-160', 'Anders Smitty',
                '(406) 111-2222')));
       end;
       PrintAll(ClientList);
       SearchPhone(ClientList, '(406)');
       Dispose(ClientList, Done);
     end.

     Заметьте как  легко   создать   коллекцию.   Первый   оператор
распределяет  новую TCollection с именем ClientList,  который имеет
начальный размер 50 клиентов.  Если в ClientList вставлено более 50
клиентов, ее размер увеличивается с шагом 10 клиентов.  2 последних
оператора создают новый объект клиента и вставляют его в коллекцию.
Dispose освобождает всю коллекцию.
     Вы нигде не говорили коллекции,  какого вида данные она  будет
хранить - ей только передан указатель.

Итерационные методы.

     Вставка и удаление являются не  единственными  операциями  над
коллекциями. Часто Вы пишете циклы for для прохода по всем объектам
коллекции для   отображения   данных   или   выполнения   некоторых
вычислений. Так  же  часто  необходимо  найти  первый или последний
элемент в коллекции,  удовлетворяющий  определенному  условию.  Для
этих целей   коллекция   имеет   3  итерационных  метода:  ForEach,
FirstThat и  LastThat.  Каждый  из  них  использует  указатель   на
процедуру или функцию как единственный параметр.

Итератор ForEach.

     ForEach берет указатель на процедуру.  Эта процедура  имеет  1
параметр -  указатель на элемент,  хранящийся в коллекции.  ForEach
вызывает эту процедуру 1  раз  для  каждого  элемента  коллекции  в
порядке, в  котором  элементы  появляются  в  коллекции.  Процедура
PrintAll в TVGUID17 приводит пример итератора ForEach.

     procedure PrintAll(C: PCollection);

       procedure PrintClient(P : PClient); far;
       begin
         with P^ do
           Writeln(Account^, '':20-Length(Account^),
                   Name^, '':20-Length(Name^),
                   Phone^, ''20-Length(Phone^));
       end;

     begin
       Writeln;
       Writeln;
       C^.ForEach(@PrintClient); { вызывает PrintClient для каждого
                                   элемента из С}
     end;

     Для каждого  элемента коллекции,  передаваемого как параметр в
PrintAll, вызывается вложенная процедура  PrintClient.  PrintClient
просто печатает  информацию  объекта  о  клиенте  в форматированном
виде.
     Вам необходимо   осторожно   выбирать  процедуры,  которые  Вы
вызываете с итераторами.  В этом примере  PrintClient  должна  быть
процедурой -  она не может быть методом объекта - и она должна быть
локальной (вложенной в тот же блок) в программе,  которая  вызывает
ее. Она  так  же должна быть объявлена как дальняя процедура либо с
помощью директивы far,  либо с помощью директивы  компилятора  $F+.
Наконец, процедура должна использовать один параметр - указатель на
элемент коллекции.

Итераторы LastThat и FirstThat.

     В дополнении  к  возможности  применять  процедуру  к  каждому
элементу коллекции  часто  необходимо  найти  определенный  элемент
коллекции на  основании  заданного  критерия.  Это делают итераторы
FirstThat и LastThat. Они просматривают коллекцию в противоположных
направлениях до  тех пор,  пока не найдут элемент,  соответствующий
критерию булевской функции, переданной как аргумент.
     FirstThat и  LastThat  возвращают  указатель  на  первый  (или
последний) элемент,   который   соответствует   условиям    поиска.
Рассмотрим предыдущий пример списка клиентов и вообразим, что Вы не
можете вспомнить номер клиента  или  как  точно  пишется  его  имя.
Однако  Вы  помните,  что  это  был первый клиент из штата Montana.
Поэтому Вы будете искать первое вхождение  клиента  с  кодом  штата
406. Процедура, выполняющая этот поиск:

     procedure SearchPhone(C: PClientCollection;
                           PhoneToFind: String);

       function PhoneMatch(Client: PClient): Boolean; far;
       begin
         PhoneMatch := Pos(PhoneToFind, Client^.Phone^) <> 0;
       end;

     var
       FoundClient: PClient;
     begin
       FoundClient := C^.FirstThat(@PhoneMatch);
       if FoundClient = nil then
         Writeln('No client met the search requirement')
       else
         with FoundClient^ do
           Writeln('Found client: ', Account^, ' ', Name^, ' ',
                   Phone^);
     end;

     Опять заметим,  что  PhoneMatch вложенная и использует дальнюю
модель вызова.  Эта  функция  возвращает  True  только  если  номер
телефона клиента  и  шаблон поиска совпадают.  Если в коллекции нет
объекта, соответствующего критерию поиска,  возвращается  указатель
nil.
     Запомните: ForEach    вызывает     процедуру,     определенную
пользователем, а  FirstThat  и LastThat вызывают булевскую функцию,
определенную пользователем. Во всех случаях им передается указатель
на объект в коллекции.

Отсортированные коллекции.

     Иногда Вам  необходимо  иметь  Ваши  данные   в   определенном
порядке. Turbo   Vision  обеспечивает  специальный  тип  коллекции,
который позволяет  Вам  упорядочить  Ваши  данные  любым  способом:
TSortedCollection.
     TSortedCollection порожден  от  TCollection  и   автоматически
сортирует получаемые  объекты.  Он  так  же автоматически проверяет
коллекцию, когда   добавляется   новый    элемент    и    отвергает
дублированные элементы.
     TSortedCollection - это абстрактный  тип.  Чтобы  использовать
его, Вы должны вначале решить,  какой тип данных Вы будете помещать
в коллекцию  и  определить  2   метода,   соответствующие   способу
сортировки. Чтобы   сделать  это,  Вам  нужно  породить  новый  тип
коллекции от  TSortedCollection.  В  нашем   случае   назовем   его
TClientCollection.
     Ваш TClientCollection уже знает  как  делать  всю  работу  над
коллекцией. Он  может  вставить  новые  записи  клиентов  и удалить
существующие, поскольку   наследует   все   основы   поведения   от
TCollection. Вам необходимо только научить TClientCollection, какое
поле использовать  как  ключ  сортировки  и  как  сравнивать   двух
клиентов и  определять,  какой  из  них  находится  перед  другим в
коллекции. Вы делаете это,  перекрывая методы  KeyOf  и  Compare  и
реализуя их как показано здесь:

     PClientCollection = ^TClientCollection;
     TClientCollection = object(TSortedCollection)
       function KeyOf(Item: Pointer): Pointer; virtual;
       function Compare(Key1, Key2: Pointer): Integer; virtual;
     end;

     function TClientCollection.KeyOf(Item: Pointer): Pointer;
     begin
       KeyOf := PClient(Item)^.Name;
     end;

     function TClientCollection.Compare(Key1, Key2: Pointer):
                                        Integer;
     begin
     {необходимо использовать приведение типа для ключей, поскольку
      они - нетипированные указатели }
       if PString(Key1)^ = PString(Key2)^ then
         Compare := 0
       else if PString(Key1)^ < PString(Key2)^ then
         Compare := -1
       else
         Compare := 1;
     end;

     KeyOf определяет,  какое  поля  или поля должны использоваться
как ключ сортировки.  В нашем  случае  -  это  поле  Name  клиента.
Compare берет  2  ключа сортировки и определяет какой из них должен
стоять первым. Compare возвращает -1, 0 или 1 взависимости от того,
является ли  Key1  меньше,  равным  или  больше  Key2.  Этот пример
использует алфавитную сортировку строк ключей.
     Заметим, что    поскольку    ключи,   возвращаемые   KeyOf   и
передаваемые Compare -  нетипированные  указатели,  Вам  необходимо
выполнить приведение типа в PString до ссылки на них.
     Это все,  что  Вы   должны   определить!   Сейчас,   если   Вы
переопределите ClientList  как PClientCollection вместо PCollection
(изменив объявление  var  и  вызов  New),  Вы  распечатаете   Ваших
клиентов в алфавитном порядке.


     { TVGUID18.PAS }
     var
       ClientList: PClientCollection;
     .
     begin
       ClientList := New(PClientCollection, Init(50, 10));
       .
     end;

     Заметьте как   просто   сделать  распечатку  списка  клиентов,
отсортированного по номерам,  а не по имени.  Вам необходимо просто
изменить метод KeyOf на возврат поля ACount вместо поля Name.

Коллекции строк.

     Многим программам необходимо хранить  отсортированные  строки.
Для этого   Turbo   Vision   предоставляет   специальную  коллекцию
TStringCollection. Заметим,  что элементы  TStringCollection  -  не
объекты, это указатели на строки Turbo Pascal.  Поскольку коллекция
строк наследуется от  TSortedCollection,  дублированные  строки  не
сохраняются.
     Использовать коллекции   строк   просто.    Просто    объявите
переменную указателя  на коллекцию строк.  Распределение коллекции,
задание начального размера и приращение  при  расширении  коллекции
определены:

     { TVGUIDE19.PAS }
     var
       WordList: PCollection;
       WordRead: String;
       .
     begin
       WordList := New(PStringCollection, Init(10, 5));
       .


     WordList первоначально хранит 10 строк,  а затем увеличивается
с приращением 5.  Все,  что Вы делаете - это  вставляете  строки  в
коллекцию. В  этом  примере  слова  читаются  из текстового файла и
вставляются в коллекцию:

     repeat
       .
       if WordRead <> '' then
         WordList^.Insert(NewStr(WordRead));
         .
     until WordRead = '';
     .
     Dispose(WordList, Done);

     Заметим, что  функция  NewStr  используется для создания копии
слова, которое было прочитано,  и адрес копии строки  передается  в
коллекцию. Когда  используется  коллекция,  Вы  всегда передаете ей
управление над собираемыми данными. Она будет тщательно освобождать
данные, когда Вы закончите работу. Это будет соответствовать вызову
Dispose; он  освобождает  каждый   элемент   коллекции,   а   затем
освобождает саму коллекцию WordList.

Опять итераторы.

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

     procedure Print(C: PCollection);

     procedure PrintWord(P : PString); far;
     begin
       Writeln(P^);
     end;

     begin { Print }
       Writeln;
       Writeln;
       C^.ForEach(@PrintWord);
     end;


     Вызов PrintWord   выглядит  привычно.  Это  просто  процедура,
которая берет  указатель  на  строку  и  передает  его  значение  в
Writeln. Заметим директиву far в объявлении PrintWord. PrintWord не
может быть  методом  -  она  должна  быть  процедурой.   (Процедура
CallDraw в  TVGUID20.PAS  показывает  как  вызвать  метод  в вызове
итератора). Она так же должна быть вложенной процедурой.  Вы можете
использовать более одной процедуры,  такой как PrintWord, но каждая
должна быть вложена в Print и должна быть дальней процедурой.

Поиск элемента.

     Отсортированные коллекции  (и  следовательно  коллекции строк)
имеют метод Search,  который возвращает индекс элемента с  заданным
ключем.  Как  Вам найти элемент в неотсортированной коллекции?  Или
как найти элемент,  когда критерий поиска не включает ключ? Конечно
необходимо использовать FirstThat и LastThat. Вы просто определяете
булевскую функцию с нужным критерием поиска и вызываете FirstThat.

Полиморфные коллекции.

     Вы видите,  что  коллекции  могут  хранить  любой  тип  данных
динамически и что они содержат методы,  помогающие  Вам  эффективно
обращаться к   данным  коллекции.  В  действительности  TCollection
определяете 23 метода.  Когда  Вы  используете  коллекции  в  Ваших
программах, Вы удивитесь скорости их работы. Они спроектированы для
обеспечения гибкости и реализованы на удивление быстрыми.
     Сейчас Вы  увидите  реальную  мощь  коллекций:  элементы могут
обрабатываться полиморфно.  Это  означает,  что  Вы  можете  делать
больше, чем  просто  сохранять  тип объекта в коллекции;  Вы можете
хранить множество  различных  типов  объектов  из  любого  места  в
иерархии объектов.
     В примерах,  которые мы рассматривали до сих пор, все элементы
коллекции были  одного  типа.  Но  коллекции  могут  хранить  любые
объекты, порожденные от TObject и Вы можете свободно  смешивать эти
объекты. Обычно   Вам   необходимо  иметь  объекты  с  определенным
сходством.
     Как пример рассмотрим программу,  которая помещает 3 различных
графических объекта   в   коллекцию.   Затем    итератор    ForEach
используется для   прохода   по  коллекции  и  отображения  каждого
объекта.
     Этот пример  использует  модуль Graph и драйверы BGI,  поэтому
выо время компиляции GRAPH.TPU должен быть  в  текущем  справочнике
или в  справочниках  модулей  (Options/Directories/Unit Directory).
При выполнении  программы  перейдите   в   справочник,   содержащий
драйверы .BGI  или модифицируйте вызов InitGraph,  чтобы указать их
расположение (например C:\TP\BGI).
     Вначале определим объект абстрактного предка.

     { TVGUID20.PAS }
     type
       PGraphObject = ^TGraphObject;
       TGraphObject = object(TObject)
         X,Y: Integer;
         constructor Init;
         procedure Draw; virtual;
       end;

     Вы видите из этого объявления,  что каждый графический  объект
может инициализироваться   (Init)  и  отображаться  на  графическом
экране (Draw).  Теперь определим точку, окружность и прямоугольник,
наследуя их от общего предка:

     PGraphPoint = ^TGraphPoint;
     TGraphPoint = object(TGraphObject)
       constructor Init;
       procedure Draw; virtual;
     end;

     PGraphCircle = ^TGraphCircle;
     TGraphCircle = object(TGraphObject)
       Radius: Integer;
       constructor Init;
       procedure Draw; virtual;
     end;

     PGraphRect = ^TGraphRect;
     TGraphRect = object(TGraphObject)
       Width, Height: Integer;
       constructor Init;
       procedure Draw; virtual;
     end;

     Эти 3 объекта наследуют поля X и Y от PGraphObject,  но  имеют
различные размеры.  PGraphCircle  добавляет  Radius,  а  PGraphRect
добавляет Width и Height. Следующий код создает коллекцию:

     .
     List := New(PCollection, Init(10, 5));

     for I := 1 to 20 do
     begin
       case I mod 3 of
         0: P := New(PGraphPoint, Init);
         1: P := New(PGraphCircle, Init);
         2: P := New(PGraphRect, Init);
       end;
       List^.Insert(P);
     end;
     .

     Как Вы видите,  цикл for вставляет 20 графических  объектов  в
коллекцию List.  Все,  что Вы знаете,  это то,  что каждый объект в
List - какого-то из типов от  TGraphObject.  После  того,  как  они
вставлены в коллекцию, неважно какой из элементов окружность, точка
и прямоугольник.  Благодаря полиморфизму Вам не нужно знать сколько
данных  содержит  каждый  объект  и какой код (Draw) ему требуется.
Просто пройдем  по  коллекции,  используя  метод итератора и каждый
объект отобразит себя сам:

     procedure DrawAll(C: PCollection);

     procedure CallDraw(P : PGraphObject); far;
     begin
       P^.Draw;
     end;

     begin { DrawAll }
       C^.ForEach(@CallDraw);
     end;

     var
       GraphicsList: PCollection;
     begin
       .
       DrawAll(GraphicsList);
       .
     end.

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

Коллекции и управление памятью.

     TCollection может   динамически   расти   от   первоначального
размера, установленного в  Init  до  максимального  размера  16,380
элементов. Максимальный  размер  коллекции  хранится  в  переменной
MaxCollectionSize Turbo  Vision.   Каждый   элемент,   который   Вы
добавляете в  коллекцию,  требует только 4 байта памяти,  поскольку
элемент хранится как указатель.  Библиотека  динамических  структур
данных не   будет   полной,   если   ее   не  обеспечить  средством
обнаружения ошибок.  Если для инициализиции коллекции  недостаточно
памяти,  возвращается указатель nil. Если при добавлении элемента в
TCollection недостаточно памяти, вызывается метод TCollection.Error
и   генерируется  ошибка  времени  выполнения  в  куче.  Вы  можете
перекрыть TCollection.Error,  чтобы самому  выдавать  сообщение  об
ошибке или реализовать механизм восстановления.
     Вы должны обратить особое внимание на обработку  ошибок  кучи,
поскольку пользователь  имеет  в  программе  Turbo  Vision  гораздо
больше возможностей,  чем в традиционной программе на Паскале. Если
пользователь управляет  добавлением  объектов в коллекцию (например
открывая новые окна на  панели  экрана),  не  всегда  будет  просто
предупредить ошибку  кучи.  Вам  может понадобиться предпринять ряд
шагов для  защиты  пользователя   от   фатальной   ошибки   времени
выполнения либо  используя собственные проверки памяти при работе с
коллекцией, либо обработчик ошибок времени выполнения.  

                              Назад | Содержание | Вперед