
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


// version 1.0.6
 
fun main(args: Array<String>) {
   val fruits  = setOf("apple", "pear", "orange", "banana")
   println("fruits  : $fruits")
   val fruits2 = setOf("melon", "orange", "lemon", "gooseberry")
   println("fruits2 : $fruits2\n")
 
   println("fruits  contains 'banana'     : ${"banana" in fruits}")
   println("fruits2 contains 'elderberry' : ${"elderbury" in fruits2}\n")
 
   println("Union        : ${fruits.union(fruits2)}")
   println("Intersection : ${fruits.intersect(fruits2)}")
   println("Difference   : ${fruits.minus(fruits2)}\n")
 
   println("fruits2 is a subset of fruits : ${fruits.containsAll(fruits2)}\n")
   val fruits3 = fruits
   println("fruits3 : $fruits3\n")
   var areEqual = fruits.containsAll(fruits2) && fruits3.containsAll(fruits)
   println("fruits2 and fruits are equal  : $areEqual")
   areEqual = fruits.containsAll(fruits3) && fruits3.containsAll(fruits)
   println("fruits3 and fruits are equal  : $areEqual\n")
 
   val fruits4 = setOf("apple", "orange")
   println("fruits4 : $fruits4\n")
   var isProperSubset = fruits.containsAll(fruits3) && !fruits3.containsAll(fruits)
   println("fruits3 is a proper subset of fruits : $isProperSubset")
   isProperSubset = fruits.containsAll(fruits4) && !fruits4.containsAll(fruits)
   println("fruits4 is a proper subset of fruits : $isProperSubset\n")
 
   val fruits5 = mutableSetOf("cherry", "blueberry", "raspberry")
   println("fruits5 : $fruits5\n")
   fruits5 += "guava"
   println("fruits5 + 'guava'  : $fruits5")
   println("fruits5 - 'cherry' : ${fruits5 - "cherry"}")
}