Struct EquivalenceClass

Source

pub struct EquivalenceClass { /* private fields */ }

Expand description

A bounded union-by-rank equivalence-class partition.

Implementations§

Source §

impl EquivalenceClass

Source

pub fn new(elements: usize, max_unions: u64) -> Self

Construct a singleton partition with a merge-operation ceiling.

Examples found in repository ?

examples/catalog.rs (line 84)

20fn main() -> Result<(), Box<dyn Error>> {
21    // Primitives.
22    let mut budget = Budget::new(8);
23    assert!(budget.try_reserve(3));
24    budget.commit_reservation(3)?;
25
26    let mut hierarchy = QualityHierarchy::new(2, 2);
27    hierarchy.set_node_properties(0, 2, 1)?;
28    hierarchy.set_node_properties(1, 1, 2)?;
29    hierarchy.add_child(0, 1)?;
30
31    let mut registry = ResourceRegistry::new();
32    registry.insert(1, 10);
33    assert_eq!(registry.get(1), Some(10));
34
35    let mut hard = CompetitiveSelectionHard::new(2)?;
36    hard.update_score(0, 2)?;
37    hard.update_score(1, 1)?;
38    assert_eq!(hard.evaluate(), 0);
39
40    let mut exclusive = CompetitiveSelectionHardExclusive::new(1, 2, 2)?;
41    exclusive.update_score(0, 0, 2)?;
42    exclusive.update_score(0, 1, 1)?;
43    assert_eq!(exclusive.evaluate(0)?, 0);
44
45    let mut soft = CompetitiveSelectionSoft::begin(vec![3, 1], 4, 3)?;
46    assert_eq!(soft.assign_next()?, 0);
47
48    let mut ranked = CompetitiveSelectionRanked::new(vec![2, 1], 1, 2)?;
49    ranked.select();
50    assert_eq!(ranked.is_selected(0), Some(true));
51
52    let mut actuation = ActuationPass::new(vec![Some(7)]);
53    actuation.actuate(0)?;
54    actuation.finish()?;
55
56    let mut propagation = PropagationPass::new(1, 2, vec![], vec![0])?;
57    propagation.start_round()?;
58    propagation.update_node(0)?;
59    propagation.end_round()?;
60
61    let mut convergence = ConvergenceGovernor::new(2, 6, 2, 10)?;
62    assert_eq!(convergence.update(1)?, 1);
63
64    let mut audit = AuditSink::new(1);
65    assert!(audit.try_record(7));
66    assert!(audit.validate());
67
68    let mut backtracking = BacktrackingTraversal::new(2, 1, 0)?;
69    backtracking.descend(1, 1)?;
70    backtracking.visit()?;
71
72    // Named compositions.
73    let mut snapshot = AllocationSnapshot::new(3, 1);
74    snapshot.accept(0, 3)?;
75
76    let mut federated = FederatedBudget::new(4, 1);
77    assert!(federated.try_delegate(0, 4));
78    assert!(federated.try_allocate(0, 2));
79
80    let mut bisection = Bisection::new(4, 2)?;
81    bisection.converge();
82    assert!(bisection.is_converged());
83
84    let mut classes = EquivalenceClass::new(2, 1);
85    assert!(classes.union(0, 1)?);
86
87    let mut rate_limit = RateLimit::new(1, 1, 1)?;
88    assert!(rate_limit.try_acquire());
89
90    let mut reduction = Reduction::new(vec![2, 3])?;
91    reduction.process_next()?;
92
93    let mut graph = RelationshipGraph::new(2, 1);
94    assert!(graph.add_edge(0, 1, 1)?);
95
96    let mut sampler = Sampler::new(vec![1, 1], 1);
97    sampler.sample(0)?;
98
99    let mut signal = Signal::new(0, 2, 1)?;
100    assert!(signal.set_value(1)?);
101    signal.notify(0)?;
102
103    let mut traversal = TraversalEngine::new(1, 0, 1)?;
104    traversal.visit(0)?;
105    traversal.terminate()?;
106
107    // Execution modalities.
108    let mut sequential = Sequential::new(1, 2, 0)?;
109    assert!(sequential.begin_step());
110    assert!(sequential.complete_step(1));
111
112    let mut fork_join = ForkJoin::new(1, 2, 0)?;
113    assert!(fork_join.start_worker(0));
114    assert!(fork_join.complete_worker(0, 1));
115    assert!(fork_join.barrier());
116    assert!(fork_join.produce_output());
117
118    let mut step_graph = StepGraph::new(1, vec![])?;
119    assert!(step_graph.start(0));
120    assert!(step_graph.complete(0));
121
122    let mut stream_graph = StreamGraph::new(3, 1, 1, 2)?;
123    assert!(stream_graph.ingest(1));
124    assert!(stream_graph.advance_first());
125    assert_eq!(stream_graph.consume(), Some(1));
126
127    // Connective roles.
128    let mut cursor = Cursor::new(0);
129    cursor.advance_to(1)?;
130
131    let mut accumulator = Accumulator::new(vec![1]);
132    assert_eq!(accumulator.advance(), Some(1));
133
134    let mut marker = Marker::new(false);
135    assert!(marker.set());
136
137    let mut counter = Counter::new(0);
138    assert!(counter.try_increment());
139
140    let mut buffer = Buffer::new(1);
141    assert_eq!(buffer.push(1), Ok(()));
142    assert_eq!(buffer.pop(), Some(1));
143
144    assert!(projection_consistent(true, true));
145    assert!(strictly_before(0, 1));
146
147    assert_debuggable!(
148        budget,
149        hierarchy,
150        registry,
151        hard,
152        exclusive,
153        soft,
154        ranked,
155        actuation,
156        propagation,
157        convergence,
158        audit,
159        backtracking,
160        snapshot,
161        federated,
162        bisection,
163        classes,
164        rate_limit,
165        reduction,
166        graph,
167        sampler,
168        signal,
169        traversal,
170        sequential,
171        fork_join,
172        step_graph,
173        stream_graph,
174        cursor,
175        accumulator,
176        marker,
177        counter,
178        buffer,
179    );
180
181    println!("all public automation structures constructed and exercised");
182    Ok(())
183}

Source

pub fn len(&self) -> usize

Number of elements in the partition.

Source

pub fn is_empty(&self) -> bool

Whether the partition contains no elements.

Source

pub fn unions_performed(&self) -> u64

Successful union operations performed.

Source

pub fn max_unions(&self) -> u64

Configured union-operation ceiling.

Source

pub fn representative( &self, element: usize, ) -> Result<usize, EquivalenceClassError>

Find an element’s representative.

Source

pub fn union( &mut self, left: usize, right: usize, ) -> Result<bool, EquivalenceClassError>

Merge two classes, returning false if equal or the operation ceiling is exhausted.

Examples found in repository ?

examples/catalog.rs (line 85)

20fn main() -> Result<(), Box<dyn Error>> {
21    // Primitives.
22    let mut budget = Budget::new(8);
23    assert!(budget.try_reserve(3));
24    budget.commit_reservation(3)?;
25
26    let mut hierarchy = QualityHierarchy::new(2, 2);
27    hierarchy.set_node_properties(0, 2, 1)?;
28    hierarchy.set_node_properties(1, 1, 2)?;
29    hierarchy.add_child(0, 1)?;
30
31    let mut registry = ResourceRegistry::new();
32    registry.insert(1, 10);
33    assert_eq!(registry.get(1), Some(10));
34
35    let mut hard = CompetitiveSelectionHard::new(2)?;
36    hard.update_score(0, 2)?;
37    hard.update_score(1, 1)?;
38    assert_eq!(hard.evaluate(), 0);
39
40    let mut exclusive = CompetitiveSelectionHardExclusive::new(1, 2, 2)?;
41    exclusive.update_score(0, 0, 2)?;
42    exclusive.update_score(0, 1, 1)?;
43    assert_eq!(exclusive.evaluate(0)?, 0);
44
45    let mut soft = CompetitiveSelectionSoft::begin(vec![3, 1], 4, 3)?;
46    assert_eq!(soft.assign_next()?, 0);
47
48    let mut ranked = CompetitiveSelectionRanked::new(vec![2, 1], 1, 2)?;
49    ranked.select();
50    assert_eq!(ranked.is_selected(0), Some(true));
51
52    let mut actuation = ActuationPass::new(vec![Some(7)]);
53    actuation.actuate(0)?;
54    actuation.finish()?;
55
56    let mut propagation = PropagationPass::new(1, 2, vec![], vec![0])?;
57    propagation.start_round()?;
58    propagation.update_node(0)?;
59    propagation.end_round()?;
60
61    let mut convergence = ConvergenceGovernor::new(2, 6, 2, 10)?;
62    assert_eq!(convergence.update(1)?, 1);
63
64    let mut audit = AuditSink::new(1);
65    assert!(audit.try_record(7));
66    assert!(audit.validate());
67
68    let mut backtracking = BacktrackingTraversal::new(2, 1, 0)?;
69    backtracking.descend(1, 1)?;
70    backtracking.visit()?;
71
72    // Named compositions.
73    let mut snapshot = AllocationSnapshot::new(3, 1);
74    snapshot.accept(0, 3)?;
75
76    let mut federated = FederatedBudget::new(4, 1);
77    assert!(federated.try_delegate(0, 4));
78    assert!(federated.try_allocate(0, 2));
79
80    let mut bisection = Bisection::new(4, 2)?;
81    bisection.converge();
82    assert!(bisection.is_converged());
83
84    let mut classes = EquivalenceClass::new(2, 1);
85    assert!(classes.union(0, 1)?);
86
87    let mut rate_limit = RateLimit::new(1, 1, 1)?;
88    assert!(rate_limit.try_acquire());
89
90    let mut reduction = Reduction::new(vec![2, 3])?;
91    reduction.process_next()?;
92
93    let mut graph = RelationshipGraph::new(2, 1);
94    assert!(graph.add_edge(0, 1, 1)?);
95
96    let mut sampler = Sampler::new(vec![1, 1], 1);
97    sampler.sample(0)?;
98
99    let mut signal = Signal::new(0, 2, 1)?;
100    assert!(signal.set_value(1)?);
101    signal.notify(0)?;
102
103    let mut traversal = TraversalEngine::new(1, 0, 1)?;
104    traversal.visit(0)?;
105    traversal.terminate()?;
106
107    // Execution modalities.
108    let mut sequential = Sequential::new(1, 2, 0)?;
109    assert!(sequential.begin_step());
110    assert!(sequential.complete_step(1));
111
112    let mut fork_join = ForkJoin::new(1, 2, 0)?;
113    assert!(fork_join.start_worker(0));
114    assert!(fork_join.complete_worker(0, 1));
115    assert!(fork_join.barrier());
116    assert!(fork_join.produce_output());
117
118    let mut step_graph = StepGraph::new(1, vec![])?;
119    assert!(step_graph.start(0));
120    assert!(step_graph.complete(0));
121
122    let mut stream_graph = StreamGraph::new(3, 1, 1, 2)?;
123    assert!(stream_graph.ingest(1));
124    assert!(stream_graph.advance_first());
125    assert_eq!(stream_graph.consume(), Some(1));
126
127    // Connective roles.
128    let mut cursor = Cursor::new(0);
129    cursor.advance_to(1)?;
130
131    let mut accumulator = Accumulator::new(vec![1]);
132    assert_eq!(accumulator.advance(), Some(1));
133
134    let mut marker = Marker::new(false);
135    assert!(marker.set());
136
137    let mut counter = Counter::new(0);
138    assert!(counter.try_increment());
139
140    let mut buffer = Buffer::new(1);
141    assert_eq!(buffer.push(1), Ok(()));
142    assert_eq!(buffer.pop(), Some(1));
143
144    assert!(projection_consistent(true, true));
145    assert!(strictly_before(0, 1));
146
147    assert_debuggable!(
148        budget,
149        hierarchy,
150        registry,
151        hard,
152        exclusive,
153        soft,
154        ranked,
155        actuation,
156        propagation,
157        convergence,
158        audit,
159        backtracking,
160        snapshot,
161        federated,
162        bisection,
163        classes,
164        rate_limit,
165        reduction,
166        graph,
167        sampler,
168        signal,
169        traversal,
170        sequential,
171        fork_join,
172        step_graph,
173        stream_graph,
174        cursor,
175        accumulator,
176        marker,
177        counter,
178        buffer,
179    );
180
181    println!("all public automation structures constructed and exercised");
182    Ok(())
183}