dagre 0.1.1

A Rust port of dagre - directed graph layout using the Sugiyama method
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

//! Sort resolved entries by barycenter, interleaving unsortable entries.
//!
//! Entries that have a barycenter are sorted by it. Entries without a barycenter
//! ("unsortable") are placed at their original index position, interleaved
//! among the sorted entries.

use super::resolve_conflicts::ResolvedEntry;

/// Result of sorting: the final node order and optional aggregate barycenter/weight.
#[derive(Debug, Clone)]
pub(crate) struct SortResult {
    pub vs: Vec<String>,
    pub barycenter: Option<f64>,
    pub weight: Option<i32>,
}

/// Sort entries, placing those with barycenters in order and interleaving
/// those without at their original positions.
pub(crate) fn sort(entries: &[ResolvedEntry], bias_right: bool) -> SortResult {
    // Partition into sortable (has barycenter) and unsortable (no barycenter)
    let mut sortable: Vec<&ResolvedEntry> = Vec::new();
    let mut unsortable: Vec<&ResolvedEntry> = Vec::new();

    for entry in entries {
        if entry.barycenter.is_some() {
            sortable.push(entry);
        } else {
            unsortable.push(entry);
        }
    }

    // Sort unsortable by descending index (so we can pop from the end to get ascending)
    unsortable.sort_by(|a, b| b.i.cmp(&a.i));

    // Sort sortable by barycenter, with tie-breaking by index
    sortable.sort_by(|a, b| {
        let a_bc = a.barycenter.unwrap();
        let b_bc = b.barycenter.unwrap();
        if a_bc < b_bc {
            return std::cmp::Ordering::Less;
        }
        if a_bc > b_bc {
            return std::cmp::Ordering::Greater;
        }
        // Tie-break by index
        if !bias_right {
            a.i.cmp(&b.i)
        } else {
            b.i.cmp(&a.i)
        }
    });

    let mut vs: Vec<Vec<String>> = Vec::new();
    let mut sum = 0.0_f64;
    let mut weight = 0_i32;
    let mut vs_index: usize = 0;

    // Consume unsortable entries whose index <= current position
    consume_unsortable(&mut vs, &mut unsortable, &mut vs_index);

    for entry in &sortable {
        vs_index += entry.vs.len();
        vs.push(entry.vs.clone());
        sum += entry.barycenter.unwrap() * entry.weight.unwrap() as f64;
        weight += entry.weight.unwrap();
        consume_unsortable(&mut vs, &mut unsortable, &mut vs_index);
    }

    let flat: Vec<String> = vs.into_iter().flatten().collect();

    let mut result = SortResult {
        vs: flat,
        barycenter: None,
        weight: None,
    };

    if weight > 0 {
        result.barycenter = Some(sum / weight as f64);
        result.weight = Some(weight);
    }

    result
}

/// Pop unsortable entries whose original index is <= the current vs_index.
fn consume_unsortable(
    vs: &mut Vec<Vec<String>>,
    unsortable: &mut Vec<&ResolvedEntry>,
    index: &mut usize,
) {
    while let Some(last) = unsortable.last() {
        if last.i <= *index {
            let entry = unsortable.pop().unwrap();
            vs.push(entry.vs.clone());
            *index += 1;
        } else {
            break;
        }
    }
}