algorithms_edu/data_structures/
vector.rs

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

algorithms_edu/data_structures/
vector.rs
