Struct datafrog::Variable [−][src]
An monotonically increasing set of Tuple
s.
There are three stages in the lifecycle of a tuple:
- A tuple is added to
self.to_add
, but is not yet visible externally. - Newly added tuples are then promoted to
self.recent
for one iteration. - 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.
Implementations
impl<Tuple: Ord> Variable<Tuple>
[src]
pub fn from_join<'me, K: Ord, V1: Ord, V2: Ord>(
&self,
input1: &'me Variable<(K, V1)>,
input2: impl JoinInput<'me, (K, V2)>,
logic: impl FnMut(&K, &V1, &V2) -> Tuple
)
[src]
&self,
input1: &'me Variable<(K, V1)>,
input2: impl JoinInput<'me, (K, V2)>,
logic: impl FnMut(&K, &V1, &V2) -> Tuple
)
Adds tuples that result from joining input1
and input2
–
each of the inputs must be a set of (Key, Value) tuples. Both
input1
and input2
must have the same type of key (K
) but
they can have distinct value types (V1
and V2
respectively). The logic
closure will be invoked for each
key that appears in both inputs; it is also given the two
values, and from those it should construct the resulting
value.
Note that input1
must be a variable, but input2
can be a
relation or a variable. Therefore, you cannot join two
relations with this method. This is not because the result
would be wrong, but because it would be inefficient: the
result from such a join cannot vary across iterations (as
relations are fixed), so you should prefer to invoke insert
on a relation created by Relation::from_join
instead.
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.extend((0 .. 10).map(|x| (x, x + 1))); variable.extend((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
)
[src]
&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
.
Note that input1
must be a variable: if you have a relation
instead, you can use Relation::from_antijoin
and then
Variable::insert
. Note that the result will not vary during
the iteration.
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.extend((0 .. 10).map(|x| (x, x + 1))); let relation: Relation<_> = (0 .. 10).filter(|x| x % 3 == 0).collect(); 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
)
[src]
&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.extend((0 .. 10).map(|x| (x, x))); 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);
pub fn from_leapjoin<'leap, SourceTuple: Ord, Val: Ord + 'leap>(
&self,
source: &Variable<SourceTuple>,
leapers: impl Leapers<'leap, SourceTuple, Val>,
logic: impl FnMut(&SourceTuple, &Val) -> Tuple
)
[src]
&self,
source: &Variable<SourceTuple>,
leapers: impl Leapers<'leap, SourceTuple, Val>,
logic: impl FnMut(&SourceTuple, &Val) -> Tuple
)
Adds tuples that result from combining source
with the
relations given in leapers
. This operation is very flexible
and can be used to do a combination of joins and anti-joins.
The main limitation is that the things being combined must
consist of one dynamic variable (source
) and then several
fixed relations (leapers
).
The idea is as follows:
- You will be inserting new tuples that result from joining (and anti-joining)
some dynamic variable
source
of source tuples (SourceTuple
) with some set of values (of typeVal
). - You provide these values by combining
source
with a set of leapersleapers
, each of which is derived from a fixed relation. Theleapers
should be either a single leaper (of suitable type) or else a tuple of leapers. You can create a leaper in one of two ways:- Extension: In this case, you have a relation of type
(K, Val)
for some typeK
. You provide a closure that maps fromSourceTuple
to the keyK
. If you userelation.extend_with
, then anyVal
values the relation provides will be added to the set of values; if you useextend_anti
, then theVal
values will be removed. - Filtering: In this case, you have a relation of type
K
for some typeK
and you provide a closure that maps fromSourceTuple
to the keyK
. Filters don’t provide values but they remove source tuples.
- Extension: In this case, you have a relation of type
- Finally, you get a callback
logic
that accepts each(SourceTuple, Val)
that was successfully joined (and not filtered) and which maps to the type of this variable.
impl<Tuple: Ord> Variable<Tuple>
[src]
pub fn insert(&self, relation: Relation<Tuple>)
[src]
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 extend<T>(&self, iterator: impl IntoIterator<Item = T>) where
Relation<Tuple>: FromIterator<T>,
[src]
Relation<Tuple>: FromIterator<T>,
Extend the variable with values from the iterator.
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>
[src]
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>
[src]
fn clone(&self) -> Self
[src]
pub fn clone_from(&mut self, source: &Self)
1.0.0[src]
impl<'me, Tuple: Ord> JoinInput<'me, Tuple> for &'me Variable<Tuple>
[src]
type RecentTuples = Ref<'me, [Tuple]>
If we are on iteration N of the loop, these are the tuples
added on iteration N-1. (For a Relation
, this is always an
empty slice.) Read more
type StableTuples = Ref<'me, [Relation<Tuple>]>
If we are on iteration N of the loop, these are the tuples
added on iteration N - 2 or before. (For a Relation
, this is
just self
.) Read more
fn recent(self) -> Self::RecentTuples
[src]
fn stable(self) -> Self::StableTuples
[src]
Auto Trait Implementations
impl<Tuple> !RefUnwindSafe for Variable<Tuple>
impl<Tuple> !Send for Variable<Tuple>
impl<Tuple> !Sync for Variable<Tuple>
impl<Tuple> Unpin for Variable<Tuple>
impl<Tuple> !UnwindSafe for Variable<Tuple>
Blanket Implementations
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
pub fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> From<T> for T
[src]
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<T> ToOwned for T where
T: Clone,
[src]
T: Clone,
type Owned = T
The resulting type after obtaining ownership.
pub fn to_owned(&self) -> T
[src]
pub fn clone_into(&self, target: &mut T)
[src]
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
pub fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,