algorithm/arr/
fix_vec.rs

1use std::cmp::Ordering;
2
3#[derive(Debug)]
4struct FixedVecNode<T> {
5    prev: usize,
6    next: usize,
7    data: T,
8}
9
10/// 指定位置的序列, 每个位置上指向上向的位置, 相当于模拟指针
11/// 可以根据坐标位置获取相应数据, 亦可以操作上级及下级位置
12/// 
13/// # Examples
14///
15/// ```
16/// use algorithm::FixedVec;
17/// fn main() {
18///     let mut val = FixedVec::new(2);
19///     val.insert_head(1);
20///     val.insert_head(2);
21///     assert_eq!(val.len(), 2);
22///     assert_eq!(val.head(), Some(&2));
23///     assert_eq!(val.tail(), Some(&1));
24///     assert_eq!(val.insert_head(3), None);
25/// }
26/// ```
27#[derive(Debug)]
28pub struct FixedVec<T> {
29    capacity: usize,
30    nodes: Vec<Option<FixedVecNode<T>>>,
31    // 存储空闲位置, 用O(1)的时间复杂度取出空闲位置
32    free: Vec<usize>,
33    head: usize,
34    tail: usize,
35}
36
37impl<T> FixedVec<T> {
38    #[inline]
39    pub fn new(capacity: usize) -> Self {
40        Self {
41            capacity,
42            nodes: Vec::new(),
43            free: Vec::new(),
44            head: usize::MAX,
45            tail: usize::MAX,
46        }
47    }
48
49    #[inline]
50    pub fn with_memory(capacity: usize, mut reserve: usize) -> Self {
51        reserve = reserve.min(capacity);
52        Self {
53            capacity,
54            nodes: Vec::with_capacity(reserve),
55            free: Vec::new(),
56            head: usize::MAX,
57            tail: usize::MAX,
58        }
59    }
60
61    /// 获取容量
62    #[inline]
63    pub fn capacity(&self) -> usize {
64        self.capacity
65    }
66
67    /// 返回长度
68    #[inline]
69    pub fn len(&self) -> usize {
70        self.nodes.len() - self.free.len()
71    }
72
73    #[inline]
74    pub fn is_empty(&self) -> bool {
75        self.len() == 0
76    }
77
78    #[inline]
79    pub fn is_full(&self) -> bool {
80        self.len() == self.capacity()
81    }
82
83    /// 清除数据
84    /// # Examples
85    ///
86    /// ```
87    /// use algorithm::FixedVec;
88    /// fn main() {
89    ///     let mut val = FixedVec::new(2);
90    ///     val.insert_head(1);
91    ///     assert_eq!(val.len(), 1);
92    ///     val.clear();
93    ///     assert_eq!(val.len(), 0);
94    /// }
95    /// ```
96    pub fn clear(&mut self) {
97        self.nodes.clear();
98        self.free.clear();
99        self.head = usize::MAX;
100        self.tail = usize::MAX;
101    }
102
103    fn next(&mut self) -> Option<usize> {
104        if self.is_full() {
105            None
106        } else if self.free.is_empty() {
107            let len = self.len();
108            self.nodes.push(None);
109            Some(len)
110        } else {
111            self.free.pop()
112        }
113    }
114
115    #[inline]
116    fn node_ref(&self, idx: usize) -> Option<&FixedVecNode<T>> {
117        self.nodes.get(idx).and_then(|node| node.as_ref())
118    }
119
120    #[inline]
121    pub fn get(&self, idx: usize) -> Option<&T> {
122        self.node_ref(idx).map(|node| &node.data)
123    }
124
125    #[inline]
126    fn node_mut(&mut self, idx: usize) -> Option<&mut FixedVecNode<T>> {
127        self.nodes.get_mut(idx).and_then(|node| node.as_mut())
128    }
129
130    #[inline]
131    pub fn get_mut(&mut self, idx: usize) -> Option<&mut T> {
132        self.node_mut(idx).map(|node| &mut node.data)
133    }
134    /// 获取头部的坐标位置
135    /// 
136    /// # Examples
137    ///
138    /// ```
139    /// use algorithm::FixedVec;
140    /// fn main() {
141    ///     let mut val = FixedVec::new(2);
142    ///     val.insert_tail(1);
143    ///     assert_eq!(val.head_idx(), 0);
144    /// }
145    /// ```
146    #[inline]
147    pub fn head_idx(&self) -> usize {
148        self.head
149    }
150    /// 获取头部首位数据
151    /// 
152    /// # Examples
153    ///
154    /// ```
155    /// use algorithm::FixedVec;
156    /// fn main() {
157    ///     let mut val = FixedVec::new(2);
158    ///     val.insert_tail(1);
159    ///     assert_eq!(val.head(), Some(&1));
160    /// }
161    /// ```
162    #[inline]
163    pub fn head(&self) -> Option<&T> {
164        self.node_ref(self.head).map(|node| &node.data)
165    }
166
167    /// 获取头部首位可变数据
168    /// 
169    /// # Examples
170    ///
171    /// ```
172    /// use algorithm::FixedVec;
173    /// fn main() {
174    ///     let mut val = FixedVec::new(2);
175    ///     val.insert_tail(1);
176    ///     assert_eq!(val.head_mut(), Some(&mut 1));
177    /// }
178    /// ```
179    #[inline]
180    pub fn head_mut(&mut self) -> Option<&mut T> {
181        self.node_mut(self.head).map(|node| &mut node.data)
182    }
183
184    /// 获取尾部的坐标位置
185    /// 
186    /// # Examples
187    ///
188    /// ```
189    /// use algorithm::FixedVec;
190    /// fn main() {
191    ///     let mut val = FixedVec::new(2);
192    ///     val.insert_tail(1);
193    ///     assert_eq!(val.tail_idx(), 0);
194    /// }
195    /// ```
196    #[inline]
197    pub fn tail_idx(&self) -> usize {
198        self.tail
199    }
200
201    /// 获取尾部首位数据
202    /// 
203    /// # Examples
204    ///
205    /// ```
206    /// use algorithm::FixedVec;
207    /// fn main() {
208    ///     let mut val = FixedVec::new(2);
209    ///     val.insert_head(1);
210    ///     assert_eq!(val.tail(), Some(&1));
211    /// }
212    /// ```
213    #[inline]
214    pub fn tail(&self) -> Option<&T> {
215        self.node_ref(self.tail).map(|node| &node.data)
216    }
217
218    /// 获取尾部首位可变数据
219    /// 
220    /// # Examples
221    ///
222    /// ```
223    /// use algorithm::FixedVec;
224    /// fn main() {
225    ///     let mut val = FixedVec::new(2);
226    ///     val.insert_head(1);
227    ///     assert_eq!(val.tail_mut(), Some(&mut 1));
228    /// }
229    /// ```
230    #[inline]
231    pub fn tail_mut(&mut self) -> Option<&mut T> {
232        self.node_mut(self.tail).map(|node| &mut node.data)
233    }
234
235    /// 从头部插入新的数据
236    /// 
237    /// # Examples
238    ///
239    /// ```
240    /// use algorithm::FixedVec;
241    /// fn main() {
242    ///     let mut val = FixedVec::new(2);
243    ///     assert_eq!(val.insert_head(1), Some((0, &mut 1)));
244    ///     assert_eq!(val.insert_head(2), Some((1, &mut 2)));
245    ///     assert_eq!(val.insert_head(3), None);
246    /// }
247    /// ```
248    pub fn insert_head(&mut self, data: T) -> Option<(usize, &mut T)> {
249        let idx = self.next()?;
250        if let Some(head) = self.node_mut(self.head) {
251            head.prev = idx;
252        }
253        if self.node_ref(self.tail).is_none() {
254            self.tail = idx;
255        }
256        let node = self.nodes.get_mut(idx).unwrap().insert(FixedVecNode {
257            prev: usize::MAX,
258            next: self.head,
259            data,
260        });
261        self.head = idx;
262        Some((idx, &mut node.data))
263    }
264    /// 从头部插入新的数据
265    /// 
266    /// # Examples
267    ///
268    /// ```
269    /// use algorithm::FixedVec;
270    /// fn main() {
271    ///     let mut val = FixedVec::new(2);
272    ///     assert_eq!(val.insert_tail(1), Some((0, &mut 1)));
273    ///     assert_eq!(val.insert_tail(2), Some((1, &mut 2)));
274    ///     assert_eq!(val.insert_tail(3), None);
275    /// }
276    /// ```
277    pub fn insert_tail(&mut self, data: T) -> Option<(usize, &mut T)> {
278        let idx = self.next()?;
279        if let Some(tail) = self.node_mut(self.tail) {
280            tail.next = idx;
281        }
282        if self.node_ref(self.head).is_none() {
283            self.head = idx;
284        }
285        let node = self.nodes.get_mut(idx).unwrap().insert(FixedVecNode {
286            prev: self.tail,
287            next: usize::MAX,
288            data,
289        });
290        self.tail = idx;
291        Some((idx, &mut node.data))
292    }
293
294    /// 从头部弹出数据
295    /// 
296    /// # Examples
297    ///
298    /// ```
299    /// use algorithm::FixedVec;
300    /// fn main() {
301    ///     let mut val = FixedVec::new(2);
302    ///     val.insert_tail(1);
303    ///     val.insert_tail(2);
304    ///     assert_eq!(val.pop_head(), Some(1));
305    /// }
306    /// ```
307    #[inline]
308    pub fn pop_head(&mut self) -> Option<T> {
309        self.remove(self.head)
310    }
311    /// 从尾部弹出数据
312    /// 
313    /// # Examples
314    ///
315    /// ```
316    /// use algorithm::FixedVec;
317    /// fn main() {
318    ///     let mut val = FixedVec::new(2);
319    ///     val.insert_head(1);
320    ///     val.insert_head(2);
321    ///     assert_eq!(val.pop_tail(), Some(1));
322    /// }
323    /// ```
324    #[inline]
325    pub fn pop_tail(&mut self) -> Option<T> {
326        self.remove(self.tail)
327    }
328
329    /// 删除指定位置数据
330    /// 
331    /// # Examples
332    ///
333    /// ```
334    /// use algorithm::FixedVec;
335    /// fn main() {
336    ///     let mut val = FixedVec::new(2);
337    ///     val.insert_head(1);
338    ///     val.insert_head(2);
339    ///     assert_eq!(val.remove(1), Some(2));
340    ///     assert_eq!(val.len(), 1);
341    ///     assert_eq!(val.tail_idx(), 0);
342    /// }
343    /// ```
344    pub fn remove(&mut self, idx: usize) -> Option<T> {
345        let node = self.nodes.get_mut(idx)?.take()?;
346        if let Some(prev) = self.node_mut(node.prev) {
347            prev.next = node.next;
348        } else {
349            self.head = node.next;
350        }
351        if let Some(next) = self.node_mut(node.next) {
352            next.prev = node.prev;
353        } else {
354            self.tail = node.prev;
355        }
356        self.free.push(idx);
357        Some(node.data)
358    }
359
360    
361    /// 迭代器
362    /// 
363    /// # Examples
364    ///
365    /// ```
366    /// use algorithm::FixedVec;
367    /// fn main() {
368    ///     let mut val = FixedVec::new(5);
369    ///     val.insert_head(1);
370    ///     val.insert_head(2);
371    ///     val.insert_head(3);
372    ///     assert_eq!(val.iter().map(|(_, v)| *v).collect::<Vec<_>>(), vec![3, 2, 1]);
373    /// }
374    /// ```
375    #[inline]
376    pub fn iter(&self) -> FixedVecIter<'_, T> {
377        FixedVecIter {
378            list: self,
379            head: self.head,
380            tail: self.tail,
381            len: self.len(),
382        }
383    }
384
385    /// 迭代器
386    /// 
387    /// # Examples
388    ///
389    /// ```
390    /// use algorithm::FixedVec;
391    /// fn main() {
392    ///     let mut val = FixedVec::new(5);
393    ///     val.insert_head(1);
394    ///     val.insert_head(2);
395    ///     val.insert_head(3);
396    ///     let _ = val.iter_mut().map(|(_, v)| *v = *v * 2).collect::<Vec<_>>();
397    ///     assert_eq!(val.iter().map(|(_, v)| *v).collect::<Vec<_>>(), vec![6, 4, 2]);
398    /// }
399    /// ```
400    #[inline]
401    pub fn iter_mut(&mut self) -> FixedVecIterMut<'_, T> {
402        FixedVecIterMut {
403            head: self.head,
404            tail: self.tail,
405            len: self.len(),
406            list: self,
407        }
408        // let head = self.head;
409        // let tail = self.tail;
410        // let len = self.len();
411        // FixedVecIterMut::new(self, head, tail, len)
412    }
413
414    fn reorder(&mut self) {
415        if self.is_empty() {
416            return;
417        }
418
419        let len = self.len();
420        let mut current = 0;
421        while current < len {
422            let head = self.head;
423            let head_data = self.pop_head().unwrap();
424            if head != current {
425                debug_assert!(current < head, "{} < {}", current, head);
426                if let Some(current_node) = self.nodes[current].take() {
427                    if let Some(node) = self.node_mut(current_node.prev) {
428                        node.next = head;
429                    } else {
430                        self.head = head;
431                    }
432                    if let Some(node) = self.node_mut(current_node.next) {
433                        node.prev = head;
434                    } else {
435                        self.tail = head;
436                    }
437                    self.nodes[head] = Some(current_node);
438                }
439            }
440            self.nodes[current] = Some(FixedVecNode {
441                prev: current.wrapping_sub(1),
442                next: current + 1,
443                data: head_data,
444            });
445            current += 1;
446        }
447        self.head = 0;
448        self.nodes[len - 1].as_mut().unwrap().next = usize::MAX;
449        self.tail = len - 1;
450        self.free.clear();
451        self.free.extend((len..self.nodes.len()).rev());
452    }
453
454    
455    /// 重置设置大小
456    /// 
457    /// # Examples
458    ///
459    /// ```
460    /// use algorithm::FixedVec;
461    /// fn main() {
462    ///     let mut val = FixedVec::new(5);
463    ///     val.insert_head(1);
464    ///     val.insert_head(2);
465    ///     val.resize(3);
466    ///     assert_eq!(val.len(), 2);
467    ///     assert_eq!(val.head_idx(), 0);
468    ///     assert_eq!(val.tail_idx(), 1);
469    ///     assert_eq!(val.tail(), Some(&1));
470    /// }
471    /// ```
472    pub fn resize(&mut self, capacity: usize) {
473        let len = self.len();
474        let cap = self.capacity();
475        if capacity < len {
476            return;
477        }
478        match capacity.cmp(&cap) {
479            Ordering::Less => {
480                self.reorder();
481                self.nodes.truncate(capacity);
482                self.free.clear();
483                self.free.extend(len..self.nodes.len());
484                self.capacity = capacity;
485            }
486            Ordering::Equal => {}
487            Ordering::Greater => {
488                self.capacity = capacity;
489            }
490        };
491        debug_assert_eq!(self.len(), len);
492        debug_assert_eq!(self.capacity(), capacity);
493    }
494
495    pub fn retain<F>(&mut self, mut f: F)
496    where
497        F: FnMut(&T) -> bool,
498    {
499        let mut head = self.head;
500        while head != usize::MAX {
501            let node = self.node_ref(head).unwrap();
502            let next = node.next;
503            if !f(&node.data) {
504                self.remove(head);
505            }
506            head = next;
507        }
508    }
509
510    pub fn retain_mut<F>(&mut self, mut f: F)
511    where
512        F: FnMut(&mut T) -> bool,
513    {
514        let mut head = self.head;
515        while head != usize::MAX {
516            let node = self.node_mut(head).unwrap();
517            let next = node.next;
518            if !f(&mut node.data) {
519                self.remove(head);
520            }
521            head = next;
522        }
523    }
524
525    /// 将指定位置挪到最前面
526    /// 
527    /// # Examples
528    ///
529    /// ```
530    /// use algorithm::FixedVec;
531    /// fn main() {
532    ///     let mut val = FixedVec::new(5);
533    ///     val.insert_head(1);
534    ///     val.insert_head(2);
535    ///     val.insert_head(3);
536    ///     assert_eq!(val.get(1), Some(&2));
537    ///     assert_eq!(val.head(), Some(&3));
538    ///     val.move_head(1);
539    ///     assert_eq!(val.head(), Some(&2));
540    ///     assert_eq!(val.get(1), Some(&2));
541    ///     assert_eq!(val.tail(), Some(&1));
542    /// }
543    /// ```
544    #[inline]
545    pub fn move_head(&mut self, idx: usize) -> Option<&mut T> {
546        let node = self.nodes.get_mut(idx)?.take()?;
547        if let Some(prev) = self.node_mut(node.prev) {
548            prev.next = node.next;
549        } else {
550            self.head = node.next;
551        }
552        if let Some(next) = self.node_mut(node.next) {
553            next.prev = node.prev;
554        } else {
555            self.tail = node.prev;
556        }
557
558        if let Some(head) = self.node_mut(self.head) {
559            head.prev = idx;
560        }
561        if self.node_ref(self.tail).is_none() {
562            self.tail = idx;
563        }
564
565        let node = self.nodes.get_mut(idx).unwrap().insert(FixedVecNode {
566            prev: usize::MAX,
567            next: self.head,
568            data: node.data,
569        });
570        self.head = idx;
571        Some(&mut node.data)
572    }
573
574    
575    /// 将指定位置挪到最后面
576    /// 
577    /// # Examples
578    ///
579    /// ```
580    /// use algorithm::FixedVec;
581    /// fn main() {
582    ///     let mut val = FixedVec::new(5);
583    ///     val.insert_tail(1);
584    ///     val.insert_tail(2);
585    ///     val.insert_tail(3);
586    ///     assert_eq!(val.get(1), Some(&2));
587    ///     assert_eq!(val.tail(), Some(&3));
588    ///     val.move_tail(1);
589    ///     assert_eq!(val.tail(), Some(&2));
590    ///     assert_eq!(val.get(1), Some(&2));
591    ///     assert_eq!(val.head(), Some(&1));
592    /// }
593    /// ```
594    #[inline]
595    pub fn move_tail(&mut self, idx: usize) -> Option<&mut T> {
596        let node = self.nodes.get_mut(idx)?.take()?;
597        if let Some(prev) = self.node_mut(node.prev) {
598            prev.next = node.next;
599        } else {
600            self.head = node.next;
601        }
602        if let Some(next) = self.node_mut(node.next) {
603            next.prev = node.prev;
604        } else {
605            self.tail = node.prev;
606        }
607
608        if let Some(tail) = self.node_mut(self.tail) {
609            tail.next = idx;
610        }
611        if self.node_ref(self.head).is_none() {
612            self.head = idx;
613        }
614
615        let node = self.nodes.get_mut(idx).unwrap().insert(FixedVecNode {
616            prev: self.tail,
617            next: usize::MAX,
618            data: node.data,
619        });
620        self.tail = idx;
621        Some(&mut node.data)
622    }
623}
624
625#[derive(Debug)]
626pub struct FixedVecIter<'a, T> {
627    list: &'a FixedVec<T>,
628    head: usize,
629    tail: usize,
630    len: usize,
631}
632
633impl<'a, T> Clone for FixedVecIter<'a, T> {
634    fn clone(&self) -> Self {
635        Self {
636            list: self.list,
637            head: self.head,
638            tail: self.tail,
639            len: self.len,
640        }
641    }
642}
643
644impl<'a, T> Iterator for FixedVecIter<'a, T> {
645    type Item = (usize, &'a T);
646
647    fn next(&mut self) -> Option<Self::Item> {
648        if self.len > 0 {
649            let head = self.head;
650            let node = self.list.node_ref(head).unwrap();
651            self.head = node.next;
652            self.len -= 1;
653            Some((head, &node.data))
654        } else {
655            None
656        }
657    }
658
659    fn size_hint(&self) -> (usize, Option<usize>) {
660        (self.len, Some(self.len))
661    }
662}
663
664impl<'a, T> DoubleEndedIterator for FixedVecIter<'a, T> {
665    fn next_back(&mut self) -> Option<Self::Item> {
666        if self.len > 0 {
667            let tail = self.tail;
668            let node = self.list.node_ref(tail).unwrap();
669            self.tail = node.prev;
670            self.len -= 1;
671            Some((tail, &node.data))
672        } else {
673            None
674        }
675    }
676}
677
678#[derive(Debug)]
679pub struct FixedVecIterMut<'a, T> {
680    list: &'a mut FixedVec<T>,
681    head: usize,
682    tail: usize,
683    len: usize,
684}
685
686impl<'a, T> Iterator for FixedVecIterMut<'a, T> {
687    type Item = (usize, &'a mut T);
688
689    fn next(&mut self) -> Option<Self::Item> {
690        if self.len > 0 {
691            let head = self.head;
692            let node = unsafe {
693                core::mem::transmute::<&'_ mut FixedVecNode<T>, &'a mut FixedVecNode<T>>(self.list.node_mut(head).unwrap())   
694            };
695            self.head = node.next;
696            self.len -= 1;
697            Some((head, &mut node.data))
698        } else {
699            None
700        }
701    }
702
703    fn size_hint(&self) -> (usize, Option<usize>) {
704        (self.len, Some(self.len))
705    }
706}
707
708impl<'a, T> DoubleEndedIterator for FixedVecIterMut<'a, T> {
709    fn next_back(&mut self) -> Option<Self::Item> {
710        if self.len > 0 {
711            let tail = self.tail;
712            let node = unsafe {
713                core::mem::transmute::<&'_ mut FixedVecNode<T>, &'a mut FixedVecNode<T>>(self.list.node_mut(tail).unwrap())   
714            };
715            self.tail = node.prev;
716            self.len -= 1;
717            Some((tail, &mut node.data))
718        } else {
719            None
720        }
721    }
722}
algorithm/arr/fix_vec.rs

algorithm/arr/
fix_vec.rs
