petgraph/acyclic/
order_map.rs1use alloc::{collections::BTreeMap, vec, vec::Vec};
7use core::{fmt, ops::RangeBounds};
8
9use crate::{
10 algo::{toposort, Cycle},
11 visit::{GraphBase, IntoNeighborsDirected, IntoNodeIdentifiers, NodeIndexable, Visitable},
12};
13
14#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Default)]
21#[repr(transparent)]
22pub struct TopologicalPosition(pub(super) usize);
23
24#[derive(Clone)]
31pub(super) struct OrderMap<N> {
32 pos_to_node: BTreeMap<TopologicalPosition, N>,
34 node_to_pos: Vec<TopologicalPosition>,
38}
39
40impl<N> Default for OrderMap<N> {
41 fn default() -> Self {
42 Self {
43 pos_to_node: Default::default(),
44 node_to_pos: Default::default(),
45 }
46 }
47}
48
49impl<N: fmt::Debug> fmt::Debug for OrderMap<N> {
50 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
51 f.debug_struct("OrderMap")
52 .field("order", &self.pos_to_node)
53 .finish()
54 }
55}
56
57impl<N: Copy> OrderMap<N> {
58 pub(super) fn try_from_graph<G>(graph: G) -> Result<Self, Cycle<G::NodeId>>
59 where
60 G: NodeIndexable<NodeId = N> + IntoNeighborsDirected + IntoNodeIdentifiers + Visitable,
61 {
62 let topo_vec = toposort(graph, None)?;
64
65 let mut pos_to_node = BTreeMap::new();
67 let mut node_to_pos = vec![TopologicalPosition::default(); graph.node_bound()];
68
69 for (i, &id) in topo_vec.iter().enumerate() {
71 let pos = TopologicalPosition(i);
72 pos_to_node.insert(pos, id);
73 node_to_pos[graph.to_index(id)] = pos;
74 }
75
76 Ok(Self {
77 pos_to_node,
78 node_to_pos,
79 })
80 }
81
82 pub(super) fn with_capacity(nodes: usize) -> Self {
83 Self {
84 pos_to_node: BTreeMap::new(),
85 node_to_pos: Vec::with_capacity(nodes),
86 }
87 }
88
89 #[track_caller]
93 pub(super) fn get_position(
94 &self,
95 id: N,
96 graph: impl NodeIndexable<NodeId = N>,
97 ) -> TopologicalPosition {
98 let idx = graph.to_index(id);
99 assert!(idx < self.node_to_pos.len());
100 self.node_to_pos[idx]
101 }
102
103 pub(super) fn at_position(&self, pos: TopologicalPosition) -> Option<N> {
105 self.pos_to_node.get(&pos).copied()
106 }
107
108 pub(super) fn nodes_iter(&self) -> impl Iterator<Item = N> + '_ {
110 self.pos_to_node.values().copied()
111 }
112
113 pub(super) fn range(
115 &self,
116 range: impl RangeBounds<TopologicalPosition>,
117 ) -> impl Iterator<Item = N> + '_ {
118 self.pos_to_node.range(range).map(|(_, &n)| n)
119 }
120
121 pub(super) fn add_node(
125 &mut self,
126 id: N,
127 graph: impl NodeIndexable<NodeId = N>,
128 ) -> TopologicalPosition {
129 let new_pos = self
131 .pos_to_node
132 .iter()
133 .next_back()
134 .map(|(TopologicalPosition(idx), _)| TopologicalPosition(idx + 1))
135 .unwrap_or_default();
136 let idx = graph.to_index(id);
137
138 if idx >= self.node_to_pos.len() {
140 self.node_to_pos
141 .resize(graph.node_bound(), TopologicalPosition::default());
142 }
143
144 self.pos_to_node.insert(new_pos, id);
146 self.node_to_pos[idx] = new_pos;
147
148 new_pos
149 }
150
151 #[track_caller]
155 pub(super) fn remove_node(&mut self, id: N, graph: impl NodeIndexable<NodeId = N>) {
156 let idx = graph.to_index(id);
157 assert!(idx < self.node_to_pos.len());
158
159 let pos = self.node_to_pos[idx];
160 self.node_to_pos[idx] = TopologicalPosition::default();
161 self.pos_to_node.remove(&pos);
162 }
163
164 #[track_caller]
168 pub(super) fn set_position(
169 &mut self,
170 id: N,
171 pos: TopologicalPosition,
172 graph: impl NodeIndexable<NodeId = N>,
173 ) {
174 let idx = graph.to_index(id);
175 assert!(idx < self.node_to_pos.len());
176
177 self.pos_to_node.insert(pos, id);
178 self.node_to_pos[idx] = pos;
179 }
180}
181
182impl<G: Visitable> super::Acyclic<G> {
183 #[track_caller]
187 pub fn get_position<'a>(&'a self, id: G::NodeId) -> TopologicalPosition
188 where
189 &'a G: NodeIndexable + GraphBase<NodeId = G::NodeId>,
190 {
191 self.order_map.get_position(id, &self.graph)
192 }
193
194 pub fn at_position(&self, pos: TopologicalPosition) -> Option<G::NodeId> {
196 self.order_map.at_position(pos)
197 }
198}