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

Вместо этого давайте создадим структурный тип массива, 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-разрядных версиях.

Соответствующий метод назван rlExpand Это защищенный метод, построенный на базе простого алгоритма и предназначенный для установки значения свойства Capacity на основе его текущего значения. Метод rlExpand вызывается автоматически при использовании метода Insert для увеличения емкости массива, если будет определено, что в настоящее время массив полностью заполнен (т.е. емкость равна количеству элементов в массиве).

Листинг 2.7. Расширение массива

procedure TtdRecordList.rlExpand;

var

NewCapacity : integer;

begin

{если текущая емкость массива равна 0, установить новую емкость равной 4 элемента}

if (Capacity = 0) then

NewCapacity := 4

{если текущая емкость массива меньше 64, увеличить ее на 16 элементов}