
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


  [ [] $ "" rot
    sort$ witheach
      [ tuck != if
        [ dup dip
            [ nested join ] ] ]
    drop ]                             is -duplicates  (   { --> {   )
 
  [ [] $ "" rot
    sort$ witheach
      [ tuck = if
        [ nested join
          $ "" ] ]
    drop -duplicates ]                 is duplicates   (   { --> {   )
 
 
  [ [] $ "" rot
    sort$ witheach
      [ tuck != iff
          [ dup dip [ nested join ] ]
        else
          [ dip [ -1 pluck ]
            over != if
              [ nested join $ "" ] ] ]
    drop ]                             is --duplicates (   { --> {   )
 
  [ [] swap
    [ trim
      dup $ "" = if
        [ $ '"set{" without "}set"'
          message put bail ]
      nextword
      dup $ "}set" != while
      nested rot join swap
      again ]
    drop swap
    -duplicates
    ' [ ' ] swap nested join
    swap dip [ nested join ] ]     builds set{         ( [ $ --> [ $ )
 
  [ -duplicates
    say "{ "
    witheach [ echo$ sp ]
    say "}" ]                          is echoset      (   { --> {   )
 
  [ join duplicates ]                  is intersection ( { { --> {   )
 
  [ join -duplicates ]                 is union        ( { { --> {   )
 
  [ join --duplicates ]                is symmdiff     ( { { --> {   )
 
  [ over intersection symmdiff ]       is difference   ( { { --> {   )
 
  [ over intersection = ]              is subset       ( { { --> b   )
 
  [ dip nested subset ]                is element      ( $ { --> b   )
 
  [ 2dup = iff
      [ 2drop false ]
    else subset ]                      is propersubset ( { { --> b   )
 
( ------------------------------ demo ------------------------------ )
 
set{ apple peach pear melon
     apricot banana orange }set        is fruits       (     --> {   )
 
set{ red orange green blue
     purple apricot peach }set         is colours      (     --> {   )
 
fruits  dup echoset say " are fruits" cr
 
colours dup echoset say " are colours" cr
 
2dup intersection echoset say " are both fruits and colours" cr
 
2dup union echoset say " are fruits or colours" cr
 
2dup symmdiff echoset say " are fruits or colours but not both" cr
 
difference echoset say " are fruits that are not colours" cr
 
set{ red green blue }set dup echoset say " are"
colours subset not if [ say " not" ] say " all colours"  cr
 
say "fruits and colours are" fruits colours = not if [ say " not" ]
say " exactly the same" cr
 
$ "orange" dup echo$ say " is"
fruits element not if [ say " not" ] say " a fruit" cr
 
set{ orange }set dup echoset say " is"
fruits propersubset dup if [ say " not" ] say " the only fruit"
                    not if [ say " or not a fruit" ] cr