Фундаментальные алгоритмы и структуры данных в Delphi
Шрифт:
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
Листинг 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 для вставки нового элемента в конец массива.
Поскольку новый элемент является указателем, он может содержать 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