Фундаментальные алгоритмы и структуры данных в Delphi
Шрифт:
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;
Для
Соответствующий метод назван 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
rlError(tdeCapacityTooLarge, 'rlSetCapacity', 0);
{повторно распределить или освободить память, если емкость массива уменьшена до нуля}
{$IFDEF Delphi1}
if (aCapacity= 0) than begin
FreeMem(FArray, word(FCapacity) * FElementSize);
FArray := nil
end
else begin
if (FCapacity = 0) then
GetMem( FArray, word (aCapacity) * FElementSize) else
FArray := ReallocMem(FArray,
word(FCapacity) * FElementSize,
word(aCapacity) * FElementSize);
end;
{$ELSE}
ReallocMem(FArray, aCapacity * FElementSize);
{$ENDIF}
{емкость уменьшается? если да, проверить счетчик}
if (aCapacity < FCapacity) then begin
if (Count > aCapacity) then
Count := aCapacity;
end;
{сохранить
FCapacity := aCapacity;
end
end;
Конечно, любой класс массива оказался бы бесполезным, если бы было невозможно считать элемент из массива. В классе TtdRecordList для этой цели имеется свойство Items. Единственным средством доступа для этого свойства является метод считывания rlGetItem. Во избежание ненужного копирования данных в элемент, метод rlGetItem возвращает указатель на элемент массива. Это позволяет не только считать, но и легко изменить элемент. Именно поэтому для свойства Items нет специального метода записи. Поскольку свойство отмечено ключевым словом default, доступ к отдельным элементам можно получить с помощью кода MyArray[i], а не MyArray.Items[i].
Листинг 2.8. Получение доступа к элементу массива
function TtdRecordList.rlGetItem(aIndex : integer): pointer;
begin
if (aIndex < 0) or (aIndex >= Count) then
rlError(tdeIndexOutOfBounds, 'rlGetItem', aIndex);
Result := pointer(FArray + (aIndex * FElementSize));
end;
И последний метод, который мы сейчас рассмотрим, - это метод, используемый для установки свойства Count - rlSetCount. Установка свойства Count позволяет предварительно выделить память для элементов массива и работать с ней аналогично тому, как Delphi работает со стандартными массивами. Обратите внимание, что методы Insert и Delete будут автоматически изменять значение свойства Count при вставке и удалении элементов. Установка свойства Count явным образом будет гарантировать и корректную установку свойства Capacity (метод Insert делает это автоматически). Если новое значение свойства Count больше текущего, значения всех новых элементов будут равны нулю. В противном случае элементы, индексы которых больше или равны новому количеству элементов, станут недоступными (фактически их можно будет считать удаленными).
Листинг 2.9. Установка количества элементов в массиве
procedure TtdRecordList.rlSetCount(aCount : integer);
begin
if (aCount <> FCount) then begin
{если новое значение количества элементов в массиве больше емкости массива, расширить массив}
if (aCount > Capacity) then
Capacity := aCount;
{если новое значение количества элементов в массиве больше старого значения, установить значения новых элементов равными нулю}
if (aCount > FCount) then
FillChar((FArray + (FCount * FElementSize))^, (aCount - FCount) * FElementSize, 0);
{сохранить новое значение счетчика элементов}
FCount := aCount;
end;
end;
Полный код класса TtdRecordList можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDRecLst.pas. В файле находятся также реализации таких стандартных методов, как First, Last, Move и Exchange.
Новые динамические массивы