/rust/registry/src/index.crates.io-1949cf8c6b5b557f/prodash-31.0.0/src/progress/key.rs

Source
use std::ops::{Index, IndexMut};

use crate::progress::Task;

/// a level in the hierarchy of key components
///
/// _NOTE:_ This means we will show weird behaviour if there are more than 2^16 tasks at the same time on a level
/// as multiple progress handles will manipulate the same state.
pub type Level = u8;

pub(crate) type Id = u16;

/// A type identifying a spot in the hierarchy of `Tree` items.
#[derive(Copy, Clone, Default, Hash, Eq, PartialEq, Ord, PartialOrd, Debug)]
pub struct Key(Option<Id>, Option<Id>, Option<Id>, Option<Id>, Option<Id>, Option<Id>);

/// Determines if a sibling is above or below in the given level of hierarchy
#[derive(Default, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Debug)]
#[allow(missing_docs)]
pub enum SiblingLocation {
    Above,
    Below,
    AboveAndBelow,
    #[default]
    NotFound,
}

impl SiblingLocation {
    fn merge(&mut self, other: SiblingLocation) {
        use SiblingLocation::*;
        *self = match (*self, other) {
            (any, NotFound) => any,
            (NotFound, any) => any,
            (Above, Below) => AboveAndBelow,
            (Below, Above) => AboveAndBelow,
            (AboveAndBelow, _) => AboveAndBelow,
            (_, AboveAndBelow) => AboveAndBelow,
            (Above, Above) => Above,
            (Below, Below) => Below,
        };
    }
}

/// A type providing information about what's above and below `Tree` items.
#[derive(Copy, Clone, Default, Eq, PartialEq, Ord, PartialOrd, Debug)]
pub struct Adjacency(
    pub SiblingLocation,
    pub SiblingLocation,
    pub SiblingLocation,
    pub SiblingLocation,
    pub SiblingLocation,
    pub SiblingLocation,
);

impl Adjacency {
    /// Return the level at which this sibling is located in the hierarchy.
    pub fn level(&self) -> Level {
        use SiblingLocation::*;
        match self {
            Adjacency(NotFound, NotFound, NotFound, NotFound, NotFound, NotFound) => 0,
            Adjacency(_a, NotFound, NotFound, NotFound, NotFound, NotFound) => 1,
            Adjacency(_a, _b, NotFound, NotFound, NotFound, NotFound) => 2,
            Adjacency(_a, _b, _c, NotFound, NotFound, NotFound) => 3,
            Adjacency(_a, _b, _c, _d, NotFound, NotFound) => 4,
            Adjacency(_a, _b, _c, _d, _e, NotFound) => 5,
            Adjacency(_a, _b, _c, _d, _e, _f) => 6,
        }
    }
    /// Get a reference to the sibling location at `level`.
    pub fn get(&self, level: Level) -> Option<&SiblingLocation> {
        Some(match level {
            1 => &self.0,
            2 => &self.1,
            3 => &self.2,
            4 => &self.3,
            5 => &self.4,
            6 => &self.5,
            _ => return None,
        })
    }
    /// Get a mutable reference to the sibling location at `level`.
    pub fn get_mut(&mut self, level: Level) -> Option<&mut SiblingLocation> {
        Some(match level {
            1 => &mut self.0,
            2 => &mut self.1,
            3 => &mut self.2,
            4 => &mut self.3,
            5 => &mut self.4,
            6 => &mut self.5,
            _ => return None,
        })
    }
}

impl Index<Level> for Adjacency {
    type Output = SiblingLocation;
    fn index(&self, index: Level) -> &Self::Output {
        self.get(index).expect("adjacency index in bound")
    }
}

impl IndexMut<Level> for Adjacency {
    fn index_mut(&mut self, index: Level) -> &mut Self::Output {
        self.get_mut(index).expect("adjacency index in bound")
    }
}

impl Key {
    /// Return the key to the child identified by `child_id` located in a new nesting level below `self`.
    pub fn add_child(self, child_id: Id) -> Key {
        match self {
            Key(None, None, None, None, None, None) => Key(Some(child_id), None, None, None, None, None),
            Key(a, None, None, None, None, None) => Key(a, Some(child_id), None, None, None, None),
            Key(a, b, None, None, None, None) => Key(a, b, Some(child_id), None, None, None),
            Key(a, b, c, None, None, None) => Key(a, b, c, Some(child_id), None, None),
            Key(a, b, c, d, None, None) => Key(a, b, c, d, Some(child_id), None),
            Key(a, b, c, d, e, _f) => {
                crate::warn!("Maximum nesting level reached. Adding tasks to current parent");
                Key(a, b, c, d, e, Some(child_id))
            }
        }
    }

    /// The level of hierarchy a node is placed in, i.e. the amount of path components
    pub fn level(&self) -> Level {
        match self {
            Key(None, None, None, None, None, None) => 0,
            Key(Some(_), None, None, None, None, None) => 1,
            Key(Some(_), Some(_), None, None, None, None) => 2,
            Key(Some(_), Some(_), Some(_), None, None, None) => 3,
            Key(Some(_), Some(_), Some(_), Some(_), None, None) => 4,
            Key(Some(_), Some(_), Some(_), Some(_), Some(_), None) => 5,
            Key(Some(_), Some(_), Some(_), Some(_), Some(_), Some(_)) => 6,
            _ => unreachable!("This is a bug - Keys follow a certain pattern"),
        }
    }

    /// Return the identifier for the item at `level`.
    fn get(&self, level: Level) -> Option<&Id> {
        match level {
            1 => self.0.as_ref(),
            2 => self.1.as_ref(),
            3 => self.2.as_ref(),
            4 => self.3.as_ref(),
            5 => self.4.as_ref(),
            6 => self.5.as_ref(),
            _ => None,
        }
    }

    /// Return true if the item identified by `other` shares the parent at `parent_level`.
    pub fn shares_parent_with(&self, other: &Key, parent_level: Level) -> bool {
        if parent_level < 1 {
            return true;
        }
        for level in 1..=parent_level {
            if let (Some(lhs), Some(rhs)) = (self.get(level), other.get(level)) {
                if lhs != rhs {
                    return false;
                }
            } else {
                return false;
            }
        }
        true
    }

    /// Compute the adjacency map for the key in `sorted` at the given `index`.
    ///
    /// It's vital that the invariant of `sorted` to actually be sorted by key is upheld
    /// for the result to be reliable.
    pub fn adjacency(sorted: &[(Key, Task)], index: usize) -> Adjacency {
        use SiblingLocation::*;
        let key = &sorted[index].0;
        let key_level = key.level();
        let mut adjecency = Adjacency::default();
        if key_level == 0 {
            return adjecency;
        }

        fn search<'a>(
            iter: impl Iterator<Item = &'a (Key, Task)>,
            key: &Key,
            key_level: Level,
            current_level: Level,
            _id_at_level: Id,
        ) -> Option<usize> {
            iter.map(|(k, _)| k)
                .take_while(|other| key.shares_parent_with(other, current_level.saturating_sub(1)))
                .enumerate()
                .find(|(_idx, k)| {
                    if current_level == key_level {
                        k.level() == key_level || k.level() + 1 == key_level
                    } else {
                        k.level() == current_level
                    }
                })
                .map(|(idx, _)| idx)
        }

        let upward_iter = |from: usize, key: &Key, level: Level, id_at_level: Id| {
            search(sorted[..from].iter().rev(), key, key_level, level, id_at_level)
        };
        let downward_iter = |from: usize, key: &Key, level: Level, id_at_level: Id| {
            sorted
                .get(from + 1..)
                .and_then(|s| search(s.iter(), key, key_level, level, id_at_level))
        };

        {
            let mut cursor = index;
            for level in (1..=key_level).rev() {
                if level == 1 {
                    adjecency[level].merge(Above); // the root or any other sibling on level one
                    continue;
                }
                if let Some(key_offset) = upward_iter(cursor, key, level, key[level]) {
                    cursor = index.saturating_sub(key_offset);
                    adjecency[level].merge(Above);
                }
            }
        }
        {
            let mut cursor = index;
            for level in (1..=key_level).rev() {
                if let Some(key_offset) = downward_iter(cursor, key, level, key[level]) {
                    cursor = index + key_offset;
                    adjecency[level].merge(Below);
                }
            }
        }
        for level in 1..key_level {
            if key_level == 1 && index + 1 == sorted.len() {
                continue;
            }
            adjecency[level] = match adjecency[level] {
                Above | Below | NotFound => NotFound,
                AboveAndBelow => AboveAndBelow,
            };
        }
        adjecency
    }

    /// The maximum amount of path components we can represent.
    pub const fn max_level() -> Level {
        6
    }
}

impl Index<Level> for Key {
    type Output = Id;

    fn index(&self, index: Level) -> &Self::Output {
        self.get(index).expect("key index in bound")
    }
}

Coverage Report

Created: 2026-03-31 07:35

Line	Count	Source
1		use std::ops::{Index, IndexMut};
2
3		use crate::progress::Task;
4
5		/// a level in the hierarchy of key components
6		///
7		/// _NOTE:_ This means we will show weird behaviour if there are more than 2^16 tasks at the same time on a level
8		/// as multiple progress handles will manipulate the same state.
9		pub type Level = u8;
10
11		pub(crate) type Id = u16;
12
13		/// A type identifying a spot in the hierarchy of `Tree` items.
14		#[derive(Copy, Clone, Default, Hash, Eq, PartialEq, Ord, PartialOrd, Debug)]
15		pub struct Key(Option<Id>, Option<Id>, Option<Id>, Option<Id>, Option<Id>, Option<Id>);
16
17		/// Determines if a sibling is above or below in the given level of hierarchy
18		#[derive(Default, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Debug)]
19		#[allow(missing_docs)]
20		pub enum SiblingLocation {
21		Above,
22		Below,
23		AboveAndBelow,
24		#[default]
25		NotFound,
26		}
27
28		impl SiblingLocation {
29	0	fn merge(&mut self, other: SiblingLocation) {
30		use SiblingLocation::*;
31	0	self = match (self, other) {
32	0	(any, NotFound) => any,
33	0	(NotFound, any) => any,
34	0	(Above, Below) => AboveAndBelow,
35	0	(Below, Above) => AboveAndBelow,
36	0	(AboveAndBelow, _) => AboveAndBelow,
37	0	(_, AboveAndBelow) => AboveAndBelow,
38	0	(Above, Above) => Above,
39	0	(Below, Below) => Below,
40		};
41	0	}
42		}
43
44		/// A type providing information about what's above and below `Tree` items.
45		#[derive(Copy, Clone, Default, Eq, PartialEq, Ord, PartialOrd, Debug)]
46		pub struct Adjacency(
47		pub SiblingLocation,
48		pub SiblingLocation,
49		pub SiblingLocation,
50		pub SiblingLocation,
51		pub SiblingLocation,
52		pub SiblingLocation,
53		);
54
55		impl Adjacency {
56		/// Return the level at which this sibling is located in the hierarchy.
57	0	pub fn level(&self) -> Level {
58		use SiblingLocation::*;
59	0	match self {
60	0	Adjacency(NotFound, NotFound, NotFound, NotFound, NotFound, NotFound) => 0,
61	0	Adjacency(_a, NotFound, NotFound, NotFound, NotFound, NotFound) => 1,
62	0	Adjacency(_a, _b, NotFound, NotFound, NotFound, NotFound) => 2,
63	0	Adjacency(_a, _b, _c, NotFound, NotFound, NotFound) => 3,
64	0	Adjacency(_a, _b, _c, _d, NotFound, NotFound) => 4,
65	0	Adjacency(_a, _b, _c, _d, _e, NotFound) => 5,
66	0	Adjacency(_a, _b, _c, _d, _e, _f) => 6,
67		}
68	0	}
69		/// Get a reference to the sibling location at `level`.
70	0	pub fn get(&self, level: Level) -> Option<&SiblingLocation> {
71	0	Some(match level {
72	0	1 => &self.0,
73	0	2 => &self.1,
74	0	3 => &self.2,
75	0	4 => &self.3,
76	0	5 => &self.4,
77	0	6 => &self.5,
78	0	_ => return None,
79		})
80	0	}
81		/// Get a mutable reference to the sibling location at `level`.
82	0	pub fn get_mut(&mut self, level: Level) -> Option<&mut SiblingLocation> {
83	0	Some(match level {
84	0	1 => &mut self.0,
85	0	2 => &mut self.1,
86	0	3 => &mut self.2,
87	0	4 => &mut self.3,
88	0	5 => &mut self.4,
89	0	6 => &mut self.5,
90	0	_ => return None,
91		})
92	0	}
93		}
94
95		impl Index<Level> for Adjacency {
96		type Output = SiblingLocation;
97	0	fn index(&self, index: Level) -> &Self::Output {
98	0	self.get(index).expect("adjacency index in bound")
99	0	}
100		}
101
102		impl IndexMut<Level> for Adjacency {
103	0	fn index_mut(&mut self, index: Level) -> &mut Self::Output {
104	0	self.get_mut(index).expect("adjacency index in bound")
105	0	}
106		}
107
108		impl Key {
109		/// Return the key to the child identified by `child_id` located in a new nesting level below `self`.
110	0	pub fn add_child(self, child_id: Id) -> Key {
111	0	match self {
112	0	Key(None, None, None, None, None, None) => Key(Some(child_id), None, None, None, None, None),
113	0	Key(a, None, None, None, None, None) => Key(a, Some(child_id), None, None, None, None),
114	0	Key(a, b, None, None, None, None) => Key(a, b, Some(child_id), None, None, None),
115	0	Key(a, b, c, None, None, None) => Key(a, b, c, Some(child_id), None, None),
116	0	Key(a, b, c, d, None, None) => Key(a, b, c, d, Some(child_id), None),
117	0	Key(a, b, c, d, e, _f) => {
118		crate::warn!("Maximum nesting level reached. Adding tasks to current parent");
119	0	Key(a, b, c, d, e, Some(child_id))
120		}
121		}
122	0	}
123
124		/// The level of hierarchy a node is placed in, i.e. the amount of path components
125	0	pub fn level(&self) -> Level {
126	0	match self {
127	0	Key(None, None, None, None, None, None) => 0,
128	0	Key(Some(_), None, None, None, None, None) => 1,
129	0	Key(Some(_), Some(_), None, None, None, None) => 2,
130	0	Key(Some(_), Some(_), Some(_), None, None, None) => 3,
131	0	Key(Some(_), Some(_), Some(_), Some(_), None, None) => 4,
132	0	Key(Some(_), Some(_), Some(_), Some(_), Some(_), None) => 5,
133	0	Key(Some(_), Some(_), Some(_), Some(_), Some(_), Some(_)) => 6,
134	0	_ => unreachable!("This is a bug - Keys follow a certain pattern"),
135		}
136	0	}
137
138		/// Return the identifier for the item at `level`.
139	0	fn get(&self, level: Level) -> Option<&Id> {
140	0	match level {
141	0	1 => self.0.as_ref(),
142	0	2 => self.1.as_ref(),
143	0	3 => self.2.as_ref(),
144	0	4 => self.3.as_ref(),
145	0	5 => self.4.as_ref(),
146	0	6 => self.5.as_ref(),
147	0	_ => None,
148		}
149	0	}
150
151		/// Return true if the item identified by `other` shares the parent at `parent_level`.
152	0	pub fn shares_parent_with(&self, other: &Key, parent_level: Level) -> bool {
153	0	if parent_level < 1 {
154	0	return true;
155	0	}
156	0	for level in 1..=parent_level {
157	0	if let (Some(lhs), Some(rhs)) = (self.get(level), other.get(level)) {
158	0	if lhs != rhs {
159	0	return false;
160	0	}
161		} else {
162	0	return false;
163		}
164		}
165	0	true
166	0	}
167
168		/// Compute the adjacency map for the key in `sorted` at the given `index`.
169		///
170		/// It's vital that the invariant of `sorted` to actually be sorted by key is upheld
171		/// for the result to be reliable.
172	0	pub fn adjacency(sorted: &[(Key, Task)], index: usize) -> Adjacency {
173		use SiblingLocation::*;
174	0	let key = &sorted[index].0;
175	0	let key_level = key.level();
176	0	let mut adjecency = Adjacency::default();
177	0	if key_level == 0 {
178	0	return adjecency;
179	0	}
180
181	0	fn search<'a>(
182	0	iter: impl Iterator<Item = &'a (Key, Task)>,
183	0	key: &Key,
184	0	key_level: Level,
185	0	current_level: Level,
186	0	_id_at_level: Id,
187	0	) -> Option<usize> {
188	0	iter.map(\|(k, _)\| k)
189	0	.take_while(\|other\| key.shares_parent_with(other, current_level.saturating_sub(1))) Unexecuted instantiation: <prodash::progress::key::Key>::adjacency::search::<core::slice::iter::Iter<(prodash::progress::key::Key, prodash::progress::Task)>>::{closure#1} Unexecuted instantiation: <prodash::progress::key::Key>::adjacency::search::<core::iter::adapters::rev::Rev<core::slice::iter::Iter<(prodash::progress::key::Key, prodash::progress::Task)>>>::{closure#1}
190	0	.enumerate()
191	0	.find(\|(_idx, k)\| {
192	0	if current_level == key_level {
193	0	k.level() == key_level \|\| k.level() + 1 == key_level
194		} else {
195	0	k.level() == current_level
196		}
197	0	}) Unexecuted instantiation: <prodash::progress::key::Key>::adjacency::search::<core::slice::iter::Iter<(prodash::progress::key::Key, prodash::progress::Task)>>::{closure#2} Unexecuted instantiation: <prodash::progress::key::Key>::adjacency::search::<core::iter::adapters::rev::Rev<core::slice::iter::Iter<(prodash::progress::key::Key, prodash::progress::Task)>>>::{closure#2}
198	0	.map(\|(idx, _)\| idx)
199	0	} Unexecuted instantiation: <prodash::progress::key::Key>::adjacency::search::<core::slice::iter::Iter<(prodash::progress::key::Key, prodash::progress::Task)>> Unexecuted instantiation: <prodash::progress::key::Key>::adjacency::search::<core::iter::adapters::rev::Rev<core::slice::iter::Iter<(prodash::progress::key::Key, prodash::progress::Task)>>>
200
201	0	let upward_iter = \|from: usize, key: &Key, level: Level, id_at_level: Id\| {
202	0	search(sorted[..from].iter().rev(), key, key_level, level, id_at_level)
203	0	};
204	0	let downward_iter = \|from: usize, key: &Key, level: Level, id_at_level: Id\| {
205	0	sorted
206	0	.get(from + 1..)
207	0	.and_then(\|s\| search(s.iter(), key, key_level, level, id_at_level))
208	0	};
209
210		{
211	0	let mut cursor = index;
212	0	for level in (1..=key_level).rev() {
213	0	if level == 1 {
214	0	adjecency[level].merge(Above); // the root or any other sibling on level one
215	0	continue;
216	0	}
217	0	if let Some(key_offset) = upward_iter(cursor, key, level, key[level]) {
218	0	cursor = index.saturating_sub(key_offset);
219	0	adjecency[level].merge(Above);
220	0	}
221		}
222		}
223		{
224	0	let mut cursor = index;
225	0	for level in (1..=key_level).rev() {
226	0	if let Some(key_offset) = downward_iter(cursor, key, level, key[level]) {
227	0	cursor = index + key_offset;
228	0	adjecency[level].merge(Below);
229	0	}
230		}
231		}
232	0	for level in 1..key_level {
233	0	if key_level == 1 && index + 1 == sorted.len() {
234	0	continue;
235	0	}
236	0	adjecency[level] = match adjecency[level] {
237	0	Above \| Below \| NotFound => NotFound,
238	0	AboveAndBelow => AboveAndBelow,
239		};
240		}
241	0	adjecency
242	0	}
243
244		/// The maximum amount of path components we can represent.
245	0	pub const fn max_level() -> Level {
246	0	6
247	0	}
248		}
249
250		impl Index<Level> for Key {
251		type Output = Id;
252
253	0	fn index(&self, index: Level) -> &Self::Output {
254	0	self.get(index).expect("key index in bound")
255	0	}
256		}