Do generics and typed pointers mix? Certainly, so long as you use a nested type:
type TOuterType<T> = class public type PInnerType = ^TInnerType; TInnerType = record Value: T; end; end;
OK, so the New/Dispose bug still holds, but that’s only a minor irritant. I’m not sure why I didn’t think of the nested type ‘trick’ before, and indeed, I’ve now noticed Alexandru Ciobanu uses this sort of thing in his Collections project (which, by the way, is well worth looking at generally). Better late than never though!
Put to work, here’s a simple generic queue implementation based on a singly-linked list. In use, it works just like the stock TQueue<T>:
unit CCR.LinkedQueue; interface type TLinkedQueue<T> = class strict private type PNode = ^TNode; TNode = record NextNode: PNode; Value: T; end; public type TEnumerator = record strict private FDoneFirst: Boolean; FNode: PNode; function GetCurrent: T; public constructor Create(AHeadNode: PNode); function MoveNext: Boolean; property Current: T read GetCurrent; end; strict private FCount: Integer; FHeadNode, FTailNode: PNode; public destructor Destroy; override; function GetEnumerator: TEnumerator; procedure Clear; procedure Enqueue(const Value: T); function Dequeue: T; function Peek: T; property Count: Integer read FCount; end; implementation uses RTLConsts, Classes; constructor TLinkedQueue<T>.TEnumerator.Create(AHeadNode: PNode); begin FDoneFirst := False; FNode := AHeadNode; end; function TLinkedQueue<T>.TEnumerator.GetCurrent: T; begin Result := FNode.Value; end; function TLinkedQueue<T>.TEnumerator.MoveNext: Boolean; begin if FDoneFirst then FNode := FNode.NextNode else FDoneFirst := True; Result := (FNode <> nil); end; destructor TLinkedQueue<T>.Destroy; begin Clear; inherited; end; function TLinkedQueue<T>.GetEnumerator: TEnumerator; begin Result := TEnumerator.Create(FHeadNode); end; procedure TLinkedQueue<T>.Clear; var Node: PNode; begin while FHeadNode <> nil do begin Node := FHeadNode.NextNode; Finalize(FHeadNode.Value); FreeMem(FHeadNode); FHeadNode := Node; end; FCount := 0; end; procedure TLinkedQueue<T>.Enqueue(const Value: T); var NewNode: PNode; begin NewNode := AllocMem(SizeOf(TNode)); NewNode.Value := Value; if FHeadNode = nil then FHeadNode := NewNode else FTailNode.NextNode := NewNode; FTailNode := NewNode; Inc(FCount); end; function TLinkedQueue<T>.Dequeue: T; var Node: PNode; begin if Count = 0 then raise EListError.CreateRes(@SUnbalancedOperation); Node := FHeadNode; Result := Node.Value; FHeadNode := Node.NextNode; Finalize(Node); FreeMem(Node); Dec(FCount); end; function TLinkedQueue<T>.Peek: T; begin if Count = 0 then raise EListError.CreateRes(@SUnbalancedOperation); Result := FHeadNode.Value; end; end.
Pretty straightforward I’d say.
What of a generic linked list in a fuller sense though, where you can insert and remove items in any order? While this could be done using pointers, you would then be caught between exposing the pointer stuff directly (in which case, why bother with a generic container in the first place – just implement the pattern directly) and hiding it under an array list-type shell. I’d say it’s better to avoid both by using a class for the node type instead:
unit CCR.SimpleLinkedList; interface type TSimpleLinkedList<T> = class public type TNode = class strict private FPrevious, FNext: TNode; FList: TSimpleLinkedList<T>; FValue: T; protected constructor Create(AList: TSimpleLinkedList<T>; APrevious, ANext: TNode; const AValue: T); overload; public constructor Create; overload; //disallow outside construction by raising an exception destructor Destroy; override; procedure MoveBefore(ANode: TNode); procedure MoveAfter(ANode: TNode); property List: TSimpleLinkedList<T> read FList; property Next: TNode read FNext write FNext; property Previous: TNode read FPrevious write FPrevious; property Value: T read FValue write FValue; end; TValueEnumerator = record strict private FDoneFirst: Boolean; FNode: TNode; function GetCurrent: T; public constructor Create(AHead: TNode); function MoveNext: Boolean; property Current: T read GetCurrent; end; private FCount: Integer; FFirst, FLast: TNode; procedure ValidateNode(ANode: TNode); public destructor Destroy; override; function GetEnumerator: TValueEnumerator; procedure Clear; function Add(const AValue: T): TNode; inline; function AddAfter(ANode: TNode; const AValue: T): TNode; function Insert(Index: Integer; const AValue: T): TNode; function InsertBefore(ANode: TNode; const AValue: T): TNode; property Count: Integer read FCount; property First: TNode read FFirst; property Last: TNode read FLast; end; implementation uses SysUtils, RTLConsts; //for the standard exception types and error messages { TNode } constructor TSimpleLinkedList<T>.TNode.Create; begin raise ENoConstructException.CreateResFmt(@SNoConstruct, [ClassName]); end; constructor TSimpleLinkedList<T>.TNode.Create(AList: TSimpleLinkedList<T>; APrevious, ANext: TNode; const AValue: T); begin Assert(AList <> nil); inherited Create; FPrevious := APrevious; FNext := ANext; if APrevious <> nil then APrevious.Next := Self; if ANext <> nil then ANext.Previous := Self; if APrevious = AList.Last then AList.FLast := Self; if ANext = AList.First then AList.FFirst := Self; FList := AList; FValue := AValue; Inc(AList.FCount); end; destructor TSimpleLinkedList<T>.TNode.Destroy; begin Dec(List.FCount); if Self = List.First then List.FFirst := Next; if Self = List.Last then List.FLast := Previous; if Previous <> nil then Previous.FNext := Next; if Next <> nil then Next.FPrevious := Previous; inherited Destroy; end; procedure TSimpleLinkedList<T>.TNode.MoveBefore(ANode: TNode); begin List.ValidateNode(ANode); if ANode = Next then Exit; //unlink ourselves from our current neighbours if Previous <> nil then Previous.Next := Next; if Next <> nil then Next.Previous := Previous; //link ourselves to our new neighbours Previous := ANode.Previous; if Previous <> nil then Previous.Next := Self; ANode.Previous := Self; Next := ANode; end; procedure TSimpleLinkedList<T>.TNode.MoveAfter(ANode: TNode); begin List.ValidateNode(ANode); if ANode = Previous then Exit; //unlink ourselves from our current neighbours if Previous <> nil then Previous.Next := Next; if Next <> nil then Next.Previous := Previous; //link ourselves to our new neighbours Next := ANode.Next; if Next <> nil then Next.Previous := Self; ANode.Next := Self; Previous := ANode; end; { TValueEnumerator } constructor TSimpleLinkedList<T>.TValueEnumerator.Create(AHead: TNode); begin FDoneFirst := False; FNode := AHead; end; function TSimpleLinkedList<T>.TValueEnumerator.MoveNext: Boolean; begin if not FDoneFirst then FDoneFirst := True else FNode := FNode.Next; Result := (FNode <> nil); end; function TSimpleLinkedList<T>.TValueEnumerator.GetCurrent: T; begin Result := FNode.Value; end; { TSimpleLinkedList } destructor TSimpleLinkedList<T>.Destroy; begin Clear; inherited Destroy; end; function TSimpleLinkedList<T>.GetEnumerator: TValueEnumerator; begin Result := TValueEnumerator.Create(First); end; function TSimpleLinkedList<T>.Add(const AValue: T): TNode; begin Result := TNode.Create(Self, Last, nil, AValue); end; function TSimpleLinkedList<T>.AddAfter(ANode: TNode; const AValue: T): TNode; begin ValidateNode(ANode); Result := TNode.Create(Self, ANode, ANode.Next, AValue); end; procedure TSimpleLinkedList<T>.Clear; begin while Count > 0 do First.Free; end; function TSimpleLinkedList<T>.Insert(Index: Integer; const AValue: T): TNode; var I: Integer; Node: TNode; begin if (Index < 0) or (Index > Count) then raise EArgumentOutOfRangeException.CreateRes(@SArgumentOutOfRange); if Index = Count then Result := Add(AValue) else begin Node := First; for I := 1 to Index do Node := Node.Next; Result := TNode.Create(Self, Node.Previous, Node, AValue); end; end; function TSimpleLinkedList<T>.InsertBefore(ANode: TNode; const AValue: T): TNode; begin ValidateNode(ANode); Result := TNode.Create(Self, ANode.Previous, ANode, AValue); end; procedure TSimpleLinkedList<T>.ValidateNode(ANode: TNode); begin if ANode = nil then raise EArgumentNilException.CreateRes(@SArgumentNil); if ANode.List <> Self then raise EArgumentOutOfRangeException.CreateRes(@SGenericItemNotFound); end; end.
Beyond the custom enumerator to support for/in loops, this should be considered a pretty minimal implementation. As with the LinkedList class in the .NET BCL, it deliberately avoids an indexer and instead exposes the node objects directly. To delete an item, you therefore free the node. Here’s it in action:
var List: TSimpleLinkedList<string>; Fourth, Sixth, Seventh: TSimpleLinkedList<string>.TNode; S: string; begin ReportMemoryLeaksOnShutdown := True; List := TSimpleLinkedList<string>.Create; try Fourth := List.Add('Fourth'); List.InsertBefore(Fourth, 'Second'); Sixth := List.AddAfter(Fourth, 'Sixth'); List.InsertBefore(Sixth, 'Fifth'); Seventh := List.InsertBefore(Fourth, 'Seventh'); List.Add('Zero'); List.Insert(0, 'First'); List.Insert(2, 'Third'); Seventh.MoveAfter(Sixth); List.Last.Free; //this removes the node from the list for S in List do WriteLn(S); finally List.Free; end; ReadLn; end.
I’ve put up a slightly ‘fuller-fat’ version here if anyone’s interested. Compared to the one presented above, it fits into the framework of Generics.Collections (meaning, it descends from TEnumerable<T> and uses IComparer<T>), adds most of the methods from the stock TList<T>, and implements optional object ownership when instantiated with a class.