[Из песочницы] Индексация глобальная и не очень
Сразу оговорюсь, статья не имеет ничего общего с индексацией сайтов и т.п. Речь пойдет о вещах куда более простых, но, тем не менее, нужных. Иногда надо проиндексировать сущности, так чтобы индексы были уникальны в рамках программы и компактно упакованы в промежуток [0…N]. Причем заводить для этого отдельные механизмы совершенно не хочется.
Примером может послужить такая задача:
Всем, думаю, известно, что class var в Delphi есть не что иное, как обычная глобальная переменная, единая для класса и всех его потомков. А иногда нужно, чтобы потомки использовали свои собственные, например, для подсчета экземпляров класса. Я знаю как минимум одно решение этой проблемы, но это хак. Кроме того он требует от пользователя дополнительных действий — выделения памяти в блоке initialization и, по-хорошему, освобождения ее в finalization.
Но можно сделать и проще — завести глобальный (class var) массив, и сделать так, чтобы каждый потомок ссылался на свою ячейку. Единственная проблема в том, что для этого требуется проиндексировать потомков, причем сделать это автоматически.
В моем случае задача была несколько другой. Хотелось добавить классам универсальную возможность включать/исключать себя в множества и проверять себя на принадлежность за O (1). То есть добавить поле «сигнатуры», дающее такую возможность в независимости от количества предполагаемых множеств и не связывать классы каким-нибудь общим предком. В любом случае на определенном этапе я пришел к проблеме индексации этих самых множеств.
Немного побродив по просторам интернета, я не нашел готового решения. Собственно я не видел, чтобы такая задача вообще ставилась. А между тем, думаю, этому нашлось бы немало применений.
Вообще задача несложная. Возможно, это и послужило причиной отсутствия разговоров на эту тему. В самом примитивном виде код занимает всего несколько строк:
type
TIndexator = class
private
var FIndexTable: TDictionary;
public
constructor Create;
destructor Destroy; override;
function GetIndex(Ident: TIdent): Integer;
end;
function TIndexator.GetIndex(Ident: TIdent): Integer;
begin
if not FIndexTable.TryGetValue(Ident, Result) then begin
Result := FIndexTable.Count;
FIndexTable.Add(Ident, Result);
end;
end;
Но мне этого показалось недостаточно. В такой реализации надо создавать дополнительные переменные, как правило, глобальные и следить за их инициализацией. Кроме того не хватает некоторой гибкости. В общем, я решил немного усовершенствовать подход, и в результате получилось вот что:
type
TGlobalIndexator = class
private type
TIdentTable = TList;
TIndexTable = TDictionary;
PClientField = ^TClientField;
TClientField = record
IndexNames: TIdentTable;
IndexTable: TIndexTable;
end;
TClientTable = TDictionary;
strict private
class var FClientTable: TClientTable;
class constructor InitClass;
class function GetField(Client: Pointer): PClientField;
public
class function GetIndex(Ident: TIdent): Integer; overload;
class function GetIndex(Client: Pointer; Ident: TIdent): Integer; overload;
class function GetIdent(Index: Integer): TIdent; overload;
class function GetIdent(Client: Pointer; Index: Integer): TIdent; overload;
end;
class constructor TGlobalIndexator.InitClass;
begin
FClientTable := TClientTable.Create;
end;
class function TGlobalIndexator.GetField(
Client: Pointer): PClientField;
begin
if not FClientTable.TryGetValue(Client, Result) then begin
New(Result);
Result.IndexNames := TIdentTable.Create;
Result.IndexTable := TIndexTable.Create;
FClientTable.Add(Client, Result);
end;
end;
class function TGlobalIndexator.GetIndex(Client: Pointer;
Ident: TIdent): Integer;
var Field: PClientField;
begin
//Writeln('GetIndex(', Client.ClassName, ', , Ident, );');
Field := GetField(Client);
if not Field.IndexTable.TryGetValue(Ident, Result) then begin
Result := Field.IndexNames.Count;
Field.IndexNames.Add(Ident);
Field.IndexTable.Add(Ident, Result);
end;
end;
class function TGlobalIndexator.GetIndex(Ident: TIdent): Integer;
begin
Result := GetIndex(Pointer(Self), Ident);
end;
class function TGlobalIndexator.GetIdent(Client: Pointer;
Index: Integer): TIdent;
var Field: PClientField;
begin
Field := GetField(Client);
if Index < Field.IndexNames.Count then
Result := Field.IndexNames[Index]
else
raise Exception.CreateFmt('Index %d is not registered', [Index]);
end;
class function TGlobalIndexator.GetIdent(Index: Integer): TIdent;
begin
Result := GetIdent(Pointer(Self), Index);
end;
Код все равно не сложен. Как можно заметить, в нем нет процедур удаления индекса. Это сделано специально, чтобы избежать множества проблем, связанных с использованием «старого» индекса.
Применять этот класс можно двумя способами: В простых случаях можно просто задать новый потомок класса. Ничего переопределять при этом не нужно, важен лишь факт создания нового класса.
type
TMyStringIndexator = class(TGlobalIndexator) end;
begin
Index1 := TMyStringIndexator('Key0');
Index2 := TMyStringIndexator('Key1');
end;
Там где требуется бо́льшая гибкость можно помимо индексируемого значения указать «клиента». Индексация различных клиентов будет проводиться независимо. Если клиент — статический класс, то указывается TSomeClass.ClassInfo, если текущий потомок — Self.ClassInfo, если объект, то просто Self.
Вот, например, реализация выше упомянутого счетчика экземпляров:
type
TCountable = class
private
FIndex: Integer;
class var FCounts: array of Integer;
function GetCount: Integer; inline;
public
constructor Create;
destructor Destroy; override;
property Count: Integer read GetCount;
end;
constructor TCountable.Create;
begin
FIndex := TGlobalIndexator.GetIndex(TCountable.ClassInfo, ClassInfo);
if Length(FCounts) <= FIndex then
SetLength(FCounts, FIndex + 1);
Inc(FCounts[FIndex]);
end;
destructor TCountable.Destroy;
begin
Dec(FCounts[FIndex]);
end;
function TCountable.GetCount: Integer;
begin
Result := FCounts[FIndex];
end;
Так у каждого потомка будет свой счетчик экземпляров, и нет необходимости в каких либо дополнительных действиях.
В общем, надеюсь, кому-то эта идея пойдет на пользу.
