Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi

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, переносятся на одну позицию к началу массива, за счет чего требуемый элемент удаляется. После удаления количество элементов в массиве уменьшается, поэтому из значения счетчика элементов вычитается единица.