Construct & Apply Sets as an ADT

Overview: Set Properties & Operations

• Unordered: no notion of first or last element.
• Unique: duplicates are ignored.
• Membership: contains(x) returns true if x is in the set.
• Union: all elements in either set.
• Intersection: only elements common to both.
• Difference: elements in one set but not the other.
• Subset/Superset: tests for inclusion of all elements.

Deep Dive: Pseudocode

Add & Remove Elements

In an online shopping cart, you add a product only if it isn’t already in your cart, and remove it when you decide not to buy it. This ensures the cart contains each item at most once and reflects the user’s current selections.

// Pseudocode
function add(set, x):
    if not contains(set, x):
        append x to set    // add item to cart

function remove(set, x):
    if contains(set, x):
        delete x from set  // remove item from cart
    

Membership Test

A spam filter maintains a set of blocked email addresses. Each incoming email’s sender is checked against this set to decide whether to accept or reject the message.

// Pseudocode
function contains(set, x):
    for each element e in set:
        if e == x:
            return true      // sender is blocked
    return false             // sender allowed
    

Union, Intersection & Difference

On a social network, you might compute:
• Union: all friends of User A or User B (combined network).
• Intersection: mutual friends both users share.
• Difference: people A follows who don’t follow A back.

// Pseudocode
function union(A, B):
    result = copy of A
    for each x in B:
        add(result, x)      // combine friend lists
    return result

function intersection(A, B):
    result = empty set
    for each x in A:
        if contains(B, x):
            add(result, x)  // mutual friends
    return result

function difference(A, B):
    result = empty set
    for each x in A:
        if not contains(B, x):
            add(result, x)  // one-way follows
    return result
    

Subset & Superset

In an academic system, each course has prerequisite courses. To enroll in Course B, a student’s set of completed courses must be a superset of Course B’s prerequisites.

// Pseudocode
function isSubset(A, B):
    for each x in A:
        if not contains(B, x):
            return false   // missing a prerequisite
    return true            // all prerequisites met

function isSuperset(A, B):
    return isSubset(B, A)  // A contains everything in B
    

Scenarios & Applications

Unique Usernames

A registration system might use a set to ensure each username is unique. Before adding a new user, contains(username) prevents duplicates, maintaining data integrity.

Tag Collections

In a blogging platform, posts have tags stored in a set. union merges tags across related posts, intersection finds common tags, and difference isolates unique tags between topics.

Permission Management

User roles have permission sets. Testing isSubset(userPerms, requiredPerms) quickly verifies if a user has all needed rights.

Feature Flags

A feature-flag service stores enabled flags in a set. contains(flag) routes users to new features without complex database queries.

Example: Set ADT Implementation

A simple implementation of a Set Abstract Data Type (ADT) that stores unique items, backed by a list or dynamic array. This example provides the implementation in both Python and Java.

• Python
• Java

# A simple Set ADT storing unique items in a list
class MySet:
    def __init__(self):
        self._items = []  # internal storage for elements

    def contains(self, x):
        """Check membership in O(n) time."""
        return x in self._items

    def add(self, x):
        """Add x only if not already present to enforce uniqueness."""
        if not self.contains(x):
            self._items.append(x)

    def remove(self, x):
        """Remove x if present; no error otherwise."""
        if self.contains(x):
            self._items.remove(x)

    def union(self, other):
        """
        Return a new set containing all unique elements
        from this set and another.
        """
        result = MySet()
        # add all from self, then from other
        for x in self._items + other._items:
            result.add(x)
        return result

    def intersection(self, other):
        """Return elements common to both sets."""
        result = MySet()
        for x in self._items:
            if other.contains(x):
                result.add(x)
        return result

    def difference(self, other):
        """Return elements in this set but not in the other."""
        result = MySet()
        for x in self._items:
            if not other.contains(x):
                result.add(x)
        return result

    def is_subset(self, other):
        """Check whether all elements of this set appear in other."""
        for x in self._items:
            if not other.contains(x):
                return False
        return True

    def __str__(self):
        """Print representation in set notation."""
        return "{" + ", ".join(map(str, self._items)) + "}"

# Usage example
if __name__ == "__main__":
    A = MySet(); B = MySet()
    for v in [1,2,3]:
        A.add(v)
    for v in [2,3,4]:
        B.add(v)
    print("A:", A)                      # {1, 2, 3}
    print("B:", B)                      # {2, 3, 4}
    print("A ∪ B:", A.union(B))        # {1, 2, 3, 4}
    print("A ∩ B:", A.intersection(B))  # {2, 3}
    print("A - B:", A.difference(B))    # {1}
    print("A ⊆ B?", A.is_subset(B))     # False
                

import java.util.ArrayList;

/**
 * A simple generic Set ADT backed by a dynamic array.
 * Ensures uniqueness of elements.
 */
public class MySet<T> {
    // Internal list to hold unique items
    private ArrayList<T> items = new ArrayList<>();

    /**
     * Check if x is in the set.
     */
    public boolean contains(T x) {
        return items.contains(x);
    }

    /**
     * Add x if not already present.
     */
    public void add(T x) {
        if (!contains(x)) {
            items.add(x);
        }
    }

    /**
     * Remove x if present; does nothing if absent.
     */
    public void remove(T x) {
        items.remove(x);
    }

    /**
     * Return a new set that is the union of this and another set.
     */
    public MySet<T> union(MySet<T> other) {
        MySet<T> result = new MySet<>();
        // add all items from this set
        for (T x : this.items) result.add(x);
        // add all items from the other set
        for (T x : other.items) result.add(x);
        return result;
    }

    /**
     * Return a new set containing only common elements.
     */
    public MySet<T> intersection(MySet<T> other) {
        MySet<T> result = new MySet<>();
        for (T x : this.items) {
            if (other.contains(x)) result.add(x);
        }
        return result;
    }

    /**
     * Return a new set containing elements in this set but not in other.
     */
    public MySet<T> difference(MySet<T> other) {
        MySet<T> result = new MySet<>();
        for (T x : this.items) {
            if (!other.contains(x)) result.add(x);
        }
        return result;
    }

    /**
     * Check if this set is a subset of another.
     */
    public boolean isSubsetOf(MySet<T> other) {
        for (T x : this.items) {
            if (!other.contains(x)) return false;
        }
        return true;
    }

    @Override
    public String toString() {
        // default ArrayList format suffices for display
        return items.toString();
    }

    // Demonstration
    public static void main(String[] args) {
        MySet<Integer> A = new MySet<>();
        MySet<Integer> B = new MySet<>();
        for (int v : new int[]{1,2,3}) A.add(v);
        for (int v : new int[]{2,3,4}) B.add(v);
        System.out.println("A: " + A);                  // [1, 2, 3]
        System.out.println("B: " + B);                  // [2, 3, 4]
        System.out.println("A ∪ B: " + A.union(B));        // [1, 2, 3, 4]
        System.out.println("A ∩ B: " + A.intersection(B)); // [2, 3]
        System.out.println("A - B: " + A.difference(B));   // [1]
        System.out.println("A ⊆ B? " + A.isSubsetOf(B));   // false
    }
}