parsec 0.7.3

Implementation of Protocol for Asynchronous, Reliable, Secure and Efficient Consensus
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

// Copyright 2018 MaidSafe.net limited.
//
// This SAFE Network Software is licensed to you under The General Public License (GPL), version 3.
// Unless required by applicable law or agreed to in writing, the SAFE Network Software distributed
// under the GPL Licence is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
// KIND, either express or implied. Please review the Licences for the specific language governing
// permissions and limitations relating to use of the SAFE Network Software.

use super::{Graph, IndexedEventRef};
use crate::id::PublicId;
use std::collections::BTreeSet;

pub(crate) struct Ancestors<'a, P: PublicId + 'a> {
    pub(super) graph: &'a Graph<P>,
    pub(super) queue: BTreeSet<IndexedEventRef<'a, P>>,
    pub(super) visited: Vec<bool>, // TODO: replace with bitset, for space efficiency
}

impl<'a, P: PublicId> Iterator for Ancestors<'a, P> {
    type Item = IndexedEventRef<'a, P>;

    fn next(&mut self) -> Option<Self::Item> {
        // This is a modified breadth-first search: Instead of using a simple queue to track the
        // events to visit next, we use a priority queue (implemented as a BTreeMap keyed by
        // `topological_index`) so the events are visited in reverse topological order (children
        // before parents). We also keep track of the events we already visited, to avoid returning
        // a single event more than once.

        loop {
            let event = *self.queue.iter().rev().next()?;
            let _ = self.queue.remove(&event);

            if self.visited[event.topological_index()] {
                continue;
            }
            self.visited[event.topological_index()] = true;

            if let Some(parent) = event.self_parent().and_then(|index| self.graph.get(index)) {
                let _ = self.queue.insert(parent);
            }

            if let Some(parent) = event.other_parent().and_then(|index| self.graph.get(index)) {
                let _ = self.queue.insert(parent);
            }

            return Some(event);
        }
    }
}