Struct datafrog::Variable

pub struct Variable<Tuple: Ord> {
    pub stable: Rc<RefCell<Vec<Relation<Tuple>>>>,
    pub recent: Rc<RefCell<Relation<Tuple>>>,
    // some fields omitted
}

An monotonically increasing set of Tuples.

There are three stages in the lifecycle of a tuple:

1. A tuple is added to self.to_add, but is not yet visible externally.
2. Newly added tuples are then promoted to self.recent for one iteration.
3. After one iteration, recent tuples are moved to self.tuples for posterity.

Each time self.changed() is called, the recent relation is folded into tuples, and the to_add relations are merged, potentially deduplicated against tuples, and then made recent. This way, across calls to changed() all added tuples are in recent at least once and eventually all are in tuples.

A Variable may optionally be instructed not to de-duplicate its tuples, for reasons of performance. Such a variable cannot be relied on to terminate iterative computation, and it is important that any cycle of derivations have at least one de-duplicating variable on it.

Fields

stable: Rc<RefCell<Vec<Relation<Tuple>>>>

A list of relations whose union are the accepted tuples.

recent: Rc<RefCell<Relation<Tuple>>>

A list of recent tuples, still to be processed.

Methods

impl<Tuple: Ord> Variable<Tuple>

pub fn from_join<K: Ord, V1: Ord, V2: Ord>(     &self,     input1: &Variable<(K, V1)>,     input2: &Variable<(K, V2)>,     logic: impl FnMut(&K, &V1, &V2) -> Tuple )

Adds tuples that result from joining input1 and input2.

Examples

This example starts a collection with the pairs (x, x+1) and (x+1, x) for x in 0 .. 10. It then adds pairs (y, z) for which (x, y) and (x, z) are present. Because the initial pairs are symmetric, this should result in all pairs (x, y) for x and y in 0 .. 11.

use datafrog::{Iteration, Relation};

let mut iteration = Iteration::new();
let variable = iteration.variable::<(usize, usize)>("source");
variable.insert(Relation::from((0 .. 10).map(|x| (x, x + 1))));
variable.insert(Relation::from((0 .. 10).map(|x| (x + 1, x))));

while iteration.changed() {
    variable.from_join(&variable, &variable, |&key, &val1, &val2| (val1, val2));
}

let result = variable.complete();
assert_eq!(result.len(), 121);

pub fn from_antijoin<K: Ord, V: Ord>(     &self,     input1: &Variable<(K, V)>,     input2: &Relation<K>,     logic: impl FnMut(&K, &V) -> Tuple )

Adds tuples from input1 whose key is not present in input2.

Examples

This example starts a collection with the pairs (x, x+1) for x in 0 .. 10. It then adds any pairs (x+1,x) for which x is not a multiple of three. That excludes four pairs (for 0, 3, 6, and 9) which should leave us with 16 total pairs.

use datafrog::{Iteration, Relation};

let mut iteration = Iteration::new();
let variable = iteration.variable::<(usize, usize)>("source");
variable.insert(Relation::from((0 .. 10).map(|x| (x, x + 1))));

let relation = Relation::from((0 .. 10).filter(|x| x % 3 == 0));

while iteration.changed() {
    variable.from_antijoin(&variable, &relation, |&key, &val| (val, key));
}

let result = variable.complete();
assert_eq!(result.len(), 16);

pub fn from_map<T2: Ord>(     &self,     input: &Variable<T2>,     logic: impl FnMut(&T2) -> Tuple )

Adds tuples that result from mapping input.

Examples

This example starts a collection with the pairs (x, x) for x in 0 .. 10. It then repeatedly adds any pairs (x, z) for (x, y) in the collection, where z is the Collatz step for y: it is y/2 if y is even, and 3*y + 1 if y is odd. This produces all of the pairs (x, y) where x visits y as part of its Collatz journey.

use datafrog::{Iteration, Relation};

let mut iteration = Iteration::new();
let variable = iteration.variable::<(usize, usize)>("source");
variable.insert(Relation::from((0 .. 10).map(|x| (x, x))));

let relation = Relation::from((0 .. 10).filter(|x| x % 3 == 0));

while iteration.changed() {
    variable.from_map(&variable, |&(key, val)|
        if val % 2 == 0 {
            (key, val/2)
        }
        else {
            (key, 3*val + 1)
        });
}

let result = variable.complete();
assert_eq!(result.len(), 74);

impl<Tuple: Ord> Variable<Tuple>

pub fn insert(&self, relation: Relation<Tuple>)

Inserts a relation into the variable.

This is most commonly used to load initial values into a variable. it is not obvious that it should be commonly used otherwise, but it should not be harmful.

pub fn complete(self) -> Relation<Tuple>

Consumes the variable and returns a relation.

This method removes the ability for the variable to develop, and flattens all internal tuples down to one relation. The method asserts that iteration has completed, in that self.recent and self.to_add should both be empty.

Trait Implementations

impl<Tuple: Ord> Clone for Variable<Tuple>

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.