algorithms_edu/data_structures/
vector_int.rs

1//! A simple but working implementation of integer vector.
2
3use std::alloc::{alloc, dealloc, realloc, Layout};
4
5const DEFAULT_CAPACITY: usize = 4;
6
7pub struct IntVector {
8    ptr: *mut i32,
9    len: usize,
10    capacity: usize,
11}
12
13impl Default for IntVector {
14    fn default() -> Self {
15        let ptr = unsafe {
16            let layout = Self::layout(DEFAULT_CAPACITY);
17            alloc(layout) as *mut i32
18        };
19        Self {
20            ptr,
21            len: 0,
22            capacity: DEFAULT_CAPACITY,
23        }
24    }
25}
26
27impl IntVector {
28    pub fn new() -> Self {
29        Default::default()
30    }
31    pub fn push(&mut self, v: i32) {
32        unsafe {
33            *self.ptr.add(self.len) = v;
34            self.len += 1;
35            if self.len == self.capacity {
36                self.ptr = realloc(
37                    self.ptr as *mut u8,
38                    Self::layout(self.capacity),
39                    self.capacity * 2,
40                ) as *mut i32;
41                self.capacity *= 2;
42            }
43        }
44    }
45    pub fn get(&self, idx: usize) -> Option<&i32> {
46        if idx < self.len {
47            unsafe { Some(&*(self.ptr.add(idx))) }
48        } else {
49            None
50        }
51    }
52    pub fn get_mut(&self, idx: usize) -> Option<&mut i32> {
53        if idx < self.len {
54            unsafe { Some(&mut *(self.ptr.add(idx))) }
55        } else {
56            None
57        }
58    }
59    pub fn pop(&mut self) -> Option<i32> {
60        if self.is_empty() {
61            None
62        } else {
63            self.len -= 1;
64            unsafe { Some(std::ptr::read(self.ptr.add(self.len))) }
65        }
66    }
67    pub fn len(&self) -> usize {
68        self.len
69    }
70    pub fn is_empty(&self) -> bool {
71        self.len() == 0
72    }
73    pub fn capacity(&self) -> usize {
74        self.capacity
75    }
76    unsafe fn layout(size: usize) -> Layout {
77        Layout::from_size_align_unchecked(size, 4)
78    }
79}
80
81impl Drop for IntVector {
82    fn drop(&mut self) {
83        unsafe { dealloc(self.ptr as *mut u8, Self::layout(self.capacity)) };
84    }
85}
86
87impl std::ops::Index<usize> for IntVector {
88    type Output = i32;
89    fn index(&self, index: usize) -> &Self::Output {
90        self.get(index).unwrap()
91    }
92}
93impl std::ops::IndexMut<usize> for IntVector {
94    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
95        self.get_mut(index).unwrap()
96    }
97}
98
99#[cfg(test)]
100mod tests {
101    use super::*;
102    #[test]
103    fn test_vector_int() {
104        let mut v = IntVector::new();
105        assert_eq!(v.len(), 0);
106        assert_eq!(v.capacity(), DEFAULT_CAPACITY);
107        v.push(1);
108        assert_eq!(v.len(), 1);
109        assert_eq!(v.capacity(), DEFAULT_CAPACITY);
110        assert_eq!(v[0], 1);
111        v.push(2);
112        v.push(3);
113        v.push(4);
114        v.push(5);
115        v[4] = 100;
116        assert_eq!(v.len(), 5);
117        assert_eq!(v.capacity(), DEFAULT_CAPACITY * 2);
118        assert_eq!(v[4], 100);
119        let x = v.pop();
120        assert_eq!(x, Some(100));
121        assert_eq!(v.len(), 4);
122    }
123}
algorithms_edu/data_structures/vector_int.rs

algorithms_edu/data_structures/
vector_int.rs
