
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


 
# For ad-hoc set features, it sometimes makes sense to use hashes directly,
# rather than abstract to this level, but I'm showing a somewhat heavy
# solution to show off CoffeeScript class syntax. 
class Set    
  constructor: (elems...) ->
    @hash = {}
    for elem in elems
      @hash[elem] = true
 
  add: (elem) ->
    @hash[elem] = true
 
  remove: (elem) ->
    delete @hash[elem]
 
  has: (elem) ->
    @hash[elem]?
 
  union: (set2) ->
    set = new Set()
    for elem of @hash
      set.add elem
    for elem in set2.to_array()
      set.add elem
    set
 
  intersection: (set2) ->
    set = new Set()
    for elem of @hash
      set.add elem if set2.has elem
    set
 
  minus: (set2) ->
    set = new Set()
    for elem of @hash
      set.add elem if !set2.has elem
    set
 
  is_subset_of: (set2) ->
    for elem of @hash
      return false if !set2.has elem
    true
 
  equals: (set2) ->
    this.is_subset_of(set2) and set2.is_subset_of this
 
  to_array: ->
    (elem for elem of @hash)
 
  each: (f) ->
    for elem of @hash
      f(elem)
 
  to_string: ->
    @to_array()
 
run_tests = ->
  set1 = new Set("apple", "banana") # creation
  console.log set1.has "apple" # true (membership)
  console.log set1.has "worms" # false (membership)
 
  set2 = new Set("banana", "carrots")
  console.log set1.union(set2).to_string() # [ 'apple', 'banana', 'carrots' ] (union)
  console.log set1.intersection(set2).to_string() # [ 'banana' ] (intersection)
  console.log set1.minus(set2).to_string() # [ 'apple' ] (difference)
 
  set3 = new Set("apple")
  console.log set3.is_subset_of set1 # true
  console.log set3.is_subset_of set2 # false
 
  set4 = new Set("apple", "banana")
  console.log set4.equals set1 # true
  console.log set4.equals set2 # false
 
  set5 = new Set("foo")
  set5.add "bar" # add
  console.log set5.to_string() # [ 'foo', 'bar' ]
  set5.remove "bar" # remove
  console.log set5.to_string() # [ 'foo' ]
 
  # iteration, prints apple then banana (order not guaranteed)
  set1.each (elem) ->
    console.log elem
 
run_tests()
 