unit CyclicList;
interface
type
TSortMode = (smAscending, smDescending);
TInsertMode = (imBefore, imAfter);
TNode =
class
protected
FNext, FPrevious: TNode;
FData: Variant;
public
property Previous: TNode
read FPrevious
write FPrevious;
property Next: TNode
read FNext
write FNext;
property Data: Variant
read FData
write FData;
end;
TIterator =
class;
TCyclicList =
class
protected
FFirst, FLast: TNode;
FCount: Cardinal;
procedure QuickSortAsc(iLo, iHi: Cardinal);
procedure QuickSortDesc(iLo, iHi: Cardinal);
function GetNode(
Index: Cardinal): TNode;
public
constructor Create;
destructor Destroy;
override;
procedure Clear;
function IsEmpty: Boolean;
function Get(
Index: Cardinal): Variant;
function GetObject(
Index: Cardinal): TObject;
procedure Put(
Index: Cardinal; Value: Variant);
procedure PutObject(
Index: Cardinal; Obj: TObject);
procedure Add(Data: Variant);
procedure AddObject(Obj: TObject);
procedure Insert(
Index: Cardinal; Data: Variant; InsertMode:
TInsertMode = imBefore);
procedure Delete(
Index: Cardinal);
procedure Sort(SortMode: TSortMode = smAscending);
function GetRandom: Variant;
function MakeIterator: TIterator;
property Count: Cardinal
read FCount;
property Items[
Index: Cardinal]: Variant
read Get
write Put;
default;
end;
TIterator =
class
private
List: TCyclicList;
Node: TNode;
FIndex: Cardinal;
public
constructor Create(List: TCyclicList; FirstNode: TNode);
function EndOfList: Boolean;
function Next: Variant;
function NextObject: TObject;
function Previous: Variant;
function PreviousObject: TObject;
procedure Put(Data: Variant);
procedure PutObject(Obj: TObject);
procedure JumpForward(Steps: Cardinal);
procedure JumpBackward(Steps: Cardinal);
function GetRandom: Variant;
function GetRandomObject: TObject;
property Index: Cardinal
read FIndex;
end;
implementation
constructor TCyclicList.Create;
begin
inherited Create;
FFirst :=
nil;
FLast :=
nil;
FCount := 0;
Randomize;
end;
destructor TCyclicList.Destroy;
begin
Clear;
inherited Destroy;
end;
// Löscht alle Listenelemente
procedure TCyclicList.Clear;
var
node, node2: TNode;
begin
node := FFirst;
repeat
node2 := node.next;
node.Free;
node := node2;
until (node <>
nil)
and(node <> FLast);
FFirst :=
nil;
FLast :=
nil;
FCount := 0;
end;
// Gibt true zurück, wenn die Liste leer ist
function TCyclicList.IsEmpty: Boolean;
begin
Result := FFirst =
nil;
end;
// Gibt den Knoten an gegebenem Index zurück
function TCyclicList.GetNode(
Index: Cardinal): TNode;
var
I: Cardinal;
begin
Index :=
Index mod FCount;
if Index <= (FCount
div 2=
then
begin
Result := FFirst;
if Index > 0
then
for I := 0
to Index-1
do
Result := Result.Next
end
else begin
Result := FLast;
if Index < FCount-1
then
for I := count-1
downto Index do
Result := Result.Previous;
end;
end;
// Gibt Inhalt des Knotens an gegebenem Index zurück
function TCyclicList.Get(
Index: Cardinal): Variant;
begin
Result := GetNode(
Index).Data;
end;
// Konvertiert den Inhalt des Knotens an gegebenem Index in ein TObject
// und gibt dieses zurück
function TCyclicList.GetObject(
Index: Cardinal): TObject;
begin
Result := TObject(Pointer(Integer(Get(
Index))));
end;
// Setzt Inhalt des Knotens an gegebenem Index auf Value.
procedure TCyclicList.Put(
Index: Cardinal; Value: Variant);
begin
GetNode(
Index).Data := Value;
end;
// Setzt Inhalt des Knotens an gegebenem Index auf Obj.
procedure TCyclicList.PutObject(
Index: Cardinal; Obj: TObject);
begin
GetNode(
Index).Data := Integer(Obj);
end;
// Fügt einen Knoten ans Ende der Liste hinzu
procedure TCyclicList.Add(Data: Variant);
var
Node: TNode;
begin
Node := TNode.Create;
Node.Data := Data;
if IsEmpty
then
begin
Node.Next := Node;
Node.Previous := Node;
FFirst := Node;
FLast := Node;
end else
begin
FFirst.Previous := Node;
FLast.Next := Node;
Node.Previous := FLast;
Node.Next := FFirst;
FLast := Node;
end;
inc(FCount);
end;
// Fügt einen Knoten ans Ende der Liste hinzu. (Inhalt wird auf Obj gesetzt)
procedure TCyclicList.AddObject(Obj: TObject);
begin
Add(Integer(Obj));
end;
// Bei InsertMode = imBefore: Fügt neuen Knoten vor dem Knoten mit
// gegebenem Index hinzu.
// Bei InsertMode = imAfter: Fügt neuen Knoten nach dem Knoten mit
// gegebenem Index hinzu.
procedure TCyclicList.Insert(
Index: Cardinal; Data: Variant; InsertMode:
TInsertMode = imBefore);
var
insertpoint, node: TNode;
begin
if Index >= FCount
then
begin
Add(Data);
Exit;
end;
insertpoint := GetNode(
Index);
node := TNode.Create;
node.Data := Data;
case InsertMode
of
imBefore:
begin
Node.Previous := insertpoint.Previous;
Node.Next := insertpoint;
insertpoint.Previous.Next := Node;
insertpoint.Previous := Node;
if insertpoint = FFirst
then
FFirst := Node;
end;
imAfter:
begin
Node.Previous := insertpoint;
Node.Next := insertpoint.Next;
insertpoint.Next.Previous := Node;
insertpoint.Next := Node;
if insertpoint = FLast
then
FLast := Node;
end;
end;
inc(FCount);
end;
// Löscht Knoten an gegebenem Index.
procedure TCyclicList.Delete(
Index: Cardinal);
var
node: TNode;
begin
node := GetNode(
Index);
if FCount = 1
then
begin
node.Free;
FFirst :=
nil;
FLast :=
nil;
dec(FCount);
exit;
end;
node.previous.Next := node.Next;
node.Next.previous := node.previous;
if node=FFirst
then FFirst := node.Next;
if node=FLast
then FLast := node.Previous;
node.Free;
dec(FCount);
end;
// Führt aufsteigenden Quicksort durch
procedure TCyclicList.QuickSortAsc(iLo, iHi: Cardinal);
var
Lo, Hi, Mid: Cardinal;
T: Variant;
begin
Lo := iLo;
Hi := iHi;
Mid := Get((Lo+Hi)
div 2);
repeat
while Get(Lo) < Mid
do
Inc(Lo);
while Get(Hi) > Mid
do
Dec(Hi);
if Lo <= Hi
then
begin
T := Get(Lo);
Put(Lo, Get(Hi));
Put(Hi, T);
Inc(Lo);
Dec(Hi);
end;
until Lo>Hi;
if Hi > iLo
then
QuickSortAsc(iLo, Hi);
if Lo < iHi
then
QuickSortAsc(Lo, iHi);
end;
// Fügt absteigenden Quicksort durch
procedure TCyclicList.QuickSortDesc(iLo, iHi: Cardinal);
var
Lo, Hi, Mid: Cardinal;
T: Variant;
begin
Lo := iLo;
Hi := iHi;
Mid := Get((Lo+Hi)
div 2);
repeat
while Get(Lo) > Mid
do
Inc(Lo);
while Get(Hi) < Mid
do
Dec(Hi);
if Lo <= Hi
then
begin
T := Get(Lo);
Put(Lo, Get(Hi));
Put(Hi, T);
Inc(Lo);
Dec(Hi);
end;
until Lo > Hi;
if Hi > iLo
then
QuickSortDesc(iLo, Hi);
if Lo < iHi
then
QuickSortDesc(Lo, iHi);
end;
// Sortier auf- bzw. absteigend
procedure TCyclicList.Sort(SortMode: TSortMode = smAscending);
begin
if SortMode = smAscending
then
QuickSortAsc(0, FCount-1)
else
QuickSortDesc(0, FCount-1);
end;
// Gibt den Wert eines zufälligen Knotens zurück.
function TCyclicList.GetRandom: Variant;
begin
Result := GetNode(Random(count)).Data;
end;
// Erzeugt ein Iteratorobjekt. Wenn es mehrmals verwendet werden soll,
// muss es in einer Variable gespeichert werden.
function TCyclicLIst.MakeIterator: TIterator;
begin
Result := TIterator.Create(Self, FFirst);
end;
constructor TIterator.Create(List: TCyclicList; FirstNode: TNode);
begin
inherited Create;
Self.List := List;
Self.Node := FirstNode.Previous;
FIndex := 0;
end;
// Gibt True zurück, wenn das Listenende erreicht wurde.
function TIterator.EndOfList: Boolean;
begin
Result :=
Index = List.Count-1;
end;
// Gibt den nächsten Wert zurück.
function TIterator.Next: Variant;
begin
Node := Node.Next;
Result := Node.Data;
FIndex := (FIndex+1)
mod List.count;
end;
// Gibt den nächsten Wert als TObject zurück.
function TIterator.NextObject: TObject;
begin
Result := TObject(Pointer(Integer(Next)));
end;
// Gibt den vorherigen Wert zurück.
function TIterator.Previous: Variant;
begin
Node := Node.Previous;
Result := Node.Data;
FIndex := (FIndex-1)
mod List.count;
end;
// Gibt den vorherigen Wert als TObject zurück.
function TIterator.PreviousObject: TObject;
begin
Result := TObject(Pointer(Integer(Previous)));
end;
// Setzt den aktuellen Wert auf Data.
procedure TIterator.Put(Data: Variant);
begin
Node.Data := Data;
end;
// Setzt den aktuellen Wert auf Obj.
procedure TIterator.PutObject(Obj: TObject);
begin
Node.Data := Integer(Obj);
end;
// Springt Steps Elemente nach vorne.
procedure TIterator.JumpForward(Steps: Cardinal);
var
I: Cardinal;
begin
for I := 1
to Steps
do
Node := Node.Next;
FIndex := (FIndex+Steps)
mod List.count;
end;
// Springt Steps Elemente nach hinten.
procedure TIterator.JumpBackward(Steps: Cardinal);
var
I: Cardinal;
begin
for I := 1
to Steps
do Node := Node.Previous;
FIndex := (FIndex-Steps)
mod List.count;
end;
// Gibt einen Wert an zufälliger Position zurück.
function TIterator.GetRandom: Variant;
begin
Self.FIndex := Random(List.Count);
Result := List.Get(FIndex);
end;
// Gibt einen Wert an zufälliger Position an TObject zurück.
function TIterator.GetRandomObject: TObject;
begin
Result := TObject(Pointer(Integer(GetRandom)));
end;
end.