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

Часто бывает необходимо каким-либо образом упорядочить коллекцию, т.е. расставить ее элементы в определенном порядке. Для этих целей в Turbo Vision предусмотрен специальный объект TSortedCollection. Этот объект порожден от TCollection и, следовательно, уже умеет создавать коллекцию, вставлять в нее элементы и удалять их. Единственное, чего он не умеет - это сортировать коллекцию. В TSortedCollection есть абстрактный метод Compare, который используется для упорядочения элементов и который Вы должны перекрыть, чтобы обеспечить нужную Вам сортировку. Таким образом, чтобы создать отсортированную коллекцию, Вы должны создать объект-потомок от TSortedCollection и перекрыть его метод Compare.

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

Например, нам требуется создать отсортированную коллекцию, содержащую каталог библиотеки (см. пример п. 19.3), причем в качестве ключевого используется поле Autor^. Тогда создадим новый объект

type

PSort = Tsort;

TSort = object (TSortedCollection)

Function Compare(Key1, Key2: Pointer): Integer; Virtual; 

end;

чтобы перекрыть метод Compare. Если теперь объявить новый метод TSort.Compare следующим образом:

Function TSort.Compare(Key1, Key2: Pointer): Integer;

var

A: PSort absolute Key1;

B: PSort absolute Key2; 

begin

if A.Autor < BA.Autor then

Compare := -1 else if A.Autor = B.Autor then

Compare := 0 

else

Compare := 1 

end; {TSort.Compare}

то после объявления

var

BookList: PSort;

вместо

var

BookList: PCollection;

программа выведет каталог, отсортированный по фамилиям авторов:

Джордейн Р.

Справочник программиста персональных компьютеров типа IBM PC, XT и AT

Финансы и статистика, 1991, 544 Йенсен К., Вирт Н.

Паскаль. Руководство для пользователя и описание языка финансы и статистика, 1982, 151 Скэнлон Л.

Персональные ЭВМ IBM PC и XT. Программирование на языке ассемблера

Радио и связь, 1991, 336 Шелдон

Язык Си для профессионалов И.В.К.-СОФТ, 1991, 383

Ключевое поле определяется методом TSortedCollection.KeyOf. Этот метод по заданному в качестве параметра обращения указателю на элемент коллекции возвращает указатель на ключевое поле. По умолчанию метод KeyOf возвращает указатель на весь элемент, однако Вы можете перекрыть его новым методом, возвращающим указатель на нужное ключевое поле. Пусть, например, нам требуется отсортировать каталог по году издания книг (поле Year). Добавим в описание объекта TSort перекрытие метода KeyOf:

type

TSort = object (TSortedCollection)

.....

Function KeyOf(Item: Pointer): Pointer; Virtual; 

end ;

Опишем новый метод следующим образом:

Functon TSort.KeyOf(Item: Pointer): Pointer; 

begin

KeyOf := PBook(Item).Yеаr 

end;

и изменим описание метода Compare:

Function TSort.Compare(Key1, Key2: Pointer): Integer; 

var

A: Integer absolute Key1; 

B: Integer absolute Key2; 

begin

if А < B then

Compare := -1

else if А = B then

Compare := 0 

else

Compare := 1

end; {TSort.Compare}

Теперь после запуска программы на экран будет выведено:

Йенсен К., Вирт Н.

Паскаль. Руководство для пользователя и описание языка

Финансы и статистика, 1982, 151

Джордейн Р.

Справочник программиста персональных компьютеров типа IBM PC,

XT и AT

Финансы и статистика, 1991, 544

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

Можно ли поместить в коллекцию два или больше элементов с одинаковыми полями? Turbo Vision позволяет сделать это: поле TSortedCollection.Duplicates по умолчанию содержит FALSE, что указывает на уникальность ключевого поля; если перед наполнением коллекции Вы поместите в это поле значение TRUE, коллекция не будет контролировать уникальность ключевых полей.

Изменим начало раздела исполняемых операторов главной программы следующим образом:

begin

Bookiist := New(PSort, Init(50,10) ) ;

with BookList do

begin

Duplicates := True; {Отменяем уникальность ключей}

......

end;

.....

end.

Теперь на экран будет выведено:

Йенсен К., Вирт Н.

Паскаль. Руководство для пользователя и описание языка Финансы и статистика, 1982, 151 Скэнлон Л.

Персональные ЭВМ IBM PC и XT. Программирование на языке ассемблера

Радио и связь, 1991, 336 Шелдон

Язык Си для профессионалов И.В.К.-СОФТ, 1991, 383 Джордейн Р.

Справочник программиста персональных компьютеров типа IBM PC, XT и AT Финансы и статистика, 1991, 544

Заметим, что, очередной элемент вставляется перед первым элементом с равным значением ключевого поля. Точно также поиск First.That вернет указатель на первый из нескольких элементов с одинаковыми ключевыми полями, а метод LastThat - на последний из них.