molframe-core 0.5.0

Core types, storage and analysis contracts for molframe
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

//! Allocation-bounded position iteration and sparse merging.

use super::representation::AtomSelection;
use crate::column::Ones;
use std::iter::Peekable;
use std::ops::Range;
use std::slice;

enum MergeCursor<'a> {
    Empty,
    Range(Range<u32>),
    Ranges {
        runs: &'a [Range<u32>],
        run: usize,
        next: u32,
    },
    Sparse(slice::Iter<'a, u32>),
    Dense(Ones<'a>),
}

impl<'a> MergeCursor<'a> {
    fn new(selection: &'a AtomSelection) -> Self {
        match selection {
            AtomSelection::Empty => Self::Empty,
            AtomSelection::All(count) => Self::Range(0..*count),
            AtomSelection::Range(run) => Self::Range(run.start..run.end),
            AtomSelection::Ranges(runs) => Self::Ranges {
                runs,
                run: 0,
                next: runs.first().map_or(0, |run| run.start),
            },
            AtomSelection::Sparse(positions) => Self::Sparse(positions.iter()),
            AtomSelection::Dense(mask) => Self::Dense(mask.ones()),
        }
    }
}

impl Iterator for MergeCursor<'_> {
    type Item = u32;

    fn next(&mut self) -> Option<Self::Item> {
        match self {
            Self::Empty => None,
            Self::Range(range) => range.next(),
            Self::Sparse(positions) => positions.next().copied(),
            Self::Dense(positions) => positions.next(),
            Self::Ranges { runs, run, next } => loop {
                let current = runs.get(*run)?;
                *next = (*next).max(current.start);
                if *next < current.end {
                    let position = *next;
                    *next += 1;
                    return Some(position);
                }
                *run += 1;
                *next = runs.get(*run)?.start;
            },
        }
    }
}

pub(super) fn copy_selection(selection: &AtomSelection) -> AtomSelection {
    match selection {
        AtomSelection::Empty => AtomSelection::Empty,
        AtomSelection::All(count) => AtomSelection::All(*count),
        AtomSelection::Range(run) => AtomSelection::Range(run.start..run.end),
        AtomSelection::Ranges(runs) => {
            AtomSelection::Ranges(runs.iter().map(|run| run.start..run.end).collect())
        }
        AtomSelection::Sparse(positions) => AtomSelection::Sparse(positions.clone()),
        // The mask is reference-counted, so copying one is a count bump
        // rather than a per-bit rebuild of the same words.
        AtomSelection::Dense(mask) => AtomSelection::Dense(mask.clone()),
    }
}

pub(super) fn visit_positions(selection: &AtomSelection, mut visit: impl FnMut(u32)) {
    match selection {
        AtomSelection::Empty => {}
        AtomSelection::All(count) => (0..*count).for_each(visit),
        AtomSelection::Range(run) => (run.start..run.end).for_each(visit),
        AtomSelection::Ranges(runs) => {
            for run in runs {
                for position in run.start..run.end {
                    visit(position);
                }
            }
        }
        AtomSelection::Sparse(positions) => positions.iter().copied().for_each(visit),
        AtomSelection::Dense(mask) => mask.ones().for_each(visit),
    }
}

pub(super) fn merge_positions(left: &AtomSelection, right: &AtomSelection) -> AtomSelection {
    let mut merged = Vec::new();
    merge_cursors(
        MergeCursor::new(left).peekable(),
        MergeCursor::new(right).peekable(),
        &mut merged,
    );
    AtomSelection::from_sorted(merged)
}

fn merge_cursors(
    mut left: Peekable<MergeCursor<'_>>,
    mut right: Peekable<MergeCursor<'_>>,
    merged: &mut Vec<u32>,
) {
    loop {
        let next = match (left.peek().copied(), right.peek().copied()) {
            (None, None) => break,
            (Some(left_position), Some(right_position)) if left_position == right_position => {
                right.next();
                left.next()
            }
            (Some(left_position), Some(right_position)) if left_position > right_position => {
                right.next()
            }
            (Some(_), _) => left.next(),
            (None, Some(_)) => right.next(),
        };
        if let Some(position) = next {
            merged.push(position);
        }
    }
}