Nachbau einer C++ MAP mittels FPC (oder auch wie verwendet man generics?) [gelöst]

[corpsman]

Servus zusammen,
ich versuche gerade eine C++ Map ( https://en.cppreference.com/w/cpp/container/map )mittels FPC nach zu bauen.
So wie ich das Verstehe ist die C++ Map ein Array bestehend aus tuppeln. Nach dem 1. Element (first) kann man suchen / Sortieren und all so kram, das 2. Element (second) ist generisch.

Basierend darauf habe ich mir mal folgende Classe gebastelt:

Code: Alles auswählen

Unit umap;

{$MODE ObjFPC}{$H+}

Interface

Uses
  Classes, SysUtils;

Type
  { TMap }

  Generic TMap < T > = Class
  Type
    TPair = Record
      first: integer;
      second: T;
    End;
  private
    aReadPointer: integer;
    fdata: Array Of TPair;
    Function getElement(index: integer): T;
    Procedure SetElement(index: integer; AValue: T);
  public
    Property Element[index: integer]: T read getElement write SetElement; default;
    Procedure Insert(Index: Integer; Second: T);
    Constructor Create();
    Function First(): TPair; // Warum aktzeptiert der Compiler diese Funktion überhaupt ?
    Function Next(): TPair; // Warum aktzeptiert der Compiler diese Funktion überhaupt ?
    Function Count: integer;
  End;

Implementation

function TMap.getElement(index: integer): T;
Var
  i: Integer;
Begin
  For i := 0 To high(fdata) Do Begin
    If fdata[i].first = index Then Begin
      result := fdata[i].second;
    End;
  End;
  Raise exception.create('Not found.');
End;

procedure TMap.SetElement(index: integer; AValue: T);
Var
  i: Integer;
Begin
  For i := 0 To high(fdata) Do Begin
    If fdata[i].first = index Then Begin
      fdata[i].second := AValue;
    End;
  End;
  Insert(index, AValue);
End;

procedure TMap.Insert(Index: Integer; Second: T);
Var
  i: Integer;
Begin
  For i := 0 To high(fdata) Do Begin
    If fdata[i].first = index Then Begin
      Raise exception.create('Error, already exists.');
    End;
  End;
  setlength(fdata, high(fdata) + 2);
  fdata[high(fdata)].first := index;
  fdata[high(fdata)].second := Second;
End;

constructor TMap.Create;
Begin
  fdata := Nil;
  aReadPointer := -1;
End;

function TMap.First: TPair;
Begin
  aReadPointer := 0;
  result := fdata[aReadPointer];
End;

function TMap.Next: TPair;
Begin
  If aReadPointer = -1 Then Begin
    Raise exception.Create('missed "first" call');
  End;
  inc(aReadPointer);
  If aReadPointer > high(fdata) Then Begin
    Raise exception.Create('No next.');
  End;
  result := fdata[aReadPointer];
End;

function TMap.Count: integer;
Begin
  result := length(fdata);
End;

End.

Der Compiler findet das OK, und compiliert das auch, ok, dann will ich das ding auch mal nutzen:

Code: Alles auswählen

type
  TPointMap = specialize TMap < TPoint > ; 

Procedure TForm1.Button1Click(Sender: TObject);
var  pm: TPointMap;  
  p: tpair; // ----------- Hier ist das Problem, dass kennt er net
  i: Integer;

Begin
  pm := TPointMap.create();  
  // Einfügen    
  pm.Insert(42, point(1, 42));
  pm[42] := point(2,42); // Überschreiben
  pm[40] := point(1,40); // implizites einfügen
  // -- Iterieren
  p := pm.First();
  For i := 0 To pm.Count - 1 Do Begin

    p := pm.Next();
  End;
End;     

Das Problem das ich nun habe ist, pm.first gibt ja den generischen Typ wieder den kennt der Compiler an der Stelle aber nicht. Wie iterriere ich nun also durch meine Daten ?

[theo]

Ist das hier etwas anderes?
https://www.freepascal.org/docs-html/rt ... pgmap.html

[corpsman]

lol das scheint genau das zu sein, nur hatte ich es halt nicht gefunden, danke. das ziehe ich mir gleich mal rein

[theo]

Bei dem Beispiel hier müsste man noch darauf hinweisen, dass das Delphi Syntax ({$mode delphi}) ist, oder? https://wiki.freepascal.org/TFPGMap

Mit {$mode objfpc} eher:

Code: Alles auswählen

type
  TDict = class(specialize TFPGMap<string, integer>);
...
var
  Dict: TDict;
begin
  Dict := TDict.Create;

Es gibt übrigens noch mehr Optionen in dieser Richtung.
Hier ein Überblick: https://wiki.freepascal.org/Data_Struct ... ollections

[corpsman]

Also das hier funktioniert nun bei mir :

Code: Alles auswählen

uses fgl;
 TNode = Record
 x,y:integer;
 end;
  TNodeMap = specialize TFPGMap < integer, TNode > ;

Hab nur ein bisschen Gebraucht, bis ich geblickt habe wie man sauber mit kriegt, was ein Index, Key und Data ist.

Einen Iterator habe ich noch nicht gefunden , den ich dann mit ner While laufen lassen könnte, also verwende ich das Pattern der Schleife Rückwärtslaufen lassen, wenn ich verschiedene Array elemente löschen will (in der Annahme dass TMap im Hintergrund mit einem 0 basierten Array arbeitet...), ist diese Annahme zutreffend ?

Code: Alles auswählen

var
  nodeMap:TNodeMap;
  itNeuron:integer;
begin
...
    For itNeuron := nodeMap.Count - 1 Downto 0 Do Begin
      If (fancy_Bedingung) then begin
        nodeMap.Delete(itNeuron);
      End;
  end;

[PascalDragon]

Code: Alles auswählen

type
  TPointMap = specialize TMap < TPoint > ; 

Procedure TForm1.Button1Click(Sender: TObject);
var  pm: TPointMap;  
  p: tpair; // ----------- Hier ist das Problem, dass kennt er net
  i: Integer;

Begin
  pm := TPointMap.create();  
  // Einfügen    
  pm.Insert(42, point(1, 42));
  pm[42] := point(2,42); // Überschreiben
  pm[40] := point(1,40); // implizites einfügen
  // -- Iterieren
  p := pm.First();
  For i := 0 To pm.Count - 1 Do Begin

    p := pm.Next();
  End;
End;     

Das Problem das ich nun habe ist, pm.first gibt ja den generischen Typ wieder den kennt der Compiler an der Stelle aber nicht. Wie iterriere ich nun also durch meine Daten ?

Wieso erwartest du, dass ein Typ, der innerhalb von TMap<> deklariert ist, global verfügbar ist? Schließlich könnten andere Typen ja auch ein TPair enthalten. Also: richtigen Präfix verwenden, genauso wenn du einen Bezeichner in mehreren Units hast (nur mit dem Unterschied, dass der Bereich eines Typs nicht komplett verfügbar ist, während das bei einer Unit ja der Fall ist): p: TPointMap.TPair. Das gilt übrigens komplett unabhängig von Generics.

[theo]

(in der Annahme dass TMap im Hintergrund mit einem 0 basierten Array arbeitet...), ist diese Annahme zutreffend ?

Keine Ahnung, du hast doch den Quellcode.

Code: Alles auswählen

  TFPSList = class(TObject)
  protected
    FList: PByte;       

Ist ein PByte.