
Data Structure

This illustrates a data structure, a means of storing data within a program.

You may see other such structures in the Data Structures category.
A   set  is a collection of elements, without duplicates and without order.



Task

Show each of these set operations:

 Set creation
 Test m ∈ S -- "m is an element in set S"
 A ∪ B -- union; a set of all elements either in set A or in set B.
 A ∩ B -- intersection; a set of all elements in both set A and set B.
 A ∖ B -- difference; a set of all elements in set A, except those in set B.
 A ⊆ B -- subset; true if every element in set A is also in set B.
 A = B -- equality; true if every element of set A is in set B and vice versa.


As an option, show some other set operations.

(If A ⊆ B, but A ≠ B, then A is called a true or proper subset of B, written A ⊂ B or A ⊊ B.)

As another option, show how to modify a mutable set.



One might implement a set using an associative array (with set elements as array keys and some dummy value as the values).

One might also implement a set with a binary search tree, or with a hash table, or with an ordered array of binary bits (operated on with bit-wise binary operators).

The basic test, m ∈ S, is O(n) with a sequential list of elements, O(log n) with a balanced binary search tree, or (O(1) average-case, O(n) worst case) with a hash table.



See also

 Array
 Associative array: Creation, Iteration
 Collections
 Compound data type
 Doubly-linked list: Definition, Element definition, Element insertion, List Traversal, Element Removal
 Linked list
 Queue: Definition, Usage
 Set
 Singly-linked list: Element definition, Element insertion, List Traversal, Element Removal
 Stack


program Rosetta_Set;
 
{$mode objfpc}{$H+}
 
uses {$IFDEF UNIX} {$IFDEF UseCThreads}
  cthreads, {$ENDIF} {$ENDIF}
  Classes;
 
{$R *.res}
type
  CharSet = set of char;
 
var
  A, B, C, S: CharSet;
  M: char;
 
  function SetToString(const ASet: CharSet): string;
  var
    J: char;
  begin
    Result := '';
    // Test all chars
    for J in char do
      // If the char is in set, add to result
      if J in ASet then
        Result := Result + J + ', ';
    // Clear the result
    if Result > '' then
      Delete(Result, Length(Result) - 1, 2);
  end;
 
  procedure PrintSet(const ASet: CharSet; const ASetName: string;
  const ATitle: string = '');
  begin
    if ATitle > '' then
      WriteLn(ATitle);
    WriteLn(ASetName, ' = [', SetToString(ASet), ']', #10);
  end;
 
  procedure ShowEqual(const ASetA, ASetB: CharSet; const ASetNameA, ASetNameB: string);
  begin
    WriteLn(ASetNameA, ' = [', SetToString(ASetA), ']');
    WriteLn(ASetNameB, ' = [', SetToString(ASetB), ']');
    if ASetA = ASetB then
      WriteLn(ASetNameA, ' = ', ASetNameB)
    else
      WriteLn(ASetNameA, ' <> ', ASetNameB);
  end;
 
 
begin
  // Set Creation
  A := ['A', 'B', 'C', 'D', 'E', 'F'];
  B := ['E', 'F', 'G', 'H', 'I', 'J'];
  PrintSet(A, 'A', 'Set Creation');
  PrintSet(B, 'B');
 
  // Test m ∈ S -- "m is an element in set S"
  M := 'A';
  if M in A then
    WriteLn('"A" is in set A');
 
  // A ∪ B -- union; a set of all elements either in set A or in set B.
  S := A + B;
  PrintSet(S, 'S', 'S = A U B -- union; a set of all elements either in set A or in set B.');
 
  // A ∩ B -- intersection; a set of all elements in both set A and set B.
  S := A * B;
  PrintSet(S, 'S',
    'S = A ∩ B -- intersection; a set of all elements in both set A and set B.');
 
  // A \ B -- difference; a set of all elements in set A, except those in set B.
  S := A - B;
  PrintSet(S, 'S',
    'S = A \ B -- difference; a set of all elements in set A, except those in set B.');
 
  // A ⊆ B -- subset; true if every element in set A is also in set B.
  Writeln('A ⊆ B -- subset; true if every element in set A is also in set B.');
  if A <= B then
    WriteLn('A in B')
  else
    Writeln('A is not in B');
  Writeln;
  //A = B -- equality; true if every element of set A is in set B and vice-versa.
  Writeln('A = B -- equality; true if every element of set A is in set B and vice-versa.');
 
  ShowEqual(A, B, 'A', 'B');
  S := A * B;
  C := ['E', 'F'];
  ShowEqual(S, C, 'S', 'C');
 
  readln;
 
end.