Фундаментальные алгоритмы и структуры данных в Delphi
Шрифт:
FMaxElemCount := MaxInt div integer(FElementSize);
{$ENDIF}
FIsSorted := true;
end;
Обратите внимание, что класс не выделяет память для элементов массива. Выделение памяти происходит при добавлении элементов или, другими словами, при фактическом использовании экземпляра класса.
(В коде, приведенном в листинге 2.2, используется нестандартная директива компилятора - Delphi1. Эта директива определена во включаемом файле TDDefine.inc, который применяется во всех приведенных в книге модулях. Директиву Delphi1 намного легче запомнить, чем ее более официальное название VER80. Кроме того, официальное название сложнее запомнить, поскольку свое официальное название имеется для каждой
Деструктор ничуть не сложнее конструктора. В нем мы просто устанавливает емкость экземпляра класса равным 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 и IndexOffunction 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 элементов}
else
if (Capacity < 64) then
NewCapacity := Capacity +16
{если текущая емкость массива 64 или больше, увеличить ее на 25%}
else
NewCapacity := Capacity + (Capacity div 4);
{убедиться, что мы не выходим за верхний индекс массива}
if (NewCapacity > FMaxElemCount) then begin
NewCapacity := FMaxElemCount;
if (NewCapacity = Capacity) then
rlError (tdeAtMaxCapacity, 'rlExpand', 0);
end;
{установить новую емкость}
Capacity := NewCapacity;
end;
procedure TtdRecordList.rlSetCapacity(aCapacity : integer);
begin
if (aCapacity <> FCapacity) then begin
{запретить переход через максимально возможное количество элементов}
if (aCapacity > FMaxElemCount) then