Struct UnaryRelation 

pub struct UnaryRelation<T: Ord> { /* private fields */ }

Finite unary relation type. A finite unary relation.

In G1 this is also the canonical set type used to define carriers, domains, ranges, and images of binary relations.

The starter implementation uses BTreeSet so iteration order is deterministic.

Examples

use relmath::{FiniteRelation, UnaryRelation};

let mut xs = UnaryRelation::new();
assert!(xs.is_empty());

xs.insert(3);
xs.insert(1);
xs.insert(2);
xs.insert(2);

let ys = UnaryRelation::singleton(3);
let zs = UnaryRelation::from_values([2, 3, 4]);

assert!(xs.contains(&1));
assert_eq!(xs.iter().copied().collect::<Vec<_>>(), vec![1, 2, 3]);
assert_eq!(xs.union(&ys).to_vec(), vec![1, 2, 3]);
assert_eq!(xs.intersection(&zs).to_vec(), vec![2, 3]);
assert_eq!(xs.difference(&zs).to_vec(), vec![1]);
assert!(ys.is_subset(&xs));

Implementations

impl<T: Ord> UnaryRelation<T>

pub fn new() -> Self

Creates an empty unary relation.

pub fn from_values<I>(values: I) -> Self

where I: IntoIterator<Item = T>,

Creates a unary relation from the provided values.

Duplicate values are coalesced into a single stored element.

Examples found in repository

examples/workflow.rs (line 13)

fn main() {
    let step = BinaryRelation::from_pairs([
        ("Draft", "Review"),
        ("Review", "Approved"),
        ("Review", "Rejected"),
    ]);

    let states =
        UnaryRelation::from_values(["Draft", "Review", "Approved", "Rejected", "Archived"]);
    let reachable = step.reflexive_transitive_closure(&states);
    let draft = UnaryRelation::singleton("Draft");

    assert!(reachable.contains(&"Archived", &"Archived"));
    assert!(reachable.contains(&"Draft", &"Approved"));

    println!(
        "reachable from Draft: {:?}",
        reachable.image(&draft).to_vec()
    );
}

examples/family.rs (line 14)

fn main() {
    let parent = BinaryRelation::from_pairs([
        ("Ada", "Bob"),
        ("Ada", "Cara"),
        ("Bob", "Dana"),
        ("Cara", "Eli"),
        ("Dana", "Finn"),
    ]);

    let people = UnaryRelation::from_values(["Ada", "Bob", "Cara", "Dana", "Eli", "Finn"]);
    let grandparent = parent.compose(&parent);
    let ancestor = parent.reflexive_transitive_closure(&people);

    let ada = UnaryRelation::singleton("Ada");
    let reachable_from_ada = ancestor.image(&ada);

    assert!(grandparent.contains(&"Ada", &"Dana"));
    assert!(grandparent.contains(&"Ada", &"Eli"));
    assert!(reachable_from_ada.contains(&"Finn"));

    println!("grandparent pairs: {:?}", grandparent.to_vec());
    println!(
        "people reachable from Ada: {:?}",
        reachable_from_ada.to_vec()
    );
}

pub fn singleton(value: T) -> Self

Creates a unary relation containing exactly one value.

Examples found in repository

examples/workflow.rs (line 15)

fn main() {
    let step = BinaryRelation::from_pairs([
        ("Draft", "Review"),
        ("Review", "Approved"),
        ("Review", "Rejected"),
    ]);

    let states =
        UnaryRelation::from_values(["Draft", "Review", "Approved", "Rejected", "Archived"]);
    let reachable = step.reflexive_transitive_closure(&states);
    let draft = UnaryRelation::singleton("Draft");

    assert!(reachable.contains(&"Archived", &"Archived"));
    assert!(reachable.contains(&"Draft", &"Approved"));

    println!(
        "reachable from Draft: {:?}",
        reachable.image(&draft).to_vec()
    );
}

examples/family.rs (line 18)

fn main() {
    let parent = BinaryRelation::from_pairs([
        ("Ada", "Bob"),
        ("Ada", "Cara"),
        ("Bob", "Dana"),
        ("Cara", "Eli"),
        ("Dana", "Finn"),
    ]);

    let people = UnaryRelation::from_values(["Ada", "Bob", "Cara", "Dana", "Eli", "Finn"]);
    let grandparent = parent.compose(&parent);
    let ancestor = parent.reflexive_transitive_closure(&people);

    let ada = UnaryRelation::singleton("Ada");
    let reachable_from_ada = ancestor.image(&ada);

    assert!(grandparent.contains(&"Ada", &"Dana"));
    assert!(grandparent.contains(&"Ada", &"Eli"));
    assert!(reachable_from_ada.contains(&"Finn"));

    println!("grandparent pairs: {:?}", grandparent.to_vec());
    println!(
        "people reachable from Ada: {:?}",
        reachable_from_ada.to_vec()
    );
}

examples/access_control.rs (line 23)

fn main() {
    let user_role = BinaryRelation::from_pairs([
        ("ann", "admin"),
        ("bob", "analyst"),
        ("bob", "reviewer"),
        ("cara", "guest"),
    ]);

    let role_permission = BinaryRelation::from_pairs([
        ("admin", "read"),
        ("admin", "write"),
        ("admin", "deploy"),
        ("analyst", "read"),
        ("reviewer", "approve"),
        ("guest", "read"),
    ]);

    let effective_permission = user_role.compose(&role_permission);
    let bob = UnaryRelation::singleton("bob");
    let bob_permissions = effective_permission.image(&bob);

    assert!(effective_permission.contains(&"ann", &"deploy"));
    assert!(bob_permissions.contains(&"approve"));
    assert!(bob_permissions.contains(&"read"));

    println!(
        "effective permissions for bob: {:?}",
        bob_permissions.to_vec()
    );
}

pub fn insert(&mut self, value: T) -> bool

Inserts a value into the unary relation.

Returns true when the value was not already present.

pub fn contains(&self, value: &T) -> bool

Returns true when the unary relation contains the given value.

Examples found in repository

examples/family.rs (line 23)

fn main() {
    let parent = BinaryRelation::from_pairs([
        ("Ada", "Bob"),
        ("Ada", "Cara"),
        ("Bob", "Dana"),
        ("Cara", "Eli"),
        ("Dana", "Finn"),
    ]);

    let people = UnaryRelation::from_values(["Ada", "Bob", "Cara", "Dana", "Eli", "Finn"]);
    let grandparent = parent.compose(&parent);
    let ancestor = parent.reflexive_transitive_closure(&people);

    let ada = UnaryRelation::singleton("Ada");
    let reachable_from_ada = ancestor.image(&ada);

    assert!(grandparent.contains(&"Ada", &"Dana"));
    assert!(grandparent.contains(&"Ada", &"Eli"));
    assert!(reachable_from_ada.contains(&"Finn"));

    println!("grandparent pairs: {:?}", grandparent.to_vec());
    println!(
        "people reachable from Ada: {:?}",
        reachable_from_ada.to_vec()
    );
}

examples/access_control.rs (line 27)

fn main() {
    let user_role = BinaryRelation::from_pairs([
        ("ann", "admin"),
        ("bob", "analyst"),
        ("bob", "reviewer"),
        ("cara", "guest"),
    ]);

    let role_permission = BinaryRelation::from_pairs([
        ("admin", "read"),
        ("admin", "write"),
        ("admin", "deploy"),
        ("analyst", "read"),
        ("reviewer", "approve"),
        ("guest", "read"),
    ]);

    let effective_permission = user_role.compose(&role_permission);
    let bob = UnaryRelation::singleton("bob");
    let bob_permissions = effective_permission.image(&bob);

    assert!(effective_permission.contains(&"ann", &"deploy"));
    assert!(bob_permissions.contains(&"approve"));
    assert!(bob_permissions.contains(&"read"));

    println!(
        "effective permissions for bob: {:?}",
        bob_permissions.to_vec()
    );
}

pub fn iter(&self) -> impl Iterator<Item = &T>

Returns an iterator over the values in deterministic order.

Iteration order follows T: Ord.

pub fn union(&self, other: &Self) -> Self

where T: Clone,

Returns the union of self and other.

pub fn intersection(&self, other: &Self) -> Self

where T: Clone,

Returns the intersection of self and other.

pub fn difference(&self, other: &Self) -> Self

where T: Clone,

Returns the set difference self \ other.

pub fn is_subset(&self, other: &Self) -> bool

Returns true when every element of self also appears in other.

pub fn to_vec(&self) -> Vec<T>

where T: Clone,

Converts the unary relation into a sorted vector.

Examples found in repository

examples/workflow.rs (line 22)

fn main() {
    let step = BinaryRelation::from_pairs([
        ("Draft", "Review"),
        ("Review", "Approved"),
        ("Review", "Rejected"),
    ]);

    let states =
        UnaryRelation::from_values(["Draft", "Review", "Approved", "Rejected", "Archived"]);
    let reachable = step.reflexive_transitive_closure(&states);
    let draft = UnaryRelation::singleton("Draft");

    assert!(reachable.contains(&"Archived", &"Archived"));
    assert!(reachable.contains(&"Draft", &"Approved"));

    println!(
        "reachable from Draft: {:?}",
        reachable.image(&draft).to_vec()
    );
}

examples/family.rs (line 28)

fn main() {
    let parent = BinaryRelation::from_pairs([
        ("Ada", "Bob"),
        ("Ada", "Cara"),
        ("Bob", "Dana"),
        ("Cara", "Eli"),
        ("Dana", "Finn"),
    ]);

    let people = UnaryRelation::from_values(["Ada", "Bob", "Cara", "Dana", "Eli", "Finn"]);
    let grandparent = parent.compose(&parent);
    let ancestor = parent.reflexive_transitive_closure(&people);

    let ada = UnaryRelation::singleton("Ada");
    let reachable_from_ada = ancestor.image(&ada);

    assert!(grandparent.contains(&"Ada", &"Dana"));
    assert!(grandparent.contains(&"Ada", &"Eli"));
    assert!(reachable_from_ada.contains(&"Finn"));

    println!("grandparent pairs: {:?}", grandparent.to_vec());
    println!(
        "people reachable from Ada: {:?}",
        reachable_from_ada.to_vec()
    );
}

examples/access_control.rs (line 32)

fn main() {
    let user_role = BinaryRelation::from_pairs([
        ("ann", "admin"),
        ("bob", "analyst"),
        ("bob", "reviewer"),
        ("cara", "guest"),
    ]);

    let role_permission = BinaryRelation::from_pairs([
        ("admin", "read"),
        ("admin", "write"),
        ("admin", "deploy"),
        ("analyst", "read"),
        ("reviewer", "approve"),
        ("guest", "read"),
    ]);

    let effective_permission = user_role.compose(&role_permission);
    let bob = UnaryRelation::singleton("bob");
    let bob_permissions = effective_permission.image(&bob);

    assert!(effective_permission.contains(&"ann", &"deploy"));
    assert!(bob_permissions.contains(&"approve"));
    assert!(bob_permissions.contains(&"read"));

    println!(
        "effective permissions for bob: {:?}",
        bob_permissions.to_vec()
    );
}

Trait Implementations

impl<T: Clone + Ord> Clone for UnaryRelation<T>

fn clone(&self) -> UnaryRelation<T>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug + Ord> Debug for UnaryRelation<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: Ord> Default for UnaryRelation<T>

fn default() -> Self

Returns the “default value” for a type.

impl<T: Ord> Extend<T> for UnaryRelation<T>

fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<T: Ord> FiniteRelation for UnaryRelation<T>

fn len(&self) -> usize

Returns the number of stored tuples in the relation.

fn is_empty(&self) -> bool

Returns true when the relation contains no tuples.

impl<T: Ord> FromIterator<T> for UnaryRelation<T>

fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self

Creates a value from an iterator.

impl<'a, T: Ord> IntoIterator for &'a UnaryRelation<T>

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T: Ord> IntoIterator for UnaryRelation<T>

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T: PartialEq + Ord> PartialEq for UnaryRelation<T>

fn eq(&self, other: &UnaryRelation<T>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T: Eq + Ord> Eq for UnaryRelation<T>

impl<T: Ord> StructuralPartialEq for UnaryRelation<T>