streaming_algorithms/
ordered_linked_list.rs1use serde::{Deserialize, Serialize};
2use std::{ops, ptr};
3
4use crate::linked_list::{LinkedList, LinkedListIndex};
5
6#[derive(Copy, Clone, PartialEq, Eq, Serialize, Deserialize, Debug)]
7pub struct OrderedLinkedListIndex<'a>(LinkedListIndex<'a>);
8impl<'a> OrderedLinkedListIndex<'a> {
9 #[inline(always)]
10 pub unsafe fn staticify(self) -> OrderedLinkedListIndex<'static> {
11 OrderedLinkedListIndex(self.0.staticify())
12 }
13}
14
15#[derive(Clone, Serialize, Deserialize)]
16pub struct OrderedLinkedList<T>(LinkedList<T>);
17impl<T: Ord> OrderedLinkedList<T> {
18 pub fn new(cap: usize) -> Self {
19 Self(LinkedList::new(cap))
20 }
21 fn assert(&self) {
22 if !cfg!(feature = "assert") {
23 return;
24 }
25 if self.0.len() <= 1 {
26 return;
27 }
28 let mut idx = self.0.head().unwrap();
29 let mut cur = &self.0[idx];
30 let mut count = 0;
31 loop {
32 let x = &self.0[idx];
33 assert!(cur >= x);
34 cur = x;
35 count += 1;
36 if idx == self.0.tail().unwrap() {
37 break;
38 }
39 self.0.increment(&mut idx);
40 }
41 assert_eq!(count, self.0.len());
42 }
43 #[inline(always)]
44 pub fn head(&self) -> Option<OrderedLinkedListIndex> {
45 self.0.head().map(OrderedLinkedListIndex)
46 }
47 #[inline(always)]
48 pub fn tail(&self) -> Option<OrderedLinkedListIndex> {
49 self.0.tail().map(OrderedLinkedListIndex)
50 }
51 #[inline(always)]
52 pub fn len(&self) -> usize {
53 self.0.len()
54 }
55 #[inline(always)]
56 pub fn capacity(&self) -> usize {
57 self.0.capacity()
58 }
59 pub fn push_back(&mut self, t: T) -> OrderedLinkedListIndex {
60 if self.0.len() == 0 {
61 return OrderedLinkedListIndex(self.0.push_back(t));
62 }
63 let mut idx = unsafe { self.0.tail().unwrap().staticify() };
64 while self.0[idx] < t {
65 if idx == self.0.head().unwrap() {
66 let ret =
67 OrderedLinkedListIndex(unsafe { self.0.insert_before(idx, t).staticify() });
68 self.assert();
69 return ret;
70 }
71 self.0.decrement(&mut idx);
72 }
73 let ret = OrderedLinkedListIndex(unsafe { self.0.insert_after(idx, t).staticify() });
74 self.assert();
75 ret
76 }
77 pub fn push_front(&mut self, t: T) -> OrderedLinkedListIndex {
78 if self.0.len() == 0 {
79 return OrderedLinkedListIndex(self.0.push_front(t));
80 }
81 let mut idx = unsafe { self.0.head().unwrap().staticify() };
82 while self.0[idx] > t {
83 if idx == self.0.tail().unwrap() {
84 let ret =
85 OrderedLinkedListIndex(unsafe { self.0.insert_after(idx, t).staticify() });
86 self.assert();
87 return ret;
88 }
89 self.0.increment(&mut idx);
90 }
91 let ret = OrderedLinkedListIndex(unsafe { self.0.insert_before(idx, t).staticify() });
92 self.assert();
93 ret
94 }
95 pub fn mutate(&mut self, index: OrderedLinkedListIndex, f: impl FnOnce(T) -> T) {
96 let idx = index.0;
97 let x = &mut self.0[idx];
98 unsafe { ptr::write(x, f(ptr::read(x))) };
99 {
100 let val = &self.0[idx];
101 let mut prev = idx;
102 if prev != self.0.head().unwrap() {
103 self.0.decrement(&mut prev);
104 }
105 if val > &self.0[prev] {
106 while val > &self.0[prev] {
107 if prev == self.0.head().unwrap() {
108 self.0.move_before(idx, prev);
109 self.assert();
110 return;
111 }
112 self.0.decrement(&mut prev);
113 }
114 self.0.move_after(idx, prev);
115 }
116 }
117 {
118 let val = &self.0[idx];
119 let mut next = idx;
120 if next != self.0.tail().unwrap() {
121 self.0.increment(&mut next);
122 }
123 if val < &self.0[next] {
124 while val < &self.0[next] {
125 if next == self.0.tail().unwrap() {
126 self.0.move_after(idx, next);
127 self.assert();
128 return;
129 }
130 self.0.increment(&mut next);
131 }
132 self.0.move_before(idx, next);
133 }
134 }
135 self.assert();
136 }
137 #[inline(always)]
138 pub fn pop_back(&mut self) -> T {
139 self.0.pop_back()
140 }
141 #[inline(always)]
142 pub fn pop_front(&mut self) -> T {
143 self.0.pop_front()
144 }
145 pub fn insert_after(
146 &mut self, _index: OrderedLinkedListIndex, _t: T,
147 ) -> OrderedLinkedListIndex {
148 unimplemented!()
149 }
150 pub fn insert_before(
151 &mut self, _index: OrderedLinkedListIndex, _t: T,
152 ) -> OrderedLinkedListIndex {
153 unimplemented!()
154 }
155 #[inline(always)]
156 pub fn remove(&mut self, index: OrderedLinkedListIndex) -> T {
157 self.0.remove(index.0)
158 }
159 pub fn move_after(&mut self, _from: OrderedLinkedListIndex, _to: OrderedLinkedListIndex) {
160 unimplemented!()
161 }
162 pub fn move_before(&mut self, _from: OrderedLinkedListIndex, _to: OrderedLinkedListIndex) {
163 unimplemented!()
164 }
165 #[inline(always)]
166 pub fn increment(&self, index: &mut OrderedLinkedListIndex) {
167 self.0.increment(&mut index.0)
168 }
169 #[inline(always)]
170 pub fn decrement(&self, index: &mut OrderedLinkedListIndex) {
171 self.0.decrement(&mut index.0)
172 }
173 pub fn clear(&mut self) {
174 self.0.clear()
175 }
176 pub fn iter(&self) -> OrderedLinkedListIter<'_, T> {
177 OrderedLinkedListIter {
178 linked_list: self,
179 index: self.head(),
180 }
181 }
182}
183impl<'a, T: Ord> ops::Index<OrderedLinkedListIndex<'a>> for OrderedLinkedList<T> {
184 type Output = T;
185 #[inline(always)]
186 fn index(&self, index: OrderedLinkedListIndex) -> &T {
187 &self.0[index.0]
188 }
189}
190
191pub struct OrderedLinkedListIter<'a, T: Ord + 'a> {
192 linked_list: &'a OrderedLinkedList<T>,
193 index: Option<OrderedLinkedListIndex<'a>>,
194}
195impl<'a, T: Ord> Iterator for OrderedLinkedListIter<'a, T> {
196 type Item = &'a T;
197 fn next(&mut self) -> Option<&'a T> {
198 if let Some(index) = self.index {
199 if index != self.linked_list.tail().unwrap() {
200 self.linked_list.increment(self.index.as_mut().unwrap());
201 } else {
202 self.index = None;
203 }
204 Some(&self.linked_list[index])
205 } else {
206 None
207 }
208 }
209}
210impl<'a, T: Ord> Clone for OrderedLinkedListIter<'a, T> {
211 fn clone(&self) -> Self {
212 Self {
213 linked_list: self.linked_list,
214 index: self.index,
215 }
216 }
217}