
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 "NSLog.incl"
 
local fn DoIt
  // create
  CFSetRef s1 = fn SetWithArray( @[@"a",@"b",@"c",@"d",@"e"] )
  CFSetRef s2 = fn SetWithArray( @[@"b",@"c",@"d",@"e",@"f",@"h"] )
  CFSetRef s3 = fn SetWithArray( @[@"b",@"c",@"d"] )
  CFSetRef s4 = fn SetWithArray( @[@"b",@"c",@"d"] )
  NSLog(@"s1: %@",s1)
  NSLog(@"s2: %@",s2)
  NSLog(@"s3: %@",s3)
  NSLog(@"s4: %@\n",s4)
 
  // membership
  NSLog(@"\"b\" in s1: %d", fn SetContainsObject( s1, @"b" ))
  NSLog(@"\"f\" in s1: %d\n", fn SetContainsObject( s1, @"f" ))
 
  // union
  CFMutableSetRef s12 = fn MutableSetWithSet( s1 )
  MutableSetUnionSet( s12, s2 )
  NSLog(@"s1 union s2: %@\n", s12)
 
  // intersection
  CFMutableSetRef s1i2 = fn MutableSetWithSet( s1 )
  MutableSetIntersectSet( s1i2, s2 )
  NSLog(@"s1 intersect s2: %@\n", s1i2)
 
  // difference
  CFMutableSetRef s1d2 = fn MutableSetWithSet( s1 )
  MutableSetMinusSet( s1d2, s2 )
  NSLog(@"s1 - s2: %@\n", s1d2)
 
  // subsetof
  NSLog(@"s3 subset of s1: %d\n", fn SetIsSubsetOfSet( s3, s1 ))
 
  // equality
  NSLog(@"s3 == s4: %d\n", fn SetIsEqual( s3, s4 ))
 
  // cardinality
  NSLog(@"size of s1: %lu\n", fn SetCount(s1))
 
  // has intersection (not disjoint)
  NSLog(@"s1 intersects s2: %d\n", fn SetIntersectsSet( s1, s2 ))
 
  // adding and removing elements from mutable set
  CFMutableSetRef s1mut = fn MutableSetWithSet( s1 )
  MutableSetAddObject( s1mut, @"g" )
  NSLog(@"s1mut after adding \"g\": %@\n", s1mut)
  MutableSetAddObject( s1mut, @"b" )
  NSLog(@"s1mut after adding \"b\" again: %@\n", s1mut)
  MutableSetRemoveObject( s1mut, @"c" )
  NSLog(@"s1mut after removing \"c\": %@\n", s1mut)	
end fn
 
fn DoIt
 
HandleEvents