// Zbiory zaimplementowane
// na listach jednokierunkowych
// Data: 20.06.2014
// (C)2014 mgr Jerzy Wałaszek
//------------------------------

program sets;

// Definicja elementu
// listy jednokierunkowej
type
  PSLel = ^SLel;
  SLel = record
    // Następny element listy
    next : PSLel;
    // Wartość elementu listy
    Data: integer;
  end;

// Definicje funkcji obsługi
// list jako zbiorów
//--------------------------

// Funkcja sprawdza, czy x
// jest elementem zbioru A
// true  - jest
// false - nie jest
//------------------------
function s_isin(p : PSLel;
                x : integer)
                  : boolean;
begin
  // Przeglądamy kolejne elementy A
  while p <> nil do
  begin
    if p^.data = x then
      Exit(true);
    p := p^.next;
  end;
  s_isin := false;
end;

// Procedura dodaje na początek
// zbioru A element x, jeśli zbiór A
// nie zawiera jeszcze takiego elementu
//-------------------------------------
procedure s_add(var A : PSLel;
                    x : integer);
var
  p : PSLel;
begin
  // Jeśli elementu x nie ma w zbiorze A,
  // to go tam wstawiamy
  if not s_isin(A, x) then
  begin
    // Tworzymy nowy element listy
    new(p);
    // Wprowadzamy do niego dane
    p^.Data:= x;
    // Umieszczamy go na początku zbioru
    p^.next := A;
    A := p;
  end;
end;

// Procedura dokonuje połączenia
// zbiorów A i B.
// Wynik jest umieszczany w C
//------------------------------
procedure s_union(A, B : PSLel;
                 var C : PSLel);
var
  p : PSLel;
begin
  // Zerujemy zbiór wyjściowy
  C := nil;
  // Zbiór A kopiujemy do C
  p := A;
  while p <> nil do
  begin
    // Kopiujemy element z A do C
    s_add(C, p^.data);
    // Następny element z A
    p := p^.next;
  end;
  p := B;
  while p <> nil do
  begin
    // Teraz będziemy kopiować do C
    // te elementy z B, których nie ma
    // w A, aby ich nie zdublować
    if not s_isin(A, p^.data) then
      s_add(C, p^.data);
    // Następny element z B
    p := p^.next;
  end;
end;

// Procedura wyznacza część wspólną
// zbiorów A i B. Wynik w C
//---------------------------------
procedure s_intersection(p, B : PSLel;
                        var C : PSLel);
begin
  // Zerujemy zbiór C
  C := nil;
  // Przeglądamy kolejne elementy zbioru A
  while p <> nil do
  begin
    // Jeśli element jest w B, kopiujemy
    if s_isin(B, p^.data) then
      s_add(C, p^.data);
    // Następny element z A
    p := p^.next;
  end;
end;

// Procedura wyznacza różnicę
// zbiorów A i B. Wynik w C
//---------------------------
procedure s_difference(p, B : PSLel;
                      var C : PSLel);
begin
  // Zerujemy zbiór C
  C := nil;
  // Przeglądamy kolejne elementy zbioru A
  while p <> nil do
  begin
    // Jeśli elementu nie ma w B, kopiujemy
    if not s_isin(B, p^.data) then
      s_add(C, p^.data);
    // Następny element z A
    p := p^.next;
  end;
end;

// Funkcja sprawdza, czy zbiór
// B zawiera podzbiór A
// true  - tak
// false - nie
//----------------------------
function s_subset(p, B : PSLel)
                       : boolean;
begin
  // Przeglądamy zbiór A
  while p <> nil do
  begin
    // Jeśli elementu z A nie ma w B, kończymy
    if not s_isin(B, p^.data) then
      Exit(false);
    // Następny element z A
    p := p^.next;
  end;
  // Wszystkie elementy A są w B
  s_subset := true;
end;

// Funkcja oblicza liczebność zbioru
//----------------------------------
function s_size(p : PSLel) : integer;
var
  c : integer;
begin
  // Zerujemy licznik
  c := 0;
  // Przechodzimy przez elementy zbioru p
  while p <> nil do
  begin
    // Elementy zliczamy w c
    inc(c);
    // Następny element z p
    p := p^.next;
  end;
  s_size := c;
end;

// Procedura usuwa element x ze zbioru
//------------------------------------
procedure s_remove(var A : PSLel;
                       x : integer);
var
  p, r : PSLel;
begin
  // Zbiór nie może być pusty
  if A <> nil then
  begin
    // Zapamiętujemy adres początku zbioru
    p := A;
    // Jeśli usuwany element jest na początku,
    if p^.data = x then
    begin
      // to go usuwamy z listy
      A := p^.next;
      // oraz z pamięci
      dispose(p);
    end
    else
    begin
      while (p^.next <> nil) and
            (p^.next^.data <> x) do
        // Szukamy elementu x
        p := p^.next;
      // Jeśli go znajdziemy, to
      if p^.next <> nil then
      begin
        // zapamiętujemy jego adres,
        r := p^.next;
        // usuwamy go z listy
        p^.next := r^.next;
        // oraz z pamięci
        dispose(r);
      end;
    end;
  end;
end;

// Procedura usuwa zawartość zbioru
//---------------------------------
procedure s_clear(var A : PSLel);
var
  p, r : PSLel;
begin
  // Przechodzimy przez kolejne
  // elementy zbioru A
  p := A;
  while p <> nil do
  begin
    // Zapamiętujemy adres
    // bieżącego elementu
    r := p;
    // p ustawiamy na następnik
    p := p^.next;
    // Element usuwamy z pamięci
    dispose(r);
  end;
  // Zbiór staje się pusty
  A := nil;
end;

// Procedura wyświetla zawartość zbioru
//-------------------------------------
procedure s_print(p : PSLel);
begin
  while p <> nil do
  begin
    write(p^.data:3);
    p := p^.next;
  end;
end;

//**********************
//*** PROGRAM GŁÓWNY ***
//**********************

var
  A, B, C : PSLel;
  i, x : integer;

begin
  randomize;
  // Zerujemy zbiory
  A := nil;
  B := nil;
  // Tworzymy dwa zbiory
  // o przypadkowych elementach
  for i := 1 to 10 do
    s_add(A, random(20));
  for i := 1 to 15 do
    s_add(B, random(20));
  // Wyświetlamy je
  write('A =');
  s_print(A);
  writeln;
  writeln('SIZE OF A IS ', s_size(A));
  writeln;
  write('B =');
  s_print(B);
  writeln;
  writeln('SIZE OF B IS ', s_size(B));
  // Suma zbiorów
  writeln;
  write('UNION OF A AND B IS');
  s_union(A, B, C);
  s_print(C);
  writeln;
  writeln('SIZE OF UNION IS ', s_size(c));
  s_clear(C);
  // Iloczyn zbiorów
  writeln;
  write('INTERSECTION OF A AND B IS');
  s_intersection(A, B, C);
  s_print(C);
  writeln;
  writeln('SIZE OF INTERSECTION IS ', s_size(C));
  s_clear(C);
  // Różnica zbiorów
  writeln;
  write('DIFFERENCE OF A AND B IS');
  s_difference(A, B, C);
  s_print(C);
  writeln;
  writeln('SIZE OF DIFFERENCE IS ', s_size(C));
  s_clear(C);
  // Podzbiór
  writeln;
  write('IS');
  s_print(A^.next^.next^.next);
  writeln(' SUBSET OF A?');
  writeln(s_subset(A^.next^.next^.next, A));
  writeln;
  write ('IS');
  s_print(A^.next^.next^.next);
  writeln(' SUBSET OF B?');
  writeln(s_subset(A^.next^.next^.next, B));
  // Usuwanie
  writeln;
  write('FROM A WE REMOVE');
  for i := 1 to 4 do
  begin
    x := random(20);
    write(x:3);
    s_remove(A, x);
  end;
  writeln;
  write('A = ');
  s_print(A);
  writeln;
  writeln('SIZE OF A IS ', s_size(A));
  writeln;
  // Usuwamy wszystkie zbiory
  s_clear(A);
  s_clear(B);
  s_clear(C);
  readln;
end.

// Zbiory zaimplementowane
// na listach jednokierunkowych
// Data: 20.06.2014
// (C)2014 mgr Jerzy Wałaszek
//-----------------------------

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>

using namespace std;

// Definicja elementu
// listy jednokierunkowej
struct SLel
{
  // Następny element listy
  SLel * next;
  // Wartość elementu listy
  int data;
};

// Definicje funkcji obsługi
// list jako zbiorów
//--------------------------

// Funkcja sprawdza, czy x
// jest elementem zbioru A
// true  - jest
// false - nie jest
//-------------------------
bool s_isin(SLel * p, int x)
{
  // Przeglądamy kolejne elementy A
  while(p)
  {
    if(p->data == x) return true;
    p = p->next;
  }
  return false;
};

// Procedura dodaje na początek
// zbioru A element x,
// jeśli zbiór A nie zawiera
// jeszcze takiego elementu.
//-----------------------------
void s_add(SLel * & A, int x)
{
  SLel * p;

  // Jeśli elementu x nie ma
  // w zbiorze A, to go tam wstawiamy
  if(!s_isin(A, x))
  {
    // Tworzymy nowy element listy
    p = new SLel;
    // Wprowadzamy do niego dane
    p->data = x;
    // Umieszczamy go na początku
    // zbioru
    p->next = A;
    A = p;
  }
}

// Procedura dokonuje połączenia
// zbiorów A i B. Wynik jest
// umieszczany w C
//------------------------------
void s_union(SLel * A,
             SLel * B,
             SLel * & C)
{
  SLel * p;

  // Zerujemy zbiór wyjściowy
  C = NULL;
  // Zbiór A kopiujemy do C
  for(p = A; p; p = p->next)
    // Kopiujemy element z A do C
    s_add(C, p->data);
  for(p = B; p; p = p->next)
    // Teraz będziemy kopiować
    // do C te elementy z B,
    // których nie ma w A,
    // aby ich nie zdublować
    if(! s_isin(A, p->data))
      s_add(C, p->data);
}

// Procedura wyznacza część wspólną
// zbiorów A i B. Wynik w C
//---------------------------------
void s_intersection(SLel * p,
                    SLel * B,
                    SLel * & C)
{
  // Zerujemy zbiór C
  C = NULL;
  // Przeglądamy kolejne
  // elementy zbioru A
  while(p)
  {
    // Jeśli element jest w B,
    // kopiujemy
    if(s_isin(B, p->data))
      s_add(C, p->data);
    // Następny element z A
    p = p->next;
  }
}

// Procedura wyznacza różnicę
// zbiorów A i B. Wynik w C
//---------------------------
void s_difference(SLel * p,
                  SLel * B,
                  SLel * & C)
{
  // Zerujemy zbiór C
  C = NULL;
  // Przeglądamy kolejne elementy
  // zbioru A
  while(p)
  {
    // Jeśli elementu nie ma w B,
    // kopiujemy
    if(!s_isin(B, p->data))
      s_add(C, p->data);
    // Następny element z A
    p = p->next;
  }
}

// Funkcja sprawdza, czy zbiór B
// zawiera podzbiór A
// true  - tak
// false - nie
//------------------------------
bool s_subset(SLel * p,
              SLel * B)
{
  // Przeglądamy zbiór A
  while(p)
  {
    // Jeśli elementu z A nie ma w B,
    // kończymy
    if(!s_isin(B, p->data))
      return false;
    // Następny element z A
    p = p->next;
  }
  // Wszystkie elementy A są w B
  return true;
}

// Funkcja oblicza liczebność zbioru
//----------------------------------
int s_size(SLel * p)
{
  // Zerujemy licznik
  int c = 0;
  // Przechodzimy przez
  // elementy zbioru A
  while(p)
  {
    // Elementy zliczamy w c
    c++;
    // Następny element z A
    p = p->next;
  }
  return c;
}

// Procedura usuwa
// element x ze zbioru
//--------------------
void s_remove(SLel * & A, int x)
{
  SLel * p, * r;

  // Zbiór nie może być pusty
  if(A)
  {
    // Zapamiętujemy adres
    // początku zbioru
    p = A;
    // Jeśli usuwany element jest
    // na początku,
    if(p->data == x)
    {
      // to go usuwamy z listy
      A = p->next;
      // oraz z pamięci
      delete p;
    }
    else
    {
      while(p->next &&
           (p->next->data != x))
        // Szukamy elementu x
        p = p->next;
      // Jeśli go znajdziemy, to
      if(p->next)
      {
        // zapamiętujemy jego adres,
        r = p->next;
        // usuwamy go z listy
        p->next = r->next;
        // oraz z pamięci
        delete r;
      }
    }
  }
}

// Procedura usuwa zawartość zbioru
//---------------------------------
void s_clear(SLel *  & A)
{
  SLel * p, *r;

  // Przechodzimy przez kolejne
  // elementy zbioru A
  p = A;
  while(p)
  {
    // Zapamiętujemy adres
    // bieżącego elementu
    r = p;
    // p ustawiamy na następnik
    p = p->next;
    // Element usuwamy z pamięci
    delete r;
  }
  // Zbiór staje się pusty
  A = NULL;
}

// Procedura wyświetla
// zawartość zbioru
//--------------------
void s_print(SLel * p)
{
  while(p)
  {
    cout << setw (3) << p->data;
    p = p->next;
  }
}

//**********************
//*** PROGRAM GŁÓWNY ***
//**********************

int main()
{
  SLel * A, * B, * C;
  int i, x;

  srand (time(NULL));
  // Zerujemy zbiory
  A = B = NULL;
  // Tworzymy dwa zbiory
  // o przypadkowych elementach
  for(i = 0; i < 10; i++)
    s_add(A, rand() % 20);
  for(i = 0; i < 15; i++)
    s_add(B, rand() % 20);
  // Wyświetlamy je
  cout << "A =";
  s_print (A);
  cout << endl
       << "SIZE OF A IS "
       << s_size(A) << endl << endl
       << "B =";
  s_print(B);
  cout << endl
       << "SIZE OF B IS "
       << s_size(B) << endl << endl;
  // Suma zbiorów
  cout << "UNION OF A AND B IS";
  s_union(A, B, C);
  s_print(C);
  cout << endl
       << "SIZE OF UNION IS "
       << s_size(C) << endl << endl;
  s_clear(C);
  // Iloczyn zbiorów
  cout << "INTERSECTION OF A AND B IS";
  s_intersection(A, B, C);
  s_print(C);
  cout << endl
       << "SIZE OF INTERSECTION IS "
       << s_size(C) << endl << endl;
  s_clear(C);
  // Różnica zbiorów
  cout << "DIFFERENCE OF A AND B IS";
  s_difference(A, B, C);
  s_print(C);
  cout << endl
       << "SIZE OF DIFFERENCE IS "
       << s_size(C) << endl << endl;
  s_clear(C);
  // Podzbiór
  cout << "IS";
  s_print(A->next->next->next);
  cout << " SUBSET OF A?" << endl
       << (s_subset(A->next->next->next, A)
           ?"TRUE":"FALSE")
       << endl << endl;
  cout << "IS";
  s_print(A->next->next->next);
  cout << " SUBSET OF B?" << endl
       << (s_subset(A->next->next->next, B)
           ?"TRUE":"FALSE")
       << endl << endl;
  // Usuwanie
  cout << "FROM A WE REMOVE";
  for(i = 0; i < 4; i++)
  {
    x = rand() % 20;
    cout << setw (3) << x;
    s_remove(A, x);
  }
  cout << endl << "A =";
  s_print(A);
  cout << endl
       << "SIZE OF A IS " << s_size(A)
       << endl << endl;
  // Usuwamy wszystkie zbiory
  s_clear(A);
  s_clear(B);
  s_clear(C);
  return 0;
}

' Zbiory zaimplementowane
' na listach jednokierunkowych
' Data: 20.06.2014
' (C)2014 mgr Jerzy Wałaszek
'------------------------------

' Definicja elementu listy jednokierunkowej
Type SLel
  ' Następny element listy
  next As SLel Ptr
  ' Wartość elementu listy
  data As Integer
End Type

' Definicje funkcji obsługi
' list jako zbiorów
'--------------------------

' Funkcja sprawdza, czy x jest
' elementem zbioru A
' 1  - jest
' 0 - nie jest
'-----------------------------
Function s_isin(ByVal p As SLel Ptr, _
                ByVal x As integer) _
                        As Integer
  ' Przeglądamy kolejne elementy A
  While p
    If p->data = x Then Return 1
    p = p->Next
  Wend
  Return 0
End Function

' Procedura dodaje na początek
' zbioru A element x, 
' jeśli zbiór A nie zawiera
' jeszcze takiego elementu.
'-----------------------------
Sub s_add(byref A As SLel Ptr, _
          byval x As Integer)
  Dim As SLel Ptr p

  ' Jeśli elementu x nie ma w zbiorze A,
  ' to go wstawiamy do C
  If s_isin(A, x) = 0 Then
    ' Tworzymy nowy element listy
    p = new SLel
    ' Wprowadzamy do niego dane
    p->data = x
    ' Umieszczamy go na początku zbioru
    p->next = A
    A = p
  End If
End Sub

' Procedura dokonuje połączenia
' zbiorów A i B. Wynik jest umieszczany w C
'------------------------------------------
Sub s_union(ByVal A As SLel Ptr,_
            ByVal B As SLel Ptr,_
            ByRef C As SLel Ptr)
  Dim  As SLel Ptr p

  ' Zerujemy zbiór wyjściowy
  C = 0
  p = A
  While p
    ' Kopiujemy element z A do C
    s_add(C, p->data)
    ' Następny element z A
    p = p->next
  Wend
  p = B
  While p
    ' kopiujemy element,
    ' którego nie ma w A
    If s_isin(A, p->data) = 0 Then _
      s_add(C, p->data)
    ' Następny element z B
    p = p->next
  Wend
End Sub

' Procedura wyznacza część wspólną
' zbiorów A i B. Wynik w C
'---------------------------------
Sub s_intersection(ByVal p As SLel Ptr,_
                   ByVal B As SLel Ptr,_
                   ByRef C As SLel Ptr)
  ' Zerujemy zbiór C
  C = 0
  ' Przeglądamy kolejne elementy zbioru A
  While p
    ' Jeśli element jest w B, kopiujemy
    If s_isin(B, p->Data) = 1 Then _
      s_add(C, p->data)
    ' Następny element z A
    p = p->Next
  Wend
End Sub

' Procedura wyznacza różnicę
' zbiorów A i B. Wynik w C
'---------------------------
Sub s_difference(ByVal p As SLel Ptr,_
                 ByVal B As SLel Ptr,_
                 ByRef C As SLel Ptr)
  ' Zerujemy zbiór C
  C = 0
  ' Przeglądamy kolejne elementy zbioru A
  While p
    ' Jeśli elementu nie ma w B, kopiujemy
    If s_isin(B, p->data) = 0 Then  _
      s_add(C, p->data)
    ' Następny element z A
    p = p->next
  Wend
End Sub

' Funkcja sprawdza,
' czy zbiór B zawiera podzbiór A
' 1 - tak
' 0 - nie
'-------------------------------
Function s_subset(ByVal p As SLel Ptr,_
                  ByVal B As SLel Ptr) _
                          As Integer 
  ' Przeglądamy zbiór A
  While p
    ' Jeśli elementu z A nie ma w B,
    ' kończymy
    If s_isin(B, p->data) = 0 Then _
      Return 0
    ' Następny element z A
    p = p->next
  Wend
  ' Wszystkie elementy A są w B
  Return 1
End Function

' Funkcja oblicza liczebność zbioru
'----------------------------------
Function s_size(ByVal p As SLel Ptr) _
                        As Integer

  ' Zerujemy licznik
  Dim As Integer c = 0

  ' Przechodzimy przez elementy zbioru A
  While p
    ' Elementy zliczamy w c
    c += 1
    ' Następny element z A
    p = p->next
  Wend 
  Return c
End Function

' Procedura usuwa element x ze zbioru
'------------------------------------
Sub s_remove(ByRef A As SLel Ptr,_
             ByVal x As integer)
  Dim As SLel Ptr p, r
  
  ' Zbiór nie może być pusty
  If A Then
    ' Zapamiętujemy adres początku zbioru
    p = A
    ' Jeśli usuwany element
    ' jest na początku, 
    If p->data = x Then
      ' to go usuwamy z listy
      A = p->next
      ' oraz z pamięci
      Delete p
    Else
      while (p->next <> 0) AndAlso _
            (p->next->data <> x)
        ' Szukamy elementu x
        p = p->next
      Wend
      ' Jeśli go znajdziemy, to
      If p->next Then
        ' zapamiętujemy jego adres, 
        r = p->next
        ' usuwamy go z listy
        p->next = r->next
        ' oraz z pamięci
        Delete r
      End If
    End If
  End If
End Sub

' Procedura usuwa zawartość zbioru
'---------------------------------
Sub s_clear(ByRef A As SLel Ptr)
  Dim As SLel Ptr p, r

  ' Przechodzimy przez kolejne
  ' elementy zbioru A
  p = A
  While p
    ' Zapamiętujemy adres bieżącego elementu
    r = p
    ' p ustawiamy na następnik
    p = p->next
    ' Element usuwamy z pamięci
    Delete r
  Wend
  ' Zbiór staje się pusty
  A = 0
End Sub

' Procedura wyświetla zawartość zbioru
'------------------------------------
Sub s_print(ByVal p As SLel Ptr)
  While p
    Print Using "###";p->data;
    p = p->next
  Wend
End Sub

'**********************
'*** PROGRAM GŁÓWNY ***
'**********************

Dim As SLel Ptr A, B, C
Dim As integer i, x

Randomize
' Zerujemy zbiory
A = 0
B = 0
' Tworzymy dwa zbiory o przypadkowych elementach
For i = 1 To 10
  s_add(A, Int(Rnd() * 20))
Next
For i = 1 To 15
  s_add(B, Int(Rnd() * 20))
Next
' Wyświetlamy je
Print "A =";
s_print(A)
Print
Print "SIZE OF A IS"; s_size(A)
Print
Print "B =";
s_print(B)
Print
Print "SIZE OF B IS"; s_size(B)
Print
' Suma zbiorów
Print "UNION OF A AND B IS";
s_union(A, B, C)
s_print(C)
Print
Print "SIZE OF UNION IS"; s_size(C)
Print
s_clear(C)
' Iloczyn zbiorów
Print "INTERSECTION OF A AND B IS";
s_intersection(A, B, C)
s_print(C)
Print
Print "SIZE OF INTERSECTION IS"; s_size(C)
Print
s_clear(C)
' Różnica zbiorów
Print "DIFFERENCE OF A AND B IS";
s_difference(A, B, C)
s_print(C)
Print
Print "SIZE OF DIFFERENCE IS"; s_size(C)
Print
s_clear(C)
' Podzbiór
Print "IS";
s_print(A->next->next->next)
Print " SUBSET OF A?"
If s_subset(A->next->next->next, A) = 1 Then
  Print "TRUE"
Else 
  Print "FALSE"
End If
Print
Print "IS";
s_print(A->next->next->next)
Print " SUBSET OF B?"
If s_subset(A->next->next->next, B) = 1 Then
  Print "TRUE"
Else
  Print "FALSE"
End If
Print
' Usuwanie
Print "FROM A WE REMOVE";
For i = 1 To 4
  x = Int(Rnd() * 20)
  Print Using "###";x;
  s_remove(A, x)
Next
Print
Print "A =";
s_print(A)
Print
Print "SIZE OF A IS"; s_size(A)
Print
' Usuwamy wszystkie zbiory
s_clear(A)
s_clear(B)
s_clear(C)
End