
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


with ada.containers.ordered_sets, ada.text_io;
use ada.text_io;
 
procedure set_demo is
	package cs is new ada.containers.ordered_sets (character); use cs;
 
	function "+" (s : string) return set is
	(if s = "" then empty_set else Union(+ s(s'first..s'last - 1), To_Set (s(s'last))));
 
	function "-" (s : Set) return string is
	(if s = empty_set then "" else - (s - To_Set (s.last_element)) & s.last_element);
	s1, s2 : set;
begin
	loop
		put ("s1= ");
		s1 := + get_line;		
		exit when s1 = +"Quit!";
		put ("s2= ");
		s2 := + get_line;
		Put_Line("Sets [" & (-s1) & "], [" & (-s2) & "] of size"
                & S1.Length'img & " and" & s2.Length'img & ".");
  		Put_Line("Intersection:   [" & (-(Intersection(S1, S2))) & "],");
  		Put_Line("Union:          [" & (-(Union(s1, s2)))        & "],");
  		Put_Line("Difference:     [" & (-(Difference(s1, s2)))   & "],");
  		Put_Line("Symmetric Diff: [" & (-(s1 xor s2)) & "],");
  		Put_Line("Subset: "  & Boolean'Image(s1.Is_Subset(s2))
              & ", Equal: " & Boolean'Image(s1 = s2) & ".");
	end loop;
end set_demo; 
 