
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


function is_in( N as integer, S() as integer ) as boolean
    'test if the value N is in the set S
    for i as integer = 0 to ubound(S)
        if N=S(i) then return true
    next i
    return false
end function
 
sub add_to_set( N as integer, S() as integer )
    'adds the element N to the set S
    if is_in( N, S() ) then return
    dim as integer k = ubound(S)
    redim preserve S(0 to k+1)
    S(k+1)=N
end sub
 
sub setunion( S() as integer, T() as integer, U() as integer )
    'makes U() the union of the sets S and T
    dim as integer k = ubound(S)
    redim U(-1)
    for i as integer = 0 to k
        add_to_set( S(i), U() )
    next i
    k = ubound(T)
    for i as integer = 0 to k
        if not is_in( T(i), U() ) then
            add_to_set( T(i), U() )
        end if
    next i
end sub
 
sub setintersect( S() as integer, T() as integer, U() as integer )
    'makes U() the intersection of the sets S and T
    dim as integer k = ubound(S)
    redim U(-1)
    for i as integer = 0 to k
        if is_in(S(i), T()) then add_to_set( S(i), U() )
    next i
end sub
 
sub setsubtract( S() as integer, T() as integer, U() as integer )
    'makes U() the difference of the sets S and T
    dim as integer k = ubound(S)
    redim U(-1)
    for i as integer = 0 to k
        if not is_in(S(i), T()) then add_to_set( S(i), U() )
    next i
end sub
 
function is_subset( S() as integer, T() as integer ) as boolean
    for i as integer = 0 to ubound(S)
        if not is_in( S(i), T() ) then return false
    next i
    return true
end function
 
function is_equal( S() as integer, T() as integer ) as boolean
    if not is_subset( S(), T() ) then return false
    if not is_subset( T(), S() ) then return false
    return true
end function
 
function is_proper_subset( S() as integer, T() as integer ) as boolean
    if not is_subset( S(), T() ) then return false
    if is_equal( S(), T() ) then return false
    return true
end function
 
sub show_set( L() as integer )
    'display a set
    dim as integer num = ubound(L)
    if num=-1 then
        print "[]"
        return
    end if
    print "[";
    for i as integer = 0 to num-1
        print str(L(i))+", ";
    next i
    print str(L(num))+"]"
end sub
 
'sets are created by making an empty array
redim as integer S1(-1), S2(-1), S3(-1), S4(-1), S5(-1)
'and populated by adding elements one-by-one
add_to_set( 20, S1() )  :  add_to_set( 30, S1() )
add_to_set( 40, S1() )  :  add_to_set( 50, S1() )
add_to_set( 19, S2() )  :  add_to_set( 20, S2() )
add_to_set( 21, S2() )  :  add_to_set( 22, S2() )
add_to_set( 22, S3() )  :  add_to_set( 21, S3() )
add_to_set( 19, S3() )  :  add_to_set( 20, S3() )
add_to_set( 21, S3() ) ' attempt to add a number that's already in the set
add_to_set( 21, S4() )
print "S1    ", 
show_set S1()
print "S2    ", 
show_set S2()
print "S3    ", 
show_set S3()
print "S4    ", 
show_set S4()
print "S5    ", 
show_set S5()
print "----"
redim as integer S_U(-1)
setunion S1(), S2(), S_U()
print "S1 U S2    ",
show_set S_U()
redim as integer S_U(-1)
setintersect S1(), S2(), S_U()
print "S1 n S2    ",
show_set S_U()
redim as integer S_U(-1)
setsubtract S1(), S2(), S_U()
print "S1 \ S2    ",
show_set S_U()
redim as integer S_U(-1)
setsubtract S3(), S1(), S_U()
print "S3 \ S1    ",
show_set S_U()
print "S4 in S3? ", is_subset(S4(), S3())
print "S3 in S4? ", is_subset(S3(), S4())
print "S5 in S3? ", is_subset(S5(), S3())  'empty set is a subset of every set
print "S2 = S3?  ", is_equal(S2(), S3())
print "S4 proper subset of S3?   ", is_proper_subset( S4(), S3() )
print "S2 proper subset of S3?   ", is_proper_subset( S2(), S3() )