{$MODE OBJFPC}
{$MODESWITCH AUTODEREF}
unit dlist_oldstyle;

interface

uses
  delement_oldstyle;

type
PNode = ^TNode;
TNode = record
  Prev, Next: PNode;
end;

PList = ^TList;
TList = object
private
  FElementSize: LongInt;
  FMethods: PElementMethods;
  FHead: PNode;
  FTail: PNode;
  FDummy: TNode;
public
  procedure Init(ElementSize: LongInt; Methods: PElementMethods = nil);
  procedure Done;
  procedure Clear;
  function Next(var Data: Pointer): Boolean; inline;
  function Head: Pointer;
  function Add(P: Pointer): Pointer;
  function AddBefore(X, Y: Pointer): Pointer; // adds X before Y
  function Del(P: Pointer): Pointer;
  function AddSorted(X: Pointer; LessThan: TLessThan): Pointer;
protected
  function DeleteNode(Node: PNode): PNode;
end;

implementation

function NodeByData(Data: Pointer): PNode; inline;
begin
  Result := Data - SizeOf(TNode);
end;

function DataByNode(Node: PNode): Pointer; inline;
begin
  Result := Pointer(Node) + SizeOf(TNode);
end;

procedure TList.Init(ElementSize: LongInt; Methods: PElementMethods = nil);
begin
  FElementSize := ElementSize;
  FMethods := Methods;
  if FMethods = nil then
    FMethods := @ELEMENT_METHODS_DEFAULT;
  FHead := @FDummy;
  FTail := FHead;
  FDummy.Prev := nil;
  FDummy.Next := nil;
end;

procedure TList.Done;
begin
  Clear;
end;

procedure TList.Clear;
var
  Node: PNode;
begin
  Node := FHead^.Next;
  while Node <> nil do
    Node := DeleteNode(Node);
end;

function TList.Next(var Data: Pointer): Boolean;
var
  Node: PNode;
begin
  Node := NodeByData(Data)^.Next;
  Result := Node <> nil;
  if Result then
    Data := DataByNode(Node);
end;

function TList.Head: Pointer;
begin
  Result := DataByNode(FHead);
end;

function TList.Add(P: Pointer): Pointer;
var
  Node: PNode;
begin
  Node := GetMem(SizeOf(TNode) + FElementSize);
  FTail^.Next := Node;
  Node^.Prev := FTail;
  Node^.Next := nil;
  FMethods^.Copy(FElementSize, P, DataByNode(Node), FMethods);
  FTail := Node;
  Result := DataByNode(Node);
end;

function TList.AddBefore(X, Y: Pointer): Pointer;
var
  Node, YNode: PNode;
begin
  Node := GetMem(SizeOf(TNode) + FElementSize);
  YNode := NodeByData(Y);
  Node^.Prev := YNode^.Prev;
  Node^.Next := YNode;
  YNode^.Prev := Node;
  Node^.Prev^.Next := Node;
  FMethods^.Copy(FElementSize, X, DataByNode(Node), FMethods);
  Result := DataByNode(Node);
end;

function TList.Del(P: Pointer): Pointer;
begin
  Result := DataByNode(DeleteNode(NodeByData(P)));
end;

function TList.AddSorted(X: Pointer; LessThan: TLessThan): Pointer;
var
  Data: Pointer;
begin
  Data := Head;
  while Next(Data) do
    if LessThan(X, Data) then
      Exit(AddBefore(X, Data));
  Exit(Add(X));
end;

function TList.DeleteNode(Node: PNode): PNode;
begin
  Result := Node^.Next;
  if Node^.Prev <> nil then begin
    Node^.Prev^.Next := Node^.Next;
  end else
    FHead := Node^.Next;
  if Node^.Next <> nil then begin
    Node^.Next^.Prev := Node^.Prev;
  end else
    FTail := Node^.Prev;
  FMethods.Delete(FElementSize, DataByNode(Node), FMethods);
  FreeMem(Pointer(Node));
end;

end.
