
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 FMS-SI.f
include FMS-SILib.f
 
: union {: a b -- c :}
  begin
    b each:
  while dup
    a indexOf: if 2drop else a add: then
  repeat b <free a dup sort: ; ok
 
i{ 2 5 4 3 } i{ 5 6 7 } union p: i{ 2 3 4 5 6 7 } ok
 
 
: free2 ( a b -- ) <free <free ; 
: intersect {: a b | c -- c :}
  heap> 1-array2 to c 
  begin
    b each:
  while dup
    a indexOf: if drop c add: else drop then
  repeat a b free2 c dup sort: ; 
 
i{ 2 5 4 3 } i{ 5 6 7 } intersect p: i{ 5 } ok
 
 
: diff {: a b | c -- c :}
  heap> 1-array2 to c 
  begin
    a each:
  while dup
    b indexOf: if 2drop else c add: then
  repeat a b free2 c dup sort: ; 
 
i{ 2 5 4 3 } i{ 5 6 7 } diff p: i{ 2 3 4 } ok
 
: subset {: a b -- flag :}
  begin
    a each:
  while 
    b indexOf: if drop else false exit then
  repeat a b free2 true ; 
 
i{ 2 5 4 3 } i{ 5 6 7 } subset . 0 ok
i{ 5 6 } i{ 5 6 7 } subset .  -1 ok
 
 
: set= {: a b -- flag :}
  a size: b size: <> if a b free2 false exit then
  a sort: b sort:
  begin
    a each: drop b each: 
  while 
    <> if a b free2 false exit then
  repeat a b free2 true ; 
 
i{ 5 6 } i{ 5 6 7 } set= .  0 ok
i{ 6 5 7 } i{ 5 6 7 } set= .  -1 ok
 