struct Node<T, A>{
value: T,
first_child: Option<Box<Node<T, A>>>,
next_sibling: Option<Box<Node<T, A>>>,
lazy: A::Act,
}Fields§
§value: T§first_child: Option<Box<Node<T, A>>>§next_sibling: Option<Box<Node<T, A>>>§lazy: A::ActImplementations§
Source§impl<T, A> Node<T, A>
impl<T, A> Node<T, A>
Sourcefn apply(&mut self, act: &A::Act)
fn apply(&mut self, act: &A::Act)
Examples found in repository?
crates/competitive/src/data_structure/pairing_heap.rs (line 43)
39 fn propagate(&mut self) {
40 if !<A::ActMonoid as Unital>::is_unit(&self.lazy) {
41 let act = replace(&mut self.lazy, A::unit());
42 if let Some(node) = self.first_child.as_mut() {
43 node.apply(&act);
44 }
45 if let Some(node) = self.next_sibling.as_mut() {
46 node.apply(&act);
47 }
48 }
49 }
50}
51
52impl<T, A> Debug for Node<T, A>
53where
54 T: Debug,
55 A: MonoidAct<Key = T, Act: PartialEq + Debug>,
56{
57 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
58 f.debug_struct("Node")
59 .field("value", &self.value)
60 .field("first_child", &self.first_child)
61 .field("next_sibling", &self.next_sibling)
62 .field("lazy", &self.lazy)
63 .finish()
64 }
65}
66
67#[derive(Clone)]
68pub struct PairingHeap<T, C = Less, A = EmptyAct<T>>
69where
70 A: MonoidAct<Key = T, Act: PartialEq>,
71{
72 root: Option<Box<Node<T, A>>>,
73 len: usize,
74 cmp: C,
75}
76
77impl<T, C, A> PairingHeap<T, C, A>
78where
79 C: Comparator<T>,
80 A: MonoidAct<Key = T, Act: PartialEq>,
81{
82 pub fn with_comparator(cmp: C) -> Self {
83 Self {
84 root: None,
85 len: 0,
86 cmp,
87 }
88 }
89
90 pub fn len(&self) -> usize {
91 self.len
92 }
93
94 pub fn is_empty(&self) -> bool {
95 self.len == 0
96 }
97
98 pub fn peek(&self) -> Option<&T> {
99 self.root.as_ref().map(|node| &node.value)
100 }
101
102 pub fn push(&mut self, value: T) {
103 let node = Box::new(Node::new(value));
104 let root = self.root.take();
105 self.root = self.merge_option(root, Some(node));
106 self.len += 1;
107 }
108
109 pub fn append(&mut self, other: &mut Self) {
110 if other.is_empty() {
111 return;
112 }
113
114 let left = self.root.take();
115 self.root = self.merge_option(left, other.root.take());
116 self.len += other.len;
117 other.len = 0;
118 }
119
120 pub fn pop(&mut self) -> Option<T> {
121 self.root.take().map(|mut root| {
122 self.len -= 1;
123 root.propagate();
124 let children = root.first_child.take();
125 self.root = self.merge_pairs(children);
126 root.value
127 })
128 }
129
130 pub fn peek_mut(&mut self) -> Option<PeekMut<'_, T, C, A>> {
131 let mut root = self.root.take()?;
132 root.propagate();
133 let children = root.first_child.take();
134 debug_assert!(root.next_sibling.is_none());
135 root.next_sibling = None;
136 self.root = self.merge_pairs(children);
137 Some(PeekMut {
138 heap: self,
139 node: Some(root),
140 })
141 }
142
143 pub fn clear(&mut self) {
144 self.root = None;
145 self.len = 0;
146 }
147
148 pub fn apply_all(&mut self, act: A::Act) {
149 if let Some(root) = self.root.as_mut() {
150 root.apply(&act);
151 }
152 }Sourcefn propagate(&mut self)
fn propagate(&mut self)
Examples found in repository?
crates/competitive/src/data_structure/pairing_heap.rs (line 123)
120 pub fn pop(&mut self) -> Option<T> {
121 self.root.take().map(|mut root| {
122 self.len -= 1;
123 root.propagate();
124 let children = root.first_child.take();
125 self.root = self.merge_pairs(children);
126 root.value
127 })
128 }
129
130 pub fn peek_mut(&mut self) -> Option<PeekMut<'_, T, C, A>> {
131 let mut root = self.root.take()?;
132 root.propagate();
133 let children = root.first_child.take();
134 debug_assert!(root.next_sibling.is_none());
135 root.next_sibling = None;
136 self.root = self.merge_pairs(children);
137 Some(PeekMut {
138 heap: self,
139 node: Some(root),
140 })
141 }
142
143 pub fn clear(&mut self) {
144 self.root = None;
145 self.len = 0;
146 }
147
148 pub fn apply_all(&mut self, act: A::Act) {
149 if let Some(root) = self.root.as_mut() {
150 root.apply(&act);
151 }
152 }
153
154 pub fn into_sorted_vec(mut self) -> Vec<T> {
155 let mut result = Vec::with_capacity(self.len);
156 while let Some(value) = self.pop() {
157 result.push(value);
158 }
159 result
160 }
161
162 fn merge_option(
163 &mut self,
164 a: Option<Box<Node<T, A>>>,
165 b: Option<Box<Node<T, A>>>,
166 ) -> Option<Box<Node<T, A>>> {
167 match (a, b) {
168 (None, None) => None,
169 (Some(node), None) | (None, Some(node)) => Some(node),
170 (Some(mut a), Some(mut b)) => {
171 a.propagate();
172 b.propagate();
173 if self.cmp.compare(&a.value, &b.value) == Ordering::Greater {
174 swap(&mut a, &mut b);
175 }
176 b.next_sibling = a.first_child.take();
177 a.first_child = Some(b);
178 Some(a)
179 }
180 }
181 }
182
183 fn merge_pairs(&mut self, mut head: Option<Box<Node<T, A>>>) -> Option<Box<Node<T, A>>> {
184 let mut pairs: Vec<Box<Node<T, A>>> = Vec::new();
185 while let Some(mut first) = head {
186 first.propagate();
187 let next = first.next_sibling.take();
188 if let Some(mut second) = next {
189 second.propagate();
190 head = second.next_sibling.take();
191 pairs.push(self.merge_option(Some(first), Some(second)).unwrap());
192 } else {
193 pairs.push(first);
194 break;
195 }
196 }
197
198 let mut result = None;
199 while let Some(node) = pairs.pop() {
200 result = self.merge_option(Some(node), result);
201 }
202 result
203 }Trait Implementations§
Auto Trait Implementations§
impl<T, A> Freeze for Node<T, A>
impl<T, A> RefUnwindSafe for Node<T, A>
impl<T, A> Send for Node<T, A>
impl<T, A> Sync for Node<T, A>
impl<T, A> Unpin for Node<T, A>
impl<T, A> UnwindSafe for Node<T, A>
Blanket Implementations§
Source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere
T: ?Sized,
Source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
Mutably borrows from an owned value. Read more