
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


use AppleScript version "2.4" -- OS X 10.10 (Yosemite) or later
use framework "Foundation"
--use scripting additions
 
on doSetTask()
    -- 'set' at the beginnings of lines is an AppleScript command; nothing to do with sets.
 
    set output to {}
    set astid to AppleScript's text item delimiters
    set AppleScript's text item delimiters to ", "
 
    set S to current application's class "NSSet"'s setWithArray:({1, 2, 3, 6, 7, 8, 9, 0})
    set end of output to "Set S:  " & (S's allObjects() as list)
    set end of output to "\"aardvark\" is a member of S:  " & ((S's containsObject:("aardvark")) as boolean)
    set end of output to "3 is a member of S:  " & ((S's containsObject:(3)) as boolean)
 
 
    set A to S's |copy|() -- or: set A to current application's class "NSSet"'s setWithArray:({1, 2, 3, 6, 7, 8, 9, 0})
    set end of output to linefeed & "Set A:  " & (A's allObjects() as list)
    set B to current application's class "NSSet"'s setWithArray:({2, 2, 2, 3, 4, 5, 6, 7, 7, 7, 8})
    set end of output to "Set B:  " & (B's allObjects() as list)
 
    set union to A's setByAddingObjectsFromSet:(B)
    -- Or:
    -- set union to A's mutableCopy()
    -- tell union to unionSet:(B)
    set end of output to "Union of A and B:  " & (union's allObjects() as list)
 
    set intersection to A's mutableCopy()
    tell intersection to intersectSet:(B)
    set end of output to "Intersection of A and B:  " & (intersection's allObjects() as list)
 
    set difference to A's mutableCopy()
    tell difference to minusSet:(B)
    set end of output to "Difference of A and B:  " & (difference's allObjects() as list)
 
    set end of output to "A is a subset of B:  " & ((A's isSubsetOfSet:(B)) as boolean)
    set end of output to "A is a subset of S:  " & ((A's isSubsetOfSet:(S)) as boolean)
 
    set end of output to "A is equal to B:  " & ((A's isEqualToSet:(B)) as boolean)
    set end of output to "A is equal to S:  " & ((A's isEqualToSet:(S)) as boolean)
 
    set AppleScript's text item delimiters to linefeed
    set output to output as text
    set AppleScript's text item delimiters to astid
 
    return output
end doSetTask
 
doSetTask()