use std::ptr::{self, NonNull};
use std::marker::PhantomData;
use std::ops::{Add};
use std::mem;

use std::alloc::{handle_alloc_error, AllocRef, Global, Layout};

pub struct RawTwoSidedVec<T> {
    middle: NonNull<T>,
    marker: PhantomData<T>,
    capacity: Capacity
}
impl<T> RawTwoSidedVec<T> {
    #[inline]
    pub fn new() -> Self {
        assert_ne!(mem::size_of::<T>(), 0, "Zero sized type!");
        RawTwoSidedVec {
            middle: NonNull::dangling(),
            marker: PhantomData,
            capacity: Capacity { back: 0, front: 0 }
        }
    }
    pub fn with_capacity(capacity: Capacity) -> Self {
        assert_ne!(mem::size_of::<T>(), 0, "Zero sized type!");
        if capacity.is_empty() {
            return RawTwoSidedVec::new()
        }
        let mut heap = Global::default();
        let layout = capacity.layout::<T>();
        unsafe {
            let (ptr, actual_capacity_bytes) = heap.alloc(layout)
                .unwrap_or_else(|_| handle_alloc_error(layout));
            let middle = (ptr.as_ptr() as *mut T).add(capacity.back);
            RawTwoSidedVec::from_raw_parts(
                middle,
                capacity.with_actual_capacity(actual_capacity_bytes / mem::size_of::<T>())
            )
        }
    }
    #[inline]
    pub unsafe fn from_raw_parts(middle: *mut T, capacity: Capacity) -> Self {
        assert_ne!(mem::size_of::<T>(), 0, "Zero sized type!");
        debug_assert!(!middle.is_null());
        RawTwoSidedVec { middle: NonNull::new_unchecked(middle), marker: PhantomData, capacity }
    }
    #[inline]
    pub fn capacity(&self) -> &Capacity {
        &self.capacity
    }
    #[inline]
    pub fn middle(&self) -> *mut T {
        self.middle.as_ptr()
    }
    /// A pointer to the start of the allocation
    #[inline]
    fn alloc_start(&self) -> *mut T {
        unsafe { self.middle.as_ptr().sub(self.capacity.back) }
    }
    fn reserve_in_place(&mut self, request: CapacityRequest) -> bool {
        let requested_capacity = request.used + request.needed;
        /*
         * If we have enough room in the back,
         * we can attempt in-place reallocation first.
         * This avoids moving any memory unless we absolutely need to.
         */
        let mut heap = Global::default();
        if !self.capacity.is_empty() && self.capacity.back >= requested_capacity.back {
            match unsafe { heap.grow_in_place(
                NonNull::new_unchecked(self.alloc_start() as *mut u8),
                self.capacity.layout::<T>(),
                requested_capacity.layout::<T>().size()
            ) } {
                Ok(actual_capacity_bytes) => {
                    self.capacity = requested_capacity.with_actual_capacity(
                        actual_capacity_bytes / mem::size_of::<T>()
                    );
                    true
                },
                Err(_) => false
            }
        } else {
            false
        }
    }
    #[inline(never)] #[cold]
    pub fn reserve(&mut self, request: CapacityRequest) {
        assert!(self.capacity.can_fit(request.used));
        let requested_capacity = request.used + request.needed;
        if !self.capacity.can_fit(requested_capacity) && !self.reserve_in_place(request) {
            unsafe {
                let reallocated = Self::with_capacity(requested_capacity);
                // Fallback to reallocating the vector and moving its memory.
                ptr::copy_nonoverlapping(
                    self.middle().sub(request.used.back),
                    reallocated.middle().sub(request.used.back),
                    request.used.total()
                );
                drop(mem::replace(self, reallocated));
            }
        }
        debug_assert!(self.capacity.can_fit(requested_capacity));
    }
}
unsafe impl<#[may_dangle] T> Drop for RawTwoSidedVec<T> {
    #[inline]
    fn drop(&mut self) {
        if !self.capacity.is_empty() {
            let mut heap = Global::default();
            unsafe {
                let layout = self.capacity.layout::<T>();
                heap.dealloc(
                    NonNull::new_unchecked(self.alloc_start() as *mut u8),
                    layout
                );
            }
        }
    }
}
#[derive(Copy, Clone, Debug)]
pub struct Capacity {
    pub back: usize,
    pub front: usize
}
impl Capacity {
    #[inline]
    pub fn empty() -> Self {
        Capacity { back: 0, front: 0 }
    }
    #[inline]
    pub fn checked_total(&self) -> usize {
        self.back.checked_add(self.front).expect("Capacity overflow")
    }
    #[inline]
    pub fn total(&self) -> usize {
        self.back + self.front
    }
    #[inline]
    pub fn can_fit(&self, other: Capacity) -> bool {
        self.back >= other.back && self.front >= other.front
    }
    #[inline]
    fn layout<T>(&self) -> Layout {
        Layout::array::<T>(self.checked_total()).expect("Capacity overflow")
    }
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.back == 0 && self.front == 0
    }
    #[inline]
    fn with_actual_capacity(&self, actual_capacity: usize) -> Self {
        assert!(actual_capacity >= self.total());
        Capacity {
            back: self.back,
            front: actual_capacity - self.back
        }
    }
}
impl Add for Capacity {
    type Output = Capacity;

    #[inline]
    fn add(self, rhs: Capacity) -> Capacity {
        match (self.front.checked_add(rhs.front), self.back.checked_add(rhs.back)) {
            (Some(front), Some(back)) => Capacity { front, back },
            _ => panic!("Capacity overflow")
        }
    }
}
#[derive(Copy, Clone, Debug)]
pub struct CapacityRequest {
    pub used: Capacity,
    pub needed: Capacity
}