
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


 
A$ ="red hot chili peppers rule OK"
B$ ="lady in red"
 
print " New set, in space-separated form. Extra spaces and duplicates will be removed. "
input newSet$
 newSet$  =trim$(           newSet$)
 newSet$  =stripBigSpaces$( newSet$)
 newSet$  =removeDupes$(    newSet$)
print " Set stored as the string '"; newSet$; "'"
 
print
print " 'red'  is an element of '"; A$; "' is "; isAnElementOf$( "red",  A$)
print " 'blue' is an element of '"; A$; "' is "; isAnElementOf$( "blue",  A$)
print " 'red'  is an element of '"; B$; "' is "; isAnElementOf$( "red",  B$)
print
print " Union        of '"; A$; "' & '"; B$; "' is '"; unionOf$( A$, B$); "'."
print
print " Intersection of '"; A$; "' & '"; B$; "' is '"; intersectionOf$( A$, B$); "'."
print
print " Difference   of '"; A$; "' & '"; B$; "' is '"; differenceOf$( A$, B$); "'."
print
print " '"; A$; "' equals '";        A$; "' is "; equalSets$( A$, A$)
print " '"; A$; "' equals '";        B$; "' is "; equalSets$( A$, B$)
print
print  " '"; A$; "' is a subset of '"; B$; "' is "; isSubsetOf$( A$, B$)
print  " 'red peppers' is a subset of 'red hot chili peppers rule OK' is "; isSubsetOf$( "red peppers", "red hot chili peppers rule OK")
 
end
 
function removeDupes$( a$)
    numElements =countElements( a$)
    redim elArray$( numElements)         '   ie 4 elements are array entries 1 to 4 and 0 is spare =""
    for m =0 to numElements
        el$ =word$( a$, m, " ")
        elArray$( m) =el$
    next m
    sort elArray$(), 0, numElements
    b$           =""
    penultimate$ ="999"
    for jk =0 to numElements    '   do not use "" ( nuls) or elementsalready seen
        if elArray$( jk) ="" then [on]
        if elArray$( jk) <>penultimate$ then b$ =b$ +elArray$( jk) +" ": penultimate$ =elArray$( jk)
        [on]
    next jk
    b$ =trim$( b$)
    removeDupes$ =b$
end function
 
function stripBigSpaces$( a$)   '   copy byte by byte, but id=f a space had a preceding space, ignore it.
    lenA =len( a$)
    penul$ =""
    for i =1 to len( a$)
        c$ =mid$( a$, i, 1)
        if c$ <>" " then
            if penul$ <>" " then
                b$ =b$ +c$
            else
                b$ =b$ +" " +c$
            end if
        end if
        penul$ =c$
    next i
    stripBigSpaces$ =b$
end function
 
function countElements( a$) '   count elements repr'd by space-separated words in string rep'n.
    if isNul$( a$) ="True" then countElements =0: exit function
    i  =0
    do
        el$ =word$( a$, i +1, " ")
        i =i +1
    loop until el$ =""
    countElements =i -1
end function
 
function isNul$( a$)    '   a nul set implies its string rep'n is length zero.
    if a$ ="" then isNul$ ="True" else isNul$ ="False"
end function
 
function isAnElementOf$( a$, b$)    '   check element a$ exists in set b$.
    isAnElementOf$ ="False"
    i  =0
    do
        el$ =word$( b$, i +1, " ")
        if a$ =el$ then isAnElementOf$ ="True"
        i =i +1
    loop until el$ =""
end function
 
function unionOf$( a$, b$)
    i  =1
    o$ =a$
    do
        w$ =word$( b$, i, " ")
        if w$ ="" then exit do
        if isAnElementOf$( w$, a$) ="False" then o$ =o$ +" " +w$
        i =i +1
    loop until w$ =""
    unionOf$ =o$
end function
 
function intersectionOf$( a$, b$)
    i  =1
    o$ =""
    do
        el$ =word$( a$, i, " ")
        if el$ ="" then exit do
        if ( isAnElementOf$( el$, b$) ="True") and ( o$ ="")  then o$ =el$ 
        if ( isAnElementOf$( el$, b$) ="True") and ( o$ <>el$) then o$ =o$ +" " +el$ 
        i =i +1
    loop until el$ =""
    intersectionOf$ =o$
end function
 
function equalSets$( a$, b$)
    if len( a$) <>len( b$) then equalSets$ ="False": exit function
    i =1
    do
        el$ =word$( a$, i, " ")
        if isAnElementOf$( el$, b$) ="False" then equalSets$ ="False": exit function
        i =i +1
    loop until w$ =""
    equalSets$ ="True"
end function
 
function differenceOf$( a$, b$)
    i  =1
    o$ =""
    do
        el$ =word$( a$, i, " ")
        if el$ ="" then exit do
        if ( isAnElementOf$( el$, b$) ="False") and ( o$ ="")   then o$ =el$ 
        if ( isAnElementOf$( el$, b$) ="False") and ( o$ <>el$) then o$ =o$ +" " +el$ 
        i =i +1
    loop until el$ =""
    differenceOf$ =o$
end function
 
function isSubsetOf$( a$, b$)
    isSubsetOf$ ="True"
    i  =1
    do
        el$ =word$( a$, i, " ")
        if el$ ="" then exit do
        if ( isAnElementOf$( el$, b$) ="False") then isSubsetOf$ ="False": exit function
        i =i +1
    loop until el$ =""
end function
 
 