Manipuler les éléments d'un SET de façon ciblée par leur indice

**KlausGunther** · 21/04/2017, 21h39

Normalement, un SET en Delphi représente une collection d'informations du même type. On ne connaît pas la position d'un élément dans un SET, on peut juste savoir si un élément est dans un SET ou non.

Or, je travaille avec des set de caractères représentant des "alphabets". Ils sont déclarés comme suit:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
type
  TAlphabet = set of char;
 
var
  Alphabet1: TAlphabet;
  Alphabet2: TAlphabet; 
  ...

Maiintenant, je peux savoir si un caractère est membre d'un alphabet:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

if car in Alphabet1 then ...

Or, j'ai deux jeux d'alphabets 1 et 2 qui contiennent des éléments associés, comme des parenthèses:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
Alphabet1 := ['(','{','['];
Alphabet1 := [')','}',']'];

J'ai choisi le cas des parenthèses représentant chacune un seul caractère, mais le principe est appicable pour des structures différentes. Mon but: si un candidat car1 est membre de Alphabet1, je voudrais récupérer l'élément car2 de Alphabet2 provenant de la même position !

J'ai trouvé une solution à ce problème, en généralisant une technique publiée ici:
http://stackoverflow.com/questions/3...le-of-type-set
J'ai utilisée l'excelente fonction Cardinality (qui retourne le nombre des éléments d'un SET) pour créer 2 nouvelles fonctions:

Retourner l'indixe d'unn candidat dans un SET quelconque (1, 2, 3, ...):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
  function IndexOf(const PSet: PByteArray; const SizeOfSet(*in bytes*): integer; const aValue: Byte): Integer;
  const
    Masks: array[0..7] of Byte = (1, 2, 4, 8, 16, 32, 64, 128);
  var
    I, J, I1, J1, ind: Integer;
  begin
    Result := -1;
    ind := 0;
    I1 := (aValue shr 3);
    J1 := (aValue and 7);
    for I := 0 to SizeOfSet - 1 do begin
      for J := 0 to 7 do begin
        if (PSet^[I] and Masks[J]) > 0 then begin
          Inc(ind);
          if (I=I1) and (J=J1) then begin
            result := ind;
            exit;
          end;
        end;
      end;
    end;
  end;

et retourner l'élément d'un indice donné d'un SET quelconque:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
  function ElementOf(const PSet: PByteArray; const SizeOfSet(*in bytes*): integer; const aIndex: integer): byte;
  const
    Masks: array[0..7] of Byte = (1, 2, 4, 8, 16, 32, 64, 128);
  var
    I, J, ind: Integer;
  begin
    Result := 0;
    ind := 0;
    for I := 0 to SizeOfSet - 1 do begin
      for J := 0 to 7 do begin
        if (PSet^[I] and Masks[J]) > 0 then begin
          Inc(ind);
          if ind=aIndex then begin
            result := I*8+J;
            exit;
          end;
        end;
      end;
    end;
  end;

Ces fonctions sont appelées comme suit:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
n := IndexOf(@Alphabet1,sizeof(Alphabet1),car);
ch := chr(ElementOf(@Alphabet2,sizeof(Alphabet2),n));

Dans mon cas, la fonction ElementOf retourne une valeur BYTE permettant d'en déduire le caractère recherché. Il est aisé de modifier cela pour d'autres types de SETs.

Voilà. Je voulais partager cela. C'est une astuce qui m'a coûté quelques heures de recherche et de mise au point, mais qui est maintenant parfaitement intégrée dans mes logiciels et rend de bons sersices.

**retwas** · 23/04/2017, 13h15

Je ne sais pas si c'est moi qui comprend pas ou si c'est toi qui t’embête mais, d'après ce que tu dis tu veux faire ça :

Envoyé par KlausGunther

Mon but: si un candidat car1 est membre de Alphabet1, je voudrais récupérer l'élément car2 de Alphabet2 provenant de la même position !

Si ton Alphabet est déclaré ainsi :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

TAlphabet = TList<Char>;

Que tu charges tes deux listes :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
  FAlphabet1 := TAlphabet.Create;
  FAlphabet2 := TAlphabet.Create;
 
  FAlphabet1.Add('(');
  FAlphabet1.Add('{');
  FAlphabet1.Add('[');
 
  FAlphabet2.Add(')');
  FAlphabet2.Add('}');
  FAlphabet2.Add(']');

Pour retourner l’élément de la liste 2 ayant l'indice du caractère trouvé dans la liste 1 :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
procedure GetCharFromAlphabet;
var
  Indice: integer;
begin
  Indice := Alphabet1.IndexOf('{');
 
  if (Indice <> -1) and (Indice <= Alphabet2.Count - 1) then
  begin
    Showmessage(Alphabet2[Indice])
  end
  else
  begin
    ShowMessage('Char non trouvé.');
  end;
end;

**KlausGunther** · 23/04/2017, 15h56

Tu as raison, Retwas. Il y a d'ailleurs 36 façons différentes de réaliser une sorte de "traduction", pour passer d'un caractère (ou d'une chaîne, d'une valeur binaire, ...) à un autre. La solution que tu donnes, en est un exemple.

J'étais intrigué par la gestion des SET. Avec l'opérateur "IN", on peut savoir si un élément est dans un set ou pas. Bien. Et déjà, à la base, il n'y a aucun moyen natif de connaître le nombre d'éléments dans un set. Et pour des raisons de "défi intellectuel", je voulais comprendre l'implémentation de ces objets mystérieux que sont les sets. Et j'ai fini par trouver la page dont l'URL est indiquée dans mon post, qui donne des explications et une fonction, parfaitement opérationnelle, pour retourner le nombre d'éléments d'un set.

Alors, l'étape suivante coulait de source. En réalité, en infiormatique, la notion "d'ensemble non ordonné" n'existe pas. C'est une construction ingtellectuelle qui se traduit, dans la réalité, par des solutions techniques différentes mais qui, toutes, imposent, d'une manière ou d'une autre, une sordre "d'ordonnancement" séquentiel des éléments dans la mémoire de la machine. Et j'ai vu que la fonction de comptage exploite cela. Alors, j'en, ai déduit qu'on peut connaître le numéro d'ordre (l'indice) d'un élément, et en conséquence, récupérer un élément en l'identifiant par sin indice. Ceci était le point de départ de mon exercice.

Je l'emploie dans mon application car j'ai l'intuition (qui reste sûrement à confirmer) que ce système est plus rapide que les méthodes du genre que tu proposes,, tout simplement parce que la recherche est basée sur une opération binaire sur des octets accédés par pointeur.

On pourrait d'ailleurs facilement créer un objet dérivé de TComposant encapsulant un set et implémentant, outre les fonctions de gestion classique des sets sous forme de méthdes, les opérations de IndexOf et ElementOf comme des méthodes. Ca ferait un bel outil, sur le plan intellectuel. Mais le but de mon post était siomplement de partager cette découverte (découverte pour moi, bien sûr...) du fonctionnement interne des objets set. En fait, un pur exercice de style.

**KlausGunther** · 23/04/2017, 17h46

Voici un "habillage" de ces techniques, appliquées à des SET of CHAR, sous forme de composant:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
unit TCharSet;
 
interface
 
uses
  SysUtils, Classes;
 
type
{
  Operator  Operation     Operand Types  Result Type  Example
  --------  ---------     -------------  -----------  -------
  +          union        set            set          Set1 + Set2
  -          difference   set            set          S - T
  *          intersection set            set          S * T
  <=         subset       set            Boolean      Q <= MySet
  >=         superset     set            Boolean      S1 >= S2
  =          equality     set            Boolean      S2 = MySet
  <>         inequality   set            Boolean      MySet <> S1
  in         membership   ordinal, set   Boolean      A in Set1
}
  TSetOfChar = class(TComponent)
  private
    fSet: set of char;
  public
    constructor CreateNew(AOwner: TComponent); //override;
    destructor Destroy; override;
  published
    procedure Clear();                                           // empty the set
    procedure AppendAllCharacters(aString: string);              // append each character of a string as new element
    procedure DoUnion(aSet: TSetOfChar);                         // current set := current set + aSet
    procedure DoDifference(aSet: TSetOfChar);                    // current set := current set - aSet
    procedure DoIntersection(aSet: TSetOfChar);                  // current set := current set * aSet
    function IsSubset(aSet: TSetOfChar): boolean;                // checks if aSet is subset of current set
    function IsSuperset(aSet: TSetOfChar): boolean;              // checks if aSet is superset of current set
    function IsEqual(aSet: TSetOfChar): boolean;                 // checks if aSet is equal tp current set
    function IsInequal(aSet: TSetOfChar): boolean;               // checks if aSet is different from current set
    function IsMember(aChar: Char): boolean;                     // checks if aSet is element is in current set
 
    function Count(): integer;                                   // get element count
    function GetIndexOfChar(aChar: Char): integer;               // get index of a specific element
    function GetElementOfIndex(aIndex: integer): Char;           // get an element by its index
  end;
 
 
implementation
 
{ ************* methods and properties fot TSetOfChar }
 
constructor TSetOfChar.CreateNew(AOwner: TComponent);
begin
  fSet := [];
end;
 
destructor TSetOfChar.Destroy();
begin
  fSet := [];
end;
 
procedure TSetOfChar.Clear();
begin
  fSet := [];
end;
 
procedure TSetOfChar.AppendAllCharacters(aString: string);
var
  i: integer;
begin
  for i:=1 to length(aString) do include(fSet,aString[i]);
end;
 
procedure  TSetOfChar.DoUnion(aSet: TSetOfChar);
begin
  fSet := fSet + aSet.fSet;
end;
 
procedure  TSetOfChar.DoDifference(aSet: TSetOfChar);
begin
  fSet := fSet - aSet.fSet;
end;
 
procedure  TSetOfChar.DoIntersection(aSet: TSetOfChar);
begin
  fSet := fSet * aSet.fSet;
end;
 
function TSetOfChar.IsSubset(aSet: TSetOfChar): boolean;
begin
  result := fSet <= aSet.fSet;
end;
 
function TSetOfChar.IsSuperset(aSet: TSetOfChar): boolean;
begin
  result := fSet >= aSet.fSet;
end;
 
function TSetOfChar.IsEqual(aSet: TSetOfChar): boolean;
begin
  result := fSet = aSet.fSet;
end;
 
function TSetOfChar.IsInequal(aSet: TSetOfChar): boolean;
begin
  result := fSet <> aSet.fSet;
end;
 
function TSetOfChar.IsMember(aChar: Char): boolean;
begin
  result := aChar in fSet;
end;
 
function TSetOfChar.Count(): integer;
  function Cardinality(const PSet: PByteArray; const SizeOfSet(*in bytes*): Integer): Integer;
  const
    Masks: array[0..7] of Byte = (1, 2, 4, 8, 16, 32, 64, 128);
  var
    I, J: Integer;
  begin
    Result := 0;
    for I := 0 to SizeOfSet - 1 do
      for J := 0 to 7 do
        if (PSet^[I] and Masks[J]) > 0 then
          Inc(Result);
  end;
begin
  result := Cardinality(@fSet,SizeOf(fSet));
end;
 
function TSetOfChar.GetIndexOfChar(aChar: Char):integer;
  function IndexOf(const PSet: PByteArray; const SizeOfSet(*in bytes*): integer; const aValue: Byte): Integer;
  const
    Masks: array[0..7] of Byte = (1, 2, 4, 8, 16, 32, 64, 128);
  var
    I, J, I1, J1, ind: Integer;
  begin
    Result := -1;
    ind := 0;
    I1 := (aValue shr 3);
    J1 := (aValue and 7);
    for I := 0 to SizeOfSet - 1 do begin
      for J := 0 to 7 do begin
        if (PSet^[I] and Masks[J]) > 0 then begin
          Inc(ind);
          if (I=I1) and (J=J1) then begin
            result := ind;
            exit;
          end;
        end;
      end;
    end;
  end;
begin
  result := IndexOf(@fSet,SizeOf(fSet),byte(aChar));
end;
 
function TSetOfChar.GetElementOfIndex(aIndex: integer): Char;
  function ElementOf(const PSet: PByteArray; const SizeOfSet(*in bytes*): integer; const aIndex: integer): byte;
  const
    Masks: array[0..7] of Byte = (1, 2, 4, 8, 16, 32, 64, 128);
  var
    I, J, ind: Integer;
  begin
    Result := 0;
    ind := 0;
    for I := 0 to SizeOfSet - 1 do begin
      for J := 0 to 7 do begin
        if (PSet^[I] and Masks[J]) > 0 then begin
          Inc(ind);
          if ind=aIndex then begin
            result := I*8+J;
            exit;
          end;
        end;
      end;
    end;
  end;
begin
  result := chr(ElementOf(@fSet,SizeOf(fSet),aIndex))
end;
 
end.

Utilisation:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
...
uses ... , TCharSet, ...
 
var
  SC: TSetOfChar;
...
begin
...
  SC := TSetOfChar.CreateNew(nil);
  SC.AppendAllCharacters('ABCDEFG');
  showmessage('Le set a '+inttostr(SC.Count)+' éléments');
  if SC.IsMember('C') then showmessage('C est un élément du set')
                      else showmessage('C n''est pas un élément du set');
  if SC.IsMember('H') then showmessage('H est un élément du set')
                      else showmessage('H n''est pas un élément du set');
  ...

On a les méthodes et propriétés suivantes:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
    constructor CreateNew(AOwner: TComponent);                   // create a new component
    destructor Destroy; override;                                // delete the component
    procedure Clear();                                           // empty the set
 
    procedure AppendAllCharacters(aString: string);              // append each character of a string as new element
    procedure DoUnion(aSet: TSetOfChar);                         // current set := current set + aSet
    procedure DoDifference(aSet: TSetOfChar);                    // current set := current set - aSet
    procedure DoIntersection(aSet: TSetOfChar);                  // current set := current set * aSet
    function IsSubset(aSet: TSetOfChar): boolean;                // checks if aSet is subset of current set
    function IsSuperset(aSet: TSetOfChar): boolean;              // checks if aSet is superset of current set
    function IsEqual(aSet: TSetOfChar): boolean;                 // checks if aSet is equal tp current set
    function IsInequal(aSet: TSetOfChar): boolean;               // checks if aSet is different from current set
    function IsMember(aChar: Char): boolean;                     // checks if aSet is element is in current set
 
    function Count(): integer;                                   // get element count
    function GetIndexOfChar(aChar: Char): integer;               // get index of a specific element
    function GetElementOfIndex(aIndex: integer): Char;           // get an element by its index

**Andnotor** · 24/04/2017, 11h47

Ca peut pas marcher ton histoire.

Un set est un array of bit. Insérer un élément est juste activer un bit, il n'y a pas de notion d'ordre d'insertion.

Ca fonctionne dans ton cas parce que dans la table Ansi, ] suit [, ) suit ( et } suit {. Mais si maintenant tu inverses la deuxième liste :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
Alphabet1 := ['(','{','['];
Alphabet2 := [']','}',')'];

Les paires sont toujours identiques [], () et {}.
Et cela s'explique aisément simplement en observant les deux ensembles en héxa :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
                           (                 [           {
Alphabet1 = 00 00 00 00 00 01 00 00 00 00 00 08 00 00 00 08 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
                           )                 ]           }
Alphabet2 = 00 00 00 00 00 02 00 00 00 00 00 20 00 00 00 20 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

ord(')') = 41 = bit 40 est plus petit que ord(']') = 93 = bit 92 et apparaît donc toujours avant dans ta boucle, ) reste le premier élément.

Si on remplace ) par », le résultat pour [ est }, deuxième élément (dans l'ordre Ansi) dans Alphabet1 et deuxième élément (dans l'ordre Ansi) dans Alphabet2 :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
Alphabet1 := ['(','{','['];
Alphabet2 := ['»','}',']'];
car := '[';

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
                           (                 [           {
Alphabet1 = 00 00 00 00 00 01 00 00 00 00 00 08 00 00 00 08 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
                                             ]           }                       »
Alphabet2 = 00 00 00 00 00 00 00 00 00 00 00 20 00 00 00 20 00 00 00 00 00 00 00 08 00 00 00 00 00 00 00 00

Donc oui tu peux compter le nombre d'éléments dans l'ensemble (l'exemple StackOverflow) mais pas en déterminer l'ordre d'insertion

**KlausGunther** · 24/04/2017, 12h02

Merci pour ces explications, Andnotor. Cela clarifie la situation.

En effet, dans mon application, je charge les sets, toujours, par un jeu de caractères triés dans l'orde numérique des codes ASCII. Cela me paraissait judicieux, mais sans raison technique particulière. Je constate donc que mon "astuce" ne s'applique que dans une situation très précise et pas dans le cas général. Dommage, mais on ne lute pas contre des données techniques...

Donc, ma trouvaille n'en pas vraiment une, mais j'ai appris quelque chose. Merci à vous tous !

Manipuler les éléments d'un SET de façon ciblée par leur indice

Langage Delphi

Discussions similaires

Partager

Partager