{$MODE FPC}
{$MODESWITCH ADVANCEDRECORDS}
{$MODESWITCH AUTODEREF}
{$MODESWITCH DEFAULTPARAMETERS}
{$MODESWITCH NESTEDPROCVARS}
{$MODESWITCH RESULT}
unit dlist2;

interface

type
generic TList2<TData, TAllocator> = object
public type
  PData = ^TData;
  PNode = ^TNode;
  TNode = record
    Data: TData;
    Prev: PNode;
    Next: PNode;
  end;
private
  FAllocator: TAllocator;
  FHead: PNode;
  FTail: PNode;
public
  procedure Init(AllocatorData: Pointer = nil);
  procedure Done; inline;
  procedure Clear;
  function AllocAfter(Node: PNode): PNode;
  // Removes Node and returns next node
  function Remove(Node: PNode): PNode;
  function IsEmpty: Boolean;
  property Head: PNode read FHead;
  property Tail: PNode read FTail;
end;

implementation

procedure TList2.Init(AllocatorData: Pointer = nil);
begin
  FAllocator.Init(AllocatorData);
  FHead := nil;
  FTail := nil;
end;

procedure TList2.Done;
begin
  Clear;
  FAllocator.Done;
end;

procedure TList2.Clear;
var
  It: PNode;
begin
  It := FHead;
  while It <> nil do begin
    It := Remove(It);
  end;
end;

function TList2.AllocAfter(Node: PNode): PNode;
begin
  Result := FAllocator.Allocate(SizeOf(TNode));
  if Result <> nil then begin
    if Node <> nil then begin
      Result^.Prev := Node;
      Result^.Next := Node^.Next;
      Node^.Next := Result;
      if Node^.Next <> nil then
        Node^.Next^.Prev := Result;
    end else begin
      Result^.Prev := FTail;
      Result^.Next := nil;
      FTail := Result;
    end;
    if FHead = nil then
      FHead := Result;
    if Node = FTail then
      FTail := Result;
  end;
end;

function TList2.Remove(Node: PNode): PNode;
begin
  if Node = nil then
    Exit(nil);
  Result := Node^.Next;
  if FHead = Node then
    FHead := Node^.Next;
  if FTail = Node then
    FTail := Node^.Prev;
  if Node^.Next <> nil then
    Node^.Next^.Prev := nil;
  if Node^.Prev <> nil then
    Node^.Prev^.Next := nil;
  FAllocator.DeAllocate(Node, SizeOf(TNode));
end;

function TList2.IsEmpty: Boolean;
begin
  Result := FHead = nil;
end;

end.
