🚀 go-pugleaf

Witam, w tym poście chcę przedstawić moje rozwiązanie dotyczące tworzenia i posługiwania się zbiorami o dowolnej wielkości. Krytyka i alternatywne propozycje mile widziane. 
Biblioteka i kody źródłowe do pobrania ze strony https://apl.home.amu.edu.pl/apl/
Pozdrawiam,
apl

Typ zbiorowy w Delhi pozwala operować na zbiorach zawierających do 256 elementów. Stan ten można łatwo zmienić. Przedstawiamy tu metodę tworzenia i obsługi zbiorów o praktycznie nieograniczonej licz-bie elementów.
W Delhi (jak również i w Turbo-Pascalu), wartości typu zbiorowego są odnotowywane w ten sposób, że każdemu elementowi zbioru jest przyporządkowany jeden bit. Ustawienie bitu na 1 sygnalizuje obecność elementu, a ustawienie na 0 jego nieobecność. Każdy bajt może zatem kodować obecność ośmiu elemen-tów. Ten sposób kodowania zbiorów jest bardzo oszczędny i z tego względu chcieliśmy go zachować. 
Delhi przeznacza na zapis zmiennej zbiorowej nie więcej niż 32 bajty, stąd wspomniane ograniczenie li-czebności zbiorów. Można to zmienić przeznaczając na kodowanie zbiorów strukturę o większych roz-miarach, np. tablica array[byte] of byte pozwoli zapisywać zbiory o 2048 elementach. Wystarczy więc zadeklarować tablicę o odpowiednio dużych rozmiarach o elementach typu byte (ze względu na prostotę obliczeń) i następnie utworzyć podprogramy modyfikujące i odczytujące odpowiednie bity owej struktury, aby móc posługiwać się zbiorami o nieograniczonej praktycznie wielkości.
Do właściwego bitu można dotrzeć posługując się maskami i operacjami bitowymi. Zakładając że ele-menty tablicy są indeksowane zaczynając od 0, bajt w którym znajduje się bit związany z danym elemen-tem zbioru można obliczyć wg wzoru
m= i div 8, 
a numer bitu wg wzoru 
n=i mod 8,
gdzie i jest numerem elementu, zaś maska, to liczba
l=1 shl n. 

Przykładowo, przy deklaracjach 

type TarrSet = array[byte] of byte;
procedure ilmn(const i:word;var l,m,n:word);
 
  Begin
   m:=i div 8;  
   n:=i mod 8;  
   l:=1 shl n;  
  End;{lmn}
  
elementy do zbioru można włączać za pomocą procedury:

procedure includeToSet(var s:TarrSet;i:word);
 //włącza liczbę i do zbioru s
  var l,m,n:word;
  Begin
   ilmn(i,l,m,n);
   s[m]:=l or s[m];
  End;{includeToSet}

W załączonym tekście modułu pn. „Megasety” zamieszczamy podprogramy do włączania i wyłączania elementów ze zbioru, obliczania sumy różnicy i iloczynu zbiorów, sprawdzania zawartości zbioru i przy-należności elementu do zbioru. Dołączamy też prosty program demonstrujący ich użycie.

Andrzej Pluciński
apl@amu.edu.pl