use std::{mem, ptr};
use std::alloc::{Layout, alloc, dealloc};

/// Very simple resizable array. Doesn't call destructors or anything. Just
/// makes sure that the array is cleaned up when dropped, and allows the user
/// to ergonomically resize. Assumes that `size_of::<T>() != 0` (and checks this
/// in debug mode).
pub struct RawArray<T> {
    data: *mut T,
    count: usize,
}

impl<T> RawArray<T> {
    const SIZE: usize = mem::size_of::<T>();
    const ALIGNMENT: usize = mem::align_of::<T>();

    /// Constructs a new and empty (not allocated) array.
    pub fn new() -> Self {
        return Self{
            data: ptr::null_mut(),
            count: 0,
        }
    }

    /// Resizes the array. All existing elements are preserved (whether the
    /// contained bytes are bogus or not).
    pub fn resize(&mut self, new_count: usize) {
        if new_count > self.count {
            let new_data = Self::allocate(new_count);
            if !self.data.is_null() {
                unsafe {
                    ptr::copy_nonoverlapping(self.data, new_data, self.count);
                    Self::deallocate(self.data, self.count);
                }
            }

            self.data = new_data;
            self.count = new_count;
        } else if new_count < self.count {
            // `new_count < count` and `new_count >= 0`, so `data != null`.
            if new_count == 0 {
                Self::deallocate(self.data, self.count);
                self.data = ptr::null_mut();
                self.count = 0;
            } else {
                let new_data = Self::allocate(new_count);
                unsafe {
                    ptr::copy_nonoverlapping(self.data, new_data, new_count);
                    Self::deallocate(self.data, self.count);
                }
                self.data = new_data;
                self.count = new_count;
            }
        } // otherwise: equal
    }

    /// Retrieves mutable pointer to the value at the specified index. The
    /// returned `*mut T` may point to bogus uninitialized memory.
    pub fn get(&self, index: usize) -> *mut T {
        debug_assert!(index < self.count); // at least some safety, amirite?
        return unsafe{ self.data.add(index) };
    }

    /// Retrieves the base pointer of the array. Hence may be null, or may point
    /// to bogus uninitialized memory.
    pub fn data(&self) -> *mut T {
        return self.data;
    }

    /// Returns the capacity of the array.
    pub fn cap(&self) -> usize {
        return self.count;
    }

    fn allocate(count: usize) -> *mut T {
        debug_assert_ne!(Self::SIZE, 0);
        let size = count * Self::SIZE;
        unsafe {
            let layout = Layout::from_size_align_unchecked(size, Self::ALIGNMENT);
            let data = alloc(layout);
            return mem::transmute(data);
        }
    }

    fn deallocate(data: *mut T, count: usize) {
        let size = count * Self::SIZE;
        unsafe {
            let layout = Layout::from_size_align_unchecked(size, Self::ALIGNMENT);
            dealloc(mem::transmute(data), layout);
        }
    }
}

impl<T> Drop for RawArray<T> {
    fn drop(&mut self) {
        if !self.data.is_null() {
            Self::deallocate(self.data, self.count);
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn fill(array: &mut RawArray<usize>, count: usize) {
        for idx in 0..count {
            unsafe{ *array.get(idx) = idx }
        }
    }

    fn check(array: &RawArray<usize>, count: usize) {
        for idx in 0..count {
            assert_eq!(unsafe{ *array.get(idx) }, idx);
        }
    }

    #[test]
    fn drop_empty_array() {
        let array = RawArray::<u32>::new();
        assert_eq!(array.cap(), 0);
        assert_eq!(array.data(), ptr::null_mut());
    }

    #[test]
    fn increase_size() {
        const INIT_SIZE: usize = 16;
        const NUM_RESIZES: usize = 4;
        let mut array = RawArray::new();
        array.resize(INIT_SIZE);
        fill(&mut array, INIT_SIZE);

        for grow_idx in 0..NUM_RESIZES {
            let new_size = INIT_SIZE + grow_idx * 4;
            array.resize(new_size);
            assert_eq!(array.cap(), new_size);
        }

        check(&array, INIT_SIZE);
    }

    #[test]
    fn maintain_size() {
        const INIT_SIZE: usize = 16;
        const NUM_RESIZES :usize = 4;

        let mut array = RawArray::new();
        array.resize(INIT_SIZE);
        fill(&mut array, INIT_SIZE);
        for _idx in 0..NUM_RESIZES {
            array.resize(INIT_SIZE);
            assert_eq!(array.cap(), INIT_SIZE);
        }
        check(&array, INIT_SIZE);
    }

    #[test]
    fn decrease_size() {
        const INIT_SIZE: usize = 16;
        const FINAL_SIZE: usize = 8;

        let mut array = RawArray::new();
        array.resize(INIT_SIZE);
        fill(&mut array, INIT_SIZE);
        array.resize(FINAL_SIZE);
        check(&array, FINAL_SIZE);
    }

    #[test]
    fn increase_and_decrease_size() {
        let sizes = [12, 8, 6, 150, 128, 32, 16, 90, 4, 18, 27];
        let min_size = *sizes.iter().min().unwrap();
        let max_size = *sizes.iter().max().unwrap();

        let mut array = RawArray::new();
        array.resize(max_size);
        fill(&mut array, max_size);
        for size in sizes {
            array.resize(size);
            assert_eq!(array.cap(), size);
        }
        check(&array, min_size);
    }
}