Code-Kata: Cache-Klasse. Wer produziert den besten Code

[Namenloser]

Ich geb mal meinen Senf dazu. Bin jetzt nicht wirklich glücklich über den ganzen Boilerplate-Code, aber ich kann ja auch nichts dafür, dass es keine gescheite Standardlib gibt (oder hat Delphi inzwischen eine verkettete Liste? Habe nichts gefunden).

Habe den Code nicht getestet, da ich kein Delphi mehr habe, also habe ich bestimmt irgendwo was übersehen. Aber es geht ja eher um den Ansatz, denke ich.

Ein paar Worte zu meinen Designentscheidungen:
- Ich habe es jetzt mal so interpretiert, dass es ein einfacher MRU-Cache sein soll.
- Ich prüfe nicht explizit ob die Aufrufe gültig sind (z.B. ob bei Get der Key auch wirklich existiert) und werfe daher auch keine Exceptions. Denn offensichtlich ist die Schnittstelle so angelegt, dass der Benutzer vorher selbst mit Contain prüfen soll, ob der Key existiert. Wenn die Klasse selber es dann noch mal prüfen würde, würde doppelt geprüft. Deswegen habe ich die Prüfungen nur als nur Assertions drin. Die ganze Schnittstelle ist meiner Meinung nach nicht optimal (die von TDictionary übrigens auch nicht), aber war ja so vorgegeben, also muss man das beste daraus machen.
- Edit: Achso, und falls sich jemand wundert: Ich verwende grundsätzlich (fast) nie private sondern immer protected (bis auf sehr wenige Ausnahmen, bei denen es wirklich gute Gründe gibt, die dagegen sprechen). Könnt ihr meinetwegen schlecht finden, ist mir aber egal

Delphi-Quellcode:

  { TLinkedListItem }

  TLinkedListItem<T> = class
  protected
    FValue: T;
    FPrev: TLinkedListItem<T>;
    FNext: TLinkedListItem<T>;
  public
    constructor Create;
    constructor Create(Value: T);
    property Value: T read FValue write FValue;
    property Next: TLinkedListItem<T> read FNext;
    property Prev: TLinkedListItem<T> read FPrev;
  end;

  { TLinkedList }

  TLinkedList<T> = class
  protected
    FSentinel: TLinkedListItem<T>;
    function GetFirst: TLinkedListItem<T>;
    function GetLast: TLinkedListItem<T>;
  public
    constructor Create;
    destructor Destroy; override;
    procedure InsertBefore(Item: TLinkedListItem<T>; Successor: TLinkedListItem<T>);
    function Extract(Item: TLinkedListItem<T>): TLinkedListItem<T>;
    property First: TLinkedListItem<T> read GetFirst;
    property Last: TLinkedListItem<T> read GetLast;
  end;

  { TCache }

  TCache = class
  protected type
    TKeyValuePair = record
      Key: Integer;
      Value: TObject;
    end;

    TCacheItem = TLinkedListItem<TKeyValuePair>;
    TCacheItemList = TLinkedList<TKeyValuePair>;
  protected
    FMaxSize: Integer;
    FMRU: TCacheItemList;
    FMap: TDictionary<Integer, TCacheItem>;

    function GetCurrentNumberOfElements: Integer;
    function GetSize: Integer;

    function MakePair(Key: Integer; Value: TObject): TKeyValuePair;

    procedure Bump(Item: TCacheItem);
    procedure Evict(Item: TCacheItem);
  public
    constructor Create(MaxSize: Integer);
    destructor Destroy; override;
    function Contains(ID: Integer): Boolean;
    function Get(ID: Integer): TObject;
    procedure Put(ID: Integer; Item: TObject);
    procedure Remove(ID: Integer);
    property MaxSize: Integer Read FMaxSize;
    property CurrentNumberOfElements : Integer Read GetCurrentNumberOfElements;
  end;

implementation

{ TLinkedListItem }

constructor TLinkedListItem<T>.Create;
begin
  FNext := Self;
  FPrev := Self;
end;

constructor TLinkedListItem<T>.Create(Value: T);
begin
  Create;
  Self.Value := Value;
end;

{ TLinkedList }

constructor TLinkedList<T>.Create;
begin
  FSentinel := TLinkedListItem<T>.Create;
end;

destructor TLinkedList<T>.Destroy; override;
begin
  FSentinel.Free;
end;

function TLinkedList<T>.GetFirst: TLinkedListItem<T>;
begin
  Result := FSentinel.Next;
end;

function TLinkedList<T>.GetLast: TLinkedListItem<T>;
begin
  Result := FSentinel.Prev;
end;

procedure TLinkedList<T>.InsertBefore(Item: TLinkedListItem<T>;
  Successor: TLinkedListItem<T>);
begin
  Extract(Successor);
  Item.Next := Successor;
  Item.Prev := Successor.Prev;
  Item.Next.Prev := Item;
  Item.Prev.Next := Item;
end;

function TLinkedList<T>.Extract(Item: TLinkedListItem<T>): TLinkedListItem<T>;
begin
  Item.Prev.Next := Item.Next;
  Item.Next.Prev := Item.Prev;
  Item.Prev := Item;
  Item.Next := Item;
  Result := Item;
end;

{ TCache }

constructor TCache.Create(MaxSize: Integer);
begin
  FMaxSize := MaxSize;
  FMap := TDictionary<Integer, TCacheItem>.Create;
  FMRU := TCacheItemList.Create;
end;

destructor TCache.Destroy; override;
begin
  while (NumberCurrentNumberOfElements > 0) do
    Evict(FMRU.First);
  FMRU.Free;
  FMap.Free;
end;

function TCache.GetCurrentNumberOfElements: Integer;
begin
  Result := FMap.Count;
end;

function TCache.MakePair(Key: Integer; Value: TObject): TKeyValuePair;
begin
  Result.Key := Key;
  Result.Value := Value;
end;

procedure TCache.Bump(Item: TCacheItem);
begin
  FMRU.InsertBefore(CacheItem, FMRU.First);
end;

procedure TCache.Evict(Item: TCacheItem);
begin
  FMap.Remove(CacheItem.Value.Key);
  FMRU.Extract(CacheItem);

  CacheItem.Value.Value.Free;
  CacheItem.Free;
end;

function TCache.Contains(ID: Integer): Boolean;
begin
  Result := FMap.ContainsKey(ID);
end;

function TCache.Get(ID: Integer): TObject;
var
  CacheItem: TCacheItem;
begin
  Assert(Contains(ID));

  CacheItem := FMap[ID];
  Bump(CacheItem);
  Result := CacheItem.Value.Value;
end;

procedure TCache.Put(ID: Integer; Item: TObject);
var
  CacheItem: TCacheItem;
begin
  Assert(not Contains(ID));

  if GetCurrentNumberOfElements >= FMaxSize then
    Evict(FMRU.Last);

  CacheItem := TCacheItem.Create(MakePair(ID, Item));
  FMap[ID] := CacheItem;
  Bump(CacheItem);
end;

procedure TCache.Remove(ID: Integer);
begin
  Assert(Contains(ID));
  Evict(FMap[ID]);
end;