|
Часть 22
Часть 4. Наборы и потоки
Глава 20. Наборы
Программисты на языке Pascal обычно тратят очень много времени на создание кода по манипулированию и обеспечению структур данный, таких как скомпонованные списки и массивы с динамическим установлением размеров. И очень часто один и тот же код имеет тенде
нцию к повторному переписыванию и отладке еще и еще раз.
Что касается традиционного языка Pascal, он лишь предоставляет вам встроенные типы записи и массива. Все другие структуры остаются на ваше усмотрение.
Например, если вы собираетесь хранить данные в массиве, то обычно вам нужно написать код для создания массива, импортирования данных в массив, получение данных массива для обработки, и, возможно, вывода данных на устройство ввода/вывода. Позднее, когда п
отребуется новый тип элемента массива, вы начинаете все с начала.
Было бы замечательно, если бы тип массива поставлялся вместе с кодом, который обрабатывал бы многие из тех операций, которые обычно выполняются на массиве. Это был бы тип массива, который можно было бы расширять без разрушения первоначального кода.
Все это является целью создания типа ObjectWindows TCollection. Это объект, который хранит наборы указателей и обладает набором методов по манипулированию ими.
Объекты наборов
Будучи объектами и тем самым имея встроенные методы, наборы обладают двумя дополнительными чертами, которые имеют отношение к обычным массивам языка Pascal - это динамическое установление размеров и полиморфизм.
Размеры наборов устанавливаются динамически
Размер стандартного массива в Turbo Pascal фиксируется во время компилирования. Это очень хорошо, если вы точно знаете, какой размер должен иметь ваш массив, но может быть не столь хорошо к тому моменту, когда кто-нибудь будет запускать на выполнение ваш
код. Изменение размера массива требует изменения кода и перекомпилирования.
Однако, для наборов вы устанавливаете только их начальный размер, который динамически увеличивается в процессе работы программы, для размещения в нем всех нужных данных. Это делает ваше приложение в его скомпилированном виде значительно более гибким. Одн
ако, следует иметь в виду, что набор не может сжиматься, поэтому следует быть аккуратным и не делать его неоправданно большим.
Полиморфизм наборов
Второй аспект, по которому массивы могут ограничивать ваше приложение, состоит в том, что каждый элемент массива должен иметь один и тот же тип, и этот тип должен быть определен при компилировании кода.
Наборы обходят это ограничение использованием указателей без типа. Это сказывается не только на быстроте и эффективности, но наборы могут состоять из объектов (и даже не из объектов) разного типа и размера. Набору не нужно знать что-либо об объектах, кот
орые он обрабатывает. Он просто организует связь с ними в случае необходимости.
Проверка типа и наборы
Наборы ограничивают традиционную мощную проверку типа языка Pascal. Это означает, что можете поместить нечто в набор и когда вы запрашиваете это назад, компилятор уже не может проверить, ваших предположений относительно объекте. Вы можете поместить нечто
как PHedgehog (ежик), а прочитать назад как PSheep (овца), и набор никак не сможет насторожить вас.
Как программист на языке Turbo Pascal вы вполне оправданно будете нервничать о такой реализации. Проверка типов языка Pascal в конце концов сберегает несколько часов при поиске некоторых достаточно иллюзорных ошибок. Поэтому вы должны принять во внимание
следующее предупреждение: Вы даже представить себе не можете насколько трудно бывает искать ошибки несоответствия типа, поскольку обычно эту работу за вас выполнял компилятор! Однако, если вы обнаружите, что ваша программа сбивается или зацикливается, т
щательно проверьте хранимые типы объектов и считываемые из наборов.
Объединение в набор элементов, не являющихся объектами
Вы даже можете добавить в набор нечто, что вообще не является объектом, но это также может явиться серьезным предметом озабоченности. Наборы ожидают приема указателей незаданного типа на нечто. Но некоторые методы TCollection предназначены специально для
работы на наборах элементов, производных от TObject. Это касается методов доступа к потоку PutItem и GetItem, и стандартной процедуры FreeItem.
Например, это означает, что вы можете хранить PChar в наборе, но при попытке послать этот набор в поток, результаты будут не столь успешными, если вы не перепишете стандартные методы набора GetItem и PutItem. Аналогично, при попытке деаллокации набора бу
дет сделана попытка удаления каждого элемента с помощью FreeItem. Например, это делает TStrCollection.
Если вам удастся преодолеть все эти трудности, вы обнаружите, что наборы (и построенные вами производные наборов) являются быстрыми, гибкими и надежными структурами данных.
Создание набора
Создание набора столь же просто, как и создание типа данных, которые вы хотите в нем хранить. Предположим, что вы - консультант, и вам нужно хранить и искать номер счета, имя и номер телефона каждого из ваших клиентов. Сначала определим тип объекта клиен
та (TClient), который будет хранится в наборе (Не забудьте определить тип указателя для каждого нового типа объекта):
type
PClient=^TClient;
TClient=object(TObject)
Account, Name, Phone: PChar;
constructor Init(NewAccount, NewName, NewPhone: PChar);
destructor Done; virtual;
procedure Print; virtual;
end;
Затем реализуем методы Init и Done для размещения и удаления данных о клиенте и метод Print для отображения данных о клиенте в виде таблицы. Обратите внимание, что поля объекта имеют тип PChar, поэтому память выделяется только для той части строки, котор
ая действительно используется. Функции StrNew и StrDispose очень эффективно обрабатывают динамические строки.
constructor TClient.Init(NewAccount, NewName, NewPhone: PChar);
begin
Account:=StrNew(NewAccount);
Name:=StrNew(NewName);
Phone:=StrNew(NewPhone);
end;
destructor TClientDone;
begin
StrDispose(Account);
StrDispose(Name);
StrDispose(Phone);
end;
procedure TClient.Print;
begin
Writeln( ' ',
Account, '':10 - StrLen(Account),
Name, '':20 - StrLen(Name),
Phone, '':16 - StrLen(Phone));
end;
TClient.Done будет автоматически вызываться для каждого клиента при удалении всего набора. Сейчас вы просто инициируете набор для хранения ваших клиентов и вставляете в него записи о клиентах. Головное тело программы (COLLECT1.PAS) будет выглядеть следую
щим образом:
var
ClientList: PCollection;
begin
ClientList:=New(PCollection, Init(10,5));
with ClientList^ do
begin
Insert(New(PClient, Init('91-100', 'Anders, Smitty',
'(406) 111-2222')));
Insert(New(PClient, Init('90-167', 'Smith, Zelda',
'(800) 555-1212')));
Insert(New(PClient, Init('90-177', 'Smitty, John',
'(406) 987-4321')));
Insert(New(PClient, Init('90-160', 'Johnson, Agatha',
'(302) 139-8913')));
end;
PrintAll(ClientList);
SearchPhone(ClientList, '(406)');
Dispose(ClientList, Done);
end.
Процедуры PrintAll и SearchPhone будут рассмотрены позднее.
Обратите внимание, насколько просто было построить набор. Первый оператор размещает новый экземпляр TCollection с именем ClientList с начальным размером на 10 клиентов. В случае необходимости размещения более 10 клиентов в ClientList, его размер будет у
величиваться каждый раз на 5 клиентов. Следующие два оператора создают новый объект клиента и вставляют его в набор. Вызов Dispose в конце операции освобождает весь набор клиентов.
Нигде не нужно было сообщать набору, какой вид данных предполагается хранить - для этого просто используется указатель.
Методы итератора
Вставка и удаление элемента не являются единственными общими операторами набора. Очень часто вы будете писать циклы for для просмотра всех объектов набора с целью отображения данных или выполнения некоторых вычислений. В других случаях вы будете искать п
ервый или последний элемент набора, который удовлетворяет некоторому критерию поиска. Для этих целей у наборов имеется три метода итератора: ForEach, FirstThat и LastThat. Каждый из них берет указатель на процедуру или функцию в качестве своего единствен
ного параметра.
Итератор ForEach
ForEach берет указатель на процедуру. Процедура имеет один параметр, который является указателем на хранимый в наборе элемент. Для каждого элемента набора ForEach вызывает процедуру один раз, в той последовательности, в которой элементы появляются в набо
ре. Процедура PrintAll в Collect1 показывает пример итератора FoeEach.
procedure PrintAll(C: PCollection);
procedure CallPrint(P: PClient); far;
begin
P^.Print; {Вызов метода Print}
end;
begin {Print}
Writeln;
Writeln;
Writeln('Client list:');
C^.ForEach(@CallPrint); {Распечатка для каждого клиента}
end;
Для каждого элемента набора, переданного в качестве параметра в PrintAll, вызывается вложенная процедура CallPrint. CallPrint просто распечатывает информацию об объекте клиента в отформатированных колонках.
Итераторы должны вызывать удаленные локальные процедуры.
Вам нужно быть аккуратным с сортировкой процедур, которые вы вызываете итераторами. Для того, чтобы быть вызванной итератором, процедура (в данном примере, CallPrint) должна:
- быть процедурой - она не может быть функцией или методом объекта, хотя данный пример показывает, что процедура может вызвать метод.
- быть локальной (вложенной внутрь) относительно вызывающей ее программы.
- быть объявленной как удаленная процедура, директивой far или директивой компилятора {$F+}.
- брать указатель на элемент набора в качестве своего единственного параметра.
Итераторы FirstThat и LastThat
Кроме возможности приложения процедуры к каждому элементу набора, часто бывает очень нужно найти конкретный элемент набора на основании некоторого критерия. Это является предназначением итераторов FirstThat и LastThat. Как это следует из их имен они прос
матривают набор в противоположных направлениях до момента нахождения первого элемента набора, который удовлетворяет критерию булевской функции, переданной в качестве элемента.
FirstThat и LastThat возвращают указатель на первый (или последний) элемент, который удовлетворяет условию поиска. Предположим, что в приведенно ранее примере списка клиентов, вы не можете вспомнить номер счета клиента или не помните точно написание имен
и клиента. К счастью, вы точно помните, что это был ваш первый клиент из штата Монтана. Следовательно, вы можете организовать поиск первого клиента с кодом штата 406 (поскольку ваш список клиентов ведется хронологически). Данная процедура использует мето
д FirstThat, который и сделает всю работу:
procedure SearchPhone(C: PCollection; PhoneToFind: PChar);
function PhoneMatch(Client: PClient: PClient): Boolean; far;
begin
PhoneMatch:=StrPos(Client^.Phone, PhoneToFind) <> nil;
end;
var
FoundClient: PClient;
begin {SearchPhone}
Writeln;
FoundClient:=C^.FirstThat(@PhoneMatch);
if FoundClient=nil then
Writeln('No client met the search requirement')
else
begin
Writeln('Found client:');
FoundClient^.Print;
end;
end;
Снова обратите внимание на то, что PhoneMatch вложен и использует удаленную модель вызова. В этом случае эта функция возвращает True только при совпадении номера телефона клиента и заданного образца поиска. Если в наборе нет объекта, который соответствов
ал бы критерию поиска, FirstThat возвращает указатель nil.
Запомните: ForEach вызывает определенную пользователем процедуру, а FirstThat и LastThat каждая вызывает определенную пользователем булевскую функцию. В любом случае определенная пользователем процедура или функция передают указатель на объект набора.
Отсортированные наборы
Иногда вам бывает нужно, чтобы ваши данные были определенным образом отсортированы. ObjectWindows имеет специальный тип набора, который позволяет вам упорядочить ваши данные произвольным образом, TSortedCollection.
TSortedCollection происходит от TCollection и автоматически сортирует задаваемые ему объекты. При добавлении нового члена он автоматически проверяет набор на дублирование ключей.
Булевское поле, Duplicates, контролирует разрешение дублирования ключей. Если для поля Duplicates установлено значение False (по умолчанию), то новый член добавляется к набору, заменяя существующий член с тем же самым ключом. Если Duplicates имеет значен
ие True, то новый член просто вставляется в набор.
TSortedCollection это набор абстрактного типа. Для его использования вы должны сначала решить, какой тип данных вы собираетесь собирать и определить два метода, отвечающих вашим конкретным требованиям сортировки. Для этого вам нужно сделать новый тип, пр
оизводный от TSortedCollection. В данном случае назовем его TClientCollection.
Ваш TClientCollection уже знает, как делать всю реальную работу с набором. Он может вставить (Insert) запись о новом клиенте и удалять (Delete) существующие записи - он унаследовал эти основные черты поведения от 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.Compare(Key1, Key2: Pointer): Integer;
begin
Compare:=StrIComp(PChar(Key1), PChar(Key2));
end;
KeyOf определяет какое поле или поля используются в качестве ключей сортировки. В данном случае это поле клиента Account. Compare берет два ключа сортировки и определяет, какой из них должен идти первым в соответствии с правилами сортировки. Compare возв
ращает -1, 0 или 1 в зависимости от того, Key1 меньше, равен или больше Key2, соответственно. В данном примере используется сортировка по алфавиту (для прописных и строчных букв) ключевой строки (Account) путем вызова модуля Strings функции StrIComp. Вы
можете легко сортировать набор по именам, вместо номера счета, если замените возвращаемое KeyOf поле на Name.
Обратите внимание на то, что ключи, возвращаемые KeyOf и передаваемые в Compare являются указателями без типа, поэтому вы должны привести их тип к PChar до их различения и передачи в StrIComp в данном примере.
Это практически все, что вам нужно определить ! Теперь, если вы переопределите ClientList как PClientCollection вместо PCollection (сменив объявление var и вызов New), вы легко сможете распечатать ваших клиентов в алфавитном порядке (COLLECT2.PAS):
var
ClientList: PClientCollection;
...
begin
ClientList:=New(PClientCollection, Init(10,5));
...
end.
Обратите внимание и на то, как легко будет сменить сортировку списка клиентов по номеру счета на сортировку по имени. Все что вам нужно сделать, это сменить метод KeyOf на возврат поля Account на поле Name.
Наборы строк
Многим программам требуется работать с отсортированными строками. Для этих целей ObjectWindows предоставляет набор специального назначения, TStrCollection. Обратите внимание, что элементы TStrCollection не объекты - они указатели на строки, заканчивающие
ся пустым символом. Поскольку наборы строк происходят от TSortedCollection, можно хранить и дублированные строки.
Использование наборов строк очень просто. Просто определяется переменная указателя для хранения набора строк. Разместим набор, задав его начальный размер и приращение для роста при добавлении новых строк (COLLECT3.PAS):
var
WordList: PCollection;
WordRead: PChar;
...
begin
WordList:=New(PStrCollection, Init(10,5));
...
WordList первоначально рассчитан для хранения 10 строк с последующим приращением по 5 строк. Все что вам нужно сделать, это вставить несколько строк в набор. В данном примере слова считываются из текстового файла и вставляются в набор:
repeat
...
if GetWord(WordRead, WordFile)^ <> #0 then
WordList^.Insert(StrNew(WordRead));
...
until WordRead[0]=#0;
...
Dispose(WordList, Done);
Обратите внимание, что функция StrNew используется для копирования считанных слов и адрес скопированной строки передается в набор. При использовании набора вы всегда передаете ему контроль над данными набора. Он позаботится о деаллокации данных после раб
оты. Он при этом делает то, что происходит при вызове Dispose: удаляется каждый элемент набора и затем удаляется сам набор WordList.
Пересмотренные итераторы
Метод ForEach просматривает весь набор, элемент за элементом, и выполняет над каждым из них заданную процедуру. В предыдущем примере процедуре PrintWord передавался указатель строки для ее отображения. Обратите внимание, что процедура PrintWord вложенна
я (или локальная). Она работает в другой процедуре, Print, которой дается указатель на TstrCollection. Print использует метод итератора ForEach для передачи каждого элемента своего набора в процедуру PrintWord.
procedure Print(C: PCollection);
procedure PrintWord(P: PChar); far;
begin
Writeln(P); {Высветить строку}
end;
begin {Print}
Writeln;
Writeln;
C^.ForEach(@PrintWord); {Вызов PrintWord}
end;
PrintWord должен выглядеть как уже знакомая процедура. Она просто берет указатель строки и передает его значение Writeln. Обратите внимание на директиву far после объявления PrintWord. PrintWord не может быть методом, это просто процедура. Кроме того, эт
о должна быть вложенная процедура. Print надо рассматривать как некую оболочку вокруг процедуры, которая выполняет некоторую работу над каждым элементом набора, может быть отображает или модифицирует данные. Вы можете иметь несколько аналогичных PrintWor
d процедур, но каждая из них должна быть вложена в Print и должна быть удаленной процедурой( использовать директиву far или {$F+}).
Нахождение элемента
Отсортированные наборы (и следовательно наборы строк) имеют метод Search, который возвращает индекс элемента с конкретным значением ключа. Но как найти элемент в неотсортированном наборе ? Или когда критерий поиска не использует сам ключ ? Конечно же сле
дует использовать FirstThat и LastThat. Вы просто определяете булевскую функцию для проверки нужного вам критерия и вызываете FirstThat.
Полиморфные наборы
Вы уже видели, что наборы могут динамически хранить любой тип данных. и они обладают множеством методов, которые помогают вам организовывать эффективный доступ к данным. В действительности сам TCollection определяет 23 метода. Когда вы используете наборы
в ваших программах вы будете удивлены скоростью их работы: Они разработаны с максимальной гибкостью и реализованы для использования с максимальной скоростью.
Сейчас пришло время рассмотреть действительную мощь наборов, элементы могут обрабатываться полиморфно. Это значит, что вы не просто можете хранить определенный тип объекта в наборе; вы можете хранить несколько разных типов объектов, взятых произвольно из
вашей иерархии объектов.
Если вы рассмотрите приведенные примеры наборов, вы можете заметить, что все элементы каждого набора были одно и того же типа. Мы имели дело со списком строк в котором каждый элемент был строкой. Мы также занимались списком клиентов. Но наборы могут хран
ить любые производные от TObject объекты, и вы можете произвольно смешивать эти объекты. Естественно, что вы желаете, чтобы эти объекты имели нечто общее. На самом деле вам нужно, чтобы у них был общий абстрактный объект-предок.
В качестве примера рассмотрим программу, которая помещает в набор три различных графических объекта. Затем итератор ForEach используется для просмотра набора и отображения каждого объекта.
В отличие от других примеров данной главы данный пример (Collect4) использует функции Windows для рисования в окне. Обязательно включите WinProcs и WinTypes в uses данного примера.
Сначала определяется абстрактный объект-предок.
type
PGraphObject=^TGraphObject;
TGraphObject=object(TObject)
Rect: TRect;
constructor Init(Bounds: TRect);
procedure Draw(DC: HDC); virtual;
end;
Из этого объявления вы можете видеть, что каждый графический объект может инициализировать себя (Init) и отобразить себя на графическом экране (Draw). Теперь определим эллипс, прямоугольник и сектор как производные от этого общего предка:
PGraphEllipse=^TGraphEllipse;
TGraphEllipse=object(TGraphObject)
procedure Draw(DC: HDC); virtual;
end;
PGraphRect=^TGraphRect;
TGraphRect=object(TGraphObject)
procedure Draw(DC: HDC); virtual;
end;
PGraphPie=^TGraphPie;
TGraphPie=object(TGraphObject)
ArcStart, ArcEnd: TPoint;
constructor Init(Bounds: TRect);
procedure Draw(DC: HDC); virtual;
end;
Все эти три типа объекта наследуют полу Rect из TGraphObject, но все они разного размера. TGraphEllipse и TGraphRect нужно только добавить их новые методы рисования, т.к. их методам рисования нужны только размеры и местоположение, а TGraphPie нужны допол
нительные поля и другой конструктор для их корректного представления. Приведем код для помещения этих фигур в набор:
...
GraphicsList:=New(PCollection, Init(10,5)); {Создать набор}
for I:=1 to NumToDraw do
begin
case I mod 3 of {Создать объект}
0: P :=New(GraphRect, Init(Bounds));
1: P :=New(GraphEllipse, Init(Bounds));
2: P :=New(GraphPie, Init(Bounds));
end;
GraphicsList^.Insert(P); {Добавить в набор}
end;
...
Как вы можете видеть цикл for вставляет графические объекты в набор GraphicsList. Все что вы знаете, это то, что каждый объект в GraphicsList есть некоторый вид TGraphObject. После помещения в набор у вас уже нет информации о том, является ли элемент наб
ора прямоугольником, эллипсом или сектором. Благодаря полиморфизму, вам этого и не нужно знать, поскольку каждый объект содержит все данные и код (Draw), который ему нужен. Просмотрим набор с использованием итеративного метода и каждый набор будет сам от
ображать себя:
procedure DrawAll(C: PCollection);
procedure CallDraw(P: PGraphObject); far;
begin
P^.Draw(PaintDC); {Вызов метода Draw}
end;
begin {DrawAll}
C^.ForEach(@CallDraw); {Прорисовать каждый объект}
end;
var
GraphicsList: PCollection;
begin
...
if GraphicsList <> nil then DrawAll(GraphicsList);
...
end.
Способность наборов хранить разные но связанные объекты основывается на мощном краеугольном камне объектно-ориентированного программирования. В следующей главе вы увидите тот же принцип полиморфизма, приложенный к потокам с равными приоритетами.
Наборы и управление памятью
TCollection может динамически расти от начально размера, установленного Init, до максимального размера в 16380 элементов. ObjectWindows хранит максимальный размер набора в переменной MaxCollectionSize. Каждый добавляемый в набор элемент занимает четыре б
айта памяти, т.к. он хранится в виде указателя.
Ни одна библиотека динамических структур данных не будет полной, если она не снабжена средствами обнаружения ошибок. Если для инициализации набора не хватает памяти, то возвращается указатель nil.
Если не хватает памяти при добавлении элемента в набор, то вызывается метод TCollection.Error и возникает ошибка в исполняемой динамической области памяти. Вы можете переписать TCollection.Error для организации собственного метода информирования или испр
авления ошибки.
Вам следует уделить особое внимание доступности динамической области памяти, поскольку у пользователя есть значительно больше контроля над программой ObjectWinodws, чем над обычной программой языка Pascal. Если добавлением объектов в набор управляет поль
зователь (например, открывая новое окно), то ошибку динамической области памяти не так то легко предсказать. Вы можете предпринять некоторые шаги по защите пользователя от фатальной ошибки при выполнении программы, если либо проверяя память сами при испо
льзовании набора, либо обрабатывая сбой исполняемой программы таким образом, чтобы избежать прекращения ее работы.
|