
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


$ include "seed7_05.s7i";
 
const type: charSet is set of char;
enable_output(charSet);
 
const proc: main is func
  local
    const charSet: A is {'A', 'B', 'C', 'D', 'E', 'F'};
    var charSet: B is charSet.value;
    var char: m is 'A';
  begin
    B := {'E', 'F', 'G', 'H', 'I', 'K'};
    incl(B, 'J');        # Add 'J' to set B
    excl(B, 'K');        # Remove 'K' from set B
    writeln("A: " <& A);
    writeln("B: " <& B);
    writeln("m: " <& m);
    writeln("m in A -- m is an element in A: " <& m in A);
    writeln("A | B  -- union:                " <& A | B);
    writeln("A & B  -- intersection:         " <& A & B);
    writeln("A - B  -- difference:           " <& A - B);
    writeln("A >< B -- symmetric difference: " <& A >< B);
    writeln("A <= A -- subset:               " <& A <= A);
    writeln("A < A  -- proper subset:        " <& A < A);
    writeln("A = B  -- equality:             " <& A = B);
  end func;