ГЛАВА 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 гораздо
больше возможностей, чем в традиционной программе на Паскале. Если
пользователь управляет добавлением объектов в коллекцию (например
открывая новые окна на панели экрана), не всегда будет просто
предупредить ошибку кучи. Вам может понадобиться предпринять ряд
шагов для защиты пользователя от фатальной ошибки времени
выполнения либо используя собственные проверки памяти при работе с
коллекцией, либо обработчик ошибок времени выполнения.
Назад | Содержание | Вперед