Module hash_set

A set structure based on this library’s HashMap

About

This structure provides common binary set operations (as self and other), mostly as an excuse to explore implementing custom iterators.

• Union: Returns an iterator over references to all elements that appear in either self or other as a set-theoretic union.
• Extend: Mutates self to contain all unique elements in both self and other. This is a mutating version of union().
• Intersection: Returns an iterator over references to elements that appear in both self and other as a set-theoretic intersection.
• Retain All: Mutates self such that self only keeps elements that are also in other. This function could also appropriately be called “intersect”, but that was too close to the non-mutating version of this function called “intersection”.
• Difference: Returns an iterator over references to elements that are present in self but not in other as a set-theoretic asymmetric difference or relative complement. This operation is asymmetric: interchanging self and other generally produces different results.
• Unique: Returns an iterator over references to elements that are present in exactly one of the two sets as a set-theoretic symmetric difference. This operation is symmetric: interchanging self and other yields the same result.

Design

The structure is based on this library’s (open-addressing) hash map. Each entry is stored as (T, ()), and because of the underlying implementation, T must be Hash, PartialEq, and Eq.

Example

use dsa_rust::associative::hash_set::HashSet;

    //Creates a couple new hash sets
    let mut set1 = HashSet::<u8>::new();
    // [0, 1, 2, 3]
    for n in 0..=3 {
        set1.put(n); 
    }

    let mut set2 = HashSet::<u8>::new();
    // [2, 3, 4, 5]
    for n in 2..=5 {
        set2.put(n); 
    }

    // Creates a list of all elements in both self and other
    let mut union: Vec<u8> = Vec::new();
    for e in set1.union(&set2) {
        union.push(*e); 
    }
    assert_eq!(union.len(), 6);
    assert!(union.contains(&0));
    assert!(union.contains(&1));
    assert!(union.contains(&2));
    assert!(union.contains(&3));
    assert!(union.contains(&4));
    assert!(union.contains(&5));

    // Creates a list of elements only present in both sets
    let mut intersection: Vec<u8> = Vec::new();
    for e in set1.intersection(&set2) {
        intersection.push(*e); 
    }
    assert_eq!(intersection.len(), 2);
    assert!(intersection.contains(&2));
    assert!(intersection.contains(&3));

    // Creates a list of elements from self not present in other
    let mut difference: Vec<u8> = Vec::new();
    for e in set1.difference(&set2) {
        difference.push(*e); 
    }
    assert_eq!(difference.len(), 2);
    assert!(difference.contains(&0));
    assert!(difference.contains(&1));

    // Proves that difference() is asymmetric 
    let mut difference: Vec<u8> = Vec::new();
    for e in set2.difference(&set1) {
        difference.push(*e); 
    }
    assert_eq!(difference.len(), 2);
    assert!(difference.contains(&4));
    assert!(difference.contains(&5));

    // Creates a list of elements present in either the first or 
    // second one set, but not both
    let mut unique: Vec<u8> = Vec::new();
    for e in set1.unique(&set2) {
        unique.push(*e); 
    }
    assert_eq!(unique.len(), 4);
    assert!(unique.contains(&0));
    assert!(unique.contains(&1));
    assert!(unique.contains(&4));
    assert!(unique.contains(&5));

    // Illustrates that unique() is symmetric
    let mut unique: Vec<u8> = Vec::new();
    for e in set2.unique(&set1) {
        unique.push(*e); 
    }
    assert_eq!(unique.len(), 4);
    assert!(unique.contains(&0));
    assert!(unique.contains(&1));
    assert!(unique.contains(&4));
    assert!(unique.contains(&5));

Structs

Difference

HashSet

Intersection

Union

Unique