
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


class MySet(*set) {
 
    method init {
        var elems = set
        set = Hash()
        elems.each { |e| self += e }
    }
 
    method +(elem) {
        set{elem} = elem
        self
    }
 
    method del(elem) {
        set.delete(elem)
    }
 
    method has(elem) {
        set.has_key(elem)
    }
 
    method ∪(MySet that) {
        MySet(set.values..., that.values...)
    }
 
    method ∩(MySet that) {
        MySet(set.keys.grep{ |k| k ∈ that } \
                    .map { |k| set{k} }...)
    }
 
    method ∖(MySet that) {
        MySet(set.keys.grep{|k| !(k ∈ that) } \
                    .map {|k| set{k} }...)
    }
 
    method ^(MySet that) {
        var d = ((self ∖ that) ∪ (that ∖ self))
        MySet(d.values...)
    }
 
    method count { set.len }
 
    method ≡(MySet that) {
        (self ∖ that -> count.is_zero) && (that ∖ self -> count.is_zero)
    }
 
    method values { set.values }
 
    method ⊆(MySet that) {
        that.set.keys.each { |k|
            k ∈ self || return false
        }
        return true
    }
 
    method to_s {
        "Set{" + set.values.map{|e| "#{e}"}.sort.join(', ') + "}"
    }
}
 
class Object {
    method ∈(MySet set) {
        set.has(self)
    }
}