Текст книги "Фундаментальные алгоритмы и структуры данных в Delphi"

Автор книги: Джулиан Бакнелл

сообщить о нарушении

Текущая страница: 4 (всего у книги 36 страниц)

Тестовый каркас Dunit можно найти в Internet по адресу http://dunit.sourceforge.net. Все коды, приведенные в книге, были протестированы с помощью тестов, написанных с использованием Dunit. Некоторые тесты включены в материалы, сопровождающие книгу, которые доступны на Web-сайте издательства.

Отладка

При разработке приложений всегда наступает момент, когда приходится переходить к поиску и устранению ошибок. В настоящей книге мы не будем подробно описывать процесс отладки, давать советы по использованию отладчика и описывать методы поиска и устранения основных типов ошибок. Здесь будут приведены лишь основные правила, которые позволят читателю существенно упростить сам процесс отладки. Все они взяты из книги Роббинса (Robbins) [19].

–

Правило отладки № 1. Выбирайте воспроизводимый случай тестирования.

–

По нечеткому описанию проблемы можно обнаружить только самые простые ошибки. Тестовый случай, который при необходимости может воспроизвести ошибку, – это, по крайней мере, 90% на пути к ее обнаружению и устранению. Возможность воспроизведения ошибки позволяет с помощью отладчика определить место, где она возникает. Если же у вас нет теста, который может воспроизвести ошибку, то у вас нет и надежды.

Второе правило отладки намного сложнее.

–

Правило отладки № 2. Исходите из того, что ошибка внесена вами.

–

Может быть, вы неправильно используете API-интерфейс операционной системы или библиотека компонентов требует определенной последовательности операций. Или, в конце концов, может быть, вызываемая вами функция не может принимать nil в каком-либо входном параметре. Маловероятно, чтобы ошибка была вызвана неправильной работой API-интерфейса или компилятора. Более вероятно, что ошибка присутствует в библиотеке компонентов, тем не менее, попытайтесь выделить проблему (см. правило отладки 1), что позволит с уверенностью сказать, что ошибка находится не в вашем коде. Конечно, если ошибка находится не в вашем коде, ваша задача только усложняется, поскольку придется положиться на разработчиков операционной системы, компилятора или библиотеки компонентов, что они достаточно быстро устранят имеющуюся проблему.

Следующее правило вытекает из уже рассмотренного нами материала.

–

Правило отладки № 3. Для проверки того, что код работает, как того ожидалось, используйте утверждения.

–

Кроме того, можно применять и протоколирование, которое позволит отслеживать состояние различных объектов.

А теперь перейдем собственно к отладке.

–

Правило отладки № 4. Используйте автоматизированные инструментальные средства отладки.

–

Возможно, ваша ошибка вызвана перезаписью какой-то области памяти или получением доступа к памяти после того, как она была освобождена, либо, скажем, при вызове API-функции не проверяется код возвращаемой ошибки. Все описанные типы проблем можно обнаружить в таком автоматизированном средстве отладки, как TurboPower Sleuth QA Suite. Приобретите средство отладки и используйте его не только в процессе тестирования, но и в процессе обнаружения ошибок.

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

Резюме

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

Иногда быстродействие является результатом правильного выбора алгоритма или структуры данных (или того и другого). В других случаях увеличение скорости может быть достигнуто благодаря глубоким знаниям оборудования компьютера и операционной системы. Прежде всего, важно понимать, что единственным методом увеличения быстродействия приложения является использование профилировщика. Только предоставляемая профилировщиком статистика поможет определить, на что приложение тратит время, и лишь глубокое изучение отдельных блоков кода позволит оптимизировать приложение и увеличить его быстродействие. Хотелось бы подчеркнуть, что просто выбор "правильного" алгоритма или структуры данных отнюдь не означает, что приложение будет работать быстрее. Приведенная в книге информация поможет вам понять возможные способы ускорения выполнения отдельных частей кода, но только не нужно вносить в код сложные реализации алгоритмов там, где этого не требуется – вы только зря потеряете время.

Кроме того, в этой главе мы кратко рассмотрели тестирование и отладку – это тоже не алгоритмы, а скорее методы, гарантирующие, что код не содержит ошибок. А если ошибки все-таки присутствуют, то в коде находится столько разного рода следов и указателей, что поиск и устранение ошибок не должны отнимать много времени.

Глава 2. Массивы.

Несмотря на то что при стандартном (и не совсем стандартном) программировании используется огромное количество разного рода структур данных, большинство из них основаны на одном из двух фундаментальных контейнеров: массив и связный список. Если после прочтения этой книги вы научитесь правильно применять эти два типа структур, цель книги можно будет считать достигнутой. Они важны не только благодаря своей простоте, но и вследствие своей высокой эффективности. Массивы будут подробно рассмотрены в этой главе, а связные списки – в следующей. Кроме того, в главе 3 после связных списков будут описаны некоторые простые типы структур данных, основанные на этих двух фундаментальных типах. В главах 4 и 5, посвященных поиску и сортировке соответственно, мы также коснемся фундаментальных типов структур данных, но под несколько другим углом.

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

Массивы

Во многих отношениях массивы являются простейшей структурой данных. Проще могут быть только такие базовые типы данных, как integer или Boolean. Массив (array) представляет собой последовательный список определенного количества элементов. Все элементы в массиве принадлежат к одному типу данных, и, как правило, хранятся в одном блоке памяти, т.е. каждый последующий элемент в памяти находится непосредственно после предыдущего. В таком случае говорят, что элементы массива являются смежными в памяти. Если ссылаться на элементы массива по их числовым индексам, то первый элемент будет иметь индекс 0 (или 1, или любое другое число, по крайней мере, в Delphi), значение индекса второго элемента будет больше на единицу и т.д. В коде элемент с индексом i обозначается как А[i], где А – идентификатор массива.

В Delphi имеется большой набор встроенных типов массивов. Кроме того, отдельные удобные типы массивов определены в библиотеке визуальных компонент VCL (Visual Component Library) в виде классов (и не только классов). Для поддержки таких классов, как массивы, разработчики Delphi предусмотрели возможность перегрузки операции массива, [], добавляя к нему новые свойства. Это единственная операция в Delphi, помимо + (сложение и конкатенация строк), которую можно перегружать.

Типы массивов в Delphi

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

И последний тип массивов, как правило, не считается массивом, хотя в языке Object Pascal имеется несколько его вариаций. Конечно, мы говорим о строках: однобайтных строках (тип shortstring в 32-разрядной версии Delphi), строках с завершающим нулем (тип Pchar) и длинных строках в 32-разрядных версиях Delphi (которые имеют отдельную вариацию для "широких" символов).

Все массивы имеют одну и ту же структуру. Они состоят из одного или большего количества повторений другого типа данных, например, char, integer или record, которые в памяти находятся рядом друг с другом. Именно это последнее свойство стандартных массивов позволяет очень быстро получить доступ к отдельным элементам массивов. Весь процесс доступа к элементу сводится к простому вычислению адреса, для чего требуются, как мы вскоре увидим, всего несколько машинных инструкций.

Стандартные массивы

Можно даже не сомневаться, что все вы знаете стандартный способ объявления массивов в Delphi. Так, объявление

var

MyIntArray : array [0..9] of integer;

создает массив из 10 элементов типа integer. В языке Object Pascal диапазон изменения индексов элементов можно выбирать любым (в приведенном случае – от 0 до 9). В следующем примере объявляется еще один массив из 10 элементов типа integer, но здесь индексация элементов следует от 1 до 10:

var

MyIntArray : array [1..10] of integer;

Некоторые считают, что работать с массивом, объявленном во втором примере, удобнее (в конце концов, первый элемент имеет индекс 1).

Тем не менее, нужно сказать несколько слов о работе с массивами, индексация которых начинается с нуля. Во-первых, очень часто в API-интерфейсах операционных систем Windows и Linux, а также Delphi-библиотеках VCL и CLX предполагается, что первый элемент в массиве имеет индекс 0. Кроме того, в языках программирования С, С++ и Java индексация всех массивов обязательно начинается с 0. Поскольку и Windows, и Linux реализованы на С (или С++), при вызове API-функций считается, что индекс первого элемента массива равен 0.

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

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

Еще один момент, о котором необходимо помнить, – для основных типов массивов, элементы которых располагаются в памяти непрерывно, вычисление адреса элемента N (т.е. элемента MyArray[N]) в случае индексации с 0 производится по следующему выражению:

AddressOfElementN :=

AddressOfArray + (N * sizeof(ElementType));

Если же индексация массива начинается с X, то адрес элемента N будет вычисляться в соответствии с выражением:

AddressOfElementN :=

AddressOfArray + ((N – X) * sizeof(ElementType));

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

И в качестве последнего аргумента в пользу применения массивов, индексация элементов которых начинается с нуля, может служить удобство вычислений и программирования. Например, если доступ ко всем элементам осуществляется в цикле For, компилятор получает возможность оптимизировать цикл таким образом, чтобы последним значением переменной цикла был 0, поскольку сравнение с 0 в конце цикла будет быстрее, нежели сравнение с произвольным числом. В книге можно будет встретить несколько таких примеров. Таким образом, учитывая все вышесказанное, имеет смысл использовать массивы, первый элемент которых имеет индекс 0.

Так что же такого замечательного в использовании массивов в качестве структуры данных? Во-первых, вычисление адресов элементов выполняется очень быстро. Как уже говорилось, для этого нужно всего лишь умножение и сложение. При получении доступа к элементу N (MyArray [N]) компилятор для вычисления адреса добавляет простой машинный код. Независимо от значения числа N, формула для вычисления адреса будет одной и той же. Другими словами, получение доступа к элементу с индексом N принадлежит к классу операций O(1) и не зависит от величины N.

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

До сих пор мы рассматривали только преимущества массивов, но хотелось бы знать и об их недостатках. Первый недостаток связан с операциями вставки и удаления элементов. Что происходит, если, например, в массив необходимо вставить новый элемент с индексом n? В общем случае, все элементы с индексами, начиная с n и до конца массива, потребуется переместить на одну позицию, чтобы освободить место под новый элемент. А фактически выполняется следующий блок кода:

{сначала освободить место под новый элемент}

for i := LastElement downto N do

MyArray[i+1] := MyArray[i];

{вставить новый элемент в позицию с индексом N}

MyArray[N] := NewElement;

{увеличить значение длины массива на единицу}

inc(LastElementIndex);

(Конечно, на практике цикл заменяется вызовом процедуры Move.)

Рисунок 2.1. Вставка в массив нового элемента

Рисунок 2.2. Удаление элемента из массива

Объем памяти, который будет затронут при вставке нового элемента, зависит от значения n и количества элементов в самом массиве. Чем больше количество элементов, которые необходимо переместить, тем больше времени потребуется на выполнение операции. То есть, время, требуемое на выполнение цикла For, будет пропорционально количеству элементов в массиве. Другими словами, вставка нового элемента в массив принадлежит к классу операций O(n).

Тот же ход рассуждений справедлив и для операции удаления элемента из массива. Но в этом случае удаление элемента с индексом n означает, что элементы, начиная с индекса n + 1 и до конца массива, будут перенесены на одну позицию к началу массива, чтобы "закрыть" образовавшуюся от удаления элемента "дыру". Как и в случае со вставкой, удаление принадлежит к классу операций O(n).

{удалить элемент, переместив следующие за ним элементы на одну позицию вперед}

for i := N+ 1 to LastElementIndex do

MyArray[i-1] := MyArray[i];

{уменьшить значение длины массива на единицу}

dec(LastElementIndex);

(Конечно, на практике цикл заменяется вызовом процедуры Move.)

Таким образом, важно понимать, что операции вставки и удаления элемента при увеличении количества элементов в массиве будут выполняться медленнее, поскольку они принадлежат к классу операций O(n).

Кроме того, есть еще один вопрос, связанный со вставкой и удалением элементов, – необходимо контролировать количество активных элементов, т.е. в качестве последнего элемента массива нужно ввести сигнальный (sentinel) элемент, который будет использоваться в качестве метки конца массива. (В строках с завершающим нулем таким сигнальным элементом является символ #0.) Как правило, во время компиляции объявляются массивы фиксированного размера (сейчас мы говорим о методах увеличения размеров массивов), а, следовательно, для этого нам необходимо знать количество активных элементов. В двух приведенных выше примерах для хранения количества активных элементов использовалась переменная LastElementIndex. В строках и длинных строках, например, в самой строке, содержится счетчик количества символов. Но если мы не планируем использовать вставку или удаление элементов, никаких дополнительных элементов не требуется.

Стоит упомянуть и об еще одной проблеме, которая касается только программирования в Delphi1. В Delphi1 максимальный объем непрерывного выделяемого блока памяти (по крайней мере, без написания дополнительного кода на ассемблере) равен 64 Кб. Если объем одного элемента массива составляет 100 байт, то это означает, что в массиве не может быть больше 655 таких элементов. Не так уж и много. Это 64-Кбное ограничение может вызвать определенные проблемы и привести к тому, что придется использовать указатели на элементы (как, например, в знаменитом классе TList), а не сами элементы (в массиве TList в Delphi1 количество элементов ограничено числом 16 383).

Динамические массивы

Часто приходится сталкиваться с программированием процедур, которые требуют использования массива, причем количество элементов в таком массиве заранее не известно – их может быть десять, сто или тысяча, но окончательно количество элементов будет известно только во время выполнения процедур. Более того, из-за незнания количества элементов, его трудно объявить как локальную переменную (объявление массива с максимально возможным количеством элементов может привести к перегрузке стека, особенно это касается Delphi1). Таким образом, память под элементы массива лучше выделять из кучи.

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

Одним из методов, которые уходят корнями еще к временам языка Pascal, является создание типа массива со всего одним элементом и указателя на этот массив:

type

PMyArray : ^TMyArray;

TMyArray : array[0..0] of TMyType;

Теперь, если нам необходим массив типа TMyType, можно легко указать требуемое количество элементов:

var

MyArray : PMyArray;

begin

GetMem(MyArray, 42 * sizeof(TMyType));

... использование массива MyArray...

FreeMem(MyArray, 42*sizeof(TMyType));

Обратите внимание, что процедура FreeMem при освобождении выделенного блока памяти только в Delphi1 требует указания размера блока. Все 32-разрядные версии Delphi и Kylix хранят размер выделенного блока в самом блоке. Размер блока находится непосредственно перед блоком, который код получает с помощью процедуры GetMem. В последних версиях Delphi передаваемый в качестве входного параметра размер блока игнорируется, а вместо него используется скрытое значение.

До освобождения памяти MyArray указывает на массив, состоящий из 42 элементов типа TMyType. Несмотря на свою простоту, приведенный метод обладает некоторыми недостатками, о которых всегда нужно помнить. Во-первых, такой код нельзя компилировать с включенной проверкой диапазонов ($R+), поскольку компилятор считает, что массив должен содержать только один элемент, а, следовательно, может использоваться только индекс 0.

(От этого недостатка можно избавиться, если при объявлении массива указать, что он содержит не один элемент, а некоторое, достаточно большое, количество элементов. Но такое решение привносит свою проблему: все индексы до указанной верхней границы будут действительными. Так, например, если выделить массив из 42 элементов, основанный на массиве из 1000 элементов, то для компилятора индексы от 42 до 999 также будут действительными.)

Тем не менее, описанный метод очень широко применяется в повседневном программировании. Например, в модуле SysUnit содержится очень гибкий тип массива TByteArray, указатель на который имеет тип PByteArray. Используя этот тип (точнее сказать, указатель на тип) можно легко преобразовывать любой нетипизированный параметр, содержащийся в буфере, в массив байтов. Существуют и другие типы массивов: массив элементов типов longint, word и т.д.

Наиболее удобным методом решения второй проблемы является создание класса массива, который бы позволил выделять произвольное количество элементов, получать доступ и задавать значения отдельных элементов и даже уменьшать или увеличивать количество элементов в массиве. Другие возможности, например, сортировка, удаление и вставка, тоже были бы оказаться очень кстати. Фактически, программист создавал бы экземпляр класса, объявляя в конструкторе размер каждого элемента, а выделением памяти под элементы занимался бы сам класс.

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

Вместо этого давайте создадим структурный тип массива, TtdRecordList, который по функциям был бы аналогичен классу TList, но выделял память для самих элементов. Интерфейс такого класса приведен в листинге 2.1.

Если вы уже знакомы с интерфейсом класса TList, то наверняка обратите внимание, что класс TtdRecordList содержит все те же методы и свойства, что и TList. Таким образом, например, метод Add будет добавлять новый элемент в конец списка, a Insert – вставлять в список новый элемент в позицию с заданным индексом. Оба метода при необходимости будут приводить к расширению внутренней структуры массива, и увеличивать счетчик элементов. Метод Sort в этой главе мы рассматривать не будем. Описание его реализации будет приведено в главе 5.

Листинг 2.1. Объявление класса TtdRecordList

TtdRecordList = class

private

FActElemSize : integer;

FArray : PAnsiChar;

FCount : integer;

FCapacity : integer;

FElementSize : integer;

FIsSorted : boolean;

FMaxElemCount: integer;

FName : TtdNameString;

protected

function rlGetItem(aIndex : integer) : pointer;

procedure rlSetCapacity(aCapacity : integer);

procedure rlSetCount(aCount : integer);

function rlBinarySearch(aItem : pointer;

aCompare : TtdCompareFunc;

var aInx : integer) : boolean;

procedure rlError(aErrorCode : integer;

const aMethodName : TtdNameString;

aIndex : integer);

procedure rlExpand;

public

constructor Create(aElementSize : integer);

destructor Destroy; override;

function Add(aItem : pointer) : integer;

procedure Clear;

procedure Delete(aIndex : integer);

procedure Exchange(aIndex1, aIndex2 : integer);

function First : pointer;

function IndexOf(aItem : pointer; aCompare : TtdCompareFunc) : integer;

procedure Insert(aIndex : integer; aItem : pointer);

function InsertSorted(aItem : pointer; aCompare : TtdCompareFunc) : integer;

function Last : pointer;

procedure Move(aCurIndex, aNewIndex : integer);

function Remove(aItem : pointer; aCompare : TtdCompareFunc) : integer;

procedure Sort(aCompare : TtdCompareFunc);

property Capacity : integer read FCapacity write rlSetCapacity;

property Count : integer read FCount write rlSetCount;

property ElementSize : integer read FActElemSize;

property IsSorted : boolean read FIsSorted;

property Items[aIndex : integer] : pointer read rlGetItem; default;

property MaxCount : integer read FMaxElemCount;

property Name : TtdNameString read FName write FName;

end;

Конструктор Create сохраняет переданный ему размер элементов и вычисляет размер каждого элемента, округляя его до ближайших 4 байт. Округление будет гарантировать, что элементы всегда выровнены по границе 4 байт. Это вызвано соображениями увеличения скорости работы. В качестве последней операции, конструктор будет вычислять максимальное количество элементов, которое может содержаться в классе при заданном размере одного элемента. Фактически такая операция необходима только для Delphi1, поскольку в этой версии максимальный объем выделяемой из кучи памяти не может превышать 64 Кб и нужно убедиться, что мы не выходим за установленную границу.

Листинг 2.2. Конструктор класса TtdRecordList

constructor TtdRecordList.Create(aElementSize : integer);

begin

inherited Create;

{сохранить фактический размер элемента}

FActElemSize := aElementSize;

{округлить фактический размер элемента до 4 байт}

FElementSize := ((aElementSize + 3) shr 2) shl 2;

{вычислить максимальное количество элементов}

{$IFDEF Delphi1}

FMaxElemCount := 65535 div FElementSize;

{$ELSE}

FMaxElemCount := MaxInt div integer(FElementSize);

{$ENDIF}

FIsSorted := true;

end;

Обратите внимание, что класс не выделяет память для элементов массива. Выделение памяти происходит при добавлении элементов или, другими словами, при фактическом использовании экземпляра класса.

(В коде, приведенном в листинге 2.2, используется нестандартная директива компилятора – Delphi1. Эта директива определена во включаемом файле TDDefine.inc, который применяется во всех приведенных в книге модулях. Директиву Delphi1 намного легче запомнить, чем ее более официальное название VER80. Кроме того, официальное название сложнее запомнить, поскольку свое официальное название имеется для каждой версии. Так, например, для Delphi3 – это VER100, для Delphi4 – VER120 и т.д. Тем не менее, существуют и соответствующие неофициальное названия – Delphi3 и Delphi4.)

Деструктор ничуть не сложнее конструктора. В нем мы просто устанавливает емкость экземпляра класса равным 0 (немного ниже мы подробно рассмотрим, что такое емкость) и вызываем унаследованный деструктор Destroy.

Листинг 2.3. Деструктор класса TtdRecordList

destructor TtdRecordList.Destroy

begin

Capacity := 0;

inherited Destroy;

end;

А теперь давайте перейдем к более интересным вещам: добавлению и вставке новых элементов. Реализация метода Add достаточно проста. В ней вызывается Insert для вставки нового элемента в конец массива. Метод Insert в качестве входного параметра принимает значение, представляющее собой индекс позиции, в которую требуется вставить новый элемент. Сам элемент задается указателем (есть еще один способ представления вставляемого элемента – в виде нетипизированного параметра var, однако указатели позволяют упростить реализацию и понимание других методов и, кроме того, обеспечивают непротиворечивость). При вызове метода Insert для передачи адреса вставляемого элемента в виде указателя используется операция 8, определенная в Delphi.

Поскольку новый элемент является указателем, он может содержать nil, поэтому сначала необходимо проверить, что указатель не равен nil. Затем в реализации метода выполняется проверка выхода индекса за границы допустимого диапазона. Только после этого можно приступить к собственно вставке. Если количество элементов равно текущей емкости массива, то для расширения массива вызывается метод rlExpand Теперь мы перемещаем элементы, начиная с индекса aIndex до конца массива, на один элемент, дабы тем самым освободить место под новый элемент. И, наконец, мы вставляем элемент в образовавшуюся "дыру" и увеличиваем значение счетчика элементов на единицу.

Листинг 2.4. Добавление и вставка новых элементов

function TtdRecordList.Add(aItem : pointer): integer;

begin

Result := Count;

Insert(Count, aItem);

end;

procedure TtdRecordList.Insert(aIndex : integer;

aItem : pointer);

begin

if (aItem = nil) then

rlError(tdeNilItem, 'Insert', aIndex);

if (aIndex < 0) or (aIndex > Count) then

rlError(tdeIndexOutOfBounds, 'Insert', aIndex);

if (Count = Capacity) then

rlExpand;

if (aIndex < Count) then

System.Move((FArray + (aIndex * FElementSize))^,

(FArray+ (succ(aIndex) * FElementSize))^,

(Count – aIndex) * FElementSize);

System.Move (aItem^,

(FArray + (aIndex * FElementSize))^, FActElemSize);

inc(FCount);

end;

Реализация метода Delete, предназначенного для удаления элементов из массива, показана в листинге 2.5. Как и для Insert, сначала проверяется переданный методу индекс, затем элементы, начиная с индекса aIndex, переносятся на одну позицию к началу массива, за счет чего требуемый элемент удаляется. После удаления количество элементов в массиве уменьшается, поэтому из значения счетчика элементов вычитается единица.

Листинг 2.5. Удаление элемента массива

procedure TtdRecordList.Delete(aIndex : integer);

begin

if (aIndex < 0) or (aIndex >= Count) then

rlError(tdeIndexOutOfBounds, 'Delete', aIndex);

dec(FCount);

if (aIndex < Count) then

System.Move((FArray+ (succ(aIndex) * FElementSize))^,

(FArray + (aIndex * FElementSize))^,

(Count – aIndex) * FElementSize);

end;

Метод Remove аналогичен Delete в том, что с его помощью также удаляется отдельный элемент, но при этом не требуется знание его индекса в массиве. Нужный элемент находится с помощью метода indexOf и вспомогательной процедуры сравнения, которая является внешней по отношению к классу. Таким образом, метод Remove требует не только самого удаляемого элемента, но и вспомогательной процедуры, которая бы идентифицировала элемент, подлежащий удалению. Такая процедура имеет тип TdtCompareFunc. Она будет вызываться для каждого элемента массива до тех пор, пока возвращаемое значение для определенного элемента не окажется нулевым (что означает «равно»). Если процедура выполняется для всех элементов, а нулевое возвращаемое значение так и не получено, метод IndexOf возвращает значение tdcJEtemNotPresent. Листинг 2.6. Методы Remove и IndexOf

function TtdRecordList.Remove(aItem : pointer;

aCompare : TtdCompareFunc): integer;

begin

Result := IndexOf(aItem, aCompare);

if (Result <> tdc_ItemNotPresent) then

Delete(Result);

end;

function TtdRecordList.IndexOf(aItem : pointer;

aCompare : TtdCompareFunc): integer;

var

ElementPtr : PAnsiChar;

i : integer;

begin

ElementPtr := FArray;

for i := 0 to pred(Count) do begin

if (aCompare(aItem, ElementPtr) = 0) then begin

Result := i;

Exit;

end;

inc(ElementPtr, FElementSize);

end;

Result := tdc_ItemNotPresent;

end;

Для расширения массива (т.е. для увеличения его емкости) используется свойство Capacity. При его установке вызывается защищенный метод rlSetCapacity. Реализация метода несколько сложнее, чем могла бы быть. Это вызвано тем, что процедура ReAllocMem в версии Delphi1 не делает всего того, что она делает в 32-разрядных версиях.