1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

//! A simple but working implementation of integer vector.

use std::alloc::{alloc, dealloc, realloc, Layout};

const DEFAULT_CAPACITY: usize = 4;

pub struct IntVector {
    ptr: *mut i32,
    len: usize,
    capacity: usize,
}

impl Default for IntVector {
    fn default() -> Self {
        let ptr = unsafe {
            let layout = Self::layout(DEFAULT_CAPACITY);
            alloc(layout) as *mut i32
        };
        Self {
            ptr,
            len: 0,
            capacity: DEFAULT_CAPACITY,
        }
    }
}

impl IntVector {
    pub fn new() -> Self {
        Default::default()
    }
    pub fn push(&mut self, v: i32) {
        unsafe {
            *self.ptr.add(self.len) = v;
            self.len += 1;
            if self.len == self.capacity {
                self.ptr = realloc(
                    self.ptr as *mut u8,
                    Self::layout(self.capacity),
                    self.capacity * 2,
                ) as *mut i32;
                self.capacity *= 2;
            }
        }
    }
    pub fn get(&self, idx: usize) -> Option<&i32> {
        if idx < self.len {
            unsafe { Some(&*(self.ptr.add(idx))) }
        } else {
            None
        }
    }
    pub fn get_mut(&self, idx: usize) -> Option<&mut i32> {
        if idx < self.len {
            unsafe { Some(&mut *(self.ptr.add(idx))) }
        } else {
            None
        }
    }
    pub fn pop(&mut self) -> Option<i32> {
        if self.is_empty() {
            None
        } else {
            self.len -= 1;
            unsafe { Some(std::ptr::read(self.ptr.add(self.len))) }
        }
    }
    pub fn len(&self) -> usize {
        self.len
    }
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }
    pub fn capacity(&self) -> usize {
        self.capacity
    }
    unsafe fn layout(size: usize) -> Layout {
        Layout::from_size_align_unchecked(size, 4)
    }
}

impl Drop for IntVector {
    fn drop(&mut self) {
        unsafe { dealloc(self.ptr as *mut u8, Self::layout(self.capacity)) };
    }
}

impl std::ops::Index<usize> for IntVector {
    type Output = i32;
    fn index(&self, index: usize) -> &Self::Output {
        self.get(index).unwrap()
    }
}
impl std::ops::IndexMut<usize> for IntVector {
    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
        self.get_mut(index).unwrap()
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_vector_int() {
        let mut v = IntVector::new();
        assert_eq!(v.len(), 0);
        assert_eq!(v.capacity(), DEFAULT_CAPACITY);
        v.push(1);
        assert_eq!(v.len(), 1);
        assert_eq!(v.capacity(), DEFAULT_CAPACITY);
        assert_eq!(v[0], 1);
        v.push(2);
        v.push(3);
        v.push(4);
        v.push(5);
        v[4] = 100;
        assert_eq!(v.len(), 5);
        assert_eq!(v.capacity(), DEFAULT_CAPACITY * 2);
        assert_eq!(v[4], 100);
        let x = v.pop();
        assert_eq!(x, Some(100));
        assert_eq!(v.len(), 4);
    }
}